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 »

Primes below a given number

Find number of prime numbers below a given number One could test for prime, from 4 till the given number and count those numbers. This does not need extra memory but slow. Below we provide solution which is fast but needs memory. This is using Sieve of Eratosthenes method. Approach:- Have a memory allocated for …

Primes below a given number 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 »