/Competitive-Programming-Journey-for-Interviews

Primary LanguageC++

Topics and notes from my CP journey

Important

Common

Arrays

Questions
☆ Problem Solution
★☆☆ Subarray with given sum (1) Only non-negateive nos. (2) -ve nos. allowed, using hashmap (3) -ve nos. allowed, constant space

Tortoise and Hare algo

Stacks & Queues

Questions
☆ Problem Solution
★★★ Largest Rectangle in Histogram Link
★★★ Max Rectangle in Binary Matrix Link

Sorting

Linear time sorting

Strings

Manacher's Algorithm

Notes

  • Finding all sub-palindromes in O(N)

//TODO: find better video

  • Video explanation: Algorithm is not straigtforward, better to familiarize yourself first

  • Article: Contributed as a PR in this article, what I would have written in my notes.

Pattern matching

Notes

  • KMP

    • First think about naive algo. Place pattern P below ith index in string A. Then perform O(|P|) search. Repeat for order O(|A|) times.

    • Let i & j be traversing A and P respectively. Suppose in the first iteration, only the last letter of P does not match A, all before the last letter do match A. Then in the next iteration, i will have to be shifted back to i=1. This is the extra work.

    • // TODO: explain KMP

  • Rabin Karp

    • Pattern matching using rolling hash technique.

Z algorithm

Math

Binary exponentiation

Sieve of Eratosthenes

Notes

  • Algorithm for finding all the prime numbers in a segment [1:n] using O(nloglogn)

  • Prime number theorem: no. of primes less than n is approximately equal to n/ln(n).

  • Let there be k primes less than n. Thus the k ~= n/ln(n). Also, the kth prime no. is closest to n. Thus

k*ln(k) = {n/ln(n)}*{ln(n) - ln(ln(n))}
        ~= n
        ~= value of kth prime

        //TODO:

Fermat's little theorem

Compute nCr

Bit manipulation

Hash Map

Questions
☆ Problem Solution
★☆☆ Find subarray with given sum (with -ve numbers) GFG solution

DP

Questions
☆ Problem Solution
★☆☆ Longest Common Subsequence Link Video
★☆☆ Longest Increasing Subsequence //TODO: Video
★★☆ Longest Palindromic Subsequence Link
★★☆ Distinct Subsequences Video
★☆☆ Longest Palindromic Substring Video

Graph

DFS

  • Refer DFS implementation in dfs-recursive.cpp, dfs-iterative.cpp

  • Iterative DFS implementation comes in handy for many questions where you might not want to use recursion for DFS

  • Detect cycle using DFS

BFS

  • Detect cycle using BFS

Floyd-Warshall algo

Notes

  • Find the length of the shortest path dij between each pair of vertices i and j

  • -ve edges allowed, but not -ve cycles

  • Although, can be used to detect -ve cycles: if the dist of a vertex v from itself is negative.

  • Before the kth iteration, the d[i][j] contains the shortest distance between nodes i & j using only the nodes {1,2,...,k-1} in between i & j.

  • Proof by induction:

    • For k=0, d[i][j] == wt[i][j] if there exists and edge between i and j. Otherwise, d[i][j] == INF

    • Let the above claim be true for k. So for (k+1)th iteration there can only be two cases

      1. path between //TODO:

Minimum Spanning Tree (MST)

Topological sort

Questions
  • Refer CLRS (Ch: Graphs Algorithms -> DFS)

Strongly connected components (Tarjan’s Algo)

Notes

  • If a node has even a single outgoing edge, then it cannot be the one finshing last during DFS

  • Equivalently, if a node has only incoming edges and you reverse all the edges, then it will be the first one to finish.

Questions

  • Refer CLRS (Ch: Graphs Algorithms -> DFS)

  • Have a look at the implementation in scc.cpp

Bellman Ford's

Notes 
`s`           : source vertex
`|V|`         : num vertices
`d[v]`        : current smallest dist of v from s
`delta(s,v)`  : true shortest dist of v from s
  • Iterations: In each iteration, we go over all the edges. For each edge e, we update
d[e.second] = min (
  d[e.second],
  d[e.first] + e.cost
);

  • Total |V|-1 iterations: it is guaranteed that after k iterations, all nodes reachable from S would have d[v] == delta(s,v)

  • Correctness of algo: any shortest path to a node v from s can have at most |V|-1 edges in it. Thus, in |V|-1 iterations, we would have d[v] == delta(s,v) for all vertices v.

  • Existence of -ve cycle: If in |V|th iteration there is still a relaxtion possible (observed), then there definitely exists a -ve cycle

  • To find -ve cycle reachable from s: During the Vth iteration, let x be the last vertex for which a relaxation was made. x either lies on the cycle or is reachable from it. Then follow x's ancestors till you reach the -ve cycle. Going back |V| time from x will ensure that you are definitely in the -ve cycle. Then we can trace the cycle.

  • To find any -ve cycle: Initialize all d[v] to 0 (instead of INF), as if we were trying to find shortest path from all vertices simoltaneously. The validity of -ve cycle detection remains the same.

  • Gotchas:

    • If there are -ve edges, do not relax those edges yet which end on nodes that haven't even been discovered (aren't reachable in k edges if only k iterations are done). Because those nodes will have d[v]==INF and then new value could be INF-1, INF-2, etc.

    • When -ve cycle are present then d[] values could overflow (going below -INF). Take care of integer overflow.

  • Shorter path faster algorithm (SPFA)

    • takes advantage of the fact that not all attempts at relaxation will work. The main idea is to create a queue containing only the vertices that were relaxed but that still could further relax their neighbors. And whenever you can relax some neighbor, you should put it in the queue.

    • This too can be used to find -ve cycle.

    • Keep count of no. of relaxations for each node. If count[v] > |V|, then -ve cycle exists.

    • Keep track of all nodes in queue using a boolean array. Add to queue only if not already present.

    • Note: relaxation happens without caring about which nodes are in the queue. The only purpose of queue is to record all nodes that have been relaxed. A node in queue might even be relaxed twice before actually being processed.

Djikstra’s

Maxim Flow algo

Ford Fulkerson

Bipartite Graph

Finding negative cycles

Graph elegant solutions

Trees

Traversal

Imp concepts

Heaps

Notes

  • build_max_heap runs max_heapify from n/2 downto 1 only

  • Runtime of build_max_heap O(n) instead of O(nlogn) (). Still heapsort takes O(nlogn) time. See Reference-1 and Reference-2 below.

Binary search trees

AVL Trees

Segment trees

Notes

  • Used to find sum of range of indices in an array in O(logn) time. Brute force would take O(n) time for computing sum, O(1) time for value update

  • Leaf nodes are the array itself. Subsequent upper layer contain nodes which simply represent the sum of their own sub-tree.

  • Total no. of nodes in tree = n + n/2 + ... + 1

    = (2^(logn +1) - 1)/(2-1) = 2n -1

    = O(n) space

  • Time complexity for update is O(logn) since only one of the leaf values changes. Then you just have to change all its ancestors upto the root.

  • Sum(l,r) has left borer inclusive and right border exclusive.

Miscellaneous

  • Huffman Coding: Try to implement this on your own before looking at the code. It would require a mix of data structures to implement quick compression and decompression.

  • Majority element using BST

  • Majority element using Hashmap

  • Element in LL w/ freq >= N/3

  • Love Babbar suggest coding questions