Ace your Coding Interview
Get hired by top tech companies with our comprehensive interview preparation.
Get StartedGiven a set of activities, along with the starting and finishing time of each activity, find the maximum number of activities performed by a single person assuming that a person can only work on a single activity at a time.
Given a set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest path weights d(s, v) from every source s for all vertices v present in the graph. If the graph contains a negative-weight cycle, report it.
Given a source vertex s from a set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest path weights d(s, v) from source s for all vertices v present in the graph. If the graph contains a negative-weight cycle, report it.
Given a source vertex s from a set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest path weights d(s, v) from source s for all vertices v present in the graph.
Given an undirected, connected and weighted graph, construct a minimum spanning tree out of it using Kruskal’s Algorithm.
Given an undirected connected graph, check if it contains any cycle or not using the union–find algorithm.
Given a chessboard, find the shortest distance (minimum number of steps) taken by a knight to reach a given destination from a given source.
This post explains the working of disjoint-set data structure (also called union find data structure). A disjoint-set is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Given an undirected connected graph, check if the graph is 2–edge connected or not. A connected graph is 2–edge connected if it remains connected whenever any edges are removed.
The transitive closure for a digraph G is a digraph G’ with an edge (i, j) corresponding to each directed path from i to j in G. The resultant digraph G’ representation in the form of the adjacency matrix is called the connectivity matrix.
Given a Directed Acyclic Graph (DAG), print it in topological order using topological sort algorithm. If the DAG has more than one topological ordering, output any of them.
Find the minimum number of throws required to win a given Snake and Ladder game. For example, the following game requires at least 7 dice throws to win.