[mirajshah]

A difficult technical problem, for example, is Google search. It's not just managing the completely of PageRank, it involves creating fundamentally new algorithms to deliver better search results.

Another way to think about it is that Google wants SWEs who can also act like researchers (e.g. PhD students).

[freyir]

Yet it seems like a big complaint among (ex-)Googlers is that they were underutilized and spent their time working on trivial tasks.

[photoJ]

And yet, the bulk of phd students don't reverse binary trees.

[swerveonem]

The binary tree is one of the core data structures used in search. To apply at google and not be able to perform the basic search algorithms on that data structure is a huge red flag. Binary tree is to search what an array is to the programming language, would you hire a programmer that could not use array indexes?

[wruza]

As if everyone employed at google is a core search engineer. Moreover, if you take your average programmer and let him/her implement an array at a low level, you’ll get either a mess or nothing, since the complexity of using arrays and btrees has nothing to do with the complexity of implementing these. And the complexity not in theory knowledge, but in an implementation itself. One basically cannot write, test and prove it in short term (see e.g. “Implementation Issues” on wp).