How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at eBay.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at eBay during technical interviews.

Solve Dependency, Prefix, and Cache Problems

Quick Overview

This set of problems evaluates graph algorithms for dependency and cycle detection, efficient data structure design for prefix-based word storage, and cache eviction policy implementation, assessing skills in algorithmic analysis, data structures, and time/space complexity within the Coding & Algorithms domain.

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following three coding problems. ## Problem 1: Determine Whether All Tasks Can Be Completed You are given `numTasks`, the number of tasks labeled from `0` to `numTasks - 1`, and a list of prerequisite pairs `prerequisites`. Each pair `[a, b]` means task `b` must be completed before task `a`. Return `true` if it is possible to complete all tasks. Return `false` if the prerequisite graph contains a cycle. Example: ```text numTasks = 2 prerequisites = [[1, 0]] Output: true ``` ```text numTasks = 2 prerequisites = [[1, 0], [0, 1]] Output: false ``` ## Problem 2: Implement a Prefix-Based Word Store Design a data structure that supports the following operations: - `insert(word)`: Add a lowercase English word. - `search(word)`: Return whether the exact word exists. - `startsWith(prefix)`: Return whether any inserted word starts with the given prefix. All inputs contain only lowercase English letters `a` through `z`. Example: ```text insert("apple") search("apple") -> true search("app") -> false startsWith("app") -> true insert("app") search("app") -> true ``` ## Problem 3: Implement a Fixed-Capacity Least-Recently-Used Cache Design a cache with positive integer capacity that supports: - `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key makes it the most recently used item. - `put(key, value)`: Insert or update the value for `key`. If the cache exceeds capacity, evict the least recently used item. Both operations should run in average `O(1)` time. Example: ```text capacity = 2 put(1, 1) put(2, 2) get(1) -> 1 put(3, 3) // evicts key 2 get(2) -> -1 put(4, 4) // evicts key 1 get(1) -> -1 get(3) -> 3 get(4) -> 4 ```

Quick Answer: This set of problems evaluates graph algorithms for dependency and cycle detection, efficient data structure design for prefix-based word storage, and cache eviction policy implementation, assessing skills in algorithmic analysis, data structures, and time/space complexity within the Coding & Algorithms domain.

Part 1: Determine Whether All Tasks Can Be Completed

Given an integer numTasks and a list of prerequisite pairs prerequisites, where each pair [a, b] means task b must be completed before task a, determine whether it is possible to finish every task. Return True if the prerequisite graph contains no cycle; otherwise return False.

Constraints

0 <= numTasks <= 100000
0 <= len(prerequisites) <= 200000
Each prerequisite is a pair [a, b] with 0 <= a, b < numTasks

Examples

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

Expected Output: True

Explanation: Task 0 can be done first, then task 1. There is no cycle.

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

Expected Output: False

Explanation: Task 0 depends on task 1 and task 1 depends on task 0, forming a cycle.

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

Expected Output: True

Explanation: A valid order is 0, 1, 2, 3 or 0, 2, 1, 3. No cycle exists.

Input: (3, [])

Expected Output: True

Explanation: With no prerequisites, all tasks can be completed in any order.

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

Expected Output: False

Explanation: The only task depends on itself, which is a cycle.

Hints

Model the tasks as a directed graph and look for a way to detect cycles.
If you repeatedly remove tasks with indegree 0 and cannot process all tasks, a cycle must exist.

Part 2: Implement a Prefix-Based Word Store

Implement a prefix-based word store using a function interface. The function receives a list of operations. Each operation is a tuple (op, text), where op is one of 'insert', 'search', or 'startsWith'. For each 'insert', append None to the output list. For each 'search' or 'startsWith', append the boolean result. Return the full result list in operation order.

Constraints

0 <= len(operations) <= 20000
Each word or prefix has length between 1 and 2000
The sum of lengths of all words and prefixes is at most 200000
All characters are lowercase English letters a through z

Examples

Input: [('insert', 'apple'), ('search', 'apple'), ('search', 'app'), ('startsWith', 'app'), ('insert', 'app'), ('search', 'app')]

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

Explanation: 'apple' is inserted first. Exact search for 'apple' is True, exact search for 'app' is False until 'app' is inserted, while startsWith('app') is already True because 'apple' starts with it.

Input: [('search', 'dog'), ('startsWith', 'do')]

Expected Output: [False, False]

Explanation: No words have been inserted yet, so both the exact search and prefix check return False.

Input: []

Expected Output: []

Explanation: With no operations, the returned result is an empty list.

Input: [('insert', 'cat'), ('insert', 'cat'), ('search', 'cat'), ('startsWith', 'ca'), ('search', 'car')]

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

Explanation: Inserting the same word twice is allowed. 'cat' exists, 'ca' is a valid prefix, and 'car' was never inserted.

Input: [('insert', ''), ('search', ''), ('startsWith', ''), ('startsWith', 'a')]

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

Explanation: After inserting the empty string, searching for it succeeds. Every word starts with the empty prefix, but no stored word starts with 'a'.

Hints

A trie stores one character per level and is a natural fit for both exact word checks and prefix checks.
Exact search and prefix search traverse similarly; only exact search must verify an end-of-word marker.

Part 3: Implement a Fixed-Capacity Least-Recently-Used Cache

Simulate an LRU cache using a function interface. The function receives a positive integer capacity and a list of operations. Each operation is either ('put', key, value) or ('get', key). Return a list aligned with the operations: append None for each put, and append the returned integer for each get. Accessing or updating a key makes it the most recently used item. When the cache exceeds capacity, evict the least recently used key.

Constraints

1 <= capacity <= 30000
0 <= len(operations) <= 200000
0 <= key <= 1000000000
0 <= value <= 1000000000

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

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

Explanation: After getting key 1, it becomes most recently used. Putting 3 evicts 2. Putting 4 later evicts 1.

Input: (1, [('put', 2, 1), ('put', 3, 2), ('get', 2), ('get', 3), ('put', 4, 3), ('get', 4)])

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

Explanation: With capacity 1, each new key evicts the previous one. Key 2 is gone after putting 3, and key 3 is gone after putting 4.

Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('put', 3, 3), ('get', 2), ('get', 1), ('get', 3)])

Expected Output: [None, None, None, None, -1, 10, 3]

Explanation: Updating key 1 changes its value and makes it most recently used, so key 2 is evicted when key 3 is inserted.

Input: (3, [])

Expected Output: []

Explanation: No operations means the result is an empty list.

Hints

Use a hash map for O(1) access to cache entries and a doubly linked list to track recency order.
Move a key to the front whenever it is read or updated, and remove from the tail when eviction is needed.

Quick Overview