Ace the Problem Solving /Algorithms Interviews(using Data Structures)

Hacking the coding interviews at FAANG!

Landing a job at top tech companies is a dream for many developers around the globe. Tech Giants like Facebook, Amazon, Apple, Netflix, Google, Microsoft are the largest and most dominant companies in the information technology. They are apparently hiring at a rapid rate with a unique hiring process that emphasizes the harmony between the candidate and the companies’ culture and leadership principles while assessing the technical proficiency and expertise.

This story is dedicated to the coding questions and problem solving round at these top-tech companies. Let’s adopt a strategic approach to prepare for the common coding interview questions at FAANG by learning the patterns behind them while simultaneously analysing the given problems and their respective algorithms and complexities.

Note: Problem Solving and mastering Data Structures and Algorithms is an art/craft that Engineers are able to master by being in constant practise.

Here’s the first pattern, your acquaintance to which, will leave your interview highly impressed with you.

Cyclic Sort Pattern : This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range.

Problem Statement

We are given an unsorted array containing ’n’ objects. Each object, when created, was assigned a unique number from 1 to ’n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’.

Write a function to sort the objects in-place on their creation sequence number in O(n).

Example :

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Solution

As we know, the input array contains numbers in the range of 1 to ’n’. We can use this fact to devise an efficient way to sort the numbers. Since all numbers are unique, we can try placing each number at its correct place, i.e., placing ‘1’ at index ‘0’, placing ‘2’ at index ‘1’, and so on.

We will iterate the array one number at a time, and if the current number we are iterating is not at the correct index, we swap it with the number at its correct index. This way we will place the numbers in their correct indices, hence, sorting the whole array.

Let’s see this algorithm visually with the above-mentioned example:

Cyclic Sort

Code (Python)

def cyclic_sort(nums):
i = 0
while i < len(nums):   #execute if i less than length of nums array
j = nums[i] - 1        # j stores the number's desired index
if nums[i] != nums[j]:   # if number is not at the correct index
nums[i], nums[j] = nums[j], nums[i]  # swap the numbers
else:
i += 1            # if at correct index: skip and move to next index
return nums         # return the sorted array

Code (JavaScript)

function cyclic_sort(nums) {
let i = 0;
while (i < nums.length) {
const j = nums[i] - 1;
if (nums[i] !== nums[j]) {
[nums[i], nums[j]] = [nums[j], nums[i]]; // swap
} else {
i += 1;
}
}
return nums;
}

Runtime(Time) complexity

The time complexity of the above algorithm is O(n), n being the length of the array nums .

Although we are not incrementing the index i when swapping the numbers, this will result in more than ‘n’ iterations of the loop, but in the worst-case scenario, the while loop will swap a total of ‘n-1’ numbers and once a number is at its correct index, we will move on to the next number by incrementing i. So overall, our algorithm will take O(n) + O(n-1) which is asymptotically equivalent to O(n).

Memory(Space) complexity

The algorithm runs in constant space O(1), since there’s a constant expense of the memory resources.

Now, here’s an example of the question being asked at FAANG interviews (based on Cyclic Sort pattern):

Find the missing number in the array

Problem Statement : You are given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one number x. You have to find x. The input array is not sorted.

Example :

Input: [4, 0, 3, 1]
Output: 2

Solution 1: Use Cyclic Sort to sort the given array and then find the first number missing from its correct index, that will be our required number

Code (JavaScript):

function find_missing_number(nums) {
let i = 0;
const n = nums.length;
while (i < n) {
j = nums[i];
if (nums[i] < n && nums[i] !== nums[j]) {
[nums[i], nums[j]] = [nums[j], nums[i]]; // swap
} else {
i += 1;
}
}
//End of Cyclic Sort
// find the first number missing from its index, that will be our required number
for (i = 0; i < n; i++) {
if (nums[i] !== i) {
return i;            // i is the missing number
}
}
return n;      // if no missing number found: return the length 
}

Time complexity : O(n) [same as above]

Space complexity : O(1).

Solution 2 : Using arithmetic series sum formula — {n *(n + 1)}/2

​​Here are the steps to find the missing number.

1. Find the sum ‘sum_of_elements’ of all the numbers in the array. This would require a linear scan, O(n).
2. Then find the sum ‘expected_sum’ of first ’n’ numbers using the arithmetic series sum formula i.e. ( n * (n + 1) ) / 2.
3. The difference between these i.e. ‘expected_sum — sum_of_elements’, is the missing number in the array

Code (JavaScript) :

function find_missing(input) {
//  calculate sum of all integers in input list
let actual_sum = 0;
for (let i in input) {
actual_sum += input[i];
}
//  There is exactly 1 number missing
let n = input.length + 1;  // this is tricky
let sum_of_n = Math.floor((n * (n + 1)) / 2);
return sum_of_n - actual_sum;   // returns the missing number
};

Runtime(Time) Complexity: Linear, O(n).

Memory(Space) Complexity: Constant, O(1).

With this we come to the end of the discussion on Pattern — Cyclic Sort.

Will discuss more patterns for coding questions at FAANG interviews in the upcoming stories.