Coding Interview Patterns for Microsoft, Facebook, Google, Amazon and Netflix

For Whom this Article is?

• If you want to be a pro on Algorithms and problem-solving skills. Welcome, this article is made for you.

Prerequisites

• You need to have a basic understanding of common data-structures like “Array, Linked-list, Hash-map, Stack, Queue, Heap and Graph”.

What about Patterns

• The goal is to build an understanding of the underlying pattern so that we can apply that pattern to solve other problems.
• In a Coding Interviews held by FANG -(Facebook, Amazon, Netflix and Google) those interview coding rounds are based really next level of thinking, those coding rounds are not only for how good you code but how you will think and how you identify the problem and give optimize solution.
• Before you writing the code for a specific algorithm question or problem. First, you need to understand the problem well and in which approach you are trying to solve it.
• These patterns are for you to ace any coding interview.

Overview of Big-O Notation

The Time Complexity of an algorithm refers to its runtime in relation to an increase or decrease in the number of inputs. The notation used to describe the performance and complexity (the number of operations) of an algorithm is known as Big O. We can calculate the execution time (time complexity) and space (space complexity) that are required to run a particular algorithm, and determine whether that algorithm will be useful in this scenario. The most common time complexities are:

Introduction to Time Complexity — Big O

Constant — O(1)

Linear — O(n)

Logarithmic — O(log n)

Quadratic — O(n²)

Exponential — O(2^n)

The colors represent how good the time complexities are , if you are not familiar with Big-O notation. No, problem take a look at this https://medium.com/@nagamalliaditya3/big-o-notation-what-is-time-complexity-and-space-complexity-87631add1746?source=your_.

Let’s Dive into the topic Patterns

1.Sliding Window

Intro:The Sliding Window pattern is used to perform a required operation on a specific window size of a given array or linked list.

Identify Problem: The problem input is a linear data structure i.e, Linked List , array or string.

You’ve asked the Longest/Shortest Subarray , Substring or a desired value

Eg. Of Problems:

• Maximum Sum Subarray of size K
• Smallest Subarray with a given sum
• Longest Substring with k distinct characters
• Fruits into Baskets
• No-repeat Substring
• Longest Substring with same letters after replacement
• Longest Subarray with ones after replacement

2.Two Pointers or Iterators

Intro:Two Pointers is a pattern where two pointers iterate through the data structure in tandem until one or both of the pointers hit a certain condition.Two Pointers is often useful when searching pairs in a sorted array or linked list.

Identify Problem:

• Feature Problems where Sorted Arrays / Linked Lists and need to find a set of elements that fulfill certain constraints
• The set of elements in the array is a pair , a triplet, or even a subarray

Eg. Of Problems:

• Pair with target sum
• Squaring a Sorted Array
• Remove Duplicates.
• Comparing strings that contains backspaces
• Triplet Sum to Zero
• Triplet Sum Close to Target
• Triplets with Smaller Sum
• Subarrays with product less than a Target
• Dutch National Flag

3.Fast and Slow Pointers

Intro: The Fast and Slow pointer approach, also known as Hare & Tortoise Algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence / linked list) at different speeds.

This Approach is quite useful when dealing with Cyclic Linked Lists or arrays.

The faster pointer should catch the slower pointer once both the pointers are in a cyclic loop.

Identify Problem:

• problem will deal with a loop in a linked list or array.
• Position of a certain element or the overall length of the linked list.

Eg. Of Problems:

• Linked List Cycle
• Middle of the Linked List
• Start of the Linked List Cycle
• Happy Number
• Palindrome Linked List
• Cycle in a Circular Array

4.Merge Intervals

Intro: The Merge Intervals patterns is an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, you either need to find overlapping intervals or merge intervals if they overlap

Identify Problem:

• If you hear the term “Overlapping intervals”.

Eg. Of Problems:

• Merge Intervals
• Insert Intervals
• Intervals Intersection
• Conflicting Appointments
• Maximum CPU Load

5.Cyclic Sort

Intro: This Cyclic Sort pattern iterates over the array one number at a time, and if the current number you are iterating is not at the correct index,you swap the number at its correct index.

Identify Problem:

• There will be problems involving a sorted array with numbers in a given range.
• Problem asks you to find the missing/duplicate/smallest number in the given range.

Eg. Of Problems:

• Cyclic Sort
• Find the Missing Number
• Find all Missing Numbers
• Find the Duplicate Numbers

6.In-Place Reversal of a Linked List

Intro: Reverse the links between a set of nodes of a linked list. I.e., Using the existing node objects and without using extra memory.

Identify Problem:

• Reverse a linked list without using extra memory

Eg. Of Problems:

• Reverse a LinkedList
• Reverse a Sub-list
• Reverse Every K-Element Sub-list

7.Tree Breadth First Search

Intro: This pattern is based on Breadth First Search(BFS) technique to traverse a tree uses a queue to keep track of all the nodes of a level before jumping onto the next level.Any problem involving the traversal of a tree in a level-by-level order can be efficiently using this approach.

Identify Problem:

• Traverse a tree in a level-by-level fashion (or level order traversal).

Eg. Of Problems:

• Binary Tree Level Order Traversal
• Reverse Level Order Traversal
• ZigZag traversal
• Level Averages in a Binary Tree
• Level Order Successor
• Connect Level Order Siblings

8.Tree Depth First Search

Intro: Tree DFS is based on the Depth First Search (DFS) technique to traverse a tree.

You can use recursion(or a stack for the iterative approach) to keep track of all the previous(parent) nodes.

Identify Problem:

• If you’re asked to traverse a tree with in-order,preorder, postorder DFS.
• If the problem requires searching for something where the node is closer to a leaf.

Eg. Of Problems:

• Binary Tree Path Sum
• All Paths for a sum
• Sum of Path Numbers
• Path with Given Sequence
• Count Paths for a sum.

9.Two Heaps

Intro: This pattern uses Two Heaps, A Min-Heap to find the Smallest element and a Max-Heap to find the Biggest element. The Pattern works by storing the first half of numbers in a Max Heap,then Store the smallest number in the second half.

The median of the current list of numbers can be calculated from the top element of the two heaps.

Identify Problem:

• Useful in Situations like Priority Queue, Scheduling.
• If the problem states that you need to find the Smallest/Largest/Median elements of a set.
• Sometimes, useful in problems featuring a binary tree data structure.

Eg. Of Problems:

• Find the Median of a Number Stream
• Sliding Window Median
• Maximize Capital

10.Subsets

Intro: Permutations and Combinations of a given set of elements. The Pattern Subsets describes an efficient Breadth First Search (BFS) approach to handle all these problems.

Identify Problem:

• Problems where you need to find the combinations or permutations of a given set.

Eg. Of Problems:

• Subsets
• Subsets with Duplicates
• Permutations
• String Permutations by changing case
• Balanced Parentheses
• Unique Generalized Abbreviations.

11.Modified Binary Search

Intro: Whenever, you are given a sorted array, linked list, or matrix, and are asked to find a certain element, the best algorithm you can use is the Binary Search.

This pattern describes an efficient way to handle all problems involving Binary Search.

Identify Problem:

Find a certain element given in an array,linked list, matrix.

Eg. Of Problems:

• Order-agnostic Binary Search
• Ceiling of a Number
• Next letter
• Number Search
• Search in a Sorted Infinite Array
• Minimum Difference Element
• Bitonic Array Maximum

12.Top ‘K’ elements

Intro: Any problem that asks us to find the top/smallest/frequent ‘K’ elements among a given set falls under this pattern

The best data structure to keep track of ‘K’ elements is Heap.This pattern will make use of the Heap to solve multiple problems dealing with ‘K’ elements at a time from a set of given elements.

The pattern looks like this:

1. Insert ‘K’ elements into the min-heap or max-heap based on the problem.
2. Iterate through the remaining numbers and if you find one that is larger than what you have in the heap, then remove that number and insert the larger one.

Identify Problem:

• Find the Top/Smallest/Frequent ‘K’ elements of a given set.
• If you are asked to sort an array to find an exact element.

Eg. Of Problems:

• Top ‘K’ numbers
• Kth Smallest Number
• ‘K’ Closest Points to the Origin
• Connect Ropes
• Top ‘K’ Frequent Numbers
• Frequency Sort
• Kth Largest Number in a Stream
• K Closest Numbers
• Maximum Distinct Elements
• Sum of Elements
• Rearrange String

13.K-way Merge

Intro: K-way Merge helps you solve problems that involve a set of sorted arrays.

Whenever you’re given ‘K’ Sorted arrays, you can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays. You can push the smallest element of each array in a MinHeap to get the overall minimum.After getting the overall minimum, push the next element from the same array to the heap. Then, repeat this process to make a sorted traversal of all elements.

The pattern looks like this:

1. Insert the first element of each array in a Min Heap.
2. After this, take out the smallest(top) element from the heap and add it to the merged list.
3. After removing the smallest element from the heap, insert the next element of the same list into the heap.
4. Repeat steps 2 and 3 to populate the merged list in sorted order.

Identify Problem:

• The problem will feature sorted arrays, lists or a matrix.
• If the problem asks you to merge sorted lists, find the smallest element in a sorted list.

Eg. Of Problems:

• Merge K sorted lists
• Kth Smallest Number in M Sorted Lists
• Kth Smallest Number in a Sorted Matrix.
• Smallest Number Range.

14.Topological Sort

Intro: Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For eg. If event ‘B’ is dependent on event ‘A’, ‘A’ comes before ‘B’ in topological ordering.

This pattern defines an easy way to understand the technique for performing topological sorting of a set of elements.

This pattern Works like this:

1. Initialization

i. Store the graph in adjacency lists by using a HashMap.

ii. To find all sources, use a HashMap to keep the count of in-degreesBuild the graph and find in-degrees of all vertices.

2.Build the graph from the input and populate the in-degrees HashMap

3.Find all sources

i. All vertices with ‘0’ in-degrees will be sources and are stored in a Queue.

4.Sort

a. For each source, do the following things:

i) Add it to the sorted list.

ii)Get all of its children from the graph.

iii)Decrement the in-degree of each child by 1.

iv)If a child in-degrees becomes ‘0’, add it to the sources Queue.

1. Repeat (i), until the source Queue is empty.

Identify Problem:

• The problem will deal with graphs that have no directed cycles.
• If you’re asked to update all objects in a sorted order.
• If you have a class of objects that follow a particular order

Eg. Of Problems:

• Topological Sort
• Tasks Scheduling
• Tasks Scheduling Order
• All Tasks Scheduling Orders
• Alien Dictionary

IMP NOTE: “The most of the content from this article is collected from internet only. I am not the only one to eligible for this credit. Most of the intelligent and experienced people will work on this even before me and i gathered some of the opensource data and published on my article.””

NOTE: Coding is not a copy and paste of some data, Coding is logical thinking , if you want to be a pro in Coding. You must know these Basics and Data Structures and Algorithms, Learn >> Apply >> Share these three should be in a cyclic loop.

Thank you everyone, taking time to learn this and feel free to give suggestions i am happy to change and learn new things from you or which topics you need further comment.