Company questionsGroundworkMeesho

Machine coding · Matching engines

Car pooling system

  • Reported once
  • SDE-1 (open campus)
  • Strategy
  • Facade
  • 1 source

One candidate write-up. Treat it as a single data point.

The prompt
Design and build a working car pooling system within about an hour. The interviewer reportedly looked at the overall approach, the design of classes and modules, and whether the code was clean and executable.

Restated in our own words, not a quote from Meesho or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

The source lists no requirements, so state them. That drivers offer rides and riders search for and book seats is this answer's reading of the name. Questions to ask: is a ride a single hop from an origin to a destination, or does it have stops? Is the price per seat fixed by the driver? Can a rider book several seats at once? Who can cancel, and what happens to existing bookings? Does a rider search for an exact departure time or for anything after a time? How should results be ranked? Is everything in memory in one process?

Assumed scope: a ride is direct, with a named origin, a named destination, a departure time as a number of minutes, a seat count and a price per seat. A rider searches by exact origin and destination, the earliest acceptable departure and a number of seats. Booking is immediate with no driver approval. A rider can cancel a booking, and only the driver can cancel a ride. Results are ordered by a replaceable ranking rule. Out of scope: intermediate stops, map distances, payments and ratings.

Entities and relationships

Who owns what, and who talks to whom.

  • CarPool is the service. It owns the rides, a lookup from booking id to ride, the ranking strategy and an injected clock, and exposes offer, search, book, match, cancelBooking(rider, bookingId) and cancelRide(driver, rideId).
  • Ride holds the id, driver, origin, destination, departure, seat count, price, its bookings and a cancelled flag. Free seats are computed from the bookings.
  • Booking is a plain record of an id, a rider and a number of seats, owned by its ride.
  • Ranking strategy is an interface with compare(a, b), implemented by EarliestFirst and CheapestFirst.
  • Clock is a function passed to the service that returns the current time.

Relationships: the service has many rides, a ride has many bookings, and the service uses one ranking strategy and one clock.

The design

The class map, the main flow and the patterns that earn their place.

Class map of the car pooling systemOne service owns rides, a ride owns its bookings, and ranking and time are supplied from outside.
Driver or riderCarPooloffer, search, bookRideroute, seats, bookingsBookingrider and seatsRankingStrategycompare(a, b)EarliestFirstCheapestFirstClockinjected functionoffer, searchhas manyhas manysorts withreads timeimplementsimplements1234
  1. Drivers offer rides and riders search and book through the service.
  2. The service holds every ride by id.
  3. Each ride holds its own bookings, and free seats come from them.
  4. Search results are ordered by the current ranking strategy.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

The shape is one service over two entities, kept honest by a few rules. A Ride owns its bookings, and free seats are always computed as seats minus the sum of booked seats instead of being kept in a counter. A counter can drift when a booking or a whole ride is cancelled, while a computed value cannot. Ranking is the Strategy pattern: compare(a, b) with the id as the last tie-breaker, so the order is always deterministic, and adding a rule is a new class. The clock is injected as a function so that rules about departed rides can be tested without real time.

  1. offer validates a whole number of seats of at least one, a price that is not negative, different origin and destination, and a departure after the current time, then stores the ride under a sequential id.
  2. search keeps rides that are bookable for this rider (not cancelled, not departed, not driven by the rider, not already booked by the rider), on the requested route, departing no earlier than asked and with enough free seats. A search that leaves out the earliest time means "from now", and asking for fewer than one seat is an error. It sorts them with the ranking strategy and returns the ids.
  3. book checks the booking rules again at the moment of booking (not cancelled, not departed, not the driver, not already booked), because a search result can be stale, then checks the seat count is a whole number of at least one and that enough seats are free, writes the booking and records which ride holds it.
  4. match is search followed by booking the first result, or null when nothing fits. It is the automatic matching path.
  5. cancelBooking takes the rider and the booking id, finds the ride through the lookup, refuses a booking that belongs to someone else, and removes it, so its seats are free again by recalculation.
  6. cancelRide is allowed only for the ride's driver. It marks the ride cancelled, clears its bookings and returns the affected riders so a caller can notify them.

Booking is a check-then-act on free seats. In this single threaded version that is atomic. With real concurrency it needs a lock per ride, not one global lock, or a conditional database update such as "set booked = booked + n where seats - booked >= n". Search may be stale, and booking is the one place that decides. Search scans every ride and sums its bookings, which is O(R) with a small factor for the bookings per ride, plus the sort of the results. Keeping a map from origin and destination to rides would cut that to the rides on the route. Treating a ride as direct keeps seat counting trivial. With stops, occupancy has to be tracked per segment.

The code

Runnable JavaScript, with the checks it passes.

meesho-car-pooling.js
class Ride {
  constructor(id, driver, from, to, departure, seats, price) {
    this.id = id;
    this.driver = driver;
    this.from = from;
    this.to = to;
    this.departure = departure;
    this.seats = seats;
    this.price = price;
    this.bookings = new Map();
    this.cancelled = false;
  }
  taken() {
    let total = 0;
    for (const booking of this.bookings.values()) total += booking.seats;
    return total;
  }
  free() {
    return this.seats - this.taken();
  }
}

class EarliestFirst {
  compare(a, b) {
    return a.departure - b.departure || a.id - b.id;
  }
}

class CheapestFirst {
  compare(a, b) {
    return a.price - b.price || a.departure - b.departure || a.id - b.id;
  }
}

class CarPool {
  constructor(clock, ranking) {
    this.clock = clock;
    this.ranking = ranking;
    this.rides = new Map();
    this.bookingRide = new Map();
    this.nextRide = 1;
    this.nextBooking = 1;
  }
  offer(driver, from, to, departure, seats, price) {
    if (!Number.isInteger(seats) || seats < 1) throw new Error("a ride needs at least one seat");
    if (!(price >= 0)) throw new Error("price must not be negative");
    if (from === to) throw new Error("origin and destination must differ");
    if (departure <= this.clock()) throw new Error("departure is in the past");
    const ride = new Ride(this.nextRide++, driver, from, to, departure, seats, price);
    this.rides.set(ride.id, ride);
    return ride.id;
  }
  bookable(ride, request) {
    const mine = [...ride.bookings.values()].some((booking) => booking.rider === request.rider);
    return !ride.cancelled && ride.driver !== request.rider && !mine && ride.departure > this.clock();
  }
  search(request) {
    if (!Number.isInteger(request.seats) || request.seats < 1) throw new Error("book at least one seat");
    const earliest = request.notBefore === undefined ? this.clock() : request.notBefore;
    return [...this.rides.values()]
      .filter((ride) => this.bookable(ride, request))
      .filter((ride) => ride.from === request.from && ride.to === request.to)
      .filter((ride) => ride.departure >= earliest && ride.free() >= request.seats)
      .sort((a, b) => this.ranking.compare(a, b))
      .map((ride) => ride.id);
  }
  book(rider, rideId, seats) {
    if (!Number.isInteger(seats) || seats < 1) throw new Error("book at least one seat");
    const ride = this.rides.get(rideId);
    if (!ride || ride.cancelled) throw new Error("no such ride");
    if (ride.driver === rider) throw new Error("a driver cannot book their own ride");
    if (ride.departure <= this.clock()) throw new Error("ride has departed");
    if (!this.bookable(ride, { rider })) throw new Error("rider already booked this ride");
    if (ride.free() < seats) throw new Error("not enough seats");
    const booking = { id: this.nextBooking++, rider, seats };
    ride.bookings.set(booking.id, booking);
    this.bookingRide.set(booking.id, ride);
    return booking.id;
  }
  match(request) {
    const found = this.search(request);
    return found.length > 0 ? this.book(request.rider, found[0], request.seats) : null;
  }
  cancelBooking(rider, bookingId) {
    const ride = this.bookingRide.get(bookingId);
    if (!ride) return false;
    if (ride.bookings.get(bookingId).rider !== rider) throw new Error("not your booking");
    ride.bookings.delete(bookingId);
    this.bookingRide.delete(bookingId);
    return true;
  }
  cancelRide(driver, rideId) {
    const ride = this.rides.get(rideId);
    if (!ride || ride.driver !== driver) throw new Error("only the driver can cancel a ride");
    ride.cancelled = true;
    const riders = [...ride.bookings.values()].map((booking) => booking.rider);
    for (const id of ride.bookings.keys()) this.bookingRide.delete(id);
    ride.bookings.clear();
    return riders;
  }
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

  1. How would you support intermediate stops, so that a rider boards at the second stop and leaves at the fourth, and how do you check seat capacity along the way?
  2. How would you add a driver approval step, and which states does a booking go through?
  3. How would you match by distance from the rider's pickup point instead of exact place names, and what index would you use?
  4. How would you stop two riders from taking the last seat at the same moment when bookings arrive at several servers?
  5. How would you add a ranking rule that combines price and departure time, and would any class other than a new strategy change?

Where candidates slip

The mistakes this problem punishes.

  • Accepting zero or negative seats, so a negative booking quietly adds seats to the ride.
  • Letting anyone cancel any booking because the id is the only thing checked.
  • Keeping a seats-left counter and forgetting to adjust it when a booking or a whole ride is cancelled.
  • Trusting a search result when booking, with no second check of seats, departure time and cancellation.
  • Letting a driver book their own ride, or letting a rider book the same ride twice and so count the seats twice.
  • Calling the real clock inside the class, which makes the rules about departed rides impossible to test.
  • Putting ranking as if-else inside search, or one class doing search, booking, pricing and cancellation. The reported feedback was about class and module design.
  • Cancelling a ride but leaving its bookings behind, or not telling the riders who lost their seats.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Now make it stick

Sketch the class map on the whiteboardRun a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Read these chapters first