Search Algorithm Interview Questions: A Comprehensive Guide

Submit an interview question

Questions and answers sent in will be looked over and edited by Toptal, LLC, and may or may not be posted, at their sole discretion.

Toptal sourced essential questions that the best algorithm developers can answer. Driven from our community, we encourage experts to submit questions and offer feedback.

What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used?.

Divide and Conquer algorithms are a paradigm for solving problems that involve several basic steps. First, we divide the problem into smaller pieces and work to solve each of them independently. Once all the parts have been solved, we take all the smaller solutions that were found and put them together into a single, complete solution.

This process can be repeated, which means that each “sub problem” can be broken down into even smaller parts if needed. This process of dividing the problem over and over again is done until each problem is small enough that it’s not hard to solve.

Some common examples of problems that lend themselves well to this approach are binary search, sorting algorithms (e. g. , Merge Sort, Quicksort), optimization of computationally complex mathematical operations (Exponentiation, FFT, Strassen’s algorithm), and others. 2 .

How would you find the best way to calculate p^k, where k is a positive integer? How hard is the answer?

First, let’s mention that the trivial solution has the complexity of O(k). The problem can be solved by squaring and multiplying.

We know that p^k = p^x * p^y if x+y=k. We also know that p^k = (p^a)^b if a*b=k.

If k is an even number, setting a = 2 and b = k/2 will make p^k = (p^2)^(k/2). This will cut the number of multiplications needed by almost half. If k is an odd number, setting x = 1 and y = k-1 will make y even, and then we can do the same thing we did for the even number. This allows us to define a recursive function:

This solution results in a complexity of O(log k). 3 .

How do Insertion sort, Heapsort, Quicksort, and Merge sort work?

Insertion sort takes elements from the array one at a time and keeps a sorted subarray to the left of where the current point is. This is done by finding an element’s correct place in the sorted array and moving all the elements that come after it by one, leaving a space for the element to be added.

Heapsort starts by building a max heap. A binary max heap is a nearly full binary tree where each parent node is bigger or the same size as its children. The heap is stored in the same memory in which the original array elements are. Once the heap is formed, it completely replaces the array. Then we remove the first element, restore the heap property, and cut the size of the heap by 1. Finally, we put the max element at the end of that memory. This is done over and over until the heap is empty. The smallest element is at the top, and the elements that come after it get bigger.

Quicksort is performed by taking the first (leftmost) element of the array as a pivot point. We then compare it to each following element. When we find one that is smaller, we move it to the left. To move quickly, that element is swapped with the first element after the pivot point, and then the pivot point is swapped with the element after it. After going through the whole array, we call quicksort on the subarray of points to the left of the pivot and then on the subarray of points to the right of the pivot. The recursion is performed until we reach subarrays of 0-1 elements in length.

Merge sort recursively halves the given array. Once the subarrays reach trivial length, merging begins. When two subarrays are joined together, merging takes the smallest element between them and does it again and again until all the elements are taken. This makes a sorted subarray. The process is repeated on pairs of adjacent subarrays until we arrive at the starting array, but sorted.

Check out the visualization of these sorting algorithms here: www.sorting-algorithms.com

Apply to Join Toptals Development Network

and enjoy reliable, steady, remote Freelance Algorithm Developer Jobs

What are the best things about Insertion Sort, Quicksort, Heapsort, and Mergesort? Talk about the best, average, and worst cases for time and memory usage.

Insertion sort has an average and worst runtime of O(n^2), and a best runtime of O(n). It doesn’t need any extra buffer, so space complexity is O(1). It is efficient at sorting extremely short arrays due to a very low constant factor in its complexity. It is also extremely good at sorting arrays that are already “almost” sorted. A common use is for re-sorting arrays that have had some small updates to their elements.

The other three algorithms have a best and average runtime complexity of O(n log n). Even in the worst cases, Heapsort and Mergesort keep their complexity. Quicksort, on the other hand, has worst case performance of O(n^2).

Quicksort is sensitive to the data provided. Without usage of random pivots, it uses O(n^2) time for sorting a full sorted array. But by swapping random unsorted elements with the first element and then sorting, the algorithm is less affected by data that would normally make it act in the worst way (e.g. g. already sorted arrays). It is not simpler than Heapsort or Merge sort, but it has a very low constant factor that affects how fast it runs. This usually gives it an edge when working with a lot of random data.

Heapsort has reliable time complexity and doesn’t require any extra buffer space. That’s why it’s useful for software that needs reliable speed over optimal average runtime and/or doesn’t have a lot of memory to work with the data. Thus, systems with real time requirements and memory constraints benefit the most from this algorithm.

Heapsort has a much bigger constant factor than merge sort. However, to store intermediate data, merge sort needs O(n) buffer space, which is very expensive. Its main selling point is that it is stable, as compared to Heapsort which isn’t. In addition, its implementation is very parallelizable. 5 .

Why is a Hash Table useful? What are its best and worst case times for each operation? How can we use this structure to look through a dictionary and find all the anagrams?

A Hash Table is a data structure for mapping values to keys of arbitrary type. The Hash Table consists of a sequentially enumerated array of buckets of a certain length. A hash function, which gives back an integer number (the index of a bucket) for any given key, is used to assign each key to a bucket. Since the same bucket can have more than one key, all the (key, value) pairs are kept in lists inside their own buckets.

Choosing the right hashing function can have a great impact on performance. If we use a good hash function on the dataset we want to store, hashes with different keys will not happen very often. The worst case time complexity for accessing, adding, and deleting is O(N), where N is the number of elements in the hash table. In practice, the average time complexity is O(1).

We only need to group words with the same set of letters in a dictionary to find all the anagrams. So, if we turn words into strings that show how their letters are sorted, we can use that to group words into lists and use the strings as a key.

The hash table stores lists mapped to strings. At the right key, we add each word to the list or make a new list and add it to that one. In general, this algorithm takes O(N L log L) time to run on a dictionary of N words that are all less than or equal to L in length. 6 .

A numeric array of length N is given. We need to come up with a way to find all the positive numbers in the array that also have their opposites. Describe approaches for solving optimal worst case and optimal average case performance, respectively.

Let us first design an approach with optimal worst case time.

We need to compare numbers to see if they have their opposites in the array. The trivial solution of comparing all numbers has a consistent time of O(N^2). Because there are so many comparisons, we should try to find a total order operator that lets us use sorting to solve the problem. If we set up a comparison operator that puts all instances of a number right after all instances of its opposite, for every number in the array that has an opposite, we would have exactly two instances of the opposite number right after each other.

An example of what we want to achieve:

After our special sorting method, we can see that the combinations [-2, 2], [-3, 3], and [-7, 7] happen one after the other exactly once. Implementing this comparison is simple and it can be implemented as follows.

We put the numbers in order by their absolute value if they are not equal or opposite. If they are, we put them in order by their sign. Finally, a solution based on this is now very simple:

In the worst case, this implementation takes O(N log N) time to run, and the sorting algorithm is the slowest part.

Optimal average case time complexity of O(N) can be achieved using Hash Tables. We map numbers to their absolute values, and check if their opposites are already in the Hash Table.

So that we don’t give you the same results twice, we change the value in the table to something that will never be equal to any of the numbers in the array.

The average time complexity of all HashTable operations is O(1). Our complexity comes from doing operations N times. 7 .

How would you describe dynamic programming in a general way? For example, how would you use this to find the length of the longest common subsequence of pieces in two arrays?

Dynamic programming is a paradigm for solving optimization problems. It involves finding answers to smaller problems that can be saved and used again to solve the main problem. The best way to solve hard problems that become easy once we know how to solve a slightly easier version of the problem (the intermediate subproblem) is to use dynamic programming. Dynamic programming solutions are best represented by a recursive relation, and easily implemented.

If the intermediate subproblems are not overlapping, then we have just a case of Divide and Conquer.

Finding the longest common subsequence (LCS) between two arrays is a classical example of using dynamic programming. Let the arrays have lengths M and N, and stored as variables a[0:M] and b[0:N]. Let’s use L[p, q] to show how long the LCS is for subarrays a[0:p] and b[0:q]. This means that L[p, q] == LCS(a[0:p], b[0:q]). Also, let’s picture what a matrix L[p, q] would look like for a pair of “bananas” and “sandals.”

If p or q is zero, then L[p, q] = 0 since we have one empty subarray. All the other fields are linked by a simple rule: L[p, q] is equal to the highest value of the following pairs:

• The LCS didn’t change; we just added one letter to array a to get L[p, q].
• L[p, q – 1] – analogous for array b
• Adding the same letter to both a and b, which can’t happen in every field (L[p – 1, q – 1] 1)

When you look at the table again, you can see that numbers are always equal to the highest number of their upper or left neighbor, unless the values in that field are equal. In that case, the highest number is raised by 1. So a solution to the problem is given with the following algorithm.

The time complexity of this solution is O(MxN) 8 .

Develop a program that can figure out how many ways there are to move N meters by jumping 1, 2, 3, 4, or 5 meters. Assume that N can be a very large number. What is the resulting complexity?.

We can use dynamic programming for solving this problem. Let’s use n[k] to represent the number of ways we can reach distance k. That distance can be reached by jumping from one of the 5 previous distances. That is, the number of ways to get to this distance is equal to the sum of the ways to get to the first five distances:

n[k] = n[k-1] + n[k-2] + n[k-3] + n[k-4] + n[k-5]

The solution is a simple for loop.

This solution has a time complexity of O(N). But, we can have even better performance. The given number can be shown as a 1×5 matrix of ones multiplied by a 5×1 matrix of elements that came before. When we shift in the same way, we get the relationship B[k] = A * B[k-1], which says:

If B[0] = [0 0 0 0 1]’, then [0 0 0 0 1] * B[k] = n[k]. Now, due to B[k] = A * B[k-1], B[k] = A^T * B[0]. This means that the answer to our problem can be shown as the relation n[N] = [0 0 0 0 1] * A^N * [0 0 0 0 1]. If we use the best method we talked about before to figure out pow(A, N), this answer takes O(log N) time. As we go along, we should remember that this is very hard to make because matrix multiplication takes a lot of time. But, for a large enough N, this solution is optimal. 9 .

What are Red-Black Trees and B-Trees? What is the best use case for each of them?

To find items that can be compared, you can use both Red-Black Trees and B-Trees, which are both balanced search trees. You can do things like minimum, maximum, predecessor, successor, insert, and delete on them in O(log N) time, where N is the number of elements. In this way, they can be used to make a map, a priority queue, or a database index, among other things.

Red-Black Trees are an improvement upon Binary Search Trees. The named operations in Binary Search Trees are done by binary trees, but the depth of the tree is not controlled. This means that operations can take a lot longer than expected. All nodes in a red-black tree are marked as either red or black, and rules are set for how certain positions between nodes should be handled. To keep things simple, this method makes sure that the longest branch isn’t twice as long as the shortest branch. This means that each branch is less than 2*log_base2(N).

This is the ideal structure for implementing ordered maps and priority queues. Most binary trees split into two branches, but B-Trees split into K-2K branches (for a given number K). Other than that, they behave pretty similarly to a binary search tree. This is helpful because it cuts down on access operations, which is especially helpful when data is stored on secondary storage or in a different location. For this reason, we can ask for more data at once, and when we’re done with one request, our next one is ready to be handled. This structure is often used in implementing databases, since they have a lot of secondary storage access. 10 .

You are given a matrix of MxN boolean values that show a board with fields that are either free (True) or occupied (False). Find the size of the largest square of free fields.

A field with a True value represents a 1×1 square on its own. It’s the bottom right corner of a 2×2 square if a field has empty spaces on its left, top, and top-left. These three fields are all in the bottom right corner of a 5×5 square. If they overlap and the field in question is free, they make a 6×6 square. We can use this logic to solve this problem. What this means is that for every free field, size[x, y] = min(size[x-1, y], size[x, y-1], size[x-1, y-1]) 1. For an occupied field, we can set size[x,y] = 0, and it will fit our recursive relation perfectly. Now, size[x, y] represents the largest square for which the field is the bottom-right corner. Tracking the maximum number achieved will give us the answer to our problem.

What are the Dijkstra and Prim algorithms and how do they work? What does the Fibonacci heap have to do with them?

Dijkstra is an algorithm for finding single source shortest paths. Prim is an algorithm for finding minimum spanning trees.

Both algorithms have a similar implementation. We’ll only show you how to figure out the distance and spanning tree size, but it’s easy to figure out the shape of the answers.

In addition to the calculations for the return data, the only thing that is different is the data that is added to the heap. Dijkstra adds up the distance, but Prim only uses the branch distance. Both algorithms form a tree by taking branches with the smallest price from the MinHeap. In Dijkstra, the cheapest point is the one that is closest to the starting point. In Prim, the cheapest point is the one that is closest to its parent.

Using a normal binary heap, we can’t prevent adding duplicates. Thus, the heap can have as many item additions as there are edges in the graph. It takes O((E V) log V) time to solve if V is the number of vertices and E is the number of edges.

We will have to add all edges to the heap at some point, which is what slows things down. There can be more than one edge that points to the same vertex, so in the visited check, all but one of those edges will be thrown away. To avoid that, we can let the heap access the element directly, change the edge if it’s better, and then heapify to fix any changes to the order. This operation has the complexity of O(log V). In a Fibonacci Heap this operation has an O(1) complexity. Thus by using a Fibonacci heap this complexity can be reduced to O(E + V log V). 12 .

What is the Bellman-Ford algorithm for finding single source shortest paths? What are its main advantages over Dijkstra?

The Bellman-Ford algorithm finds the shortest paths from a single source by lowering distances over and over again until there are no more distances to lower. To relax distances, check to see if an intermediate point offers a better path than the one that is currently being used. We can see if the solution is best after a certain number of iterations, which is a little less than the number of nodes. If not, there is a cycle of negative edges that will provide better paths infinitely long.

This algorithm is better than Dijkstra because it can work with graphs that have negative edges, while Dijkstra can only work with graphs that have positive edges. It can’t handle graphs with cycles that have an overall negative path, but that just means there isn’t a end to the problems.

Let’s again just implement finding a distance, rather than the actual path that it represents:

The complexity of this algorithm is O(V * E), which is slower than Dijkstra in most cases. So this algorithm should be used only when we expect negative edges to exist. 13 .

What exactly is A*, how does it work, and what are its pros and cons when it comes to moving through graphs to reach a goal?

A* is a pathfinding algorithm that doesn’t try to find the best solutions. Instead, it just wants to find solutions quickly and without going too far into parts of the graph that aren’t important.

It does this by employing a heuristic that approximates the distance of a node from the goal node. This is most trivially explained on a graph that represents a path mesh in space. The heuristic could be the Euclidean distance from point A to point B, scaled by a certain factor. This would help us find a way to get from point A to point B.

This heuristic is employed by adding it to our distance from the start point. Beyond that, the rest of the implementation is identical to Dijkstra.

The algorithm’s main advantage is the quick average runtime. The main problem with it is that it doesn’t find the best solutions; it just finds any solution that fits the heuristic. 14 .

We are given an array of numbers. What is the best way to find the sum of a certain subarray? How could we ask for the sum of any subarray an unlimited number of times? What would be the best way to update the array between sum queries? How hard is it to prepare and ask for each solution?

For the sake of notation, let us represent the length of the array as N.

The first problem consists of calculating the sum of the array. There is no preprocessing involved and we do one summing operation of O(N) complexity.

The second problem needs to calculates sums multiple times. Thus, it would be wise to perform preprocessing to reduce the complexity of each query. Let’s replace the create an array of subsums s[0:N+1] for the array a[0:N], that is:

Now each element k stores the sum of a[0:k]. To find the sum of a subarray a[p:q], add up all the elements until q (s[q]) and take away all the elements before p (s[p]). This is written as subsum(p, q) = s[q] – s[p].

The preprocessing for this method takes O(N) time, but each query takes O(1) time to perform.

The hardest problem is responding to an arbitrary number of data updates and queries. First, let us look at the previous solutions. The first solution has O(1) insertion complexity, but O(N) query complexity. The second solution has the opposite, O(N) insertion and O(1) queries. Neither of these approaches is ideal for the general case. Ideally, we want to achieve a low complexity for both operations.

A Fenwick tree (or binary indexed tree) is ideal for this problem. We keep track of a value array tree [0:N 1], where each Nth item stores the sum (a[M:N]), and M is equal to N with the least significant 1 in its binary representation changed to 0. N = 19 = b10011, M = 18 = b10010, N = 20 = b10100, M = 16 = b10000, etc. Now we can easily calculate the sum by following M until we reach 0. Updates are done in the opposite direction.

Both operations require O(log N) complexity, which is better than either previous approach. 15 .

You need to design a scheduler that to schedule a set of tasks. A number of the tasks need to wait for some other tasks to complete prior to running themselves. What algorithm could we use to design the schedule and how would we implement it?.

What we need to do is a topological sort. We connect a graph of all the task dependencies. After that, we mark each node with the number of dependencies it has and add nodes with no dependencies to a queue. As we take nodes from that queue, we remove a dependency from all of its children. As nodes reach zero dependencies, we add them to the queue.

After the algorithm runs, we have circular dependencies if the list doesn’t have enough items for the number of tasks. Otherwise, we have a solution:

You have been given a very large static list of string keys along with information for each one. We need to set up a data structure that lets us quickly access and change that data, even in the worst situations. How can we solve this problem?.

Let’s mark the number of keys as N. The problem presented is a problem of perfect hashing. Like a normal HashTable, we do the same thing, but we store collisions in a secondary HashTable instead of a list. We choose primary hashing functions until all buckets have a relatively small number of elements in them. After that, in buckets with K keys we place hash tables with K^2 buckets. Even though this seems to result in high memory complexity, expected memory complexity is O(N). By choosing this size of HashTables we have a 50% probability to have collisions. This makes it easy to choose hashing functions that will not result in collisions. 17 .

Determine if two rectangles intersect.

• Given rectangles’ width, height, and the (x, y) coordinates of their top-left corners, come up with a way to solve this problem.
• Show another way to define rectangles based on their width, height, and the (x, y) coordinates of their centers.

What are the behaviors of your algorithms for edge cases?

• Just make sure that one rectangle isn’t completely on top, bottom, right, or left of the other:

• You find the x and y distances between the two centers and compare them to half of the sum of their width and height:

One of the only edge cases is when one of the rectangles is completely inside the other one. This is because the word “intersect” isn’t always clear about what to do in this situation. That’s because both algorithms see this as an intersection. If that’s not what’s needed, it will take some extra checks to get rid of this case. 18 .

You have a set of date intervals represented by StartDate and EndDate. How would you efficiently calculate the longest timespan covered by them?.

What will be the time complexity?

The overall time complexity is O(NlogN) because:

• Sort intervals by start date. Time complexity is O(NlogN).
• Take first interval as actual range. Repeat intervals, and if the current StartDate is in the real range, extend the EndDate of the real range if necessary and the longest time span reached so far if necessary. Otherwise, use current interval as new actual range. Time complexity is O(N).

19 .

It is up to you to figure out the best way to connect a master server to a group of N routers. In a tree structure, the routers are linked together with the bare minimum of N-1 wires, and we know the data rate at which devices (not routers) connected to each router will need data. That amount of information shows how much each router will have to do if it is not chosen to host the master. Determine which router we need to connect the master to in order to minimize congestion along individual lines.

First we form an array of connections for each router (connections variable). Finally, we make a note of how many connections we still need to handle for each router and add all routers with one connection to the queue for processing. In the tree of routers, these are the leaf nodes. We start from each leaf node and prune the tree along the way, ignoring pruned nodes. When a router doesn’t host the master server, it needs to send data to the leftover branch. This is called outbound data. Total load minus outgoing data is the data that the router will get from the branch that has extra work to do if it hosts the master server. Then, we can use a for loop to find the dead branch, add the outgoing data to its incoming data, cut off the branch, and see if the other router turns into a leaf node when it is added to the queue. At the end, we retrieve the node with minimum congestion. During the whole algorithm, the congestion variable held an array, and each item in the array showed how much work was being done on the busiest branch if that router was the server.

The algorithm runs at O(N) time complexity, which is as efficient as we can get. Pseudocode for the solution is as follows:

There is more to interviewing than tricky technical questions, so these are intended merely as a guide. Not every good candidate for the job will be able to answer all of them, and answering all of them doesn’t mean they are a good candidate. At the end of the day, hiring remains an art, a science — and a lot of work.

Tired of interviewing candidates? Not sure what to ask to get you a top hire?

Let Toptal find the best people for you.

Our Exclusive Network of Algorithm Developers

Looking to land a job as an Algorithm Developer?

Let Toptal find the right job for you.

Job Opportunities From Our Network

Top 7 Algorithms for Coding Interviews Explained SIMPLY

FAQ

What is an algorithm test in an interview?

Which sorting algorithm is most asked in interview?

What are algorithmic questions?

What is a search algorithm?

Check MLStack.Cafe – 1704 Data Science & ML Interview Questions & Answers! Search algorithms form an important part of many programs. Some searches involve looking for an entry in a database, such as looking up your record in the IRS database. Other search algorithms trawl through a virtual space, such as those hunting for the best chess moves.

What are algorithm questions?

Algorithm questions can cover a broad range of topics. Brute Force — This method requires us to go through all the possibilities to find a solution to the problem we are meaning to solve. This is often the algorithm that comes to mind first, and even though it may be the least efficient, you’re guaranteed a solution.

What are artificial intelligence search algorithms?

Explore our comprehensive guide on Artificial Intelligence Search Algorithms, featuring essential interview questions and answers to prepare you for a successful career in AI. Artificial Intelligence (AI) search algorithms are the backbone of intelligent systems, enabling them to navigate through vast solution spaces and identify optimal outcomes.

What is a binary search algorithm?

Binary search is one of the fastest search algorithms because it halves the search space with each iteration. It requires an ordered set that also has constant access times, meaning that only sorted arrays are suitable for binary search. For more questions like these, check out our list of 50 binary search questions and solutions. 5. Sorting