Me Solving Top Coding Interview Questions – Arrays (10 Solved in 45 minutes!)
5. Array cheat sheet
You can download the cheat sheet here.
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 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.
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.
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.
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.
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.
2. Medium array interview questions
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.
