Frontend School

Meesho Order Stage Exclusive Processing Time

DSA
medium

Meesho Order Stage Exclusive Processing Time

Medium
Stack
Arrays
Parsing

Overview

Meesho's order fulfillment system processes orders through various stages like OrderValidation, PaymentProcessing, LogisticsAssignment, etc. Each stage has a defined start and end event, and stages can be nested (e.g., PaymentProcessing might start and end within OrderValidation). To optimize our systems, we need to accurately measure the exclusive time spent in each stage, meaning the time a stage was active and no sub-stage was running.

What you need to do / Task

You are given a list of log entries, each representing a start or end event for a specific order processing stage. Your task is to calculate the total exclusive processing time for each stage ID.

  1. Parse the input log entries to extract stage ID, event type (start or end), and timestamp.
  2. Use an appropriate data structure to keep track of active stages and correctly calculate exclusive time.
  3. Return the total exclusive time for each stage ID.

Input & output

Input: n: number, the number of distinct stage IDs. logs: string[], an array of log entries. Each entry is a string in the format "stage_id:event_type:timestamp".

  • stage_id: an integer from 0 to n-1.
  • event_type: either "start" or "end".
  • timestamp: a non-negative integer representing seconds.

Output: number[], an array of size n where output[i] is the total exclusive time for stage_id = i.

Clarifications

  • All start events will have a corresponding end event.
  • Events are guaranteed to be well-formed and sorted by timestamp.
  • There will be no concurrent start events for the same stage ID without an intervening end event. This implies a valid call stack model.
  • The maximum timestamp can be large, but n (number of stage IDs) will be relatively small.

Examples

1

Example 1

Input:

n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]

Output:

[3,3]

Note:

Stage 0 starts at t=0. Stage 1 starts at t=2, so stage 0 is paused and accumulates 2 units (0 to 2). Stage 1 runs exclusively from t=2 to t=5 (3 units). Stage 1 ends, stage 0 resumes at t=5. Stage 0 runs exclusively from t=5 to t=6 (1 unit). Total for stage 0: 2+1=3. Total for stage 1: 3.

2

Example 2

Input:

n = 1, logs = ["0:start:0", "0:start:1", "0:end:2", "0:end:3"]

Output:

[3]

Note:

Stage 0 starts at t=0. Another instance of Stage 0 (recursive call) starts at t=1, pausing the first. The inner Stage 0 runs from t=1 to t=2 (1 unit). The inner Stage 0 ends, the outer Stage 0 resumes at t=2. The outer Stage 0 runs from t=2 to t=3 (1 unit). The total time accumulated for stage 0 is (1-0) + (2-1) + (3-2) = 1 + 1 + 1 = 3.

3

Example 3

Input:

n = 3, logs = ["0:start:0", "1:start:1", "2:start:2", "2:end:3", "1:end:4", "0:end:5"]

Output:

[2,2,1]

Note:

Stage 0 runs from t=0 to t=1 (1 unit). Stage 1 runs from t=1 to t=2 (1 unit). Stage 2 runs from t=2 to t=3 (1 unit). Stage 1 resumes from t=3 to t=4 (1 unit). Stage 0 resumes from t=4 to t=5 (1 unit). Total for stage 0: 1+1=2. Total for stage 1: 1+1=2. Total for stage 2: 1.

Constraints

Constraints & assumptions

  • 1 <= n <= 100 (Number of distinct stage IDs)
  • 1 <= logs.length <= 10^4
  • 0 <= stage_id < n
  • 0 <= timestamp <= 10^9
  • event_type is strictly either "start" or "end".
  • Logs are guaranteed to be chronologically sorted by timestamp.
  • Logs represent a valid sequence of nested function calls (i.e., every start has a matching end, and the end event for stage_X will only occur if stage_X is currently at the top of the call stack).

Out of scope

  • Error handling for malformed log entries or unsorted timestamps.
  • Performance optimization beyond O(N) where N is logs.length.
  • Handling of non-integer stage IDs or timestamps.

What interviewers evaluate

  • Correctness in parsing log entries and extracting relevant information.
  • Efficient and correct use of a stack to manage stage states.
  • Accurate calculation of exclusive time, correctly handling nested stages and recursive calls of the same stage.
  • Code clarity, organization, and adherence to best practices.

Loading editor...