Fun With Data Structures: Simple Tricks for Technical Interviews

Simple data structures and algorithm tricks you should learn before taking technical interviews with big tech companies

This is the second story in this series. You can find the first one here.

In this article, we will discover five simple tricks that will help you with the most common FAANG technical questions. If you are not familiar already, I suggest you to learn about binary tree, min/max heap and hash maps before reading more.

Trick #1: Removing an element in O(1) time from an unordered array

Problem: [10, 4, 56, 0, 8, 1] remove the element 4 in O(1) time.

Note: you can assume you already know the index of the element.

When you perform a remove operation on an array, all the subsequent elements are shifted to left, which takes O(n) time. It protects the order property of the array.

What if the ordering of the elements doesn’t matter for us? Well, there is a very simple, O(1) implementation you can use:

• Replace the element you want to remove with the last element of the array. Then decrease the array size by one.

So removing 4 would look like:

[10, 4, 56, 0, 8, 1] # This is how list looks like before removing
[10, 1, 56, 0, 8, 1] # Replace "4" with the last element "1"
[10, 1, 56, 0, 8]    # Decrease array size by 1.
# Congrats! You removed an element in O(1) time

Trick #2: Min/Max heap for “K’th smallest/largest element” problems

For this trick you first need to be familiar with min/max heap. If you are not, please read this article.

Problem: Given a list of numbers, find the kTh smallest element. I.e: Find the third smallest element in list [4, 20, 16, 10, 0, 47]

When a question is asked in the form of “Find K’th smallest element in a list”, you naturally tend to come up with a solution using a min-heap because of the word “smallest” in the problem statement. You can simply build a min-heap of the given list and extract the root element until you get k’th smallest element.

The time complexity of this solution is O(n + kLogn) and it occupies O(n) memory. Is there a better solution for this specific problem though, both in terms of time and space complexity?

The answer is, as you can guess, yes! We will use max-heap instead of min-heap.

The idea behind this technique is very simple actually. You keep the smallest k elements in a max-heap structure and root of the tree always points to the smallest k’th element in the list. An example is worth a thousands words.

Our original problem is: Find third smallest element in [4, 20, 16, 10, 0, 47]

1- Build a max-heap from the first k elements of the array: initial max-heap [20, 4, 16]. Notice that how the root element points to largest of the first three elements.

2- For every remaining element in the list, compare them with the root of the max-heap. If it is less than the root, replace the root with that element. For our example: next element is 10, root of the heap is 20. 10 is less then 20 so we replace the root with element 10 and keep the max-heap property of the heap. New root is 16.

3- When you are done with the second step you will still have k elements in the max heap and the root of the heap will be k’th smallest element.

Time complexity: O(k + (n-k)Logk)

• Use max-heap for K’th smallest problems.
• Use min-heap for K’th largest problems.

Note: there are different solutions to this problem using quickselect, median of medians... I chose heaps because they are simpler to understand and visualize.

Trick #3: Use index mapping

Index mapping is a technique I have used many times in technical interviews, to save search time at the expense of using more memory.

Problem: Implement a min-heap data structure with O(1) search time. Why O(1) ? Let’s assume that we are updating the nodes frequently and we don’t want to spend time on searching the them.

For the sake of simplicity we will only focus on the “search” part of the problem, min-heap is already implemented.

This is a min-heap and it is represented as an array underneath:

[0, 4, 16, 10, 20, 47]

And we want to find the index of a given node in the array, let's say 10.

We can do a linear search on the array, which will take O(n) time. It is obvious that we can’t magically have O(1) search time unless we sacrifice some resources. Solution?

We can keep the index of each node in a hash-map. And we need to update the indexes on this hash-map, whenever we update the heap.

For the heap above, [0, 4, 16, 10, 20, 47] , index mapping is:

{
  0: 0,
  4: 1,
  16: 2,
  10: 3,
  20: 4,
  47: 5
}

Now we can find the position of the node 10 in O(1) time. If we change the ordering of elements in heap, we also update their relative indexes in the index-map data structure.

Note: You can use other data structures such as trees for index-map.

Follow-up: Can you use the same technique for pointers/references as well?

Trick #4: Understand the fundamentals of Binary Search

Binary search is not just for finding an element in a sorted array. It is much more powerful. Once you understand the fundamentals of it, you will be fascinated by the number of problems you can solve with it!

Problem:

Farmer John has built a new long barn, with N stalls.
Given an array of integers A of size N where each element of the array represents the location of the stall,
and an integer B which represent the number of cows.
His cows don’t like this barn layout and become aggressive towards each other once put
into a stall. To prevent the cows from hurting each other, John wants to assign the cows to the stalls,
such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

This is a problem from interviewbit.

Can you solve this problem using binary search?

Yes you can. It will take hundreds of lines to describe the fundamentals of the solution in this article. Instead, I strongly recommend you to read this beautiful article on topcoder and it will all make sense.

Trick #5: Manipulate the bits

Bit manipulation is a useful technique to optimize your code (mostly memory) and they can be used in a variety of problems. You should at least be comfortable with bit shifting, and/or/xor/not operations.

Good to know bit operations:

x ^ x = 0 // xor
x ^ 0 = x // xor
x | 0 = x // or
x & 1 = x // and
Get i'th bit on num: (num & (1 << i)) != 0
Set i'th bit on num: num |= 1 << i

Problem: Given an array of integers, every element appears twice except one. Find that element. (from leetcode.)

Sample input: [1, 0, 8, 1, 8]
Output: 0 // the number that doesn't repeat

There are many data structures you can use to solve this operation such as hash-maps, trees. Which all will take at least O(n) time and O(n) memory. Can you think of a solution that takes O(1) memory?

Well, you guessed right. We can use bit operations. What do we know so far: x ^ 0 = x and x ^ x = 0 .

If you XOR all the elements of the array, the ones that repeat will cancel each other (x ^ x = 0) and at the end, you will have the number that doesn’t repeat:

arr = [1, 0, 8, 1, 8]
result = 0
for num in arr:
  result ^= num
return result

This will take O(n) time and O(1) memory. As good as it gets!