Katkat
Back

Solve three coding tasks: binary search, tree path, subarray

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Solve three coding tasks: binary search, tree path, subarray states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Solve the following coding tasks:

  1. In a sorted array, every value appears exactly twice except for one value that appears once. Find the single value in O(log n) time and O(

  2. extra space using a binary-search-based approach.

  3. Given the root of an N-ary tree and a sequence of integers representing a path, determine whether this path exists in the tree. Each node may have multiple children and values are not guaranteed to be unique. A valid path must start from the root but does not need to end at a leaf node. Return true/false and analyze time and space complexity.

  4. Given two integer arrays, compute the maximum length of a contiguous subarray that appears in both arrays. Discuss multiple approaches (e.g., dynamic programming; binary search on length with rolling hash) and their time/space trade-offs.