PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCareers

Quick Overview

This question evaluates implementation skills for stateful in-memory data structures, API evolution handling, substring search and prioritized sorting, and time-windowed assignment logic with quota enforcement in the Coding & Algorithms domain, and is primarily a practical application problem rather than a purely conceptual one.

  • medium
  • Ramp
  • Coding & Algorithms
  • Software Engineer

Implement multi-level task manager APIs

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are implementing an **in-memory task management system** with a set of APIs that evolve over 4 levels. All APIs receive a `timestamp: int` parameter. Unless otherwise stated, timestamps are integers and can be assumed to be non-decreasing across calls (you may state and rely on this if needed). Task IDs are generated sequentially as strings: - First task is `"task_id_1"`, then `"task_id_2"`, etc. - Creation order is the numeric suffix order (e.g., `task_id_2` comes before `task_id_10`). A task has: - `name: str` - `priority: int` (non-negative, `>= 0`) Assignments (introduced later) are time-based. --- ## Level 1: Basic task CRUD Implement the following: 1. `add_task(self, timestamp: int, name: str, priority: int) -> str` - Adds a new task with the given `name` and `priority`. - Returns the unique task ID. - Adding multiple tasks with the same `name` and `priority` is allowed; tasks are differentiated by ID. - Note: `timestamp` is unused in Level 1 logic; included for API consistency. 2. `update_task(self, timestamp: int, task_id: str, name: str, priority: int) -> bool` - Updates the `name` and `priority` of the task identified by `task_id`. - Returns `True` if update succeeds; `False` if `task_id` does not exist. 3. `get_task(self, timestamp: int, task_id: str) -> str | None` - Retrieves a task by `task_id`. - If it exists, return a JSON-formatted string containing the task details (`name` and `priority`). - If it does not exist, return `None`. --- ## Level 2: Searching and sorting tasks Add the following APIs: 1. `search_tasks(self, timestamp: int, name_filter: str, max_results: int) -> list[str]` - Finds tasks whose `name` contains `name_filter` as a **case-sensitive substring**. - Returns **up to** `max_results` matching **task IDs**. - Sort results by: 1) `priority` descending, then 2) creation order ascending. - If `max_results <= 0`, return `[]`. 2. `list_tasks_sorted(self, timestamp: int, limit: int) -> list[str]` - Returns **up to** `limit` task IDs across the system. - Sorting is the same: `priority` descending, then creation order ascending. --- ## Level 3: Users and time-based task assignments Introduce users with quotas and time-windowed assignments. 1. `add_user(self, timestamp: int, user_id: str, quota: int) -> bool` - Adds a new user with a maximum number of **simultaneously active assignments** (`quota`). - Returns `True` if added, `False` if `user_id` already exists. 2. `assign_task(self, timestamp: int, task_id: str, user_id: str, finish_time: int) -> bool` - Assigns `task_id` to `user_id` for the time interval **[timestamp, finish_time)**. - The assignment is **active** at time `t` iff `start_time <= t < finish_time`. - Returns `True` if successful; otherwise `False` if: - the task does not exist, or - the user does not exist, or - the user's quota is already fully used by currently active assignments. - Each successful active assignment consumes one quota slot while it remains active. 3. `get_user_tasks(self, timestamp: int, user_id: str) -> list[str]` - Returns all **active** task IDs assigned to `user_id` at the given `timestamp`. - Only include assignments where `start_time <= timestamp < finish_time`. --- ## Level 4: Completion and overdue detection Add completion and overdue queries. 1. `complete_task(self, timestamp: int, task_id: str, user_id: str) -> bool` - Marks a task as completed by `user_id` at time `timestamp`. - The task must be **assigned to the user and active** at `timestamp`. - When completed, the user's quota slot is freed **immediately**. - Returns `True` if successful; otherwise `False` if: - task does not exist, or - user does not exist, or - task is not assigned to the user at `timestamp`. 2. `get_overdue_assignments(self, timestamp: int, user_id: str) -> list[str]` - Returns task IDs for assignments that were given to `user_id` and **expired without completion**. - An assignment is overdue if: - `finish_time <= timestamp`, and - the task was **not completed before the `finish_time` of that specific assignment**. --- Implement the full system so that all levels work together consistently. Clarify any additional assumptions you need (e.g., whether timestamps are non-decreasing, whether a task can be assigned multiple times, and how repeated assignments to the same user/task should behave), but your behavior must remain consistent with the definitions above.

Quick Answer: This question evaluates implementation skills for stateful in-memory data structures, API evolution handling, substring search and prioritized sorting, and time-windowed assignment logic with quota enforcement in the Coding & Algorithms domain, and is primarily a practical application problem rather than a purely conceptual one.

Part 1: Task CRUD Simulator

Simulate a small in-memory task manager. Each new task gets an ID in creation order: task_id_1, task_id_2, and so on. Process a list of operations and return the output for each operation in order. Supported operations are add, update, and get. For a get operation, return a compact JSON string with keys in this exact order: name, then priority. If a task does not exist, return None.

Constraints

  • 0 <= len(operations) <= 10000
  • Timestamps are non-decreasing, but they do not affect Level 1 behavior
  • 0 <= priority <= 10^9
  • Task IDs must be generated exactly as task_id_1, task_id_2, ...

Examples

Input: [('add', 1, 'write', 3), ('get', 2, 'task_id_1'), ('update', 3, 'task_id_1', 'write docs', 5), ('get', 4, 'task_id_1')]

Expected Output: ['task_id_1', '{"name":"write","priority":3}', True, '{"name":"write docs","priority":5}']

Explanation: Create one task, read it, update it, then read the updated version.

Input: [('add', 1, 'bug', 1), ('add', 2, 'bug', 1), ('get', 3, 'task_id_2')]

Expected Output: ['task_id_1', 'task_id_2', '{"name":"bug","priority":1}']

Explanation: Tasks with identical fields are still different because IDs are unique.

Input: [('update', 1, 'task_id_9', 'x', 1), ('get', 2, 'task_id_9')]

Expected Output: [False, None]

Explanation: Updating or reading a missing task should fail cleanly.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Solution

def solution(operations):
    import json
    tasks = {}
    next_id = 1
    result = []

    for op in operations:
        kind = op[0]
        if kind == 'add':
            _, timestamp, name, priority = op
            task_id = f'task_id_{next_id}'
            next_id += 1
            tasks[task_id] = {'name': name, 'priority': priority}
            result.append(task_id)
        elif kind == 'update':
            _, timestamp, task_id, name, priority = op
            if task_id in tasks:
                tasks[task_id]['name'] = name
                tasks[task_id]['priority'] = priority
                result.append(True)
            else:
                result.append(False)
        elif kind == 'get':
            _, timestamp, task_id = op
            if task_id in tasks:
                task = tasks[task_id]
                result.append(json.dumps({'name': task['name'], 'priority': task['priority']}, separators=(',', ':')))
            else:
                result.append(None)
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return result

Time complexity: O(n), where n is the number of operations. Space complexity: O(t), where t is the number of created tasks.

Hints

  1. Use a dictionary keyed by task_id so update and get are O(1).
  2. Keep a counter for the next numeric suffix, and use a JSON serializer to produce the exact string format.

Part 2: Search and Sort Tasks

Build a task catalog that supports insertion, substring search, and global listing. Every added task gets an ID in creation order. A search matches tasks whose name contains the filter as a case-sensitive substring. Search results and global listings must be sorted by priority descending, then by creation order ascending. Process all operations and return the result of each one.

Constraints

  • 0 <= len(operations) <= 2000
  • 0 <= priority <= 10^9
  • Timestamps are non-decreasing, but they do not affect sorting logic here
  • Substring matching is case-sensitive
  • Sorting rule: higher priority first, then earlier creation first

Examples

Input: [('add', 1, 'alpha', 5), ('add', 2, 'beta', 2), ('add', 3, 'alphabet', 5), ('search', 4, 'alpha', 5), ('list', 5, 2)]

Expected Output: ['task_id_1', 'task_id_2', 'task_id_3', ['task_id_1', 'task_id_3'], ['task_id_1', 'task_id_3']]

Explanation: Both matching tasks have priority 5, so creation order breaks the tie.

Input: [('add', 1, 'Task', 4), ('add', 2, 'task', 4), ('search', 3, 'Task', 10), ('search', 4, 'task', 10)]

Expected Output: ['task_id_1', 'task_id_2', ['task_id_1'], ['task_id_2']]

Explanation: Search is case-sensitive.

Input: [('add', 1, 'x', 1), ('search', 2, 'x', 0), ('list', 3, 0), ('search', 4, '', -2)]

Expected Output: ['task_id_1', [], [], []]

Explanation: Edge cases with non-positive limits should return empty lists.

Input: [('add', 1, 'ab', 1), ('add', 2, 'cd', 5), ('search', 3, 'z', 3), ('list', 4, 5)]

Expected Output: ['task_id_1', 'task_id_2', [], ['task_id_2', 'task_id_1']]

Explanation: No search matches, and the global list is sorted by priority descending.

Solution

def solution(operations):
    tasks = []
    next_id = 1
    result = []

    for op in operations:
        kind = op[0]
        if kind == 'add':
            _, timestamp, name, priority = op
            task_id = f'task_id_{next_id}'
            next_id += 1
            tasks.append({
                'id': task_id,
                'name': name,
                'priority': priority,
                'order': len(tasks)
            })
            result.append(task_id)
        elif kind == 'search':
            _, timestamp, name_filter, max_results = op
            if max_results <= 0:
                result.append([])
                continue
            matches = [task for task in tasks if name_filter in task['name']]
            matches.sort(key=lambda task: (-task['priority'], task['order']))
            result.append([task['id'] for task in matches[:max_results]])
        elif kind == 'list':
            _, timestamp, limit = op
            if limit <= 0:
                result.append([])
                continue
            ordered = sorted(tasks, key=lambda task: (-task['priority'], task['order']))
            result.append([task['id'] for task in ordered[:limit]])
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return result

Time complexity: Worst-case O(n^2 log n) over all operations, because each search/list may sort the current tasks. Space complexity: O(t), where t is the number of created tasks.

Hints

  1. Store a creation index when each task is added.
  2. A sort key like (-priority, creation_index) directly matches the required order.

Part 3: Users and Time-Windowed Assignments

Extend the task manager with users and time-based assignments. Each assignment created at time t with finish_time f is active on the half-open interval [t, f). A user has a quota: the maximum number of simultaneously active assignments. Process the operations and return the output of each one. For get_user_tasks, return all active task IDs for that user in assignment creation order. If the same task is assigned multiple times and multiple assignments are active, duplicate task IDs may appear. If get_user_tasks is called for an unknown user, return an empty list.

Constraints

  • 0 <= len(operations) <= 2000
  • Timestamps are non-decreasing
  • 0 <= priority <= 10^9
  • 0 <= quota <= 10^9
  • Every assign operation satisfies finish_time > t

Examples

Input: [('add_task', 0, 'A', 1), ('add_task', 1, 'B', 2), ('add_user', 2, 'alice', 1), ('assign', 3, 'task_id_1', 'alice', 10), ('assign', 4, 'task_id_2', 'alice', 8), ('get_user_tasks', 5, 'alice'), ('get_user_tasks', 10, 'alice')]

Expected Output: ['task_id_1', 'task_id_2', True, True, False, ['task_id_1'], []]

Explanation: Alice's quota is 1, so the second assignment fails while the first one is still active. The interval is half-open, so the task is not active at time 10.

Input: [('add_task', 0, 'A', 1), ('add_task', 1, 'B', 1), ('add_user', 2, 'u', 1), ('assign', 2, 'task_id_1', 'u', 3), ('assign', 3, 'task_id_2', 'u', 6), ('get_user_tasks', 3, 'u')]

Expected Output: ['task_id_1', 'task_id_2', True, True, True, ['task_id_2']]

Explanation: At time 3, the first assignment has already expired, so quota is available for the second one.

Input: [('add_user', 0, 'u', 2), ('add_user', 1, 'u', 5), ('assign', 2, 'task_id_1', 'u', 4), ('get_user_tasks', 2, 'ghost')]

Expected Output: [True, False, False, []]

Explanation: Duplicate users are rejected, assigning a missing task fails, and querying an unknown user returns an empty list.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Solution

def solution(operations):
    tasks = {}
    users = {}
    assignments = []
    next_id = 1
    result = []

    for op in operations:
        kind = op[0]
        if kind == 'add_task':
            _, t, name, priority = op
            task_id = f'task_id_{next_id}'
            next_id += 1
            tasks[task_id] = {'name': name, 'priority': priority}
            result.append(task_id)
        elif kind == 'add_user':
            _, t, user_id, quota = op
            if user_id in users:
                result.append(False)
            else:
                users[user_id] = quota
                result.append(True)
        elif kind == 'assign':
            _, t, task_id, user_id, finish_time = op
            if task_id not in tasks or user_id not in users:
                result.append(False)
                continue
            active_count = 0
            for assignment in assignments:
                if assignment['user_id'] == user_id and assignment['start'] <= t < assignment['finish']:
                    active_count += 1
            if active_count >= users[user_id]:
                result.append(False)
            else:
                assignments.append({
                    'task_id': task_id,
                    'user_id': user_id,
                    'start': t,
                    'finish': finish_time
                })
                result.append(True)
        elif kind == 'get_user_tasks':
            _, t, user_id = op
            if user_id not in users:
                result.append([])
            else:
                active_tasks = []
                for assignment in assignments:
                    if assignment['user_id'] == user_id and assignment['start'] <= t < assignment['finish']:
                        active_tasks.append(assignment['task_id'])
                result.append(active_tasks)
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return result

Time complexity: O(n^2) worst-case over all operations, because each assign/query may scan earlier assignments. Space complexity: O(t + u + a), for tasks, users, and assignments.

Hints

  1. To check whether an assignment fits, count how many assignments for that user satisfy start <= t < finish at the assignment timestamp.
  2. If you store assignment records in insertion order, you can scan them later to build get_user_tasks in the required order.

Part 4: Task Completion and Overdue Detection

Add completion and overdue queries to the task assignment system. Each assignment is its own record. An assignment is active at time t if start <= t < finish and it has not been completed before or at t. Completing a task frees the quota slot immediately, so later operations at the same timestamp should see that slot as available. For deterministic behavior, if multiple active assignments exist for the same task_id and user_id, complete the earliest such assignment. The overdue query returns one task ID per overdue assignment in assignment creation order; duplicates are allowed. If overdue is called for an unknown user, return an empty list.

Constraints

  • 0 <= len(operations) <= 2000
  • Timestamps are non-decreasing
  • 0 <= priority <= 10^9
  • 0 <= quota <= 10^9
  • Every assign operation satisfies finish_time > t

Examples

Input: [('add_task', 0, 'A', 1), ('add_task', 1, 'B', 2), ('add_user', 1, 'alice', 1), ('assign', 2, 'task_id_1', 'alice', 5), ('complete', 3, 'task_id_1', 'alice'), ('assign', 3, 'task_id_2', 'alice', 6), ('overdue', 10, 'alice')]

Expected Output: ['task_id_1', 'task_id_2', True, True, True, True, ['task_id_2']]

Explanation: Completing task_id_1 at time 3 frees Alice's only slot immediately, so task_id_2 can be assigned at the same timestamp. The second task later becomes overdue.

Input: [('add_task', 0, 'A', 1), ('add_user', 0, 'u', 1), ('assign', 1, 'task_id_1', 'u', 4), ('complete', 4, 'task_id_1', 'u'), ('overdue', 4, 'u')]

Expected Output: ['task_id_1', True, True, False, ['task_id_1']]

Explanation: The assignment is active on [1, 4), so completion at time 4 fails and the task is already overdue at time 4.

Input: [('add_user', 0, 'u', 1), ('complete', 1, 'task_id_1', 'u'), ('overdue', 2, 'ghost')]

Expected Output: [True, False, []]

Explanation: Completing a missing task fails, and querying overdue tasks for an unknown user returns an empty list.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Solution

def solution(operations):
    tasks = {}
    users = {}
    assignments = []
    next_id = 1
    result = []

    def is_active(assignment, t):
        return (
            assignment['start'] <= t < assignment['finish']
            and (assignment['completed_at'] is None or t < assignment['completed_at'])
        )

    for op in operations:
        kind = op[0]
        if kind == 'add_task':
            _, t, name, priority = op
            task_id = f'task_id_{next_id}'
            next_id += 1
            tasks[task_id] = {'name': name, 'priority': priority}
            result.append(task_id)
        elif kind == 'add_user':
            _, t, user_id, quota = op
            if user_id in users:
                result.append(False)
            else:
                users[user_id] = quota
                result.append(True)
        elif kind == 'assign':
            _, t, task_id, user_id, finish_time = op
            if task_id not in tasks or user_id not in users:
                result.append(False)
                continue
            active_count = 0
            for assignment in assignments:
                if assignment['user_id'] == user_id and is_active(assignment, t):
                    active_count += 1
            if active_count >= users[user_id]:
                result.append(False)
            else:
                assignments.append({
                    'task_id': task_id,
                    'user_id': user_id,
                    'start': t,
                    'finish': finish_time,
                    'completed_at': None
                })
                result.append(True)
        elif kind == 'complete':
            _, t, task_id, user_id = op
            if task_id not in tasks or user_id not in users:
                result.append(False)
                continue
            done = False
            for assignment in assignments:
                if assignment['task_id'] == task_id and assignment['user_id'] == user_id and is_active(assignment, t):
                    assignment['completed_at'] = t
                    done = True
                    break
            result.append(done)
        elif kind == 'overdue':
            _, t, user_id = op
            if user_id not in users:
                result.append([])
            else:
                overdue_tasks = []
                for assignment in assignments:
                    if (
                        assignment['user_id'] == user_id
                        and assignment['finish'] <= t
                        and (assignment['completed_at'] is None or assignment['completed_at'] >= assignment['finish'])
                    ):
                        overdue_tasks.append(assignment['task_id'])
                result.append(overdue_tasks)
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return result

Time complexity: O(n^2) worst-case over all operations, because assignment, completion, and overdue queries may scan earlier assignments. Space complexity: O(t + u + a), for tasks, users, and assignments.

Hints

  1. Store completion time per assignment. An assignment is active at time t only if it has started, not finished, and t is strictly earlier than its completion time.
  2. Overdue is a property of each assignment record, not just of a task ID, so do not merge repeated assignments.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • Careers
  • 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

  • Find an Exit in a URL Maze - Ramp (medium)
  • Implement a multi-level digital recipe manager - Ramp (medium)
  • Build a Wordle-style game in React - Ramp (medium)
  • Find final URL by crawling until “congrats” - Ramp (hard)
  • Implement wildcard querySelector to extract URL - Ramp (medium)