SDE 2 at Microsoft

How it went

What they would tell you

How to prepare

Round by round

1. 1

   Technical Round60 min

   Question Asked: Given a maze represented as a grid of characters, where 0 → open cell, X → blocked cell, M → mine, find the shortest distance of every open cell from its nearest mine.

   • Movement is allowed only in 4 directions (up, down, left, right).

   • Distance of a mine to itself is 0.

   • Blocked and unreachable cells should return -1. Approach: I used a multi-source BFS starting from all the mines simultaneously. The idea was to propagate the shortest distance level by level from each mine, updating each open cell's distance as soon as it is visited for the first time.

   • Step 1: Push all mine positions into a queue and initialise their distances as 0.

   • Step 2: Use standard BFS traversal in 4 directions, marking visited '0' cells with their distance.

   • Step 3: Blocked cells and unvisited open cells remain -1. This ensures optimal distance calculation in O(n × m) time complexity, where n is the number of rows and m is the number of columns. Code Snippet This code snippet is the same that I wrote for my interview. #include <bits/stdc++.h> using namespace std;

   /* Discussed a few test cases in the comments before started to code

   Make sure you think of a few(if not all)
   edge cases before jumping into the solution
   edge case -> 1. There is a possibility that no blocker is there
   
   Be very clear with variables that you need upfront
   n = rows
   m = cols
   */
   

   void findShortestDistance(vector<vector<char>> & adj){ int n = adj.size() ; // number of rows int m = adj[0].size(); //number of columns

   vector<vector<int>> dis(n, vector<int> (m, -1));
   queue<pair<int, int>> q;
   
   for( int i =0;i <n ;i++){
       for( int j =0;j <m ;j++){
           if(adj[i][j] == 'M'){
               q.push({i, j});
               dis[i][j] =0;
           }
       }
   }
   
   //For 4 directional movement
   int di[] = {0, 0 , 1, -1};
   int dj[] = {1, -1, 0, 0};
   
   while(!q.empty()){
       int row = q.front().first;
       int col = q.front().second;
   
       q.pop();
   
       for(int i = 0 ;i < 4; i++){
           int newi = row + di[i];
           int newj = col + dj[i];
   
           if(newi >=0 and newj >=0 and newi <n and newj <m and
           dis[newi][newj] == -1 and adj[newi][newj] == 'O')
           {
               dis[newi][newj] = dis[row][col] + 1;
               q.push({newi, newj});
           }
       }
   }
   
   //Print matrix (Interviewer asked me to print the matrix at the end)
   for( int i = 0;i < n; i++){
       for( int j =0; j<m; j++){
           cout<<dis[i][j];
       }
       cout<<endl;
   }
   

   }

   int main() { vector<vector<char>> adj = {{'X', 'X'}};

   int n = adj.size() ; // number of rows
   if (n == 0 ) {
       cout <<"Empty";
       return 0;
   }
   
   findShortestDistance(adj);
   return 0;
   

   }

   Edge Cases Considered

   • Empty grid
   • Grid with no mines or all blocked
2. 2

   DSA + Low-Level System Design60 min

   Question Asked: I was given a practical design-based DSA problem. The context was a startup called BookNest, facing performance issues due to frequent database hits for book previews. Design and implement a cache system that:

   • Stores a fixed number of book records.

   • Supports get(bookID) and put(bookId, bookData) operations.

   • If the cache is full, it should evict the least recently used (LRU) book.

   • Both operations should run in O(1) time. My Approach: I proposed an LRU Cache using a combination of:

   • Doubly Linked List to track usage order.

   • HashMap for fast lookups. This allowed me to maintain the LRU order and perform all operations efficiently. I wrapped the logic inside a bookService and BookServiceImpl setup to follow proper abstraction.

   Code Snippet: #include <bits/stdc++.h> using namespace std;

   // Class to represent a Book object class Book { public: int bookId; string author;

   // Constructor to initialize a Book with ID and author name
   Book(int id, const string &information) {
       bookId = id;
       author = information;
   }
   

   };

   // LRU Cache class class LRUCache { public: // Constructor to initialize cache with a given capacity LRUCache(int cap) { capacity = cap; }

   // Fetches a book from the cache
   Book* get(int bookId) {
       // If the book is not in cache, return nullptr
       if (cacheMap.find(bookId) == cacheMap.end()) {
           return nullptr;
       }
   
       // Move the accessed item to the front (most recently used)
       accessList.splice(accessList.begin(), accessList, cacheMap[bookId]);
   
       // Return a pointer to the book
       return &(cacheMap[bookId]->second);
   }
   
   // Inserts a book into the cache
   void put(int bookId, const string &bookData) {
       // If the book is already in cache, update it and move it to front
       if (cacheMap.find(bookId) != cacheMap.end()) {
           cacheMap[bookId]->second = Book(bookId, bookData);
           accessList.splice(accessList.begin(), accessList, cacheMap[bookId]);
           return;
       }
   
       // If cache is full, remove the least recently used book
       if (accessList.size() == capacity) {
           auto last = accessList.back(); // last = least recently used
           cacheMap.erase(last.first);    // remove from map
           accessList.pop_back();         // remove from list
       }
   
       // Insert the new book at the front of the list
       accessList.push_front({bookId, Book(bookId, bookData)});
       cacheMap[bookId] = accessList.begin(); // update map with iterator to list node
   }
   

   private: int capacity; // Maximum capacity of the cache

   // Doubly linked list to track LRU order: most recently used at front
   list<pair<int, Book>> accessList;
   
   // Hash map to quickly access list nodes by bookId
   unordered_map<int, list<pair<int, Book>>::iterator> cacheMap;
   

   };

   int main() { // Create an LRUCache with capacity 2 LRUCache cache(2);

   // Add books with ID 1 and 2
   cache.put(1, "xyz");
   cache.put(2, "test");
   
   // Try to retrieve book with ID 1 (should be in cache)
   Book* book = cache.get(1);
   if (book != nullptr) {
       cout << book->author << endl; // Output: xyz
   } else {
       cout << "-1" << endl;
   }
   
   // Add book with ID 3, this should evict book with ID 2 (least recently used)
   cache.put(3, "new author");
   
   // Try to retrieve book with ID 2 (should be evicted)
   Book* book2 = cache.get(2);
   if (book2 != nullptr) {
       cout << book2->author << endl;
   } else {
       cout << "-1" << endl; // Output: -1
   }
   
   return 0;
   

   }

3. 3

   System Design60 min

   In this round, I was asked to **design a Rate Limiter, **a classic system design problem, often used to prevent abuse of APIs or services by limiting the number of requests from a user/client within a certain time frame.

   Problem: Design a system that:

   • Limits the number of API requests a user/client can make within a fixed time window (e.g., 100 requests per minute).

   • Ensures efficient performance even under high load.

   • Supports multiple users and scales well. My Approach: I started by discussing different types of rate limiting techniques:

   • Fixed Window Counter

   • Sliding Window Log

   • Sliding Window Counter

   • Token Bucket Algorithm Then, I proposed the Token Bucket approach for its flexibility and smoother rate limiting under burst traffic. I discussed:

   • Data structures required (e.g., hashmap for user tokens).

   • Handling concurrency and TTL using threads or queues.

   • How this could be extended in a distributed system using Redis. The focus was on trade-offs, scalability, and writing a basic implementation outline.

4. 4

   Sytem Design60 min

   This round focused on designing a bus reservation service for Microsoft employees. The buses operate on 25 fixed routes, with a defined list of stops per route. Morning buses only pick up from home stops and drop at the MS campus, while evening buses only allow boarding from campus and drop at respective home stops. Problem Requirements:

   • Design the database schema to manage passengers, drivers, bookings, and routes.
   • Design basic APIs to support a frontend for employee use.

   My Approach Database Design (Key Entities):

   • Passenger: passenger_id, name, start_stop, end_stop, date_of_travel

   • Driver: driver_id, name, assigned_bus_id

   • Bus: bus_id, route_id, capacity, assigned_driver_id

   • Route: route_id, list_of_stops

   • Stop: stop_id, location_name, geo_coordinates

   • Booking: booking_id, passenger_id, bus_id, status (active/cancelled), trip_type (morning/evening) API's:

   • POST /register – Passenger signup

   • POST /login – Login API

   • GET /routes/{route_id}/stops – View stops on a particular route

   • POST /booking – Create a booking (takes passenger_id, route_id, stop_id, trip_type)

   • GET /booking/active – View current active bookings

   • GET /stops/nearby?lat=..&lng=.. – Get nearby stops using geolocation Discussion Areas: We also discussed:

   • Ensuring morning/evening rules via validations.

   • How the booking system could handle seat availability.

   • Designing with extensibility in mind (e.g., support for future evening pickups).

5. 5

   Hiring Manager Round60 min

   This round lasted for about 45–50 minutes and was conducted by the Hiring Manager. Unlike the previous rounds, this one didn’t focus on solving coding or design problems. Instead, it was a deep dive into my resume, projects, and professional journey, essentially trying to assess who I am beyond just a set of skills.

   What Happened in the Round:

   • The manager began by going through my resume line by line, starting right from my first job.

   • Every point I had mentioned, whether it was a small project, an impact statement, or a role description, was questioned with follow-up "why", "how", and "what happened then".

   • I was frequently put into hypothetical and mixed real-life scenarios, like:

   • “What would you do if a key project is failing and you’re brought in late?”

   • “How would you respond if your design was challenged by a senior architect?”

   • “You joined a new team and the domain is alien to you. What’s your next 30 days strategy?” These weren’t just random stress questions, they were trying to understand:

   • How I think under pressure

   • My approach to problem-solving in ambiguity

   • Adaptability to new teams/domains

   • Communication and articulation skills

   • And most importantly, whether I take ownership of my work

What came up