PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multipart problem evaluates algorithmic problem solving and systems-design competencies including in-place array manipulation, queue-based scheduling, and event-driven trading simulation, while testing API/interface specification, edge-case handling, and time/space complexity analysis.

  • medium
  • Citadel
  • Coding & Algorithms
  • Software Engineer

Implement array merge, round-robin scheduler, and trading simulator

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given three independent coding prompts. For each prompt, clearly define your function/class interfaces, handle edge cases, and analyze time/space complexity. ## 1) Merge sorted arrays in-place Given two **non-decreasing** integer arrays: - `nums1` of length `m + n`, where the first `m` elements are valid and the last `n` elements are placeholders. - `nums2` of length `n`. Merge `nums2` into `nums1` so that `nums1` becomes a single sorted array. **Inputs** - `nums1: int[]`, `m: int` - `nums2: int[]`, `n: int` **Output** - Modify `nums1` in-place. **Constraints (typical interview scale)** - `0 ≤ m, n ≤ 2e5` - Values fit in 32-bit signed integer. ### Follow-up - How would you merge **three** sorted arrays (`A`, `B`, `C`) into one sorted array? - How would you merge them while also **removing duplicates** (i.e., output strictly increasing values)? --- ## 2) Implement a round-robin task scheduler Implement a round-robin CPU/task scheduler with a fixed time quantum `q`. Each task has: - `id` (string/int) - `arrivalTime` (non-negative integer) - `burstTime` (positive integer total runtime required) Scheduling rules: 1. Tasks enter the ready queue at their `arrivalTime`. 2. The scheduler repeatedly takes the next task from the head of the queue and runs it for `min(q, remainingTime)`. 3. If the task finishes, it leaves the system. 4. If not finished, it goes to the back of the queue. 5. Tasks that arrive while another task is running should be enqueued as soon as they arrive (but do not preempt the current time slice). **Output** Return the execution trace as a list of segments like: - `(taskId, startTime, endTime)` Include idle time segments if the CPU is idle. --- ## 3) Simulate a simplified stock trading system Design and implement a simplified in-memory trading simulator that processes a time-ordered stream of events. Each event is one of: - `DEPOSIT amount` - `BUY symbol qty price` - `SELL symbol qty price` Rules: - Start with zero cash and zero positions. - A `BUY` decreases cash by `qty * price` and increases position for `symbol` by `qty`. - A `SELL` increases cash by `qty * price` and decreases position by `qty`. - Reject any `BUY` that would make cash negative. - Reject any `SELL` that would make the position for that symbol negative. **Output** After processing all events, return: - final cash balance - final positions per symbol - list of rejected events (or their indices) **Follow-ups (optional, if time allows)** - Add average cost basis per symbol. - Add realized P&L using FIFO or average cost.

Quick Answer: This multipart problem evaluates algorithmic problem solving and systems-design competencies including in-place array manipulation, queue-based scheduling, and event-driven trading simulation, while testing API/interface specification, edge-case handling, and time/space complexity analysis.

Part 1: Merge Two Sorted Arrays In-Place

You are given two non-decreasing integer arrays. nums1 has length m + n, where the first m elements are valid sorted values and the last n elements are placeholders. nums2 has length n and is also sorted. Merge nums2 into nums1 so that nums1 becomes one sorted array. For testability, return nums1 after modifying it in-place.

Constraints

  • 0 <= m, n <= 200000
  • len(nums1) == m + n
  • len(nums2) == n
  • Values fit in a 32-bit signed integer
  • The first m elements of nums1 and all elements of nums2 are sorted in non-decreasing order

Examples

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

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

Explanation: The two sorted arrays [1,2,3] and [2,5,6] merge into [1,2,2,3,5,6].

Input: ([0], 0, [1], 1)

Expected Output: [1]

Explanation: nums1 has no valid original elements, so it becomes nums2.

Input: ([1], 1, [], 0)

Expected Output: [1]

Explanation: nums2 is empty, so nums1 is unchanged.

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

Expected Output: [1,2]

Explanation: The smaller nums2 value must be placed before the original nums1 value.

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

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

Explanation: Negative numbers and duplicates are handled normally.

Hints

  1. Try filling nums1 from the back so that unprocessed values are not overwritten.
  2. Compare the largest remaining values of nums1 and nums2.

Part 2: Merge Three Sorted Arrays

Given three integer arrays A, B, and C, each sorted in non-decreasing order, merge them into one sorted array. Keep duplicate values in the output.

Constraints

  • 0 <= len(A), len(B), len(C) <= 200000
  • The total number of elements is at most 600000
  • Values fit in a 32-bit signed integer
  • Each input array is sorted in non-decreasing order

Examples

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

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

Explanation: All three arrays are merged into sorted order.

Input: ([], [], [])

Expected Output: []

Explanation: All inputs are empty, so the result is empty.

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

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

Explanation: Duplicates are preserved.

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

Expected Output: [-3,-2,0,4]

Explanation: One array may be empty.

Input: ([1,3,7], [2,6], [4,5,8,9])

Expected Output: [1,2,3,4,5,6,7,8,9]

Explanation: Arrays of different lengths are supported.

Hints

  1. Maintain one pointer into each array.
  2. At each step, append the smallest currently pointed-to value.

Part 3: Merge Three Sorted Arrays Without Duplicates

Given three integer arrays A, B, and C, each sorted in non-decreasing order, merge them into one strictly increasing sorted array. If a value appears multiple times in any input array or across arrays, it should appear only once in the output.

Constraints

  • 0 <= len(A), len(B), len(C) <= 200000
  • The total number of elements is at most 600000
  • Values fit in a 32-bit signed integer
  • Each input array is sorted in non-decreasing order

Examples

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

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

Explanation: Values 1 and 2 appear multiple times but are returned once.

Input: ([], [], [])

Expected Output: []

Explanation: No input values means no output values.

Input: ([1,1,1], [], [1,1])

Expected Output: [1]

Explanation: All values are duplicates of 1.

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

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

Explanation: The result is sorted and contains each distinct value once.

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

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

Explanation: Duplicates across arrays are removed.

Hints

  1. After finding the smallest current value, advance past all copies of that value in all three arrays.
  2. Because the arrays are sorted, duplicates will be adjacent within each array.

Part 4: Round-Robin Task Scheduler

Implement a round-robin scheduler with fixed time quantum q. Each task is represented as (task_id, arrival_time, burst_time), where task_id is an integer, arrival_time is non-negative, and burst_time is positive. Tasks enter the ready queue at their arrival time. The scheduler repeatedly runs the task at the front of the queue for min(q, remaining_time). If the CPU is idle before the next task arrives, include an idle segment using task id -1. Tasks that arrive during a time slice are enqueued before the running task is requeued.

Constraints

  • 0 <= len(tasks) <= 200000
  • 1 <= q <= 1000000000
  • 0 <= arrival_time <= 1000000000
  • 1 <= burst_time <= 1000000000
  • task_id values are integers and are not -1
  • The number of output segments is bounded by the total number of time slices

Examples

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

Expected Output: [(1,0,2),(2,2,4),(3,4,5),(1,5,7),(2,7,8),(1,8,9)]

Explanation: Tasks 2 and 3 arrive during task 1's first time slice and are queued before task 1 is requeued.

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

Expected Output: [(-1,0,3),(10,3,5)]

Explanation: The CPU is idle from time 0 to 3 before task 10 arrives.

Input: ([], 3)

Expected Output: []

Explanation: With no tasks, there are no execution segments.

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

Expected Output: [(1,0,2),(2,2,4),(3,4,6),(1,6,8),(3,8,9)]

Explanation: Tasks 1 and 2 arrive together, so their input order is preserved.

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

Expected Output: [(1,0,2),(-1,2,5),(2,5,7),(2,7,8)]

Explanation: The input is unsorted, and an idle gap occurs between task 1 finishing and task 2 arriving.

Hints

  1. Sort tasks by arrival time, preserving input order for equal arrivals.
  2. Use a queue to store ready tasks with their remaining runtime.

Part 5: Simplified Stock Trading Simulator

Process a time-ordered stream of trading events in memory. Start with zero cash and no positions. A DEPOSIT increases cash. A BUY decreases cash by qty * price and increases the symbol position. A SELL increases cash by qty * price and decreases the symbol position. Reject any BUY that would make cash negative, and reject any SELL that would make the position negative. Rejected events have no effect.

Constraints

  • 0 <= len(events) <= 200000
  • amount, qty, and price are positive integers
  • Symbols are non-empty strings
  • All cash computations fit in signed 64-bit integers
  • Events are validly formatted and time-ordered

Examples

Input: ([('DEPOSIT',1000),('BUY','AAPL',5,100),('SELL','AAPL',2,120)],)

Expected Output: (740, {'AAPL': 3}, [])

Explanation: Cash becomes 1000 - 500 + 240 = 740, and 3 AAPL shares remain.

Input: ([('BUY','MSFT',1,10),('DEPOSIT',50),('BUY','MSFT',3,20),('BUY','MSFT',2,20),('SELL','MSFT',3,25)],)

Expected Output: (10, {'MSFT': 2}, [0, 2, 4])

Explanation: The first buy has no cash, the second buy is too expensive, and the sell exceeds the position.

Input: ([],)

Expected Output: (0, {}, [])

Explanation: No events means zero cash, no positions, and no rejected events.

Input: ([('DEPOSIT',100),('BUY','ABC',2,30),('SELL','ABC',2,40)],)

Expected Output: (120, {}, [])

Explanation: The final ABC position is zero, so it is omitted.

Input: ([('DEPOSIT',500),('BUY','A',2,100),('BUY','B',3,50),('SELL','A',1,120)],)

Expected Output: (270, {'A': 1, 'B': 3}, [])

Explanation: Multiple symbols are tracked independently.

Hints

  1. Keep one integer cash balance and a dictionary of symbol quantities.
  2. Validate an event before mutating cash or positions.

Part 6: Trading Simulator with Average Cost Basis

Extend the simplified trading simulator to maintain average cost basis per symbol. Start with zero cash and no positions. A BUY is accepted only if there is enough cash; it increases the position and updates that symbol's weighted average cost. A SELL is accepted only if there is enough position; it decreases the position but does not change the average cost of remaining shares. When a symbol's position reaches zero, remove it from both positions and average costs.

Constraints

  • 0 <= len(events) <= 200000
  • amount, qty, and price are positive integers
  • Symbols are non-empty strings
  • All cash computations fit in signed 64-bit integers
  • Events are validly formatted and time-ordered

Examples

Input: ([('DEPOSIT',1000),('BUY','AAPL',2,100),('BUY','AAPL',3,120),('SELL','AAPL',1,150)],)

Expected Output: (590, {'AAPL': 4}, {'AAPL': 112.0}, [])

Explanation: The average cost is (2*100 + 3*120) / 5 = 112.0 and remains unchanged after selling 1 share.

Input: ([],)

Expected Output: (0, {}, {}, [])

Explanation: No events produce no positions or average costs.

Input: ([('DEPOSIT',100),('BUY','X',5,10),('SELL','X',5,12)],)

Expected Output: (110, {}, {}, [])

Explanation: The full position is sold, so X is removed from positions and average costs.

Input: ([('DEPOSIT',50),('BUY','A',2,20),('BUY','A',2,20),('SELL','A',3,30)],)

Expected Output: (10, {'A': 2}, {'A': 20.0}, [2, 3])

Explanation: The second buy is rejected due to insufficient cash, and the sell is rejected due to insufficient shares.

Input: ([('DEPOSIT',100),('BUY','B',1,10),('BUY','B',2,11)],)

Expected Output: (68, {'B': 3}, {'B': 10.666667}, [])

Explanation: The weighted average cost is (1*10 + 2*11) / 3 = 10.666667 after rounding.

Hints

  1. For an accepted buy, combine old cost basis and new purchase cost using a weighted average.
  2. Selling shares reduces quantity but leaves the average cost of the remaining shares unchanged.

Part 7: Trading Simulator with FIFO Realized P&L

Extend the simplified trading simulator to compute realized profit and loss using FIFO lots. Start with zero cash and no positions. A BUY is accepted only if there is enough cash; it increases the position and appends a cost lot for that symbol. A SELL is accepted only if there is enough position; it consumes the oldest open lots first and adds qty_sold_from_lot * (sell_price - lot_price) to realized P&L. Rejected events have no effect.

Constraints

  • 0 <= len(events) <= 200000
  • amount, qty, and price are positive integers
  • Symbols are non-empty strings
  • All cash and P&L computations fit in signed 64-bit integers
  • Events are validly formatted and time-ordered

Examples

Input: ([('DEPOSIT',2000),('BUY','A',5,100),('BUY','A',5,110),('SELL','A',7,120)],)

Expected Output: (1790, {'A': 3}, 120, [])

Explanation: The sell consumes 5 shares bought at 100 and 2 shares bought at 110, for P&L 5*20 + 2*10 = 120.

Input: ([('DEPOSIT',500),('BUY','X',4,50),('SELL','X',2,40)],)

Expected Output: (380, {'X': 2}, -20, [])

Explanation: Selling below cost realizes a loss of 2*(40 - 50) = -20.

Input: ([('SELL','A',1,10),('DEPOSIT',100),('BUY','A',2,30),('BUY','A',2,30),('SELL','A',5,40)],)

Expected Output: (40, {'A': 2}, 0, [0, 3, 4])

Explanation: The first sell has no shares, the second buy lacks cash, and the final sell exceeds the position.

Input: ([],)

Expected Output: (0, {}, 0, [])

Explanation: No events means no cash, positions, P&L, or rejections.

Input: ([('DEPOSIT',300),('BUY','A',1,100),('BUY','A',1,120),('SELL','A',2,130)],)

Expected Output: (340, {}, 40, [])

Explanation: Both lots are fully sold, realizing 30 + 10 = 40 profit and leaving no position.

Hints

  1. Maintain a FIFO queue of buy lots for each symbol, where each lot stores remaining quantity and purchase price.
  2. Each accepted sell may consume multiple lots, but each buy lot is removed at most once overall.
Last updated: Jun 18, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Sort a Nearly Sorted Array - Citadel (hard)
  • Implement a single-producer multi-consumer ring buffer - Citadel (medium)
  • Compute BBO and NBBO from order data - Citadel (medium)
  • Simulate 2048 and pack board into uint64 - Citadel (medium)
  • Implement task queue with insert, delete, execute - Citadel (medium)