Quick Overview

This question evaluates a candidate's competency in algorithm design and data-structure reasoning for detecting n-length consecutive integer sequences, encompassing handling of duplicates, negative values, and dynamic insertions and deletions.

Detect n-length consecutive sequences

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an unsorted collection of integers and a parameter n > 0, determine whether there exists a set of n distinct integers that form a run of consecutive values (i.e., some x, x+1, ..., x+n- 1) regardless of order. If such a run exists, return any one such run; otherwise, return empty. Follow-ups: (a) Handle duplicates and negative numbers; (b) Achieve near-linear time using appropriate data structures; (c) Adapt the design to an online stream supporting insertions and deletions while answering queries about the existence of an n-length consecutive run.

Quick Answer: This question evaluates a candidate's competency in algorithm design and data-structure reasoning for detecting n-length consecutive integer sequences, encompassing handling of duplicates, negative values, and dynamic insertions and deletions.

Part 1: Detect a consecutive run in an unsorted distinct array

You are given an unsorted array of distinct non-negative integers and a positive integer n. Determine whether the array contains n distinct integers that form a consecutive run, such as x, x+1, ..., x+n-1, regardless of their order in the input. Return that run in increasing order. If multiple valid runs exist, return the one with the smallest starting value. If no such run exists, return an empty list.

Constraints

  • 0 <= len(nums) <= 100000
  • 0 <= nums[i] <= 10^9
  • All values in nums are distinct
  • 1 <= n <= 100000

Examples

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

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

Explanation: The numbers 1, 2, 3, and 4 are all present.

Input: ([10, 6, 7, 8, 20], 3)

Expected Output: [6, 7, 8]

Explanation: The array contains one run of length 3 starting at 6.

Hints

  1. Sorting the numbers can turn the problem into finding a long enough consecutive streak.
  2. Because all values are distinct in this version, you only need to compare adjacent sorted elements.

Part 2: Detect a consecutive run with duplicates and negative numbers

You are given an unsorted array of integers and a positive integer n. The array may contain duplicates and negative numbers. Determine whether there exist n distinct integers that form a consecutive run, such as x, x+1, ..., x+n-1. Duplicates do not increase the length of a run. Return the valid run with the smallest starting value in increasing order. If no such run exists, return an empty list.

Constraints

  • 0 <= len(nums) <= 100000
  • -10^9 <= nums[i] <= 10^9
  • Duplicates may appear in nums
  • 1 <= n <= 100000

Examples

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

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

Explanation: After ignoring duplicates, -2, -1, and 0 form a valid run.

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

Expected Output: [1, 2, 3]

Explanation: The duplicate 3 should count only once.

Hints

  1. Duplicates should be ignored when deciding whether values are consecutive.
  2. After removing duplicates, a sorted scan works even when numbers are negative.

Part 3: Find a consecutive run in near-linear time

You are given an unsorted array of integers and a positive integer n. The array may contain duplicates and negative numbers. Return the consecutive run of length n with the smallest starting value, or [] if no such run exists. Your goal is to design an average-case near-linear-time solution, so sorting the full input is not the intended approach.

Constraints

  • 0 <= len(nums) <= 200000
  • -10^9 <= nums[i] <= 10^9
  • Duplicates may appear in nums
  • 1 <= n <= 200000

Examples

Input: ([100, 4, 200, 1, 3, 2], 4)

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

Explanation: The classic consecutive run 1 through 4 is present.

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

Expected Output: [1, 2, 3]

Explanation: Both 1-3 and 10-12 work, so return the smaller start.

Hints

  1. A hash set gives O(1) average membership checks.
  2. Only try to grow a run from values whose predecessor is not present.

Part 4: Maintain consecutive runs in an online stream

You are given a fixed positive integer n and a sequence of online operations over a multiset of integers. Each operation is one of: [1, x] to insert x, [2, x] to delete one occurrence of x if present, or [3, 0] to query whether the current set of distinct values contains a consecutive run of length n. Duplicates matter for insertions and deletions, but a run is still defined using distinct values only. For each query, return the consecutive run of length n with the smallest starting value, or [] if none exists.

Constraints

  • 1 <= n <= 100000
  • 0 <= len(operations) <= 20000
  • -10^9 <= value <= 10^9
  • Delete on a value not currently present should be ignored
  • The stream is a multiset: a value disappears from the distinct set only when its count drops to 0

Examples

Input: (3, [[1, 5], [1, 1], [1, 2], [1, 3], [3, 0], [1, 10], [1, 11], [1, 12], [3, 0]])

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

Explanation: After the first four inserts, 1-3 exists. Later 10-12 also exists, but 1-3 has the smaller start.

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

Expected Output: [[-1, 0, 1], [], [], [-1, 0, 1]]

Explanation: Duplicates are counted, so deleting one 1 does not remove the value 1 entirely.

Hints

  1. Think in terms of maximal consecutive intervals of currently active distinct values.
  2. Keep a count for each value so duplicates only affect the structure when a count changes between 0 and 1.

Loading coding console...