Rahul Arora

Posted on Mar 6, 2021 • Edited on Sep 11

The ultimate guide for data structures & algorithm interviews 🔥

#career #beginners #algorithms #javascript

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

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:

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, BBST-AVL 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:

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 vice-versa 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:

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

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:

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 1-26. 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

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

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:

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(n-1) + f(n-2) i.e from n-1 it can take you 1 step and from n-2 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 n-1 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 i-1,j-1 or we take min or max of i,j-1 and i-1,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

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:

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.
Boyer-Moore 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:

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:

MISC

General Questions

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

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 n-ary 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) = (i-1) / 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 3-ary or n-ary 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 non-labelled 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 non-weighted 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

Top comments (18)

Shaiju T • Mar 7 '21

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 atleast Java ?

Rahul Arora • Mar 7 '21

@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.

Shaiju T • Mar 7 '21 • Edited

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 ?

Rahul Arora • Mar 7 '21 • Edited

@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.

Shaiju T • Mar 7 '21

Thank you. Appreciate. :)

Shaiju T • Mar 7 '21

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/decode-coding-int...

Is that course better to learn than this post ?

Rahul Arora • Mar 7 '21

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:

Content
Direction that it gives you

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.