• ← Previous
• Next →

Arrays are a common structures that appear frequently in the interview. They are used commonly because they are simple and fundamental. Interviewers expect candidates to be familiar with arrays and their operations (traversal, search, sort, insertion, deletion, etc). Further, arrays are often used as the basis for solving more complex problems. Thus, it is good to have a solid understanding of arrays for coding interviews.

Array Problems can be solved using a lot of techniques such as:

• Two-pointer technique: Used for solving problems that require searching for pairs or triplets in an array.
• Sliding window technique: Used to solve problems that require finding the maximum or minimum of a subarray.
• Binary search: Used to search for a specific element in a sorted array.
• Hash tables: Used to store elements and check if they appear more than once in an array.
• Dynamic programming: Used to solve problems that require optimized solutions for overlapping subproblems.
• Prefix sum array: Used to find the sum of elements in a specific range in an array.
• Bit manipulation: Used to solve problems that require efficient manipulation of binary data.
• Stack: Used to solve problems that require keeping track of the order of elements in an array.
• Sorting: Used to solve problems that require sorting the elements in an array.
• DFS or BFS: Used to solve problems that require traversing through the elements in an array in a specific order.

Lastly, when you see an array problem, consider the following two things:

• Sliding window
• Binary range

This is especially true, if you are not able to figure out anything during the interview. And if you run out of all options, then greedy might be the way go to!

A common thing to forget when dealing with an array (e.g. subarray problems) is the case when the answer is at the last subarray boundary. Here is an example:

 for (int elem: array) {
     if (condition holds) {
         cur++;
     }
     ret = Math.max(ret, cur);
 }

 if (condition holds) ret = Math.max(ret, i-cur);

In most of the cases, the last case be avoided, if we were to take the candidate right where increment/adjust the value. For example.

 for (int elem: array) {
     if (condition holds) {
         cur++;
         ret = Math.max(ret, cur);
     }
 }

• ← Previous
• Next →