Financial Software Developer was asked...15 February 2010

↳

Seems to me the correct answer is five. Assuming that each horse's performance is timed, by running five races with five horses each, you'll know the speed of all 25 horses. The three with the shortest times are the three fastest horses. Most responses assume you need multiple rounds, but these responses seem to assume that the five horses that finish first in the first round are the fastest five overall. That may not be the case. Just because a horse beat its four competitors doesn't mean it's one of the five fastest overall ... just that it was faster than the four it competed against. Less

↳

7 races. We run five races with five horses. The five winners race in a sixth race while the 4th and fith place finishers are eliminated from further consideration. The sixth race show horse is faster than all the horses that participated in the preliminary races where the 4th and 5th place horses participated and they are eliminated from further consideration. The other horses in the preliminary race where the 6th race show horse participated are also eliminated. The show horse in the preliminary race where the 6th race place horse participated is eliminated since there are at least three remaining horses that are faster. We are left with 6 horses. We know the winner of the 6th race is fastest overall, so that leaves five horses to enter a 7th race for the overall place and show. Less

↳

12 RACES ARE REQUIRED -------------------------------------- In the worst case scenario the 'best three' can be from a single team of 5 horses. So 5 races in round one. Chose all the first three of each of the 5 races. 3 races of all the 15 horses which were the 3 winners of the first round. Chose the 9 horses which were winners in round two and have 2 races for the 9 winners[ 5 & 4 horses] you get 6 winners. 1 race of 5 horses, out of the 6 round three winners, keeping one standby 1 race of 4 horses of round four winners with the standby. This will give you the best 3 horses out of 25 So you need to have 5+3+2+1+1 = 12 races in order to get the best three horses. Answer 12 races required. Sometimes the 2nd and/or 3rd best athlete do not get selected if they are teamed in a race along with the best athlete. Less

Financial Software Developer was asked...17 May 2010

↳

Never....the frog would be dead by day 10 since nothing to eat or drink.

↳

Assuming it doesn't die of starvation, the answer is 28 days.* start of day 1 (0 days elapsed): 0m --> 3m (then falls back 2m by start of day 2) start of day 2 (1 day elapsed): 1m --> 4m start of day 3 (2 days elapsed): 2m --> 5m ... start of day 28 (27 days elapsed): 27m --> 30m start of day 29 (28 days elapsed): 28m --> 31m In other words, 28 days will have elapsed before the frog can jump to a height exceeding 30m.* * This answer assumes the frog is not able to walk away after it hits 30m. I would assume it has no energy left to climb out based on the problem description. If the questioner disagrees with this assumption, then the answer is 27 days. Less

↳

I agree -- it's 28...because on that morning, he'll be at 27 metres and he can jump to the top in one bound. Less

Financial Software Developer was asked...1 October 2010

↳

1. calculate the sum of elements in array say SUM 2. sum of numbers 1 to 100 is(n* (n+1))/2 = 5050 when n==100 3. missing element is (5050-SUM) Less

↳

Sum them and then subtract them from 5050. In general, if an array of size n - 1 elements has unique elements from 1 to n, then the missing element can be found by subtracting the sum of the elements in the array from sum(1 ... n) = n * (n + 1) / 2. Alternately, one could use a boolean array of length n with all values set to false and then for each value, set array[val - 1] to true. To find the missing value, scan through the array and find the index which is set to false. Return index + 1. This requires O(n) memory and two passes over an O(n) array (instead of constant memory and one pass), but has the advantage of actually allowing you to verify whether or not the input was well formed. Less

↳

Read the question. Here are the steps to solve it: 1) find the sum of integers 1 to 100 2) subtract the sum of the 99 members of your set 3) the result is your missing element! Very satisfying! Less

Financial Software Developer was asked...29 June 2012

↳

You are complicating it too much... There are 5 cards... 4 ACes and 1 Joker. and there are 5 places.. What is the probability that joker occupies the 5th place? It is 1/5 = 20% Less

↳

Select 5 positions from the 53 cards; assign the 4 aces to the first 4 positions, and the joker to the 5th position. The 4 aces and the rest 48 cards can have full permutations. The probability is C(53,5)*4!*48!/53!=0.2 Less

↳

It's a hyper-geometric distribution. There is no single answer since the probability of having all 4 aces depends on how many cards were chosen. If all cards were chosen, the probability of you having all four aces is 1. So just make an expression with n equal to the amount of draws from the deck until reaching joker. This is what I got. (49 C (n-4)) / (53 C n) Less

Financial Software Developer Intern was asked...17 April 2012

↳

The above two are close, but wrong.. There are 20 buttons, thus 20 choices, sure. But you are getting on at one of the floor. No body will press the button for the floor they get on.. Thus, there is really only 19 choices. P = (1/19)^3 (Independent events mean (1/19)(1/19)(1/19)). Less

↳

1/19 + 1/18 + 1/17 + 1/16 assuming that there were no repeated destinations.

↳

based on question: P(all 4 ahead of you want to get off on 20th fl) = (1/19)^4 real life(all 4 want to get off on 20th fl, and one of them is the first person press the button to 20th fl, and that leave all others, including you, stay still): (1/19) * (1/4) Less

Financial Software Developer was asked...4 November 2014

↳

Its a hashmap. It never guarantees you the order in which you inserted the elements...!! Less

↳

@ankush: this is where LinkedHashMap comes into play.

↳

One possibility that comes in mind: * Walk the array, create a hashmap (key is the value in array, value is the count of such values). * Walk the array again and check the count in the hash map, once you hit 1, you have the first unique value. This is O(n) both space and time. Less

Financial Software Developer was asked...12 March 2014

↳

If 2 linked lists point to the same node, then by definition, all subsequent nodes MUST be the same. A linked list only has a single 'next' node, and that doesn't change depending on the previous node. for example: A) 1->2->3->4->5 B) 6->7->4->8 The above example is what you're talking about. And it can't exist. Node 4 cannot simultaneously point to both 5 and 8, it MUST point to a single next node (or even if it points to multiple next nodes, they must be the same for every linked list that contains 4) Less

↳

There is no restriction on destroying the list so I would 1. Find the length of first list. 2. Destroy/break the links of the second list 3. Check the size of the first list. 4. If size if still the same then lists don't intersect otherwise they do. Edge case is that the lists intersect in the last element, so additional check is needed for that Less

↳

use LinkedHashMap to find out first distinct element

Financial Software Developer was asked...22 December 2012

↳

F(n) = F(n-1)+F(n-2)

↳

Correction on the above: Summation(i=0,floor(n/2))[(n-i)P(i)].

↳

Summation(i=0,floor(n/2))[(n-i)C(i)] is correct. I need to sleep. Sorry.

Financial Software Developer was asked...7 December 2010

↳

Person A splits his salary into two unequal parts, A1+A2, choosing any split he likes. He tells B what A1 is and C what A2 is. Now B adds his own salary to A1 and tells C the total, B+A1. Then C can add B+A1 to his own salary plus A2 which he received from A, getting the sum of the three salaries, and divide by 3. No randomness needed. Less

↳

http://mindyourdecisions.com/blog/2009/04/07/game-theory-and-salary-transparency/ Less

↳

The answer can simply be that the first guy adds a random number, and after going around the group the first guy himself subtracts it and gives the average. No need to add two other random numbers as stated above Less

Financial Software Developer was asked...13 January 2014

↳

I had an idea that would solve the problem in 7 races. First divide the 25 horses into 5 groups, race respectively to get their winners. Then, race the winners in the same game and rank. The winner of the 6th game is the fastest. 4th and 5th are disqualified (together with all horses within their original groups). Then, I choose the 2nd and 3rd position from the group where the grand winner belongs to, the 2nd and 3rd position of the 6th race and the 2nd position from the group where the 2nd position of the 6th race belongs to. These five horses have the last race and the top two are the 2nd and 3rd of all horses. Less

↳

I had an idea that would solve the problem in 7 races. First divide the 25 horses into 5 groups, race respectively to get their winners. Then, race the winners in the same game and rank. The winner of the 6th game is the fastest. 4th and 5th are disqualified (together with all horses within their original groups). Then, I choose the 2nd and 3rd position from the group where the grand winner belongs to, the 2nd and 3rd position of the 6th race and the 2nd position from the group where the 2nd position of the 6th race belongs to. These five horses have the last race and the top two are the 2nd and 3rd of all horses. Less

↳

No offense, but the above mentioned methods do not use the information that relative information (i.e., A is better than B) is given. Ignoring the information given is a wrong thing in an interview. (Assuming you know the classic "Union & Find" datastructure used in Kruskal's algorithm): Let there be 25 nodes each representing a horse. Initially all nodes point to itself. Based on the relative information, the pointers are modified such that B is made to point A (and A pointer still points to itself). After all the information is fed, you end up with possibly few distinct sets. Race #1: the race is conducted between the heads (the nodes pointing to themselves) of all the distinct sets. Discard the sets of the lost horses (horses that stood in 4th and fifth position) Race#2: Get the children of the Winning horse(there can be more than one). to fill 3 leftover positions (replace the winner of Race#1, losers of Race #1). Race#3. Similar to Race#2. In this way if after forming the datastructure, if there are <= 5 distinct sets, the top 3 horses can be obtained in 3 races! Less