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

41–50 of 66 posts

Re: Hiring the Smartest People in the World

#41

Post by alexchamberlain »

pantaloons wrote: post #32
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…

1. Not constant space. Not linear time. 2. Not constant space. Not linear time. 3. Looks correct.

1. How's it not constant space?

Re: Hiring the Smartest People in the World

#42

Post by Gupie »

Aren't the first two problems simple to solve:

1. create an array length n of booleans set to false, set the each index i to true for the integers in the array, the index of one still false is the missing integer 2. same as 1 but with a count

Both are O(N) but perhaps my understanding of what constant space means is flawed?

Re: Hiring the Smartest People in the World

#43

Post by hristov »

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…

All of your solutions work. I am curious however, are you new to HN or did you start a new ID just so you can brag about how much of a badass you are?

Re: Hiring the Smartest People in the World

#44

Post by drostie »

cncool wrote: post #37
pantaloons wrote: post #32

Earlier quoted context omitted.

1. Not constant space. Not linear time. 2. Not constant space. Not linear time. 3. Looks correct.

1. How is this not linear time?

Because as the numbers increase, their storage requirement also increases.

Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number.

Given this, any algorithm which only uses O(n) instructions cannot asymptotically read the whole array, and this presents a fundamental limitation on the problem. Technically, there cannot be a solution better than O(n log n) for this reason -- unless you get lucky and find the duplicated element in the very first O(n) of the array, you will miss it in the last O(n log n) of the array.

The larger problem is that there is a fundamental confusion here. Really you should say that the array is some permutation of [1, 2, 3, ... m] and that n = m log m is the input size, and then ask whether algorithms run in linear time relative to n, not relative to m. This allows you to read in the array. You still have the problem that you have storage which grows like 1 + log m, though.

Re: Hiring the Smartest People in the World

#45

Post by cncool »

Gupie wrote: post #42

Aren't the first two problems simple to solve: 1. create an array length n of booleans set to false, set the each index i to true for the integers in the array, the index of one still false is the missing integer 2. same as 1 but with a count Both are O(N) but perhaps my understanding of what constant space means is flawed?

"create an array length n of booleans"

This could have a space complexity of O(n), not O(1).

Re: Hiring the Smartest People in the World

#46

Post by thaumasiotes »

Gupie wrote: post #42

Aren't the first two problems simple to solve: 1. create an array length n of booleans set to false, set the each index i to true for the integers in the array, the index of one still false is the missing integer 2. same as 1 but with a count Both are O(N) but perhaps my understanding of what constant space means is flawed?

yes, "create an array of length n" requires O(n) space.

Re: Hiring the Smartest People in the World

#47

Post by Wilya »

gaius wrote: post #35
drewcrawford wrote: post #8

People tend to hire, not so much the best people they can find, but the people who are most like themselves. And if you hire people like yourself, and your job ad says "We hire the smartest people," then you must be the smartest people! I've found it to be a huge negative signal. These sorts of interviews seem to mostly be about developers patting themselves on the back about how they stumped the applicants in interv…

Maybe if you are Google Yes, ad sales is the most pressing issue facing humankind.

While I don't specially disagree with you, the difficulty of a problem and its benefit to humanity are two completely orthogonal issues.

The fact that it's ultimately aimed at selling ads doesn't make what Google does (for example) in NLP an easy task.

Re: Hiring the Smartest People in the World

#48

Post by brohee »

Gupie wrote: post #42

Aren't the first two problems simple to solve: 1. create an array length n of booleans set to false, set the each index i to true for the integers in the array, the index of one still false is the missing integer 2. same as 1 but with a count Both are O(N) but perhaps my understanding of what constant space means is flawed?

Your solution is in O(N) space, since you create a N sized array.

The elegant solution to the first problem requires big integers in a realistic setting, and simply involves summing all the numbers and comparing with what the sum of 1 to n should be (n(n+1)/2 iirc).

Re: Hiring the Smartest People in the World

#49

Post by gnud »

hristov wrote: post #40
ckuehne wrote: post #34

I very much doubt that the OP can solve either problem 1 or problem 2 with constant space. Hint: even storing an additional integer N requires \Omega(log(N)) space. Edit: For the down voter: I searched around and found a discussion of the puzzle [1]. Please go ahead and read it. [1] http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&#38...

I am not sure how you got downvoted but the constant space requirement seems a little puzzling. When the problem says that you are given a list of n numbers (or, more correctly, n-1) you are already in linear space. You have to store the list somehow. Maybe they meant "constant additional space". Or constant space for the data you are using in addition to the space required for the inputs. That however tends to go ag…

It's fairly standard to talk about how much auxiliary space an algorithm needs - in sorting, for example. I guess that's what the author means.

Re: Hiring the Smartest People in the World

#50

Post by pantaloons »

drostie wrote: post #44
cncool wrote: post #37

Earlier quoted context omitted.

1. How is this not linear time?

Because as the numbers increase, their storage requirement also increases. Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number. Give…

The larger problem is the cult of "Big O" and its use as a form of signalling in interviews.

If I wanted to test whether a candidate understood Big O, I'd ask them if there was a difference between O(1) and O(0). What these companies want is to see if the candidate understands program performance in general. Big O is the vogue (in my view misguided) way to do that.

Post reply on HN