Number of Unique Categories

Number of Unique Categories

What is this problem about?

The Number of Unique Categories problem presents an interactive problem where you have n items, each belonging to one of several categories, but you can only discover categories through an API call haveSameCategory(a, b) that returns true if items a and b are in the same category. Find the total number of unique categories using the minimum number of API calls. This coding problem applies Union-Find with strategic querying.

Why is this asked in interviews?

Amazon asks this because it requires using Union-Find in an interactive context — grouping items by category while minimizing API usage. The efficient strategy: call haveSameCategory(0, i) for all i (n-1 calls), grouping all items in the same category as item 0. Then process remaining ungrouped items similarly. The union find, interactive, and counting interview pattern is applied.

Algorithmic pattern used

Union-Find with comparison to a reference. Call haveSameCategory(0, i) for i=1..n-1. Union all items returning true with item 0. For remaining ungrouped items, pick the first (call it j) and call haveSameCategory(j, k) for all remaining ungrouped k. Repeat. Count the number of Union-Find roots — that's the number of unique categories. Total calls: O(n) in the best case.

Example explanation

n=4 items. haveSameCategory(0,1)=true, (0,2)=false, (0,3)=false.

• Group: {0,1}, {2}, {3} so far.
• Call haveSameCategory(2,3)=true. Group: {0,1}, {2,3}.
• Unique categories = 2. Total calls = 4.

Common mistakes candidates make

• Calling all O(n²) pairs (far too many API calls).
• Not grouping items after each positive response.
• Forgetting to check remaining ungrouped items after the first reference group is complete.
• Not using Union-Find for O(α) group operations.

Interview preparation tip

Interactive Union-Find problems require designing a query strategy to minimize API calls while correctly grouping elements. The key insight: always compare against a known ungrouped reference item. After exhausting comparisons to one reference, pick a new unprocessed item as the next reference. This linear strategy finds all groups in O(n) total calls. Practice similar "find equivalence classes with minimal queries" problems — they test both algorithmic thinking and interactive problem-solving skills.