Placement test and interview puzzles

Couple of juniors have been asking me for the placements tips. Frankly, I don't have any but I can certainly help you guys out with some technical part. I solved quite a lot of puzzles during my placement season and sharing some of those with you. Here are couple of links that I think can be useful for interviews.

1. Problems(with solutions) categorized based on the companies. It has problems from interviews of companies like Google, Microsoft, Adobe, Goldman Sachs and more than hundred other companies
   http://www.careercup.com/page
   There are some useful tips other than problems as well. You may wanna check those out too.
   
2. Common puzzles asked in the interview and tests(I was asked half the questions in my interview from this problem bank).
   http://research.microsoft.com/en-us/um/people/leino/puzzles.html
3. Puzzles(with solutions) with ratings(difficulty level) for each puzzle.
   http://www.qbyte.org/puzzles/puzzle02.html

There are other collection of problems but these are the three big pool of problems I have. If you want other links(with fewer problems) contact me personally. And if you have any other useful links please comment or mail me the list so that I can include those in the list. 

(Check out the previous posts also for the problems asked in some of the interviews last year)

Just for the starter, here are a few problems which were asked in Adobe's interview. My friend Romil was asked these problems in the interview and he wrote some of them down to share with everybody .

1. You are given a binary tree and 2 data values. Find the lowest common ancestor of the two concerned nodes( Only data values are given, not pointers to nodes).
2. An array contains integers in the range 1-n. There are n-1 different numbers in the array and one is repeated. Which number is missing? Use only a single pass and don't allocate additional memory.
3. Consider the following hash function: h(x) = ((x mod 1000) div 100) + x mod 10
   What kind of values will map to the same location?
4. Output of following:
   int *i, *j;
   i = (int*)60;
   j = (int*)20;
   printf(i-j);

Here are some other random puzzles: 

1. Two players take turns choosing one number at a time (without replacement) from the set {−4, −3, −2, −1, 0, 1, 2, 3, 4}.  The first player to obtain three numbers (out of three, four, or five) which sum to 0 wins. Does either player have a forced win.
2. Consider a two dimensional grid with nodes (x,y) where x,y>0. Consider a particle initially at point (1,1). If the particle is at (x,y), it can move to either (x+y,y) or (x,x+y). Can the particle starting at (1,1) reach (m,n)? What should be the relation between such m and n?

Good Luck for the placements! I hope these links helps you with your tests.

My interview

First day, first slot, first hour, one interview and I got placed. World Quant :).

Whether I will be joining or not is still a question but it is good to have a back up. Rest of the week was awesome. Many parties with friends, couple of good moments with them. One of which I will never forget

" Agar aap ATM se 1024 rupay download karte hain, to heap me allocate hue variable ki kasam aap CS vaale hain"

Overall, It was a fun week.

For those of you who have not been placed or those who have placements next year, here are the questions they asked me in the interview. These are not much but will give you a flavor of the kind of questions they will ask you in the interview.

1. There are five points in an equilateral triangle of side length 1. Prove that there are two points with distance less than 1/2.

2. There are three primes p1,p2,p3 each greater than 20. Sum of these primes is 256. How many such pairs are possible.

3. There are hundred people in the class room. Everybody picks a number from 0 to 100 including 0 and 100. I take the average of all the number and multiply that by 2/3, call it m. Person with number closest to m wins. If you were in the class room, what number will you pick?
You can assume that everybody is as intelligent as you.

4. You have nine digits 1,2,..9. Make two numbers using these digits exactly once such that product of the two numbers is maximum. Eg. 4321 x 95768.

I couldn't do it in the interview(my guess was wrong).

5. This is a very common puzzle that everybody would have done.

There are hundred people standing in a line. Each person is wearing a hat of color black or white. Each person can see the hats of all the people ahead of him in the line. Now, Antariksh comes and ask each person: " what is the color of your hat?". If a person answers correctly then ant gives him a chocolate else ant kills the poor guy. Ant starts from the last person in the line.

What should be the strategy of the guys in the line so that maximum chocolates are collected?

Google Test

1. Give an efficient algorithm to generate the numbers of the form 2^i x 3^j x 5^k x 7^l in ascending order given i,j,k,l >= 0 and are integers.

2. Given a 2^n x 2^n chessboard and an infinite number of L shaped tiles (of size 2x2) which may be rotated and placed, is it possible to tile the entire chessboard leaving just a single gap?

3. Find the minimum number of comparisons required to find the minimum and maximum element in the array of 20 elements.

4. Jack and his wife went to a party where four other married couples were present. When Jack asks everyone (including his wife) how many hands they shook. He gets all different answers. No person shakes hands with their partners.

How many hands did Jack's wife shake?

Here are few more questions asked by google:

http://www.divye.in/2010/12/google-interview-questions-and-google.html

Goldman + DB

1. I have a polynomial with positive integer coefficient. You can ask me question "what is the value of the polynomial at x".

What is the minimum number of questions required to find out the polynomial.

2. You toss a coin until you get n consecutive heads. What is the expected number of tosses?

3 A random walk is a sequence of numbers R(n) such that R(n)=R(n-1)+1 with probability half and R(n)=R(n-1) -1 with probability half. Equivalent consider a particle on number line. It can move to left or right with probability half. R(0)=0 i.e. particle starts at 0.

Let N_b be the first integer n such that R(n) = b i.e particle visited the integer b for the first time.

i) Find P(N_b < t).

(I don't remember the other parts. Somebody please post the rest).

4. You have a deck of cards from which you pick a card without replacement until an ace is picked(any of the four ace). Find the expected number of picks.

Morgan Stanley

Here are few puzzles asked in the Morgan Stanley's test yesterday:

1. i) Prove that Trace(A) = sum of eigen values.

ii) If Trace(A)=1, Trace(A^2)=3, Trace(A^3)=9, then find the value of det(A).

2. You have a square matrix of size N x N. From each block you can move to any of the 8 adjacent blocks. Moving to one particular block(zero cost direction) has a cost of zero. Moving to rest of the 7 blocks has cost 1. You have been given two points S and E. You have been also given the zero cost direction for each block. Give an efficient algorithm to find the optimal path from S to E.

3. You have been given [m(m-1)^2+1] points in a Cartesian plane. Each the these points is an integer point i.e. both x and y co-ordinates are integer. Prove that you can always find m points such that centroid of those m-points is also integer point.

4. Let A be a array of integers. Find the minimum of all k-consecutive elements in O(n) time.

Ex: if A=[2 3 5 1 3 5 6] and k=3 then your answer should be [2 1 1 1 3].

Two fathers and their sons

Good to see so many people actually trying out puzzles I posted. Seeing more than 600 hits in 5 days(200 on Sunday) was quite impressive.

Thanks for the suggestions especially regarding the last two posts. For many of you those were very easy puzzles but main motive behind those was to get away from the mathematical point of view and think in a slightly different way. So, if those are easy, then lets solve some easy puzzles.

Some also asked about the solutions of the puzzles I have posted. To solve that problem, I will request the puzzle solvers to put your solutions on the blog rather than discussing it on the chat with me. This way, many people might benefit from your solutions and also, I won't have to write all the solutions by myself.

Here are few more puzzles. Have fun solving puzzles!

1. In a rectangle that's 2 by 200 units long, it's trivial to draw 400 non-overlapping unit-diameter circles. But in the same rectangle, can you draw 401 circles? (non-overlapping, unit-diameter.)

2. Two fathers took their sons to a fruit stall. Each man and son bought an apple, But when they returned home, they had only 3 apples. They did not eat, lost, or thrown. How could this be possible?

3. If F(n) denotes the nth Fibonacci number. Then, prove that F(k*n) is a multiple of F(k).

Please leave your solutions as comments. Thanks!

Logic Puzzles-2

1. Four angels sat on the Christmas tree amidst other ornaments. Two had blue halos and two – yellow. However, none of them could see above his head. Angel A sat on the top branch and could see the angels B and C, who sat below him. Angel B, could see angel C who sat on the lower branch. And angel D stood at the base of the tree obscured from view by a thicket of branches, so no one could see him and he could not see anyone either. Which one of them could be the first to guess the color of his halo and speak it out loud for all other angels to hear?

2. Three Palefaces were taken captive by a hostile Indian tribe. According to tribe’s custom they had to pass an intelligence test, or die. The chieftain showed 5 headbands – 2 red and 3 white. The 3 men were blindfolded and positioned one after another, face to back. The chief put a headband on each of their heads, hid two remaining headbands, and removed their blindfolds. So the third man could see the headbands on the two men in front of him, the second man could see the headband on the first, and the first could not see any headbands at all.
According to the rules any one of the three men could speak first and try to guess his headband color. And if he guessed correctly – they passed the test and could go free, if not – they failed. It so happened that all 3 Palefaces were prominent logicians from a nearby academy. So after a few minutes of silence, the first man in the line said: "My headband is ...".
What color was his head band? Why?