Uber Engineering Interview

A few weeks back, I got a message from a recruiter at Uber’s engineering team, asking if I was interested in interviewing with them. They had their eyes on the Uber core engineering team, particularly the marketplace group, which handles crucial tasks like driver selection, route planning, and financial transactions. After some thought, I decided to give it a shot.

The interview process followed the typical format of tech companies, starting with phone screenings that included technical coding interviews. If you do well in these, you get invited to one of their office locations (usually where your target team works) for a day of behavioral, technical, and architectural interviews.

During my interview, I tackled a coding problem that I’ll share below. I have to admit, I didn’t manage my time too wisely and ended up with just about 20 minutes to crack it. Here’s the approach I took after my initial attempt.

Question:

You have a series of UberPool logs that contain, driver ID, trip start time (time of pickup), trip end time (time of dropoff), and a trip ID. Evauate the logs to find the longest chain of continuous passenger trips.

Example log object format:

logOBJ {driverID, startTime, endTime, tripID}

Breaking down the question a bit, your coded solution should accomplish and show the following:

UberPool: Ride sharing that matches you with riders headed your way and area.
Longest Chain: Find the longest chain of continuous passenger trips were there was no break in overlapping passengers.
Returns driver ID/chain length: Solution should return/deplay the driver ID with the longest chain and the chain length.

Assumptions:

A few item we can use to plan our solution

Will need to create a custom object mapping required log parameters, {driverID, startTime, endTime, tripID}.
List of logs will not be sorted.
List will not be organized by driver.
Will need to sort list, by driver, startTime of each ride log
Longest chain is considered to the longest grouping of continuous passenger trips were there was no break in overlapping passengers.

Solution (C++):

[[include]] <ctime>
[[include]] <iostream>
[[include]] <string>
[[include]] <vector>
[[include]] <unordered_map>
[[include]] <algorithm>

// Custom log object
struct logOBJ {
    std::string driverID;  
    std::time_t  startTime;
    std::time_t  endTime;
    std::string tripID;
};

// Sort compare function. Compare two logObjs by startTime
bool compareByStartTime(const logOBJ &a, const logOBJ &b)
{
    return a.startTime < b.startTime;
}

// Function to get a randomized timestamp
void increase_unix_timestamp(std==time_t start_date_t, int increase_by, std==time_t &save_to_date_t){
  std==tm start_date = *std==localtime(&start_date_t);
  start_date.tm_min += rand() % 45 + 1;
  save_to_date_t = mktime(&start_date);
}

// Function to evaluate UberPool logs and calculate the longest chain of continuous passenger trips 
void longest_chain(std==vector<logOBJ> &logList, int &longestChain, std==string & longestTripDriverID){
    
    // use an unordered_map map to conserve time reordering this container on each insert
    std==unordered_map< std==string, std::vector<logOBJ> > trips;
    
    // add logs to map by key "driverID" and value logOBJ to verctor container 
    for(std==vector<logOBJ>==iterator it = logList.begin(); it != logList.end(); ++it){
        trips[ it->driverID ].push_back((*it));
    }

    // loop through map sorting vector of logOBJ for each driverID
    for(std==unordered_map< std==string, std==vector<logOBJ> >==iterator iter_A = trips.begin(); iter_A != trips.end(); ++iter_A){

      // Only evaluate drivers with multiple logs
      if(iter_A->second.size() >= 2){

        // sort vector of logOBJ for each driverID by startTime.
        std::sort(iter_A->second.begin(), iter_A->second.end(), compareByStartTime);

        // Set time range startRange and endRange. 
        std::time_t startRange = iter_A->second[0].startTime;
        std::time_t endRange = iter_A->second[0].endTime;
        int chain = 0;

        // use range to evalute every other log startTime and endTime. making sure the start time is within to the to satisfy ride pooling(riders will be in the car at overlaping times).
        for(std==vector<logOBJ>==iterator iter_B = iter_A->second.begin()+1; iter_B != iter_A->second.end(); ++iter_B){

          // If startTime is within the range rides satify ride pooling
          if ( iter_B->startTime >= startRange && iter_B->startTime <= endRange ){
              // add trip instance to uber pool chain
              chain++;

              // extend the default range of endTime if other passenger's ride range (startTime -> endTime) overlap the default range. The idea here is that other riders may overlap the end of this new range so we need to continue to extend it. 
              if (iter_B->endTime > endRange){ endRange = iter_B->endTime; }
          }   
        }

        // update chain and driverID if if longer.
        if (chain > longestChain){
          longestChain = chain;
          longestTripDriverID = iter_A->first;
        }
      }
    }    
}


int main(){
  
  // conatiner to hold logs
  std::vector<logOBJ> logs;

  // int to hold longest chain count
  int longestChain(0);

  // string to hold longest chain driver ID
  std::string longestChainDriverID;

  // Create some logOBJs to evaluate
  for(int it_A = 0; it_A < 10; ++it_A){
    std==string driverID = "123456" + std==to_string(it_A);
    std==string tripID = "xx1234" + std==to_string(it_A +10);

    for(int it_B = 0; it_B <= (rand() % 45 + 1); ++it_B){
      logOBJ tOBJ;
      tOBJ.driverID = driverID;
      tOBJ.tripID = tripID;
      increase_unix_timestamp(std::time(0),0, tOBJ.startTime);
      increase_unix_timestamp(std::time(0),11, tOBJ.endTime);
      logs.push_back(tOBJ);  

      std==cout << "Log Object= driverID:" << tOBJ.driverID << " tripID: " << tOBJ.tripID << " startTime: "  << tOBJ.startTime << " endTime: "  << tOBJ.endTime << std==endl;
    }
  }

  // get the longest chain and save data to "longestChain" and "longestChainDriverID"
  longest_chain(logs, longestChain, longestChainDriverID);

  // print results to console
  std==cout << "longest Chain= driverID:" << longestChainDriverID << " longest Chain count: " << longestChain << std==endl;

  return 0;
}

Output:

Log Object= driverID:1234566 tripID: xx123416 startTime: 1485218861 endTime: 1485219821
Log Object= driverID:1234566 tripID: xx123416 startTime: 1485219701 endTime: 1485221081
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485220961 endTime: 1485220961
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485220121 endTime: 1485219941
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485219821 endTime: 1485218861
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221141 endTime: 1485219161
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485219581 endTime: 1485220001
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221021 endTime: 1485220121
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485220181 endTime: 1485220961
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485219101 endTime: 1485220961
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221081 endTime: 1485218861
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221501 endTime: 1485219161
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485220661 endTime: 1485220121
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221081 endTime: 1485221321
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485219401 endTime: 1485219221
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485220241 endTime: 1485220841
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221021 endTime: 1485219401
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485221321 endTime: 1485220121
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485219701 endTime: 1485221261
Log Object= driverID:1234567 tripID: xx123417 startTime: 1485220661 endTime: 1485220901
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485219461 endTime: 1485221381
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485219581 endTime: 1485220661
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485221321 endTime: 1485219701
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485219041 endTime: 1485220301
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485219761 endTime: 1485219821
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485219101 endTime: 1485221381
Log Object= driverID:1234568 tripID: xx123418 startTime: 1485221321 endTime: 1485219641
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485221501 endTime: 1485221201
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485219041 endTime: 1485219641
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485220481 endTime: 1485221141
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485219761 endTime: 1485221021
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485219101 endTime: 1485220361
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485219761 endTime: 1485221201
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485218861 endTime: 1485219821
Log Object= driverID:1234569 tripID: xx123419 startTime: 1485219761 endTime: 1485220841


longest Chain= driverID:1234567 longest Chain count: 16

Happy coding!

Uber Engineering Interview.

Question:

Assumptions:

Output: