Google OA/Phonescreen [L4] - 24 Dec 2025

1. There are N coins valued (0 to N - 1).
   Calculate no. of ways to select K coins such that their sum is divisible by M.
   Return answer modulo 1e9 + 7.

int solve(int N, int M, int K)

Input:
4 2 2
Output: 2

Constraints:
1 <= N, M, K <= 10^3

2. Given tree graph with N nodes/regions (1 to N) and (N - 1) bidirectional edges/roads.
   Each node/region (i + 1) has no. of towns denoted by towns[i].
   Calculate min difference in total sum of towns between resulting components when you delete one edge.

int minTownsDiff(int N, vector<int>& towns, vector<vector<int>>& roads)

Input:
2
10 20
1 2
Output: 10

Constraints:
1 <= N <= 10^5
1 <= towns[i] <= 10^4

3. Phonescreen Round
   Given a playlist of songs. Implement a shuffle function, such that there is no/minimal adjacent artists.

using Song = pair<string, string>; // (artist, song)
void shuffle(vector<Song>& playlist)

Input:

[
  { "artist": "A", "song": "apple" },
  { "artist": "A", "song": "banana" },
  { "artist": "B", "song": "orange" },
  { "artist": "B", "song": "guava" },
  { "artist": "C", "song": "mango" }
]

Output: ABABC