Arrays and 12 related Data Structures & Algorithms for Coding Interviews

Lets begin with the basic data structure, in the data structure line up.

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value.

const arr = [1, 2, 3];

for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

// Output:
// 1
// 2
// 3

1-D Tutorials & Notes | Data Structures | HackerEarth

Detailed tutorial on 1-D to improve your understanding of Data Structures. Also try practice problems to test & improve your skill level.

HackerEarth

It starts out simple, however this data structure is very versatile and can be used to solve lots of problems.

Arrays and its related Data Structures & Algorithms are used to solve a lot of problems.

Data Structures

All the Data Structures mentioned below, use Array underneath in one way or another.

1. Sorted / Unsorted

There's difference between sorted & unsorted array, in terms of time complexity and problem approaches.

For instance, search becomes faster in a sorted array, but insertion gets slower.

Search, insert and delete in an unsorted array - GeeksforGeeks

A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

GeeksforGeeks

Search, insert and delete in a sorted array - GeeksforGeeks

A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

GeeksforGeeks

2. Strings

String is like an Array of characters, and all of the Array sub problems / approaches can be applied to it as well.

However it adds lot more variations. Like Sub-string, Palindrome, Regular Expression, ...

const str = "Hello, World";

console.log([...str]);
// ["H", "e", "l", "l", "o", ",", " ", "W", "o", "r", "l", "d"]

// or

console.log(str.split(''));
// ["H", "e", "l", "l", "o", ",", " ", "W", "o", "r", "l", "d"]

3. Multi-dimension

Array of arrays is called a matrix.

It can be any number of dimensions. However the common one is a 2D matrix.

It has Pixel Grid, Shortest Path, Graph, Island style problems.

const twoDArr = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

console.log(twoDArr); // [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Multi-dimensional Tutorials & Notes | Data Structures | HackerEarth

Detailed tutorial on Multi-dimensional to improve your understanding of Data Structures. Also try practice problems to test & improve your skill level.

HackerEarth

4. Min Heap / Max Heap

It's a complete binary tree, stored in an array. It has few formulas you need to remember and then you are golden.

Variations include: Min heap, Max heap.

In an interview, we don't have to write the whole thing. Instead we can just pretend we already have the data structure ready, as a separate function.

import heapq

li = [5, 7, 9, 1, 3]

heapq.heapify(li)
print(li) // [1, 3, 9, 7, 5]

heapq.heappush(li, 4)

print(li) // [1, 3, 4, 7, 5, 9]

5. Hash Table

It's is a data structure which stores data in an associative manner i.e. in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

We don't need to know how to implement a Hash Table from scratch to be able to use it.

const hashMap = {
    'hello': 'world',
    'hakuna': 'matata',
};

console.log(hashMap['hakuna']); // 'matata'

6. Stack / Queue

Stack follows LIFO, while Queue follows FIFO.

We can either use array for stack & queue implementation, or a linked list. Later being the better approach if random access is not required.

const stack = [1, 2, 3];

stack.push(4);      // Push at the end of the array
stack.pop(4);       // Pop from the end

console.log(stack); // [1, 2, 3]

const queue = [2, 3, 4];

queue.unshift(1);   // Enqueue at the beginning of the array
queue.pop();        // Dequeue at the end

console.log(queue); // [1, 2, 3]

Algorithms

All the Algorithms mentioned below use Array one way or other.

1. Binary Search

It's an efficient search mechanism that is done on a sorted array. It takes Log n time, instead of linear time to search through the array.

It is similar to a dictionary search humans perform.

var search = function(nums, target) {
    let low = 0, high = nums.length - 1;
    
    while(low <= high) {
        mid = parseInt((low + high) / 2);
        
        if(nums[mid] == target) {
            return mid;
        } else if(target > nums[mid]) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return -1;
};

2. Sliding Window

It's a small category compared to the rest of the line up, however it's worth a mention.

Problems include: Longest Sub-string, Consecutive 1s, ...

3. Two Pointers

This approach will open up doors for solving few tricky problems.

Like: Linked List Cycle, String Reversal, ...

4. Sorting

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements.

const arr = [5, 4, 3, 2, 1];

console.log(arr.sort((a, b) => a - b)); // [1, 2, 3, 4, 5]

5. Greedy

A greedy algorithm is a simple, intuitive algorithm that is used in optimisation problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem.

6. Dynamic Programming

Dynamic Programming is mainly an optimisation over plain recursion. The idea is to simply store the results of sub-problems, so that we do not have to re-compute them when needed later.

This is the biggest and toughest category of them all.

We shall conquer this category eventually.

Conclusion

This was just an introduction to the vast category that is Arrays. I will eventually write about each of the above categories.

Let me know your thoughts below.