Microsoft OA Question

Posted
6 Apr 2025
316 reads

Summary

This post details a specific online assessment question I encountered during a Microsoft interview process, which involved reconstructing a string from a grid with the minimum number of moves.

How it went

Microsoft online Assessment Question :

You are given a string S and a two-dimensional array of characters of size N×N named grid. Each field in the grid is either empty (denoted by a dot".") or contains an uppercase English letter. Each particular letter may appear at most twice in the grid.

Your task is to reconstruct string S by visiting fields of the grid. You start the reconstruction with an empty string. You can choose the field in which you want to start. In one move you can change the current field to an adjacent one (up, down, left, right). If you visit a field containing a letter, you may append this letter to the end of the reconstructed string. Appending a letter is not counted as a move. Each field can be visited and each letter can be used multiple times during the reconstruction process.

What is the minimum number of moves needed to reconstruct string s?

Write a function that, given a string S and an array grid, returns the minimum number of moves needed to reconstruct S. If it is not possible to reconstruct S, return -1.

Examples:

1.⁠ ⁠Given S = "ABCA" and grid = [".A.C", ".B..",".. "...A"], the function should return 6.

The optimal movement during the reconstruction process is as follows:

start on the field containing "A" in the first row;

go to the adjacent field with "B" in one move;

go to the field containing "C" in three moves;

return to the starting field with "A" in two moves.

This way, the string "ABCA" Is reconstructed in six moves.

  1. Given S = "KLLRML" and grid = ["K", "S...L","R", "LX...", "XM..S"], the function should return 13.

The optimal movement during the reconstruction process is as follows:

start on the field containing "K";

go to the field with "L" on the right side of the grid in five moves - note that while being on this field, two consecutive letters "L" can be appended to your string:

gather letters "R" and then "M" in six moves;

go to the closest field containing letter "L" in two moves.

  1. Given S = "XZZY" and grid = [".Z.", "XBB", "..A"], the function should return -1. It is impossible to reconstruct S because letter "Y" does not appear on the grid.

I have attached google drive link for the images of the question.

Questions asked (1)

  1. 01

    Minimum Moves to Reconstruct String from Grid

    Data Structures & Algorithms

    You are given a string S and a two-dimensional array of characters of size N×N named grid. Each field in the grid is either empty (denoted by a dot".") or contains an uppercase English letter. Each particular letter may appear at most twice in the grid.

    Your task is to reconstruct string S by visiting fields of the grid. You start the reconstruction with an empty string. You can choose the field in which you want to start. In one move you can change the current field to an adjacent one (up, down, left, right). If you visit a field containing a letter, you may append this letter to the end of the reconstructed string. Appending a letter is not counted as a move. Each field can be visited and each letter can be used multiple times during the reconstruction process.

    What is the minimum number of moves needed to reconstruct string s?

    Write a function that, given a string S and an array grid, returns the minimum number of moves needed to reconstruct S. If it is not possible to reconstruct S, return -1.

    Examples:

    1.⁠ ⁠Given S = "ABCA" and grid = [".A.C", ".B..",".. "...A"], the function should return 6.

    The optimal movement during the reconstruction process is as follows:

    start on the field containing "A" in the first row;

    go to the adjacent field with "B" in one move;

    go to the field containing "C" in three moves;

    return to the starting field with "A" in two moves.

    This way, the string "ABCA" Is reconstructed in six moves.

    1. Given S = "KLLRML" and grid = ["K", "S...L","R", "LX...", "XM..S"], the function should return 13.

    The optimal movement during the reconstruction process is as follows:

    start on the field containing "K";

    go to the field with "L" on the right side of the grid in five moves - note that while being on this field, two consecutive letters "L" can be appended to your string:

    gather letters "R" and then "M" in six moves;

    go to the closest field containing letter "L" in two moves.

    1. Given S = "XZZY" and grid = [".Z.", "XBB", "..A"], the function should return -1. It is impossible to reconstruct S because letter "Y" does not appear on the grid.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Microsoft recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!