Logic Interview Questions | Glassdoor

# Logic Interview Questions

86

interview questions shared by candidates

## Logic Interview Questions

Sort: RelevancePopular Date

Mar 11, 2009

### Software Engineering Summer Intern at Facebook was asked...

Mar 30, 2010
 25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 9 AnswersWe can do it in seven races, we'll call them races A-F. For notation, we'll say that the Nth horse in race X is called X.N. Races A-E: Divide the horses into 5 groups of 5 each such that each horse races only once. We can eliminate the slowest 2 horses in each of the five races because there are definitely 3 horses faster in each case. As a result, we eliminate 5x2 = 10 horses: {A.4,A.5,B.4,B.5,C.4,C.5,D.4,D.5,E.4,E.5} Race F: Race the fastest horses in each race A-E: {A.1, B.1, C.1, D.1, E.1}. To simplify notation, we'll label F.1 as horse A.1, F.2 as horse B.1, and so forth. That means the winner of this race is A.1, and it is the fastest horse of all. We don't have to race A.1 anymore. We can eliminate D.1 and E.1 = 2 horses. Because they are not in the top 3. As a result, we know that all remaining horses from D and E are eliminated. This is D.2,D.3,E.2,E.3 = 4 horses. We know that A.1,B.1, and B.2 are all faster than B.3 (and similar for C.3) so they are not in the top 3.We can eliminate B.3 and C.3 = 2 horses. Finally, we know that A.1 is faster than B.1, which is faster than C.1, and thus C.2, so we can remove C.2 = 1 horse. Race G: We have removed 19 horses from competition and are sure that A.1 is the fastest horse of them all. This leaves just 5 horses: {A.2,A.3,B.1,B.2,C.1}. We race them and select the top 2 to join A.1 as the top 3 fastest horses.just run them all on the one track :) one race, and you get your 3 fastest horses in one go........or am I missing something!6 races. Divide 25 horses into 5 groups. Each group races and the fastest is selected. The winner of each of the 5 races all race together. Pick Top 1,2 and 3. My only concern: Could the answer be this simple?Show More ResponsesB, you're mistaken. Imagine the top three fastest horses are Santa's Little Helper, Yojimbo, and I'm Number One. By random luck, in your first race, the five random horses you choose includes all three of those. I'm Number One wins and goes on to the final race; the other two do not.8 5 top horses from each race of 5 races (25 / 5) 5 top contenders race; 1 wins--that's one top horse (5-1) 4 remaining top horses race, one wins; that's 2 top horses (4-1) 3 remaining top horses contend; winner is #3 That's 3 top horses from 8 racesRace#1 Race#2 Race#3 Race#4 Race#5 A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Race#6 A1 B1 C1 D1 E1 Let's Say ranking 1st 2nd 3rd 4th 5th Eliminate D1 E1 D2 E2 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Left with B1 C1 A2 B2 C2 A3 B3 C3 Eliminate C3 as there are more than three faster horses C2, C1, B1, A1 Eliminate C2 as there are three faster horses C1, B1, A1 Eliminate B3 as there are three faster horses B2, B1, A1 Left with 5 horses for Race#7 B1 C1 A2 B2 A3 So 7 races7 races. put 25 horses in 5 group. and we will have 5 sorted list of horses in each group. put 1st place horse in each group, and we will have a sorted list X. X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate. 2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse.8the answer is one race as the question doesn't specify all the horses have to run in separate races.

### Candidates Day Interviews for Multiple Areas (X-Div/Back Office) at Goldman Sachs was asked...

Mar 18, 2009
 You are in a room with 3 switches which correspond to 3 bulbs in another room and you don't know which switch corresponds to which bulb. You can only enter the room with the bulbs once. You can NOT use any external equipment (power supplies, resistors, etc.). How do you find out which bulb corresponds to which switch?6 AnswersTurn on 2 switches. Turn one switch off after a few minutes. Enter room with bulbs. The bulb that is on is the only switch that is on. The bulb that is off but hot, is the switch that has been turned off. The bulb that is off and cold is the third switch.Turn on switch A for 1 minute. Turn it off. Turn on switch B. Enter the room with the bulbs. The hot bulb is A The lit bulb is B The dark bulb is CTurn switch A leave it on for 1/2 minutes and turn it off then turn on switch B. Now goto the room, the one Hot is A, Cold(or not Hot) is C, the bulb thats on is B.Show More ResponsesThe answers here all have two assumptions which are unwarranted. 1. Why do you think the light emits heat? 2. Why do you think you can touch the bulbs? (3. If you're never going to enter the room again what's the point of knowing which switch goes with which light?) The best you can do is reduce to guessing one of two bulbs.RE: Objection 1. I guess you've never touched the outside of a light bulb after it's been on for awhile. The filament gets hot-it glows, the light we see is that glowing-the heat from from the glowing filament transfers to the glass-the glass is hot. 2. Why not? This is an exercise to demonstrate problem-solving ability, not a "MacGyver" episode. Who's to say the candidates didn't ask about the room's dimensions or where the bulbs were located, or that assumptions could be made in order to formulate an answer? 3. I think you missed the point of the question. 4. Sheesh. 3.Yes, Objection, I did see that I entered "3." on here a second time. BTW, I'm not returning to this forum again, so any reply/retort/threat won't be seen by me. Good luck in your job hunting.

### Senior Software Engineer at Microsoft was asked...

Mar 18, 2009
 Given a set of people, one of them is a celebrity. You have a 2D array which describes which people know each other, that is [N, M] is true if N knows M. The celebrity will not know anyone (except them self) and everyone will know the celebrity. Find an order N algorithm to find the celebrity. 5 AnswersDon't think there is an O(n), but O(n*m) yes.The key here is that the celebrity knows nobody AND everybody knows the celebrity. So for each iteration, you can rule out 1 person. [Notation: A->B -- A knows B] If A->B then A is not the celebrity .. rule out A Next check would skip B->A since we don't care if B->A etcIt is not so simple. You can construct a matrix of relationships to defeat this algorithm. For example, start with A knows B. Then check if B knows C, and say answer is false. Then check B -> D, answer is false. And so on. That's O(N) operations. B looks like a good candidate. But then you check B-> A, you get true, so after all that work B is ruled out. Need to examine C now. Same thing. You end up checking perhaps half of all possible pairs, that's O(N^2).Show More ResponsesHow about constructing a graph with edges between who know each other.. and then checking if target is reachable..http://courses.cs.vt.edu/~cs5114/spring2010/notes.pdf

### Candidates Day Interviews for Multiple Areas (X-Div/Back Office) at Goldman Sachs was asked...

Mar 18, 2009
 If you have a three gallon jug and a five gallon jug No marks on either one The goal is to fill the five gallon jug with four gallons of water How is this accomplished?5 AnswersTake 5 gal. and pour into the 3 gal. The 5 now has 2 gal. Empty the 3 gal, and pour the remaining 2 gal into the 3 gal. Fill the 5 gallon and pour 1 gal. (which is the remainder of the space in the 3 gal.) This gives you 4 gal.that was from die hard 3. 1) fill up the 3 and pour it into the 5. 2) fill up the 3 and fill up the rest of the 5. that leaves 1 in the three. 3) dump out the 5. 4) pour the 1 that's left in the three into the 5. 5) fill up the 3 again and pour it into the 5. see - easy peasy. might be a bit rougher if solving it is necessary to stop a bomb from blowing up the city. mclain and samuel L got it done.1) Fill up half of 5 gal (2.5 gal) from 3 gal jug 2) Fill up half of 3gals jug(1.5 gal) and pour into 5gal jug 2.5 + 1.5 = 4galShow More ResponsesDie Hard 2 also has the solution to this question.there are actually 4 die hards, which is why you two are confused. 1. the classic big LA building he runs through glass 2. the airport based one 2*. the new york fed gold gets stolen (die hard with vengence) -- THIS is the one with the water puzzle. 3. the newest die hard where the stop lights get taken over etc, live free die hard i think

### Senior Software Engineer at Oracle was asked...

Mar 19, 2009
 Considering a 2-dimension matrix that can only be traversed by 1 adjacent position at a time and never diagonally. Create an algorithm to traverse that matrix from its upper-left corner to its lower-right corner using the shorter possible path in the most efficient way.5 AnswersThis is a very interesting problem. Although I knew immediately that I had to use recursion to effectively traverse the matrix and eventually got a working algorithm, the catch to make the algorithm much more efficient is to traverse the matrix backwards.How back traverse make the algo efficient?Why not just go all the way down then all the way right? Without diagonal moves the path length is fixed. Unless they provide a different definition for 'shortest length'Show More ResponsesFor a thinking outside the box answer.... assuming the set is closed for indexing, go up -1 and left -1.I guess it's the traversal of a graph's depth first search (DFS) using Adjascent matrix...

### Q & A Analyst Training Program at Eze Software was asked...

Apr 26, 2010
 Scenario: You have 8 golf balls and 1 is heavier than the 7 others. All you have is a balance used in chemistry classes. What is the shortest number of times you could measure the golf balls to find the heaviest ball?5 AnswersYou have to keep in mind that you're dividing up the balls. They try to confuse you, but just ignore the people and stick to your intuition. The quickest way to discover the heaviest ball was in 2 steps.i would say three. you could put 4 balls on each side and then take the heavier side. split that group into two balls on each side. then lastly split that group to have one ball on each side.i would say three. you could put 4 balls on each side and then take the heavier side. split that group into two balls on each side. then lastly split that group to have one ball on each side.Show More Responses2 steps. 1. Put 3 balls on each side of the scale measure( [123], [456] ) If each group of 3 is equal: 2. Place the remaining two balls on the scale - measure( [7], [8] ) If each group of 3 is not equal: assuming [123] is heavier than [456] 2. Take 2 balls from the heavier group from step 1 and place them on the scale. measure( [1], [2] ) If they are equal then [3] is the heaviest3 v. 3 Case 1: Heavier ball lies within the first 3v3 weighing. Weigh 2 of the balls on the heavier side. Either one is heavier or they balance. If they balance, then it's the 3rd one we didn't weigh. Done. Case 2: 3v3 balances. Then the heavier ball lies within the other 3 not weighed. Weigh 1v1, either it balances or it doesn't. If it doesn't, we're done because we can see that one side is heavier. If it does, then it's the third one not being weighed. Minimum amount of weighings is 2.

### Senior Applications Developer at Deutsche Bank was asked...

Feb 14, 2011
 We have a pond containing a single bacterium. The number of bacteria double every 5 minutes, and the pond is full of them in 24 hours. If we started with the same pond but two bacteria, how long will it take to fill the pond?4 AnswersI struggled with this a bit and got close. I believe answer is: 23:55This is a clear case of Geometric progression. Find the nth term Tn1 = a*r^(n-1). where n = (24 * 60)/5,a = 1 and r=2. when the initial value (a) = 2, the values become n = ?, a = 2 and r = 2. Since Tn1 = Tn2, Equate the RHS of both the equation. Since the base are equal, equate the powers, doing so will give the n value. When n is convert into minutes one get 23 hrs 55 minutes.this is easy, you don't need all the math. The pond was half full five minutes before, so it's 23:55Show More ResponsesThe first pond started with 1 bacterium and doubled to 2 in five minutes. Therefore, the second pond will take 5 minutes less than the first to be full. ie: 23:55

### Senior Systems Test Engineer at Qualcomm was asked...

Jun 7, 2010
 There is a body of water that starts with 1 square unit, and doubles in size every day (2 units after 2 days, 4 units after 4 days). It takes 100 days to fill up. How many days would it take to fill if you started with 2 square units?6 Answers100 - 1 = 99 daysThis question is phrased incorrectly. I think you meant "4 units after 3 days". Which makes your answer wrong as well. This is not helpful at all.if you start with 1sq unit - lets say you end up with 'x' amount to fill up - takes 100 days if you start with 2 sq unit - you will have to fill up '2x' amount thus it will take - 200 days.Show More ResponsesStarting with 2 square units at time t=0 is like 1 square unit at t = 1. [this logic is the key to answering the question]. Now let's do the first few cases. t = 0: size = 1+1 = 2 t = 1: size = 2(1+1) = 2+2 = 4 = f(2) in the 1 unit case. Pretty easy to see it only requires 1 time period less from here. The OP was right.1 day less that is 99 days.It is still 100 days. Starting from 2^0, and going all the way to 2^100, the reservoir has a capacity of 2^101 - 1 units. Now in the second case, starting from 2^1, in 99 days there will be 2^101-2 units of water in the reservoir, which is one unit short of the capacity of the reservoir. So we need the 100th day to fill it up!

### Senior Unix/C++ Developer - Tradebook at Bloomberg L.P. was asked...

May 3, 2011
 Sequence of numbers in random order and 1 of them is missing how to find that out...5 AnswersN(N+1)/2 - sum of the input = missing numberIt isn't stated that sequence starts from 1. The sequence could be 8,9,5,6!If the sequence is guaranteed to contain only positive integers, it can be done like so: Read in the sequence, noting the MIN and MAX numbers. The sum IF it started from 1 would be MAX(MAX-1)/2. The sum of the 'missing' numbers (from 1 up to where the sequence actually starts) is (MIN-1)*MIN/2. The missing number is given by taking the difference between the two: X = [MAX*(MAX-1) - (MIN-1)*MIN]/2.Show More ResponsesOops, in addition to what I put above there is a final step to get the actual answer. The missing number is equal to X minus the sum of the numbers given.You can graph them similar to a convex hull question. If all nodes were there the sequence would be increasing on some percentile or relative like amount. The missing node will yield an abnormality in the changes in slopes between each node. The only assumption you would have to make, which in all honesty just has to be accepted is that its not the first or the last element that's missing.
110 of 86 Interview Questions