Technical Screen Interview

Question: Something related to Airflow Task Scheduling.
You are given $N$ tasks (labeled $0$ to $N-1$) and a list of dependencies where $dependencies[i]=[a,b]$ indicates that task $a$ must be completed before task $b$ can start.

Basically the idea was to do topological sort and find the order of execution.

Coding Interview 1

You're in a ski tournament, where you ski from top of the mountain to one of the finish checkpoints at the bottom. There are multiple routes with checkpoints (each checkpoint has an associated point with it). And your total score = (points from all checkpoints you visited - time of your travel).

Given: A List of lists, that consists [start_cp, end_cp, time_to_travel]

A list of lists, that consists [cp, point]

Goal: Find the maximum score that you can collect during the tournament and print out the optimal path.

                  START[0]
                   / | \
                  5  6  10
                 /   |   \
              A[24] B[3] C[10]             
                 \   |   /|
                  4  5  6 5
                   \ | /  |
                    D[7] E[24]
                      \   |
                       3  1
                        \ |
                         F[3]
                         / \
                        5  10
                       /     \
                   END_1[4]  END_2[7]

Input:

vector<vector<string> > paths({
    {"START", "A", "5"},
    {"START", "B", "6"},
    {"START", "C", "10"},
    {"A", "D", "4"},
    {"B", "D", "5"},
    {"C", "D", "6"},
    {"C", "E", "5"},
    {"D", "F", "3"},
    {"E", "F", "1"},
    {"F", "END_1", "5"},
    {"F", "END_2", "10"}
});
vector<vector<string> > points({
    {"START", "0"},
    {"A", "24"},
    {"B", "3"},
    {"C", "10"},
    {"D", "7"},
    {"E", "24"},
    {"F", "3"},
    {"END_1", "4"},
    {"END_2", "7"}
});

• Interviewer was very strict about the 45 min time window.
• Discussed various approaches: DFS, BFS & Dijkstra.
• Spoke indepth about time and space complexity for each.
• Finally we concluded on using DFS and optimised using DP
• Honeslty I did not think that I'll be able to write down the working solution, but I was able to provide.
• Towards the end interviewer spent extra 5 mins and asked me to dry run with an example.

Coding Interview 2

At Airbnb, we want each person to have only one account to ensure trust and prevent misuse of our platform. Sometimes, people can end up with multiple accounts by using the same email, phone number, governement Id, same device or other identity information.
We need a way to find accounts that are duplicates of one another.

Given a list of Airbnb accounts (each named "A", "B", etc.) with their identity attributes (such as email address, phone number, etc) build a function that will return duplicate accounts for any given account.

Input 1

Accounts = [
    {name: A, email: alice@example.com, phone: 12345},
    {name: B, email: bob@example.com, phone: 23456},
    {name: C, email: ALICE@example.com, phone: 67890},
    {name: D, email: doug@example.com, phone: 12345},
]
account = A

Output

Duplicate Accounts = [C, D]

Started with simple hashing solution, suggested to create index for each unique identifier type.

FollowUp: what if we add another identifier GovtId?

We can't keep adding indexes, that's not optimal.
I modified the input to add a new account

• Accounts.add({name: E, email: doug@example.com, phone: 766755});

Interviewer clarified that

• Output: Duplicates of A is [C, D, E]

Clarified that accountName will be unique in Accounts.
With just 15 mins left, it instantly clicked to me that the question is similar to connected components.

// uniqueIdentifier(email,phone,govtId...etc) -> parentAccountName
unordered_map<string,string> uniqueIdentifierMap;
// accountName -> parentAccountName 
unordered_map<string, string> parent;

for every account
    -parent[accountName] = accountName
    - for every identifier
        - if uniqueIdentifier doesn't exist in uniqueIdentifierMap
            - parent = findParent(accountName)
            - duplicateParent = findParent(identifierMapping[identifier])
            // accountName doesn't have duplicate
            - if(parent==accountName) 
                // update parent of accountName
                - parent[accountName] =  duplicateParent
            - else
                // update the parent of parent account  
                - parents[parent] = duplicateParent 
        - else 
            - uniqueIdentifierMap[identifier] = accountName

- now we have the connected accountName through parent map
- for the given accountName find parent and iterate over all nodes to check for common parent.

I was able to do all of this + run testcases in 46 mins.
Interviewer wanted me to dry run a simple example through the code which took another 4 mins.