Question 1

What is the complexity of common operations: array access by index, push to the end, shift from the front, includes, Map get, sorting? Explain why they differ.

Accepted Answer

Index access and push to the end are O(1) (push is amortized): the element sits at a known address, and the end is known. shift from the front is O(n) because all elements must move one position. includes and indexOf are O(n): in the worst case we scan the whole array. Map get is O(1) on average because the key is hashed and leads straight to the right bucket. Built-in sorting is O(n log n).

Question 2

What does O(n) mean and why do we need Big O notation at all? Why do we drop constants?

Accepted Answer

Big O describes how the amount of work grows with input size, not how many milliseconds a particular run takes. O(n) means that doubling the input roughly doubles the work. We drop constants because for large n they matter less than the shape of growth: 2n and 100n are both linear, while n² eventually overtakes them. The notation does not replace profiling, but it quickly rules out an approach that will break on big data.

Question 3

How does an array differ from a linked list? When would you pick one or the other?

Accepted Answer

An array keeps elements contiguous in memory, so index access is O(1) and scanning it works well with the CPU cache. Inserting or removing in the middle or at the start is O(n) because of shifting. A linked list consists of nodes pointing to the next one: inserting or removing a node you already have a reference to is O(1), while access by index is O(n) because you walk from the head. In practice an array is almost always faster thanks to the cache, and a list is justified where you need frequent insertions in the middle through a ready pointer, for example in an LRU cache.

Question 4

How does binary search work, what is its complexity, and what must be true about the data?

Accepted Answer

The data must be sorted. Take the middle element: if it equals the target, done; if it is smaller, search the right half, otherwise the left. Each step discards half, so the complexity is O(log n): a million elements take about 20 steps. The typical mistake is the bounds: you must decide clearly whether the right end is included, and compute the middle without overflow and without an infinite loop. For unsorted data binary search does not work, so either sort once or use a Map or an index.

Question 5

How does a stack differ from a queue? Give one programming example of each.

Accepted Answer

A stack follows LIFO: the last element added is taken first. Examples: the function call stack, the back button, checking balanced brackets. A queue follows FIFO: whoever came first is taken first. Examples: a job queue for processing, breadth-first graph traversal. In JavaScript an array works for a stack through push and pop at the end, while for a queue shift from the front is slow on large arrays, so a custom structure with two indices is better there.

Question 6

How does a hash table (for example, a Map) work and what is a collision? Why is lookup O(1) only on average?

Accepted Answer

A hash function turns the key into a number that determines a slot in an array, so get and set do not scan all elements. A collision is when different keys land in the same slot. It is resolved with chains inside the slot or by probing for the next free slot. While the table is moderately full and the hash spreads keys evenly, a slot holds few elements and the operation is O(1). In the bad case, when many keys pile up in one place, it degrades to O(n). When the table fills up, it is enlarged and all keys are redistributed.

Question 7

What does a recursive function consist of? What happens if you forget the base case, and what can replace recursion?

Accepted Answer

A recursive function has a base case that returns an answer without another call, and a step that reduces the problem to a smaller version of itself. Without a base case the calls never stop, the call stack overflows, and you get an error like Maximum call stack size exceeded. Recursion can be replaced with a loop and an explicit stack, which is useful for very deep structures. Naive recursion with repeated subproblems, such as Fibonacci, can be exponential, and memoization fixes that.

Question 8

How does time complexity differ from space complexity? Give an example where we trade one for the other.

Accepted Answer

Time complexity shows how the number of operations grows, while space complexity shows how the extra memory the algorithm allocates beyond the input grows. A classic trade is a cache or hash table: finding a pair with a given sum in an array without extra memory takes O(n²), while with a Set it runs in O(n) but uses O(n) memory. Another example is memoization, which pays memory for speed. The choice depends on constraints: on a small device memory is more expensive, on a server under load time is more expensive.

Question 9

What is the two pointers technique? Explain how to use it to check whether a sorted array contains a pair with a given sum.

Accepted Answer

Two pointers are two indices that move through an array by a simple rule and replace nested loops. For a sorted array, put one at the start and the other at the end. If the sum is less than the target, move the left pointer right to increase the sum; if it is greater, move the right pointer left. Each element is visited at most once, so the complexity is O(n) time and O(1) memory, instead of O(n²) for checking all pairs. The technique works precisely because of sorting: it guarantees that moving a pointer in one direction changes the sum predictably.

Question 10

What is a stable sort and why might it matter? What is the complexity of the built-in sort in JavaScript?

Accepted Answer

A sort is stable if elements with equal keys keep their relative order. This matters when sorting by several fields in a row: first by date, then by category, and within a category the date order is preserved. Array.prototype.sort in modern JavaScript is stable by specification and runs in O(n log n). A typical trap: without a comparison function, sort compares elements as strings, so the numbers 10 and 9 end up in the wrong order.

Question 11

How do you remove duplicates from an array and what is the complexity of the simplest ways? Why is a Set better here than nested loops?

Accepted Answer

The simplest way is to search each element among the ones already added using includes: that is O(n²) because includes itself is linear. A Set stores unique values in a hash table, checking and adding run in O(1) on average, so the whole pass is O(n). In JavaScript it is enough to write new Set(arr) and spread it back into an array if needed. The order of first appearance is preserved. For objects a Set compares by reference, so duplicates by content must be distinguished by a key, for example an id.

Question 12

What is the complexity of a single loop, two nested loops over the same array, and a loop where the variable doubles each time? How do you estimate it quickly?

Accepted Answer

One pass over n elements is O(n). Two nested loops over n are n × n, that is O(n²): on 10^5 elements that is already 10^10 steps and seconds of a blocked process. A loop where a variable doubles (i *= 2) or is halved runs log n times, so it is O(log n). A quick estimate: multiply the iteration counts of nested loops, add sequential loops, and keep the largest term in the result. Hidden loops count too: includes or indexOf inside a loop add another factor of n.

Question 13

How do you find the first non-repeating character in a string? Describe the approach and the complexity.

Accepted Answer

The first pass counts how many times each character occurs and stores it in a Map or an object. The second pass goes through the string in its original order and returns the first character whose count is one. Both passes are linear, so together it is O(n) time and O(k) memory, where k is the number of distinct characters. The naive version with nested loops runs in O(n²). Edge cases: an empty string and a string where every character repeats, in which case we return a special value such as null.

Question 14

How do you reverse a linked list? Describe the iterative approach and the complexity.

Accepted Answer

Use three pointers: prev (initially null), curr (the head), and next. At each step remember curr.next, point curr.next at prev, then move prev to curr and curr to the saved next. When curr becomes null, prev points to the new head. The complexity is O(n) time and O(1) memory. A typical mistake is forgetting to save the next node before relinking, so the rest of the list is lost. The recursive version is shorter but uses O(n) of stack.

Question 15

Array a has length m + n: the first m elements are sorted and the rest are zeros as spare space. Array b with n elements is also sorted. How do you merge b into a in place so that a becomes sorted?

Accepted Answer

If you fill a from the start, you overwrite elements you have not compared yet. So we go from the end with three pointers: to the last real element of a, to the last element of b, and to the write position at the very end of a. Each time we place the larger of the two current tails at the write position and move the matching pointers. The loop continues while anything is left in b, and the rest of a is already in place. The complexity is O(m + n) time and O(1) extra memory, whereas concat plus sort is O((m + n) log(m + n)).

Question 16

Why is arr.push() considered O(1) even though the array is sometimes copied entirely? Explain amortized complexity for push and for Map growth. When does this amortization hurt in production?

Accepted Answer

A dynamic array keeps a buffer with spare capacity: while there is room, push writes to the end in O(1). When the buffer is full, V8 allocates a new one, roughly 1.5 times larger, and copies all n elements, which is O(n). Amortized analysis counts the total over the whole sequence: if capacity grows geometrically, n insertions cause only a few n copies in total, so O(1) on average per push. If the buffer grew by a constant amount, the total would be O(n²). Map and Set also rebuild their hash table as they grow. Amortization does not bound the latency of a single call, so in production it shows up as rare spikes: one push or set on a large collection can take milliseconds and block the event loop.

Question 17

Name the complexity in V8 and explain where the trap is: arr.includes(x), arr.indexOf(x), arr.pop(), arr.shift(), arr.unshift(x), arr.slice(), arr.splice(i, 1), [...arr], arr.sort(), map.get(k), set.has(k), str += 'x' in a loop.

Accepted Answer

Linear, O(n): includes, indexOf, find, shift and unshift (they shift all indices), splice from the middle, slice, spread, concat, Array.from. Constant on average: push, pop, index access, Map.get, set, has, delete, Set.has and add. Sort in V8 is TimSort: O(n log n) comparisons in the worst case, close to O(n) on already sorted data, stable since Node 11. Strings: str += x in a loop builds a rope in V8, so it is usually not quadratic, but the string is flattened on read. For large volumes it is safer to collect an array of parts and join, or write to a stream. About memory: slice, spread, map and filter create a new copy, O(n) extra memory, while sort works in place and mutates the input array.

Question 18

When should you use a Map for a dictionary in Node.js and when a plain object? What breaks if you count word frequencies from user input in {}?

Accepted Answer

Map is for a dynamic dictionary: keys come from outside, there are many of them, and they are added and removed. An object is for a record with known fields, config, a DTO, anything that goes into JSON. The differences that break code. Object keys are always strings or symbols: obj[1] and obj['1'] are the same field, and an object used as a key becomes "[object Object]". Map compares with SameValueZero, so 1 and '1' are different keys, and an object is looked up by reference. Order: a Map iterates in insertion order. An object puts integer keys first in ascending order, then string keys in insertion order.

Question 19

What conditions does binary search need? Can you look up a record by id in an array sorted by created_at? And when does binary search on an in-memory array lose to a Map or a database index?

Accepted Answer

Binary search needs a monotonic predicate: there is an index before which the condition is false and after which it is true. A sorted array is a special case for the predicate a[i] ≥ x. That is why you can search by answer, by time in logs, or for the first bad commit in git bisect. An array sorted by created_at is not sorted by id. The predicate id ≥ x is not monotonic on it, and the search returns garbage without any error. The exception: ids are guaranteed to grow with time, like an auto-increment in one database or UUIDv7. An exact lookup in a Map is O(1) on average, binary search is O(log n), which for 10^6 is 20 comparisons.

Question 20

Compare merge sort and quick sort: average and worst-case complexity, memory, stability. What does V8 use and why?

Accepted Answer

Merge sort splits the array in half down to single elements and merges the sorted halves with two pointers. There are log n levels, each doing O(n) work, so it is always O(n log n) regardless of the data. It is stable if, on ties, you take the element from the left half. Quick sort picks a pivot, partitions the array into elements smaller and larger than it, and sorts the parts recursively. On average it is O(n log n) and fast in practice: it works in place and is friendly to the CPU cache. But with a bad pivot, for example the first element on already sorted data, each partition peels off one element: O(n²) and recursion depth n, which in Node ends in a RangeError after just a few thousand elements. Protection: a random pivot, median of three, introsort, which switches to heap sort when the recursion gets too deep. Classic quick sort is not stable.

Question 21

Where do linked lists show up in a real Node.js backend, given that JS has arrays? Why is a list of objects in JS often slower than an array even though insertion in the middle is O(1)?

Accepted Answer

A linked list wins when you already hold a reference to the node: removing it or inserting next to it is O(1) with no shifting. Finding a node by value or index is still O(n). That is why a list makes sense together with an index that gives a reference to the node. The classic example is LRU: a Map from key to node plus a doubly linked list ordered by recency, and both get and put are O(1). Where it shows up in a real stack: libuv keeps handles and request queues in intrusive lists, and Node timers are grouped into lists by duration. Redis used to store LIST as a linked list, and since version 3.2 it is a quicklist, a list of compressed blocks. So lists live mostly in runtimes, not in application code.

Question 22

Why does BFS give the shortest path only in an unweighted graph? What do you use when edges have weights, for example latency between services, and what if the weights are only 0 and 1?

Accepted Answer

BFS discovers vertices in layers: first at a distance of 1 edge, then 2, and so on, so it minimizes the number of edges, not the weight. If the direct edge costs 100 ms and the path through B costs 10 ms per edge, BFS picks the direct one because it is a single edge. For non-negative weights use Dijkstra: instead of a queue, a min-heap by current distance, where the nearest unfinalized vertex has its final distance and its neighbors are updated, O((V + E) log V) overall. If the weights are only 0 and 1, 0-1 BFS on a deque is enough, in O(V + E). With negative weights Dijkstra gives wrong answers because a finalized vertex may later become closer, so you need Bellman-Ford, which also detects negative cycles.

Question 23

How do you tell that a problem can be solved with dynamic programming? When do you pick top-down memoization and when a bottom-up table? When is recursion appropriate in Node at all?

Accepted Answer

There are two signs: optimal substructure (the answer is made of answers to smaller subproblems) and overlapping subproblems, meaning the same smaller problem is needed many times. If they do not overlap, as in merge sort, it is plain divide and conquer and a cache will not help. A practical test: write the naive recursion and see whether call arguments repeat. Then I define the state (what dp[i] means), the transition, the base case and the evaluation order. Top-down memoization is close to the recursive idea and computes only reachable states, while a bottom-up table has no recursion, predictable memory, and often compresses to a few variables. Recursion in Node is fine only for guaranteed small depth, otherwise you need iteration.

Question 24

What is a Bloom filter and where is it useful on the backend? And briefly: how does token bucket work as an algorithm, what is its memory and complexity?

Accepted Answer

A Bloom filter is a bit array of m bits and k hash functions. Adding sets k bits to 1. A check looks at the same k bits: if at least one is 0, the element was definitely not added. If all are 1, the element may have been added, because other elements could have set those bits. There are no false negatives, but there are false positives. You cannot delete an element because a cleared bit might belong to others; a counting Bloom filter exists for that. Memory: about 9.6 bits per element for 1% errors at k ≈ 7, regardless of key length. 10 million URLs take roughly 12 MB instead of hundreds of megabytes in a Set.

Question 25

BFS over a graph of 10^5 vertices with an array and shift() takes seconds. Why? Describe a queue with O(1) add and take, and explain how it frees memory.

Accepted Answer

shift on an array moves all elements by one position, which is O(n), and BFS becomes O(n²). The fix is a queue on an array with a head index: push appends to the end, and taking reads the element at index head and increments head, with no shifting, so both operations are O(1). To keep memory from growing forever, the taken element is cleared, and when head exceeds half the length, the array is trimmed and head is reset to zero. An alternative is a linked list with head and tail pointers, or a ring buffer.

Question 26

How do you merge two sorted linked lists into one sorted list without creating new nodes? Describe the approach and the complexity.

Accepted Answer

Take a dummy node so you do not have to special-case which node becomes the head of the result, and a tail pointer to the last node of the result. While both lists are non-empty, compare the heads, attach the smaller one to tail.next, and advance that list's pointer and tail. When one list ends, attach the rest of the other one whole to tail.next, since it is already sorted. The result is dummy.next. The complexity is O(m + n) time and O(1) extra memory, because we only relink existing nodes. For stability on equal values, take the node from the first list.

Question 27

There is a stream of 10^7 latency values and you need the 100 largest. What structure do you use, what is the complexity, and why is it better than a full sort?

Accepted Answer

Keep a min-heap of size k = 100 with the largest values seen so far. The root is the smallest of them, which is the entry threshold. A new element larger than the root replaces it and sifts down in O(log k), while a smaller one is discarded in O(1). Overall it is O(n log k) time and O(k) memory, while a full sort is O(n log n) and needs all the data in memory. For a stream this is the only acceptable option, because millions of values do not need to be stored. JavaScript has no built-in priority queue, so you write the heap yourself or use a library.

Question 28

How do you implement an LRU cache with get and set in O(1) that evicts the entry that was accessed the longest ago? Which data structure would you use?

Accepted Answer

You need a hash table to reach an entry by key and an ordering by recency of use to find the oldest quickly. The classic scheme is a hash table plus a doubly linked list: on get the node moves to the head, and on overflow the tail is removed. In JavaScript a Map keeps insertion order, so it provides all of this by itself: on get the key is deleted and inserted again, which makes it the newest, and the oldest is the first key of the iterator. All operations are O(1) on average. For a multi-process service such an in-memory cache is local, so Redis usually sits next to it.

Question 29

Given an array of numbers and a target number, how do you find the indices of two different elements whose sum equals the target? Describe the approach and complexity, and compare with a sorting-based variant.

Accepted Answer

Go through the array once and keep a Map from value to index for the elements already seen. For the current number x, look up the value target minus x in the Map: if it is there, return the pair of indices, otherwise add x to the Map. This is O(n) time and O(n) memory. The variant with sorting and two pointers is O(n log n) time and O(1) extra memory, but sorting loses the original indices, so they must be saved separately. Duplicates and using the same number twice are handled by the order: check the Map first, then add.

Question 30

How do you find the length of the longest substring without repeating characters? Describe an O(n) approach and the edge cases.

Accepted Answer

This is a sliding window problem. Keep a Map with the last index of each character and the left edge of the window. The right edge moves through the string on every step: if the character was seen before and its last index is not to the left of the left edge, move the left edge right after it. After each step update the maximum length as right minus left plus one. Both edges only move forward, so it is O(n) time, and memory is O(k) by alphabet size. Edge cases: an empty string, all characters the same, all different.

Algorithms interview questions and answers

Junior questions

1. What is the complexity of common operations: array access by index, push to the end, shift from the front, includes, Map get, sorting? Explain why they differ.

2. What does O(n) mean and why do we need Big O notation at all? Why do we drop constants?

3. How does an array differ from a linked list? When would you pick one or the other?

4. How does binary search work, what is its complexity, and what must be true about the data?

5. How does a stack differ from a queue? Give one programming example of each.

6. How does a hash table (for example, a Map) work and what is a collision? Why is lookup O(1) only on average?

7. What does a recursive function consist of? What happens if you forget the base case, and what can replace recursion?

8. How does time complexity differ from space complexity? Give an example where we trade one for the other.

9. What is the two pointers technique? Explain how to use it to check whether a sorted array contains a pair with a given sum.

10. What is a stable sort and why might it matter? What is the complexity of the built-in sort in JavaScript?

11. How do you remove duplicates from an array and what is the complexity of the simplest ways? Why is a Set better here than nested loops?

12. What is the complexity of a single loop, two nested loops over the same array, and a loop where the variable doubles each time? How do you estimate it quickly?

13. How do you find the first non-repeating character in a string? Describe the approach and the complexity.

14. How do you reverse a linked list? Describe the iterative approach and the complexity.

15. Array a has length m + n: the first m elements are sorted and the rest are zeros as spare space. Array b with n elements is also sorted. How do you merge b into a in place so that a becomes sorted?

Middle questions

1. Why is arr.push() considered O(1) even though the array is sometimes copied entirely? Explain amortized complexity for push and for Map growth. When does this amortization hurt in production?

2. Name the complexity in V8 and explain where the trap is: arr.includes(x), arr.indexOf(x), arr.pop(), arr.shift(), arr.unshift(x), arr.slice(), arr.splice(i, 1), [...arr], arr.sort(), map.get(k), set.has(k), str += 'x' in a loop.

3. When should you use a Map for a dictionary in Node.js and when a plain object? What breaks if you count word frequencies from user input in {}?

4. What conditions does binary search need? Can you look up a record by id in an array sorted by created_at? And when does binary search on an in-memory array lose to a Map or a database index?

5. Compare merge sort and quick sort: average and worst-case complexity, memory, stability. What does V8 use and why?

6. Where do linked lists show up in a real Node.js backend, given that JS has arrays? Why is a list of objects in JS often slower than an array even though insertion in the middle is O(1)?

7. Why does BFS give the shortest path only in an unweighted graph? What do you use when edges have weights, for example latency between services, and what if the weights are only 0 and 1?

8. How do you tell that a problem can be solved with dynamic programming? When do you pick top-down memoization and when a bottom-up table? When is recursion appropriate in Node at all?

9. What is a Bloom filter and where is it useful on the backend? And briefly: how does token bucket work as an algorithm, what is its memory and complexity?

10. BFS over a graph of 10^5 vertices with an array and shift() takes seconds. Why? Describe a queue with O(1) add and take, and explain how it frees memory.

11. How do you merge two sorted linked lists into one sorted list without creating new nodes? Describe the approach and the complexity.

12. There is a stream of 10^7 latency values and you need the 100 largest. What structure do you use, what is the complexity, and why is it better than a full sort?

13. How do you implement an LRU cache with get and set in O(1) that evicts the entry that was accessed the longest ago? Which data structure would you use?

14. Given an array of numbers and a target number, how do you find the indices of two different elements whose sum equals the target? Describe the approach and complexity, and compare with a sorting-based variant.

15. How do you find the length of the longest substring without repeating characters? Describe an O(n) approach and the edge cases.

16. A worker processes batches from a queue one after another. A batch of size b at a speed of r units per hour takes ceil(b / r) hours. How do you find the minimum integer speed r to process all batches within a given number of hours?

17. You need to sort 10 million user records by age (an integer from 0 to 150), keeping the order among equal ages. Can you do better than O(n log n)?

18. How do you traverse a binary tree level by level and return the values level by level? How do you find the maximum depth from this?

19. There are database migrations with dependencies: each states which ones must run before it. How do you find an execution order or detect a cycle?

20. Given coin denominations and an amount, how do you find the minimum number of coins to make the amount? Why does the greedy algorithm not work here?

Senior questions

1. Why does a sliding window work for "longest subarray with sum at most S" on positive numbers and break when the array contains negatives? What do you do then?

2. Explain why a monotonic stack gives O(n) for "next greater element" and "largest rectangle in a histogram". How do you decide whether the stack should be increasing or decreasing?

3. How do you merge k sorted lists and how do you maintain the median of a stream of numbers? Name the structures and the complexity of both.

4. You shard a cache across N Redis nodes using hash(key) % N. What happens when you add a node? How does consistent hashing fix this, and why are virtual nodes needed?

5. A recursive traversal of a category tree works in tests, but on production data it fails with RangeError: Maximum call stack size exceeded. Why, and how do you fix it?

Train these questions

Answer out loud and get graded

Other topics

Explore the platform