Programming interview questions and answers

Find a loop in linked list and identify the looped node

A linked list has tail joined back in to the list forming a loop. Identify the looped node. For example A->B->C->D->E->F->G->H->I-NULL, has been modified so that I’s next is pointing to, let us say D. Task is to identify D. Alternatively, another question would be to find I and set it’s next to NULL to …

Find a loop in linked list and identify the looped node Read More »

Find the first occurrence of unique character in a string

Write a program to find the first occurrence of a unique character in a string For example, given a string: “aBcBcaAbBaAdAc”, b and d are unique occurrences and b is the first one. The approach:- Count each occurrence of the characters. Also whenever it is first occurrence append it to an order array. Traverse through …

Find the first occurrence of unique character in a string Read More »

Longest compound word (LCW) from a list of words

Write a program to find the longest compound word (LCW) from a list of words For example, given string list, “hello” and “ball”, “world”, “helloworld”, “morning”, “helloball”, the LCW is helloworld. In the below solution we use trie, though there are other ways to solve. Follow this C++ Tries to understand more about implementing Tries. Approach …

Longest compound word (LCW) from a list of words Read More »

Longest common substring problem

Write a program to find the longest common sub-string of two given strings The approach:- Key to the LCS problem is to generate a LCS matrix based on which the longest common sub-string could be derived. There is a cool video explaining the LCS matrix construction from Jay Liew, Security Researcher @ Websense Security Labs. The solution:- #include <iostream>#include <cstdlib>using …

Longest common substring problem Read More »