Tech Interview with Microsoft

I got an opportunity to be interviewed by Microsoft Engineering Center France for an internship position. I came across this opportunity from my campus internal bulletin board and my documents were submitted to this private channel. The position offered is a software engineer intern. So here’s some story about my experience getting interviewed by a tech giant.

First Step: Online Coding Test

Similar to other tech companies, everything began with an online coding test. The test used the Codility platform, however, the test was unlike the usual coding test I did: they don’t expect a program to be compiled. The compilation feature was completely turned off and you only use the platform as a text editor where you will eventually submit your code. The total duration of the coding test is 1 hour.

They allowed me to pick some programming languages I like: C#, C++, or Java. Definitely I went with C++. Below is the rough problem statement for the coding test:

The program stores a maze with a maximum size of 100×100. In the maze, there is a cheese where a mouse has to find. You are given an interface where you can move the mouse into four direction, and to check whether the current position has a cheese or not. Create a function that will direct the mouse to find the cheese.

class IMaze {
public:
    virtual bool FoundCheese() = 0;
    virtual bool TryMoveMouse(Direction d) = 0;
};

I remembered that I used to do similar stuff for my Foundation of Programming course 12 years ago. So, I dug down my document folder to look for the solution I made at that time, so I didn’t have to reinvent the wheel. Thankfully I keep every document I made since I entered the university. Although sadly, some artifact from my high school era is totally gone due to file format error 12 years ago.

My initial solution used a very simple right-hand maze traversal. This is the “simplest” idea of solving a maze where the character “put their right-hand to the wall”, and follow that wall towards the exit or goal. It is implemented simply by forcing the character to always turn right whenever it is available. This is definitely not the smartest idea as it has several limitations. The maze cannot have a loop and the width of a path in the maze can only be one-cell wide as those can raise issues with the algorithm to make the character infinitely circling around the loop.

void FindCheeseBasic(IMaze& maze) {
    // Since we don't have any information about the maze structure
    // we first try using "Right Hand Principle"

    // But we also try to remember which point that we have visited, so that
    // we are not trying to step on that point again
    Visited visitedMap;
    Direction currentDirection = Direction::Up;  

    while(!maze.FoundCheese()) {
        
        // Try to move right according tou our first direction
        switch(currentDirection) {
        case Direction::Left:
            if(maze.TryMoveMouse(Direction::Up)) {
                currentDirection = Direction::Up;
                visitedMap.MoveMouse(Direction::Up);
            }
            break;
        case Direction::Right:
            if(maze.TryMoveMouse(Direction::Down)) {
                currentDirection = Direction::Down;
                visitedMap.MoveMouse(Direction::Down);
            }
            break;
        case Direction::Up:
            if(maze.TryMoveMouse(Direction::Right)) {
                currentDirection = Direction::Right;
                visitedMap.MoveMouse(Direction::Right);
            }
            break;
        case Direction::Down:
            if(maze.TryMoveMouse(Direction::Left)) {
                currentDirection = Direction::Left;
                visitedMap.MoveMouse(Direction::Left);
            }
            break;
        }

        // Revalidate first this position since we make a one step
        // move
        if(maze.FoundCheese())
            break;

        // Then try to move forward
        if(maze.TryMoveMouse(currentDirection)) {
            // If it is success, restart the process
            visitedMap.MoveMouse(currentDirection);
            continue;

        } else {
            // If we cant move forward, probe our left or right
            switch(currentDirection) {
            case Direction::Up:
            case Direction::Down:
                if(maze.TryMoveMouse(Direction::Right) && !visitedMap.HaveVisited(Direction::Right)) {
                    currentDirection = Direction::Right;
                } else if(maze.TryMoveMouse(Direction::Left) && !visitedMap.HaveVisited(Direction::Left)) {
                    currentDirection = Direction::Left;
                } else {
                    // If it is a deadend, go back, regardless we have visit it or not
                    if( currentDirection == Direction::Up ) 
                        currentDirection = Direction::Down;
                    else 
                        currentDirection = Direction::Up;
                }
                break;

            case Direction::Left:
            case Direction::Right:
                if(maze.TryMoveMouse(Direction::Up) && !visitedMap.HaveVisited(Direction::Up)) {
                    currentDirection = Direction::Up;
                } else if(maze.TryMoveMouse(Direction::Down) && !visitedMap.HaveVisited(Direction::Down)) {
                    currentDirection = Direction::Down;
                } else {
                    // If it is a deadend, go back, regardless we have visit it or not
                    if(currentDirection == Direction::Left) 
                        currentDirection = Direction::Right;
                    else
                        currentDirection = Direction::Left;
                }
                break;
            }
        }
    }

    std::cout << "Success!" << std::endl;
}

When I coded the algorithm, I eventually realized that we can also track the movement of the mouse and use it to create a map of the maze by ourselves. The map then can be used in a decision-making process to not take the same option again when backtracking a dead-end path. The map is tracked in Visited class.

class Visited {
private:
    // Initialize in the middle of the map
    char currentPosX { 100 }, currentPosY { 100 };
    char theMaze[200 * 200] = { 0, };

    char Idx(char x, char y) {
        return y * 200 + x;        
    }

public:
    Visited() { 
        theMaze[Idx(100, 100)] = 1; // The first position is visited
    }
    bool HaveVisited(Direction d) {
        char lookIdx = 0;
        switch(d) {
        case Direction::Left:
            lookIdx = Idx(currentPosX - 1, currentPosY);
            break;
        case Direction::Right:
            lookIdx = Idx(currentPosX + 1, currentPosY);
            break;
        case Direction::Up:
            lookIdx = Idx(currentPosX, currentPosY + 1);
            break;
        case Direction::Down:
            lookIdx = Idx(currentPosX, currentPosY - 1);
            break;
        }
        
        return theMaze[lookIdx] == 1;
    }

    void MoveMouse(Direction d) {
        switch(d) {
        case Direction::Left:
            currentPosX -= 1;
            break;
        case Direction::Right:
            currentPosX += 1;
            break;
        case Direction::Up:
            currentPosY += 1;
            break;
        case Direction::Down:
            currentPosY -= 1;
            break;
        }
        
        theMaze[Idx(currentPosX, currentPosY)] = 1;
    }
};

Eventually, I realized that by using this Visited class, I can exploit the Visited map to building a graph-search based algorithm such as Depth-First Search (DFS) instead. It is because the visited information is necessary to perform the correct backtracking step in a DFS algorithm. I realized this one with only about 15 minutes remaining time to complete the test.

bool FindCheeseRecursive(IMaze& maze, Direction direction, Visited& v) {
    if(maze.FoundCheese())
        return true;

    // Move Forward    
    v.MoveMouse(direction);

    // Try to find all the way, if we have not visited it yet
    if(FindCheeseRecursive(maze, Direction::Up, v) && !v.HaveVisited(Direction::Up)) {
        return true;
    } else if(FindCheeseRecursive(maze, Direction::Down, v) && !v.HaveVisited(Direction::Down)) {
        return true;
    } else if(FindCheeseRecursive(maze, Direction::Left, v) && !v.HaveVisited(Direction::Left)) {
        return true;
    } else if(FindCheeseRecursive(maze, Direction::Right, v) && !v.HaveVisited(Direction::Right)) {
        return true;
    }
    switch(direction) {
    case Direction::Up:    direction = Direction::Down;  break;
    case Direction::Down:  direction = Direction::Up;    break;
    case Direction::Left:  direction = Direction::Right; break;
    case Direction::Right: direction = Direction::Left;  break;
    }
    // Move Backward and backtrack    
    v.MoveMouse(direction);
    return false;
}

void FindCheese(IMaze& maze) {
    Visited visited;
    if(FindCheeseRecursive(maze, Direction::Up, visited)) {
        std::cout << "Success!" << std::endl;
    }
}

Since I cannot compile the code, I didn’t have any idea if the code can work correctly or not. However, I just submitted it instead, assuming the idea should yield a proper working solution. I did the coding challenge in the evening, and the next morning I received a notification that I passed the coding test and advance to the online interview.

Second Step: Online Tech Interview

Microsoft scheduled the online interview the following week. The tech interview will be performed using online conferencing tools, which would take approximately 1 hour. I did my interview in the afternoon on my campus, to ensure I could focus on the interview rather than in my own place.

The interview began by discussing my prior experience. I explained about my prior experience at Accenture and Samsung, and how I could eventually have deep experience in C++. I also explained about my contribution in my previous work and its relation with me becoming a speaker in CppCon 2018.

Then the interview continued with discussing the code I wrote in the online coding test. The interviewer asked me to explain the code I wrote. My explanation was basically similar to the explanation I wrote in this post. We discussed the general idea of the code and making an experiment to demonstrate how the algorithm would work in real execution.

The final question during the online interview was about a simple algorithm and data structure knowledge. I don’t exactly remember the exact question, but I consider the question to be fairly easy if you have a good understanding of common algorithms and data structure. So, it is always a good idea to understand all the foundational knowledge about algorithms and data structure to nail this tech interview.

The next day after the interview, I received a notification that I passed the online interview, and they would invite me to go to Paris for an on-site interview.

Third Step: On-site Tech Interview

I was invited to come to Microsoft office in Issy-les-Moulineaux, Paris, to conduct an on-site tech interview. The interview happened one week after the online interview. It took about 4 hours for all interview to complete, and there are 4 different people who are interviewing me, which roughly took an hour for each interview. The interview started at 1PM and ended at around 5.30PM.

First Interview

The first challenge is about Mastermind game. At first, I didn’t know what the hell is mastermind game. The interviewer said that it is a kind of board game where you find a correct color sequence and for each turn, you will receive how many correct colors in the correct sequence and how many correct colors with incorrect placement. I remembered back then I played this game in Hoyle Board Games but I never know or pay attention to its name. Here’s the Wikipedia link for the game.

I am tasked to create a function that reports the result of checking for each turn. The function accepts two arguments which are the guess and the correct answer and expects to return two arguments which are the number correct color and place, and the number of correct colors only.

std::pair < int, int > checkGuess(std::string
    const & guess, std::string
    const & answer) {
    // Check how many colors are there in the correct answer
    std::map < char, int > colorMap;
    for (int i = 0; i < answer.length(); i++) {
        if (colorMap.find(answer[i]) == colorMap.end())
            colorMap.emplace(answer[i], 0);
        colorMap[answer[i]] += 1;
    }

    int correctPlacement = 0;
    // Loop the guess and answer
    for (int i = 0; i < answer.length(); i++) {
        if (answer[i] == guess[i]) {
            correctPlacement += 1;
            colorMap[answer[i]] -= 1;
            answer[i] = '-';
        }
    }

    int correctColor = 0;
    // Loop the guess
    for (int i = 0; i < guess.length(); i++) {
        if (guess[i] != '-') {
            if (colorMap[guess[i]] != 0) {
                colorMap[guess[i]] -= 1;
                correctColor += 1;
            }
        }
    }

    return {
        correctPlacement,
        correctColor
    }
}

The next challenge is to create a function to solve the game. It is quite challenging. The interviewer expected me to not doing brute force, but with some strategy. I don’t really remember my exact answer, but the idea is that the color placement is identified through making some combinations and counting the outcome of the combination (total correct placement and correct color). One strategy is that we can put all same color in one try, then compute how many units required for that color. In case we find a color that does not exist in the secret sequence, we can use that color as masking to identify the exact placement of a specific color in a specific position.

Throughout the interview, we also discussed about the complexity of the algorithm, and ways to improve the performance of the algorithm, including using a proper data structure, or pruning certain impossible cases.

Second Interview

I don’t really remember the exact coding test for this second interview. But in this interview, we discussed a lot about cloud architecture, such as cloud architecture and NoSQL technology. Basically, I do not really understand much about this field, but at least I know some distributed computing theories, as well as NoSQL technology from my course project at Aalto University.

The discussion was about how to achieve synchronization in a highly distributed and partitioned NoSQL database. The case was about two different NoSQL databases where one of the databases needs to be updated in case of changes in the other database. We brainstormed possible solutions to achieve consistency in a non-ACID conformant system like NoSQL. I was also challenged to think about implementing a rollback mechanism in this scheme, especially in case of an unfinished transaction.

Third Interview

The third interview was about solving a graph-based problem. The idea was to make a representation of friendship networks between people, like in a social networking system. A friend can have one or more friends. I needed to create the data structure design to represent this information. I used adjacency list representation to describe the friendship relation between people.

struct Person {
    std::string name;
    std::vector<Person const*> friends;
};

With this representation, I was asked to develop an algorithm to print the shortest relationship connection between people. For example, Alice is friends with Charlie, Charlie is friends with Dylan, and Dylan is friends with Bob. Therefore, the connection between Alice and Bob is Alice → Charlie → Dylan → Bob. I designed the algorithm using Breadth-First Search algorithm (BFS) to find the target person, then print the traversal using backtracking.

I picked BFS because the requirement is to print the shortest connection. BFS algorithm ensures that the shortest connection will appear first. This is to avoid local-maximum problem if we use Depth-First Search. However, BFS algorithm is implemented using loop and queue, which by default does not support backtracking. To support printing the connection between root node (Alice) and target node (Bob), we need to also track the connectivity during each visit of the node, so that we can backtrack the relationship and print it.

struct VisitEntry {
    VisitEntry* from;
    Person const* to;
};

void PrintConnection(Person const& a, Person const& b) {
    std::queue<VisitEntry> theQueue;
    std::list<VisitEntry> visited;
    std::set<Person const*> visitedSet;

    // Visit the first person
    auto& root = visited.emplace_back(VisitEntry {nullptr, &a});
    visitedSet.emplace(&a);
    
    // Insert all a's friends to the queue
    std::for_each(a.friends.begin(), a.friends.end(), 
                  [&] (Person const* p) { 
                      theQueue.emplace(VisitEntry { &root, p }); 
                  });
    
    while(!theQueue.empty()) {
        auto front = theQueue.front();
        theQueue.pop();

        if(visitedSet.find(front.to) != visitedSet.end())
            continue; // Already visited
        else
            visitedSet.emplace(front.to);

        auto& visit = visited.emplace_back(front);

        // If the visited is the target, it is found
        if(visit.to == &b) {
            // Backtrack and print
            VisitEntry* backtrack = &visit;
            do {
                std::cout << backtrack->to->name;
                backtrack = backtrack->from;
                if(backtrack != nullptr)
                  std::cout << " -> ";
            } while(backtrack != nullptr);
            std::cout << std::endl;
            return;
        } else {
            // Emplace the next friend list
            std::for_each(visit.to->friends.begin(), visit.to->friends.end(),
                          [&] (Person const* p) { 
                            theQueue.emplace(VisitEntry { &visit, p }); 
                          });
        }
    }

    std::cout << "No connection!" << std::endl;
}

During the interview, the interviewer also asked about several C++ techniques. Here are some of questions and answers that I can still remember:

1. “Why using references over pointer?” references are safer than pointer especially if we don’t intend to modify the reference, or if we don’t need to represent null value. It is also a better choice if we want to pass an argument by reference to a function.
2. “But using references in Standard Template Library (STL) is not supported, right?” Yes, but STL provides a template called reference_wrapper which can be used as elements in STL templates such as vector or list.
3. “Why using const? Is it just to impress the interviewer?” (This is exactly what he asked :P) Well, it is generally a very good practice to do const-correct in our programming. By doing this, we also require to mark member functions as const if the function does not make any modification to its members (except mutable members).

Fourth Interview

The final interview was with the department head in Microsoft Engineering. The task was implementing an algorithm to perform the intersection of two arrays in a single pass loop, given that the array is already sorted. Here’s the example of the solution. I forgot whether I made the solution using a simple pointer-based array or iterator, but basically the idea is the same.

The second task was implementing an algorithm to generate a permutation of a number using a loop. Usually, we implement a permutation generator using a recursion algorithm as it is relatively simple using backtracking. However, I was not allowed to write using recursion, but I need to use a loop. The main construct was using multiple layers of loops. I cannot remember the exact detail of this task, but the challenge is more than just generating the permutation using loops, but also some other details and advanced techniques.

After completing the coding task, we were discussing about practical architecture for a web service. The case study was a music-recognition service such as Shazam. I was challenged in giving the concept of how to implement Shazam-like service. I answered with fingerprinting the waveform in the music and identifying certain markers or patterns that can be matched with different music pieces. The interview asked more on the question of why Shazam can be fast, and how if we are going to implement similar features with PC based media players such as Windows 10 Groove. I was also asked about cloud terminologies such as reliability, availability, etc (which I failed to answer though).

Result

The result came the day after the interview. I was on the TGV back to Antibes when I received the e-mail. I passed the interview process and they offered the internship position for 6 months which can be progressed towards full-time employment after I graduate from my master’s study.

My Decision

I decided not to take it. After a very long and tough consideration, I decided to go work with my professor here at EURECOM to complete my master’s study by performing a research-based internship. On the other hand, I also received an offer from my previous internship position at Huawei Finland to continue my work there, but I decided to stay in France as I planned to take extra courses as well as helping the professors to host SECCLO Summer School. But unfortunately, all of the additional plans have changed due to COVID-19 🙁

But no regret! I am enjoying my experiment with my professor here. The topic is interesting and I am learning quite a lot by performing this independent research. Later I will share my new knowledge here.