I think the alphago program is getting similar crazy scale burn-in access to the gpu computing that google will soon offer in its cloud. Recall alphago was the first program to beat a professional in a tournament setting. They published in nature. The emphasis was on their deep learning approach, but the technical details were pretty impressive. Alphago beat Fan Hui, a 2 dan professional, using a 1202 cpu/776 gpu diatributed system. They don't give hardware details, but my back-of-the-envelope estimate based on recent hardware is they were at around the petaflop calculation rate. In the nature paper they examine how the program's ELO rating varies with computation power; it looks like to reach world champion level they need at least an order of magnitude more computation. They challenged a player at that level (Lee Sedol) for a series in March and express a quiet confidence in winning. On their blog they give google cloud credit for supplying the compute power, but google cloud doesn't yet have gpu units available publicly. I am thinking alphago is getting to do burn-in on a massive gpu cloud computing center. Look for public availability shortly after the Sedol match!
Note that this sort [in 2012] was 500 times larger than the
GraySort large-scale requirement and twice as fast in
throughput as the **current 2015** official GraySort winner.
It had to feel fucking amazing to be an engineer that was part of that at the time. To know (even if it was publicly unknown) that you were able to so massively destroy a record which still stands 4 years later.
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.
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.
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?
I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.
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 they accidentally did something in O(N^2), their half-day compute job would suddenly literally take centuries to complete.
Also, part of the point of a Google style interview is to keep pushing you to the point where your ability fails, then push in another direction to the point your ability fails. That way, they get an idea of the dimensions of your skillset. The vast majority of the people I recommended hiring didn't answer the questions perfectly.
Or, someone could not quite put enough thought into the integer encoding for Protocol Buffers. 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. The only advantage to this over encoding the length of the integer as the number of leading ones in the first byte (like UTF-8) is if they want the option to have the option later of a forward-compatible encoding for longer integer types, without just supporting multi-precision integers as byte arrays. If you slide all of those flag bits to the first byte, you don't have any more or any fewer flag bits, so it takes as much space, but you can use a jump table and the ability to use native 8-byte and 4-byte simple loads instead of many more masking operations and conditional branches. Giving up on anything longer than int64_t means that the maximum encoding length becomes 9 bytes instead of 10.
One day, the speed of the indexing system just dropped in half. It turns out that someone wrote a job that used machine learning to generate a bunch of regexes for some signal. They were recompiling the regexes for every page in the index. Google really needs most of their engineers that will naturally spot this kind of thing in code reviews, because if every engineer on the indexing team made a mistake like that once a year, the indexing system would always run at half speed, sometimes even 1/3 or 1/4 speed.
The indexing system uses as much electricity as a small town. The tiniest of improvements can mean thousands of dollars per year in savings.
> 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 or tree riddles in an interview has absolutely nothing to do with those longer-view skills.
> Google really needs most of their engineers that will naturally spot this kind of thing in code reviews, because if every engineer on the indexing team made a mistake like that once a year, the indexing system would always run at half speed, sometimes even 1/3 or 1/4 speed.
Again, this has nothing to do with puzzle interviews. In this case, you could hire smart people almost independently of whether they had encountered certain data structures before, and certainly without much concern about how fast they could spot things like this in an interview setting. And instead, hire for general aptitude, and then invest in training someone to be able to spot these things to the necessary degree.
Even though you can provide impressive-seeming examples of problems where minor tweaks in complexity or subtle implementation-specific points about data structures can result in huge problems, it's still not supportive of whiteboard-hazing style interviews that test more for interview aptitude than anything else.
After all, whoever it was that wrote the ML regex job, that person passed the interviews (and that person may have rightfully passed the interviews and deserved to work for Google, even after this later evidence that they weren't careful enough in one case).
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 probably also takes people out of the industry who could do more vital work someplace else.
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.
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.
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.
If they are testing for quality X and the test says "yes" even though the person doesn't have quality X, then it's a false positive.
I'm saying that they view the riddles, data structure hazing, etc., as tests for quality X (where X == careful engineer who won't inject N^2 complexity into something and make it take centuries).
But really, the puzzles and so forth do not select for that X. You get people who are good at the trivia, but who still otherwise would inject poor complexity. Meanwhile, you reject people who might be careful and pragmatic, but are not talented at the trivia.
From their perspective (since they believe it does test for X) it produces false positives.
>>Also, part of the point of a Google style interview is to keep pushing you to the point where your ability fails, then push in another direction to the point your ability fails. That way, they get an idea of the dimensions of your skill-set. The vast majority of the people I recommended hiring didn't answer the questions perfectly.<<
I can't even begin to tell you how valuable I consider this approach to be...pushing (or leading) a candidate in every conceivable direction until failure is reached or limits are exposed...
HR professionals in almost any profession would benefit from implementing this technique to the extent that their resources allow...most don't have the luxury of time...
Example: As a member of a non-profit board I was once tasked with performing screening interviews for 5 candidates who were applying for a Camp Ranger position at one of the organization's youth camps...
I was not an HR expert then (or now), so I jotted down a few interview questions and scheduled interviews with the candidates...each one to begin at 8:00am at the site, and to last as long as it took...one per day...
I simply walked around the site, visited with the candidates, asked about their experience, and did everything I could to encourage them to "reveal" themselves...
I eliminated 2 candidates by around 10:00am, 2 more around 11:00am, and ended up driving to town for a burger lunch with the 5th...I later recommended the fifth...
He was hired, and ended up doing an incredible job...
I ended up giving other board members the impression that I knew what I was doing...at the time I most certainly did not...but I filed that lesson away...
I am convinced that a commitment to open-ended interview time, combined with "soft" skills probing, are critical if you want to properly evaluate candidates...
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.
There's actually no reason to ever use 10 bytes in this encoding. If you use 10 bytes, that means your last byte only holds one bit of actual user data. That's not very cool. But, your next-to-last byte holds seven bits of user data and one bit of metadata. We can easily say "if we're at the next to last byte, don't use metadata, just use all the bits we need." All you have to do is say "if we are currently at 9 bytes, don't use a 10th byte, just use this 9th byte directly." bam. Your 9th byte now has 8 bits of user data and you don't roll over a useless 10th byte with one bit of data.
The "slide all continuation bits into the first byte" sounds like a trick, but it's really using a TLV encoding where the first byte just holds a number between 1 and 8, so the entire integer+metadata is now [1 type byte][1 to 8 user data] = 2 to 9 bytes total. 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).
No, it's not a type-length-value encoding, just a length-value encoding. I should have been more explicit in my UTF-8 reference. I'm really talking about a UTF-8 like encoding, except that it doesn't specially mark any of the continuation bytes and generalizes to lengths of 9 bytes, so the encoding (plus using zigzag encoding to put the sign bit in the least significant bit) is:
0xxxxxxS : 1 byte, 7 bits of data, -64 to 63
10xxxxxx xxxxxxxS : 2 bytes, 14 bits of data, -8192 to 8191
110xxxxx xxxxxxxx xxxxxxxS : 3 bytes, 21 bits of data, -(2^20) to 2^20 -1
1110xxxx xxxxxxxx xxxxxxxx xxxxxxxS : 4 bytes, 28 bits of data, -2^27 to 2^27-1
... and so on.
int64_t zigzag_decode(uint64_t in) {
/* Signed right-shift is implementation-defined behavior in C */
COMPILE_TIME_ASSERT( (1LL << 63) >> 63 == -1, compiler_uses_signed_arith_shift );
return (int64_t) ((((int64_t) in << 63 ) >> 63 ) ^ (in >> 1));
}
You can actually get slightly more dense packing using an encoding that doesn't have any non-canonical encodings by adding a length-dependent constant before the zigzag decoding step, but that's a bit more complicated to explain, and allows some 9 byte encoding values that won't fit in an int64_t.
well, the "type" is presumed by a schema or somewhere by the time you hit your decoder, so it's technically there even if physically absent (and "LV encoding" doesn't seem to be a thing with any meaningful search results).
Or we can just store everything as int64_t natively anyway. It's only 8 bytes after all (and storage is big these days).
The FAST (FIX Adapted for STreaming) protocol also uses a stop bit encoding. My guess was the data dependencies added to the pipeline would wash out the message size saved on average.
> 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.
That's clever too, but it seems we're back to masking/shifting things all over the place too (which seemed to be an anti-design goal listed above.
These can also have the "avoid 10 bytes" optimization by just reading the next 8 bytes exactly if the first byte is just all ones (no need for a zero separator; it would be in the way and push out the final bit to its own isolated byte again).
"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.
I made no mention of low dimensionality. It's clearly a very high dimensional estimation problem with time constraints on measurement. There are some correlations, so you can pick the principal components that you think are most important, and measure some dimensions that are (you cross your fingers and hope) correlated with those principal components.
But, it's largely guestimates anyway. It's hard to come up with good metrics of employee performance that correlate well to company performance and even harder to come up with interview questions that have good predictive power for those metrics.
Ideally, they'd relax the hiring criteria and all employees would start as 1-year or 2-year contractors. On-job performance is the best indicator of on-job performance.
You may well be asked how a distributed sort would work in principle, and be asked to code a small part of it. Any reasonable answer that shows you can think on your feet would be evidence in favor of hiring.
It sounds like you didn't get hired, and I'm sorry about that. Interviewers' preferences are of course diverse, but for at least the last 5 years, probably 10, Google interviews favor practical solutions to problems we face every day. Some of those are theoretical CS, many are not.
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 record, I have both been hired and not hired by G and not necessarily paired with the above interviews as you'd expect.
I mention this instance largely because my friends at the big G tell me such a question is generally frowned upon, and not part of standard practice, (So I don't feel bad speaking openly about it) but more importantly it gives me a way to see how people can get a skewed perspective on a company given a... unique interview question when the overall guidance within the corp wouldn't align to asking that.
(Tedious disclaimer: not speaking for anybody else, my opinion only, etc. I'm an SRE at Google.)
"Within the last 10 years" covers several generations of refinement to the interview process. I'd suggest forgetting about anything more than a couple of years old.
The major thing to keep in mind is that these days, your recruiter will ask you up front what subject areas you are strongest in, and you should expect to get interviews about those things.
Thanks for the datapoint. I concur with your friends, I wouldn't ask that question. IMHO even if you get a perfect answer, all you can be sure of is that the candidate has a good memory and happened to read the right books last night. I'd be more interested in a much simpler problem but with some modifications that prove there's original thought going on.
There is a (surprising?) latitude given to interviewers to ask their own questions however, and the best advice I could give to interviewers and interviewees is that the question should really just be a seed to a good technical discussion.
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.
> 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.
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.
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.
"with more rules we have solved most of the problems in the world. That just leaves the weird events" -Steve Coast
The remaining problems are indeed weird, and succumb only after application of every available tool: "asking around", CS theory, low-level debugging, visualization, heavy logs analysis, pouring over source code, strolling aimlessly, mining commit history, politicking, brainstorming...
The type of CS interview questions they ask aren't any different from what to expect at Facebook, Twitter, or any other tech firm in the valley. Many of my friends who are nowhere near the best CS students at my school passed their interviews without any problems. Is it perhaps remotely conceivable that you simply weren't well-prepared?
It is interesting to compare this with Apache Spark, which won the open source Graysort competition of 2014 [1].
Apache Spark completed a 1PB sort on 190 EC2 (i2.8xlarge) instances in 234 mins. Google did their 2011 1PB sort on 8000 computers in 33 minutes.
Moore's law is at work here and the results aren't very comparable but it would be interesting to see a head-to-head test on similarly speced clusters.
"To reduce the impact of stragglers, we used a dynamic sharding technique called reduce subsharding. This is the precursor to fully dynamic sharding used in Dataflow."
Fun ways in which internal Google tech makes its way to Google Cloud services.
This is my favorite part! There's so much and learning to be had in engineering solving problems with no real practical use. I don't consider it a waste of time at all and I'm glad they went ahead with their experiment.
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).
If the key is a sizable part of the data, then sorting could allow you to shave a few bytes from the key and reduce the overall storage needed. (Going from 50,000 drives to 40,000 drives is pretty significant even for someone who can afford 50,000 drives.) But I have no idea if there are real world cases where that is the right way to compress the data.
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.
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).
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."
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.
"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 or service that doesn't freak people out too much or do something stupid like place untrustworthy systems in charge of live nuclear missiles.
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...
