Recruiter reached out to me for the opportunity. The first step was Online assessment which had 3 parts:-

1. [105 minutes] Coding Round - 4 problems (2 coding problems, other 2 problems asked me describe my solutions of coding problem)
2. [15 minute] Work Style Survey - Psychometric personality test with vague objective MCQ questions describing myself.
3. [5 minute] Feedback Survey - Optional

---

Problem 1 - Robot Rodeo

Given an Amazonian Robot, that supports three commands:-

• 'L' - Turn direction of Robot to left.
• 'R' - Turn direction of Robot to Right.
• 'G' - Move Robot in its currently set direction

Initially Robot is facing North. You need to find out if the given string of command, if repeated by Robot infinite number of times, is it going to visit finite number of cells? If yes then print "YES" otherwise "NO".

---

Problem 2 - Shopping Options

A customer wants to buy a pair of jeans, a pair of shoes, a skirt, and a top but has a limited budget in dollars. Given different pricing options for each product, determine how many options our customer has to buy 1 of each product. You cannot spend more money than the budgeted amount.

Example
priceOfJeans = [2, 3]
priceOfShoes = [4]
priceOfSkirts = [2, 3]
priceOfTops = [1, 2]
budgeted = 10

The customer must buy shoes for 4 dollars since there is only one option. 
This leaves 6 dollars to spend on the other 3 items. Combinations of prices paid 
for jeans, skirts, and tops respectively that add up to 6 dollars or less are 
[2, 2, 2], [2, 2, 1], [3, 2, 1], [2, 3, 1]. There are 4 ways the customer can purchase all 4 items.

Function Description
Complete the getNumberOfOptions function in the editor below. The function must return an integer which represents the number of options present to buy the four items.

getNumberOfOptions has 5 parameters: int[] priceOfJeans: An integer array, which contains the prices of the pairs of jeans available. int[] priceOfShoes: An integer array, which contains the prices of the pairs of shoes available. int[] priceOfSkirts: An integer array, which contains the prices of the skirts available. int[] priceOfTops: An integer array, which contains the prices of the tops available. int dollars: the total number of dollars available to shop with.

Constraints

• 1 <= a, b, c, d <= 1000
• 1 <= dollars <= 10⁹
• 1 <= price of each item <= 10⁹
• Note: a, b, c and d are the sizes of the four price arrays

Solution 1 - Robot Rodeo

Tricky problem. After working out cases, its a simple solution.
Simulate given command string once, if you

• end up at starting position
• OR direction of robot is not north (initial direction is north).
then you will be visiting finite cells (or in other words loop around finite cells forever).

---

That is it. Lets unbundle and understand it through claims and proofs. Claim 1: if direction of robot is not north after simulate command-string once, then you visit finite cells.
Proof

• Case #1 - Robot is facing South after first simulation of command-string
  Lets say, after first simulation of command-string, it moved A distance in x-direction and B in y-direction. In next simulation of command-string, it has to face North and will have to move -A distance in x-direction and -B in y-direction. Clearly, sum of movement x & y direction is 0 and Robot is facing same orientation and is at start point. So this loop will continue.
• Case #2 - Robot is facing East/West after first simulation of command-string
  Lets say, after first simualtion of command-string, it moved A distance in x-direction and B in y-direction and faces East. In next simulation of command-string, it has to face South and will have to move -A distance in x-direction and B in y-direction. In next simulation of command-string, it has to face West and will have to move A distance in x-direction and -B in y-direction. In next simulation of command-string, it has to face South and will have to move -A distance in x-direction and -B in y-direction. Clearly, sum of movement x & y direction is 0 and Robot is facing same orientation and is at start point. So this loop will continue.
• Case #3 - Robot is facing North after first simulation of command string
  Lets say, after first simualtion of command-string, it moved A distance in x-direction and B in y-direction and faces North. In next simulation of command-string, it has to face North and will have to move A distance in x-direction and B in y-direction. In next simulation of command-string, it has to face North and will have to move A distance in x-direction and B in y-direction. In next simulation of command-string, it has to face North and will have to move A distance in x-direction and B in y-direction. Clearly, sum of movement x & y direction is multiple of A and B respectively and will never sum to 0. Hence Robot keeps on visiting new cells infinitely. No loop.

Here is C++ implementation of the idea.

bool robotRodeo(string instruction) {
    int dx[] = {0, 1, 0, -1}; 
    int dy[] = {1, 0, -1, 0};
    int x = 0, y = 0, dir = 0;
    for (auto cur: instruction) {
        if (cur == 'R') dir = (dir + 1) % 4;
        if (cur == 'L') dir = (dir + 3) % 4; //same as dir -= 1; handled mod underflow
        if (cur == 'G') x += dx[dir], y += dy[dir];
    }
    if (x == 0 and y == 0) return true;
    if (dir != 0) return true;
    return false;
}

---

Problem 2 - Shopping Options

This problem can be solved in O(N² log N). This problem closely resembles famous 4-SUM problem.
Key insight is, instead of bruting over every choice of items out of 4 cateogories one by one, we divide and meet-in-middle.
So first we brute first two choices out of first two category (Jeans, Shoes) and store sum of their prices in vector memory1.
Similarly brute last two choices out of other two category (Skirt, Top) and store sum of their prices in vector memory2.
Sort these two vectors. Now, we need to simply choose 1 item from each of the two vectors and it is going to represent a combination of 4 item choices. Simply do 2 pointer approach to find out pairs of these two choices such that their sum is less than dollars you own.
Here is C++ implementation.

long shoppingOptions(vector jeans, vector shoes, vector skirt, vector top, int dollars) {
    vector memory1, memory2;
    for (auto x: jeans) for (auto y: shoes) memory1.push_back(x+y);
    for (auto x: skirt) for (auto y: top) memory2.push_back(x+y);
    sort(memory1.begin(), memory1.end());
    sort(memory2.begin(), memory2.end());
    long ans = 0, j = memory2.size()-1;
    for (auto x: memory1) {
        while (j >= 0 and x + memory2[j] > dollars) --j;
        ans += j+1;
    }
    return ans;
}