Questions
23 of 59
1What is a Graph? Define Vertex, Edge, Degree.
2What is the difference between Directed and Undirected Graphs?
3What is a Weighted Graph?
4What is a Cyclic vs Acyclic Graph?
5What is the difference between a Tree and a Graph?
6Explain Adjacency Matrix. What are its pros and cons?
7Explain Adjacency List. What are its pros and cons?
8Which representation is better for Sparse vs Dense graphs?
9Explain Breadth-First Search (BFS). What data structure does it use?
10Explain Depth-First Search (DFS). What data structure does it use?
11What is the time complexity of BFS and DFS?
12What is Topological Sorting? Which algorithm is used?
13How do you detect a cycle in a Directed Graph?
14How do you detect a cycle in an Undirected Graph?
15Explain Dijkstra's Algorithm. When does it fail?
16Explain Bellman-Ford Algorithm. Why is it slower than Dijkstra?
17What is the difference between Dijkstra and A* (A-star)?
18What is a Minimum Spanning Tree (MST)?
19Explain Kruskal's Algorithm. Which data structure is crucial for it?
20Explain Prim's Algorithm.
21What is the difference between Kruskal's and Prim's? When is one preferred?
22What is Union-Find (Disjoint Set Union)? Explain Path Compression and Union by Rank.
23What is a Bipartite Graph? How do you check for it?
24How do you find the shortest path in an unweighted graph?
25Explain Strongly Connected Components (Kosaraju/Tarjan).
26What is a Directed Acyclic Graph (DAG)? Why are they important in build systems?
27How do you solve a Maze using Graph algorithms?
28Explain Floyd-Warshall Algorithm (All Pairs Shortest Path).
29How do you detect a Deadlock using a Graph?
30What is the difference between Linear Search and Binary Search?
31What is the precondition for Binary Search?
32Write down the time complexities of Bubble, Selection, Insertion Sort.
33Why is Insertion Sort preferred for small or nearly sorted arrays?
34Explain Merge Sort. What is its time and space complexity?
35Explain Quick Sort. What is its worst-case complexity? How do you avoid it?
36Compare Merge Sort vs Quick Sort. When do you choose which?
37What is Heap Sort? How does it work?
38Is Heap Sort stable? Is Merge Sort stable?
39What is Counting Sort? What are its limitations?
40What is Radix Sort? How does it handle strings?
41What is the fastest possible time complexity for a comparison-based sort? Why?
42What is the difference between Internal and External Sorting?
43How do you find the k-th largest element in an array?
44How do you find the median of a stream of numbers?
45What is a Bucket Sort? When is it effective?
46Explain the concept of Stability in sorting. Why does it matter for multi-key sorting?
47What is a Persistent Data Structure?
48What is a Treap? How does it combine BST and Heap properties?
49What is a Bloom Filter? How do you calculate the False Positive rate?
50What is an LRU Cache? How do you implement it using a Hash Map and Doubly Linked List?
51What is an LFU Cache? How is it different from LRU?
52What is a Suffix Tree/Array? What string problems does it solve?
53What is a Van Emde Boas tree?
54How do you design a Data Structure that supports insert, delete, search, and getRandom in O(1)?
55What is the Median of Medians algorithm? Why is it better than random pivot selection?
56Explain the concept of Cache Oblivious algorithms.
57What is the difference between a Binary Heap and a Fibonacci Heap? Why is Fibonacci Heap theoretically faster for Dijkstra's?
58How are Data Structures used in Database Indexing? (B+ Trees, Hash Indexes)
59How does the Garbage Collector interact with data structures? (Weak references, Gen0/Gen1/Gen2)
Data-StructuresData-Structures
Basics
Complexity Analysis
Arrays and Strings
Linked Lists
Stacks and Queues
Hash Tables
Trees
Graphs
23 / 59

What is a Bipartite Graph? How do you check for it?

Difficulty: 4/10

Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects vertices from different sets. A standard way to test this is graph coloring with two colors using BFS or DFS. If an edge connects two vertices having the same color, the graph is not bipartite.

javascript
  1. 1

    Use two colors.

  2. 2

    Adjacent vertices must have different colors.

  3. 3

    BFS or DFS can perform the coloring.

  4. 4

    A graph is bipartite if and only if it contains no odd-length cycle.

  5. 5

    Complexity: O(V+E).

Follow-up Questions

  • Why does an odd cycle make a graph non-bipartite?
  • Can a disconnected graph be bipartite?
Share

Share via WhatsApp, X, Facebook, LinkedIn or copy link. Open Graph preview enabled.