6 ms·
Hiring the Smartest People in the World
- olliesaunders 14y agoBetter title: Acing The Interview Doesn’t Mean You’ll Be Hired. No explanation why though. Envy?
- arethuza 14y ago"The problems were so difficult that he wanted to sit with me and read them together to make sure that I understood them" That sounds slightly condescending to me, especially as the problems don't sound that complex to describe and he is a mathematician! It doesn't surprise me that someone who takes that attitude reacts badly to someone easily solving a problem that they couldn't.
- theallan 14y agoI'd suggest more that the interviewer felt threatened rather than envy. From their point of view, they would have someone smarter than them working under them, who might show them up to senior management or displace their current position in the company.
- maak 14y agoProblem solving is only part of what makes a good employee.
- pja 14y agoBecause being able to solve puzzle problems isn't actually a good predictor of employee quality? (It remains an open question why interviewers use them at all in that case.) Many interviewers do not (in reality) want to employ people who are obviously better than them, whatever they may say in public?
- alexchamberlain 14y agoA quick Google will find you the answer to the first question. The second just requires an additional equation, where people are suggesting powers in finite groups. This seems rather complex. Can we not reach the same constraints by only summing the even numbers, for instance?
- Feanim 14y ago1°: 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 = px}
- alexchamberlain 14y agoSorry, can you expand on what you meant by that?
- gsa 14y agoSum 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).
- emillon 14y agoIf 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.
- hristov 14y agoThe 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.
- alexchamberlain 14y agoIt also requires one to assume n! can be computed. Factorials get huge very quickly.
- drostie 14y ago
- drewcrawford 14y agoPeople 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 interviews. I think we need to have the talk about the "hire the smartest developers" meme in our industry like the web hosting industry talks about five 9s of uptime. The first nine is writing FizzBuzz. The second nine is being able to design and maintain large systems. The third nine is knowing the finer points of Prim's and Dijkstra's and a copy of TAOCP with arbitrary dust coating on the shelf. Do you really need talent that meets a higher standard than that? Maybe if you are Google or NASA. But if you are not launching things into space, you don't need to hire the world's smartest people. Certainly, there is a spectrum between 'we write CRUD software' vs 'we read journals and do some novel algorithms work', and a company in the second category will want to say something positive about the intelligence of their employees as a signal. But "we hire the smartest people" is absolutely the wrong thing to say. "Smarter" is not even better once you've hit the threshold of "acceptable number of nines to write this program." I routinely pass over hiring extremely smart people. Some of them have abrasive personalities, or are the wrong cultural fit, or are not interested in the problem domain, etc.
- sparknlaunch12 14y agoTeam fit is important. However definitely want smarter people around us. That is why they are selected otherwise we would do the job ourselves.
- troels 14y agootherwise we would do the job ourselves Only if you have infinite time at hand.
- gaius 14y agoMaybe if you are Google Yes, ad sales is the most pressing issue facing humankind.
- 6ren 14y agoFor the first one, if they are in an order, and in an array, you can do a binary search, O(log2 n) time - better than linear time. Perhaps the question was misstated. Also, the friend's relationship is accidentally disclosed as a son.
- zheng 14y agoThe 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.
- deleted 14y ago[deleted]
- 6ren 14y agoThe question states they are in an order - ah, by that, they probably mean "not ordered".
- zheng 14y agoYou'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.
- jyothi 14y agoyeah i noticed the "son's interview" part in first read itself - it was amusing O(n) solution for who the friend is.
- timthorn 14y agoI used to work at a company inordinately full of extremely smart people. The issue there was the lack of absolutely competent but not stellar thinkers - the people to do the grunt work. I'm convinced that in most engineering companies you need a good mix, biased towards the competent types.
- lllbean 14y agoSolution 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 binary string) must contain at least one 1. So there is some digit where the binary representation of x differs from the binary representation of y. Let this digit be the ith digit. Let's say that a number is good if the ith digit of its binary representation is a 1. Let's call numbers that aren't good bad. Observe that exactly one of x, y is good, and the other one is bad. Let S be the number that we get by doing this: S = 0 for j in 1..n: if j is good: S = S + j if j is bad: S = S - j Let T be the number that we get by doing this: T = 0 for j in our_list_of_numbers: if j is good: T = T + j if j is bad: T = T - j We find that S - T = x + y or -(x + y). Since x + y is positive, we can find x + y in either case. We have x + y and x - y, so we can find x and y. Solution to problem 3: imagine that we have a car, car 1, that has a really big tank with a bunch of gas in it. Put car 1 somewhere on the track and have it drive one complete revolution. The amount of gas G in the tank of car 1 varies over time, but at some point P on the track, G reaches its minimum value. P has to be at a gas station. (Otherwise G would be lower at a point right in front of P.) If we take our regular car and start it (with an empty tank) at point P, it's pretty easy to see that it'll make it all the way around the loop. Because if it didn't, then at some point Q it would run out of gas. Q wouldn't be a gas station, otherwise our car would refuel; so there's some point Q' in between Q and the next gas station from Q. Then driving a car from P to Q' results in a net loss of gas. Then when car 1 drove around the track, it should have had less gas at Q' than it had at P. (That's not 100% obvious in the case where car 1 drove past point Q' before it drove past point P, but it follows from the fact that car 1 had the same amount of gas when it finished as when it started.) Contradiction. Fuck yeah, I'm a badass.
- cncool 14y agoFor 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 running out of gas.
- deleted 14y ago[deleted]
- lhnz 14y agoMost 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'.
- hnhg 14y agoYou 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.
- cheald 14y agoThe 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.
- matthieupiguet 14y agoI always beware of the "we want the best of the best" companies. Usually they are looking for the "best that don't show it if they are smarter than the boss". That's a shame ...
- sakri 14y agoso was it her friend or her son?
- jyothi 14y agoit was either Sergei or Alexey. Brenstein btw
- ckuehne 14y agoI 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&dq=muthukrishnan+data+stream+algorithms&hl=el&pg=PA1&redir_esc=y#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&...
- hristov 14y agoI 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 against the main principles of complexity theory and O-notation. The main principle of O notation is that you mostly care on how things grow as n becomes large. Thus, constant terms should be deleted if you have a linear term. In other words, if you have something that adds constant space to linear space, you get linear space. Thus, if you already have something that requires linear space, and have to add something else to it, it is not that important (for complexity theory purposes) if the second thing is in constant space, or log space or even linear space, as long as it is smaller or equal to linear space.
- gnud 14y agoIt'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.
- ckuehne 14y agoThinking 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.
- noonespecial 14y ago"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 interesting problems in the world.
- jobmatchbox 14y agoThere 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.
- Gupie 14y agoAren'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?
- cncool 14y ago"create an array length n of booleans" This could have a space complexity of O(n), not O(1).
- thaumasiotes 14y agoyes, "create an array of length n" requires O(n) space.
- brohee 14y agoYour 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).
- Robin_Message 14y agoI 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.
- raverbashing 14y agoSo, here's the thing, and you can be guilty of this too! If you're too worried about the answers matching your little pop quiz, sorry, you're doing it wrong I know G needs the users to know what they ask, and their business stand on scalability, still There is so much more! The article is just one example where google fails (yes, it doesn't say it's google: it's google) And you solved it in O(n) where they want an O(n log n) solution?! What are they thinking of refusing this? You can be a specialist on several other technologies and techniques that are not asked in the interview it's not even funny. Discrete math, code optimization, machine learning (yeah, ok, Norvig is there, and they do that a lot, still), graphics rendering, etc, etc
- deleted 14y ago[deleted]