Katkat
Back

Find Shortest Queue with Few Calls

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize search operations across multiple data sources, focusing on minimizing high-latency API calls by using heuristic strategies and efficient state management.

Problem Statement

You are tasked with finding the shortest queue among N remote queues. You are provided with an API get_queue_size(queue_id) which returns the integer length of a queue. However, calling this API is expensive, and you want to minimize the number of calls made.

Furthermore, each queue has an associated 'priority' value (a float between 0 and 1). You are told that the actual size of a queue is correlated with its priority: higher priority queues are statistically more likely to have smaller sizes.

Implement a function find_shortest_queue(queue_ids, get_size_api) that returns the ID of the queue with the minimum size.

Constraints

  • queue_ids: A list of strings representing unique identifiers.
  • N (number of queues) can be up to 10,000.
  • You should aim for a solution that significantly reduces the number of API calls compared to checking every single queue.
  • You may assume you have access to a function get_priority(queue_id) that returns the priority.

Example

Input: queue_ids = ['q1', 'q2', 'q3'] priorities = {'q1': 0.9, 'q2': 0.1, 'q3': 0.5}

  • If get_size_api returns 10 for 'q1', 2 for 'q2', and 5 for 'q3', the function should return 'q1' if queried first, but ideally, you'd check 'q1' first due to its high priority.

Edge Cases

  • What if multiple queues have the same priority?
  • What if the API returns 0 for a queue size?
  • How do you handle empty input lists?

Hints

Hint 1

Consider sorting the queues by their priority scores in descending order before making any API calls.

Hint 2

Maintain a variable to keep track of the smallest size found so far to prune the search space.

Hint 3

Think about implementing a stopping condition: if the current best size is 0, you can terminate early since no queue can be smaller than 0.

Follow-up questions

  • How would your approach change if the priority values were not static but updated periodically based on recent activity?
  • If the API had a cost associated with each call, how would you modify the algorithm to optimize for 'cost' instead of just the 'number of calls'?
  • How would you handle potential network latency or API timeouts when calling `get_size_api` for 10,000 queues?