How can you answer on tricky algorithmic questions when you have lack of time. The secret to success with this free-form question is to focus and practice. Never “wing it.” What do you want the interviewer to remember most about you? List five strengths you have that are pertinent to this job: experiences, traits, skills, personality etc. Because if you prepare for the tough interview questions ahead of time, you’ll likely do very well and actually enjoy the process.The main idea of this article is make your brain think rapidly. Also increase creativity and grow yourself to broad-minded person.
“Like snowflakes, no two people are alike. Take some time to think about what sets you apart from others,” advises Martin.
Here the list of top 15 tricky algorithm Interview questions that you can be prepared to.
1. Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife?
Join the centers of the original and the removed rectangle. It works for cuboids too! BTW, I have been getting many questions asking why a horizontal slice across the middle will not do. Please note the “any size or orientation” in the question! Don’t get boxed in by the way you cut your birthday cake 🙂 Think out of the box.
2. There are 3 baskets. one of them have apples, one has oranges only and the other has mixture of apples and oranges. The labels on their baskets always lie. (i.e. if the label says oranges, you are sure that it doesn’t have oranges only, it could be a mixture) The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets.
HINT. There are only two combinations of distributions in which ALL the baskets have wrong labels. By picking a fruit from the one labeled MIXTURE, it is possible to tell what the other two baskets have.
3. Why is a manhole cover round?
HINT. The diagonal of a square hole is larger than the side of a cover! Alternate answers: 1. Round covers can be transported by one person, because they can be rolled on their edge. 2. A round cover doesn’t need to be rotated to fit over a hole.
4. One train leaves Los Angeles at 15mph heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
HINT. Think relative speed of the trains.
5. You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?
1. Mark the jars with numbers 1, 2, 3, 4, and 5.
2. Take 1 pill from jar 1, take 2 pills from jar 2, take 3 pills from jar 3, take 4 pills from jar 4 and take 5 pills from jar 5.
3. Put all of them on the scale at once and take the measurement.
4. Now, subtract the measurement from 150 ( 1*10 + 2*10 + 3*10 + 4*10 + 5*10)
5. The result will give you the jar number which has contaminated pill.
6. There are four dogs/ants/people at four corners of a square of unit distance. At the same instant all of them start running with unit speed towards the person on their clockwise direction and will always run towards that target. How long does it take for them to meet and where?
HINT. They will meet in the center and the distance covered by them is independent of the path they actually take (a spiral).
7. If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
We can pour water back and forth between the two jugs as follows:
OBSERVATIONS AND SUGGESTIONS: »»Many brain teasers have a math / CS root to them—this is one of them! Note that as long as the two jug sizes are relatively prime (i.e., have no common prime factors), you can find a pour sequence for any value between 1 and the sum of the jug sizes.
8. You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?
9. Which way should the key turn in a car door to unlock it?
10. If you could remove any of the 50 states, which state would it be and why?
11. How many cars are there in the USA?
12. You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weightings how do you find the defective one?
13. You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
14. You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked?
What are the exact odds of getting a red marble using your scheme?
15. Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
"Can you tell me about yourself?"
"Your answer to this question sets the tone for the rest of the interview.
"Practice your script until you feel confident.
Your script will help you stay on track, but don't memorize it -- you'll sound stiff.
Instead, aim for a natural and conversational tone".
"What are your long-term goals?"
This and other open-ended questions, like: "Where do you see yourself in five years?"
can throw you off balance.
The employer wants to check your self-awareness and communication skills here.
"If you're an organized type of person, answering this question may be a piece of cake.
If not, you'll need to give your answer some forethought."
The best answers will come from you thinking about what you want.
Most successful employers believe that a key success factor is
the ability to set and achieve goals.
So begin by setting short-term goals for yourself.
Right now your goal may be to get a job. But, what kind of job?
And, where do you go from there?
"No one can tell you exactly how to answer this question --
it will come from what is important to you. However, the more
focused and employer-centered you are about your goal,
the better your chances of steering the interview in the right direction".
"Why should we hire you?"
This is another broad question that can take you down the wrong road
unless you prepare thoroughly.
This is about selling yourself as a product. Why should the customer buy?
"Develop a sales statement. The more detail you give, the better.
This is not a time to talk about what you want.
It is a time to summarize your accomplishments and relate what makes you unique,"
Start by looking at the job description or posting.
What is the employer stressing as requirements of the job?
What will it take to get the job done? Make a list of those requirements.
Next, do a personal inventory. Think of two or three key qualities you have
that match what the employer is seeking.
Don't underestimate personal traits that make you unique -- your energy,
personality type, working style and people skills, for example.
Three students checked into a hotel and paid the clerk $30 for a room ($10 each). When the hotel manager returned, he noticed that the clerk had incorrectly charged $30 instead of $25 for the room. The manager told the clerk to return $5 to the students. The clerk, knowing that the students would not be able to divide $5 evenly, decided to keep $2 and to give them only $3.
The students were very happy because they paid only $27 for the room ($9 each). However, if they paid $27 and the clerk kept $2, that adds up to $29. What happened to the other Dollar?
There is a saying that you cannot add apples and oranges. If you have 3 apples and 2 oranges do you have 5 apples? No. Do you have 5 oranges? No. You have five fruits, but the number of apples and oranges has not changed. Similarly, you cannot add real money and “what they think they paid”.
When we count only real money, the students have $3, the clerk has $2, and the manager has $25. That is $30 total.
| Accounting of Real Money | ||
|---|---|---|
| Before | After | |
| Student #1 | $10.00 | $1.00 |
| Student #2 | $10.00 | $1.00 |
| Student #3 | $10.00 | $1.00 |
| Clerk | $0.00 | $2.00 |
| Manager | $0.00 | $25.00 |
| Total | $30.00 | $30.00 |
1. A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2.
2. Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.
#include<stdio.h>#define bool int/* Function to check if x is power of 2*/bool isPowerOfTwo(int n){ if(n == 0) return 0; while(n != 1) { n = n/2; if(n%2 != 0 && n != 1) return 0; } return 1;} /*Driver program to test above function*/int main(){ int test_no = 31; if(isPowerOfTwo(test_no)) printf("%d is a power of 2", test_no); else printf("%d is not a power of 2", test_no); getchar();} |
3. All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2. Please see http://geeksforgeeks.org/?p=1176 for counting set bits.
4. If we subtract a power of 2 numbers by 1 then all unset bits after the only set bit become set; and the set bit become unset.
For example for 4 ( 100) and 16(10000), we get following after subtracting 1
3 –> 011
15 –> 01111
So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on value of n&(n-1). The expression n&(n-1) will not work when n is 0. To handle this case also, our expression will become n& (!n&(n-1))
Below is the implementation of this method.
#include<stdio.h>#define bool int/* Function to check if x is power of 2*/bool isPowerOfTwo (int x){ /* First x in the below expression is for the case when x is 0 */ return x && (!(x&(x-1)));}/*Driver program to test above function*/int main(){ int test_no = 15; if(isPowerOfTwo(test_no)) printf("%d is a power of 2", test_no); else printf("%d is not a power of 2", test_no); getchar();} |
Example:
1
/ \
2 3
/ \ / \
4 5 6 7
The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
Implementation:
void get_Vertical_Sum(Tree* T,int[] sum,int column)
{
if(T==NULL)
return;
else
{
verticalSum[column]+=T->data;
get_Vertical_Sum(T->left,column-1);
get_Vertical_Sum(T->right,column+1);
}
}
Example:
5 / \ 3 8 / \ / \ 1 4 6 10
for this tree a[0]=5, a[1]=11, a[2]=21…..
Implementation:
void get_Horizontal_Sum(Tree* T,int[] sum,int level)
{
if(T==NULL)
return;
else
{
sum[level]+=T->data;
get_Horizontal_Sum(T->left,level+1);
get_Horizontal_Sum(T->right,level+1);
}
}
Given a number x and two positions (from right side) in binary representation of x, write a function that swaps n bits at given two positions and returns the result. It is also given that the two sets of bits do not overlap.
Examples:
Let p1 and p2 be the two given positions.
Example 1 : –
Input:
x = 47 (00101111)
p1 = 1 (Start from second bit from right side)
p2 = 5 (Start from 6th bit from right side)
n = 3 (No of bits to be swapped)
Output:
227 (11100011)
The 3 bits starting from the second bit (from right side) are
swapped with 3 bits starting from 6th position (from right side)
Example 2 : –
Input:
x = 28 (11100)
p1 = 0 (Start from first bit from right side)
p2 = 3 (Start from 4th bit from right side)
n = 2 (No of bits to be swapped)
Output:
7 (00111)
The 2 bits starting from 0th postion (from right side) are
swapped with 2 bits starting from 4th position (from right side)
Solution
We need to swap two sets of bits. XOR can be used in a similar way as it is used to swap 2 numbers. Following is the algorithm.
1) Move all bits of first set to rightmost side
set1 = (x >> p1) & ((1U << n) – 1)
Here the expression (1U << n) – 1 gives a number that
contains last n bits set and other bits as 0. We do &
with this expression so that bits other than the last
n bits become 0.
2) Move all bits of second set to rightmost side
set2 = (x >> p2) & ((1U << n) – 1)
3) XOR the two sets of bits
xor = (set1 ^ set2)
4) Put the xor bits back to their original positions.
xor = (xor << p1) | (xor << p2)
5) Finally, XOR the xor with original number so
that the two sets are swapped.
result = x ^ xor
Implementation:
#include<stdio.h>int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n){ /* Move all bits of first set to rightmost side */ unsigned int set1 = (x >> p1) & ((1U << n) - 1); /* Moce all bits of second set to rightmost side */ unsigned int set2 = (x >> p2) & ((1U << n) - 1); /* XOR the two sets */ unsigned int xor = (set1 ^ set2); /* Put the xor bits back to their original positions */ xor = (xor << p1) | (xor << p2); /* XOR the 'xor' with the original number so that the two sets are swapped */ unsigned int result = x ^ xor; return result;}/* Drier program to test above function*/int main(){ int res = swapBits(28, 0, 3, 2); printf("\nResult = %d ", res); return 0;} |
Output:
Result = 7
Following is a shorter implementation of the same logic
int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n){ /* xor contains xor of two sets */ unsigned int xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1); /* To swap two sets, we need to again XOR the xor with original sets */ return x ^ ((xor << p1) | (xor << p2));} |
Riddle1 :
A room contains a group of people . One of them is a celebrity.Celebrity doesn’t know any one in the room.All the non celebrities know celebrity. Some non celebrities may know some other non celebrities but the converse is may or may not be true. Every person in the room knows himself. How do you find the celebrity ?
Answer1 :
STEP 1. Ask any random person, the people he knows.
If he does not know anyone then that person = celebrity
If he knows some people .Update set known. {known is a set of person he knows}
STEP 2. Then the go in the known set & repeat step 1.
Repeat step 2 until Known = celebrity
Riddle2 :
A man has two cubes on his desk. Every day he arranges both cubes so that the front faces show the current day of the month. What numbers are on the faces of the cubes to allow this?
Answer2 :
0,1,2,3,4,5 (cube1)
0,6,7,8,1,2 (cube2)
This problem goes back a number of years and is used to demonstrate how angry people can get when they don’t agree with an answer. Each time this problem appears in the press it generates thousands of letters from people who disagree with the solution. So the message here is don’t try this problem at home.
The problem also demonstrates the need to draw diagrams to be certain that your testing is not negatively influenced by preconceived ideas. Here’s the problem:
There are three doors. One of the doors has a very valuable prize behind it. If you can guess which door conceals the prize, it is yours. Whichever door you choose we’ll call it door number 1. The game show host, who knows exactly where the prize is located now opens one of the remaining doors which he knows has nothing behind it. Note: he is not opening a door at random, but is deliberately opening a door that has no prize behind it. The door just opened we’ll call door 2.
Now you are facing the 2 remaining doors. The one you originally chose and the remaining closed door. You are now asked whether you want to keep door 1, the choice you originally made or switch to door 3, the other closed door.
Do you maximize your chances of winning by switching doors, staying with your first choice, or does it not make any difference?
Answer: Switching to door 3 increases the probability of winning the prize from 1/3 to 2/3. If you think that the problem really involves 2 doors and 1 prize then the odds must logically be 50-50. But opening a door with full knowledge of what is behind it does not add any information to the problem and the probabilities do not change.
When all three doors were closed, there was a one out of three (1/3) probability of the prize being behind the door you chose. There was a two out of three (2/3) probability that the prize was behind one of the other two doors.
Now door 2 is opened, and the probabilities do not change. Since you obviously won’t choose the open door, the odds are in your favor to choose door 3.
Another way to view the problem is to imagine another person entering the room and seeing two closed doors and one open door. If this person is asked about the odds of finding the prize the chances are 50-50. But if the person is allowed to ask you one question, they will ask which door you chose first. That one clearly had a 1/3 probability of being correct and they will select the other door.
A decision table may also be helpful because it identifies all of the possible conditions:
| Original Selection | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |
| Prize Location | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
| Keep Original Door Choice | W | L | L | L | W | L | L | L | W |
| Switch Door Choice | L | W | W | W | L | W | W | W | L |
W = Win, L = Lose
| Note that switching your selection results in winning twice as often as staying with the original selection. |
I gathered some of the important and top interview questions of Google from different people interviews. I hope This post helps those who are preparing for the Google Interview.
1.There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve it without division operator and in O(n).
2.There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
Hint:
i)Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
ii)It should be done in O(n).
3.Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
4.You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.
Note:Some position may be blank in the game। So your data structure should
consider this condition also.
5.You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
6.How do you put a Binary Search Tree in an array in a efficient manner.
Hint: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.
7.How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
8.Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn
9.Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
10.Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
11.How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?
12.Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ?
13.Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
14.Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal – anybody in for writing some code
15.You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
16.Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
17.Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
18.Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
19.Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
20.Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
21.Given an array,
i) find the longest continuous increasing subsequence.
ii) find the longest increasing subsequence.
22.Write a function to find the middle node of a single link list.
23.Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
26.Implement put/get methods of a fixed size cache with LRU replacement algorithm.
27.You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))”
Please give a solution in O(n) time complexity
28.Classic – Egg Problem
You are given 2 eggs.You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
You can discuss these puzzles in comments.if you have any more Google puzzles which are interesting and frequently asking in interviews comment it, i will add to the above 27 puzzles.
dopuzzles 