In a Coding Interviews held by Facebook, Amazon, Netflix and Google or other startups 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(2n)
The notations represent how good the time complexities are , if you are not familiar with Big-O notation.
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:
Insert ‘K’ elements into the min-heap or max-heap based on the problem.
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:
Insert the first element of each array in a Min Heap.
After this, take out the smallest(top) element from the heap and add it to the merged list.
After removing the smallest element from the heap, insert the next element of the same list into the heap.
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:
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.
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