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 Technical Screen 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 Three Algorithm Variants | Amazon Coding Question

Quick Overview

This multi-part question evaluates combinatorics and permutation generation, tree traversal and node-relationship classification, and array/sequence processing under bounded-gap constraints, measuring algorithmic design, complexity reasoning, and data-structure manipulation within the Coding & Algorithms domain.

Solve Three Algorithm Variants

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given three independent coding problems. For each one, describe and implement an efficient solution. 1. **Generate queue arrangements** - You are given `n` distinct students, represented by unique IDs. - Return all possible ways to arrange the students in a line. - Follow-up: return all distinct ways to arrange the same students in a circle, where rotations are considered the same arrangement. Reversed order should still be considered different unless explicitly stated otherwise. 2. **Classify the relationship between two tree nodes** - You are given the root of a tree and two target nodes that may appear in the tree. - Return: - `"siblings"` if the two nodes have the same parent, - `"cousins"` if the two nodes are at the same depth but have different parents, - `"others"` otherwise. - If either target node does not exist in the tree, return `"others"`. 3. **Find the longest bounded-gap sequence** - You are given an unsorted integer array `nums` and a positive integer `k`. - Find the maximum length of a sequence of distinct values `x1 < x2 < ... < xm` chosen from `nums` such that every adjacent pair satisfies `xi+1 - xi < k`. - Duplicates in `nums` do not increase the length of the sequence. - Return the maximum possible length.

Quick Answer: This multi-part question evaluates combinatorics and permutation generation, tree traversal and node-relationship classification, and array/sequence processing under bounded-gap constraints, measuring algorithmic design, complexity reasoning, and data-structure manipulation within the Coding & Algorithms domain.

Part 1: Generate Queue Arrangements

Given a list of distinct student IDs, return every possible way to arrange the students in a straight line. The returned arrangements should follow the deterministic order produced by choosing the next unused student from left to right in the input list.

Constraints

0 <= len(students) <= 8
All student IDs are distinct integers
Because the output size is factorial, n is intentionally small

Examples

Input: []

Expected Output: [[]]

Explanation: There is exactly one permutation of an empty list: the empty arrangement.

Input: [7]

Expected Output: [[7]]

Explanation: A single student has only one possible position.

Input: [1, 2]

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

Explanation: Both possible linear orders are returned.

Input: [1, 2, 3]

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

Explanation: The permutations are generated in left-to-right backtracking order.

Hints

Think about building the arrangement one position at a time.
Keep track of which students have already been used in the current partial arrangement.

Part 2: Generate Circular Queue Arrangements

Given a list of distinct student IDs, return all distinct circular arrangements where rotations are considered the same arrangement. To make the output representation unique, represent every circle as a list that starts with the first student from the input list. Reversed order is still considered different.

Constraints

0 <= len(students) <= 9
All student IDs are distinct integers
Rotations are considered identical, but reversed orders are different

Examples

Input: []

Expected Output: [[]]

Explanation: There is one empty circular arrangement.

Input: [9]

Expected Output: [[9]]

Explanation: A single student forms exactly one circle.

Input: [1, 2, 3]

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

Explanation: Fixing 1 removes rotational duplicates, leaving two distinct circles.

Input: [1, 2, 3, 4]

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

Explanation: With 4 distinct students, there are (4 - 1)! = 6 distinct circular arrangements.

Hints

If rotations are the same, you can fix one student in place and only permute the others.
Using the first input student as the fixed anchor makes the output deterministic.

Part 3: Classify the Relationship Between Two Tree Nodes

You are given a rooted tree and two target node values. The tree is represented as nested tuples of the form (value, children), where children is a list of child nodes in the same format. Return 'siblings' if the targets share the same parent, 'cousins' if they are at the same depth but have different parents, and 'others' otherwise. If either target does not exist in the tree, return 'others'.

Constraints

0 <= number of nodes <= 100000
All node values in the tree are unique integers
The tree is rooted and acyclic

Examples

Input: ((1, [(2, [(4, []), (5, [])]), (3, [(6, []), (7, [])])]), 4, 5)

Expected Output: 'siblings'

Explanation: Nodes 4 and 5 share the same parent, node 2.

Input: ((1, [(2, [(4, []), (5, [])]), (3, [(6, []), (7, [])])]), 4, 6)

Expected Output: 'cousins'

Explanation: Nodes 4 and 6 are at the same depth but have different parents.

Input: ((1, [(2, [(4, []), (5, [])]), (3, [(6, []), (7, [])])]), 2, 4)

Expected Output: 'others'

Explanation: Nodes 2 and 4 are at different depths, so they are neither siblings nor cousins.

Input: ((1, [(2, [(4, []), (5, [])]), (3, [(6, []), (7, [])])]), 4, 99)

Expected Output: 'others'

Explanation: Node 99 does not exist in the tree.

Input: (None, 1, 2)

Expected Output: 'others'

Explanation: An empty tree cannot contain either target.

Hints

For each target, you only need two facts: its parent and its depth.
A single DFS or BFS traversal can collect both targets' information.

Part 4: Find the Longest Bounded-Gap Sequence

Given an unsorted integer array nums and a positive integer k, find the maximum length of a sequence of distinct values x1 < x2 < ... < xm chosen from nums such that every adjacent difference is strictly less than k. Duplicates in nums do not increase the length.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
1 <= k <= 10^9

Examples

Input: ([], 3)

Expected Output: 0

Explanation: No numbers means no valid sequence.

Input: ([7], 5)

Expected Output: 1

Explanation: A single distinct value forms a sequence of length 1.

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

Expected Output: 1

Explanation: For distinct integers, every positive gap is at least 1, so no adjacent pair can satisfy gap < 1.

Input: ([4, 1, 2, 10, 6], 3)

Expected Output: 4

Explanation: Using distinct sorted values [1, 2, 4, 6, 10], the longest valid block is [1, 2, 4, 6].

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

Expected Output: 2

Explanation: After deduplication, the best sequences are [1, 2] and [5, 6], both of length 2.

Hints

Duplicates never help, so try removing them first.
After sorting the distinct values, the answer becomes the longest consecutive block whose neighboring gaps are all less than k.

Quick Overview