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

History of massive-scale sorting experiments at Google

cloud.google.com

Post reply on HN
Print view View original

71–80 of 82 posts

Re: History of massive-scale sorting experiments at Google

#71

Post by xiphias »

wantreprenr007 wrote: post #61
AI_Overlord wrote: post #47

Earlier quoted context omitted.

Emotions are not a requirement for strong AI. I frankly would not waste any time with them. I just need an AI that can learn and solve problems at the human level. I'm not naive enough to think that it can be solved in a short time. I do think that it is worth it for a person to spend the rest of their life working on it. There is just nothing more exciting than AI in my opinion. Just imagine the possibilities...

"Narrow" AI is already here: search, banking, insurance, internet ads, crime prediction, Siri, plane autopilot (autotakeoff/landing too), autoparking, driver assist, on and on. (At Trimble, we had fully autonomous tractor PoC in 2001) "Deep" AI (self-directed / human-interactive) will take more time and effort, and can have (simulated) emotions if so programmed; the determinate is how to sell such as a viable product…

Deep AI already started with deep learning, which improves exponentially every year, if you look at the performances. It already freaks me out that you can put together cheap drones+guns+self driving+better-than-human level face detection. Imagine controlling a drone botnet...

Re: History of massive-scale sorting experiments at Google

#72

Post by vijucat »

If you know the distribution of the data (which can be imputed as part of the sorting process by sampling the data), it is possible to guess if the next number is going to be larger or smaller than the current one 75% of the time without looking at it by using Cover's pick the largest number trick [1, 2, 3]. I wonder if distributed sorting algorithms know and incorporate this, which should reduce the cost of hitting the network in distributed algorithms considerably? (Asking because I don't work in that field; this is just an idea that I had).

References

1. "Playing a Trick on Uncertainty" by Thomas Bruss, page 7 of http://www.emis.de/newsletter/newsletter50.pdf

2. "Tom Cover’s Number Guessing Game" by Robert Snapp, http://www.ibrarian.net/navon/paper/Tom_Cover_s_Number_Guess...

3. "Who discovered this number-guessing paradox?", https://math.stackexchange.com/questions/709984/who-discover...

Re: History of massive-scale sorting experiments at Google

#73

Post by p4wnc6 »

rhizome wrote: post #58
p4wnc6 wrote: post #41

Earlier quoted context omitted.

Even so, it only pays to be conservative via an overly selective filter if that filter actually selects for what you want. If you zealously apply some filter, believing that you're being extra cautious, but the filter doesn't actually select for what you think, or the filter isn't actually as selective as you think, then it's just a form of selectivity theater. I've met plenty of ex-Googlers who were great at recitin…

I don't doubt it. They've got a (evolving) process that has a lot of false negatives. The creativity vaunted by the earlier poster is more common in the rejects, and as a long-time Android (and Google) user I can draw a correlation. And none of this counters that Google's hiring process has been engineered to produce a conservative model of acceptible employee.

I'm saying it produces false positives. False negatives are ok for a conservative hiring process, because you're paying for a super low false positive rate with a higher budget for false negatives.

But the whiteboard hazing produces too high a rate of false positives -- candidates who can recite CS trivia, study in a way tailored and overfitted to the interviews, and then pass them and be hired even if they don't actually have the broader skills that the interview was designed to conservatively filter for.

I speculate that new hires at Google aren't much better at anything than new hires anywhere else. They might become better later due to a compounding returns effect of already being at Google, but the hiring process didn't select them because they already were better. Instead, the hiring process is a status show, selectivity theater, to enhance the promotional reputation of a business-conquering nerds stereotype and to enhance Google's bargaining power by convincing people that they are only worthwhile to the extent they jump through interview hoops.

Re: History of massive-scale sorting experiments at Google

#75

Post by saalweachter »

fapjacks wrote: post #33
dpe82 wrote: post #29

Earlier quoted context omitted.

Part of the magic of working at Google is there are lots of projects that can make you feel that way.

From what I understand, those kinds of projects are only available to certain engineers, and the vast majority of engineers working at Google don't get to play those games. Six of my seven interviewers essentially said that they did not get to work on problems that challenged them when I asked "If you could change one thing without veto...." This is actually one of the two big reasons I chose not to accept an offer.

Eh, there's an important thing to realize about working at a company like Google.

1. As a programmer, you will feel most productive working on a project by yourself where you just pound out thousands of lines of code.

2. The secret to how you get 100x more done than any individual programmer can do is that you have 200 programmers working together feeling 50% productive.

3. Google has no interest in projects that can be accomplished by one brilliant engineer working by themselves.

It can be really unsatisfying for a programmer, because we all learn to program individually and that's what we base our "am I being productive?" feeling on, but it turns out that you can do some really amazing things if you're willing to put that aside and work together, even if it means spending half your day in meetings and checking email or writing design docs that no one reads.

And if you're feeling challenged, it's probably because you're doing something convoluted and even you won't remember how it works in six months and no one will be able to maintain it and you can actually get nearly equivalent performance out of three mapreduces and a drop-in machine learning model, so maybe you should just do that?

It's not for everyone, but at the end of the day would you rather feel productive and challenged, or actually change the world a little bit at a time?

Re: History of massive-scale sorting experiments at Google

#76

Post by dpe82 »

thrownaway2424 wrote: post #45
fapjacks wrote: post #33

Earlier quoted context omitted.

From what I understand, those kinds of projects are only available to certain engineers, and the vast majority of engineers working at Google don't get to play those games. Six of my seven interviewers essentially said that they did not get to work on problems that challenged them when I asked "If you could change one thing without veto...." This is actually one of the two big reasons I chose not to accept an offer.

"Moving huge amounts of data from hither to yon" is not a specialized role at Google. Anybody with solid C++ skills can find a way to work on that.

Heck if that's the metric anybody familiar with SQL or even basic unix command line operations can do it if they really want. It's sometimes easy to forget how much data we regularly move around without really thinking about it.

Re: History of massive-scale sorting experiments at Google

#77

Post by eru »

existencebox wrote: post #48
eru wrote: post #36

Earlier quoted context omitted.

> I was not interviewing for a high theory/deep algorithms [...] Implementing a well known data structure is pretty far removed from `deep algorithms' and `high theory'.

Honest question; are you able to recall or extrapolate all of the rotations on the fly in a 45 minute time slice? For what metric it is, I've been succeeding well enough at comparable positions for nearly a decade since then, and in that time I've met a single engineer who could have pulled that off without prep, I likely still would have trouble with not leaving some bits out. I don't ask this to be dismissive, I ju…

> Honest question; are you able to recall or extrapolate all of the rotations on the fly in a 45 minute time slice?

Yes, easily. The invariants are pretty simple. For extra fun, I'd try to enforce them via the type system. Though honestly, if you'd try to do red black trees in a language like Java or C++ you'd probably get a headache.

(Just follow Okasaki's simple approach there. See https://wiki.rice.edu/confluence/download/attachments/276121...

Functional languages make the typical Google / Facebook style interview much easier.)

> (Thus my "high theory/deep algo" exemption statement, specialists who really have to get that deep I might expect to be familiar with something like this offhand)

I guess my perspective is tainted there. I know some things about algorithms and datastructures, but some people I admire as `specialists' know so much more.

Re: History of massive-scale sorting experiments at Google

#78

Post by hueving »

skj wrote: post #74
hueving wrote: post #46

Earlier quoted context omitted.

Because they are a really crappy approximation of how good someone is.

Feel free to suggest a viable alternative.

I didn't imply that I have one. I was just explaining why Google shouldn't be proud of what they do.

Re: History of massive-scale sorting experiments at Google

#79

Post by rockinghigh »

amelius wrote: post #69
rockinghigh wrote: post #51

Earlier quoted context omitted.

If you sort records by time you can perform time range queries. You can also create an index to access random keys (like a MapFile in Hadoop).

But isn't sorting by time easy, because records come in the correct order? I would say you don't need an algorithm for that.

You may want to sort by settlement date instead of transaction date. There are plenty of examples where you need to sort before you can index: let's say you want to create a spatial index. You first need to sort/group spatially (by tile) to query an area.

Re: History of massive-scale sorting experiments at Google

#80

Post by rhizome »

p4wnc6 wrote: post #73
rhizome wrote: post #58

Earlier quoted context omitted.

I don't doubt it. They've got a (evolving) process that has a lot of false negatives. The creativity vaunted by the earlier poster is more common in the rejects, and as a long-time Android (and Google) user I can draw a correlation. And none of this counters that Google's hiring process has been engineered to produce a conservative model of acceptible employee.

I'm saying it produces false positives. False negatives are ok for a conservative hiring process, because you're paying for a super low false positive rate with a higher budget for false negatives. But the whiteboard hazing produces too high a rate of false positives -- candidates who can recite CS trivia, study in a way tailored and overfitted to the interviews, and then pass them and be hired even if they don't act…

It's not a false positive if they aren't testing for the thing that turns out to be positive. That people express creativity or whatever, despite making it through an employment filter based almost solely on technical concepts.

It's just luck.

Post reply on HN