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 Apple.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Apple during technical interviews.

Implement Kubernetes Service Dependency Queries

Company: Apple

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an in-memory inventory of Kubernetes-like services. Each service has the following fields: ```text Service { id: string // unique, for example "namespace/name" name: string namespace: string attributes: map<string, string> status: one of {"Healthy", "Degraded", "Down", "Unknown"} dependencies: list<string> // service IDs this service depends on } ``` Implement a small query library for this inventory. 1. **Filtering:** Implement `filterServices(services, criteria)` where `criteria` may include: - an optional namespace, - a set of required attribute key-value pairs, all of which must match, - an optional set of allowed statuses. Return all matching services in deterministic order, sorted by service ID. 2. **Dependency traversal:** Implement `getDependencyChain(services, rootId)` that returns all transitive dependencies reachable from `rootId`, including each dependency's status. The implementation should handle missing dependencies and cycles gracefully. 3. **Status query along a chain:** Implement `queryStatusAlongDependencyChain(services, rootId)` that reports the status of every service along every dependency path starting at `rootId`. The result should make it easy to identify whether a degraded or down dependency may affect the root service. 4. **Design extension:** Suppose this query library is exposed as a Model Context Protocol-style tool server for an AI agent. Describe how the agent should call the tools and how you would reduce noisy or irrelevant results.

Quick Answer: This question evaluates proficiency with data structures and algorithms for service inventory operations, including deterministic filtering, attribute matching, graph traversal for transitive dependency resolution, and status propagation across service graphs.

Part 1: Filter Kubernetes Services

You are given an in-memory list of service records. Implement filtering by optional namespace, required attribute key-value pairs, and optional allowed statuses. A service matches only if all provided filters match. Return matching service IDs in deterministic order sorted lexicographically by ID. If 'allowed_statuses' is provided as an empty list, no service matches.

Constraints

0 <= len(services) <= 10000
Each service ID is unique
Each service has at most 50 attributes
Status is one of 'Healthy', 'Degraded', 'Down', or 'Unknown'

Examples

Input: ([{'id': 'ns1/b', 'name': 'b', 'namespace': 'ns1', 'attributes': {'tier': 'backend'}, 'status': 'Degraded', 'dependencies': []}, {'id': 'ns1/a', 'name': 'a', 'namespace': 'ns1', 'attributes': {'tier': 'backend', 'app': 'api'}, 'status': 'Healthy', 'dependencies': ['ns1/b']}, {'id': 'ns2/c', 'name': 'c', 'namespace': 'ns2', 'attributes': {'tier': 'frontend'}, 'status': 'Healthy', 'dependencies': []}, {'id': 'ns1/d', 'name': 'd', 'namespace': 'ns1', 'attributes': {'team': 'platform'}, 'status': 'Down', 'dependencies': []}], {'namespace': 'ns1', 'required_attributes': {'tier': 'backend'}, 'allowed_statuses': ['Healthy', 'Degraded']})

Expected Output: ['ns1/a', 'ns1/b']

Explanation: Only ns1/a and ns1/b are in namespace ns1, have tier=backend, and have an allowed status.

Input: ([{'id': 'z', 'name': 'z', 'namespace': 'ops', 'attributes': {}, 'status': 'Unknown', 'dependencies': []}, {'id': 'a', 'name': 'a', 'namespace': 'default', 'attributes': {}, 'status': 'Healthy', 'dependencies': []}], {})

Expected Output: ['a', 'z']

Explanation: With no filters, all services match and are returned in sorted order.

Hints

Check each optional filter independently; missing filters should not block a match.
For required attributes, every key-value pair must be present in the service's attributes map.

Part 2: Transitive Dependency Status Lookup

Given a service inventory and a root service ID, return every distinct transitive dependency reachable from the root. Follow dependencies in the order they appear in each service. Use depth-first traversal order, report each dependency at most once, exclude the root itself even if a cycle points back to it, and handle missing dependency IDs by returning them with status 'Missing'. If the root service does not exist, return an empty list.

Constraints

0 <= len(services) <= 10000
The total number of dependency edges is at most 20000
Each service ID is unique
Cycles may exist in the dependency graph

Examples

Expected Output: [{'id': 'b', 'status': 'Degraded'}, {'id': 'd', 'status': 'Down'}, {'id': 'c', 'status': 'Healthy'}, {'id': 'e', 'status': 'Missing'}]

Explanation: Traversal discovers b, then d, then c, then missing e. The cycle back to a is ignored.

Input: ([{'id': 'solo', 'name': 'solo', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': []}], 'solo')

Expected Output: []

Explanation: A service with no dependencies has an empty dependency chain.

Hints

Build a map from service ID to service data so lookups are O(1).
Mark IDs as seen before exploring children so cycles and repeated references do not cause duplicate work.

Part 3: List Statuses Along Every Dependency Path

Given a root service, enumerate every dependency path starting at that root. Each path should include the root and the status of every service visited. Follow dependencies in the order they are listed. A path ends when it reaches a service with no dependencies, a missing dependency, or a cycle. Represent a missing dependency with status 'Missing' and a repeated node on the current path with status 'Cycle'. If the root does not exist, return one path containing only the missing root marker.

Constraints

1 <= len(services) <= 200 for typical cases
The total number of returned paths is guaranteed to fit in memory
Cycles may exist
Each service ID is unique

Examples

Input: ([{'id': 'a', 'name': 'a', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['b', 'c']}, {'id': 'b', 'name': 'b', 'namespace': 'ns', 'attributes': {}, 'status': 'Degraded', 'dependencies': ['d']}, {'id': 'c', 'name': 'c', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['e', 'f']}, {'id': 'd', 'name': 'd', 'namespace': 'ns', 'attributes': {}, 'status': 'Down', 'dependencies': []}, {'id': 'e', 'name': 'e', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['a']}, {'id': 'f', 'name': 'f', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['x']}], 'a')

Expected Output: [[{'id': 'a', 'status': 'Healthy'}, {'id': 'b', 'status': 'Degraded'}, {'id': 'd', 'status': 'Down'}], [{'id': 'a', 'status': 'Healthy'}, {'id': 'c', 'status': 'Healthy'}, {'id': 'e', 'status': 'Healthy'}, {'id': 'a', 'status': 'Cycle'}], [{'id': 'a', 'status': 'Healthy'}, {'id': 'c', 'status': 'Healthy'}, {'id': 'f', 'status': 'Healthy'}, {'id': 'x', 'status': 'Missing'}]]

Explanation: The result shows one normal leaf path, one cycle-terminated path, and one missing-dependency path.

Input: ([{'id': 'solo', 'name': 'solo', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': []}], 'solo')

Expected Output: [[{'id': 'solo', 'status': 'Healthy'}]]

Explanation: A leaf root still produces one path containing the root.

Hints

Use DFS with backtracking and keep a set of IDs currently on the path to detect cycles.
A shared dependency can appear in multiple output paths if it is reached through different branches.

Part 4: Prune Noisy Tool Results for an AI Agent

An AI agent already ran a broad filter tool and received a list of candidate service IDs. To reduce noisy or irrelevant results, keep only candidates that are actually reachable from a given root service through dependencies. For each kept candidate, report its ID, status, and shortest distance from the root. Ignore duplicate candidate IDs, ignore candidates not present in the inventory, and ignore candidates that are not reachable from the root. Sort results by severity first ('Down' before 'Degraded' before 'Unknown' before 'Healthy'), then by smaller distance, then by lexicographically smaller ID. Return at most max_results items.

Constraints

0 <= len(services) <= 10000
0 <= len(candidate_ids) <= 10000
The total number of dependency edges is at most 20000
0 <= max_results <= len(candidate_ids) + 1

Examples

Input: ([{'id': 'a', 'name': 'a', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['b', 'c']}, {'id': 'b', 'name': 'b', 'namespace': 'ns', 'attributes': {}, 'status': 'Down', 'dependencies': []}, {'id': 'c', 'name': 'c', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['d']}, {'id': 'd', 'name': 'd', 'namespace': 'ns', 'attributes': {}, 'status': 'Degraded', 'dependencies': []}, {'id': 'e', 'name': 'e', 'namespace': 'ns', 'attributes': {}, 'status': 'Down', 'dependencies': []}], 'a', ['x', 'c', 'd', 'b', 'e', 'b'], 3)

Expected Output: [{'id': 'b', 'status': 'Down', 'distance': 1}, {'id': 'd', 'status': 'Degraded', 'distance': 2}, {'id': 'c', 'status': 'Healthy', 'distance': 1}]

Explanation: Only b, c, and d are both present and reachable from a. They are sorted by severity, then distance.

Input: ([{'id': 'a', 'name': 'a', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': ['b']}, {'id': 'b', 'name': 'b', 'namespace': 'ns', 'attributes': {}, 'status': 'Unknown', 'dependencies': []}], 'a', ['a', 'b'], 2)

Expected Output: [{'id': 'b', 'status': 'Unknown', 'distance': 1}, {'id': 'a', 'status': 'Healthy', 'distance': 0}]

Explanation: Both are reachable, but Unknown ranks ahead of Healthy.

Hints

Use BFS from the root to compute shortest distances in an unweighted dependency graph.
Filtering by reachability before sorting is an effective way to remove irrelevant results.

Quick Overview