Search “are coding interviews broken” on YouTube and you’ll find countless videos by developers and hiring managers with passionate opinions on the subject. But if you take a closer look at developer critiques about coding interviews, you’ll find that the subject of their frustration isn’t the interviews themselves. The source of their frustration actually stems from algorithm and data structure questions.
To say that developers dislike algorithm and data structure questions is an understatement. Over time, the word “algorithm” has become associated with useless questions you learn for a tech interview and never use again.
But many algorithms are useful, and developers actually do use algorithms and data structures in the real world. For example, Google Search, the most popular website in the world, has been described as an algorithm of algorithms. As tech and artificial intelligence drive the next evolution of humanity, engineers and scientists are beginning to decode the algorithms behind human anatomy.
With countless algorithms available to learn, it can be hard for developers to know which ones are actually useful on the job. The Pragmatic Programmer offers a helpful guideline on what concepts are worth learning. Developers should know what algorithms are and be able to work with the fundamental ones they would use on the job. While you might need to study more advanced algorithms to pass a tech interview, having these concepts mastered isn’t necessary to succeeding in a real-world setting.
With that in mind, the rest of this blog covers the core algorithm concepts you actually need to know.
What Are Algorithms?
An algorithm is a set of well-defined instructions for solving a problem. A key distinction is that an algorithm isn’t a solution. It’s a process for obtaining a solution.
There are dozens of types of algorithms, including searching, hashing, sorting, and brute force, to name just a few. To answer an algorithm interview question, you’ll need to master the underlying properties behind the algorithmic concept.
Useful Algorithm Questions
This section covers core algorithmic concepts that a developer can expect to use in practical applications throughout their career. Each concept also includes a practice question that can be solved in an integrated development environment (IDE). You can access the sample inputs, sample outputs, and base code by clicking Solve Problem at the end of every prompt.
Greedy Algorithms
A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step to find the global or overall optimal solution to the entire problem. This makes them an efficient problem-solving algorithm for some mathematical challenges.
However, a greedy algorithm isn’t always the right problem-solving approach. In some cases, it can create an inaccurate or suboptimal solution. Occasionally, the largest sum or most optimal path is hiding on a path that at first appears small or suboptimal.
Problem: Cutting Boards
Alice gives Bob a board composed of 1×1 wooden squares and asks him to find the minimum cost of breaking the board back down into its individual squares. To break the board down, Bob must make cuts along its horizontal and vertical lines.
To reduce the board to squares, Bob makes horizontal and vertical cuts across the entire board. Each cut has a given cost, cost_y[i] or cost_x[j] for each cut along a row or column across one board, so the cost of a cut must be multiplied by the number of segments it crosses. The cost of cutting the whole board down into 1×1 squares is the sum of the costs of each successive cut.
Can you help Bob find the minimum cost? The number may be large, so print the value modulo 10^9 + 7.
For example, you start with a 2×2 board. There are two cuts to be made at a cost of cost_y[1] = 3 for the horizontal and cost_x[1] = 1 for the vertical. Your first cut is across 1 piece, the whole board. You choose to make the horizontal cut between rows 1 and 2 for a cost of 1 x 3 = 3. The second cuts are vertical through the two smaller boards created in step 1 between columns 1 and 2. Their cost is 2 x 1 = 2. The total cost is 3 + 2 = 5 and 5%(109 + 7) = 5.
Dynamic Programming
Technically, dynamic programming is not a type of algorithm. Rather, it’s an algorithmic technique that developers use to reduce algorithm runtime and solve optimization problems. Dynamic programming is often compared to greedy algorithms because you can use them to solve similar types of problems. Dynamic programming is most useful for problems where greedy algorithms yield an inaccurate or suboptimal solution.
Dynamic programming is able to outperform greedy algorithms because it breaks down decisions into components and solves for the overall optimal solution. The drawback, however, is that dynamic programming can be challenging, compared to the easier greedy algorithms.
Real-world use cases for dynamic programming include:
- Artificial intelligence
- Machine learning
- Computer networks
- Computer vision
Problem: Billboards
ADZEN is a popular advertising firm in your city that owns all n billboard locations on Main Street. The city council passed a new zoning ordinance mandating that no more than k consecutive billboards may be up at any given time. For example, if there are n = 3 billboards on Main street and k = 1, ADZEN must remove either the middle billboard, the first two billboards, the last two billboards, or the first and last billboard.
Being a for-profit company, ADZEN wants to lose as little advertising revenue as possible when removing the billboards. They want to comply with the new ordinance in such a way that the remaining billboards maximize their total revenues (i.e., the sum of revenues generated by the billboards left standing on Main street).
Given n, k, and the revenue of each of the n billboards, find and print the maximum profit that ADZEN can earn while complying with the zoning ordinance. Assume that Main street is a straight, contiguous block of n billboards that can be removed but cannot be reordered in any way.
For example, if there are n = 7 billboards, and k = 3 is the maximum number of consecutive billboards that can be active, with revenues = [5, 6, 4, 2, 10, 8, 4], then the maximum revenue that can be generated is 37: 5 + 6 + 4 + 2 + 10 + 8 + 4.
Function Description
Complete the billboards function in the editor below. It should return an integer that represents the maximum revenue that can be generated under the rules.
billboards has the following parameter(s):
- k: an integer that represents the longest contiguous group of billboards allowed
- revenue: an integer array where each element represents the revenue potential for a billboard at that index
Input Format
The first line contains two space-separated integers, n (the number of billboards) and k (the maximum number of billboards that can stand together on any part of the road).
Each line i of the n subsequent lines contains an integer denoting the revenue value of billboard i (where 0 <= i <= n).
Constraints
- 1 <= n <= 105
- 1 <= k <= n
- 0 <= revenue value of any billboard <= 2 * 109
Output Format
Print a single integer denoting the maximum profit ADZEN can earn from Main street after complying with the city’s ordinance.
Search Algorithms
A search algorithm is an algorithm that solves a search problem by locating specific data within a larger dataset. Solving a search problem requires identifying the correct type of search algorithm to use. These include:
- Linear: checks every record in a linear fashion
- Binary: repeatedly divides the search space in half
- Hashing: uses a hash function to map keys to records
- Breadth-first: starts at tree root and searches all entries before changing depth
- Depth-first: explores a branch at all depths before changing to a different branch
The main factors used to evaluate a search algorithm are ranking quality and result accuracy. Solution speed and efficiency are a second priority.
Problem: Bike Racers
There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers want to participate in a race, but unfortunately the race can only accept K bikers. Jack is organizing the HackerRace and wants to start the race as soon as possible. He can instruct any biker to move towards any bike in the city. In order to minimize the time to start the race, Jack instructs the bikers in such a way that the first K bikes are acquired in the minimum time.
Every biker moves with a unit speed and one bike can be acquired by only one biker. A biker can proceed in any direction. Measure the distance between bikes and bikers as Euclidean distance.
Jack would like to know the square of required time to start the race as soon as possible.
Resources for Interview Preparation
Tech Interview Prep: How To Ace Your Interview
Data Structures & Algorithms I Used Working at Tech Companies