The ultimate interview preparation framework. Part 3: Data Structures and Algorithms
Articles in this series
In the previous article we uncovered ways to talk to a recruiter during the initial screening, in order to avoid getting rejected. Today we talk about what comes next.
Modern companies that don't do rocket science more and more often avoid DSA interviews. It's getting more commonly accepted, that an ability to write logic-rich code under time pressure tells very little about how a candidate actually performs in real life. Who cares if they know what a Heaps is, if their daily routine typically consists of implementing CRUDs and fixing bugs? IRL they can use just another library that implements Heaps and move on.
One man once said on Linkedin, and he was damn right:
A failed DSA interview can be a filter for some real talent.
Nevertheless, for many companies such interviews is still a thing, so let's do this recap on the most frequently used data structures and algorithms on them and briefly uncover the ways to behave during the interview.
TL;DR; There seems to be a good prep course at Geeks4Geeks, that covers a lot of DSA-related stuff.
What to expect
So far I've encountered two main types of technical interviews:
- Classic coding interview. They provide a story to make the task sound less academic, e.g. "You are a scientist living on a space station, and your task is to do ...blah...". This is just a colorful wrapping around a real task: either write a unique algorithm or implement some well-know one, such as, for example, Ring Buffer. Unit tests are usually optional. Complexity assessment is compulsory.
- Test-driven coding interview. In my opinion, the most boring one. It can be of two types:
- Unit tests are given in advance, your task is to write code that makes them green, one by one.
- Both the code and the unit tests must be written simultaneously, starting from the most obvious happy path and going deeper into edge cases and problematic situations.
In terms of the organisation there are two types:
- Remote interview, one or two engineers join the call and ask to do sort of pair programming.
- On-site interview. Can also be paired, but in some cases they may leave you alone for an hour and then you will be presenting your solution at the end.
When it comes to the equipment needed, most of the time it will be either an online collab code editor, such as Coderpad (with or without an opportunity to compile and execute the program), or it can be an IDE of your choice on your own laptop. In the last case you are asked to share your screen. In severe cases, they may also ask you to push your code to github, I've met this at least three times. It makes sense if they don't use any collab tool and the answers of the candidates are kept on Github as a repository.
Sometimes googling is allowed, but only after the permission is explicitly granted. ChatGPT is usually off-limits.
The drawbacks of this type of interviews
It may happen, that the company tosses on your an engineer who isn't quite up for running the interview. Let me explain what I mean. A hiring manager asks one of their engineers to "interview that guy or gal they found two days ago". Since that engineer is most likely overwhelmed with usual routine already, he/she decides to have a little fun with you and check if you know... algorithms for finding best routes on a graph. How many times during your career of a typical dev you used algorithms on graphs? Yes, my thoughts exactly.
Unfortunately, such an event of un-professionalism may take place, which means not all candidates sometimes have equal chances of passing the interview. It usually happens in companies where the hiring process isn't very well fostered and streamlined. There is only little you can do about it. You can ask the recruiter to give you hints and pointers on what it is to come, but most of the time they'll reply: "Our engineers decide what kind of task it will be", which isn't really helpful.
There may also be situations, when you are certain you saw this task (or similar) before, therefore you know the solution. In that case of course your answer is swift, as you already know the tradeoffs and gotchas, so you shine like crazy and proceed to the next level without too much questioning. On the other hand, the question can be completely unfamiliar to you, and then you'll have tough times trying to apply different approaches while confined in a rather small time box. This is clearly an another disadvantage of DSA interviews frequently pointed out.
If you haven't succeed with the interview, it maybe not 100% your fault.
You can train yourself for a couple of months with Leetcode questions, but it's ultimately dead knowledge susceptible to quick weathering, as you'll most likely never use it IRL (unless you work for a scientific innovative company). Until the next interview comes.
How to behave
The most important thing: don't freak out if the task looks scary. Don't succumb to panic, it's the worst of your enemies during the intreview. Remember: this is just an interview, not the end of the world. There are much, much scarier things in life than this silly task.
The second important thing: drive the interview process and be vocal. This is expected that you communicate your train of thoughts clearly, so interviewers can follow and steer the interview if necessary. An ability to teamwork is one of the key traits they are looking for.
The third thing: dispense with the pleasantries and idle talks, you don't have time for chit-chat.
All in all, here is the step-by step algorithm to crack the coding challenge:
- Read the task carefully, ask the clarifying questions (remember: no freaking out!).
- Propose a brute-force solution, ask if it's okay to implement it. Some interviewers accept brute-force as a first step with a promise to improve it later. Also, having brute-force coded is better than having nothing.
- Code the brute-force quickly.
- Check for errors and typos, run through possible edge cases.
- Promptly talk about time and space complexity, without asking. Also worth mentioning what could happen if the input parameters are of enormous size and ways to prevent it.
- Discuss possible improvements and trade-offs.
Code complexity
A few words on complexity and it's properties.
- Complexity can be of two types:
- Time complexity (how slow/fast the algorithm is given that the input number is relatively high).
- Space complexity (how much memory this algorithm allocates).
- Time and space complexities co-exist in balance: an algorithm can't be both time and space effective. If the algorithm is fast, it usually consumes geather amount of memory and the other way around. There is no way to cheat on the laws of physics, and also it's not fair to say one algorithm sucks and the other does not: it all eventually depends on the conditions of the task.
- Complexity is presented in a form of Big-O notation. E.g. O(N). It can be roughly explained as "around N, where N is the size of the input".
- Typical complexities and their gradation from lower to higher:
- O(1) < O(LogN) < O(N) < O(m*N) < O(N*LogN) < O(Nm) < O(mN) < O(N!), where m is a constant.
- O(N) is called "linear" complexity. Everything that is higher than O(N) is considered to be "bad performance".
- If one algorithm is nested into another, their complexities multiply.
- E.g. a cycle over N within a cycle over N gives O(N*N) = O(N2).
- If one algorithm goes after another, their complexities make a sum.
- E.g. two cycles over N going one after another give O(N + N) = O(2*N).
- Constants don't contribute to the complexity and therefore don't count. O(1) is the only complexity that holds a constant, and it literary means "no work at all".
- E.g. O(N+1) = O(N)
- There is also things such as "best case" and "worst case" for algorithms whose complexity changes based on the initial shape of data.
- E.g. for a sorting algorithm the complexity will be lower if the array is almost sorted at the beginning.
How to calculate the compexity
If the alogrithm isn't standard one, and you can't determine the complexity by just looking at the code, there is a method I find useful. It's called The Stepcount method.
- Take a look at the algorithm fn(n) closely, understand what it is doing.
- Select your N. It shouldn't be too little (so not all if statements are hit), or too big. Maybe 7 or 9 is enough.
- Now start "executing" the algorithm f(n), assuming n to be your chosen value. Every pass of the algorithm or a cycle body inside gives you 1 point. Single operations don't add any points.
- Execute the algo until the exit condition is reached, and sum up all you points given.
- Now remember all the complexities you know, and start calculating all of them using your n. E.g. N! = 7! = 5040, N^2 = 7^2 = 49 and so on. Whichever value is closer to the sum of the points is probably the right answer.
Array
Arrays are built-in type for many languages, and operations such as push()/pop()/shift()/unshift() are already available out of the box (hello, Golang). That's why it makes sense to talk about some other fun stuff here.
Bubble sort
This is only applicable to a numerical array.
Simple algorithm with two nested loops, where an item bubbles up in the inner loop. Slow, but memory-efficient.
const bubbleSort = <T extends number>(arr: T[]): T[] => {for (let i = 0; i < arr.length; i++) {for (let j = i; j < arr.length; j++) {if (arr[i] > arr[j]) {const tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}}return arr;};
Merge sort
This is only applicable to a numerical array.
Here the idea is to split the array onto arrays of length 1 using recursion, and then merge again whilst sorting.
const mergeSort = <T extends number>(arr: T[]): T[] => {if (arr.length <= 1) {return arr;}const middleIndex = arr.length / 2;let leftPart = arr.splice(0, middleIndex);let rightPart = arr;return mergeArrays(mergeSort(leftPart), mergeSort(rightPart));};const mergeArrays = <T extends number>(arr1: T[], arr2: T[]): T[] => {let result: T[] = [];while(arr1.length && arr2.length) {const element = arr1[0] < arr2[0] ? arr1.shift() : arr2.shift();if (element) {result.push(element);}}return [...result, ...arr1, ...arr2];};
Quick sort
This is only applicable to a numerical array.
The main idea is that we divide an array into two parts using an index P (which is typically one at the center). Then to the left part we move all elements that are smaller than array[P], and to the right part we move all element that are greater. At this point we can say, that to the left all elements are smaller than any element from the right part, so in that sense two parts of the array are sorted relatively to each other. We do the same for both left and right parts recursively to make the whole array sorted.
const quickSort = <T extends number>(array: T[], indexStart: number, indexEnd: number): T[] => {if (array.length > 1 && indexStart < indexEnd) {const pivotIndex = partition(array, indexStart, indexEnd);// in the left part there is no elements that are greater than array[pivotIndex]// that's why repeat the operation for that partif (indexStart < pivotIndex - 1) {quickSort(array, indexStart, pivotIndex - 1);}// in the right part there is no elements that are smaller than array[pivotIndex]// that's why repeat the operation for that partif (pivotIndex < indexEnd) {quickSort(array, pivotIndex, indexEnd);}}return array;};const swap = <T extends number>(array: T[], indexOne: number, indexTwo: number) => {let tmp = array[indexOne];array[indexOne] = array[indexTwo];array[indexTwo] = tmp;};const partition = <T extends number>(array: T[], indexStart: number, indexEnd: number): number => {// get an element in betweenconst chosenElement = array[Math.floor((indexStart + indexEnd) / 2)];// take indexes of start and endlet left = indexStart;let right = indexEnd;// start moving indexes toward each other until they meetwhile(left <= right) {// moving to the left and search for the first element which is smaller then chosenElementwhile(array[left] < chosenElement) {left += 1;}// moving to the right and search for the first element which is greater then chosenElementwhile(array[right] > chosenElement) {right -= 1;}// if indexes didn't go one over anotherif (left <= right) {// then swap the elementsswap(array, left, right);// move indexes forwardleft += 1;right -= 1;}}// return an index on which the cycle has endedreturn left;};
Binary search
This is only applicable to a pre-sorted numerical array.
The main idea is to divide the array in half, and see if an element in that position is smaller or greater that the one we are looking for. Depending on the result of the observation, we proceed to the right or to the left, and repeat the same action recursively until the element is found or an array of length 1 is given.
The binary search algorithm exists in two types: recursive and iterative. The iterative version has lower memory consumption, so I'll go with that one.
const binarySearchIterative = <T extends number>(input: T[], element: T): number => {let startIndex = 0;let endIndex = input.length - 1;while(endIndex >= startIndex) {const midIndex = Math.floor((endIndex + startIndex) / 2);const midElement = input[midIndex];if (midElement === element) {return midIndex;}if (midElement > element) {endIndex = midIndex - 1;}if (midElement < element) {startIndex = midIndex + 1;}}return -1;};
Two-pointer search
This is only applicable to a pre-sorted numerical array.
The algorithm solves a quite narrow task: find any pair of elements whose sum equals to X. Seems oddly specific, yet I was asked this question during one of my interviews.
The idea is have two indexes set to 0 and the array length -1, and then move them slowly but steadily towards each other.
const twoPointersSearch = <T extends number>(array: T[], equalTo: T): [T, T] | null => {let startIndex = 0;let endIndex = array.length - 1;while(startIndex <= endIndex) {const startElement = array[startIndex];const endElement = array[endIndex];const sum = startElement + endElement;if (sum === equalTo) {return [startElement, endElement];}if (sum < equalTo) {startIndex += 1;}if (sum > equalTo) {endIndex -= 1;}}return null;};
Circular buffer
Also known as "Ring buffer", is an array of fixed length, that stores every incoming value at a certain position that is calculated using the division by module.
Map
Also known as "Hash", is a key => value structure. The most prominent property of Maps is that under certain conditions they can improve the time complexity of an algorithm from O(N2) to O(N). See for yourself.
Task: in an ordered array find the first pair of numbers that make a sum of X. The brute-force solution would be a two nested cycles with the complexity of O(N2), but Maps can help to turn this algorithm linear.
function findPairWithSum(arr: number[], targetSum: number): [number, number] | null {const map = new Map<number, boolean>();for (let i = 0; i < arr.length; i++) {const currentNum = arr[i];const complement = targetSum - currentNum;if (map.has(complement)) {return [complement, currentNum];}map.set(currentNum, true);}return null;}
Linked list
A linked list is a set of objects in memory, each object references the next one, so the form a certain "chain" or "list". Any linked list has a head (first element) and the tail (the last) element.
Typical operations on a linked list are somewhat similar to the ones from array: push()/pop()/shift()/unshift()/search().
Tree
A tree is a special kind of Graph that does not have cycles. There are several ways to store trees: a naive way using pointers (not very effective), adjacency lists, nested sets.
Here is a simple implementation of a tree using an array to store adjacency and a map for the node payload.
type TreeNode<P> = {id: number;payload: P;};class Tree<P> {root: TreeNode<P> | null = null;nodes: Map<number, TreeNode<P>>;edges: Map<number, number[]>;constructor() {this.nodes = new Map<number, TreeNode<P>>();this.edges = new Map<number, number[]>();}...}
Traverse in-depth
Traversing in-depth means that the first visited node will be the deepest leaf.
...public traverseInDepth(cb: (node: TreeNode<P>, depth: number) => void) {if (!this.root) {return;}const traverse = (node: TreeNode<P>, depth: number) => {if (!node) {return;}cb(node, depth);this.edges.get(node.id)?.forEach(connectedNodeId => {const childNode = this.nodes.get(connectedNodeId);if (childNode) {traverse(childNode, depth+1);}});};traverse(this.root, 0);}...
Traverse in-breadth
Traversing in-breadth allows visiting nodes layer-by-layer, from top to the bottom. This is useful for the tree visualisation and has some other applications.
...public traverseInBreadth(cb: (node: TreeNode<P>, depth: number) => void) {if (!this.root) {return;}let stack = [{nodeID: this.root.id,depth: 0,}];while(stack.length) {let stackItem = stack.shift();if (!stackItem) {return;}let node = this.nodes.get(stackItem.nodeID);if (!node) {return;}cb(node, stackItem.depth);this.edges.get(stackItem.nodeID)?.forEach(connectedNodeId => {stack.push({nodeID: connectedNodeId,depth: stackItem.depth + 1,});});}}...
Prefix tree (Trie)
Prefix trees is a special kind of Trees, where every node holds the maximum common prefix of all it's child nodes. The tree is used for string search, the most prominent use-case of a prefix tree is to implement search autocompletion.
Binary tree
Binary trees is a special kind of Trees, where every node has no more than two child nodes. The most prominent example of a Binary Tree is a Heap.
Heap
A heap is a binary tree with special properties: for every node the value of it's children is smaller (max-heap) or greater (min-heap) than the value of that node.
Heaps can aid implementing array heap sort, or when it's needed to keep top N elements of higher/lower value on top. Heaps can be used to implement priority queues.
Node payload of a Heap is merely a number, and also thanks to the nature of Heaps, a simple one-dimensional array can be used to store it. There are simple formulas to get nodes of the tree.
class MinHeap {private data: number[] = [];public getParent(i: number): number {return this.data[Math.round((i-1)/2)];}public getLeftChild(i: number): number {return this.data[2*i + 1];}public getRightChild(i: number): number {return this.data[2*i + 2];}}
Queue
A queue is a list of elements, similar to arrays and linked lists. They typically have operations such as add() and unshift(). They may also be called "FIFO buffers".
Queues play crucial role in system design, as microservices usually organise their work using different kind of queues. In many languages there are native support of queues. For example, in Golang a channel a is typical queue that can be used for ordered processing of elements coming from different sources asynchronously and in parallel.
Priority queue
A priority queue is a queue where elements have priorities. If an element comes and it has higher priority than the last element in the queue, it will be pushed up closer to the beginning of the queue.
Heaps are canonically used to effortlessly implement priority queues.
Dynamic programming and Backtracing
In two words this is basically a programming approach when a large task is split into several smaller ones, but similar to the original one in terms of structure (typically by using recursion). Then this split continues until the solution is found.
The key point here to mention is that recursive steps can be repeated several times, and thus the result must be cached to save the computation effort. The canonical example used to illustrate the principle is calculating Fibonacci numbers.
In my practice I've only met such a task once or twice. Both times it was about finding all routes (or the best route) in a graph or on a chess board (which is essentially the same).
Backtracking is about searching for a solution by picking an arbitrary one, then checking for that potential solution to satisfy the requirements. If not, choose another potential solution and repeat until the true solution is found.
Sergei Gannochenko
Golang, React, TypeScript, Docker, AWS, Jamstack.
19+ years in dev.