The interviewprep from shyrenmore

interviewprep's Introduction

A new visitor?

you can refer readmes of

LinkedList
Corner cases
- empty LL
- LL with one node
Arrays
for every array quest, you should ask the interviewer if not already specified:
- is the array sorted?
- minimum no of elements in array?
- does the array contain negative elements
  Corner cases
- would the code run properly if n=1?
Matrix
Sorting
Stack
Queue
Hashing
Dynamic Programming
Graph
Corner cases
- would the dfs code run properly for 1x1 matrix?

What is this repo about?

Interview prep

Work in progress

Trees and graph
Trie

Some resources and hacks

Cheatsheet for time and space complexity: https://www.bigocheatsheet.com/
The below tips are taken from here


If input array is sorted then
    - Binary search
    - Two pointers

If asked for all permutations/subsets then
    - Backtracking

If given a tree then
    - DFS
    - BFS

If given a graph then
    - DFS
    - BFS

If given a linked list then
    - Two pointers

If recursion is banned then
    - Stack

If must solve in-place then
    - Swap corresponding values
    - Store one or more different values in the same pointer

If asked for maximum/minumum subarray/subset/options then
    - Dynamic programming

If asked for top/least K items then
    - Heap

If asked for common strings then
    - Map
    - Trie

Else
    - Map/Set for O(1) time & O(n) space
    - Sort input for O(nlogn) time and O(1) space

Comparison of operations b/w common DS

Operation	Unsorted Arr	Sorted Arr	Linked List	BST(Balanced)	Hash Table
Search	O(n)	O(logn)	O(n)	O(logn)	O(1)
Insert	O(1)	O(n)	O(1) for sorted LL: O(n)	O(logn)	O(1)
Delete	O(n)	O(n)	O(n)	O(logn)	O(1)
Get Closest value	O(n)	O(logn)	O(n)	O(logn)	O(1)
Sorted Traversal	O(nlogn)	O(n)	O(nlogn)/ O(n) for sorted LL	O(n)	O(nlogn)

Here sorted traversal implies printing items in sorted order

Identifying the solution methodology by looking at constraints

upto n<=10^3 naive sols will work most of the times

n-value	Maximum time it can take
n <= 12	O(n!)
n <= 25	O(2^n)
n <= 100	O(n^4)
n <= 500	O(n^3)
n <= 10^4	O(n^2)
n <= 10^6	O(nlogn) - sorting
n <= 10^8	O(n) - hashing
n > 10^8	O(logn) or O(1) - binary search

Recommend Projects