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

Hiring the Smartest People in the World

blog.tanyakhovanova.com

Post reply on HN
Print view View original

21–30 of 66 posts

Re: Hiring the Smartest People in the World

#21

Post by gsa »

alexchamberlain wrote: post #12
Feanim wrote: post #11

Earlier quoted context omitted.

1°: s is the sum of the numbers in the array, x = n (n+1)/2-s 2°: s sum, p product, solve the linear system {n (n+1)/2-x+y=s; n! y = p x}

Sorry, can you expand on what you meant by that?

Sum of first n natural numbers is n(n+1)/2. The sum of the array, represented by s, is n(n+1)/2 - x + y (subtract x - the missing number and add y - the duplicated number) gives:

1: n(n+1)/2 - x + y = s

Product of first n natural numbers is represented as: n! The product of the numbers in array is p.

2: p x / y = n!

(multiply by x - add missing number to product and divide by y - remove duplicated number from product).

Re: Hiring the Smartest People in the World

#22

Post by emillon »

alexchamberlain wrote: post #12
Feanim wrote: post #11

Earlier quoted context omitted.

1°: s is the sum of the numbers in the array, x = n (n+1)/2-s 2°: s sum, p product, solve the linear system {n (n+1)/2-x+y=s; n! y = p x}

Sorry, can you expand on what you meant by that?

If a is duplicated and b missing, computing the sum and the product of all the numbers can give you a-b and a/b, from which you can deduce a and b.

Re: Hiring the Smartest People in the World

#23

Post by alexchamberlain »

hristov wrote: post #20
Feanim wrote: post #11

Earlier quoted context omitted.

1°: s is the sum of the numbers in the array, x = n (n+1)/2-s 2°: s sum, p product, solve the linear system {n (n+1)/2-x+y=s; n! y = p x}

The second solution works in linear time only if one assumes that multiplication is a constant time operation. But is it really? If you look at how a processor does multiplication it becomes clear it is a O(log n) operation where n is one of the numbers being multiplied. Thus, the second solution is probably a O(nlogn) solution.

It also requires one to assume n! can be computed. Factorials get huge very quickly.

Re: Hiring the Smartest People in the World

#24

Post by [deleted] »

cncool wrote: post #19
lllbean wrote: post #15

Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…

For question 3, it clearly states two things: "the total amount of gas available at the stations and in the car is exactly enough for the car to drive around the road once" and "the car completes a full circle without running out of gas" Given the first condition, in your solution, at the exact moment the car completes the drive around the track, it runs out of gas. Therefore, it is impossible to complete it without…

[deleted]

Re: Hiring the Smartest People in the World

#25

Post by lhnz »

Most companies do not need to hire the 'smartest people in the world'. They also don't need the 'hardest working people in the world' or the 'most creative people in the world'.

Sometimes a company needs the very best people -- and they can try to define what this means to themselves and then filter for it. However, generally they need people that can solve the problems that they face to an above market-rate level of quality, and that are willing work for the least amount of money.

Unless your companies selling point is solving hard mathematical problems, or designing the most beautiful/elegant interfaces you should probably hire for 'good value', and a few people that you believe to be 'multipliers'.

Re: Hiring the Smartest People in the World

#26

Post by cheald »

The last problem seems trivial enough, and I'm no mathematician. The trick lies in that you get to pick the starting point.

Imagine you have a circular track, and four segments of the circle, each representing the gas station's distance potential (the left edge shall be the gas station's location, the right edge shall be how far that station's gas will carry you). Place the segments any way you like on the track (though they may not overlap; overlap is double-burning gas. We 'compensate' for that by placing them adjacent, representing the total distance travellable on the gas in those two stations). You have a 5th segment representing the initial tank. All 5 segments form a complete circle.

In order for the trip to be impossible, you would have to arrange the 4 pieces in such a way that it would not be possible to cut up the 5th piece and fit it into the track without space left over. Since we know that the sum of the 5 segments (no matter what their division or arrangement) always equals a full circle, we can conclude that the trip must be possible.

We can then conclude that after placing the first 4 station pieces, any empty space in the track before the station with the most gas is a valid starting point that will enable you to complete the full trip.

In the edge case where your initial tank is empty (that is, your 5th segment is null-sized), you may start at the station with the most gas and complete the trip.

Re: Hiring the Smartest People in the World

#27

Post by cheald »

cncool wrote: post #19
lllbean wrote: post #15

Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…

For question 3, it clearly states two things: "the total amount of gas available at the stations and in the car is exactly enough for the car to drive around the road once" and "the car completes a full circle without running out of gas" Given the first condition, in your solution, at the exact moment the car completes the drive around the track, it runs out of gas. Therefore, it is impossible to complete it without…

1) Momentum!

2) The implication of the question is not "can you complete the trip with gas left over", but rather "can you complete the trip". If the requirement is that you must have gas left over, then barring a trick answer, the problem is trivially answerable as "false".

Re: Hiring the Smartest People in the World

#28

Post by [deleted] »

lllbean wrote: post #15

Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…

[deleted]

Re: Hiring the Smartest People in the World

#30

Post by hnhg »

lhnz wrote: post #25

Most companies do not need to hire the 'smartest people in the world'. They also don't need the 'hardest working people in the world' or the 'most creative people in the world'. Sometimes a company needs the very best people -- and they can try to define what this means to themselves and then filter for it. However, generally they need people that can solve the problems that they face to an above market-rate level of…

You forget the value of people who work well together as a team. Individually they might not be anything special but together they can produce great results.

Personally, I hate the idea of abstracting people out to fungible goods that a company buys in because it's a cop-out and an over-simplification. Putting together a group of people in a team is as much a social challenge as it is ticking technical requirements.

Post reply on HN