Basic Concepts for Coding Interviews

Data Structures	Algorithms	Concepts
Linked Lists	Breadth First Search	Bit Manipulation
Trees Tries & Graphs	Depth First Search	Memory(Stack vs Heap)
Stacks & Queues	Binary Search	Recursion
Heaps	Merge Sort	Duynamic Progrmming
Vectors/ArrayLists	Quick Sort	Big O Time & Space
Hash Tables
Arrays

Time and Space Complexity

Time Complexity ->

quanitfies the time taken by an algorithm to run as a function of the length of the input (not actual execution time of the machine on which the algorithms run on )

assume constant time(c) is taken to run one operation Ref

Length of input	Worst Accepted Algorithm
<= [10..11]	[O(N),O(N^6)]
<= [15..18]	[O(2^N*N^2)]
<= [18..22]	[O(2^N*N)]
<= [100]	[O(N^4)]
<= [400]	[O(N^3)]
<= [2000]	[O(N^2*logN)]
<= 10k	[O(N^2)]
<= [1M]	[O(N*logN)]
<= [100M]	[O(N),O(logN),O(1)]

Name	Notation
Contant	[O(1)]
Logarithmic	[O(log(N))]
Linear	[O(N)]
Log-Linear	[O(N log(N))]
Quadratic	[O(N^2)]
Cubic	[O(N^3)]
Exponential	[O(2^N)]
Factorial	[O(N!)]

Space Complexity ->

quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input

Solution guidelines

Input Type	Category	Review status
Input array is sorted	Binary Search, Two Pointers	✔️
asked for all permutations/subsets	Backtracking	❌
Binary Tree	BFS, DFS	✅
Graph	BFS, DFS	❌
Linked List	Two Pointers	✅
If Recursion not allowed	Stack	✅
In Place Traversal	Swap corresponding values	✔️
Mximum/MInimum subarray/subset/options	Dynamic Programing	✅
top/least k items	Heap	❌
Common Strings	Map, Trie	❌
Otherwise	Map/Set	✅