Katkat
Back

Solve Three Algorithm Variants

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.
  1. 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".
  1. 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.