Collections of Resources I collected during my Internship Interview Prepration. I had spent significant amount of time for choosing resources while styding and have mentioned them with topics for easy reading. Will add Questions soon!.
Free Resources to study/ revise each of the topics which I felt were concise and good enough.
| Topic | Resource |
|---|---|
| Graph (Basics/Theory) | Basics and Representing Graph , Depth First Search and Breath First Search. |
| Graph (Programming) | Topcoder Tutorial |
| Graph Traversals (Programming and Applications) | DFS and BFS |
| Dynamic Programming | Dynamic Programming-Topcoder |
| Dynamic Programming (How to Approach) | 7 Steps to Solve DP Problems |
- A Linked List is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.
- Singly-linked list: linked list in which each node points to the next node and the last node points to null
- Doubly-linked list: linked list in which each node has two pointers, p and n, such that p points to the previous node and n points to the next node; the last node's n pointer points to null
- Circular-linked list: linked list in which each node points to the next node and the last node points back to the first node
- Time Complexity:
- Access:
O(n) - Search:
O(n) - Insert:
O(1) - Remove:
O(1)
- Access:
Try to know optimal/various solutions(even in no. of passes/traversals and space) because other than that their are not much in Linked Lists. Also for Linked List search various solutions even if you got optimal, you will learn many tricks on how to traverse etc in each case.
- Reverse the Linked List (Recursive and Iterative)
- Intersection of Two Linked Lists
- Remove Nth Node From End (try it in one pass).
- Reorder List.
- Separate Even/Odd nodes in LL
- Clone LinkedList with Random Pointer
- LinkList Cycle Detection
- LinkList Cycle Removal and also the gfg one
- Pairwise Swap linkedList Nodes
- Reverse LL in Group of K
- LRU cache (optional)
Special(Applications in non-trivial form)
Even Nodes/Odd Nodes (also Single or Two Nodes) and list has cycle
- A Stack is a collection of elements, with two principle operations: push, which adds to the collection, and pop, which removes the most recently added element
- Last in, first out data structure (LIFO): the most recently added object is the first to be removed
- Time Complexity:
- Access:
O(n) - Search:
O(n) - Insert:
O(1) - Remove:
O(1)
- Access:
Questions directly on stack are very limited, the real applications of stack are in Graph/Tree Traversals. Also understand both List and Array implementation of stack.
- Min/Max Stack (Remembe O(1) )
- Implement Queue using Stack
- Backspace String Compare
- Valid Stack Sequence
- Valid Parenthesis
- Minimum Deletion to make valid Paranthesis.
- Minimum add to make parenthesis valid
- Score of Parenthesis
- Decode String (Something New!)
- Longest Valid Parenthesis (Challenge)
- Maximal Rectangle (optional)
- Trapping Rainwater (optional)
- A Queue is a collection of elements, supporting two principle operations: enqueue, which inserts an element into the queue, and dequeue, which removes an element from the queue
- First in, first out data structure (FIFO): the oldest added object is the first to be removed
- Time Complexity:
- Access:
O(n) - Search:
O(n) - Insert:
O(1) - Remove:
O(1)
- Access:
Applications of Queues in other techniques is very prevalent like Sliding Windows, Priority Queue, BFS so grasp basic concepts properly.
- Implementation (Array and LinkedList)
- Deque (Implementaion)
- Design Circular Queue
- Design Circular Deque
- A Matrix is a @-Diensional Array.Every element of the array is an array of fixed Size then it forms an Matrix. Many times Matrix Questions can also be solved by imaginig matrix as a Graph and adjacent cells as connected nodes so.
- Rotate Image (for anti-clockwise also).
- Spiral Traversal of Matrix
- Search a 2-D Matrix
- [Set Matrix Zeros] (https://leetcode.com/problems/set-matrix-zeroes/)
- Kth Smallest Element
- A Tree is an undirected, connected, acyclic graph
- A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and right child
- Full Tree: a tree in which every node has either 0 or 2 children
- Perfect Binary Tree: a binary tree in which all interior nodes have two children and all leave have the same depth
- Complete Tree: a binary tree in which every level except possibly the last is full and all nodes in the last level are as far left as possible
- A binary search tree, sometimes called BST, is a type of binary tree which maintains the property that the value in each node must be greater than or equal to any value stored in the left sub-tree, and less than or equal to any value stored in the right sub-tree.
- Time Complexity:
- Access:
O(log(n)) - Search:
O(log(n)) - Insert:
O(log(n)) - Remove:
O(log(n))
- Access:
- A Heap is a specialized tree based structure data structure that satisfies the heap property: if A is a parent node of B , then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the entire heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node
- Time Complexity:
- Access Max / Min:
O(1) - Insert:
O(log(n)) - Remove Max / Min:
O(log(n))
- Access Max / Min:
- Hashing is used to map data of an arbitrary size to data of a fixed size. The values returned by a hash function are called hash values, hash codes, or simply hashes. If two keys map to the same value, a collision occurs
- Hash Map: a hash map is a structure that can map keys to values. A hash map uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
- Collision Resolution
- Separate Chaining: in separate chaining, each bucket is independent, and contains a list of entries for each index. The time for hash map operations is the time to find the bucket (constant time), plus the time to iterate through the list
- Open Addressing: in open addressing, when a new entry is inserted, the buckets are examined, starting with the hashed-to-slot and proceeding in some sequence, until an unoccupied slot is found. The name open addressing refers to the fact that the location of an item is not always determined by its hash value
- A Graph is an ordered pair of G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or arcs, which are 2-element subsets of V (i.e. an edge is associated with two vertices, and that association takes the form of the unordered pair comprising those two vertices)
- Undirected Graph: a graph in which the adjacency relation is symmetric. So if there exists an edge from node u to node v (u -> v), then it is also the case that there exists an edge from node v to node u (v -> u)
- Directed Graph: a graph in which the adjacency relation is not symmetric. So if there exists an edge from node u to node v (u -> v), this does not imply that there exists an edge from node v to node u (v -> u)
- Stable:
No - Time Complexity:
- Best Case:
O(nlog(n)) - Worst Case:
O(n^2) - Average Case:
O(nlog(n)) - Improvement:
RandomizedQuick-Sort.
- Best Case:
- Mergesort is also a divide and conquer algorithm. It continuously divides an array into two halves, recurses on both the left subarray and right subarray and then merges the two sorted halves
- Stable:
Yes - Time Complexity:
- Best Case:
O(nlog(n)) - Worst Case:
O(nlog(n)) - Average Case:
O(nlog(n))
- Best Case:
- Depth First Search is a graph traversal algorithm which explores as far as possible along each branch before backtracking
- Time Complexity:
O(|V| + |E|)
- Breadth First Search is a graph traversal algorithm which explores the neighbor nodes first, before moving to the next level neighbors
- Time Complexity:
O(|V| + |E|)
- Topological Sort is the linear ordering of a directed graph's nodes such that for every edge from node u to node v, u comes before v in the ordering
- Time Complexity:
O(|V| + |E|)
- Dijkstra's Algorithm is an algorithm for finding the shortest path between nodes in a graph
- Time Complexity:
O(|V|^2)
- Bellman-Ford Algorithm is an algorithm that computes the shortest paths from a single source node to all other nodes in a weighted graph
- Although it is slower than Dijkstra's, it is more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers
- Time Complexity:
- Best Case:
O(|E|) - Worst Case:
O(|V||E|)
- Best Case:
- Floyd-Warshall Algorithm is an algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights, but no negative cycles
- A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of nodes
- Time Complexity:
- Best Case:
O(|V|^3) - Worst Case:
O(|V|^3) - Average Case:
O(|V|^3)
- Best Case:
- Prim's Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. In other words, Prim's find a subset of edges that forms a tree that includes every node in the graph
- Time Complexity:
O(|V|^2)
- Kruskal's Algorithm is also a greedy algorithm that finds a minimum spanning tree in a graph. However, in Kruskal's, the graph does not have to be connected
- Time Complexity:
O(|E|log|V|)
(Go to Approaches)
If input array is sorted then
- Binary search
- Two pointers
- Upper_bound lower_bound
If given a Tree/Graph then
- DFS
- BFS
If asked/generate all permutations/subsets then
- Backtracking
If asked to generate any/all solutions
- Backtracking
If very complex counting kind problem ( N < 50 )
- Backtracking
If feel like multiple nested for loops whose numbers depend upon conditional input
- backtracking
If given a linked list then
- Two pointers
If linklist backtraversing pointer needed then
- Recursion (Head Recursion)
If recursion is banned/TLE then
- Stack
If asked for maximum/minumum subarray/subset/options then
- Dynamic programming
If asked for counting then
- Dynamic programming (Optimising Backtracking)
If most subproblems are needed/Tighter Constraints in DP then
- Tabulation in DP
If BruteForce Recursion fails then :
- Recursion + store solved sub-problems (Memoization).
If asked for top/least K items then
- Heap
If asked for common strings then
- Map
- Trie
If O(1) operations needed then
- map or unordered_map
If O(logn) time operations needed then
- set , multi_set
If find first/Number of elements greater than/equal to then
- lower_bound, upper_bound (in sorted )