Amazon (SDE AWS, Berlin) | Phone | Column Traversel Tree and Car Pooling
Anonymous User
1399

First 15 Min behavorial part about some questions surrounding Leadership principles.

1. Question: Sum up the Trees nodes column wise.

image

This is a sub problem of https://leetcode.com/problems/binary-tree-vertical-order-traversal/ but only the column by column part.
Solution:
Solved this with a recursion and a hashmap. Traverse the map from the root and a column variable, everytime you go left you add +1 and everytime you go right you -1
Then you put the column number into a Map<Integer, Integer> where the key is the column and the values is the sum. At the end add the values to a integer list.

2. Question:
Exactly this Question: https://leetcode.com/problems/car-pooling/
But instead of cars and passenger it was a truck and packages.

I told her in the beginning i saw that problem last week and knew the solution. She didnt really care and told me to state my algorithm and code it down.
Solution:

I solved it with an array in O(n) and O(n) space complexity solution. Exactly coded the solution down like this:
'''

public boolean carPooling(int[][] trips, int capacity) {
    int road[] = fillUpRoad(trips);
    
    int currentCap = 0;
    
    for(int i = 0; i < road.length; i++) {
        currentCap += road[i];
        if(currentCap > capacity) {
            return false;
        }
    };
    
    return true;
}

public int[] fillUpRoad(int[][] trips) {
    int road[] = new int[1001];
    
    for(int i = 0; i < trips.length; i++) {
        int tripCapacity = trips[i][0];
        int start = trips[i][1];
        int end = trips[i][2];
        
        road[start] += tripCapacity;
        road[end] -= tripCapacity;
        
    }
    
    return road;
}

'''

Proceeded to the onsites 4 Days later.

Comments (5)