How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Roblox.

What role is this question designed for?

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

Rank queries by prefix, frequency, and time

Q: Rank queries by prefix, frequency, and time

This question evaluates understanding of string processing, frequency aggregation, earliest-timestamp tracking, and efficient prefix-based retrieval for large datasets.

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given three arrays of the same length `n`: - `queries[i]`: a non-empty string representing the text of the i-th query. - `timestamps[i]`: an integer representing the time when `queries[i]` was issued. - `0 <= i < n`. You are also given an array `prefixes` of length `m`, where each `prefixes[j]` is a non-empty string. For each prefix `p` in `prefixes`, you must find **all distinct query strings** that start with `p` (i.e., `query.startsWith(p)`), then sort those distinct queries by: 1. **Descending frequency**: the number of times that exact query string appears in `queries`. 2. If multiple queries have the same frequency, break ties by **ascending earliest timestamp**: for a given query string `q`, look at all indices `k` where `queries[k] == q` and take `min(timestamps[k])`; the query with the smaller earliest timestamp comes first. Return, for each prefix `prefixes[j]`, the list of matching query strings sorted according to the above rules. Assume: - `1 <= n, m <= 2 * 10^5` (large enough that an $O(nm)$ solution will time out). - `1 <= len(queries[i]), len(prefixes[j]) <= 50`. - `timestamps[i]` fit in a 32-bit signed integer. You may return the result in any reasonable structure; for example, an array `result` of length `m`, where `result[j]` is a list of strings for prefix `prefixes[j]`. **Example** Input: - `queries = ["apple", "app", "banana", "app", "application"]` - `timestamps = [5, 3, 10, 7, 8]` - `prefixes = ["ap", "app", "b"]` Processing: - For prefix `"ap"`: - Matching queries: `"apple"`, `"app"`, `"app"`, `"application"`. - Distinct query strings and frequencies: - `"app"`: appears 2 times, earliest timestamp = `min(3, 7) = 3`. - `"apple"`: appears 1 time, earliest timestamp = `5`. - `"application"`: appears 1 time, earliest timestamp = `8`. - Sorted: `"app"` (freq 2), then `"apple"` (freq 1, time 5), then `"application"` (freq 1, time 8). - For prefix `"app"`: - Matching queries: `"apple"`, `"app"`, `"app"`, `"application"` (same set as above since all start with "app"). - Sorted order is the same as for `"ap"`. - For prefix `"b"`: - Matching queries: `"banana"` only, with frequency 1 and earliest timestamp 10. Output (conceptually): - For `"ap"`: `["app", "apple", "application"]` - For `"app"`: `["app", "apple", "application"]` - For `"b"`: `["banana"]`

Quick Answer: This question evaluates understanding of string processing, frequency aggregation, earliest-timestamp tracking, and efficient prefix-based retrieval for large datasets.

You are given three arrays of the same length n:

queries[i] : a non-empty string representing the text of the i-th query.
timestamps[i] : an integer representing the time when queries[i] was issued.
0 <= i < n .

You are also given an array prefixes of length m, where each prefixes[j] is a non-empty string.

For each prefix p in prefixes, you must find all distinct query strings that start with p (i.e., query.startsWith(p)), then sort those distinct queries by:

Descending frequency : the number of times that exact query string appears in queries .
If multiple queries have the same frequency, break ties by ascending earliest timestamp : for a given query string q , look at all indices k where queries[k] == q and take min(timestamps[k]) ; the query with the smaller earliest timestamp comes first.

Return, for each prefix prefixes[j], the list of matching query strings sorted according to the above rules.

Assume:

1 <= n, m <= 2 * 10^5 (large enough that an $O(nm)$ solution will time out).
1 <= len(queries[i]), len(prefixes[j]) <= 50 .
timestamps[i] fit in a 32-bit signed integer.

You may return the result in any reasonable structure; for example, an array result of length m, where result[j] is a list of strings for prefix prefixes[j].

Example

Input:

queries = ["apple", "app", "banana", "app", "application"]
timestamps = [5, 3, 10, 7, 8]
prefixes = ["ap", "app", "b"]

Processing:

For prefix "ap" :
- Matching queries: "apple" , "app" , "app" , "application" .
- Distinct query strings and frequencies:
  - "app" : appears 2 times, earliest timestamp = min(3, 7) = 3 .
  - "apple" : appears 1 time, earliest timestamp = 5 .
  - "application" : appears 1 time, earliest timestamp = 8 .
- Sorted: "app" (freq 2), then "apple" (freq 1, time 5), then "application" (freq 1, time 8).
For prefix "app" :
- Matching queries: "apple" , "app" , "app" , "application" (same set as above since all start with "app").
- Sorted order is the same as for "ap" .
For prefix "b" :
- Matching queries: "banana" only, with frequency 1 and earliest timestamp 10.

Output (conceptually):

For "ap" : ["app", "apple", "application"]
For "app" : ["app", "apple", "application"]
For "b" : ["banana"]

Rank queries by prefix, frequency, and time

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Quick Answer: This question evaluates understanding of string processing, frequency aggregation, earliest-timestamp tracking, and efficient prefix-based retrieval for large datasets.

You are given three arrays of the same length n:

queries[i] : a non-empty string representing the text of the i-th query.
timestamps[i] : an integer representing the time when queries[i] was issued.
0 <= i < n .

You are also given an array prefixes of length m, where each prefixes[j] is a non-empty string.

For each prefix p in prefixes, you must find all distinct query strings that start with p (i.e., query.startsWith(p)), then sort those distinct queries by:

Descending frequency : the number of times that exact query string appears in queries .
If multiple queries have the same frequency, break ties by ascending earliest timestamp : for a given query string q , look at all indices k where queries[k] == q and take min(timestamps[k]) ; the query with the smaller earliest timestamp comes first.

Return, for each prefix prefixes[j], the list of matching query strings sorted according to the above rules.

Assume:

1 <= n, m <= 2 * 10^5 (large enough that an $O(nm)$ solution will time out).
1 <= len(queries[i]), len(prefixes[j]) <= 50 .
timestamps[i] fit in a 32-bit signed integer.

You may return the result in any reasonable structure; for example, an array result of length m, where result[j] is a list of strings for prefix prefixes[j].

Example

Input:

queries = ["apple", "app", "banana", "app", "application"]
timestamps = [5, 3, 10, 7, 8]
prefixes = ["ap", "app", "b"]

Processing:

For prefix "ap" :
- Matching queries: "apple" , "app" , "app" , "application" .
- Distinct query strings and frequencies:
  - "app" : appears 2 times, earliest timestamp = min(3, 7) = 3 .
  - "apple" : appears 1 time, earliest timestamp = 5 .
  - "application" : appears 1 time, earliest timestamp = 8 .
- Sorted: "app" (freq 2), then "apple" (freq 1, time 5), then "application" (freq 1, time 8).
For prefix "app" :
- Matching queries: "apple" , "app" , "app" , "application" (same set as above since all start with "app").
- Sorted order is the same as for "ap" .
For prefix "b" :
- Matching queries: "banana" only, with frequency 1 and earliest timestamp 10.

Output (conceptually):

For "ap" : ["app", "apple", "application"]
For "app" : ["app", "apple", "application"]
For "b" : ["banana"]

Rank queries by prefix, frequency, and time

Quick Overview

Comments (0)

Rank queries by prefix, frequency, and time

Quick Overview

Comments (0)