Top 10 graph problems?

Top 10 graph problems?



1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Shortest Path from source to all vertices *Dijkstra*
4. Shortest Path from every vertex to every other vertex *Floyd Warshall*
5. To detect cycle in a Graph *Union Find*
6. Minimum Spanning tree *Prim*
7. Minimum Spanning tree *Kruskal*
8. Topological Sort
9. Boggle (Find all possible words in a board of characters)
10. Bridges in a Graph

Popular posts from this blog

After analyzing the model, your manager has informed that your regression model is suffering from multicollinearity. How would you check if he's true? Without losing any information, can you still build a better model?

After analyzing the model, your manager has informed that your regression model is suffering from multicollinearity. How would you check if he's true? Without losing any information, can you still build a better model? Answer: To check multicollinearity, we can create a correlation matrix to identify & remove variables having correlation above 75% (deciding a threshold is subjective). In addition, we can use calculate VIF (variance inflation factor) to check the presence of multicollinearity. VIF value <= 4 suggests no multicollinearity whereas a value of >= 10 implies serious multicollinearity. Also, we can use tolerance as an indicator of multicollinearity. But, removing correlated variables might lead to loss of information. In order to retain those variables, we can use penalized regression models like ridge or lasso regression. Also, we can add some random noise in correlated variable so that the variables become different from each other. But, adding noise m...
Read more

Is rotation necessary in PCA? If yes, Why? What will happen if you don't rotate the components?

Is rotation necessary in PCA? If yes, Why? What will happen if you don't rotate the components? Answer: Yes, rotation (orthogonal) is necessary because it maximizes the difference between variance captured by the component. This makes the components easier to interpret. Not to forget, that's the motive of doing PCA where, we aim to select fewer components (than features) which can explain the maximum variance in the data set. By doing rotation, the relative location of the components doesn't change, it only changes the actual coordinates of the points. If we don't rotate the components, the effect of PCA will diminish and we'll have to select more number of components to explain variance in the data set.
Read more

Given that merge sort splits the array into 2, performs a recursive call on each of the 2 arrays, and repeats until the base case of 1 or less items in an array is reached, how many levels of recursion are there and why?

Given that merge sort splits the array into 2, performs a recursive call on each of the 2 arrays, and repeats until the base case of 1 or less items in an array is reached, how many levels of recursion are there and why? Answer: log₂n levels. Each level results in a split of an array n into arrays of size n/2. The number of levels equals the number of times you split n/2 until you reach 1 or less. The definition of log₂n is the number of times n is divided by two (split) until it reaches a value of 1 or less.
Read more