Microsoft Online Assessment Questions : December 2024

Round 1

Questions:

Question 1:

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? 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.

2. Given S = "KLLRML" and grid = ["k....", "s...L", "....R", "LX...", "x. 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 "-" in two moves.

3. 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.

Question 2:

Strings with long blocks of repeating characters take much less space if kept in a compressed representation. To obtain the compressed representation, we replace each segment of equal characters in the string with the number of characters in the segment followed by the character (for example, we replace segment "CCCC" with "4C"). To avoid increasing the size, we leave the one-letter segments unchanged (the compressed representation of "BC" is the same string - "BC"). For example, the compressed representation of the string "ABBBCDDCCC" is "A3B2C2D3C", and the compressed representation of the string "AAAAAAAAAAABXXAAAAAAAAAA" is "11AB2X10A". Observe that, in the second example, if we removed the "BXX" segment from the middle of the word, we would obtain a much shorter compressed representation - "21A". In order to take advantage of this observation, we decided to modify our compression algorithm. Now, before compression, we remove exactly K consecutive letters from the input string. We would like to know the shortest compressed form that we can generate this way. Given a string S of length N and an integer K, returns the shortest possible length of the compressed representation of S after removing exactly K consecutive characters from S.

Examples:

1. ABBBCCDDCCC, k = 3 -> Ans: 5 (Remove DDC -> A3B4C)
2. ABCDDDCEFG, k = 2 -> Ans: 6 (Remove EF -> ABC3DG)