Help wanted: Google hiring in 2011

Google gets resumes and random text from 1000s of people a day looking for a job, all over the world, completely bereft of any sort of qualification. That's the vast majority of resumes any large business like Google will see. It's like Spam writ large.

So we have resume screeners who look at those random resumes and try to separate wheat from chaff. For some, we have a phone screen that is literally to check the most basic of facts to see if the resume is at all consistent with the name at the top, then a real phone screen with an engineer, then an onsite, then offer.

Each step loses people, but the first, separating the clear bs from the real is where the huge gap comes from.

That said, I hope we have more false negatives than false positives every step of the way, and for that, all I can say is that I wish it didn't have to be that way. Well, that, and this: Get referred by a Googler, skip many of the above steps :-)

My shot: pick some random number, go through that many linked list items and return the item you're at. Only needs to store the current item pointer and the random number. Maybe I'm missing something simple, though to be fair, it's a lot harder to answer these kinds of questions when you're under the scrutiny of an interview.

If the goal of the question is to select a random item where all items have the same probability of being selected, it's impossible. If you're willing to ditch even distribution, then one answer is:

    value pickRandomItem(node* list) {
        /* Always return first item. */
        return list.value;
    }

This question seems ill-defined. Assuming you interpret "random" as "have an equal probability of returning any given element", then the probability is 1/infinite which is undefined.

I think there could be three possiblities:

A) The interviewer was baiting your friend into trying to elaborate the problem, in a "my client is asking me to do something absurd but I'll try to piece out his actual intent" sort of way. If so, you could come up with some hypothetical scenarios this algorithm would solve and show how actual problems would have actual bounds on how far the random window needs to go.

B) You could be remembering the problem wrong. It could be "Given a finite linked list whose length you don't know a priori..." instead. This is much more tractable as a stereotypical tech interview question.

C) Return the ninth element. http://dilbert.com/strips/comic/2001-10-25/

I assume they meant arbitrarily long instead of infinitely long. In which case, I just wrote that code today:

  val := nil
  for i, x in range a {
     if rand.Intn(i+1) == 0 {
         val = x  
     }
  }

What would we have done if we knew the length? We could pick a random number between 1 and the length, and then traverse that many items to get to our random item. Since we don't know the length, it means the question is, how will you know where to stop?

Constant growth for storage means you start with a fixed number of slots (lets call this number X) and keep them through the process. You could put items into these X slots, such as one out of every ten that you pass. That would mean you could pick items by rolling a 10-sided dice that shows a 10, and put them into one of the slots.

A problem is that you would have to remove past randomly-selected numbers to make room for new ones, and you would be biased towards items that appear later in the series. This would not be random.

And what about a string one character long (in this case, we can pretend we had been given an array, a string, a queue, or whatever) ? What if, at the start, we always select the first item to be the random choice? That would mean that an abrupt stop would give us the correct answer for a length of one. Another interesting thing is that we can store item one into a single container, instead of needing X (where X is a constant) slots.

What about two? Well, we would compare the container with item two and decide that the random choice for the container should be either what it already contains (item one) or item two, with a 50/50 split. Great! So our algorithm works for a length of one as well as two.

This is starting to feel like we've established a base case (what happens when the list has only one item?). We may be on track to show that constantly looking at the next item and comparing it to the one in the container may just work. If so, we could have a proof by induction.

So if we were at item three where the whole list is only three items long, then a random generator would have picked it with a probability of 1/3. So if we're comparing item three to whatever is in the container, then if a 3-sided dice rolls a 1, we can set container to be item three. That works. But what about the other 2/3 chance, where it could be item one or two? In that 2/3 chance, we pick the container. The container contains only one item (the first or the second, whichever one won the first coin flip previously.) For this to be a valid idea, both item one and item two should have had a fair chance to be in the container currently with a 50/50 split, correct? And we know that it was.

So when we come to item four, we replace the container with item four with a probability of 1/4, or use the value in the container with probability of 3/4 (e.g. 1-1/4 = 3/4, or the rest of the time.) The point is that at each step, the container contains the random value of the previous n-1 number of items.

http://stackoverflow.com/questions/1840618/fast-random-selec...

BTW, this actually is a practical question, because it's isomorphic to "How do you select a random element from a stream of elements when you don't know the length of the stream a priori?" This is crucial for many online algorithms. For example, imagine that you're FaceBook and you're trying to display a News Feed of a massive number of events coming in from a large number of apps. You don't have the computational power to handle all of them, and so you need to drop some of them on the floor. How do you fairly drop events and display only a random sampling of them?

My impression is that it's no so much "encouraged" as required. "Publish or perish" (academia), "up or out" (military), and "20% time" (Google) are all roughly equivalent. Roughly.

  > My experience has been that the top tier companies are all selective
  > and keen to avoid false positives. Google is really no different
  > in this regard.

Unless you're looking for something very specific?

Chrome has by far the best UI of any web browser I've used. Google Search has the best UI of any search engine I've ever used. Google Calendar has the best UI of any electronic calendar I've used. And so on.

Do they have as good UI as a specialist graphic design company? Maybe not. Against any tech company however, they stack up pretty damn well, despite what Gruber might claim.

[1] http://theinvisibl.com/2009/12/08/chrometabs/

The other direction is a combination of hard and unsexy. VMWare had the highest base pay in the Bay Area when I left. I'm in Australia now and it seems like the highest pay for a software developer is to work with a mining company. Of course, if you are in NYC, there's always some financial thing.

Then again, I'm on the market and have been poking around and thought the proposed compensation at places like Apple and Google was pretty good. If your career goal is a stable job that pays $250K a year, software isn't the right field.

(If you are a good engineer) You'll be bored out of your skull and you'll drown in middle manager games and meaningless meetings. But they pay very well.

They can, but they do not. The average salary may be lower as they hire more engineers out of college, but if you're an experienced engineer and have other offers, you'll get a good deal. There is, however, another other angle: they want 99 percentile talent, but are in the 75th percentile compensation wise. So a $130,000 ($100k + 30% bonus) at Google could easily be $150,000 elsewhere. However, this market value may not be realized until the said person has been at a 'brand name' company i.e., some will leave because having been at Google has made them much more valuable in the eyes of employers.

> Oracle? Something else?

Oracle pays worse, actually. Unlike Google and other companies, they also have strict rules about salaries for people with X years of experience: many excellent engineers left Oracle (and yes, Oracle can attract excellent engineers -- mostly to their database and middleware divisions) because they were told by their managers they wouldn't be able to receive any recognition for their work until they have spent N years at the company.

Your master's degree does not have much of an impact, but I know personally of strong performers at Google with 3-4 years of experience who are receiving 135k-150k in base salary + other goodies such as their obscene bonus scheme and stock grants.

if you are a star dev, you can always try your luck on wall street firm, D. E. Shaw., Knight Capital and such.

For example, in 2000-2005 I had all kinds of ideas for things I wanted to do, but ultimately got discouraged by the fact that, even though I had excellent software development skills and great ideas, I lacked the capital and knowledge to, for example, set up a rack of servers or a bank of fax machines in a closet somewhere. Today, in stark contrast to even 2005, those kinds of hurdles are totally gone. It's very easy to get servers set up in the cloud to do whatever you need.

Also it's far easier to succeed independently than it was a few years ago. In the computer games space, where I make my money, self-publishing is a seriously viable alternative now (I'm living proof!), where a few years ago you mostly needed to work for a game studio to actually make a living.

Google is still a god-like entity that many of us would love to work for, but there's a comparatively new form of competition that's probably hitting Google harder than ever before: the fact that it's 10x more viable to do your own thing today than it was in 2005 or 2007.

Basically...YMMV. I suspect that a lot of any individual candidate's experience will come down to which recruiter and interviewers they happen to draw.