Frontend School

Warehouse Stock Management

DSA
medium

Warehouse Stock Management

Medium
Segment Tree
Data Structures
Range Query
Point Update

Overview

Flipkart's warehouses are vast, and efficient inventory management is crucial for fulfilling customer orders quickly. Products are stored in a highly optimized linear arrangement across many storage slots. To maintain stock levels and plan logistics, it's essential to quickly ascertain stock availability across various sections of the warehouse.

What you need to do / Task

Implement a data structure that efficiently handles two types of operations on an array representing stock levels in contiguous warehouse slots:

  1. Update Stock: Modify the stock count for a specific slot.
  2. Query Max Stock: Find the maximum stock count within a given range of slots (inclusive).

You will be given an initial array of stock counts. Your implementation should support subsequent update and query operations.

Input & output

Your solution should implement a class WarehouseManager with the following methods:

  • constructor(initialStocks: number[]): Initializes the system with an array initialStocks where initialStocks[i] represents the stock count in slot i.
  • updateStock(slotIndex: number, newStock: number): void: Updates the stock count in slotIndex to newStock.
  • queryMaxStock(startIndex: number, endIndex: number): number: Returns the maximum stock count within the range of slots from startIndex to endIndex (inclusive).

Clarifications

  • Slot indices are 0-based.
  • newStock will always be non-negative.
  • startIndex and endIndex will always be valid and startIndex <= endIndex.

Examples

1

Example 1

Input:

operations = ["WarehouseManager","queryMaxStock","updateStock","queryMaxStock","queryMaxStock"], params = [[[10,20,5,30,15]],[0,4],[2,25],[1,3],[0,1]]

Output:

[null,30,null,30,20]

Note:

Initialize with [10,20,5,30,15]. Max in [0,4] is 30. Update slot 2 to 25. Array becomes [10,20,25,30,15]. Max in [1,3] is 30. Max in [0,1] is 20.

2

Example 2

Input:

operations = ["WarehouseManager","queryMaxStock","updateStock","queryMaxStock","queryMaxStock","updateStock","queryMaxStock"], params = [[[1,2,3,4,5]],[0,0],[0,100],[0,0],[2,4],[4,0],[0,4]]

Output:

[null,1,null,100,5,null,100]

Note:

Initialize with [1,2,3,4,5]. Max in [0,0] is 1. Update slot 0 to 100. Array becomes [100,2,3,4,5]. Max in [0,0] is 100. Max in [2,4] is 5. Update slot 4 to 0. Array becomes [100,2,3,4,0]. Max in [0,4] is 100.

3

Example 3

Input:

operations = ["WarehouseManager","queryMaxStock","updateStock","queryMaxStock"], params = [[[50]],[0,0],[0,10],[0,0]]

Output:

[null,50,null,10]

Note:

Initialize with [50]. Max in [0,0] is 50. Update slot 0 to 10. Array becomes [10]. Max in [0,0] is 10.

Constraints

Constraints & assumptions

  • 1 <= initialStocks.length <= 10^5
  • 0 <= initialStocks[i] <= 10^9
  • 0 <= slotIndex < initialStocks.length
  • 0 <= newStock <= 10^9
  • 0 <= startIndex <= endIndex < initialStocks.length
  • Total number of updateStock and queryMaxStock calls will not exceed 10^5.
  • Time complexity for updateStock and queryMaxStock should be O(log N), where N is the number of slots.
  • Space complexity should be O(N).

Out of scope

  • Handling invalid input (e.g., negative stock, out-of-bounds indices) is not required; inputs will always be valid as per constraints.
  • Concurrency or multi-threading for operations.

What interviewers evaluate

  • Correctness of the Segment Tree implementation for range maximum queries and point updates.
  • Efficiency of the updateStock and queryMaxStock methods in terms of time and space complexity.
  • Clarity and organization of the code, demonstrating good software engineering practices.
  • Ability to articulate the choice of data structure and its underlying principles.

Loading editor...