  # Vexed with solving numerous questions for placements? No worries! Try out these techniques that will help you solve most problems faster.  Spreeha Dutta

2 years ago | 11 min read

Introduction

I was inspired to write this post after going through technical interviews earlier this year. While going through related blogs of different companies, I found that some companies had asked to find the Nth number of the Fibonacci series in the first round.

Naturally, I was led to wonder why would a company be asking a simple question like that? Won’t everyone be able to do it then? How will they filter out candidates? That was until I discovered that Nth Fibonacci number can be solved just in O(log n) using the formula `F(n)={[(√5+1)/2]^n}/√5`. It brings down the complexity right from O(n) to O(log n)! And most of us aren’t even aware of it.

After all, it’s not about who gets the solution right but who gets the optimal solution!

That was just a simple example but the time spent preparing to solve coding questions can sometimes get quite taxing.

With there being an overwhelming number of topics to prepare on, often people spend their time in laboriously going through hundreds of different questions (just like I had done initially). In the end, some important topics are left uncovered. Thus an organized and systematic approach is needed at times like these!

Study Smart rather than Study Hard!

To speed up this process, I’ve created this tutorial. I have consolidated some techniques here (yes, after having scoured through hundreds of questions, sighs!). They can be used to solve some frequently asked questions during placements in a much lesser time with a better performance.

Do you understand these approaches thoroughly? Well then, you are definitely on solid ground and almost good to go!

Though I haven’t been able to cover everything in this blog, for those going through interviews, I highly suggest you refer to the books — Cracking The Coding Interview (here), Grokking the Coding Interview (here), Data Structures and Algorithms Made Easy by Narsimha Karumanchi (here). And of course a site that I found extremely useful while preparing, GeeksForGeeks.

# 1. Sliding Window

The sliding window is a very popular technique for performing operations on subarrays or substrings which are usually of a fixed size.
It reduces the time complexity to O(n).

## Commonly Asked Problems on Sliding Window :

The maximum sum subarray of size `k` OR minimum number of elements to be removed such that the sum of the remaining elements is equal to `k`
The loop iterates `(n-k)` times. First the sum of elements from index 0 to the `kth` element is calculated and stored in a variable (`sum`). Each time the window slides by 1 element,subtracting the first element of the existing window and adding the `(k+1)th` element to the new window.

(ii) Minimum product subarray of size k

(ii) Longest substring with k distinct characters

(iii) Number of substrings that are anagrams of any substring of another string

Note : The size of the window may or may not be fixed. We can modify the window size according to what the problem demands.

# 2. Slow Pointer and Fast Pointer (Floyd’s Cycle Finding Algorithm):

A very favorite question that is asked in interviews! This technique is mainly used in problems related to linked lists. It uses 2 pointers, a slow pointer and a fast pointer. For every time the slow pointer moves one node, the fast pointer moves two nodes.
It reduces the time complexity by half.

(i) Checking if a linked list is a palindrome: Iterate through the linked list using a fast pointer and slow pointer. Until the fast pointer reaches the end of the linked list, push every element visited by the slow pointer into a stack. The slow pointer will have reached the middle element now and the stack will have all elements from the first to middle in reverse order

(ii) Detecting a loop in a linked list: If the fast pointer becomes equal to the slow pointer at any point, there is a loop in the linked list

(iii) Finding the middle node in a linked list: When the fast pointer reaches the end of the linked list, the slow pointer will have reached the middle node.

(iv) Finding a happy number: A number is called “happy” if it leads to 1 after a sequence of steps wherein each step number is replaced by the sum of squares of its digit.

# 3. Meet In The Middle

Meet In The Middle is a technique that divides a problem into 2 parts of equal size, solves them, and then merges the corresponding results from both the parts that result in an overall optimal solution.

You can perform this operation when the merging of two solutions is an aggregate function like count, sum, max. It can be employed on linear data structures.

## Commonly Asked Problems that employ Meet In The Middle:

(i) Finding all triplets with a given product: Three pointers are used. For every iteration, pointer1 is kept fixed at n (where n=size-1 initially). Pointer2 is at the 0th position and pointer3 at (size-2)position. This checks if the elements at ptr2 and ptr3 give the corresponding element at ptr1 as result. ptr1 is decremented by 1 every time until the triplets are found. This again takes O(n²). It can be brought down to O(n) using hashing.

(ii) Finding Pythagorean triplets

(iii) Find 2 numbers from an array that add up to a given sum S. This takes O(n).

(iv) Minimum number of appends to make a string palindrome without rearranging it

# 4. Hashing

This is another extremely important technique to bring down your time complexity! But remember, it results in the use of extra space. A hash table is used to associate keys with values. It is used for fast storage and retrieval of information.

Time Complexity: Though the worst-case time complexity of hashing is O(n), it gives O(1) on an average. Values getting mapped into buckets after the index for that value is calculated by a hash function

## Commonly Asked Problems under Hashing:

(i) Finding the repeating and missing element from an array: Use an integer array of size 256 (`arr`). Iterate over the array and for each element, increment the value at array index corresponding to the ASCII value of the element by 1 (`arr[ASCII value of element]+=1`). Traverse the new array, wherever the value is more than 1, the element at that ASCII value will be repeated and where the value is 0, that element corresponding to that ASCII value will be missing.

(ii) Remove duplicates from an a string

(iii) Checking for a loop in a linked list

(iv) Remove characters from one string that are present in another string

(v) Find all pairs from an array whose sum is S. This takes O(n) time complexity.

# 5. Stacks and Queues

This is something most of us are very familiar with. To jog your memory, a stack is a data structure that follows the principle of LIFO (Last In First Out), the last element to go in is the first to come out. On the other hand queue is a data structure that follows the principle of FIFO (First In First Out). Many problems can be solved using the concept of stacks and queues.

## Commonly Asked Problems on Stacks and Queues:

(i) Implementing a queue using stacks

(ii) Sorting a stack using a temporary stack

(iii) Conversions between Infix, Prefix, and Postfix forms

(iv) Checking for balanced parentheses in an expression

(v) Stock span problem

(vi) Celebrity problem

(vii) LRU Cache Implementation using a queue

(viii) Finding the maximum of 3 elements using a priority queue

# 6. Breadth First Search (BFS) or Level Order Traversal (trees):

Many problems with trees can be solved using level order traversal. And yes, it is another favorite question in interviews!

Level order traversal for a tree is nothing but a breadth-first traversal of the tree. It traverses all nodes of the tree level by level starting from the root node. BFS for a graph also works in a similar way. Only here the vertices at the (n+1) level are all the adjacent unvisited neighbors of a node at level n. BFS Traversal for the above graph : A B D C E

Generally a queue is used for storing vertices at a level for both graphs and trees. You can employ this method to all those questions where levels need to be processed one after the other.

Time Complexity — O(n) where n is the number of nodes in the tree.

## Commonly Asked Problems on Level Order Traversal with Trees:

(i) Zigzag level order traversal of a BST. O(n) extra space is required.

(ii) Finding the depth of a binary tree / finding all nodes at a distance k

(iii) Finding the in-order successor of a node in a binary tree

(iv) Finding the average of every level in a BT

Function for finding the average of every level in a Binary Tree

(v) Connecting all level order siblings. Time complexity is O(n) where n is the number of nodes.

## Commonly Asked Problems on Level Order Traversal with Graphs:

(vi) Cycle detection in Undirected Graphs: If all vertices are reachable, the graph is connected. If any of the nodes remain marked unvisited, then its unreachable.

(vii) Word ladder: Start from a given word and traverse all its neighbors (words differing by 1 character). This is repeated until the target word is found or all words have been traversed.

(viii) Time taken to rot all oranges in a grid

(ix) Number of ways to reach the destination in a maze

Time Complexity — O(V+E) where V is the number of vertices in the graph and E is the number of edges in the graph.

## Q. Checking if a Graph is a Tree:

An undirected graph is a tree if —
(i) There is no cycle — O(V+E)
(ii) The graph is connected - O(V)
Overall time complexity — O(V+E)
Since the graph is undirected, either BFS or DFS can be used.

# 7. Depth First Search (DFS)

It is used for traversing trees and graphs. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
— Wikipedia

DFS Traversal for the above graph : A B C D E

## Common problems under DFS are :

(i) Detecting cycle in a graph

(ii) Number of ways to reach the destination in a maze

(iii) Finding strongly connected components of a graph — O(V+E)

(iv) To find all nodes reachable from a given node

(v) To check if a graph is bipartite

# 8. Binary Heap

It is a complete tree where the value at each parent node is either greater (for MaxHeap) or smaller (for MinHeap) and this property is true for all nodes.

Why Solve Problems using Heaps? The time complexity!
Getting the minimum or maximum element takes O(1) which is a significant decrease as compared to O(n). The time complexity of heap sort is O(n log n). Operations like extracting the minimum element, inserting or deleting a key takes O(log n).

Note:
A heap does not follow the rules of a binary search tree. The left sibling may or may not be smaller than the right sibling in a heap.

## Common Problems using Heaps are:

(i) Implementing a priority queue (can also be used to perform faster union operations using a binomial heap)

(ii) Finding the kth largest or smallest element in an array

(iii) Sorting an almost sorted array

(iv) Merging k sorted arrays

# 9. Binary Search

It is a technique we all are well familiar with. But it should not be taken lightly because for most of the questions asked, you will have to modify traditional binary search a bit. So it would be better if you try your hand at a few questions that involve modified binary search before going in for an interview.

To recapitulate briefly, the binary search looks for an element in a sorted array by dividing it into 2 halves. If the key is greater than the middle element, the value might be there in the right half of the array otherwise it might be present in the left half.

Time Complexity: In the worst case, it gives a time complexity of O(log n).

static void average(Node root)
{
Queue<Node> q = new LinkedList<Node> (); //creating a queue to store elements level-wise
int sum = 0; //to store sum of elements at each level
int n = 0; //To store number of elements at each level
int level = 0; //To store the level number
while (!q.isEmpty())
{
sum = 0;
n = 0;
Queue<Node> temp = new LinkedList<Node> (); //Temporary queue to store the elements at the next level while the current level is being processed
while (!q.isEmpty()) {
Node node = q.peek();
q.remove();
sum = sum + node.val;
n++; //Incrementing the counter for the number of nodes at the current level
if (node.left != null)
temp.add(node.left); //Adding the left child of the current node in the temprary queue
if (node.right != null)
temp.add(node.right); //Adding the right child of the current node in the temprary queue
}
q = temp; //Assigning the temporary queue as the queue to be processed next
System.out.print("Average at level " + level + " is " + (sum * 1.0 / n));
level++; //Incrementing the level by 1
}

### Binary Search

A slight modification over Binary Search can help solve many problems.

## Common Problems that employ Binary Search:

(i) Searching for an element in a sorted and rotated array

(ii) Index of least element greater/lesser than a given number

(iii) Finding row with maximum and minimum number of zeroes in a matrix

(iv) Kth smallest element in the array using constant space

(v) Splitting an array into K sub-arrays such that maximum sum of all sub arrays is minimum

# 10. Merging k Arrays

This involves finding the minimum element from all the k arrays. The minimum element can be found using heaps, as has already been discussed in point 8 or by using tournament trees or splay trees, all in O(log k). The minimum element is then repeatedly replaced with the next smallest element.

Time Complexity: The resulting running time is O(n log k).

## Common problems under k-way merge are:

(i) Merging k sorted arrays of same size: Insert the first element of all subarrays into a min heap. Put the minimum element of the heap into another array. Then replace the root of the heap with the next element from the array. Repeat this (nk) times.

(ii) Merging k sorted arrays of different size

(iii) Finding the median of contiguous sub-arrays

Upvote  Created by

Spreeha Dutta

Navigating my way through life's beautiful stories! Post

Upvote

Downvote

Comment

Bookmark

Share

Related Articles