How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Solve Union-Find, Graph, and Stream Problems

Quick Overview

This question evaluates understanding of disjoint-set (union-find) operations, directed graph processing including cycle detection and ordering, contiguous subarray sum reasoning, and online streaming/anagram detection techniques, emphasizing data structures and algorithmic problem-solving.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following independent coding problems. ### 1. Merge Product Categories You are given a list of tuples `(productA, productB)`. Each tuple means the two products belong to the same category. Category membership is transitive: if `A` is in the same category as `B`, and `B` is in the same category as `C`, then `A`, `B`, and `C` are all in the same category. Return: 1. The total number of final categories. 2. The size of each category. Products may be represented as strings or integer IDs. ### 2. Validate and Produce a Course Schedule You are given `n` courses labeled `0` to `n - 1` and a list of prerequisite pairs `(a, b)`, meaning course `b` must be taken before course `a`. Return whether it is possible to complete all courses. If possible, output one valid course order. If impossible, report that a conflict cycle exists. ### 3. Detect a Zero-Sum Subarray Given an integer array, determine whether there exists a non-empty contiguous subarray whose sum is `0`. You only need to explain the approach. ### 4. Find Anagrams in a Character Stream Characters arrive one by one in a stream. Given a target word `target`, report every position where the most recent `len(target)` characters form an anagram of `target`. For example, if `target = "abc"`, then windows such as `"bca"`, `"cab"`, and `"abc"` should be reported when they appear in the stream. Design the solution so it works online as the stream arrives, without storing the entire stream.

Quick Answer: This question evaluates understanding of disjoint-set (union-find) operations, directed graph processing including cycle detection and ordering, contiguous subarray sum reasoning, and online streaming/anagram detection techniques, emphasizing data structures and algorithmic problem-solving.

Part 1: Merge Product Categories

You are given a list of product pairs, where each pair [a, b] means the two product names belong to the same category. Category membership is transitive, so if a is connected to b and b is connected to c, then all three are in the same final category. Only products that appear in at least one pair are counted. Return a list whose first element is the total number of final categories, followed by the size of each category in ascending order.

Constraints

0 <= len(pairs) <= 200000
Each pair contains exactly 2 product strings
Each product string has length between 1 and 50
Only products appearing in pairs are included in the result

Examples

Input: [['phone', 'tablet'], ['tablet', 'laptop'], ['chair', 'desk']]

Expected Output: [2, 2, 3]

Explanation: There are two categories: {phone, tablet, laptop} of size 3 and {chair, desk} of size 2.

Input: []

Expected Output: [0]

Explanation: No products appear, so there are zero categories.

Input: [['a', 'a']]

Expected Output: [1, 1]

Explanation: A self-pair still creates one category containing only a.

Input: [['book', 'pen'], ['cup', 'plate'], ['plate', 'fork'], ['lamp', 'lamp']]

Expected Output: [3, 1, 2, 3]

Explanation: The categories are {lamp}, {book, pen}, and {cup, plate, fork}.

Hints

Think of each product as a node in an undirected graph, and each pair as an edge.
A Disjoint Set Union structure can merge connected components efficiently.

Part 2: Validate and Produce a Course Schedule

You are given n courses labeled from 0 to n - 1 and a list of prerequisite pairs [a, b], meaning course b must be taken before course a. Return the lexicographically smallest valid order that completes all courses. If no valid order exists because the prerequisite graph contains a cycle, return an empty list.

Constraints

1 <= n <= 100000
0 <= len(prerequisites) <= 200000
0 <= a, b < n for every prerequisite pair [a, b]
Duplicate prerequisite pairs may appear

Examples

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: [0, 1, 2, 3]

Explanation: Course 0 must come first, then 1 and 2, then 3.

Input: (2, [[1, 0], [0, 1]])

Expected Output: []

Explanation: The prerequisites form a cycle, so no valid schedule exists.

Input: (1, [])

Expected Output: [0]

Explanation: A single course with no prerequisites can be taken directly.

Input: (5, [[2, 1], [2, 1], [3, 2]])

Expected Output: [0, 1, 2, 3, 4]

Explanation: Duplicate prerequisite edges should not change the result.

Hints

Use indegrees to track how many prerequisites each course still needs.
If you want deterministic output, always choose the smallest available course next.

Part 3: Detect a Zero-Sum Subarray

Given an integer array nums, determine whether there exists a non-empty contiguous subarray whose sum is exactly 0. Return True if such a subarray exists, otherwise return False.

Constraints

0 <= len(nums) <= 200000
-1000000000 <= nums[i] <= 1000000000
The array may contain positive, negative, and zero values

Examples

Input: [4, 2, -3, 1, 6]

Expected Output: True

Explanation: The subarray [2, -3, 1] sums to 0.

Input: [1, 2, 3]

Expected Output: False

Explanation: No contiguous subarray has sum 0.

Input: []

Expected Output: False

Explanation: There is no non-empty subarray in an empty array.

Input: [0]

Expected Output: True

Explanation: The single-element subarray [0] sums to 0.

Input: [1, -1, 2]

Expected Output: True

Explanation: The subarray [1, -1] sums to 0.

Hints

Track prefix sums as you move through the array.
If the same prefix sum appears twice, the elements between those positions sum to 0.

Part 4: Find Anagrams in a Character Stream

You are given a non-empty target string and a stream string that represents the order in which characters arrive. Each time the most recent len(target) characters form an anagram of target, record the 0-based starting index of that window. Return all such starting indices. The intended solution should process the stream online, storing only the current window and frequency information rather than the entire history.

Constraints

1 <= len(target) <= 100000
0 <= len(stream) <= 200000
target and stream may contain repeated characters
The expected solution uses O(len(target)) extra space besides the output list

Examples

Input: ('abc', 'cbaebabacd')

Expected Output: [0, 6]

Explanation: The windows 'cba' and 'bac' are anagrams of 'abc'.

Input: ('aab', 'aaab')

Expected Output: [1]

Explanation: Only the window 'aab' starting at index 1 matches.

Input: ('xyz', 'xy')

Expected Output: []

Explanation: The stream is shorter than the target, so no full window exists.

Input: ('a', 'baa')

Expected Output: [1, 2]

Explanation: Each single-character window equal to 'a' is an anagram of the target.

Hints

Use a sliding window of size len(target) and update counts as characters enter and leave the window.
Instead of comparing two full frequency maps every time, maintain a difference map between target and the current window.

Quick Overview