Skip to content

Latest commit

 

History

History
113 lines (85 loc) · 2.6 KB

readme.md

File metadata and controls

113 lines (85 loc) · 2.6 KB
Raw

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


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