loading...
Cover image for 4 tricks to boost up your algorithms game

4 tricks to boost up your algorithms game

caroso1222 profile image Carlos Roso ・4 min read

TL;DR.

  1. Associate O(1) with table lookups and math
  2. O(n) is for list traversal
  3. The weird logarithm is for sorting: O(nlogn)
  4. Connect O(n2) with nested loops

Whether you agree or not with whiteboard interviews and algorithmic questions, becoming good at this is yet another skill you should master at some point. And, to become good at algorithms, you should grasp the notion of BigO. Notice I wrote "grasp", not "master". There's nothing mystic about this topic.

BigO is simply a notation that tells you how well or bad your algorithm performs as your input size grows. I've identified some tricks I use from time to time to solve and analyze algorithms.


I sent this post weeks ago to +450 devs on my maillist. Join here if you want to get my tips and thoughts on career growth.


1. Associate O(1) with table lookups and math

Means your algorithm will take roughly the same amount of time regardless of the input size. Applies normally to math operations and object lookups.

// regardless of a or b, a sum is a math operation that takes just 
// one clock cycle to complete
const add = (a, b) => a + b;

// no matter of how big your map is (e.g an object in JavaScript), 
// a lookup will take 1 cycle to complete
const lookup = (map, key) => map[key];

You know when you access the bar prop from the foo object like foo.bar? Well, that's an O(1) operation.

Note: Hashmap lookups are considered to be O(1) in theory regardless of how they solve collisions

2. O(n) is for list traversal

Means your algorithm run time will grow linearly with the input. Take, for instance, the algorithm to find the max number of a list. Your algorithm necessarily needs to visit every element to know which number is the max. If your list grows 2x, your algorithm will roughly take twice the time to complete.

// you need to loop through all the elements to find the max.
function findMax(list) {
  let max = -Infinity;
  for (obj of list) {
    if (obj > max) max = obj
  }
}

3. The weird logarithm is for sorting: O(nlogn)

This one is easier than what it looks like. Don't worry about the weird logarithm over there. Logs in BigO notation normally means you're dividing something into halves, and each half is divided again into halves. But, the only thing you need to remember is this: O(nlogn) is mostly associated with sorting. Sorting lists are not free operations, you're incurring in costs when using them. Let's see an example of a very inefficient way to get the max of a list:

function getMax(list) {
  return list.sort((a, b) => b - a)[0]
}

O(n) is better than O(nlogn) because if you multiply 🦄 by logn, you get a bigger 🦄.

Now you have good criteria to decide what's most efficient to find a max. Would you use the O(n)? or the O(nlogn) algorithm?

4. Connect O(n2) with nested loops

Means your input size affects the algorithm like crazy (not quite as bad as others). If your input size doubles, your run time grows 4x. If your input grows 4x, your run time grows 16x. This normally takes the shape of a nested loop. Let's write a very inefficient way to find if an array has a duplicate.

function hasDuplicates(list) {
  for (let [i, el_i] of list.entries()) {
    for (let [j, el_j] of list.entries()) {
      if (i !== j && el_i === el_j) return true;
    }
  }
  return false;
}

For every element in the list of size n, we're looping over the whole list of size n. That means we're visiting the elements n*n = n2 times.

Can you come up with an O(n) algorithm for this task? one that only loops through the list once? let me know in the comments

Summary

No need to dig into this topic if you're against learning algorithms, I can respect that. Just save this table and know that some tasks cost more than others and why.

Alt Text

Others

There are all kinds of complexities and nuances on this topic. You're free to keep researching. But, if you can grasp these 4 concepts and stick them to heart, you'll level up your algorithms game for interviews, PR reviews, or just to write better code.


Don't fear coding interviews

I've used these concepts to get better at coding algorithms. I've since landed interviews (and job offers) at Amazon, Toptal and a few more top remote work platforms. I wrote a FREE guide with a lot of tips and tricks to ace remote tech interviews. If you're curious, you can sign up here and get it in my next email.

Alt Text


My DMs on Twitter are always open to help you on your career, algorithm interviews, resume questions, or growth tips. Shoot me a message or just say hi!

Discussion

pic
Editor guide
Collapse
mortoray profile image
edA‑qa mort‑ora‑y

Good overview.

But pedantic me would like to point out that math is technically related to the number of bits in the data size. We usually deal with fixed sizes, but things like Python have unlimited integer size, and classes like BigDecimal are common in languages.

Hashmaps/tables, yeah, your linked site shows well the complexity there. So, average time O(1), but really, it's complicated. :)

Collapse
caroso1222 profile image
Carlos Roso Author

Good insight, thanks! Yeah, a worst-case scenario for hashmaps would require O(n) for read if all the objects happen to collide under the same hash (thus making the linked list abnormally large). As you point out, O(1) is a good average for newcomers and for interview purposes :D

Collapse
marln94 profile image
marln94

I'm starting to take this kind of interviews for remote work and find this guide so helpful, thanks!

Collapse
caroso1222 profile image
Carlos Roso Author

Nice, good luck with your interviews!

Collapse
inspiredbynikki profile image
Nikki

Bless you.

Collapse
caroso1222 profile image
Collapse
thisdotmedia_staff profile image
This Dot Media

This is awesome Carlos! Love it 🙌

Collapse
caroso1222 profile image
Carlos Roso Author

Appreciate it, I'm glad you liked it!

Collapse
caroso1222 profile image
Carlos Roso Author

I'm always happy to share what I learn, glad you liked it!

Collapse
mars profile image
Mara McCrann

This is a very helpful guide for me as someone who's currently weak at algorithms. Thank you! I would ask questions to 'ya if needed.

Collapse
caroso1222 profile image
Carlos Roso Author

Im glad you found it helpful!

Collapse
saniashindet profile image
Sania Shinde

Jake Paul is set to make his boxing return on the undercard of the Nov. 28 Tyson vs Jones Live Free fight against former NBA player Nate Robinson. From the look of things, his older brother appears to be following along for an encore presentation.

Collapse
lonnieharperc profile image
lonnieharperc

Get ahead of the game and find out how to Watch AFL Grand Final 2020 Live on 7plus. If you're planning to stream the Grand Final live, here's what you need to know.

Collapse
uddhavsabal profile image
uddhavsabal

The Western Hockey League has announced it will start its season Jan. 8 after the World Juniors live stream free are completed in Edmonton. The regular season will minimize travel and keep play exclusively within one of four new divisions.

Collapse
noelwilliams profile image
noelwilliams

A website dedicated to the highest quality of free Boxing live stream. You can watch all best Boxing matches here and this website is also an alternative for Live Boxing Stream Roku.