Frontend School

Dark Store Inventory Optimization

DSA
hard

Dark Store Inventory Optimization

Hard
Segment Tree
Lazy Propagation
Arrays

Overview

Blinkit's rapid delivery model relies heavily on efficient inventory management across its network of local dark stores. Each dark store maintains stock levels for thousands of items. For a critical, fast-moving item, it's crucial to have real-time insights into stock availability and the ability to quickly adjust inventory. This problem simulates a core part of that system, focusing on optimizing operations for a single item across multiple dark stores.

What you need to do / Task

You are tasked with implementing a system to manage the stock levels of a single item across N dark stores. Your system must efficiently handle a sequence of operations:

  1. Initialize Stock: Set up the initial stock levels for all N dark stores.
  2. Point Stock Adjustment (Type 1): Adjust the stock of a specific dark store (e.g., darkStore[i] += value). This could represent a single sale or a small incoming delivery.
  3. Range Stock Adjustment (Type 2): Adjust the stock for a contiguous range of dark stores (e.g., darkStore[j...k] += value). This is typical for bulk regional promotions or large-scale incoming deliveries affecting multiple stores.
  4. Range Minimum Stock Query (Type 3): Find the minimum stock level within a given contiguous range of dark stores. This is vital for identifying potential stock-out risks or determining the minimum available capacity for an order across a delivery zone.

Your function should process all operations and return a list of results for each RANGE_MIN_QUERY operation in the order they appear.

Input & output

Function Signature:

function processDarkStoreOperations(initialStocks: number[], operations: Array<[number, number, number, number?] | [number, number, number]>): number[]

Parameters:

  • initialStocks: A number[] representing the initial stock levels for N dark stores. initialStocks[i] is the stock at dark store i.
  • operations: An array of operations to perform. Each operation is an array following one of these formats:
    • [1, index, valueChange]: Point Stock Adjustment. Adds valueChange to initialStocks[index]. index is 0-based.
    • [2, startIndex, endIndex, valueChange]: Range Stock Adjustment. Adds valueChange to initialStocks[i] for all i such that startIndex <= i <= endIndex. startIndex and endIndex are 0-based and inclusive.
    • [3, startIndex, endIndex]: Range Minimum Stock Query. Returns the minimum stock level among initialStocks[i] for all i such that startIndex <= i <= endIndex. startIndex and endIndex are 0-based and inclusive.

Return Value:

  • A number[] containing the results of all RANGE_MIN_QUERY operations, in the order they were processed.

Clarifications

  • All stock levels must remain non-negative. If an operation causes a stock level to drop below zero, it should be capped at 0.
  • All indices (index, startIndex, endIndex) are 0-based.
  • Ranges ([startIndex, endIndex]) are inclusive.

Examples

1

Example 1

Input:

initialStocks = [10, 20, 5, 15], operations = [[3, 0, 3], [1, 2, 8], [3, 0, 3], [3, 1, 2]]

Output:

[5, 10, 13]

Note:

  1. Initial stocks: [10, 20, 5, 15]
  2. Query min in [0,3]: min([10,20,5,15]) = 5. Result: [5]
  3. Point adjust at index 2 by +8: stocks[2] becomes 5+8=13. Stocks: [10, 20, 13, 15]
  4. Query min in [0,3]: min([10,20,13,15]) = 10. Result: [5, 10]
  5. Query min in [1,2]: min([20,13]) = 13. Result: [5, 10, 13]
2

Example 2

Input:

initialStocks = [10, 2, 15, 8], operations = [[3, 0, 3], [2, 0, 1, -5], [3, 0, 3], [2, 2, 3, 10], [3, 0, 3], [1, 1, 20], [3, 0, 3]]

Output:

[2, 0, 0, 5]

Note:

  1. Initial stocks: [10, 2, 15, 8]
  2. Query min in [0,3]: min([10,2,15,8]) = 2. Result: [2]
  3. Range adjust [0,1] by -5:
    • stocks[0]: 10 - 5 = 5
    • stocks[1]: 2 - 5 = -3, capped at 0. So stocks[1] = 0. Current stocks: [5, 0, 15, 8]
  4. Query min in [0,3]: min([5,0,15,8]) = 0. Result: [2, 0]
  5. Range adjust [2,3] by +10:
    • stocks[2]: 15 + 10 = 25
    • stocks[3]: 8 + 10 = 18 Current stocks: [5, 0, 25, 18]
  6. Query min in [0,3]: min([5,0,25,18]) = 0. Result: [2, 0, 0]
  7. Point adjust at index 1 by +20: stocks[1] becomes 0 + 20 = 20. Current stocks: [5, 20, 25, 18]
  8. Query min in [0,3]: min([5,20,25,18]) = 5. Result: [2, 0, 0, 5]

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5 (number of dark stores)
  • 1 <= M <= 10^5 (number of operations)
  • 0 <= initialStocks[i] <= 10^9
  • -10^9 <= valueChange <= 10^9
  • 0 <= index < N
  • 0 <= startIndex <= endIndex < N
  • The total time complexity should be O(M log N).
  • The total space complexity should be O(N).

Out of scope

  • Error handling for invalid input formats or out-of-bounds indices (assume valid inputs).
  • Concurrency or multi-threaded operations.

What interviewers evaluate

  • Correctness and Efficiency: The solution must correctly handle all operation types, especially range updates and queries, within the specified time and space complexity.
  • Lazy Propagation Implementation: Demonstrates a solid understanding and correct implementation of lazy propagation for range updates.
  • Edge Case Handling: Correctly manages the non-negative stock constraint across all update operations.
  • Code Structure and Readability: The code should be well-organized, easy to understand, and follow good software engineering practices.

Loading editor...