# Programming interview questions and answers

## Towers of Hanoi

Approach to solve the Towers of Hanoi game We need to move the n rings from the first pole to target third pole using the second pole as buffer. First move the n-1 rings from first to a second pole using the third. Then move the remaining big ring from first to the third. Now …

## 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 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 number occurring odd number of times

There is an array of numbers, where each number occurs even number of times except for one number which occurs odd number of times. Find out the number. When you XOR a number even number of times, it becomes zero. So XOR all the numbers in the array, the result will be the number which …

## Find a missing number in sorted number list

You are given a sorted number list from 0 to n. The list is missing one number, find out that number We can run a binary search. Check the value in the middle, and see if the index of it is same as the value. If it is not, then 0 to mid range has …

## 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 …

## Next number formed from permutation of digits

Write a program to find the next number formed from permuting the digits in a given number For example if the given number is 312, then the next number is 321 if you permute 1,2,3. Start to looking at digits one by one from 1’s digit towards left. Check that digit value to its immediate …

## Implement LRU cache with O(1) operations

Implement LRU cache with O(1) operations LRU –> Least Recently Used cache is method where in when cache size is full to accommodate for new page, it will unload least recently used page. The approach To access the pages in the LRU cache, to have O(1) operation, good to go for hash table. How do …

## 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 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 …