Some more puzzles

A person can take one or two steps at a time to reach a particular floor( say in a building). How many different ways can a person reach the nth floor?

Given a 2D plane, suppose that there are around 6000 points on it. Find a line which passes the most number of points.

Given a Starting Node and Ending Node in a Graph where each Node has a pointer to its parent and all its children nodes. Find all the leaf nodes between the Starting and Ending Node.

Given a puzzle of letters/ characters e.g.
a e r o p s
b h a r l s
w r i s l o
a s n k t q
Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.
  

A duck, pursued by a fox, escapes to the center of a perfectly circular pond. The fox cannot swim, and the duck cannot take flight from the water (it’s a deficient duck). The fox is four times faster than the duck. Assuming the fox and duck pursue optimum strategies, is it possible for the duck to reach the edge of the pond and fly away without being eaten? If so, how?

Implement memcpy(void* src, void* dst, int len) and memmove

Count number of bits (check mit hack mem or any other method with constant time)

reverse bits in a number

reverse bytes in a number

check whether binary representation is palindromic or not

find max rectangle under a histogram

you have a bag full of airplane tickets with various destinations. given two destinations find those tickets in the bag and give the cheapest routing in the least time possible

There are N egg baskets and the number of eggs in each basket is a known quantity. Two players take turns to remove these eggs from the baskets. On each turn, a player must remove at least one egg, and may remove any number of eggs provided they all belong to the same basket. The player picking the last egg(s) wins the game. If you are allowed to decide who is going to start first, what mathematical function would you use to decide so that you end up on the winning side? ( hint game of nim )

given a 3 number discrete random number generator {1,2,3} , how can you design a 5 number random generator ? What is the average number of trials necessary ?

given an array of n elements, find if there is a subset of 3 elements sum up to value T with time complexity O(nlgn).( approximation algo for subset sum)

Given a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?

Write an algorithm to find out how many different summations you can compute using numbers range from 1 to 1000. 2 constrains
1) Each valid sum must be less than 10000
2) A number can only be used once for a sum
example:
1+2+300 < 10000 is valid
1+2+300+400 < 10000 is valid
1+2+2 is not valid (2 appear twice)

Given a set of points (x,y) on a 2D coord system, identify list of 2D coords that are of distance less than x units long.

Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum???? (karmakar karp algo)

Give two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm to let n-1 cars in P1 and P2 park in the same slots

Find the next in order node of given node in binary tree. Write the program of same. pointer to parent node is given.

You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall.
For example you are given Sbig = "hello what are you doing"
Ssmall= "eo"
answer is "ello"

how to implement a queue using one integer. this should store value 0 to 9. example suppose queue has first value 2 then insert 4 then 6 so it should look like 246. first value should be popped as 2. then it should be 46. program should support 0 in all the levels also. example queue should handle like 01235 also, 0 as first value in queue. remember 0 just to use integer, nothing else as data storage.

Given an array of 'n' random integers. Given an integer 1<=n. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum (maximum among other minimum differences for various possible selections of k numbers ).

You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

You need to organize a football tournament. There are n teams given. You need to prepare a schedule for the matches so that each team plays with every other team and on the same day no team plays twice. You want to finish the tournament as early as possible.

There is a stream of numbers, design an effective datastructre to store the numbers and to return the median at any point of time.

Some Puzzles

1) find median of two sorted array
2) intersection of two set
3) union of two set
4) given a n*n matrix row and column are sorted in ascending order , given an element find its position
5) same as 4 containg -ve also, find number of -ve
6) same as 4 print the matrics in sorted order
6) longest palindromic substring
7) longest repeatative word
8) loop in a linked list, with proof, delete, and count number of nodes
9) merge two sorted linked list without creating new
10) least common ancestor of a bst/binary tree
11) reverse a stack
12 ) implement queue using a single stack
13) caching techniques
14) closest pairs of points in a plane
15) kth smallest element in most optimum way
16) reservior sampling
17) max submatrix of a n*n matrics
18) an array contains three color balls red,green and blue. sort the array in such a way so that all red will be in the begining, all blue will be in middle and green will be at the end
19) check a graph is circular or not
20) how do you serialize a graph/tree
21) design a deck of card with shuffling algo(knuth shuffling algo)
22) design a parking station
23) how will you design stl vector
24) design a traffic signal
25) design a garbage collector
26) sort nuts and bolts you don't have anything to measure the lenght
27) there are 25 horses, 5 horse can run at a time, you dont have watch to measure time, find top 3 horses, in mim numbr os races
28) load balancing techniques