Programming puzzles, riddles and interview problems | TechInterviews
lassic: If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear.
ANS. The color of the bear is trivial. The possible solutions to it are interesting. In addition to the trivial north pole and circle near north pole solutions, there is an additional circle near south pole solution. Think it out.
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?
ANS. Join the centers of the original and the removed rectangle. It works for cuboids too!
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. 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 weighings how do you find the defective one?
Answer from Uday Venkat: weigh three balls against another three balls. if both weigh the same , then just weighing the remain two (one against one) will show the lighter ball. if the sets of three do not weigh equal, then weigh any two balls in the lighter set, one against the other . the balance will show if the lighter one is on the balance,if not the remaining one is the lighter one.
8= (3 + 3 ) + 2
(the numbers in the brackets are balls on either side of the balance)
if both are equal, then
2= (1 + 1) done.
else, from the lighter set of 3
3= (1 + 1) + 1 done.
4. 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.
5. How many cars are there in the USA?
6. 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?
ANS from Madhuri Chandoor:
Break the 7 piece gold bar to make a piece of 1 segment size and the other of 2 segments size.( the remaining 4 segments intact)
i.e 7= 1 + 2 + 4 (only two breaks needed)
1- 1st day
2- 2nd day
(1+2) - 3rd day
4 - 4th day
(4+1) - 5th day
(4+2) - 6th day
(4+2+1) - 7th day.
11. If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
ANS from Madhuri Chandoor:
Fill 5 quarts pail and use that water to fill the 3 quarts pail. now there are 2 quarts in the 5 quart pail. repeat this twice to get 4 quarts.
If there is no extra pail available to hold these 2 quarts + 2 quarts, then the following is the solution.
Fill the 5 quart pail and pour it into the 3 quart pail. now there are 2 quarts remaining in the 5 quart pail. empty the 3 quart pail and pour these 2 quarts into the 3 quarts pail. now the 3 quart pail is 1 less to be filled up. now fill the 5 quarts pail and pour 1 quart into the 3 quarts pail to fill it. the 5 quarts pail has 4 quarts in it now.
12. 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?
ANS from Madhuri Chandoor:
To be sure, to pick atleast 2 marbles of a same color we need to grab at least 4 marbles, since the worst case is that three of them are different, the fourth marble has to be a repetition of one of three colors.
9. 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?
10. 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?
ANS. 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 measurment 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.
11. If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
12. 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?
13. Which way should the key turn in a car door to unlock it?
14. If you could remove any of the 50 states, which state would it be and why?
15. 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 centre and the distance covered by them is independent of the path they actually take (a spiral).
16. (fram Tara Hovel) A helicopter drops two trains, each on a parachute, onto a straight infinite railway line. There is an undefined distance between the two trains. Each faces the same direction, and upon landing, the parachute attached to each train falls to the ground next to the train and detaches. Each train has a microchip that controls its motion. The chips are identical. There is no way for the trains to know where they are. You need to write the code in the chip to make the trains bump into each other. Each line of code takes a single clock cycle to execute.
You can use the following commands (and only these);
MF - moves the train forward
MB - moves the train backward
IF (P) - conditional that's satisfied if the train is next to a parachute. There is no "then" to this IF statement.
GOTO
ANS.
A: MF
IF (P)
GOTO B
GOTO A
—–
B: MF
GOTO B
Explanation: The first line simply gets them off the parachutes. You need to get the trains off their parachutes so the back train can find the front train's parachute, creating a special condition that will allow it to break out of the code they both have to follow initially. They both loop through A: until the back train finds the front train's parachute, at which point it goes to B: and gets stuck in that loop. The front train still hasn't found a parachute, so it keeps in the A loop. Because each line of code takes a "clock cycle" to execute, it takes longer to execute the A loop than the B loop, therefore the back train (running in the B loop) will catch up to the front train.
Personality
It is best to read some website or a book for questions like these.
1. Tell me the courses you liked and why did you like them.
2. Give an instance in your life in which u were faced with a problem and you tackled it successfully.
3. What is your ideal working environment. ( They usually to hear that u can work in group also.)
4. Why do you think you are smart?
5. Questions on the projects listed on the Resume.
6. Do you want to know any thing about the company.( Try to ask some relevant and interesting question).
7. How long do u want to stay in USA and why?
8. What are your geographical preference?
9. What are your expectations from the job.
Algorithms and Programming
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 ?
2. You're given an array containing both positive and negative integers and required to find the subarray with the largest sum (O(N) a la KBL). Write a routine in C for the above.
3. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like. [ I ended up giving about 4 or 5 different solutions for this, each supposedly better than the others ].
4. Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all. [ This one had me stuck for quite some time and I first gave a solution that did have floating point computations ].
5. Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal. [ I gave the obvious solution of taking % 10 and / 10, which gives us the decimal value in reverse order. This requires an array since we need to print it out in the correct order. The interviewer wasn't too pleased and asked me to give a solution which didn't need the array ].
6. Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]
7. Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.
8. How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started.
9. Give a very good method to count the number of ones in a 32 bit number. (caution: looping through testing each bit is not a solution).
10. What are the different ways to say, the value of x can be either a 0 or a 1. Apparently the if then else solution has a jump when written out in assembly. if (x == 0) y=0 else y =x There is a logical, arithmetic and a datastructure soln to the above problem.
11. Reverse a linked list.
12. Insert in a sorted list
13. In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this give a gast way to generate the moves by the computer. I mean this should be the fasteset way possible. The answer is that you need to store all possible configurations of the board and the move that is associated with that. Then it boils down to just accessing the right element and getting the corresponding move for it. Do some analysis and do some more optimization in storage since otherwise it becomes infeasible to get the required storage in a DOS machine.
14. I was given two lines of assembly code which found the absolute value of a number stored in two's complement form. I had to recognize what the code was doing. Pretty simple if you know some assembly and some fundaes on number representation.
15. Give a fast way to multiply a number by 7.
Read full article from Programming puzzles, riddles and interview problems | TechInterviews
No comments:
Post a Comment