By Rahul Arora, Founder Intervue

Why you should read this?
There are N number of directions to go into when preparing for a technical interview. This guide is a summary of my experience and one single direction that can be taken which will give you results for sure without digressing from your path.
It will save you time as you do not have to follow multiple resources online.
I have prepared a checklist of things from my personal experience while preparing for companies like Uber, Google, Flipkart, Amazon, Microsoft & Facebook.
I gave about 2 hours everyday for a period of 2 months for the preparation and this is the summary.

How to read the guide
Each section has two things:
 Some rough notes about the techniques that can be applied in solving the questions.
 Questions to solve for each section. The variety of questions are enough to develop a natural instinct to solve most questions that are asked in such companies.
Each question has a Github link with it's solution and explanation with multiple methods with which the question can be solved.

Arrays
Methods that can be applied (rough notes):
 sorting and then doing something, hashtable, two pointers in a loop are some of the operations that are popular to solve algos. Hash table can also be made for storing sum etc.
 to find all combinations use nested for loops (worst algos)
 another way is to stop at an element and traverse all its previous elements
 fixing one number and having two pointers one at start and one at end to make some operation
 Consider making new arrays if anything does not work or satisfies requirements. These arrays may contain cumulative sum from left to right or right to left or soul of the algo which can make computation easy.
 Compare those arrays sometimes to find algos
 Cumulative sum or prod can work out to solve algos
 XOR operation can be applied to see the number repeating odd number of times as XOR will return that num only if there is one number that repeats odd number of times
 If element in an array is to be found, and length is known apply binary search. Will complete the search in O(logn) times. If binary search cant be applied look in sizes of k at a time to limit the search set.
 We cannot find time complexity of something whose input size is unknown.
 If some number is repeating like in 0s and 1s example, 0 can be changed to 1 for certain operations.
 To find duplicates for array containing elements between 1 to n, iterate, lets say value is 3, go to third index and change value to negative. If value is already negative that means 3 has repeated and so on check for all.
 You can also use an external variable OR divide array elements into relevant groups by some computation to solve the algo
 For questions with repeating sub problems, try thinking out using recursion
 returning a function in recursion which is called will ultimately end of returning the base value which has to be returned
 Sometimes if the algo seems to be complicated move to a generalized format where the result is assumed to be N and you are solving it for some x by going from solution to problem, and then try to figure out the algo. (refer question 28.c for more clarification)
 Circular array can be used to implement a queue. Here the increment is not done just by incrementing by 1, but is done by incrementing by 1 and taking mod with array size. Like this you keep rotating the array. Refer question 2 stacks and queue for more info
 For questions involving subarrays:
 Naive approach
 Can maintain another data structure (may be a queue) sometimes to solve the algo
 Can maintain a hash Table to solve the algo
 Can maintain multiple variables to solve the algo
 Can maintain two pointers to solve the algo
 Kabane's algo
Questions
 Insertion Sort
 Merge Procedure
 Merge Sort
 Partition Procedure
 Quick Sort
 Bubble Sort
 Counting Sort
 find a pair in an array whose sum is X
 Moore Voting algorithm to find majority element in an array
 Find the max difference between any two elements in the array
 Find the number occuring odd number of times in a given array
 Separate 0's and 1's from a given array
 Seperate even and odd numbers using partition method for separating 0's and 1's
 Given an array A, find two elements whose sum is closest to zero
 Find the triplet in given array that sum to given value 'x'
 Find the equilibrium index of an array
 In an array of unknown size having all 0s at one side and all 1s at other, find the index where 1st 1 exists.
 Given an array and an integer K, find max element for each and every contiguous subarray of size k
 Count number of smaller elements on the right of each element in an array
 Find the subarray with the given sum
 Consider and array which contains only 0's and 1's. Find largest sub array which contains only 0's and 1's
 Given an array of nintegers, construct product array such that prod[i] is equal to product of all elements except arr[i] without using division operator
 Find the duplicate in O(n) time and O(1) extra space
 Find the two repeating numbers in an array in which all elements are in range 1 to n occuring atleast once
 Rotate an array of n elements by d elements
 Given n non negative integers representing an elevation map where width of each bar is 1. Find the amt. of water that is trapped in between these bars after raining
 Given an unsorted array of +ve integers, find the number of triangles that can be formed with three different elements as three sides of the triangle
 Given an array, find the smallest number that is not possible with the sum of numbers from the array
 Write a program to do binary search in an array

Linked List
Methods that can be applied:
 Use multiple variables to not loose track of the linked list and keep moving them ahead in a manner such that various operations can be done on a linked list
 If you don't want a function to return a value of something, just send that value to the address of the variable by passing the address of variable as argument and accessing it has **
 maintain hash table of addresses of the different nodes (first node has this address and so on) to access the value later without traversing
 maintain multiple pointers. The pointers can be moved at different speeds as per requirements.
 sometimes linked list while designed can have flags to make an algo possible
 If linked list has a loop, and two pointers are taken one moving at double the speed of other, they will meet at some point inside the loop. The distance from the start of the list to the first node where the loop starts is equal to the distance from where they meet to the first node.
 Linked list is generally is used to store large numbers which cannot be stored in an int or is used to store polynomials. If numbers are stored in linked list, you will have to apply your own operations (add, subt and so on for that)
 Use general Data structures like stacks and queues or arrays to sometimes solve the algo.
 Try connecting the end of the linked list to the front or make a loop to solve an algo.
 To make games like snakes & ladders, we can use a linked list with a random pointer, next pointer and data. Whenever there is a ladder or snake, the random pointer will point there else it will be NULL.
 Consider making additional connections (links to the new list or old list) for traversing or reference point of view when there are multiple things involved (random node eg:). New node sometimes can be added in the middle of the two nodes to maintain a connection and so on.
 In program involving partition or merging always take mid as start+end/2 and not subtraction because this will always give the correct value. Subtraction may not give the correct value as you keep breaking the array into smaller parts
Questions:
 Program to create a singly linked list, insert and delete nodes and print all of them
 Move the last node to the begining of a linked list
 Traverse a Single linked list using recursion
 Iterative program to reverse a linked list
 Recursive program to reverse a linked list
 Find the middle node of a linked list
 Find the kth node from the end of the linked list
 Given a single linked list. Check if it has a loop
 Find the starting node of cycle if cycle exists in a given linked list
 Suppose there are two single linked lists both of which merge at the same point and become a single linked list. Find the node at which they merge
 Alternating split of a given linked list
 [Clone a linked list with three elements] (https://github.com/Intervue/Datastructuresalgorithmsforinterviews/blob/master(/linkedlists/question12.c)
 Check whether a given list is a palindrome or not
 Merge two sorted linkedlists into one sorted linkedlist
 Merge K sorted linked lists of size N into one sorted linked list
 Apply merge sort on linked list
 Consider a single linked list with each node having an arbitrary pointer with initial value NULL.Give an algorithm to make the arbitrary pointer point to the greatest value node on its right side. Insertion and deletion in memory efficient double linked lists

Hashing
Methods that can be applied:
 When solving questions divide value with the size of the hashTable. Keep the size of the hash table one greater than size of elements to be stored.
 Solve using chaining or linear probing
 Heap, BBSTAVL are some popular data structures that can be also used for questions involving hash table.
 Binary search is very widely used. Can only be applied if the length of array is known and if array is sorted.
 Sometimes, scanning once and searching and keeping additional variables for check can do the job.
 In hashing the structure can vary as per requirements. It can store anything from sum to frequency to pointers. So decide the structure as per always.
 For hash table take mod with the number of elements present.
 In case of question involving single array using recursion where tree is made, make sure that proper start and end of array is chosen(specifically where array is split again and again)
Questions:
 General question to understand linear probing
 General question to understand chaining
 Check whether given array contains duplicates in kdistance or not
 Check whether two sets given are disjoint or not
 Group all the occurences of the elements order by their first occurence
 Given an array A, Count the distinct elements in all windows of size K
 Given an array and a range, find the elements that are in the range but not in the array
 Given an array, print all subarrays in the array which has sum 0
 Find four elements i,j,k and l in an array such that i+j=k+l

Stacks & Queues
Methods that can be applied:
 For a stack and queue for each implementation or algo its core functionalities should hold true everytime. Eg popping and pushing on a stack takes O(1) time.
 For making a stack using two queues or viceversa either burden can be on push operation or pop operation. The one having burden will hold the task of enqueuing and dequeuing to move it to the other stack or queue. Refer to stacks and queues question4 for more info
 For questions in stacks and queues use additional stacks/queues as datastructures to implement some algorithms
 You can store the minimum or max in other stack/queue or data structure for every push and pop and so on. For eg storing the minimum so far in another stack so that each time when a number if popped off, if we pop off the minimum from the other stack, we will have min from the remaining elements sitting on top of the other stack. Like this many operations can be applied.
 You can also modify the numbers being pushed onto a stack and maintain an external reference by doing some computations to make an algorithm work. (Eg question5).
 Stack is useful where something is to be computed for every element but it is going to come late after iterating over various other elements. Since it has to follow a sequence, the no. for which computation cannot be done as of now can be pushed in the stack. The number for which computation is done can be popped off from the stack (eg. question6)
 Some algos may require implementing a stack using a different data structure. For eg using Double linked list over single linked list or using single linked list over arrays and so on. (question 7)
Questions:
 Implement a stack using arrays & linkedlist
 Implement a queue using circular array
 Implement a queue using two stacks
 Implement a stack using queues
 Design a stack such that get Minimum should be O(1)
 Given an array, find the closest greater element which is present on the right side of the element
 Implement stack with push ,pop, find middle element, delete middle element in 0(1)
 Consider a set of intervals, merge all overlapping intervals
 Check whether parenthesis are balanced or not
 The stock span problem
 Implement a queue using linked list

Heaps
Methods that can be applied:
 A large heap can be declared and only a small portion of it can always be included in the heap operations.
 Whenever a heap is built, swapping etc. will be there if elements do not follow the heap property (max or min)
 Sometimes to find largest element in an array, min heap can be made, for few first elements, and each time comparisons can be done with remaining element to eliminate the minimum elements.
 Methods where min and max heap can be applied BST can also be used (depends on question)
 Sometimes a combination of min heap and max heap can be used to solve questions. Min heap can contain maximum elements from array and max heap can contain minimum elements from array (this can be known at runtime without sorting the array). (refer question 7)
 Since each data structure has its own significance, sometimes it is good to use multiple data structures like min heap + max heap + linked list as BST and so on for some algos to perform series of operations
 Given max heap to be converted to min heap, if you delete max each time and insert it in min heap it will take logn time for each element therefore, total n elements. It will take nlogn time. Therefore, if you just take the array as a random array rather than taking it as a max heap you can build the min heap in O(n) time which is a better method.
Questions
 Given an array, create a max heap
 Given a max heap, apply different heap operations (find max, delete max,increase key, insert key, decrease key.)
 Write a program for heap sort
 Find a max element in a minheap
 Build a minheap and write algo to delete an arbitrary element
 Find k largest elements from an array
 Find median in a stream of numbers
 Given ksorted lists, Find the minimum range to which at last one number belongs from every list
 Print out all integers in the form of a^3+b^3 where a and b are integers between 0 and N in sorted order
 Convert BST to max heap

Trees
Methods that can be applied:
 Recursion is used more often than not in case of trees to implement anything.
 Preorder traversal can give the path from top to any node.
 Sometimes it is good to store the path in an array to solve some algos
 For level order traversal queue is used. Each time parent is pushed, then when popping the parent its children are pushed on the queue
 Most questions in trees involve doing the core algo on the LST and then on the RST and in the end using recursion getting the desired result.
 In a tree sometimes, if two pointers are to be returned for a DLL, we return only one and make the other point to the one that is also required so that we can get it using the one that is returned. Refer to question7 method2
 while applying recursion whatever is returned is returned for that particular function stack and will be assigned to the variable or thing that called that execution stack. In case local variables in recursion are to be used pass them as address and argument should be of type pointer while assignment.
 There are two ways of incrementing levels while traversal, one is to increment once when visiting LST and RST and decrement once when returning from LST or RST OR pass level as argument as level+1, when visiting LST and so on.
 Preorder traversal is best when you have to print nodes using some logic or visit any node given distance from another node or root. (even true for vertical tree order traversal)
 Somtimes hashtable can be used to store elements while traversal. Hashing comes in handy while searching for elements using a particular logic. So can be implemented along with trees.
 Sometimes if there is a problem determining the size of the hash table, linked list can be used instead which will further have linked lists attach to each nodes. So each node of the main linked list will behave as a cell of the hash Table.
 Deleting paths in recursion means, just free the root.
 Sometimes other functions can also be used inside recursion.
 The nodes of a subtree will always occur together in case of any traversal. The order may be different but there will be no interleaving.
 Sometimes to compare two subtrees, we can apply inorder and preorder OR inorder or postorder traversal and compare the o/p strings in the end. As studied earlier, preorder and inorder or postorder and inorder will always generate a unique tree.
 In case of question involving single array using recursion where tree is made, make sure that proper start and end of array is chosen(specifically where array is split again and again)
Questions:
 Build a binary search tree and apply various operations on it
 Check whether two trees are identical or not
 Program to make a mirror tree of a binary tree
 Implementation of Level order traversal in case of trees
 Find lowest common ancestor of given two nodes in a binary search tree
 Solve the problem above for the binary tree
 Convert a binary tree into a double linked list in such a way that the order of nodes represents the inorder traversal of binary tree. Note this has to be done in place
 Find the diameter of the given binary tree
 Get the level of a given key in a binary tree
 Print nodes kdistance from the root
 Print nodes which are at a k distance from the given key in a binary tree
 Program to implement vertical tree order traversal
 Vertical sum of the given binary tree
 Check whether the given binary tree is sum tree or not
 Print top view of a binary tree
 Print bottom view of a binary tree
 Print left view of a binary tree
 Remove all paths of length k from root in a binary tree
 Check whether a given binary tree if a subtree of another binary tree
 Check whether given two nodes are cousins in a binary tree
 Form a balanced binary search tree from a given sorted array
 Convert a given binary search tree into balanced binary tree

Strings
Methods that can be applied
 All concepts of arrays are applicable to strings, since they are characters arrays (the ones that are general and not just applicable to numbers)
 For searching both BST and hash table can be applied.
 Hash table can be made for a character array (string). Length of hashtable should be 256, because ASCII values maximum is upto 255 starting from zero, therefore only that much space will be taken at max.
 Two pointers in a loop both on same side one tracking duplicates one tracking unique can be used to remove duplicates from a string.
 In case of string arr size should be measured using strlen and not using sizeof as sizeof also includes \0
 Sometimes a string can be merged with itself or the other to solve some algos. For eg: if one string is rotation of the other, concatenating one with itself can give a string where second string will be a substring in this string.
 Store as many things as required to solve the algo in hash table as it is a structure
 It is always good to free memory assigned to hashTable after the end of the program
 Sometimes hashtable value can be decremented and not incremented to solve an algo for eg. finding anagram
 Excel column number and name relation has to do with the number system. In case of excel the number system base is 26. Therefore numbers are from 126. Just that numbers in this case start from 1 and not from zero as compared to other bases for eg 2 which has 0 and 1 and so on. Therefore given a number we can keep dividing it by 26 until we receive a number which is less than 26 as remainder. Then we take the remainder and quotient from bottom to top and assign them alphabets corresponding to their values.
Questions
 Find a maximum occuring character in a given string
 Remove duplicates from a given string
 Check whether given two strings are rotations of each other or not
 Reverse the words in a given sentence
 Reverse a given string
 Check whether given string is palindrome or not
 Find the first nonrepeating character in a given string
 Run length encoding
 Check whether given two strings are anagrams of each other
 Find excel column name for given excel column number
 Find the smallest window in the string containing all characters of another string
 Find first nonrepeating characters from a stream of characters

Greedy
Methods that can be applied:
 Used in case of optimization problems (maximize of minimize something)
 When to use heaps vs when to use sorting: When the problem requires just finding the min or max, we can use sorting, but if after finding something is to be inserted again for which in case of sorting it will take O(n) time as it requires finding the place, heaps are better as they take only O(logn) time to do the same thing.
 In order to represent nodes using bits etc, (eg: huffman coding), we use trees.
 Huffman codes or optimal merge patterns where something is to be minimized, always choose the maximum value to be at the top of the tree with min edge length (or path to be traversed) and min at bottom with max edge or path to be traversed to minimize work.
 Min cost spanning tree and shortest path problems are two different things. In shortest path a source will be given and we will have to reach the target in the shortest path possible given weight of each edge. In case of min cost spanning tree we have to construct a graph with min weight possible connecting ALL the nodes. Therefore priority of the algo varies
 In greedy method, to min or max something (different methods), we can be greedy about something to solve the algo, and bring in cases which can defy out method. One of them will work.
 Hash tables and mix and match of data structures like min and max heaps can also be used in solving greedy algos
Questions
 Make a program for greedy knapsack problem
 Make a program to implement huffman encoding
 Make a program to sequence given jobs with deadlines to maximize profits
 Optimal merge patterns
 Program for PRIMS algorithm without min heap
 Program for KRUSKALS algorithm
 Program for DIJKSTRA algorithm
 Program to implement a simple graph
 Consider nropes with different length. Find algo to tie up all the rope into a single rope with min cost
 Find max intervals from given intervals such that none of them are overlapping
 Number of railway platforms
 Rearrange the string such that same characters are d distance away
 Program for PRIMS algorithm using min heap

Divide and conquer
Methods that can be applied:
 In repeating elements with fixed size and ordered array we can use binary search. Also linear search can be used where if an element should be repeating a given number of times, you can check its value at i and then i+given number of times to see if thats true or not.
 In divide and conquer even number of multiplications can be reduced from n to logn to get the same result. Example is the pow function where the base value is square everytime and power is halved everytime to get the same answer in logn multiplications. In case the power value is odd, the result is given the base value such that power value is converted to even and then same operations are applied.
 In binary search whatever the algo be, always start from the middle and compare values to the left or right. You may even compare the extreme left and the right values to see lower and upper bound or some pattern to solve the algo. But in binary search always start from the middle. Also to break the recursion to return result successful condition will be a unique property trait at that index as per algo. Find that trait.
 Sometimes rather than searching in left array or right array, it is better to divide into two components/groups and apply various operations like comparison, merges etc. Note: since its divide and conquer number of division should be done till the end where we will be left with one element in each group.
 Sometimes, we apply binary search and on finding the middle element we apply the logic that is the crux of the algo to the middle element to find out whether to search in right array or left array. Eg: crux of algo if is swapping we do swapping, if comparing we do comparing, if it is applying some formula, we do that.
 To write the iterative version of a recursive version follow the steps below
 Replace the recursion break condition with the while loop which will run
 Apply the same conditions and update the value of the variables in that condition. These variables will be a part of the while loop also. Rather than calling the function with updated values, just update the values of the variables and while loop will handle the rest
 Make sure to assign both the variable values that are passed into the function in recursion while doing it in while loop as iteration
 The false condition (if any false value is to be returned for validation) will come after the end of while loop
 To write recursive from iterative, replace while loop condition and its opposite should be break condition of recursion and reverse the sub steps
Questions:
 Find a majority element using linear search that occurs more than n/2 times
 Nuts and bolts problem
 Write a custom C function to implement a pow function
 Select an element in sorted rotated array
 Count inversions in an array
 Find the missing number in arithmetic progression
 Given an array containing 1's and 0's in which all 0's appear before all 1's, count the number of 1's in the array
 Given an array with 2n integer in the formal a1,a2,a3...b1,b2,b3.. Shuffle the array to a1b1 a2b2 a3b3 ...
 Given a sorted array of non repeated integers a[1n]. Check whether there is an index i for which a[i]=i
 Find the maximum element index in an array which is first increasing and then decreasing
 Search an element in row wise and column wise sorted 2d array

Dynamic Programming
Methods that can be applied
 Programming in this means to use a table and we dynamically decide whether to call a function to do the computation or use this table
 Dynamic programming is just like divide and conquer and can be applied to any problem with optimal substructure (given problems should be breakable into smaller problems and solution to sub problem is a part of the solution to the main problem) and overlapping sub problems and recusive eqns
 In problems involving dynamic programming, we start from the basic case first (for eg in 0/1 knapsack), we see if the weight of knapsack is 1 and object weight is 1, then if weight is 2 and object weight is 1 and so on, we keep finding solution to every basic problem to derive the solution for the main problem.
 Questions involving subsequence, kadane's algo can be applied or hash table or pointers can be used
 In questions involving matrices somehow, to calculate the next number as per the algo it will involve the diagnal, upper or left element as we did in most of the algos.
 Sometimes we divide bigger problem into smaller problems by approaching it from the other side. For eg: if a number that is needed should satisfy division by 2/3/5, we will rather multiply the base number with 2/3/5 to generate the next one. Therefore a bigger problem to generate series was broken down to a smaller problem to generate the next number each time. To keep track of multiple generations sometimes, multiple variables can be used.
 Sometimes a given problem can be solved by reducing it to another known problem whose solution is known.
 For problems involving subsequences, we can break them down to smaller problems. Specifically for linear array, array of length 1 less than total can be taken and a pattern can be found for dynamic programming to make recursive equations.
 Sometimes results of two DP solutions can be merged using some algo to find the final result.
 To breakdown any question to DP (recursive equation), follow the crux of the question and break it down into a story and later generalize to form recursive equations. For eg: in case of finding the longest palindrome subsequence in a given string, we compare the last two elements to see if they match or not, this is something that we also do in a normal palindrome question. Here on basis of that we are able to derive to equations if they match we move both pointers to next location, if they dont we move one of them (two cases) and find whichever is maximum. Then using these recursive equations we build a tree taking an example in mind. Then we find overlapping problems. To see unique problems we generalize the question for which we made the tree to i and j and rather finding how many values of j can exist for each value of i everytime. By that calculation we find unique solutions and solve the question making a table of that size.
 See if a DP is becoming a fibonacci series. For eg: in the stairs problem total ways to reach the nth step f(n) = f(n1) + f(n2) i.e from n1 it can take you 1 step and from n2 it can take you only 1 step of size 2. Therefore, this is nothing but fibonacci series.
 In some algos involving DP you can start from n and in that case answer to n is dependent on n1 and so on.
 Most problems involving strings can be taken as S(i,j), either we compare last characters then if equal it gets converted to i1,j1 or we take min or max of i,j1 and i1,j
 Somtimes if the problem is already a table, you need to reverse engineer it to find the min number of ways to do something. Example create a new table and start from the very bottom and construct the solution updwards. Answer in that case will be the cell 0,0
 If a string and its reversal have a common subsequence, then definately that common subsequence is going to be a palindrome
 Whenever a problem is given involving string, check if LCS can be used
 Whenever a generic problem is given check if it is becoming a fibonacci series or a form of it.
Questions
 Algorithm to find optimized soln for matrix chain multiplication
 Compute Longest common subsequence between two strings
 Multistage graph dynamic programming algorithm
 0/1 Knapsack dynamic programming algorithm
 Find a subset in an array whose sum is w
 Travelling salesman problem
 All pair shortest path algorithm
 Find the maximum sum sub array
 Find the max sum increasing sub sequence
 Find the longest subsequence in an array such that elements are consecutive
 Given a binary matrix, find the largest square sub matrix with all 1's
 Find kth ugly number
 Find the longest increasing subsequence
 Find the longest decreasing subsequence
 Perfect hill longest subsequence
 Given two words, word1 and word2, find min operations to convert word1 to word2 with some given set of rules
 Largest sum independent set in a binary tree
 Find the number of nbit integers which do not have any two consequent zeroes
 Given a sentence without spaces between words. Break the words in such a way that they are meaningful
 Partition problem
 Find the longest palindromic subsequence
 Given nstairs, how many number of ways a person can climb to top from bottom using 1 step or 2 steps
 Longest nonoverlapping repeating sub string
 Given two strings X and Y, find the minimum cost to make two strings equal using only delete operations. Cost to delete character in X is S and in Y is P
 Count the number of times string occured as the subsequence of the other string
 Given an amount and some coins, find out in how many ways can this amount be formed
 Given a 2xn board and tiles of size 2x1, count the number of ways to fill the board using 2x1 tiles
 Given a cost matrix mxn having a cost at each cell. Find the min cost that it will take to reach cell (m1,n1) from top left corner cell (0,0) if the only allowed directions to move are right, down and diagnal down
 Given a string, find out if it becomes a palindrome or not after doing atmost k deletions
 Find the sum of digits for all numbers from 1 to N for a given N
 Given a string of digits, find the length of the longest substring of a string, such that the length of the substring is '2k' digits and sum of left k digits is equal to the sum of right k digits
 Given a rod of length 'n' inches and an array of prices that contains prices of all pieces of size smaller than n, find the max value obtainable by cutting the rod and selling the pieces
 Fibonacci series
 Max product sub array
 Finding the maximum square submatrix with all equal elements
 All pair shortest path algorithm (Floyd Warshall)
 Collect max coins from the grid in two traversals

Graphs
Methods that can be applied:
 Most of the graph questions revolves around finding the adjacent nodes and doing operations on it. Finding adjacent nodes is easy as you can get it from the matrix easily by seeing if the value corresponding to that vertex and some i is 1 and that it has to be unvisited. So basically we either do DFS or BFS.
 When path between two vertices is to be found, they need not be connected directly. There may be some vertices/ nodes in between.
 Sometimes a given matrix can be assumed to be a graph with a set of different rules and DFS or BFS can be applied on it.
 Check question6 grapsh to check trick on how to access all surrounding elements of a cell in matrix using two arrays
 In a bipartite graph a cycle will always be of even length
Questions:
 Implement a graph using adjacency matrix and list, implement DFS and BFS, BST and DST
 Implement a graph using adjacency matrix and do BFT in a different way for custom value of nodes
 Write a program to do topological sort in a graph
 Find if there is a path between two vertices Vi and Vj in a directed graph
 Given an undirected graph, find if it has a cycle or not
 Given a 2D boolean matrix, find the number of islands
 Check whether a given graph is biparite or not
 Detect a cycle in a directed graph
 Kosaraju algorithm to find SCCs
 Find if the given directed graph is eulerian
 Find if the given undirected graph is eulerian
 Dijkstra algorithm for matrix
 Dijkstra algorithm for adjacency list
 Articulation points and bridges in a graph
 Print all jumping numbers smaller than or equal to a given value
 Shortest path in directed acyclic graph
 Longest path in directed acyclic graph
 Hamiltonian cycle in a graph

Pattern Matching
Methods that can be applied:
 For KMP to find all occurences of a pattern in a string, whenever the match is found, we assign the pointer of pattern variable value that is there in the prefix suffix array at an index less then the current value of the pointer and we start comparing again.
 BoyerMoore algorithm is much more efficient than KMP at places where pattern to be searched has characters as different as possible. If the characters are same, then in worst case it will give a time complexity of O(mn) where it will end up comparing most of the characters, therefore, in case characters are mostly same use KMP
Questions:
 Given a text and a pattern, find all occurences of a pattern in a given text.
 Implement KMP algorithm to find all occurences of a pattern in a given text
 BoyerMoore algorithm for string finding patterns
 RabinKarp for string finding patterns

Back Tracking
Methods that can be applied:
 Permutations means ordered combinations. Eg. My juice is made by a combination of 10 fruits (order does not matter), but in case of permutations the order does matter. Basically changing the order can change the outcome means permutations. Changing the order has no effect on outcome is combination
 Backtracking uses recursion where each call in the stack has its stored values and backtracking makes use of those values to do decision making at a particular level in the recursion tree
Questions:
 Generate all permutations of a given string
 Program to generate all strings of n bits
 Nqueens problem

MISC
General Questions
 Print nth term of an arithmetic series
 A square is made by bending a single piece of wire. If we make a circle of this wire, what will be the radius and area of the circle?
 Program to swap two variables without using any other variable
 Coordinates of 3 vertices of an equilateral triangle are given on a cartesian plane. Calculate the coordinates of the center and the area of the circle inscribed in the triangle.
 Program to check if a circle can be drawn through three points in a catesian plane
 Use ternary condition operator to find min and max among three integers
 Generate random numbers b/w 5 and 10, using probability given
 Write a program to print "Pascal's Triangle".
 Write a program to find the sum of digits of a positive integer
 Write a program to print the numbers that do not appear in the Fibonacci series
 Write a function to find whether a positive integer is a power of two
 Find GCD of two positive numbers
 Write a function to check whether a positive integer is a palindrome or not
 Big question (still to be done)
 Find the maximum and minimum element in an array with a little tweak
 Given an array of integers, reverse the original array
 Implement the given functions in the matrix
 Write a program which will accept two strings and check whether all characters from the first string are present in the second string
 Write a program to find the average of "n" integers entered by user
 Write a program with a function to remove all characters in a string except alphabetical characters
 Write a program to sort five words in "Lexicographical Order"
 Big question
 Another big question
 Yet another big question
 Find GCD and LCM of two numbers

Advanced data
 Use KMP to find if a pattern exists in a text or not
 For Graphs, Topological sort is possible only on directed acyclic graphs (one with no cycles). Useful when one task is dependent on other.

Advanced data structures
 Disjoint sets: If two nodes are connected or belong to the same category they will be a part of the same set. Disjoint sets can be represented in two ways. 1) Linked list 2) Trees
There are three kind of operations that can be applied on such sets.
1) Find
2) Union
3) Create
Implementation using trees is better as we can apply union by rank and path compression to make sure find happens in logn or constant time, create anyway happens in constant time only.
In case of linked list find takes O(n) time and union also takes O(n) time and create takes O(1) time
Questions
 Test whether given two strings are isomorphic or not
 Find the length of the longest suffix which is also a prefix
 Sort a stack
 Given two strings a and b print whether they contain any common subsequence (non empty) or not.

Bit Manipulation

Trie
Methods to solve algos better
 For extreme values refer to limits.h constants given by C

XOR
means taking sum of the bits and dividing by two, remainder will be the answer = 'XOR' is commutative  'XOR' of a number with itself is 0
 'XOR' of zero with a number is the number itself
 '1s compliment is number obtained by reversing all the bits in the binary representation of a number. o to 1 and 1 to 0'
 Linear hashing is (h(k) + i)modm (where m is the size of the hash table, h(k) is the hash function that takes the key k and returns a value i is the parameter that is incremented to get different values)
 Subarrays of an array are always contiguous whereas subsequence may not be contiguous but needs to be in the increasing order. Same applies to a string as well.
 There are only two ways to make any data structure one is to use an array (where size is fixed and memory is contiguous) OR you can use the heap memory (structures and linked list). So Array and linked list or combo of these two are used to implement any data structure. In most cases linked list takes more time to do operations if data structure is implemented using it. But advantage is dynamic memory allocation
 For INFIX to POSTFIX conversion, data structure used is stack. In stack all the operators are stored. For evaluation of POSTFIX stack is used to store operands
 Evaluating and expression = convert from INFIX to postfix > Evaluate POSTFIX. Time complexity: O(n)
 Heap can be implemented as a binary tree or ternary tree or nary tree. Heap is an almost complete binary tree. Leaves should always be filled from left to right in a heap
 Heap should be used when along with insertion, find min and delete min or max it to be done in less time
 In a min/max heap the root contains the min/max element compared to its children. Applicable for all levels.
 To make a heap rather than making a linked list (as it involves a lot of storage), we make an array.
 Every tree which is having one node or leaf (node with zero children) is already a min or max heap.
 From an array if a heap is to be constructed, follow:
LEFT(i) = 2i + 1;
RIGHT(i) = 2i + 2;
PARENT(i) = (i1) / 2; (valid for array with index 0)
//Go level by level from left to right and write elements from the array or to the array basically.
//Note dividing by two means right shift in binary and multiplying means left shift in binary
//There can be more than 1 max or min heap of a given array
//In a complete or almost complete binary tree, leaves start from floor(n/2+1) to n
 An array in descending order is MAX HEAP and array in ascending order is MIN HEAP.
 There is an O(n) time algo to convert an element into a heap. So no need to sort as sorting take O(nlogn)
 Recursion adds to the space complexity as well as time complexity.
 In a max heap, finding min, deleting random element or searching an element will take O(n) time because here max heap is as good as an array.
 For Binary Search tree implementation using an array, space complexity is O(2^n), but using linked list, it is O(n)
 Stream of numbers mean the numbers are coming one after the other and for each input change you have to find what is stated in the question.
 There are three ways to traverse any binary tree (can be applied to 3ary or nary trees as well with some modifications)
//all nodes should have children, even leafs
INORDER //left root right  second visit
PREORDER//root left right  first visit
POSTORDER //left right root  third visit
 Binary tree is a normal thing placing the element in order as given in the array in parent child relationship from left to right BUT Binary search tree follows a particular order.
 Binary search tree is usually used to store keys. Keys generally point to a particular record. Therefore keys have to be unique.
 INORDER traversal of BST gives us all elements in ascending order. (least element left most, max right most)
 To understand recursion better or to do a dry run or make a recursive program follow the method of 123. i.e executing all lines turn by turn at a single place as explained in trees double order traversal or indirect recursion
 Indirect recursion is when some function A calls B and B again calls A and so on.
 Number of structures possible with N nonlabelled nodes is 2ncn/n+1
 Number of trees possible per structure if labelled n nodes is n! (total trees will be 2ncn/n+1 * n!)
 Given PRE ORDER POST AND IN ORDER only 1 tree will satisfy all conditions (number of trees with n nodes given pre post and in only 1 tree is possible. Even combination of any with INRODER will generate a binary tree uniquely)
 Expression tree is a tree in which operator occupied the root along with the nodes on the left or right side. (correct side can be checked by inorder traversal). Also operators have to be arranged on the tree as per their precendence.
 preorder, postorder and inorder traversal of an expression tree gives the respective forms.
 LCRS (left child right sibling), in this left pointer points to the left child and right pointer points to the siblings which are children of the parent node along with this node. Representation is used to present trees having random number of children not necessary equal
 Array representation of trees is used in case of heaps where going up and down is required. The disadvantage of using array is that if a tree is skewed, arrays have to be as large as 2^n for storing n values given indexes of parent and child which is not the case in case of heaps.
 Recursion will keep populating the stack until dealing with statements to be executed, once a definite value truthy or falsy is returned, it will then pop off the execution context that returned that value. It is important to even return a function because then stack will know that this function is going to return something which may be a another function being returned or a value. This is how it keeps going.Note if return statement is not written then if else statement should be used so to avoid control of the program going downwards in the non satisfying condition. So return statement is just a replacement of if else in recursion
 Level order traversal uses a queue in which parent is pushed onto the queue and then its popped (dequeued) and its children are pushed in order from left to right and same process is repeated. Therefore we keep scanning the nodes level by level.
 Level order traversal is similar to BFS (breadth first search in graphs) and other traversals like inorder, preorder and postorder are similar to DFS (depth first search in graphs)
 Vertical tree order traversal: Root is at a distance 0 from itself. When we move to the left child it is at a distance 1 from the root, the right child is at a distance 1 from the root. If we keep doing 1 for every left child and +1 for every right child, we will have multiple nodes at the same distance value. The nodes having same distance value fall on a vertical line. If we traverse that line, it is called vertical tree order traversal
 Sum tree is the one where sum of values in the LST and sum of values in the RST is equal to the root. This is valid for all the nodes except the tree
 Recursion execution stack only remembers the next line if there is no return statement, else it will return the execution stack
 Two nodes in a tree are siblings if they are at the same level and have same parent, are cousins if they are at same level but do not have same parent
 O(1) means time complexity or space complexity is not dependent on the input size
 One string is rotation of the other, if one of the rotations of one string matches the other one.
 Run length encoding means, traversing through the given character array and displaying which character is repeating how many times along with the character as output. Eg: SSMMMAAARRT => S2M3A3R2T1
 Two strings are anagrams if they have same no of characters and they are composed of the same letters. Even if there are repetitions, they are going to be same.
 Ideal approach of writing a program is return from a functiona and keep strings at a single place and not scattered
 Greedy method and DP are two programing paradigms which can be used to solve optimization problems
 Greedy method fractions are allowed
 For huffman coding to work letters must not be uniformly distributed
 Spanning tree is min number of edges present in the graph such that all nodes are connected. Span tree is always subgraph of the main graph and cannot contain edges which are not present in the main graph
 Number of edges incident on the node is degree of node in undirected graphs. In case of directed, there is no degree but in degree and out degree
 Kirchoff theorem is used to find spanning tree of nonweighted undirected simple graph
 Given a weighted graph, finding the minimum cost spanning tree can be done using two algos PRIMS and KRUSKALS. Both are greedy methods
 In PRIMS, whenever weights of edges are duplicates, there is a chance that we might get more than 1 spanning tree. But final cost will remaing the same for all in that case
 Dijsktra algo cannot be applied to graphs having ve weight edges because the algo does not have capability to find if that edge is ve or its getting converted to a ve weight cycle. If there is a ve weight cycle in the graph shortest path will not exist as with each cycle path will keep on decreasing.
 Tree is an acyclic graph
 Greedy method and dynamic programming are the only two methods that can be applied to find the solution to optimization problems. Greedy may not give the right solution everytime for each problem but will work for some of them and it takes less time. Dynamic on the other hand takes a little more time but always gives the correct answer to such problems.
 n factorial is nothing but n power n
 In a graph represented by cost matrix, if two vertices have an edge, weight will be given otherwise if they dont have edge it is infinity.
 Travelling salesman problem time complexity O(n^2 ^ 2^n)
 Ugly number is a one which can be written as a product of 2,3 or 5 or a combination of these numbers. 1 is also considered as ugly number as it is an exception.
 Whenever highest or lowest power of two is to be found, use log operations

Conclusion:
I hope this guide comes in handy at any of your interviews involving Data Structures & Algorithms.
To stay updated follow me on Twitter
Discussion (19)
Nice 😄, I want to start from scratch as beginner. Do we need to know any theory about data structure before starting to practice problems in your post ?
Also can I have solutions in
C#
or atleastJava
?@Shaiju: You can read little bit theory alongside solving the problem statements.
I have tried to add explanation to as many questions as possible as well. So, it will help cover the theoretical part as well. Do not spend too much time reading theory. Handson is the best way to learn and hence this guide is ultimate.
I will try adding solutions in Python and Javascript. Will see if Java can be accomodated then.
Right now converting C to Java will not be a big deal since most of the solutions are straight forward.
Also I saw below course from educative. It claims to prepare for DS coding interview by learning them to apply in real world projects.
try.educative.io/decodecodingint...
Is that course better to learn than this post ?
That is what the intended purpose of this post is at the first place. As I said, there are N number of ways to go about preparing for a technical interview.
This is one way and you do not have to digress.
I can tell you two things about a course that makes it different:
This post has both the things. I have seen people learning from geeks for geeks and numerous other websites online and cracking interviews.
The thing with DS/Algo is that you just need to start and go in a direction. Post that you do not need courses.
Regarding the educative course  Looks comprehensive as well. But you do not need to know more than given in the post honestly to crack an interview.
Thanks, I have 6 years of software development experience. I am not good at c language and data structure algorithms. Is it good start now using Java instead ?
Suppose I choose to join big companies at 10 + years of experience, is it good to join them after 10 years, still the interview will consist of these type of DS problems ?
@Shaiju:
Big companies at 10+ years of experience will concentrate more on design problems. If you are India focused, leading a project and all aspects related to it might count as well depending on the role and the company. If you are abroad chances are more that you can still get to code. DS/Algo is then the way to go.
Also, learning DS/Algo and developing an instinct always helps when thinking of a solution in a real job.
If you are at 6+ years, you can easily prepare in about 2 months time given you give 1 hour or so everyday. If you apply after that, product companies will definitely ask DS/Algo.
DS/Algo is mostly language agnostic. It does not matter whether you know C or not. Whatever language you are comfortable with, you can start solving the problem in that.
Thank you. Appreciate. :)
Just wanted to make you aware of some more resources that will be useful for job seekers. I've built some interactive altos courses:
qvault.io/bigoalgorithmscourse/
qvault.io/bigodatastructuresco...
I'd also love you to DM me, I think there could be some collaboration between Qvault and Intervue
Hey Lane thank you for this. Check DM on twitter
Saved for later since it looks too big but well structured
FIRE
Such a useful article, gosh
😊
Great stuff
Thanks. Hope you like it :)
More coming soon!
looks like very comprehensive guide. 👍
Thank you. Hope you liked it!
Wow so in depth thats what I like to see!
Yesterday was stuck with back tracking question, this really helped a lot.
Since having a step by step approach helps in breaking down the problem statement in smaller unit, solving becomes easier.
Thanks, This will definitely help the community.
Wow!. I am glad :D