# interview questions

## Interleaving Strings

Problem Statement This is a question from one of the interview experiences. The statement, "Given three strings A, B and C find if C is an interleaving of A and B." Interleaving is defined as below: A string C is said to be an interleaving of two strings A and B if C contains a sub sequence of A and B such that the relative order of characters in A and in B are preserved in C. For e.g. : A - ABCD B - BACDX C - ABACDXBCD The Idea - Interleaving Strings Here I am not giving any solution which is less than O(M*N) solution where M is the length of the shortest string among A and B...

## Find Frequency In Sorted Array

Problem Statement This is a question from one of the interview experiences. You are given a sorted array of numbers (this can be extended for arrays of characters, strings and what not) and a number K. Find the number of occurrences of K in the array. Solution Yes you got that right, it is really very simple. Walk through the array sequentially and if you get K then start counting till you get anything bigger than K. You can break out of the loop after this and the counter will tell you the obvious answer. So, why am I even writing this post? Because this is not fun, the above approach te...

## Find Pair of Numbers in Array with a Given Sum

Problem Definition This problem has appeared in many interviews as well as the qualifying round of Google Code Jam in the past. There are various versions of the problem. To list a few: Find Pair of Numbers in Array with a Given Sum - The array is unsorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array is sorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array contains unique numbers only. In all the above versions, we have to return the ...