Microsoft OA | India | 6 YOE

Round 1

Questions:

1. Given a grid of size N x N. The grid can contain capital letters and ".". We are also given a string as input that contains only capital letters. Each letter appears at most twice in the grid. We have to form the string with minimum moves by going through the grid. We can start at any cell. We can visit the same cell multiple times and we can choose whether we want to append the letter or ignore it to form the resultant string. On a cell, we could also re-use the letter multiple times. If we cannot form the string, return -1.

   • Example:
     • Grid: [['A','B'],['C','.']]
     • Word: "ABC"
       • Start at 'A': 1 move
       • Move right to 'B': 1 move
       • Move down to '.': 1 move
       • Move left to 'C': 1 move
       • Ans is 4 moves
     • Grid: [['A','B'],['C','.']]
     • Word: "ABCC"
       • Start at 'A': 1 move
       • Move right to 'B': 1 move
       • Move down to '.': 1 move
       • Move left to 'C': 1 move (You can add two Cs here without making extra moves)
       • Ans is 4 moves

2. Same question as String Compression II except couple of changes. Instead of making at most k deletions, we have to make exactly k deletions of consecutive characters and the constraints were quite big. String length and k can be between 1 to 10^6.