Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Job Interview at Google

catonmat.net

Post reply on HN
Print view View original

61–70 of 114 posts

Re: My Job Interview at Google

#61

Post by litewulf »

globalrev wrote: post #36

Could anyone point me on how to solve this(either a solution or preferrably a pointer on how to get to it): "Q: Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7." First I thought it was simple but the I got stuck, maybe I'm just tired. No matter how I twsit and turn it I seem to get only an even distribution over 5 numbers.

Dumb/obvious idea: Generate 7 random numbers, pick the index that had the highest value. (If theres a tie, run it again!)

(Note: not guaranteed to terminate.)

Re: My Job Interview at Google

#62

Post by andreyf »

webwright wrote: post #42

Isn't this level of interviewing kind of excessive and time-expensive? If I were Google, I would do the following: 1) Have the first interviewer be the best/most-appropriate interviewer for the position (manager, lead dev, whatever). Have them write down in a sealed envelope a "hire" or "no hire" statement after the interview. 2) At the end of the assorted interviews, measure how often the first interviewer is correc…

you'd get 98% of the value with 10% of the time invested.

Hard to say. The economics of hiring aren't intuitive - a bad hire can do a lot of damage, esp. if it's a management position (which this wasn't, I know). It's probably better to nicely turn down 10 people (and nicely ask them to re-apply in 6 months) than to let in 1 charming, but conniving and free-riding bullshitter into your team.

Re: My Job Interview at Google

#63

Post by llimllib »

globalrev wrote: post #36

Could anyone point me on how to solve this(either a solution or preferrably a pointer on how to get to it): "Q: Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7." First I thought it was simple but the I got stuck, maybe I'm just tired. No matter how I twsit and turn it I seem to get only an even distribution over 5 numbers.

1) Given a number 1 to 5, get a new one if it's 5, else throw away the MSB, you get 2 bits of randomness per number. Subtract one and call it a.

(Now you have two bits of randomness evenly distributed among the set {00, 01, 10, 11})

2) Get another number 1 to 5, toss it if it's 5, take the LSB. Call it b.

(Now you have another bit of randomness, evenly distributed among {0,1})

3) if b == 1 and a == 11, start over. else return (4b)+a+1

Python implementation (with the -1 then +1 factored out):

  def one_to_seven(debug=False):
    a = one_to_five()
    while a == 5: a = one_to_five()
    b = one_to_five()
    while b == 5: b = one_to_five()
    b = (b % 2) * 4
    if a+b == 8: return one_to_seven()
    return a+b

Re: My Job Interview at Google

#64

Post by llimllib »

nostrademons wrote: post #57
deadsy wrote: post #54

Earlier quoted context omitted.

This won't work. f gives 1 to 5. 7 * f gives 7 to 35. But 7 to 35 will not be evenly generated. Think about it: There are more ways to get a 20 than there are to get a 7 or a 35. Same thing with rolling 2 die.

That was my second thought too (my first thought was to upvote the comment), but at least in the 2-die case, the modulus takes care of it. If you work out the probabilities, the chance of getting 0mod2 = 1/36 (2) + 3/36 (4) + 5/36 (6) + 5/36 (8) + 3/36 (10) + 1/36 (12) = 18/36 = 1/2. Same goes for getting 1mod2. So you end up with a fair result even though the chances for each individual outcome are biased. I didn't…

experimental evidence says that it is in fact a uniform distribution:

  r = random.Random()

  def one_to_five():
    return r.randint(1, 5)

  def mod_seven():
    return (sum(one_to_five() for x in xrange(7)) % 7) + 1

  def test_dist(lst):
    return [(x, lst.count(x)) for x in [1,2,3,4,5,6,7]]

Re: My Job Interview at Google

#65

Post by JesseAldridge »

gaius wrote: post #28
nostrademons wrote: post #25

Earlier quoted context omitted.

I asked my recruiter specifically if they were in a hiring freeze (I'm in the middle of the application process now), and she was very adamant that they were not. If they were, they would lay off the whole HR department, except for a skeleton crew needed for benefits and such. After all, why spend ~40M/year on recruiters if you're not recruiting?

Who lays off the layers-off? HR departments look after themselves.

Executives?

Re: My Job Interview at Google

#66

Post by ninjackn »

Retric wrote: post #35
nostrademons wrote: post #34

Earlier quoted context omitted.

It's actually * and &. ;-) Don't interview for positions in languages you've forgotten, then, or brush up and re-learn stuff before the interview. It's like riding a bike...it comes back to you. Not being able to remember pointer syntax is a serious problem if you're being hired to program in C. I can understand why they'd want to weed out anyone who can't get that, particularly given how many candidates they have.

lol, thanks. I could have said x[i] is the same as ^(x + i) and really thought that was the correct syntax. The problem is I have used enough languages and dialects that I really can't brush up on it all. I just say if it's been five years, let me break out my cheet sheet for that stuff. PS: Ok, if it was really just a C job of course I would focus on that. Edit: Dammit it is like riding a bike. I have been having C…

Maybe it was Visual C++ you were programming in. ^ is for a handle to a object on the managed heap so it's almost the same as pointer. http://msdn.microsoft.com/de-de/library/yk97tc08.aspx

Re: My Job Interview at Google

#67

Post by andreyf »

MaysonL wrote: post #58
deadsy wrote: post #54

Earlier quoted context omitted.

This won't work. f gives 1 to 5. 7 * f gives 7 to 35. But 7 to 35 will not be evenly generated. Think about it: There are more ways to get a 20 than there are to get a 7 or a 35. Same thing with rolling 2 die.

f * f gives you 25 boxes, number 11, 12, ... 15, 21,...25...55. Assign 3 each of 21 of those to 1..7. If f * f doesn't fall into one of those 21 boxes, repeat until it does.

Runtime: O(infinity)?

Re: My Job Interview at Google

#68

Post by ig1 »

globalrev wrote: post #36

Could anyone point me on how to solve this(either a solution or preferrably a pointer on how to get to it): "Q: Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7." First I thought it was simple but the I got stuck, maybe I'm just tired. No matter how I twsit and turn it I seem to get only an even distribution over 5 numbers.

Generate two random numbers with your rand5 function, let them be the two digits of your base 5 number. Each number from 0-24 has a 1/25 chance of being picked.

If the number is greater than 6 throw it away and repeat, otherwise you have your random number.

Re: My Job Interview at Google

#69

Post by sdfx »

llimllib wrote: post #64
nostrademons wrote: post #57

Earlier quoted context omitted.

That was my second thought too (my first thought was to upvote the comment), but at least in the 2-die case, the modulus takes care of it. If you work out the probabilities, the chance of getting 0mod2 = 1/36 (2) + 3/36 (4) + 5/36 (6) + 5/36 (8) + 3/36 (10) + 1/36 (12) = 18/36 = 1/2. Same goes for getting 1mod2. So you end up with a fair result even though the chances for each individual outcome are biased. I didn't…

experimental evidence says that it is in fact a uniform distribution: r = random.Random() def one_to_five(): return r.randint(1, 5) def mod_seven(): return (sum(one_to_five() for x in xrange(7)) % 7) + 1 def test_dist(lst): return [(x, lst.count(x)) for x in [1,2,3,4,5,6,7]]

i've tried it out experimentally in google docs and it looks really good for big numbers. No real proof tho and it might be that the errors counter each other by chance:

http://spreadsheets.google.com/ccc?key=pq4tB7LQWN03gF7ImGhIP...

Post reply on HN