Thread by @iximiuz

Algorithms and Data Structures at work

Long story short: I solved hundreds of LeetCode and HackerRank problems, and I do find this experience useful for my day job.

Here is why (thread)

Sometimes, a developer may stumble upon a purely algorithmic task.

In my very first company, I wrote a GUI framework for SmartTV devices. These sets were quite slow back in 2011, so I needed to make the framework really lightweight and fast because even jQuery would be too heavy

The framework had a virtual DOM tree (react wasn't a thing yet). And the element rendering and navigation were all about tree traversals.

This framework essentially saved the project from failure.

In another company, we worked on a vehicle fleet management software dealing with lots of geospatial data.

I had a task to detect if some areas intersect. DFS or BFS was a natural choice for it, and no library implementation existed. So, I came up with my own.

Same company, sibling project. Discrete simulation of the vehicle fleet. Different events are scheduled at arbitrary timestamps but it needs to run much faster than a real-time. Thus, no sleeps in between two events. Priority query was a natural choice.

A quite common task in my practice - process a huge log file and keep top K entries by some attribute. Again, a priority queue to the rescue - close to constant memory and linear time complexities.

Not a typical example, but I'll mention `pq` here:

- tree traversals (PromQL parsing into AST, AST evaluation)
- shunting-yard algorithm (AST evaluation, LR grammar with different operator precedences)
- trie (vector matching)

github.com/iximiuz/pq

I always had a passion for implementing something like my own TSDB or SQL engine. Without algorithm and data structure skills, I wouldn't be able to even approach such a project.

But back to regular stuff...

Algorithms and Data Structure courses taught me to exercise formal code complexity analysis.

When I see (or about to write) a bunch of nested loops, I intuitively estimate the number of iterations per loop deriving the total snippet complexity as N * M * K * ....

It's useful to understand the complexity and memory layout of the most common data structures. It helps to reason about the potential side effects, caused, for instance, by a vector reallocation, or performance impact.

Insertion/removal of an element from the middle of an array (aka vector) may be quite costly because of the reallocation. The same operation is cheap in a list, but only if you have a pointer to the node beforehand. Such things in a loop make cost you an outage.

If I need to add elements on one side and pop them from another, the deque data structure is my first guess.

Need an ordered map iteration - use a BTreeMap instead of HashMap and sorting.

Need to maintain a sorted list with insertions/removals - use a balanced search tree.

Binary search is one love. Understanding how it turns O(n) into O(log n) utilizing the orderliness of data allowed me to grasp database indexes and log-structured merge-trees. The latter one is the basis of LevelDB, Cassandra, DynamoDB, and almost any modern TSDB.

This knowledge helps me understanding database query performance and allows me to design more optimal schemas and indexes.

Last but not least, hashing. Just imagine a programmer's life without hash tables. But actually, hashing is applied on higher levels too. For instance, to distribute records per database or cache servers. Consistent hashing is another concept I admire.

All this knowledge finds application in my code and designs on the daily basis. Most of it I got through taking algorithms and data structure courses and practicing problem-solving on LeetCode, HackerRank, and GeeksForGeeks.

Here is my favorite course:

coursera.org/specialization…

Bonus content: good read by @GergelyOrosz on the same topic

blog.pragmaticengineer.com/data-structure…