Math-related Interview Questions - Page 2

On March 29 2011 20:29 Adeeler wrote:
Think outside the box and inside the box also for the wolf lake problem.

Know your variables. 1 human, 1 wolf.

Swim a little side to side and the wolf will run the entire distance around the lake again and again and tire itself out.

Then proceed in any direction. Remember the math solution doesn't help you if the lake is so small the wolf always catchs you; you want a solution that encompasses all possible lake sizes which the math only solves for large lakes considering the speed of a human swimming is.

On March 29 2011 20:46 BrTarolg wrote:
The more im working on the horse problem the more i am sure that the solution is 6

Even in the very worst case scenario, by always racing your fastest horse you will eliminate a minimum of 2 horses per round (as usual), however, instead of having to do 7 races since you don't know which horse is the fastest, after the end you DO know which horse is the fastest (since you've raced your fastest one every time) reducing your race count by 1

edit: god damn worst case gives 8 races, but its possible to do it by 5? in best case (5-6 i'm still not 100% sure)
Kinda annoying me now lol because i was expecting a more elegant solution but let me crack with it for longer

On March 29 2011 21:22 TrainSamurai wrote:


But wouldn't you need to measure the time other horses finish relative to that chosen horse for that? If you can do that might as well do it in 5 races. If you're comparing distances it gets a bit icky because the horses don't run at constant speed.

On March 29 2011 19:23 paper wrote:



Columns are groups of horses in fives. They are conveniently sorted from fastest to slowest from the top left to the bottom right because... The first five races give you the top runners from each group. Throw the top runners from each group in a sixth race. You now have your guaranteed fastest horse at the most top left position. The seventh race has the leftover five horses marked by the orange circles (excluding the fastest horse at the upper left corner). The two winners are the remainder of your three fastest horses. This is just a matter of following the "circles" (when prioritizing going right over going down).

That's just how I see it though ;p

On March 29 2011 20:03 Chriamon wrote:
Also, I saw an interesting explanation about #6. There is a variation at http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/
Basically, assuming that the islanders are all incredibly smart, and they know each other are smart, and assuming they know that the explorer is not lying, + Show Spoiler +

this problem is actually the example on http://en.wikipedia.org/wiki/Common_knowledge_(logic)

On March 29 2011 17:54 DTK-m2 wrote:
2.) 30 strings. Two parallel rows of 30 holes. Each of the 30 strings goes through one of the 30 holes in the first row, and then one of the 30 holes in the second row. What is the expected number of crossovers, where one string overlaps the other?

P.S.: Despite being the language of group theory, this is reasonably intuitive stuff. Which by no means means it's easy, I just mean that I have no idea if this is the solution economics firms would expect. I'm a grad student doing pure math, and have no clue what goes on in the world of finance and applied math and what sorts of things people know and don't know.

On March 29 2011 23:26 Joementum wrote:


You confused the hell out of me good sir. I understand what you did, sort of, but it boggles my mind. I've taken up to Calculus 3 and I could not come up with that answer on my own in an interview. It would have taken me at least a 30 minutes to figure it out. I'm doubting a firm would actually ask this question though. I'm looking at my College's Finance major requirements and only up to Calculus 1 is required. How any student with just some basic knowledge of Calculus is supposed to figure that out is beyond me.

On March 29 2011 18:35 eluv wrote:
5) There are 100 people in separate rooms. They can talk as much as they want until they "begin." Once they begin, they are called one at a time, in no particular order, into another room. In this room is only a light switch that turns on and off a lightbulb in the room. Noone can see the lightbulb unless they are in the room, and the only thing you can do in the room is check the lightbulb, turn it on, or turn it off. How do the people know when all 100 have been called? (You can be called more than once before everyone else has gone once).

On March 29 2011 22:59 Iranon wrote:


This is pretty cool. As stated it's still ambiguous though - do you mean to say that exactly one string goes through every hole? Or can more than one go through the holes... I'll assume the former.

If you're matching up one left hole with one right hole 30 times, we're looking at a random element of S_30, the symmetric group on 30 objects. A configuration of the 30 strings is just a permutation s on {1,2,...,29,30}. That is, number the holes on each side from 1 to 30, and when you put all the strings on, for each n from 1-30, let s(n) be number at the right end of the string which starts at n at the left end. We want to know how many strings cross other strings. When do those crossovers happen? Well, whenever we have some pair of holes n and m with ns(m). In math-land these are called inversions. The number of inversions (i.e. the number of pairs in the list {s(1),s(2),...,s(29),s(30)} which are out of order) is the same as the number of times you'd have to interchange consecutive elements to get everything back to the correct order (i.e. the number of times you'd have to swap right endpoints of adjacent strings to get all the strings going straight across). The minimum number of inversions is obviously 0, corresponding to the identity permutation where every string goes straight across, and the maximum number of inversions obviously happens when every pair is out of order -- that is, s(1)=30, s(2)=29,... s(30)=1. Visually, this is when every string crosses every other and it makes a giant X. How many inversions is that? Well, if every string crosses every other we have one inversion for each possible pair of strings, which is (30 choose 2)=(30*29)/2=435.

The neat bit is that if you take any permutation and reverse the order (not the inverse element, I mean lexicographically reverse it), you get a permutation where all the incorrectly ordered pairs are correctly ordered and vice versa. So in our case, if s={s(1),s(2),...,s(30)} has k inversions, then defining s' to be the permutation {s(30),s(29),...,s(1)}, s' has exactly 435-k inversions.

But then if every permutation with k inversions has a corresponding permutation with 435-k inversions, a moment's thought tells us that *on average*, there will be 435/2 = 217.5 inversions, and that's your expected number of crossovers.

Notice that along the way we've actually proven the much more general fact that if you do this with N holes on each side and N strings, your expected number of crossovers is exactly (n choose 2)/2, which is n(n-1)/4.


P.S.: Despite being the language of group theory, this is reasonably intuitive stuff. Which by no means means it's easy, I just mean that I have no idea if this is the solution economics firms would expect. I'm a grad student doing pure math, and have no clue what goes on in the world of finance and applied math and what sorts of things people know and don't know.

On March 30 2011 00:40 Oracle wrote:
7) There are N cars travelling along an infinitely long one-lane highway. No two cars travel at the same speed. When a car is travelling at a speed less than the car behind it, it forms a jam. How many jams are expected to be on this highway, in terms of n?

+ Show Spoiler [Hint] +

On March 30 2011 00:50 ]343[ wrote:


if n_a < n_{a+2} there's no ja
correct? only if n_a < n_{a+1}? and jams don't cause other jams? because then expected value works again: for each pair of adjacent cars, 1/2 probability of jam. n-1 pairs of cars, so (n-1)/2 jams are expected.

On March 30 2011 01:00 Oracle wrote:



Consider the set {6, 4, 5, 3, 2}

4,5 form a jam, but also 4,5,3 forms a jam. So yes, jams may cause other jams.

However, jams are coutned contiguously, {4,5} would be not regarded as a different jam than {4, 5, 3}