You are given three independent programming tasks. For each, describe and implement an efficient algorithm, and be prepared to analyze its time and space complexity.
You are given a log of chat messages from a messaging application.
Input:
messages
of length
n
, where each element
messages[i]
is the
user_id
(string or integer) of the sender of the i-th message.
k
(1 ≤ k ≤ number of distinct users).
Output:
k
user IDs corresponding to the users who have sent the most messages.
Details & requirements:
messages
).
k
distinct users, return all distinct users.
user_id
in ascending order.
k
is much smaller than the number of distinct users.
Design and implement a function, for example:
List<UserId> topKActiveUsers(List<UserId> messages, int k)
Also explain:
You have a 2D grid with m rows and n columns. Index rows from top to bottom as 0..m-1 and columns from left to right as 0..n-1.
(m-1, 0)
.
(m-1, n-1)
.
From any cell (r, c), you may move only to the next column to the right, in one of up to three ways (if within bounds):
(r-1, c+1)
(r, c+1)
(r+1, c+1)
You cannot move left or stay in the same column. All cells are passable (no obstacles).
Task:
m
and
n
, compute the total number of distinct paths from the start cell
(m-1, 0)
to the end cell
(m-1, n-1)
using only the allowed moves.
Requirements:
long countPaths(int m, int n)
.
You work at a car rental company. You are given a list of rental bookings, each with a pickup and return time.
Input:
R
rental records. Each record has:
rental_id
: a unique identifier (e.g., integer or string).
pickup_time
: an integer start time.
return_time
: an integer end time, with
pickup_time < return_time
.
Assume times are on a single timeline (e.g., minutes from some epoch). A car can be reassigned immediately after it is returned, i.e., if one rental ends at time t and another starts at time t, the same car can serve both.
Tasks:
Output:
C
= minimal number of cars needed.
rental_id
to a
car_id
in the range
1..C
, such that no two rentals assigned to the same
car_id
overlap in time.
Requirements & clarifications:
[s1, e1)
and
[s2, e2)
overlap if their time intervals intersect with non-empty duration. Using half-open intervals, if
e1 == s2
they do
not
overlap.