Thread by @GergelyOrosz

“Why do companies ask data structure&algorithm questions? It’s not like you’d use this day to day...”

At my past 3 companies - Skype/Microsoft, Skyscanner, Uber - I needed to use them to write some code, and *especially* to understand things. Here’s some examples. A thread.

At Skype, building Skype for Xbox One, the platform was missing a bunch of basic libraries. We built a navigation framework on top of WinJS that needed to keep track, and in some cases, traverse the DOM tree. #Trees, #DFS, #BFS

Also at Skype, one of the devs was obsessed with performance. For the contact list sorting, he built his own algo. I used the O(n) approach to tell him why this was silly. Then built a faster version. Then we benchmarked the built-in sort which was faster #sorting #facepalm

At Skyscanner, getting the latest prices was a complex operation. A graph of possible ways to fly, and the cost of these each is a decent mapping of the problem. Weighed graph traversal, and coding it in practice is what the company runs on. With caching, of course. #graphs

At Uber, we needed to parallelise hundreds of builds/day that each took a long time. How do you do parallel builds when changes could conflict? You pull in some probabilistic modelling. The team sitting next to me worked on this state-of-the art approach: eng.uber.com/research/keepi…

At all three companies, the #1 data structure I’ve used (and seen used) beyond arrays is hashtables and the related hashing function. Use for local caching and for sharding. With sharding, re-hashing is an interesting problem. At Uber, it was a real issue on how to shard cities.

Also at Uber, for RIBs (github.com/uber/RIBs) we built a GUI to visualise the components (like the DOM) and update real-time, as things changed. Your usual trees here, with traversals & updating nodes. At Uber, there’s tons of tools like this built from the ground up. #graphs

Also at Uber, we built crypto libraries when they did not exist on the platform. This was the case on iOS and Android back in the day: we had to implement secure encryption on the client & decryption on the server side. Then formally validate and audit the implementation.

And there’s the storage / processing debate when deciding on approaches that is similar to the runtime / space O(N) complexity trade-offs. Should we generate N*100GB of data each month or run an additional N*100VMs to compute on the fly?

Takeaway: it’s not wasted time:effort to understand how basic data structures work (hashtables, heap, queue, stack, tree), graphs and YoY with some algorithm approaches.

They will let you peek under the hood better of frameworks/libraries you use, and you might also use them.