Katkat
Back

Implement multiple coding round problems

InstacartSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage a time-sensitive priority queue, handle dynamic variable substitution in expressions, and optimize for streaming data processing.

Part 1: Task Priority Scheduler

You are building a task scheduler. Tasks are given as a list of (task_id, priority, timestamp). If two tasks have the same priority, the one with the earlier timestamp must be processed first. Implement a data structure that supports:

  1. add_task(task_id, priority, timestamp): Adds a task.
  2. get_next_task(): Returns and removes the task with the highest priority (ties broken by earliest timestamp).

Part 2: Expression Variable Substitution

Given a dictionary of variables vars = {'a': 5, 'b': 10} and a mathematical expression string (e.g., "(a + b) * 2"), evaluate the expression. Assume expressions only contain integers, variables, +, *, and parentheses (). If a variable is missing, return -1.

Example 1

Input: [('T1', 10, 1), ('T2', 20, 2), ('T3', 10, 0)] Sequence: get_next_task returns T2, then T3, then T1.

Example 2

Input: vars = {'x': 3}, expr = "x + 5 * 2" Output: 13

Constraints

  • Task counts can reach 10^5.
  • Expressions contain only non-negative integers.
  • Use efficient data structures to ensure O(log N) operations for scheduling.

Hints

Hint 1

For the scheduler, use a min-heap or max-heap where the element is a tuple designed to satisfy the priority/timestamp sorting criteria.

Hint 2

For the expression evaluator, consider converting the expression to Reverse Polish Notation (RPN) using a stack-based algorithm like Shunting-yard.

Hint 3

Ensure the variable substitution occurs before or during the parsing step to avoid re-parsing the entire string.

Follow-up questions

  • How would you modify the scheduler if tasks had an expiration time, and you needed to remove expired tasks periodically?
  • What changes are required to support unary operators like negative signs or exponents?
  • How would you handle a scenario where variables depend on other variables (e.g., {'a': 'b + 1', 'b': 5})?