To ace your coding interview for a software engineering job, you’ll need to understand arrays. They come up frequently in coding interviews and are fundamental to many other data structures too.
Let’s take a look at some array questions that come up in interviews.
6 typical array interview questions
- Given a sorted array, return the index of a given value, or -1 if the element cannot be found.
- What is the time complexity required to find if an array of sorted integers contains a given integer?
- Given an array with all integers between 1 and 100 except for one, find the missing number.
- Given a 2D array of integers, rotate clockwise without using additional memory.
- If you have two sorted arrays, how can you merge them and keep the resulting array sorted?
- Given unlimited coins in denominations of 1c, 2c, and 5c, how many different ways can you make a total of 20c? Can you solve the general version of this problem for an arbitrary target amount and a given list of denominations?
Below, we take a look at some more questions and provide you with links to high quality solutions to them. We explain how arrays work, their variations, and the most important things you need to know about them, including a useful 'cheat sheet' to remind you of the key points at a glance.
This is an overview of what we’ll cover:
- Easy array interview questions
- Medium array interview questions
- Hard array interview questions
- Array basics
- Array cheat sheet
- Mock interviews for software engineers
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of arrays.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solutions, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high-quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the ‘phone screen’ stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
1.1 Merge two sorted arrays
1.2 Remove duplicates from an array
- Video guide (Kevin Naughton Jr.)
- Text guide (W3Schools)
- Text guide (Javarevisted)
- Code example (LeetCode)
1.3 Count the frequency of an element in an array
1.4 Two sum
1.5 Find the minimum (or maximum) element of an array
1.6 Remove duplicates from sorted array
1.7 Remove element in-place
1.8 Search Insert Position
1.9 Maximum Subarray
1.10 Plus One
1.11 Convert Sorted Array to Binary Search Tree (Arrays/Binary Trees)
1.12 Single Number
1.13 Count Primes
1.14 Contains Duplicate
1.15 Third Largest Number
1.16 Count Odd Even
Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
2.1 Move all zeros to the beginning/end of an array
2.2 Find if a given element is in a sorted array (binary search)
2.3 Rotate an array
2.4 Largest sum of non-adjacent numbers (Dynamic Programming)
2.5 A Product Array Puzzle
2.6 Maximum Product Subarray (Dynamic programming)
2.7 Shortest Unsorted Continuous Subarray
2.8 Maximum sum of hour glass in matrix
2.9 Paint House (Dynamic programming)
2.10 Minimum number of jumps to reach end
2.11 Find duplicates in O(n) time and O(1) extra space
2.12 Find three numbers with the maximum product
2.13 Maximum Sum Circular Subarray
2.14 Minimum number of swaps to sort an array
Similar to the moderate section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
3.1 Rotate a 2D array
3.2 Create change with coins (dynamic programming)
3.3 Sliding window maximum
3.4 Find the smallest positive number missing from an unsorted array
3.5 Find the missing number in unordered Arithmetic Progression
- Text guide (GeeksForGeeks)
3.6 Find the maximum j – i such that arr[j] > arr[i] (Distance maximising problem)
3.7 Array manipulation
3.8 Median of Two Sorted Arrays
3.9 Sudoku Solver
3.10 Largest Rectangle in Histogram
3.11 Maximal Rectangle in binary matrix
3.12 Find Minimum in Rotated Sorted Array
3.13 Count of Smaller Numbers After Self
3.14 Palindrome Pairs
3.15 Sort an array containing 0’s, 1’s and 2’s
- Text guide (Techie Delight)
- Text guide (GeeksForGeeks)
- Video guide (Take u Forward)
- Video guide (Back To Back SWE)
3.16 Longest increasing subsequence
3.17 Trapping Rain Water
In order to crack the questions above and others like them, you’ll need to have a strong understanding of arrays, how they work, and when to use them. Let’s get into it.
4.1 What is an array?
An array is a list-like data structure that contains a collection of values, each associated with a specific index, usually with a fixed overall size. For example, the image below shows an array that has space for up to nine elements, but contains only four. This array has the integers 1, 2, 3, and 4 as its values and these are at the “zeroth”, first, second, and third indices respectively.
Arrays are one of the most fundamental data structures in programming and computer science, and many more complex data structures are built using arrays. The array itself is not always as simple as it might seem, and it forms the basis for many tricky interview questions.
4.1.1 Types of arrays (Java, Python, C++)
Interviewers often ask questions about “arrays”, as if it cleanly refers to a single concept. In reality, there are different types of arrays, and different languages implement arrays in different ways, leading to some confusion and complexity. Mainstream programming languages offer a default built-in array implementation (e.g. `list` in Python, or `int ` in Java and C++), and usually offer alternative implementations that the user can import from a standard library.
In many languages, including Java, default arrays are static and homogenous. Static means that the size of the array (the number of elements that it can hold) has to be declared upfront, when the array is created. Homogenous means that all of the elements in the array must be of the same type - e.g. an array of integers cannot contain string or float elements.
In other languages, including Python, the default array (`list`) is dynamic and heterogeneous. This means that they can be resized dynamically at run time, and can contain a mix of different types.
You will also often encounter nested or multidimensional arrays (often called a matrix). For 2D arrays, you can usually think of these as tables with rows and columns.
Because array terminology and implementation differs across languages, it’s always a good idea to check your assumptions about a specific array question with your interviewer.
4.1.2 How arrays store data
As with strings, data stored in arrays is traditionally kept in the heap of computer memory. If you store a basic integer in a variable with a statement like `int x = 1;`, that value is stored on the stack. To answer many array-related interview questions, you should understand the fundamentals of stack vs heap.
Data in the heap has to be cleared manually in languages like C, or by the garbage collector in languages such as Java. You should be prepared to answer questions about the implications of this (for example, how it could lead to a memory leak).
Because arrays need to store data in contiguous blocks of memory, the programmer often needs to be aware of tradeoffs around space and time when it comes to using arrays.
- If you don’t reserve enough space in your array, you waste time as you have to allocate a new array.
- If you reserve too much space, this is a waste of resources and could impact the requirements of your program, or other running programs.
Adding even a single element to a ‘full’ array is an expensive operation. A new (bigger) array has to be allocated, and every single element has to be copied across. Only then can the new element be added.
A common approach that languages use for dynamic arrays is to double their allocated size every time they become full. So if you need to add an 11th item to an array of size 10, the library will create a new array of size 20 and copy across the existing data.
This means that as you are adding elements to an array, most inserts will be fast, but your code will slow down significantly every time it triggers a resize.
4.1.3 How arrays compare to other data structures
Because strings are usually implemented as arrays of characters, many interview questions for arrays can be phrased as string interview questions, and vice-versa.
Arrays are also closely related to linked lists, and many questions will expect you to be able to explain the differences between them, and when one has an advantage over the other.
Finally, arrays are often contrasted with sets. When you want to get data at a specific index (e.g. “I need the fifth element in this list”), arrays perform better than sets, as you can access any given element by its index in O(1) time.
If you need to check if a specific value is contained in the array (“Does my array contain the value 5 at any position?”), arrays are not efficient. You need to loop through every single value to see if it matches what you are looking for, while sets can provide this in O(1) time.
Need a boost in your career as a software engineer?
If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.
You can download the cheat sheet here.
5.1 Related algorithms and techniques
- Binary search
- Dynamic Programming
- Converting to a Set
- Sliding window
- Two pointers
- Prefix sum
5.2 Related concepts
- Homogeneous (elements have same type)
- Dynamic (size can change)
5.3 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity (the processing time for the various array operations) and space complexity (the amount of memory required). While you might be asked about these directly in relation to the array data structure, it’s more likely that you will need to know these in relation to specific array-related algorithms, such as searching and sorting, which is what the third section details.
For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.
5.3.1 Time complexity
For time complexity, some of the results are fairly intuitive. For example, accessing any element of an array is always O(1) as arrays are stored in contiguous memory, so accessing the 100th element is no harder than accessing the first one, and this is true for updating any specific element too.
Deleting or inserting an element can require us to touch every single other element in some cases, so this is O(n) in the worst case. For example, if we have an array of size 10 and we want to add an 11th element, we need to copy each element to a new array first, and then add the new one. However, this is rare, as we would usually double the size of the array every time we run out of space, making future inserts faster. Thus the amortized complexity is still constant as we can ‘pay off’ the expensive operation over time.
The time complexity is similar when searching for an element by value, where in the worst case we need to look at every single element before finding our target, but if we ‘get lucky’ we might find it in the first place we look (probably at the start of the array), so our best case is O(1).
5.3.2 Space complexity
In most cases, the space complexity of an array is simply the number of elements, so this is O(n). In some contexts, the array might be some (small) constant size, which means the space complexity is simplified to O(1). Space complexity is almost always only relevant in the context of a specific algorithm, which we cover in the next section.
5.3.3 Array algorithms complexity
We’ve listed the algorithms that interviewers will most frequently discuss while asking about arrays, but there are dozens of other search algorithms and sorting algorithms. One of the most important aspects to understand is the tradeoff between mergesort and quicksort. Quicksort works in place, so does not require additional memory, while Mergesort uses an auxiliary array, and therefore uses more space. On the flip side, the worst time complexity of mergesort is better than that of quicksort which can in some cases (e.g. when the array is already sorted) perform as badly as a naive bubble sort.
For the search algorithms, a key insight to understand is that binary search is log(n) as we can eliminate half of the array with each operation. Therefore doubling the size of the array requires only one more operation. By contrast, a linear search looks at every element until it finds the target, so doubling the size of the array also requires, on average, twice as many operations.
For example, searching an element using binary search in an array of one million elements needs a maximum of 20 comparisons. Doubling the array (two million elements) would only add one extra comparison (a total of 21 comparisons). By contrast, a linear search would need one million comparisons and doubling the array would also double the number of comparisons (to two million).
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only linked lists but also the rest of the relevant data structures. Check out our guides for questions, explanations and helpful cheat sheets.
- Linked lists
- Stacks and Queues
- Coding interview examples (with solutions)
Once you’re confident on all the topics, you’ll want to start practicing answering coding questions in an interview situation.
One way of doing this is by practicing out loud, which is a very underrated way of preparing. However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice system design interviews 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.
Further reading: Best interview coaching services 2023