PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

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.

  • medium
  • Apple
  • Coding & Algorithms
  • Machine Learning Engineer

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.

Input: ([], {'namespace': 'ns1'})

Expected Output: []

Explanation: Empty input should return an empty list.

Input: ([{'id': 'a', 'name': 'a', 'namespace': 'ns1', 'attributes': {'app': 'api'}, 'status': 'Healthy', 'dependencies': []}], {'allowed_statuses': []})

Expected Output: []

Explanation: An explicitly empty allowed-status list means nothing is allowed.

Hints

  1. Check each optional filter independently; missing filters should not block a match.
  2. 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

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': ['b', 'e']}, {'id': 'd', 'name': 'd', 'namespace': 'ns', 'attributes': {}, 'status': 'Down', 'dependencies': ['a']}], 'a')

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.

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

Expected Output: []

Explanation: If the root is absent, there are no reachable dependencies.

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

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

Explanation: Repeated references to the same dependency should appear only once.

Hints

  1. Build a map from service ID to service data so lookups are O(1).
  2. 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.

Input: ([{'id': 'a', 'name': 'a', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': []}], 'missing-root')

Expected Output: [[{'id': 'missing-root', 'status': 'Missing'}]]

Explanation: A missing root is reported explicitly.

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

Expected Output: [[{'id': 'a', 'status': 'Healthy'}, {'id': 'x', 'status': 'Missing'}]]

Explanation: A direct missing dependency ends the path with a missing marker.

Hints

  1. Use DFS with backtracking and keep a set of IDs currently on the path to detect cycles.
  2. 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.

Input: ([{'id': 'a', 'name': 'a', 'namespace': 'ns', 'attributes': {}, 'status': 'Healthy', 'dependencies': []}], 'missing-root', ['a'], 5)

Expected Output: []

Explanation: If the root does not exist, nothing can be relevant to it.

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

Expected Output: []

Explanation: A max_results of 0 should always return an empty list.

Hints

  1. Use BFS from the root to compute shortest distances in an unweighted dependency graph.
  2. Filtering by reachability before sorting is an effective way to remove irrelevant results.
Last updated: May 15, 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
  • 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

  • Compute Earliest Bus Arrival - Apple (medium)
  • Find the Extra Edge - Apple (hard)
  • Rotate a Matrix In Place - Apple (medium)
  • Encode and Rebuild a Binary Tree - Apple (hard)
  • Wrap Matching Substrings in Bold Tags - Apple (medium)