# CTCI list

Here is the leetcode list for CTCI questions

Some questions are not present in the list so I have included them here

Here we do only need to replace the spaces in between words not the trailing spaces add (2*no_of_spaces) more as 1 space will already be…

# Binary Search

Note : In coding rounds, always use mid= low+(high-low)/2 instead of (low+high)/2 to pass 2 critical test cases else overflow error comes (they genuinely add these cases to test your coding skills

You use `while (start <= end)` if you are returning the match from inside the loop.

You use…

# Floyd Warshall (DP)

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. …

# Dijkstra’s shortest path algorithm

Relaxation Rule :

`dist[v] = min( dist[v], (dist[u] + cost[u,v] )`

# Bipartite graphs

• If a graph has no cycle or even length cycle then it is Bipartite if cycle length is odd it is not Bipartite
• If a graph can be colored using 2 colors such that adjacent nodes have different color then we can say that it is Bipartite
• Formal definition :

# DFS

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. Stacks are used here (either explicitly or using recursion implicitly)

• Algorithm:
1. Create a recursive function that takes the index of node…

# Graph Representation

Note : if no of edges is N & no of vertices is M then

if value of nodes are 0-indexed i.e 0,1,2,3,,,, then adjacency matrix and list are of size M+1,N+1 for matrix && N+1 for list

else if 1 based indexed then take M,N & N only

# BFS

Resources

`vector<int>bfsOfGraph(int V, vector<int> adj[]){     vector<int> ans;      vector<bool> vis(V, false);      queue<int> q;      q.push(0);      vis = true;      while(!q.empty()) {         int curr= q.front();         q.pop();          ans.push_back(curr);                   for(auto it : adj[curr]) {             if(!vis[it]) {                 q.push(it); …` 