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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

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

Return Top K Open Businesses | Microsoft Coding Question

Return Top K Open Businesses

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a list of business candidates. Each candidate has at least the following fields: - `score`: a numeric relevance score - `distance`: a numeric distance from the user - `isOpen`: a boolean indicating whether the business is currently open Write a function that returns the top `k` open businesses. Sorting requirements: 1. Higher `score` comes first. 2. If two businesses have the same `score`, the business with the smaller `distance` comes first. Return the selected businesses in the required order.

Quick Answer: This question evaluates a candidate's ability to perform filtering and multi-criteria ranking, requiring correct handling of an open-status filter and tie-breaking by score and distance.

You are given a list of business candidate dictionaries. Each business has at least these fields: `score` (numeric relevance score), `distance` (numeric distance from the user), and `isOpen` (boolean). Write a function that returns the top `k` businesses that are currently open. Ranking rules: 1. Higher `score` comes first. 2. If two businesses have the same `score`, the one with the smaller `distance` comes first. 3. If both `score` and `distance` are equal, keep their original relative order. If `k` is larger than the number of open businesses, return all open businesses in the required order. If `k` is 0, return an empty list.

Constraints

0 <= len(businesses) <= 100000
0 <= k <= 100000
Each business contains at least the keys 'score', 'distance', and 'isOpen'
'score' and 'distance' are numeric values
If k exceeds the number of open businesses, return all open businesses

Examples

Input: ([{'id': 'A', 'score': 4.8, 'distance': 3.2, 'isOpen': True}, {'id': 'B', 'score': 4.9, 'distance': 5.0, 'isOpen': False}, {'id': 'C', 'score': 4.8, 'distance': 1.1, 'isOpen': True}, {'id': 'D', 'score': 5.0, 'distance': 4.0, 'isOpen': True}], 2)

Expected Output: [{'id': 'D', 'score': 5.0, 'distance': 4.0, 'isOpen': True}, {'id': 'C', 'score': 4.8, 'distance': 1.1, 'isOpen': True}]

Explanation: Only open businesses are A, C, and D. D has the highest score. A and C have the same score, so the closer one, C, comes first.

Input: ([{'id': 'X', 'score': 4.2, 'distance': 2.0, 'isOpen': True}, {'id': 'Y', 'score': 4.2, 'distance': 2.0, 'isOpen': True}, {'id': 'Z', 'score': 3.9, 'distance': 1.0, 'isOpen': False}, {'id': 'W', 'score': 4.2, 'distance': 1.5, 'isOpen': True}], 10)

Expected Output: [{'id': 'W', 'score': 4.2, 'distance': 1.5, 'isOpen': True}, {'id': 'X', 'score': 4.2, 'distance': 2.0, 'isOpen': True}, {'id': 'Y', 'score': 4.2, 'distance': 2.0, 'isOpen': True}]

Explanation: There are only three open businesses, so all are returned. W comes first because it is closer among businesses with the same score. X and Y remain in original order because both score and distance are equal.

Input: ([], 3)

Expected Output: []

Explanation: An empty input list has no open businesses to return.

Input: ([{'id': 'P', 'score': 5, 'distance': 10, 'isOpen': True}, {'id': 'Q', 'score': 2, 'distance': 1, 'isOpen': True}], 0)

Expected Output: []

Explanation: When k is 0, the result must be an empty list regardless of the businesses available.

Hints

It may be easier to ignore all closed businesses first, then rank only the remaining ones.
A single sort key can handle both rules: descending by score and ascending by distance.

Quick Overview

This question evaluates a candidate's ability to perform filtering and multi-criteria ranking, requiring correct handling of an open-status filter and tie-breaking by score and distance.