← PayPal Interview Insights

PayPal·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Mar 2026

Summary

PayPal coding screen, one graph problem about finding connected components in an adjacency matrix. Pretty standard stuff if you've done any graph prep.

Questions Asked (1)

Q1

Given an n x n matrix representing direct connections between cities, return the total number of provinces (i.e. connected components) in the graph.

Algorithms & Data Structures
Author's notes

Classic union-find or BFS/DFS question.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the matrix as an undirected graph where cities are nodes and direct connections are edges. Use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse each connected component, counting the number of times you initiate a traversal from an unvisited city. Alternatively, use Union-Find (Disjoint Set Union) to merge connected cities and count the number of distinct sets.

Pro tip: Clarify that the matrix is symmetric and represents an undirected graph, and mention that you can optimize space by using a 1D visited array instead of a 2D one. Also, discuss the trade-offs between DFS/BFS and Union-Find in terms of simplicity and performance.

1. Understand the problem

Confirm that the input is an n x n adjacency matrix where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a maximal set of directly or indirectly connected cities.

2. Choose an algorithm

Decide between graph traversal (DFS/BFS) or Union-Find. For interviews, DFS is often simpler to implement, but Union-Find can be more efficient for dynamic connectivity.

3. Implement traversal

If using DFS: initialize a visited array, iterate over all cities, and for each unvisited city, increment the province count and perform DFS to mark all connected cities as visited. If using Union-Find: initialize parent array, union all connected pairs, then count distinct roots.

4. Analyze complexity

For DFS: O(n^2) time and O(n) space. For Union-Find with path compression and union by rank: O(n^2 α(n)) time and O(n) space, where α is the inverse Ackermann function.

5. Test with examples

Walk through a small example, such as a 3x3 matrix with two provinces, to verify correctness. Consider edge cases like no connections (n provinces) or fully connected (1 province).

Key Points to Mention

  • Graph representation: adjacency matrix vs. adjacency list
  • Connected components and how to count them
  • DFS/BFS traversal and visited tracking
  • Union-Find (Disjoint Set Union) with path compression and union by rank
  • Time and space complexity analysis
  • Edge cases: n=1, no connections, fully connected

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.