DEV Community

Sandor Dargo
Sandor Dargo

Posted on • Originally published at sandordargo.com

Should you really memorize algorithm complexities?

A few years ago I read one of Yegor Bugayenko's articles about his feelings about applying to a BigTech company. He wrote something like he would never be accepted and could never pass such interviews because he is not prepared for such nonsense and would not waste his time doing so.

I felt the same. I thought I was already a good programmer and I wouldn't need those. In any case, who wouldn't want to hire me? (Hint: in fact, many, way too many...)

I was partly wrong.

I realized that when I started to go through some interview processes with different companies.

It turned out quite fast that what I want from a job are things that many others want too. It must be remote, it must be a senior/senior+ position and it must pay a hefty salary.

Companies receive lots of applications for such positions and they must be able to select somehow. The competition is strong. They must be able to assess your skills. One relatively fast way of doing that is asking some questions about data structures and algorithms in an interview.

Let's see how I approached the first interviews and how my views changed.

Algorithms

By the time I went to my first interviews, I could figure out many solutions to easy and medium LeetCode problems on my own without using hints. I could analyze the space and time complexity of the solutions, although not in a very sophisticated manner. More on that just in a minute.

My experience is that many problems can be solved in C++ as a combination of standard algorithms. There are more than 100 of them, combining them is very powerful. Although C++ Reference lists the complexity of each algorithm, I didn't always know them. You can imagine how it impacted my complexity analysis performance.

Binary search complexity

So how did I change my approach?

I still think that being able to implement the different sorts on a whiteboard is superfluous. You'll almost never need them. In most positions, using what the standard library of your language provides is a way better choice than implementing whatever sorting algorithm. And if one day you have to implement it, it's not a big deal to look up the algorithm in a book.

No sane interviewer should ask for it.

On the other hand, it is extremely useful to know the complexity of the different algorithms and their requirements. For example, if you want to decide in C++ whether a value is in a container or not, you might use binary_search or find. While std::binary_search is faster (O(logN) vs O(N)), it requires that you have a sorted container.

As sorting a container has the complexity of O(N*logN), it's also obvious that it's not worth sorting a container just so that you can binary search it.

Knowing the standard functions, their requirements and their complexities lets us decide which path to take in different situations. You don't have to be able to implement them on the spot. (Even though implementing a simplified version of find with O(N) is really not complex)

Data structures

The case for data structures though is a bit different. When it comes to algorithms, they are quite specific and you don't have plenty of different functions to achieve the same thing. With data structures, it's different. In the C++ STL you have quite a few:

  • array
  • vector
  • list, forward_list
  • deque, stack, queue, priority_queue
  • set, multiset
  • map, multimap
  • unordered_set, unordered_multiset
  • unordered_map, unordered_multimap
  • span

Some of them are just adapters, but still. They are all there to store data. This list has 20 elements, while there are more than a hundred algorithms. I'd advise that you learn them well.

Understand how they are implemented. No, you don't have to be able to implement them with all their special cases, but know that a list is a doubly linked list, and know that vectors are dynamic size arrays with contiguous element storage. Know that a map is implemented as a tree, while an unordered_map is a hashmap.

Also focus a bit on learning how complex it is to access, insert or delete an element from these data structures. When you know the underlying data structure, most of these questions become quite easy given that you learnt about the structures once. If not, it's high time to do so.

I find this important because when you implement an algorithm on your own, it becomes way easier to analyze its complexity. You'll understand easily that finding an item in a map is O(logn), while doing the same in a hashmap is constant on average.

Once you understand these complexities it also becomes simpler to understand when and why to use each of these data structures.

To learn all these, you don't need any fancy tool or platform. Browsing C++ Reference and taking some notes of the complexities are more than enough.

Conclusion

In this article, I shared with you how unimportant I found knowing details about algorithms and data structures before I started interviewing companies after working for 9 years at the same corporation. I was pretty much wrong. I still think that knowing how to implement all the algorithms would be an overkill and I would not focus on that while preparing, but knowing the complexities of some algorithms of your standard library is essential.

What I found even more important is that you understand deeply the data structures offered by the standard library of your chosen language. Understand what kind of data structures are used for their implementations and the complexities of their operations.

Invest a few hours doing so and you'll significantly improve your chances to make good decisions to choose a data structure and nailing the complexity analysis at an interview.

Connect deeper

If you liked this article, please

Top comments (3)

Collapse
 
jmfayard profile image
Jean-Michel πŸ•΅πŸ»β€β™‚οΈ Fayard • Edited

My point of view is it's very rare that mathematics matters in programminng but when they do matter, they matter a lot.

Examples:

  • security: if someone finds out that https has a flaw that makes it possible to decipher it without quantum computers and at a reasonable cost in time, that would obviously changes everything
  • broken concepts: bad programming languages have nullable booleans (even four values in Javascript because why not!). The technical name for an algebra that has 3 values is: not a boolean algebra.
  • efficiency: Bitcoin is based on a "proof-work" concept. As a theoritical concept it's interesting. But the effects in the real world are totally inacceptable: by design it wastes preciously rare energy, it kills more people via air pollution and it helps the planet to burn faster via CO2 emissions.

When something is mathematically broken by design like bad security protocols, nullable booleans, or proof-of-waste blockchains, you are doomed.

Give up and start from scratch.

Collapse
 
sandordargo profile image
Sandor Dargo

I work with C++, and in this world, performance matters a lot. You don't need very complex math, but understanding how one algorithm, one data structures fares against another helps a lot. But I realized that all this becomes much easier if you understand what is under the hood. And that theory is one thing, but you have to understand the bottlenecks of modern hardware in order to make better decisions. (e.g. limit the CPU cycles vs. make your program cache friendly)

Collapse
 
detzam profile image
webstuff

a person should know about them and then if needed apply them also you can search the web for the code if you forget a part of it.