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

41–50 of 82 posts

Re: History of massive-scale sorting experiments at Google

#41

Post by p4wnc6 »

rhizome wrote: post #39
p4wnc6 wrote: post #30

Earlier quoted context omitted.

> genuinely had tough problems where if they accidentally did something in O(N^2), their half-day compute job would suddenly literally take centuries to complete. Yes, but this has almost zero bearing on the actual interview. Being able to avoid this in real life means that you measure twice and cut once, you pay attention, and you ask for help and training. Being able to do something similar with dynamic programming…

I think what the GP was illustrating is that Google is extremely conservative. For them to hire people outside of the strict boundaries of, "dimensions of skills as represented in an interview," is kind of a rejection of the Robustness Principle for corporate purposes. I mean, heck, something like this? They interview multiple magnitudes of people necessary for this kind of job. I respect it as a hedge, but it probab…

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 reciting CS trivia, but actually not very good at real life engineering. Granted, that may be why they were ex-Googlers, but it still doesn't speak well of Google's hiring process.

Re: History of massive-scale sorting experiments at Google

#42

Post by rl3 »

AI_Overlord wrote: post #35

To each their own. While impressive I do not find it inspiring. Instead, working on strong AI is, in my mind, the ultimate challenge. Far more amazing by any measure than anything we have acomplished so far.

Who is to say the data requirements of an AGI won't be massive? Figuring out efficient 50PB sorts might just be a required step.

Even if it isn't, it's unreasonable to expect the world to stop spinning in the interim.

If a superintelligent AGI is born tomorrow, it might just establish itself as a singleton, prohibit other AGIs from exisiting, and then take an indefinite vacation. If that happens, we'll continue to work on seemingly mundane, non-important problems (such as this one) for humanity's foreseeable future.

Don't forget that Google owns DeepMind. If there was a way to divine who's closest to AGI at the present time, the answer would probably be them (even if arrival is ultimately far off).

Re: History of massive-scale sorting experiments at Google

#43

Post by AI_Overlord »

seiji wrote: post #38
AI_Overlord wrote: post #35

To each their own. While impressive I do not find it inspiring. Instead, working on strong AI is, in my mind, the ultimate challenge. Far more amazing by any measure than anything we have acomplished so far.

working on strong AI is, in my mind, the ultimate challenge. So is working on antigravity, free energy, and backwards time travel, but people don't do that because they are no reasonable approaches we can try. Glorifying "AI AI AI" is silly because — there are no approaches we can try. Sure, we can identify ten million images per second, but none of that involves the least bit of "thinking."

Evolution has already proven that strong AI is possible. It is up to us to discover how. It is only a matter of time.

Re: History of massive-scale sorting experiments at Google

#44

Post by seiji »

AI_Overlord wrote: post #43
seiji wrote: post #38

Earlier quoted context omitted.

working on strong AI is, in my mind, the ultimate challenge. So is working on antigravity, free energy, and backwards time travel, but people don't do that because they are no reasonable approaches we can try. Glorifying "AI AI AI" is silly because — there are no approaches we can try. Sure, we can identify ten million images per second, but none of that involves the least bit of "thinking."

Evolution has already proven that strong AI is possible. It is up to us to discover how. It is only a matter of time.

Just one summer of study and it'll be solved, right? It's always been "one summer away" for the past 60 years.

Get back to us when you have an algorithm for love and art and petrichor.

Re: History of massive-scale sorting experiments at Google

#45

Post by thrownaway2424 »

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.

"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.

Re: History of massive-scale sorting experiments at Google

#46

Post by hueving »

skj wrote: post #27
theoh wrote: post #25

Earlier quoted context omitted.

"an idea of the dimensions of your skillset" sounds like a really reductive way of thinking. It's as if the skillset is restricted to something easy to quickly explore and visualize, like a convex object in a few dimensions. Maybe those assumptions are necessary for interviewing but they're nothing to be proud of.

Why would they be something to be ashamed of?

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

Re: History of massive-scale sorting experiments at Google

#47

Post by AI_Overlord »

seiji wrote: post #44
AI_Overlord wrote: post #43

Earlier quoted context omitted.

Evolution has already proven that strong AI is possible. It is up to us to discover how. It is only a matter of time.

Just one summer of study and it'll be solved, right? It's always been "one summer away" for the past 60 years. Get back to us when you have an algorithm for love and art and petrichor.

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...

Re: History of massive-scale sorting experiments at Google

#48

Post by existencebox »

eru wrote: post #36
existencebox wrote: post #14

Earlier quoted context omitted.

As a datapoint, a while back I was asked (for a G interview within the last 10 years) to code an RB tree from start to finish. I'll admit I was a little miffed at how distanced this seemed from anything I would potentially do; I was not interviewing for a high theory/deep algorithms group. That being said, in my other experience with a G interview, the entire process was much more mundane and as expected. For the rec…

> 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 just find this expectation that an RB tree is "well known" to be incongruous with the skill sets I've seen in a large number of thriving industry engineers in the roles that would have been relevant to me. (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) Broad knowledge about the algo, sure. To replicate the finer points of the implementation ad-hoc? I'm skeptical; and even if you can, the correct answer in most positions sans my exemptions would be "use a library", and as such I tend to prefer interviews that ask more relevant questions.

Keep in mind, this whole point was initially stated to contrast the RB tree question to many more "typical" interviews, and suggest that these outliers are just that, outliers; They certainly have been in my experience.

Re: History of massive-scale sorting experiments at Google

#49

Post by haberman »

seiji wrote: post #40
KMag wrote: post #19

Earlier quoted context omitted.

I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…

The encoding actually used is that the first bit of every byte is a flag for if there's a next byte, for a maximum of 10 bytes. Fun facts: those are commonly known as "vbytes." They are the slowest kind of variable width integer encoding. The simplest (naive, and generally considered "wrong") implementations of variable-width-by-continuation-bits uses 10 bytes maximum. A proper implementation uses 9 bytes maximum. Th…

> Using this scheme also kills any "1 byte, standalone, variable width integer" capability (unless you're storing partial values in the first T/L byte, but then that limits you to a much lower max value for one byte).

You can get the best of both worlds. The way to do it is: separate continuation bits (1's) from data bits with a 0. This gives identical encoding-length characteristics as what you are calling "vbytes" (1 byte can encode 0-127, 2 bytes can encode 128-16383, etc) while still front-loading the continuation bits.

Re: History of massive-scale sorting experiments at Google

#50

Post by cmrdporcupine »

late2part wrote: post #15
alexnewman wrote: post #11

Earlier quoted context omitted.

Lol normal Google arrogance. Yea they only seem to ask theoretical questions basically out of that famous book

Maybe, maybe not. Most people's surface area of problems don't even approach Google's problems. The kind of things most companies aspire to solve, Google automated a decade ago. So, this esoteric CS theory may be more practical inside Google than your external vantage point can consider.

The problems being automated years ago means the vast majority of Google engineers don't ever get close to having to work on those solutions. One of things that disappointed me after joining G was that many of the problems I found fun to solve at previous employers were a) solved already and b) solved by people much smarter and senior than me.

It's a great place to work for all sorts of reasons. But working on cutting edge stuff, well, that requires that you be good at fighting on both meritocratic and political fronts. The majority of the people that came in the same acquisition as me left before their golden handcuff payouts finished, because of this.

Post reply on HN