Given two set , 1st one is of 1 to n numbers where n is very very large say this set T and other set is very small contains only number {3,5,7} , Now generate all number from set T (bigger) except element in smaller set , with "equal probability" , you have given rand function , also minimize the call to rand function so solve it in most optimal way

Given a BST, maximum and minimum value, find the sum of nodes with values between the above range

Given 2 arrays A,B, where x(A.length) < y(B.length), we want to insert (y - x) 0's to A at various places such that A*B is minimum. For instance, if A = (1, -1) and B = (1,2, 3, 4), then inserting two 0's in the middle of A such that A = (1, 0, 0, -1) would minimize

assume that dictionary has only 5 words... APPLE,APE,BABY,BALL,CAT write a program which will accept a string and list all possible words in the dictionary which start with that string.

Say you have an HTML file which contains more than 100,000 characters. How do you extract all the Phone Numbers from it

Given a website you have to find number of hits in the last second, last minute and last hour.

Given a signature, compute the lexicographically smallest permutation of [1,2,....n].

You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.   vector* FindPermute(const string& signature);

This is another good one from google easy though :)

Find All subsubsequence of size r in given array of length n

Given a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j. Hint :- If the average of two numbers is not an integer then we can assume that they do not have an average.

One possible solution  i can think of is  divide the array in two parts , odd and even , sort them and use be.low algo , like if we have the array say N=10 and array is 3 10 2 7 5 3 4 6 9 8 1 after dividing and sorting
array will be 1 3 5 7 9 2 4 6 8 10
now calculate length of even and odd list ,if length is odd,then divide it into 2 equal parts and align alone one middle value like
1 3 5 7 9 2 4 6 8 10
now swap all values of two list except first value based on middle if each sub-list
1 7 5 3 9 2 8 6 4 10

i have not coded it yet so feel free to comment if it fails for any test case :)

How would you implement trending topics for twitter. Think at large scale as well.