Problem solving Interview Questions | Glassdoor

# Problem solving Interview Questions

100

interview questions shared by candidates

## Problem solving Interview Questions

Sort: RelevancePopular Date

Apr 3, 2009

### Software Development Engineer In Test at Amazon was asked...

Dec 6, 2012

Jan 15, 2010
 You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently. 7 AnswersThe problem is not too difficult, what you have to do is find the empty spot, then look in the desired arrangement for what car should be in that spot, and move that car there. Repeat until complete.Does this really work? If I the empty spot is expected to be the same, but the positions of two (or more) cars are switched, how to rearrange it without a complete search?It's the Tower of Hanoi Problem.Show More ResponsesSo there are actually 2 empty spots then or is there a way to 'stack' cars I don't know of?The parking lot problem has nothing to do with Tower of Hanoi, which requires O(2^n -1). This problem, however, can be solved in O(n) - that's because all you need to do is to perform (0 or more) rotations using the empty parking spot.Here is a C# implementation, using generics and .NET 4.0 Tuple: IEnumerable> RearrangeCars( TCar emptyCarMarker, IDictionary initial, IDictionary desired) { // reverse the lookup: car -> spot Dictionary pending = initial.ToDictionary(p => p.Value, p => p.Key); // remove emptySpot from lookup TSpot emptySpot = pending[emptyCarMarker]; pending.Remove(emptyCarMarker); while (pending.Any()) { // check if the empty spot is where is should be if (desired[emptySpot].Equals(emptyCarMarker)) { while (true) { // pick a car (any car would do) var carToMove = pending.First(); // check if this car is already in its desired position if (desired[carToMove.Value].Equals(carToMove.Key)) { // remove from pending, no moving is necessary pending.Remove(carToMove.Key); if (pending.Any() == false) yield break; } else { yield return new Tuple(carToMove.Key, carToMove.Value, emptySpot); // move the car TSpot newSpot = emptySpot; emptySpot = carToMove.Value; pending[carToMove.Key] = newSpot; break; } } } // move the car into its desired spot var car = desired[emptySpot]; var newEmptySpot = pending[car]; yield return new Tuple(car, newEmptySpot, emptySpot); emptySpot = newEmptySpot; pending.Remove(car); } } Note that there is a while-loop inside another while-loop. However, the complexity is still O(n) since at every iteration of internal or external loop, the "pending" map is reduced by one element. Below are some examples (emptyCarMarker == ""). EXAMPLE 1: Input: initial == { "", "B", "A"} desired == { "", "A", "B"} Output: (B, 1, 0) // move car B from spot #1 to #0 (A, 2, 1) // move car A from spot #2 to #1 (B, 0, 2) // move car B from spot #0 to #2 EXAMPLE 2: Input: initial == { "", "B", "A", "D", "C" } desired == { "A", "B", "", "C", "D" } Output: (A, 2, 0) (D, 3, 2) (C, 4, 3) (D, 2, 4)Here is a Java Implementation, using Google's guava library for the BiMap. It takes O(n) to first create the BiMap and O(n) to move the cars, total O(2n), i.e. O(n) time complexity. import com.google.common.collect.BiMap; import com.google.common.collect.HashBiMap; import java.util.Map; import java.util.Set; class ParkingAttendant { static class ParkingConfiguration { static final Integer EMPTY = -1; Integer moves = 0; BiMap conf, i_conf; static ParkingConfiguration getInstance(int[] conf){ return new ParkingConfiguration(conf); } private ParkingConfiguration(int[] conf){ this.conf = arrayToMap(conf); this.i_conf = this.conf.inverse(); } BiMap arrayToMap(int[] arr){ BiMap m = HashBiMap.create(arr.length); for(int i=0;i> entrySet(){ return conf.entrySet(); } } static void moveCars(ParkingConfiguration from, int[] to){ for(int pos=0; pos e : p.entrySet()){ int pos = e.getKey(); int car = e.getValue(); System.out.format("%1\$s, ", ParkingConfiguration.EMPTY.equals(car)?"_":car); } System.out.println("]"); } static void printCars(int[] p){ System.out.print("["); for(int pos=0; pos

Aug 29, 2009

### Software Developer at Epic was asked...

Aug 29, 2009
 Please write a function that accepts a floating number and returns its square-root. You may not use built-in square root function from your language. However, basic operators like addition, subtraction, multiplication are allowed. Please take into consideration the floating precision.3 AnswersHint: please really take into consideration the floating point.Newton's method: http://en.wikipedia.org/wiki/Newton's_methodhttp://www.dreamincode.net/code/snippet244.htm

### Web Development Intern at AllofE Solutions was asked...

Aug 28, 2012
 One of the software engineers asked me the question about the colored chameleons bonking into each other question. Basically, there are 15 red, 17 green, and 19 blue chameleons on a desert island. Whenever two chameleons of different colors collide, they both become chameleons of the third color. Can it ever be that all the chameleons on the island are the same color?3 AnswersGoogle the problem for a full mathematical proof. I was able to solve it intuitively and explain my reasoning for my (correct) solution, and that seemed to be what the interviewer was looking for.Answer is yes - Green and Blue combine to give a Red. State: 16R 16G 18B - All the 16R and 16G can combine to give 16 more BluesAnshul its incorrect what you said, because when 2 chameleon bonk they turn into other color of 2 chameleon and not 1 chameleon.

### Financial Software Developer at Bloomberg L.P. was asked...

Jan 30, 2010
 You have 25 horses, and you want to know which are the top 3 fastest, but you don't have a stopwatch. You can race the horses, but the track is only big enough to fit 5 horses at a time. How do you find the first, second and third fastest horses using the least amount of races possible?3 AnswersSplit the horses into 5 groups and race each of the 5 groups (5 races). After that, you have the horse placements for each group. I laid it out like this: A B C D E 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 Five columns, one for each group of horses, lettered A-E. Each number represents a horse... say horse A1 is the one that came in first place from group A, C2 is the horse that placed 2nd in group C, and so on. You can eliminate all 4's and 5's from the chart, since we know that there are at least 3 horses that are faster for each 4th and 5th place horse. A B C D E 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 Now race all the 1's (race #6). This will give you the fastest horse from the initial 25. But what about 2nd and 3rd place? Let's say A1 got 1st, B1 got 2nd, C1 got 3rd, D1 got 4th and E1 placed last in race #6. A1 is definitely the fastest horse, but B1 may or may not be. Horse A2 can still be faster than B1- we have never raced them together before. Approach it this way: which horses can we eliminate? Find all horses that we know have at least 3 horses faster than them. We can eliminate D1 and E1, because we know that A1, B1, and C1 are all faster than them. We can also eliminate all other horses in columns D and E below them. We can't eliminate C1, but we can eliminate C2 and C3. We also eliminate B3, since B2, B1, and A1 were all proven to be faster. A B C D E 1* 1 1 2 2 3 The only horses left to race are A2, A3, B1, B2, and C1. (Race #7). The 2nd and 3rd place finishers are then 2nd and 3rd fastest from the original 25.thanks. very nice explanationvery nice~calm thinking! hope I can be so calm in an interview!

### Product Analyst at Stockamp & Associates was asked...

Nov 17, 2009
 Problem Solving #2 - You have 3 light switches and 1 light bulb controlled by only 1 switch in a room you can't see into. You can flip any or as many switches as you want and can check the room once. The next time you go into the room, you have to know for sure which switch controls the light bulb. 2 AnswersAnswer #2 - Flip on two switches and check the light. If it is off, you have your answer. If it is on, it is one of the two. Go back to the switches and turn all off. Turn on of the switches on that was on before for about 5 minutes, turn it off, then turn on the other one. When you go into the room, if the bulb is warm but off, it is the first switch. If it is on, it is the second switch. (I didn't get this one right)Start with all the switches in the off position. Turn on two of the three switches. when you enter the room the first time, if the light is off, then you know it is the switch you didn't turn on. Else, turn on that switch and turn off one of the switches you previously had on. Now, if the light is off when you enter the room, you know it is the switch you just turned off. If the light is on, you know it is the switch that you had turned on when you looked at the room the first time.

### Product Analyst at Stockamp & Associates was asked...

Nov 17, 2009
 Problem Solving #1 - Given a 5 gallon bucket and a 3 gallon bucket with no measures. Measure exactly 4 gallons. 2 AnswersFill 5 gallon, use it to fill 3 gallon. 2 gallons left in 5 gallon. Empty 3 gallon and fill it with the 2 gallons. Refill 5 gallon and use it to fill 3 gallon (1 gallon left to fill). 4 gallons left in 5 gallon bucket.fill each bucket up halfway...

### Technical Support Engineer at HealthEdge Software was asked...

May 29, 2012
 If you had 9 marbles, all the same size. One is heavier than the rest. You have a balance scale. How do you determine the heavy marble in the least number of moves. 2 AnswersI suggested going in half.. 4 marbles each. The heavier group then divided 2 and 2, then 1 and 1. If it balanced, the extra is the heaviest. The answer was using 3 each. That would identify the set of marbles faster by one move.The answer is 2. Group them into 3 marbles each. 1. Weigh any 2 groups first - Find the heaviest group. If both are equal then the 3rd group is heaviest. 2. Now follow step 1 with 1 marble and you can find the heaviest.
110 of 100 Interview Questions