The ultimate guide for data structures & algorithm interviews 🔥
Tags: career, beginners, algorithms, javascript
Published: 2021-03-06 16:07:52

By [Rahul Arora](https://twitter.com/rahhularora), Founder [Intervue](https://www.intervue.io)

--

# 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

![Arrays](https://i.ibb.co/Pg9xc2Y/arrays.png)

### 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question1.c)
- [Merge Procedure](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question2.c)
- [Merge Sort](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question3.c)
- [Partition Procedure](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question4.c)
- [Quick Sort](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question5.c)
- [Bubble Sort](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question6.c)
- [Counting Sort](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question7.c)
- [find a pair in an array whose sum is X](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question8.c)
- [Moore Voting algorithm to find majority element in an array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question9.c)
- [Find the max difference between any two elements in the array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question10.c)
- [Find the number occuring odd number of times in a given array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question11.c)
- [Separate 0's and 1's from a given array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question12.c)
- [Seperate even and odd numbers using partition method for separating 0's and 1's](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question13.c)
- [Given an array A, find two elements whose sum is closest to zero](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question14.c) 
- [Find the triplet in given array that sum to given value 'x'](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question15.c)
- [Find the equilibrium index of an array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question16.c)
- [In an array of unknown size having all 0s at one side and all 1s at other, find the index where 1st 1 exists.](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question17.c)
- [Given an array and an integer K, find max element for each and every contiguous subarray of size k](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question18.c)
- [Count number of smaller elements on the right of each element in an array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question19.c)
- [Find the subarray with the given sum](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question20.c) 
- [Consider and array which contains only 0's and 1's. Find largest sub array which contains only 0's and 1's](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question21.c) 
- [Given an array of n-integers, construct product array such that prod[i] is equal to product of all elements except arr[i] without using division operator](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question22.c)
- [Find the duplicate in O(n) time and O(1) extra space](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question23.c)
- [Find the two repeating numbers in an array in which all elements are in range 1 to n occuring atleast once](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question24.c)
- [Rotate an array of n elements by d elements](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question25.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question26.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question27.c)
- [Given an array, find the smallest number that is not possible with the sum of numbers from the array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question28.c)
- [Write a program to do binary search in an array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/arrays/question29.c)

--

## Linked List

![Linked list](https://i.ibb.co/R6vRwpG/Linkedlist.png)

### 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question1.c)
- [Move the last node to the begining of a linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question2.c)
- [Traverse a Single linked list using recursion](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question3.c)
- [Iterative program to reverse a linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question4.c)
- [Recursive program to reverse a linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question5.c)
- [Find the middle node of a linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question6.c)
- [Find the kth node from the end of the linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question7.c)
- [Given a single linked list. Check if it has a loop](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question8.c)
- [Find the starting node of cycle if cycle exists in a given linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question9.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question10.c)
- [Alternating split of a given linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question11.c)
- [Clone a linked list with three elements]
(https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master(/linked-lists/question12.c)
- [Check whether a given list is a palindrome or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question13.c)
- [Merge two sorted linked-lists into one sorted linked-list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question14.c)
- [Merge K sorted linked lists of size N into one sorted linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question15.c)
- [Apply merge sort on linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question16.c)
- [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.](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question17.c)
-[Insertion and deletion in memory efficient double linked lists](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/linked-lists/question18.c)

--

## Hashing

![Hashmaps](https://i.ibb.co/7kPCLCm/hashmaps.png)

### 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:

- [General question to understand linear probing](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/general-question1.c)
- [General question to understand chaining](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/general-question2.c)
- [Check whether given array contains duplicates in k-distance or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question1.c)
- [Check whether two sets given are disjoint or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question2.c)
- [Group all the occurences of the elements order by their first occurence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question3.c)
- [Given an array A, Count the distinct elements in all windows of size K](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question4.c)
- [Given an array and a range, find the elements that are in the range but not in the array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question5.c)
- [Given an array, print all subarrays in the array which has sum 0](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question6.c)
- [Find four elements i,j,k and l in an array such that i+j=k+l](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/hashing/question7.c)

--

## Stacks & Queues

![Stacks](https://i.ibb.co/SNwMqP8/Stacks.png)
![Queues](https://i.ibb.co/PhBnfSn/queues.png)

### 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:

- [Implement a stack using arrays & linked-list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question1.c)
- [Implement a queue using circular array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question2.c)
- [Implement a queue using two stacks](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question3.c)
- [Implement a stack using queues](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question4.c)
- [Design a stack such that get Minimum should be O(1)](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question5.c)
- [Given an array, find the closest greater element which is present on the right side of the element](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question6.c)
- [Implement stack with push ,pop, find middle element, delete middle element in 0(1)](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question7.c)
- [Consider a set of intervals, merge all overlapping intervals](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question8.c)
- [Check whether parenthesis are balanced or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question9.c)
- [The stock span problem](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question10.c)
- [Implement a queue using linked list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/stacks-and-queues/question11.c)

--

## Heaps

![Heaps](https://i.ibb.co/98FXS7H/Heaps.png)

### 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question1.c)
- [Given a max heap, apply different heap operations (find max, delete max,increase key, insert key, decrease key.)](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question2.c)
- [Write a program for heap sort](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question3.c)
- [Find a max element in a min-heap](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question4.c)
- [Build a min-heap and write algo to delete an arbitrary element](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question5.c)
- [Find k largest elements from an array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question6.c)
- [Find median in a stream of numbers](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question7.c)
- [Given k-sorted lists, Find the minimum range to which at last one number belongs from every list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question8.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question9.c)
- [Convert BST to max heap](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/heaps/question10.c)

--

## Trees

![Trees](https://i.ibb.co/CmWMVZb/trees.png)

### 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question1.c)
- [Check whether two trees are identical or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question2.c)
- [Program to make a mirror tree of a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question3.c)
- [Implementation of Level order traversal in case of trees](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question4.c)
- [Find lowest common ancestor of given two nodes in a binary search tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question5.c)
- [Solve the problem above for the binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question6.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question7.c)
- [Find the diameter of the given binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question8.c)
- [Get the level of a given key in a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question9.c)
- [Print nodes k-distance from the root](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question10.c)
- [Print nodes which are at a k distance from the given key in a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question11.c)
- [Program to implement vertical tree order traversal](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question12.c)
- [Vertical sum of the given binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question13.c)
- [Check whether the given binary tree is sum tree or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question14.c)
- [Print top view of a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question15.c)
- [Print bottom view of a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question16.c)
- [Print left view of a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question17.c)
- [Remove all paths of length k from root in a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question18.c)
- [Check whether a given binary tree if a subtree of another binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question19.c)
- [Check whether given two nodes are cousins in a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question20.c)
- [Form a balanced binary search tree from a given sorted array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question21.c)
- [Convert a given binary search tree into balanced binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/trees/question22.c)

--

## Strings

![Strings](https://i.ibb.co/dQGKBLy/Strings.png)

### 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

- [Find a maximum occuring character in a given string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question1.c)
- [Remove duplicates from a given string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question2.c)
- [Check whether given two strings are rotations of each other or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question3.c)
- [Reverse the words in a given sentence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question4.c)
- [Reverse a given string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question5.c)
- [Check whether given string is palindrome or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question6.c)
- [Find the first non-repeating character in a given string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question7.c)
- [Run length encoding](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question8.c)
- [Check whether given two strings are anagrams of each other](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question9.c)
- [Find excel column name for given excel column number](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question10.c)
- [Find the smallest window in the string containing all characters of another string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question11.c)
- [Find first non-repeating characters from a stream of characters](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/strings/question12.c)

--

## Greedy

![Greedy](https://i.ibb.co/PtGP1GV/whiteboard.png)

### 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question1.c)
- [Make a program to implement huffman encoding](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question2.c)
- [Make a program to sequence given jobs with deadlines to maximize profits](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question3.c)
- [Optimal merge patterns](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question4.c)
- [Program for PRIMS algorithm without min heap](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question5.c)
- [Program for KRUSKALS algorithm](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question6.c)
- [Program for DIJKSTRA algorithm](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question7.c)
- [Program to implement a simple graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question8.c)
- [Consider n-ropes with different length. Find algo to tie up all the rope into a single rope with min cost](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question9.c)
- [Find max intervals from given intervals such that none of them are overlapping](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question10.c)
- [Number of railway platforms](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question11.c)
- [Rearrange the string such that same characters are d distance away](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question12.c)
- [Program for PRIMS algorithm using min heap](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/greedy/question13.c)

--

## 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question1.c)
- [Nuts and bolts problem](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question2.c)
- [Write a custom C function to implement a pow function](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question3.c)
- [Select an element in sorted rotated array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question4.c)
- [Count inversions in an array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question5.c)
- [Find the missing number in arithmetic progression](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question6.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question7.c)
- [Given an array with 2n integer in the formal a1,a2,a3...b1,b2,b3.. Shuffle the array to a1b1 a2b2 a3b3 ...](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question8.c)
- [Given a sorted array of non repeated integers a[1--n]. Check whether there is an index i for which a[i]=i](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question9.c)
- [Find the maximum element index in an array which is first increasing and then decreasing](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question10.c)
- [Search an element in row wise and column wise sorted 2d array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/divide-and-conquer/question11.c)

--

## 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

- [Algorithm to find optimized soln for matrix chain multiplication](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question1.c)
- [Compute Longest common subsequence between two strings](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question2.c)
- [Multistage graph dynamic programming algorithm](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question3.c)
- [0/1 Knapsack dynamic programming algorithm](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question4.c)
- [Find a subset in an array whose sum is w](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question5.c)
- [Travelling salesman problem](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question6.c)
- [All pair shortest path algorithm](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question7.c)
- [Find the maximum sum sub array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question8.c)
- [Find the max sum increasing sub sequence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question9.c)
- [Find the longest subsequence in an array such that elements are consecutive](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question10.c)
- [Given a binary matrix, find the largest square sub matrix with all 1's](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question11.c)
- [Find kth ugly number](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question12.c)
- [Find the longest increasing subsequence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question13.c)
- [Find the longest decreasing subsequence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question14.c)
- [Perfect hill longest subsequence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question15.c)
- [Given two words, word1 and word2, find min operations to convert word1 to word2 with some given set of rules](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question16.c)
- [Largest sum independent set in a binary tree](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question17.c)
- [Find the number of n-bit integers which do not have any two consequent zeroes](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question18.c)
- [Given a sentence without spaces between words. Break the words in such a way that they are meaningful](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question19.c)
- [Partition problem](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question20.c)
- [Find the longest palindromic subsequence](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question21.c)
- [Given n-stairs, how many number of ways a person can climb to top from bottom using 1 step or 2 steps](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question22.c)
- [Longest non-overlapping repeating sub string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question23.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question24.c)
- [Count the number of times string occured as the subsequence of the other string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question25.c)
- [Given an amount and some coins, find out in how many ways can this amount be formed](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question26.c)
- [Given a 2xn board and tiles of size 2x1, count the number of ways to fill the board using 2x1 tiles](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question27.c)
- [Given a cost matrix mxn having a cost at each cell. Find the min cost that it will take to reach cell (m-1,n-1) from top left corner cell (0,0) if the only allowed directions to move are right, down and diagnal down](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question28.c)
- [Given a string, find out if it becomes a palindrome or not after doing atmost k deletions](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question29.c)
- [Find the sum of digits for all numbers from 1 to N for a given N](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question30.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question31.c)
- [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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question32.c)
- [Fibonacci series](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question33.c)
- [Max product sub array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question34.c)
- [Finding the maximum square sub-matrix with all equal elements](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question35.c)
- [All pair shortest path algorithm (Floyd Warshall)](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question36.c)
- [Collect max coins from the grid in two traversals](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/dynamic-programming/question37.c)

--

## Graphs

![Graphs](https://i.ibb.co/25YcXw7/graphs.png)

### 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question1.c)
- [Implement a graph using adjacency matrix and do BFT in a different way for custom value of nodes](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question2.c)
- [Write a program to do topological sort in a graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question3.c)
- [Find if there is a path between two vertices Vi and Vj in a directed graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question4.c)
- [Given an undirected graph, find if it has a cycle or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question5.c)
- [Given a 2D boolean matrix, find the number of islands](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question6.c)
- [Check whether a given graph is biparite or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question7.c)
- [Detect a cycle in a directed graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question8.c)
- [Kosaraju algorithm to find SCCs](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question9.c)
- [Find if the given directed graph is eulerian](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question10.c)
- [Find if the given undirected graph is eulerian](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question11.c)
- [Dijkstra algorithm for matrix](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question12.c)
- [Dijkstra algorithm for adjacency list](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question13.c)
- [Articulation points and bridges in a graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question13.c)
- [Print all jumping numbers smaller than or equal to a given value](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question15.c)
- [Shortest path in directed acyclic graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question16.c)
- [Longest path in directed acyclic graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question17.c)
- [Hamiltonian cycle in a graph](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/graphs/question18.c)

--

## 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:

- [Given a text and a pattern, find all occurences of a pattern in a given text.](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/pattern-matching/question1.c)
- [Implement KMP algorithm to find all occurences of a pattern in a given text](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/pattern-matching/question2.c)
- [Boyer-Moore algorithm for string finding patterns](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/pattern-matching/question3.c)
- [Rabin-Karp for string finding patterns](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/pattern-matching/question4.c)

--

## 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/back-tracking/question1.c)
- [Program to generate all strings of n bits](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/back-tracking/question2.c)
- [N-queens problem](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/back-tracking/question3.c)

--

## MISC

### General Questions

- [Print nth term of an arithmetic series](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question1.c)
- [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?](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question2.c)
- [Program to swap two variables without using any other variable
](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question3.c)
- [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.](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question4.c)
- [Program to check if a circle can be drawn through three points in a catesian plane
](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question5.c)
- [Use ternary condition operator to find min and max among three integers
](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question6.c)
- [Generate random numbers b/w 5 and 10, using probability given](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question7.c)
- [Write a program to print "Pascal's Triangle". ](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question8.c)
- [Write a program to find the sum of digits of a positive integer](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question9.c)
- [Write a program to print the numbers that do not appear in the Fibonacci series](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question10.c)
- [Write a function to find whether a positive integer is a power of two](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question11.c)
- [Find GCD of two positive numbers](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question12.c)
- [Write a function to check whether a positive integer is a palindrome or not](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question13.c)
- [Big question](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question14.c) (still to be done)
- [Find the maximum and minimum element in an array with a little tweak](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question15.c)
- [Given an array of integers, reverse the original array](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question16.c)
- [Implement the given functions in the matrix](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question17.c)
- [Write a program which will accept two strings and check whether all characters from the first string are present 
   in the second string](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question18.c)
- [Write a program to find the average of "n" integers entered by user](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question19.c)
- [Write a program with a function
   to remove all characters in a string except alphabetical characters](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question20.c)
- [Write a program to sort five words in "Lexicographical Order"](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question21.c)
- [Big question](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question22.c)
- [Another big question](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question23.c)
- [Yet another big question](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question24.c)
- [Find GCD and LCM of two numbers](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/general/question25.c)

--

## 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](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/misc/question1.c)
- [Find the length of the longest suffix which is also a prefix](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/misc/question2.c)
- [Sort a stack](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/misc/question66.c)
- [Given two strings a and b print whether they contain any common subsequence (non empty) or not.](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/misc/question67.c)

--

## Bit Manipulation

![Bit Manipulation](https://i.ibb.co/QQFW7MQ/bit.png)

- [Find set bits in an integer](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/bit-manipulation/question1.c)
- [Find if a number is a power of 2](https://github.com/Intervue/Data-structures-algorithms-for-interviews/blob/master/bit-manipulation/question2.c)

--

## Trie

![Trie](https://i.ibb.co/Chz2FTY/tries.png)

### 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:

  ```C
	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)

```C
//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](https://twitter.com/rahhularora)