Katkat
Back

Return Top K Open Businesses

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to filter data streams and maintain a top-K collection using a priority queue with custom sorting logic.

Problem Statement

You are given a list of businesses, where each business is represented as an object or dictionary containing: id (int), is_open (boolean), rating (float), and distance (int).

Your task is to write a function get_top_k_businesses(businesses, k) that returns the IDs of the top K businesses that are currently open. The ranking criteria are as follows:

  1. Higher rating is better.
  2. If ratings are equal, smaller distance is better.
  3. If both rating and distance are equal, smaller id is better.

Function Signature

def get_top_k_businesses(businesses, k):
    # businesses: List of dicts {'id': int, 'is_open': bool, 'rating': float, 'distance': int}
    # k: int
    # returns: List of int (IDs)

Examples

Example 1:

Input:
businesses = [
  {'id': 1, 'is_open': True, 'rating': 4.5, 'distance': 10},
  {'id': 2, 'is_open': False, 'rating': 5.0, 'distance': 2},
  {'id': 3, 'is_open': True, 'rating': 4.5, 'distance': 5}
]
k = 2
Output: [3, 1]
Explanation: Business 2 is excluded because it is closed. Business 3 ranks higher than 1 due to smaller distance.

Constraints

  • businesses length: up to 10^5.
  • k is between 1 and the number of open businesses.
  • rating values are in the range [0.0, 5.0].

Edge Cases

  • No businesses are open.
  • Multiple businesses have the exact same rating and distance.
  • k is larger than the total number of open businesses.

Hints

Hint 1

First, filter the input list to include only businesses where `is_open` is true.

Hint 2

Consider using a min-heap to keep track of the top K elements, where you replace the smallest element if you find a better one.

Hint 3

Define a custom comparison rule for your sorting or heap: (rating, -distance, -id) helps in ordering the elements correctly.

Follow-up questions

  • How would your approach change if the number of businesses was in the billions and didn't fit into memory?
  • What is the time complexity of your solution, and can you optimize it to be better than O(N log K)?
  • How would you handle a scenario where business ratings are updated in real-time?