When was the last time you used this? – Part 2: Algorithms

In the previous post, I reviewed the most common data structures and reflected on how often I have used them as a software engineer over the past twenty or so years. In this post, I will do the same for the best-known algorithms.

Searching

Searching for an item in a collection is one of the most common operations every developer faces daily. It can be done by writing a basic loop or using a built-in function like indexOf in Java or First in C#

If elements in the collections are sorted, it is possible to use Binary Search to find an item much faster. Binary search is a conceptually simple algorithm that is notoriously tricky to implement. As noted by Jon Bentley in the Programming Pearls book: “While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962.” Ironically, the Binary Search implementation Bentley included in his book also had a bug – an overflow error. The same error was present in the Java library implementation for nine years before it was corrected in 2006. I mention this to warn you: please refrain from implementing binary search. All mainstream languages have binary search either as a method of array type or as part of the library, and it is easier and faster to use these implementations.

Fun fact: even though I know I should never try implementing binary search on the job, I had to code it in a few of my coding interviews. In one of them, the interviewer was intrigued by my midpoint computation. I got “additional points” for explaining the overflow error and telling them how long it took to spot and fix it in the Java library.

Sorting

Sorting is another extremely common operation. While it is interesting to implement different sorting algorithms as an exercise, almost no developer should be expected or tempted to implement sorting as part of their job. There is no need to reinvent the wheel when language libraries already contain excellent implementations.

Sometimes, it is better to use a data structure that stores items in sorted order instead of sorting them after the fact.

Bitwise operations

Even though the level of abstraction software developers work at has increased and bitwise operations have become rarer, I still deal with them frequently. What I do, however, is no longer the Hacker’s Delight level of hackery. Rather, it is as simple as setting a bit or checking if a given bit (a flag) is set. Software developers working closer to the metal or on networking protocols use bitwise operations all the time.

Recursion

Mandatory joke about recursion: To understand recursion, you must first understand recursion

I used recursive algorithms multiple times on every job I’ve had. Recursion allows solving certain classes of problems elegantly and concisely. It is also a common topic asked in coding interviews.

Backtracking

The backtracking algorithm recursively searches the solution space by incrementally building a candidate solution. A classic example could be a Sudoku solver, which tries to populate an empty cell with a valid digit and then fills other cells in the same manner. If the chosen digit didn’t lead to a solution, the solver would try the next valid digit and continue until a solution is found or all possibilities are exhausted.

So far, I haven’t used backtracking at my job but I used it to solve some programming puzzles. I found that backtracking can become impractical quickly due to a combinatorial explosion.

Depth-First Search

Depth-First Search (DFS) is an algorithm for traversing trees and graphs. Because I frequently work with trees, I have used DFS (the recursive version) often, and I have never had to implement the non-recursive version.

DFS is a good bet for interview questions that involve trees.

Breadth-First Search

Breadth-First Search (BFS) is another very popular algorithm for traversing graphs. It has many applications but is probably best known for finding the shortest path between two nodes in a graph.

I have used BFS only sporadically to solve problems at work. DFS was usually a simpler or better choice. BFS is, however, an essential tool for Advent of Code puzzles – each year, BFS is sufficient to solve at least a few puzzles. BFS is also a very common algorithm for coding interviews.

Memoization

Memoization is a fancy word for caching. More precisely, the result of a function call is cached on the first invocation, and the cached result is returned for the subsequent calls with the same arguments. Memoization only works for functions that return the same result for the same arguments (a.k.a. pure functions). This technique is widely popular as it can considerably boost the performance of expensive functions (at the expense of memory).

Dynamic programming

I have to admit that groking the bottom-up approach to dynamic programming took me a while. Even now, I occasionally encounter problems for which I struggle with defining sub-problems correctly. Fortunately, there is also the top-down approach which is much more intuitive. It is a combination of a recursive algorithm and memoization. The solutions to sub-problems are cached after computing them for the first time to avoid re-computing them if they are needed again.

I have used the top-down approach a handful of times in my career, but I have never used the bottom-up approach for work-related projects.

Advanced algorithms

There are many advanced algorithms, like graph coloring, Dijkstra, or Minimum spanning trees, that I have never used at work. I implemented some of them as an exercise, but I don’t work on problems that require using these algorithms.

Image: AlwaysAngry, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

“When was the last time you used this?” – Part 1: Data Structures

A candidate recently asked me, “When was the last time you used this data structure, if ever?”

The candidate admitted that as someone who worked on company internal tools, they hadn’t needed to use more advanced data structures in years. They were genuinely curious about how often I dealt with problems where these data structures were useful.

Their question provoked me to review data structures I used at work, learned for interviews, or used to solve programming puzzles and think about how often I used them. I share my list below.

Caveat: Every software developer deals with different problems. I created the list based on my experience. If I haven’t used a data structure, it doesn’t mean that it is not used or not useful. Instead, it likely means I could solve my problems without it.

Dictionary

Dictionary is one of the most commonly used data structures. It can be applied to a wide range of problems. I use dictionaries daily.

Typical implementations of Dictionary use a hash table (with a linked list to handle collisions) or a balanced Binary Search Tree. Understanding the underlying data structure gives immediate insights into the cost of basic operations like insertion or lookup.

Nowadays, every modern programming language offers an implementation of Dictionary.

Set

Set is another data structure that I use very frequently. It is surprising how often we need to handle duplicates efficiently. Set shares a lot with Dictionary. These similarities make sense because Set could be considered a Dictionary without the value.

Linked list

I implemented linked lists several times at the beginning of my career over twenty years ago, but I haven’t needed to do this since. Many standard libraries include implementations of linked lists, but again, I don’t remember the last time I needed them.

Linked list-related questions used to be a staple of coding interviews, but fortunately, they are less popular these days.

Knowing how linked lists work could still be valuable because they are sometimes used to implement other data structures, such as stacks or queues.

Stack

While I rarely need to use stack directly, this data structure is extremely common.

Every program uses a stack to track invoked functions, parameter passing, and local data storage (the call stack).

Stack is a foundation for many algorithms, such as backtracking, tree traversal, and recursive algorithms. It is often used to evaluate arithmetic expressions and for syntax parsing. JVM (Java Virtual Machine) or CLR (Common Language Runtime) are implemented as stack machines.

Even though this happened long ago, I vividly remember reviewing a diff in which a recursive tree traversal was converted to the iterative version with explicit stack to avoid stack overflow errors for extremely deep trees.

Queue

Task execution management is one of the most common applications for queues: iOS uses the DispatchQueue, WebServers queue incoming requests, and drinks at Starbucks are prepared on the FIFO (First-In, First-Out) principle.

I also use queues most frequently for task execution. My second most frequent use is solving Advent of Code puzzles with BFS (Breadth First Search), which uses a queue to store nodes to visit.

An interesting implementation fact about queues is that they often use a circular buffer under the hood for performance reasons. Implementations using linked lists are usually slower due to allocating and deallocating each node individually.

Heap / Priority Queue

I don’t remember when I had to use the Heap data structure to solve a problem at work. I don’t feel too bad about this (except when I forgot about Heap during an interview). Microsoft added the PriorityQueue type only in .NET 6 – about 20 years after they shipped the first version of .NET Framework. Apparently, they, too, didn’t consider Heap critical.

Although I didn’t need to use Heap directly, I am sure some libraries I integrate my code use it. Heap is crucial to efficiently implementing many algorithms (e.g., Dijkstra, Kruskal’s Minimum Spanning Trees).

Trees

It is challenging to talk about trees because they come in many shapes and colors. There are binary trees, n-ary trees, Binary Search Trees (BST), B-trees, Quadtrees, Octrees, and Segment Trees, to name just a few.

I have worked with (mostly n-ary) trees in every job. HTML and XML Document Object Models (DOM), C# Expression Trees, Abstract Syntax Trees, and domain-specific hierarchical data all require an understanding of the Tree data structure.

I have never had to implement a BST at work, but balanced BSTs are one way to implement (sorted) Dictionaries and Sets. For instance, the std::map and std::set containers in C++ are usually implemented as Red-black trees.

I used Quadtrees and Octrees only to solve a few Advent of Code puzzles that required spatial partitioning.

Graphs

I’ve only rarely had to use graphs for my daily job. In most cases, they were “natural” graphs – e.g., a dependency graph – that naturally formed an adjacency list.

Having said that, entire domains, such as Computer or Telecommunication Networks, Logistics, or Circuit Design, are built on graphs, so developers working in these domains work with graphs much more often.

This is my list. How about you? Are there data structures I haven’t included, but you use them all the time? Or maybe you don’t use some, which I consider a must. Please let me know.

Image: Jorge Stolfi, CC BY-SA 3.0, via Wikimedia Commons

The Biggest Enemy of Focus and Flow: Interruptions

Bill Gates once said: “Most people overestimate what they can do in one year and underestimate what they can do in ten years.”

I like to paraphrase it as “Most developers overestimate what they can do in 10 minutes and underestimate what they can do in 1 hour”.

Interruptions are a productivity killer. You can do barely anything in 6 blocks of 10 minutes but do a lot during an uninterrupted 1-hour focus session.

Even minor interruptions can be costly. For instance, when debugging intricate bugs, you need to build and hold a complex state in your head. A simple question from a colleague can destroy it and force you to restart your debugging session from scratch.

Here are the most common sources of interruptions with ideas on how to deal with them

Notifications

Nowadays, every application wants to grab our attention. Just the basics, like email, text messages, or work chat, send many notifications per hour. It’s impossible to stay focused and respond to these notifications. The truth is that most, if not all, of them can wait.

Turn off most notifications on your phone and laptop if you can. For the remaining ones, disable the sound entirely, or at least for the duration of your focus session. Consider leaving your phone in a different room and putting your laptop in the focus mode.

Check your email or work chat between focus sessions. Attend to messages that need to be answered and decide what to do with the remaining ones – likely, almost none will require action.

Teammates

If you work in the office, your teammates are a blessing but also a curse. While spontaneous brainstorming sessions, ad hoc design discussions, and the ease of receiving help to solve on-call issues are gold, they are also a source of constant distraction.

My first strategy to avoid these distractions is to… hide. I found a nice area in my building a few floors away from my team, which I can use to prevent interruptions. I often go there if I need to finish something important urgently. Occasionally, I work from home to get work done, which I view as an ultimate form of hiding.

Another option is to use noise-cancelling headphones. I don’t even play the music – I use the headphones to isolate myself and signal to other team members that I don’t want to be interrupted. It is not as effective as hiding, but it works fine most of the time.

Internet

It is hard to tell what is more difficult: coding with or without the Internet. On the one hand, a significant part of coding is searching the Internet for solutions to more or less trivial problems. On the other hand, it is so easy to fall into the downward spiral of checking “just one more thing.”

My way to combat these temptations is to use a dedicated virtual desktop for my coding session. The only programs open on this desktop are my developer tools, such as IDE, terminal, or a simulator, and a dedicated browser window, where I am not allowed to open any website unrelated to what I am working on. (I gave up on a multi-monitor setup long ago when I realized I used the other monitor(s) for things whose only purpose was to distract me, like email). Some people also use programs like Cold Turkey to block the Internet and avoid distractions.

Ultra focus mode

Long plane trips can trigger the ultra-focus. They definitely do it for me. Because the environment is restricted, there are few chances for interruptions. Ever since I experienced it for the first time, I have been trying to recreate it on the ground. If you have yet to discover it, take the opportunity on your next long flight.

Computer Science fundamentals are still important

I feel uncomfortable admitting that when I got my job at Microsoft in 2005, I didn’t know how to implement BFS (Breadth First Search). At that time, I was six years into my professional software engineering career and held a master’s degree in Computer Science.

I still didn’t know this a few years later when, one day, during lunch, someone mentioned that the candidate they had interviewed earlier “didn’t even know how to find the shortest path in a graph.” This made me feel horrible – I knew I couldn’t do it, too. In a few seconds, I turned from a seemingly successful Software Engineer at Microsoft into an impostor. This incident prompted me to improve my Computer Science fundamentals.

While I eventually learned BFS, my example shows that making solid progress in the software engineering career does not require knowing Introduction to Algorithms (a.k.a. CLRS) by heart. This is even more true today than it was twenty years ago. These days, we are working at a much higher level of abstraction. Most common algorithms, like binary search, are included in standard libraries, and implementing them is a waste of time.

Despite this, I urge every developer to learn the basics of Computer Science.

Why learn Computer Science fundamentals?

The answer is simple: learning Computer Science fundamentals can boost your career. Here is how.

You will understand unfamiliar systems quickly.

Once you learn the basic algorithms and data structures, you will see them everywhere. You will realize that HTML and XML documents are trees, key-value stores can be conceptually thought of as HashTables, and that from a single consumer perspective, Kafka topics are queues. This is powerful as it allows you to understand the behaviors and limitations of these systems even if you don’t know them deeply.

When I first started using git, I felt overwhelmed. I couldn’t understand how it worked, and the commands didn’t make much sense. One day, I watched yet another git explainer on YouTube, and it mentioned that git is a DAG (Directed Acyclic Graph). Overnight, I became a git guru fixing team members’ repos.

You will be able to solve challenging problems.

Most of the problems software developers deal with day-to-day don’t require advanced computer science knowledge. Once in a while, however, a challenging problem pops up. This is when knowing algorithms and data structures can be very handy. I remember struggling for a couple of days on a dependency graph problem when my co-worker pointed out that I could solve it quickly if I applied topological sorting.

You will do better at coding interviews.

Many interviews, especially in Big Tech companies, include coding questions. Usually, these problems can be solved with one of the standard algorithms. If you are familiar with them, you have a better chance to do well during these interviews.

How to keep skills up to date.

Most skills degrade over time. Algorithmic skills are not different. Even if you remember the idea behind an algorithm or a data structure, the details can get hazy with time. This is why it is good to refresh your skills periodically. There are many ways to do it. My favorite is participating in Advent of Code. Advent of Code is an online event in December where you are presented with two problems every day until Christmas. Solving these problems is a lot of fun and allows me to brush up my programming skills. But the best part is Solution megathreads – dedicated subreddits where others post their solutions. I check these threads once I solve the problems for the given day. They are a trove of startling insights, unconventional approaches, and programming tricks I would never think of, and I learn a lot from them.

Image: https://cs.stackexchange.com/a/107190

RFC Pull Requests: Because Code Wins Arguments

I believe in submitting clean and complete pull requests (PRs). I like PRs to compile without errors or warnings, include clear descriptions, and have good test coverage. However, there is one category of PRs where these standards do not apply – RFC (Request For Comments) PRs.

What are RFC PRs?

RFC PRs are PRs whose sole purpose is to help reach alignment and unblock development work.

When to send RFC PRs?

In my experience, sending RFC PRs can be particularly helpful in these situations:

When working in an unfamiliar codebase.
When trying to determine the best implementation approach, especially when there are several viable choices.
To clarify ideas that are easier to explain with code than with words

The first two scenarios are like asking: ‘This is what I am thinking. Is this going in the right direction? Any reasons why it wouldn’t work?’

The third one is often a result of a design discussion or a PR review. It is like saying: ‘I propose we approach it this way.’

The quality of RFC PRs

RFC PRs are usually created quickly to ask questions or demonstrate a point. These PRs are not expected to be approved, merged, or thoroughly reviewed, so there is little value in doing any work that does not directly contribute to achieving the goal. Adding test coverage is unnecessary, and the code does not even need to compile. For example, it is OK not to update most call sites after adding a function parameter.

I advise against trying to merge RFC PRs. Doing this rarely ends well. First, it is hard to change the reviewers’ perception after they saw the first quick and dirty iteration. Furthermore, comments from the initial attempt may mislead reviewers and cause unnecessary iterations. It is often easier to submit a new PR, even if an earlier RFC PR heavily inspires it.

Storytime

I used an RFC PR recently while researching how to integrate our services with a system owned by another team. The integration could be done in one of two ways: using a native client or an API call. The native client offered limited capabilities, but understanding the consequences of these limitations was difficult. I decided to send an RFC PR to get feedback on my approach and quickly learned that the client approach wouldn’t work and the reasons why.