Frontend School

Consistent Order Segment

DSA
medium

Consistent Order Segment

Medium
Arrays
Hashing
Sliding Window

Overview

At Blinkit, understanding customer purchasing habits is crucial for optimizing inventory, personalizing recommendations, and improving the overall shopping experience. One area of interest is identifying "consistent order segments" within a larger customer order. A consistent order segment is a contiguous sequence of items where every unique item within that segment has been purchased at least a certain number of times within that same segment. This problem asks you to determine if such a segment exists in a given order.

What you need to do / Task

You are given an array of integers itemIds, representing a sequence of item IDs in a customer's order, and an integer k. Your task is to implement a function hasConsistentOrderSegment that returns true if there exists at least one contiguous subarray (segment) within itemIds such that every distinct item ID in that subarray appears k or more times within that same subarray. Otherwise, the function should return false.

Input & output

The function hasConsistentOrderSegment takes two parameters:

  • itemIds: An array of integers, where each integer represents a unique item ID.
  • k: An integer, representing the minimum required frequency for each distinct item within a valid segment.

The function should return:

  • A boolean value: true if a consistent order segment exists, false otherwise.

Clarifications

  • An empty subarray is not considered a valid segment. A valid segment must have at least one element.
  • If k is 1, any non-empty subarray is considered valid, provided it has at least one distinct element (which will trivially appear at least once).
  • Item IDs can be any positive integer.

Examples

1

Example 1

Input:

itemIds = [1, 2, 1, 2, 3, 4], k = 2

Output:

true

Note:

The subarray [1, 2, 1, 2] from index 0 to 3 is a consistent order segment. Distinct items are 1 and 2. Item 1 appears 2 times, and item 2 appears 2 times. Both frequencies meet or exceed k=2.

2

Example 2

Input:

itemIds = [5, 5, 5, 5], k = 3

Output:

true

Note:

The subarray [5, 5, 5] from index 0 to 2 is a consistent order segment. The only distinct item is 5, which appears 3 times. This meets or exceeds k=3.

3

Example 3

Input:

itemIds = [1, 2, 3, 4, 5], k = 2

Output:

false

Note:

In this array, all items are unique. Therefore, no item can appear 2 or more times in any subarray. Thus, no consistent order segment exists for k=2.

Constraints

Constraints & assumptions

  • 1 <= itemIds.length <= 10^5
  • 1 <= itemIds[i] <= 10^9 (Item IDs are positive integers)
  • 1 <= k <= itemIds.length

What interviewers evaluate

  • Correctness: Does the solution correctly identify if a consistent order segment exists for all valid inputs?
  • Efficiency: Is the solution optimal in terms of time and space complexity? (Aim for O(N) time and O(D) or O(N) space, where D is number of distinct items).
  • Code Quality: Is the code well-structured, readable, and does it handle edge cases gracefully?
  • Problem-solving approach: Can the candidate clearly articulate their thought process, explore different approaches, and justify their chosen solution?

Loading editor...