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 data structure and algorithm questions.
To say that developers dislike algorithm and data structure questions is an understatement. Over time, the words “algorithm” and “data structure” have become associated with useless questions you learn for a tech interview and never use again.
But many data structures are useful, and developers actually do use algorithms and data structures in the real world. For example, Uber’s mobile architecture, RIBs, uses trees for state management and UI rendering.
With countless data structures 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 data structures are and be able to work with the fundamental ones they would use on the job. While you might need to study more advanced data structures 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 data structure concepts you actually need to know.
What Are Data Structures?
Data structures are a format for storing, organizing, processing, and retrieving data. There are many different types of data structures, including arrays, stacks, queues, linked lists, and trees, to name just a few. Each structure has its own set of properties that you’ll need to master to answer a data structure interview question.
Useful Data Structure Questions
This section covers core data structure 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.
Trees
Trees store data in a structured, hierarchical, and non-linear way. While developers have critiqued the inclusion of trees in technical interviews, trees do have real-world applications that make them worth learning.
Problem: Tree Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space.
For example:
1
\
2
\
5
/ \
3 6
\
4
For the above tree, the level order traversal is 1– > 2– > 5– > 3– > 6– > 4.
Input Format
You are given a function, void levelOrder(Node * root) { }
Constraints
1 <= Nodes in the tree <= 500
HashMaps
A HashMap uses hashing functions to map keys to associated values. Hash maps are useful for “efficient retrieval of key-value pairs.”
Problem: Count Triplets
You are given an array and you need to find the number of triplets of indices (i, j, k) such that the elements at those indices are in geometric progression for a given common ratio r and i < j < k.
Example
arr = [1, 4, 16, 64] r = 4
There are [1, 4, 16] and [4, 16, 64] at indices (0, 1, 2) and (1, 2, 3). Return 2.
Function Description
Complete the countTriplets function in the editor.
countTriplets has the following parameter(s):
- int arr[n]: an array of integers
- int r: the common ratio
HashTables
A HashTable is a lookup table that stores “non-contiguous keys.” HashTables are nearly equivalent to HashMaps, with one key distinction. While a HashMap allows one null key and multiple null values, a HashTable has no null keys or values.
Problem: Ransom Note
Harold is a kidnapper who wrote a ransom note, but now he is worried it will be traced back to him through his handwriting. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use only whole words available in the magazine. He cannot use substrings or concatenation to create the words he needs.
Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine. Otherwise, print No.
Example
magazine = “attack at dawn” note = “Attack at dawn”
The magazine has all the right words, but the cases don’t match. The answer is No.
Function Description
Complete the checkMagazine function in the editor. It must print Yes if the note can be formed using the magazine, or No if it cannot be.
checkMagazine has the following parameters:
- string magazine[m]: the words in the magazine
- string note[n]: the words in the ransom note
Prints
- string: either Yes or No, no return value is expected
Input Format
The first line contains two space-separated integers, m and n, the numbers of words in the magazine and the note, respectively.
The second line contains m space-separated strings, each magazine[i].
The third line contains n space-separated strings, each note[i].
Constraints
- 1 <= m, n <= 30,000
- 1 <= lengths_of_magazine[i]_and_note[i] <= 5
Each word consists of English alphabetic letters (a to z and A to Z).
Queues
Queues are a linear data structure that performs operations in First in First Out (FIFO) order. Applications for queues include:
- Resource sharing
- Asynchronous data transfers
- Device buffering
- First-come-first-serve (FCFC) scheduling
- Router and switch queueing
Problem: Down to Zero II
You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations on N in each move:
1: If we take 2 integers a and b where N = a x b (a ≠ 1, b ≠ 1), , then we can change N = max (a,b)
2: Decrease the value of N by 1.
Determine the minimum number of moves required to reduce the value of N to 0.
Input Format
The first line contains the integer Q.
The next Q lines each contain an integer, N.
Constraints
- 1 <= Q <= 103
- 0 <= N <= 106
Stacks
Stacks are a linear data structure that performs operations in Last-in-First-Out (LIFO) order. Because their removal order is reversed, you can think of stacks as the inverse of queues. Applications for stacks include:
- Reversing strings and data structures
- HTML and XML tag matching
- Text undo functions
- Function calls
Problem: Largest Rectangle
Real estate developers are planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.
There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by h[i] where i ∈ [1, n]. If you join k adjacent buildings, they will form a solid rectangle of area k x min(h[i], h[i+1],…,h[i + k – 1]).
Example
h = [3, 2, 1]
A rectangle of height h = 2 and length k = 3 can be constructed within the boundaries. The area formed is h x k = 2 x 3 = 6.
Function Description
Complete the function largestRectangle in the editor below. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.
largestRectangle has the following parameter(s):
- int h[n]: the building heights
Returns
– long: the area of the largest rectangle that can be formed within the bounds of consecutive buildings
Resources for Interview Preparation
Data Structure Coding Questions
Tech Interview Prep: How To Ace Your Interview
Data Structures & Algorithms I Used Working at Tech Companies