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 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 Relevant Apps | Microsoft Coding Question

Return Top K Relevant Apps

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a mapping from application name to keyword relevance scores, for example: ```json { "github": {"diff": 0.3, "code review": 0.8}, "jira": {"ticket": 0.7, "workflow": 0.4} } ``` Define an application's overall relevance as the sum of all its keyword scores. Given this structure and an integer `k`, return the names of the `k` most relevant applications sorted by descending relevance. If two applications have the same total relevance, break ties by application name in ascending lexicographic order. Discuss an efficient approach and its time complexity.

Quick Answer: This question evaluates algorithmic problem-solving around aggregation and ranking, testing skills in computing aggregated relevance scores, deterministic tie-breaking, and efficient selection of top-k items.

You are given a nested mapping where each application name maps to another mapping of keywords to relevance scores. The overall relevance of an application is the sum of all its keyword scores. Given this structure and an integer k, return the names of the k most relevant applications sorted by descending total relevance. If two applications have the same total relevance, break ties by application name in ascending lexicographic order. If k is larger than the number of applications, return all application names in the required order. If k is 0 or negative, return an empty list.

Constraints

0 <= number of applications <= 10^5
0 <= total number of keyword entries across all applications <= 2 * 10^5
k may be 0 or larger than the number of applications
Relevance scores are real numbers, and an application with no keywords has total relevance 0

Examples

Input: ({"github": {"diff": 0.3, "code review": 0.8}, "jira": {"ticket": 0.7, "workflow": 0.4}, "slack": {"chat": 0.5}}, 2)

Expected Output: ["github", "jira"]

Explanation: github and jira both have total relevance 1.1, which is higher than slack's 0.5. The tie is broken lexicographically, so github comes before jira.

Input: ({"zoom": {"meet": 0.5}, "asana": {"task": 0.5}, "notion": {"doc": 0.7}}, 2)

Expected Output: ["notion", "asana"]

Explanation: notion has the highest total relevance at 0.7. asana and zoom are tied at 0.5, and asana comes first lexicographically.

Input: ({"figma": {"design": 0.9}, "miro": {}}, 5)

Expected Output: ["figma", "miro"]

Explanation: figma has total relevance 0.9, while miro has no keywords and totals 0. Since k exceeds the number of applications, return all of them in ranked order.

Input: ({}, 3)

Expected Output: []

Explanation: There are no applications, so the result is an empty list.

Input: ({"alpha": {"x": 1.0}, "beta": {"y": 2.0}}, 0)

Expected Output: []

Explanation: When k is 0, no applications should be returned.

Hints

First reduce each application to a single total score by summing its keyword relevance values.
After computing totals, think about ordering pairs like (app_name, total_score) by total descending and name ascending; a size-k heap can avoid sorting everything.

Quick Overview

This question evaluates algorithmic problem-solving around aggregation and ranking, testing skills in computing aggregated relevance scores, deterministic tie-breaking, and efficient selection of top-k items.