News for hackers. Stuff that matters.
Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @12:58AM (#18713418)
(Disclaimer: I work at Google). This is going to sound like a humble-brag, but it isn't, I'm trying to give some life advice based on my experience: I have used "CS" algorithmic thinking on multiple projects, I've even used facets of abstract algebra and number theory from my Math degree to further my career and it lifted me out of poverty.

Here's an example. A few years ago, I was researching ways to crunch down the size of GWT (Java-to-JS compiler) output more. Besides obvious compiler theory work on optimizations, I noticed that the code had a lot of common chunks that could possibly be gzipped better. Knowing how bzip2 worked with the BWT transform, I wondered if sorting JS code could improve gzip output, the result was this (http://timepedia.blogspot.com/2009/08/on-reducing-size-of-co...) and writeups like this were one of the ways I got noticed by Google to get an interview. In other words, solving "useless puzzles" landed me a dream job.

The gist of that article is by using edit-distance/levenstein distance to 'cluster' JS code fragments, you can improve the efficiency of GZIP by bringing more code into its 32K window OR optimize the huffman codes it uses. However, edit-distance doesn't know anything about the LZ algorithm's mechanism.

Later on, I ran into the "LZ Distance Metric" in some papers while researching about optimal clustering and wrote an updated post: http://timepedia.blogspot.com/2009/11/traveling-salesman-pro...

It turns out optimally computing the LZ Distance Metric requires efficiently solving the Longest Common Substring problem, which can be solved with a generalized suffix tree in O(N + M) time.

In other words, if my only experience was doing web programming or standard forms + database enterprise apps, I probably would have never been able to even imagine this, because I wouldn't know what I don't know, whereas spending time actually thinking about data structures and algorithms in my past, prepared me for that moment, exposing me to stuff I would recall later when I needed it. Moreover, trying to solve this problems exercises memories you learned in college CS, so you don't forget them, especially the ability to read papers and consume mathematical notation.

Another example: I have long had a love affair with number theory. It's why I love cryptography, error correcting codes, block designs (See one of my own puzzles to see if you can solve it: http://cromwellian.blogspot.com/2006/09/puzzles-you-cant-sol...)

This led me to get into crypto. Early work on crypto during the cypherpunks mailing list days in the 90s, designing anonymous remailers, anonymous internet proxies, and digital cash algorithms, got me noticed, and led to a job at IBM TJ Watson research, my first, real, non-consulting job (before that I mostly wrote 6502/68000 assembly for games, and FastCGI+Perl). From there, I applied HashCash proof-of-work in the mid-90s to anti-fraud in hacked clients in 2-tier systems, patented an early re-CAPTCHA-like algorithm, and ended up getting acqui-hired by a California company. Now, I was born and raised in Baltimore City, grew up pretty poor, and had to start my first 2 college years in a community college. This was a fantastic dream come true for me, and I mostly credit it to serendipity made possible by being exposed to a lot of stuff.

Later, internal to Google, I came up with the idea of applying Broadcast Encryption used in copyright-protection systems (e.g. Blu-Ray AACS) and turning them around for a good purpose: creating a serverless, peer-to-peer group messaging social-network. That design was heavily based off of number theoretical knowledge I had to dust off, and helped facilitate an internal transfer to the team I'm on today.

There's nothing wrong with straightforwardly engineered apps, screens, forms, databases. Most of the world subsists on this. But sometimes, in fields of graphics algorithms, AI, mapping, bioinformatics, AR, VR, you encounter situations that aren't straightforward, and then it becomes valuable to be able to be confronted with a super-frustrating, mind bending puzzle, and bring all the weapons to bear on it. Can't you just Google-search it? Sometimes. I'd argue more often than not, you'll "flesh-based search engine it", by tracking down your local Jeff Dean clone and asking them for hints.

But IMHO there's no harm in being challenged like this anymore than being asked to complete basic training to be in the military, even though you might just be a tech-support soldier. You never know when you'll need those brain muscles, and if you're lucky, like I was, it could be a life altering opportunity. I don't think Google interviewers are interested in you solving the problem and getting the correct answer, they are interested in seeing how you work: how you think, how you communicate and ask questions of the interviewer, in other words, how you'd work as a member of the team. There's no shame in asking the interviewer questions, it's what you'd ask a coworker if you're trying to solve the problem.

It's not the end result, but the process.

Re:Google Tech Dev Guide by pathseeker on Wednesday December 19, 2018 @06:14AM (#18714851)
>There's nothing wrong with straightforwardly engineered apps, screens, forms, databases. Most of the world subsists on this.

Most of Google subsists on this. Interviewing everyone for skills that only come up when you are pushing the boundaries of CS is pointless. 99% of engineers at Google fling protos and do menial translations on them.

Have a separate "CS" group if you want and apply the CS questions to them. For the rest, interview instead on their ability to write maintainable, testable, scalable software. Google would be worlds better off for it. It's shocking how incompetent the org is as a whole at delivering and maintaining quality software.

Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @06:59AM (#18715035)
I don’t think product excellence is a function of the interview process, it’s mainly a function of what you are promoted for, and rightly or wrongly, launching new things tends to give you a better career trajectory than fixing or maintaining old stuff.
Re:Google Tech Dev Guide by kamaal on Wednesday December 19, 2018 @07:47AM (#18715219)
That's an unfortunate consequence of the OKR process. If the company has to be chasing near moonshot projects all the time. Then they also align resources towards it. That means money is chasing those projects.

There is a huge incentive to keep launching new things. To keep doing something big. Its the classic throw-pizza-at-wall-see-what-sticks approach except the experiment is run among a huge group of people. So eventually some Pizza sticks.

But even in that case. I hear '20% time projects' culture have long been dead for now. So that means the projects have to come some one from the top to get some resources.

Re:Google Tech Dev Guide by jrochkind1 on Thursday December 20, 2018 @06:24PM (#18730175)
This is a "Google Tech Dev Guide: Grow Your Technical Skills…", not a "how to interview" guide. Particularly a "foundations of programming" section, in this case.

I don't know if it's a good interview question or not, but that doesn't mean it's not part of learning programming.

There's more to learning to program than learning to do well in interviews, just like there's more to learning in general than doing well on standardized tests.

I think it's odd that so many immediately jumped to discussing the _interview process_. Google's, or anyone's, interview process may or may not be effective at finding talent or being fair. (I have no particular opinion on Google's, but there's LOTS written on the difficulty of creating a successful interview process for programmers, and various different opinions and approaches).

But why do we in this discussion seem to assume the only point of this Google site is helping people _pass interviews_? It doesn't say that's what it's for at all.

I think it's actually a pretty marvelous free site for learning CS and programming of various sorts, for people of various levels and domains.

Re:Google Tech Dev Guide by greenleafjacob on Wednesday December 19, 2018 @02:40AM (#18713905)
> That design was heavily based off of number theoretical knowledge I had to dust off

The fact you had to "dust it off" implies that it was not top of mind, which is precisely the argument people have been making; that it's not top of mind, and need not be because it can be "dust[ed] off", and that investing months in prep just to pass an arbitrary hoop is a waste of time.

Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @02:54AM (#18713974)
I'd argue that if you don't regularly dust it off, you'll forget it. The only reason I remember most of that stuff is because from time to time, I go back and read crypto papers, and then need to refresh my memory.

Think about any foreign languages you learned in high school. If you have never used them in 10+ years, it is very unlikely you'll be able to 'dust off' your second language as languages acquired late tend to require regular use before amnesia sets in.

Re:Google Tech Dev Guide by lwansbrough on Wednesday December 19, 2018 @04:09AM (#18714303)
You’re the guy writing compilers at Google, so ya you’re the exception my friend.
Re:Google Tech Dev Guide by joshuamorton on Wednesday December 19, 2018 @11:26AM (#18716746)
But he's not that unique. One of my 20% projects recently required reading up on specialized parallel parsing trees/regular expression generalizations. I was able to sketch an algorithm structure that I thought should work, and some quick searching brought me a to a paper that formalized it (I wanted a 1-pass way to match a set of subtrees on a large tree, where each subtree could be vaguely regular-expression-y, such that I could apply the `*` or `?` operators to a node in the needle-tree instead of a to a substring of the needle-string). A generalization of aho-corasick seems to work here, though I haven't had time to implement it yet.

My day to day work involves lots of statistics[1], despite being an unsexy role (SETI), and I'm of the opinion that most people at Google should have a better understanding of statistics, despite by all accounts, the average statistical knowhow of my coworkers being well above average.

A coworker is working on code generation and parsing, so his automata know-how is coming in handy too.

And that doesn't even touch on the need to have some of this foundational knowledge when dealing with tooling like spanner or many of our other tools for dealing with data at scale.

I'd generally agree that one person need not know all of it, but a familiarity with the basics in all of these areas is necessary, especially if, as another user mentioned, you want any level of internal mobility.

[1]: https://queue.acm.org/detail.cfm?id=3194655

Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @11:41AM (#18716897)
Right, I’m pretty mundane actually, I don’t think I’m all that special and there’s lots of people at Google I’m envious of able to solve problems I can’t begin to crack. Some of the people working on build systems at google are using some dizzying graph algorithms for example.

Consider how Bazel must build and test the world’s largest(?) monorepo at scale incrementally on every commit.

Perhaps this is an artifact of Google’s size, but a lot problems turn out to be “well, this would be simple if our input was a million items, Unfortunately it’s a trillion items” and now all of a sudden asymptotic complexity matters.

Re:Google Tech Dev Guide by yanslookup on Wednesday December 19, 2018 @09:13AM (#18715695)
> It turns out optimally computing the LZ Distance Metric requires efficiently solving the Longest Common Substring problem, which can be solved with a generalized suffix tree in O(N + M) time.

Imagine you walked in to your Google interview, with all of the experience from improving the size of GWT output fresh in your mind, but before you "ran into the 'LZ Distance Metric'". They sit you down and say "LZ Distance Metric is related to your past projects, we want you to solve the LCS problem. Use this whiteboard, markers are to your left, you have 45 minutes."

You don't have time to read some papers, research, prototype things or sleep on it.

No doubt it takes experience, curiousity and exposure to algorithms to solve but in order to solve it under Google interview like conditions it mostly requires that you've done it before and memorized it.

Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @11:44AM (#18716921)
Im totally sympathetic to the time pressure thing. I myself don’t do well under a clock with someone standing over my shoulder.

I know a lot of people like this, which is why I don’t like whiteboard interviews.

Re:Google Tech Dev Guide by protonimitate on Wednesday December 19, 2018 @08:55AM (#18715580)
I agree with most of your post, except for: >But IMHO there's no harm in being challenged like this anymore than being asked to complete basic training to be in the military, even though you might just be a tech-support soldier.

I would agree if the big companies making the demands on these candidates assumed the burden of training. You don't have to spend $60k for a degree, spend hundreds of hours grinding leetcode, and have a portfolio of side projects to join the military.

> don't think Google interviewers are interested in you solving the problem and getting the correct answer, they are interested in seeing how you work

I think Google (and other companies) think this is what they are doing, but unfortunately there's no way to ensure that this is actually what HMs/interviewers are screening for. For every one good interviewer that cares about thought process, etc. there are three interviewers that want to see the candidate fail to prove they are superior and justified in having the job they do.

I enjoyed your story, and am glad things worked out for you - but as others have pointed out, you are most certainly the exception to the rule. Why are we using exceptions as the baseline for 'standard'?

Re:Google Tech Dev Guide by around_here on Thursday December 20, 2018 @07:55PM (#18730642)
It's just another example of how CS (Read: Silicon Valley) culture is geared entirely towards the 20 - 30 year old male with no family or time commitments. Willing and able to spend hundreds of hours grinding leetcode and a portfolio of side projects.

Their culture problems that have become publicized of late are a knock on effect of this. It definitely establishes the fundamentals and makes you "better" than the rest (to a point), but at a terrible cost.

Re:Google Tech Dev Guide by mlthoughts2018 on Wednesday December 19, 2018 @07:07AM (#18715071)
I have worked on similar kinds of problems where obscure details about sparse matrix algorithms were required. My team ended up writing a large in-house search engine and ranking framework that combined image and text search, all in Cython, using various types of bit packed indices for fast filtering and our own implementation of a series of sparse matrix algorithms sort of ripping out CSC and CSR internals for a handful of operations related to applying latent semantic indexing and some in house vision model neural networks to the sparse data in a way that was both fast and let us store hundreds of millions of documents in memory on fairly normal hardware.

I would say that tech interviews which assess this type of skill are deeply irrelevant and fail even at the very task they attempt to solve. Not to mention how arrogant it is to reduce emphasis that should be placed on straightforward communication about real work experiences as a more important measure than performance on any type of interview coding tasks.

What you say just falls flat. You don’t give any reason to think that this stuff needs to be an interview-ready skill to be tested in a time-sensitive way. It could just be picked up later when you have a project where you need it. Most engineers can quickly grok this stuff from a book or online tutorials or talking to someone else or even just writing the problem down and locking themselves in a room for a few hours to think.

Any assumption that it needs to be already in your brain cache all the time prior to an interview or every day at a job is just harmful.

At worst it’s a thin excuse for promoting a hazing style of oneupmanship as a barrier to jobs, killing diversity of thought and at best it’s misguided reward for a certain type of extreme premature optimization thinking (that carries a lot of antagonistic culture with it too).

Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @07:39AM (#18715184)
I don’t think it’s hazing, Google internal culture frowns on that kind of alpha male coder oneupsmanship.

its mostly likely a residual of the fact that people fresh out of school actually don’t have a lot of projects or experience to talk about.

If you ask me what the perfect interview is? I’d say, send me a bunch of github repos you participate in and let me review your code, bugs, and discussions with collaborators.

I’ll learn a lot more than any 1 hr FtF interview.

My overall point is there’s this kind of attitude “calculus? I never need it.” Prevalent in society where people rail against subjects they were forced to learn and then claim their day job never needs them.

I think whether or not you actually use anything you learned in CS courses highly depends on what you want to work on. My interests happen to be in compilers, computer graphics, and cryptography and I find I need to quite often revisit stuff I learned in college.

Even when I was writing 8-bit games and demos on the Commodore 64 I found some need sometimes for these skills like replacing expensive functions with approximations.

I’m not saying interviews need to question you on these things, I’m saying these things are useful to study and learn and stay abreast of. Perhaps I’m biased because I kind of love math and find an inherent beauty in these things and so I find these kinds of puzzles fascinating. (The Shannon Fano plane is a particular example of a beautiful construct that I just adore for reasons I can’t explain)

Re:Google Tech Dev Guide by mlthoughts2018 on Wednesday December 19, 2018 @08:14AM (#18715337)
I can’t speak to Google in terms of the alpha mentality, but it’s still irresponsible of the world’s most effective computer science company to support it, advertise it with study guides, etc. I expect more self-awareness than that, and less lazy thinking that you need such time constrained trivia to keep an artificial prestige barrier (because it very sincerely is not about detecting engineer effectiveness). Take some responsibility for the cargo cult copycats you are fueling. The same could be said about stack ranking and various other policies as well.

Regarding interviews, everybody’s a comedian. You say GitHub but some of the best engineers I know do not participate in open source projects or are prevented from doing so by their employers. I say just treat software engineering like every other professional field on the planet and just conversationally interview people in a technically detailed way, focus on their past projects, work history, ability to get specific about their work. And of course that would not be as good for people just out of school or who forgot ancient work project details.

I would be fine with a holistic average approach, where each of these different ways is applied, but each counts for little weight individually. So you can be forgiven for a code test flub if you’re sharp on your work experience technical details.

But we exist in a state far away from that... where things are overwhelmingly based on isolated, time-sensitive trivia given 100% of the decision weight.

Re:Google Tech Dev Guide by brianpgordon on Thursday December 20, 2018 @01:07AM (#18722828)
Calculus probably isn't the best example, because you really don't need it. Real engineers need it, but if software engineers got a different sequence in discrete math I think they'd be better prepared for the job market. I ended up doing a math concentration so I got both Calc 1-3 and some nice discrete courses like number theory, combinatorics, and abstract algebra that were super useful, and in my opinion we could definitely stand to replace memorizing integration techniques with studying some of those topics.
Re:Google Tech Dev Guide by mlthoughts2018 on Thursday December 20, 2018 @07:23AM (#18724291)
This really is not true. Using a little calculus to derive a closed form solution to a problem can reduce computational burden. A team where I work just had to do exactly this for a geographic distance optimization problem. At first glance it seemed like you needed dynamic programming and it was expensive, but drawing it out and modeking it with equations, we actually set up a Lagrange multiplier formula for the problem and found it had an exact solution. This was not a team of mathematicians or anything, just database engineers working on a specialized in-house search optimization problem.

If you do work in statistics, then calculus matters quite a bit, especially for transformations of variables and deriving the formulas for the probability distributions you’re working with. In Bayesian methods, even if you use autodifferentiation tools to automatically sample from your model, you still often need to do a bit of calculus here or there.

Likewise, if you ever find that you need to implement your own model training algorithms, you’ll probably need to calculate gradients (for example, the gradient of custom log-likelihood functions) analytically before writing them as software functions.

Calculus is pretty pervasive in professional software engineering. You don’t need to be an expert, but should have working knowledge and ability to dig into references and work through it.

Re:Google Tech Dev Guide by brianpgordon on Thursday December 20, 2018 @03:00PM (#18728564)
Yeah the statistics and machine learning applications are a bit hard to get away from. But I would still replace the calculus sequence with discrete math, assuming the number of math credits had to stay the same. At my school (University of Maryland, College Park) most CS majors just took calculus 1-3, statistics, and one basic discrete math course from the computer science department. The size of calculus seems massive (3/5 of the total math load) compared to the benefit. That precious time could be spent digging deep into linear algebra or combinatorics or graph theory etc, and that's useful for all developers who write algorithms, not just in specific applications' niches.
Re:Google Tech Dev Guide by mlthoughts2018 on Thursday December 20, 2018 @04:58PM (#18729533)
Why do you think they are mutually exclusive? Generating functions, geometric series, difference equations, integrals over discrete probability distributions, elliptic curve cryptography, general linear programming and optimization, eigenvalue analysis in graph theory, stochastic optimization, all these things involve calculus to solve discrete algorithmic questions.

In fact I’d argue it makes calculus more important than what is typically understood as “discrete math” because in order to have the mathematical maturity to really understand the meaning of major discrete math results and theorems, it requires understanding calculus first.

If you “just” study discrete math mistakenly believing “that’s where the value is” then you’d end up with a shallow understanding of discrete math, lacking ability to extract value from it except in some narrow sense from rote discrete math application-specific coursework.

Re:Google Tech Dev Guide by Radim on Wednesday December 19, 2018 @08:29AM (#18715423)
> … applying semantic indexing … to the sparse data in a way that was both fast and let us store hundreds of millions of documents in memory on fairly normal hardware.

Fascinating. Would you mind sharing more, some links / white papers?

We did something similar with ScaleText.ai (as a step-up from Gensim), I'd be curious to compare notes and perf numbers. Drop me an email at [email protected] if interested. Thanks!

Re:Google Tech Dev Guide by Novashi on Wednesday December 19, 2018 @09:02AM (#18715637)
The underlying issue is that programmers/developers/engineers need to be split up in terms of technical difficulty.

By not doing this, companies don't clearly know how to assess your skills because as we've found, there's not an accurate and fair test that tests from the lowest level of putting HTML on a web page to cutting-edge AI and distributed systems that fits in an interview format.

There is ample, ample work to be done that doesn't concern much of CS at all.

This is the same for a lot of other more mature industries that have been around for decades or centuries -- people pushing the limits of agriculture science are different from people who run farms are different from people who work the fields. They shouldn't get the same interview, but here we are trying to test everyone as a CS graduate.

This split would be separate from salary. You can deliver $millions in value by never touching anything beyond CS-year-one and you can subsequently charge clients for that as long as you can demonstrate it.

Re:Google Tech Dev Guide by sidlls on Wednesday December 19, 2018 @10:42AM (#18716350)
Did your work on that project occur under a 45 minutes deadline on a whiteboard with someone watching you?

I see "It's the process not the result" all the time, but almost always from people who already work at Google and have for some time. From candidates and fresh hires I usually see the opposite.

Re:Google Tech Dev Guide by bicubic on Wednesday December 19, 2018 @06:01AM (#18714800)
tl;dr: sometimes algorithmic puzzle thinking comes in useful.

I don't think anyone is debating that. You don't need to write an essay worth of anecdotes. And your anecdotes don't really address the complaint: these algorithmic puzzles just don't present themselves at the majority of everyday work for the majority of everyday people. Not even at Google.

Preparing for a Google interview is like preparing for an exam on an arbitrary subject that's only loosely related to your field of work.

What this kind of interview actually tests for, is whether the candidate has the time and desire to do all the prep in the first place. It's heavily skewed towards younger individuals, especially recent graduates.

Re:Google Tech Dev Guide by paganel on Wednesday December 19, 2018 @03:35AM (#18714155)
> The gist of that article is by using edit-distance/levenstein distance to 'cluster' JS code fragments, you can improve the efficiency of GZIP by bringing more code into its 32K window OR optimize the huffman codes it uses. However, edit-distance doesn't know anything about the LZ algorithm's mechanism.

That sounds really cool, and even though I couldn't understand the technical details I understood the gist of it. But, because there is a "but", the issue with tech- and algorithm-focused companies like Google is that they don't look at the grander scheme of things, the same way as some other less tech-focused companies/people would have.

To go back to your example, that solution meant that Google could "serve" even more JS code to clients' browsers, and as I assume other googlers came out with different but related solutions that meant that even more and more JS code would "make it" to Google's web products. That's how we got to things like the latest GMail interface, which is a mess in terms of JavaScript, because Google just couldn't say at any one point: "No more JS!" presumably because it was getting easier and easier to "input" JS into that thing. All of this could have been prevented if at any one point a Google higher-up would have said "YAGNI!" or "KISS!", which are also very valid programming principles but which I didn't notice as being emphasized on this Google Tech Dev Guide page.

Re:Google Tech Dev Guide by cromwellian on Wednesday December 19, 2018 @03:54AM (#18714222)
Everything has gotten bulkier in Gmail, not just the JS, but th CSS, the DOM, the fonts, assets overall because Gmail is an app that’s over a decade old and features have mostly been added, not removed.

This is the fate of all legacy software, OSes, native apps, they all eventually burst under their own weight, and are rewritten clean. Inbox was that dream :)

In particular, Gmail has been engineered to mostly be served as a single page app that functions offline as well. SPAs were a bad architectural trend now being somewhat reversed by code-split PWAs.

The same JS tools like Closure Compiler that enable large SPAs also enable efficient code splitting into tiny pieces (look at photos.google.com as an example)

A hammer is only as good as what you use to build. Web apps got native app envy after installables and app stores took off. I think we’ve woke up from that now and you’ll gradually see it improve.

Re:Google Tech Dev Guide by paganel on Wednesday December 19, 2018 @04:47AM (#18714482)
Happy to hear that and happy to hear that in the end there were people at Google that managed to impose a KISS-like view on one of their most used products.

> Web apps got native app envy after installables and app stores took off. I think we’ve woke up from that now and you’ll gradually see it improve.

Yeah, the hype was big with SPAs, I also hope that Google diverging from that path will set an example for the rest of the industry and things will become more "normal" again.