5 ms·

Now there's a good tech interview wheat chaff test! Pass on applicants that don't shout out "hash table" perhaps?

• onion2k 12y ago
  If you used a hash table you'd be doing a lookup for every single search in addition to the search itself. It'd be better to have nodes in the index include an 'extra stuff' pointer that linked to an object containing whatever else is displayed in addition to the results - the sidebar, alternative search suggestions, etc. Any easter egg info would go in there. (That said, I don't write software to anywhere near Google scale, so there's probably a much better way.)
  • keehun 12y ago
    That's what I was thinking, but imagining maintaining an index of Google's scale just boggles my mind.
  • willvarfar 12y ago
    The cost of a lookup on the term is O(1) with one perhaps two main memory accesses and measured in nanoseconds. The search index is likely a tree, and will be taking a main memory stall every node traversal. There are hundreds of easter eggs. There a trillions of search entries. The cost of even a byte per entry would be massive.