Position: Intern

1st Round:
Decode a given encoded string

Example 1: "ab(cde){3}" -> "abcdecdecde"
Example 2: "a(bc(e){3}){2} -> "abceeebceee"

Similar problem: https://leetcode.com/problems/decode-string/

2nd round:
The interviewer started with a simple question and progressively added more constraints. At each step he asked for the time and space complexity of the solution

2.1 The initial question:
A transform is given as follows -- If number (n) is even, transform it to (n/2). If it is odd n -> (3 * n + 1). Stop until number is 1.

Example:
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Number of transforms: 7

I was asked to implement this function iteratively and recursively.

2.2
Given a range [1, N], return the k-th largest transform count.

Example:
N = 4, k = 2
transform_counts = [0, 1, 7, 2]
Return 4, since for n=4, count is 2

2.3
What if memory is limited?
Return all the indices of the k-th largest unique count