Data Structures and Algorithms

  1. Sorting algorithms
    1. Bubble sort
    2. Insertion sort
    3. Merge sort
    4. Quick sort
      • Algorithm:
        1. Choose a pivot
        2. Partition the array around pivot. After partition, it is ensured that all elements are smaller than all right and we get index of the end point of smaller elements. The left and right may not be sorted individually.
        3. Recursively call for the two partitioned left and right subarrays.
        4. We stop recursion when there is only one element is left.
    5. Heap sort
  2. Search algorithms
    1. Binary search
  3. Evaluating time and space complexity
  4. What is a heap?
  5. What is a union find data structure?
  6. What are some common techniques to use in problem solving?
    1. Two pointers
    2. Sliding window
      1. multiple possible starting points? shrink and count left
    3. More than one pass
    4. Partitioning
    5. Fast and slow pointers
    6. Prefix sum
    7. Memorization (DP - subsequence)
    8. DFS / BFS
    9. Topological sort (dependencies i.e complete A before B)
    10. Bit manipulation
      • Optimize space complexity
    11. Sentinel node
      • Used to keep a reference for a node required later
    12. Monotonic stack / queue
      • Stack -> Finding the nearest smaller or larger element in a sequence for each element in the same sequence (link)
      • Queue -> Mostly used as a dynamic programming optimization technique or find nearest elements (link)
    13. Sorting
    14. Binary search (sorted input / shrink search space i.e min-max problem)
    15. Hashmap
    16. Modifying input memory in-place
    17. Line sweep algorithm
    18. Difference array for range update queries in O(1)
    19. Union find / Disjoint Set Union (check if connected components)
    20. Bitwise AND can only switch bits off -> result is always <= smallest number
    21. a AND a = a
    22. Digit DP -> find number of ... within a range that satisfy some property based on digits of integer
    23. Range -> transform to find(big) - find(small)
    24. Binary exponentiation, x^n == (x^2)^(n/2)
    25. fenwick/segment tree -> fast range sum and update
    26. stars and bars -> combinatorics
    27. total no. of subarrays -> nums.size() * (nums.size() + 1) / 2
    28. hamming distance -> number of diff characters between 2 strings (accounting for position as well)
    29. color nodes in a graph to partition them into odd/even
    30. arr to store next nearest biggest/smallest element for efficient lookups
    31. sort but maintain index
    32. serialisation/hashing to check same objects
  7. Do you know what is a bloom filter?
  8. What is Kadane's algorithm and when to use it?
  9. Algorithms for CP (link)