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

61–66 of 66 posts

Re: Hiring the Smartest People in the World

#61

Post by mattmanser »

Wilya wrote: post #47
gaius wrote: post #35

Earlier quoted context omitted.

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.

How many google programmers are actually doing that though?

Compared to something inane and dull like the number trying to get the logins for all the different services actually working with each other properly?

Re: Hiring the Smartest People in the World

#62

Post by pantaloons »

ckuehne wrote: post #60
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...

Thinking about it, it comes down to the level of analysis you choose. If you assume constant space per integer, then it is indeed solvable with O(1) additional space. For example, this is usually assumed when analyzing sorting algorithms and I guess this is also what the author had in mind.

If you limit n then than the algorithm is actually O(1) time too -- his answer is wrong either way.

Re: Hiring the Smartest People in the World

#63

Post by Robin_Message »

brohee wrote: post #48
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).

I don't think it requires big integers. If you do it with machine words, the overflow/underflow will exactly cancel out so you will be fine. I think.

If that's not true, then adding each x and subtract i as you process it is sufficient to ensure you only need integers comparable in size to N, not N^2.

Re: Hiring the Smartest People in the World

#64

Post by zheng »

6ren wrote: post #56
zheng wrote: post #10

Earlier quoted context omitted.

The problem wasn't misstated, when they aren't in order the solution isn't obvious unless you remember a bit about sums. Most interview problems, if restricted, can either be solved very quickly, or aren't interesting anymore. Either way, as it was stated, it's a fairly common interview question as another comment has pointed out.

The question states they are in an order - ah, by that, they probably mean "not ordered".

You're probably right, although as of right now it reads "in some order", ergo there is no guarantee that i comes before i+1 for all i. It could have been updated though.

Re: Hiring the Smartest People in the World

#65

Post by jobmatchbox »

noonespecial wrote: post #38

"Hiring the smartest people" is always great right up until the "paying slightly above market rate!" part. If you really are hiring the smartest people, what you are paying them should leave average people with their chins on the ground(1). If this is not the case, then I wish they'd quit bragging, because the smartest people aren't working there. (1) This and/or have about the coolest place to work on the most inter…

There are people who volunteer to work on things like Presidential campaigns and for startups because of who they are working with rather than because of what they are being paid.

Re: Hiring the Smartest People in the World

#66

Post by IsTom »

alexchamberlain wrote: post #54
drostie wrote: post #44

Earlier quoted context omitted.

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…

I disagree. The array is stored outside of your algorithm. The algorithm is constant space.

You still need to read O(nlogn) bits of the array. It can't take less than O(nlogn) time.
Post reply on HN