Katkat
Back

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

CitadelSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate data structures efficiently, implement a fair process scheduler, and manage event-driven state transitions.

Part 1: Sorted Array Merge

Given two sorted arrays arr1 and arr2, write a function merge_in_place(arr1, arr2) that merges arr2 into arr1. Assume arr1 has sufficient buffer space at the end to hold all elements of arr2. The resulting arr1 must be sorted.

Example: arr1 = [1, 3, 5, 0, 0], arr2 = [2, 4] After merge_in_place, arr1 becomes [1, 2, 3, 4, 5]

Part 2: Round-Robin Scheduler

Implement a Scheduler class that manages tasks with fixed time slices. Use the interface:

class Scheduler:
    def add_task(self, task_id, duration):
        # Adds a task to the queue
    def execute_next(self, time_slice):
        # Runs the next task for at most 'time_slice'. 
        # Returns (task_id, remaining_duration) after execution.

Tasks should be processed in the order they were added. If a task finishes, remove it; if it remains, move it to the back of the queue.

Part 3: Trading Simulator

Design a function process_orders(order_book, trades) where order_book is a dictionary of {price: volume} and trades is a list of tuples (type, price, volume). Types are 'BUY' or 'SELL'.

  • For 'BUY', decrease volume at the lowest price level first.
  • For 'SELL', decrease volume at the highest price level first.
  • If volume reaches 0, remove the price level.

Return the final order_book state.

Hints

Hint 1

For Part 1, start filling the merged array from the back to avoid overwriting elements.

Hint 2

For Part 2, a double-ended queue (deque) is the optimal structure to maintain the order of tasks efficiently.

Hint 3

For Part 3, use a min-heap for 'SELL' orders and a max-heap for 'BUY' orders to quickly access the best available price.

Follow-up questions

  • How would you modify the round-robin scheduler to handle task priorities?
  • In the trading simulator, what is the time complexity of a single trade if there are N price levels?
  • How would you ensure thread safety if multiple threads were adding and removing orders simultaneously?