## Microsoft Interview Question for Software Development Managers

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

This one is pretty straightforward: Do one pass of the matrix O(n) finding all instances of the starting letter ("M" in the example). From each M you find, path outwards (N,S,E,W, optionally NW,NE,SW,SE) terminating the path as soon as you encounter a letter not in the sequence, and continuing the search when you find the next expected letter (e.g. "I"). Repeat recursively. You can do this exhaustively to find all instances of the word, or exit when you find the first complete path, depending on what is asked for.

I'd also ask the interviewer if letters can be used more than once (i.e. path can have loops) or if the visited letter nodes must be marked and not revisited.

Comment hidden because of low score. Click to expand.
1
of 1 vote

"Do one pass of the matrix O(n)". Shouldn't it be O(n^2)? Assuming the matrix is of size nxn.

Comment hidden because of low score. Click to expand.
0

I was assuming the matrix would be a 2D array in memory, with random access to all elements. Conventionally, the 'n' in what's given for big-O notation for searching data structures is the number of elements in the structure (i.e size of the data set). For the example, n=25. You could call it O(N*M) if you make it clear that you're talking about an N-by-M matrix, but you wouldn't call this O(n^2) because people would misinterpret you. An example of an O(n^2) operation on this puzzle would to be compare every letter to every other.

Comment hidden because of low score. Click to expand.
0

What's the time complexity of your algorithm?

Comment hidden because of low score. Click to expand.
0

@anonymous in the worst case, the matrix is full of the same letter, and the string you're searching for is of length n*n and all the same letter as what's in the matrix. In this case, you're starting at all locations in the matrix (n*n) and approximately traversing all locations in the matrix (n*n), so this would end up with O(n^4) if you wanted to find all possible occurrences of the string.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#include<stdio.h>
#include<stdbool.h>
#include<string.h>

#define M 5
#define N 5

bool findpath(int m[M][N], char *str, int i, int j, int path[M][N])
{
bool ret;

if(!str || !(*str))
return true;

if(i < 0 || j < 0 || i > M || j > N)
return false;

if(path[i][j] == 1)
return false;

if(*str != m[i][j])
return false;
path[i][j] = 1;

ret = findpath(m, str+1, i+1, j, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i, j+1, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i-1, j, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i, j-1, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i+1, j+1, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i+1, j-1, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i-1, j+1, path);
if(ret == true)
return ret;

ret = findpath(m, str+1, i-1, j-1, path);
if(ret == true)
return ret;

path[i][j] = 0;
return false;
}

int main()
{
bool ret;
int i, j;
char str[] = "microsoft";
int m[M][N] ={{'a','c','p','r','c'},{'x','s','o','p','c'},{'v','o','v','n','i'},{'w','g','f','m','n'},{'q','a','t','i','t'}};
int path[M][N] = {};

for(i = 0; i < M; i++) {
for(j = 0; j < N; j++) {
if(m[i][j] == str[0]) {
ret = findpath(m, str, i, j, path);
if(ret) {
printf("found\n");
}
else
printf("Not");
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I usually discourage pasting code but once I coded it up, it'd be no harm sharing it than not..
Feel free to comment.

``````import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Map;
import java.util.Scanner;

/**
* Created by Nikunj Parekh on 11/1/2014.
*/

public class FindStringInMatrix {

private char[][] mtx;

FindStringInMatrix() {
mtx = null;
}

public static void main(String[] args) {

FindStringInMatrix job = new FindStringInMatrix();
job.populateMtx();

job.findWord();
}

private void findWord() {
System.out.println("Enter word to be found: ");
Scanner s = new Scanner(System.in);

char[] word = s.nextLine().toCharArray();
int p=0;
for (int i=0; i < mtx.length; i++) {
for (int j=0; j < mtx[i].length; j++) {
if (word[p] == mtx[i][j]) {
System.out.println("* "+word[p] + ", (" + i + ", " + j + ")");
p++;
if(p==word.length)
return;
for(int r=Math.max(j-1,0); r<Math.min(j+1,mtx.length); r++) {
for(int c=Math.max(i-1,0); c<Math.min(i+1,mtx[r].length); c++) {
if (word[p] == mtx[c][r]) {
System.out.println(word[p] + ", (" + c + ", " + r + ")");
p++;
if(p==word.length)
return;
} else {
i = c;
j = r;
}
if(c==mtx[r].length)
break;
}
if(r==mtx.length)
break;
}
}
}
}
}

private void populateMtx() {
int row = 0, col;
Scanner s = null;
try {
s = new Scanner(new InputStreamReader(new FileInputStream("C:\\tmp\\matrix.txt")));
} catch (FileNotFoundException e) {
System.err.println(e.getMessage());
e.printStackTrace();
}

this.mtx = new char[100][100];
while (s.hasNextLine()) {
String line = s.nextLine();
this.mtx[row] = new char[100];
col = 0;
for (char ch : line.toCharArray()) {
this.mtx[row][col] = ch;
System.out.print("mtx["+row+"]["+col+"] = "+mtx[row][col]+", ");
col ++;
}
System.out.println();
row++;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Define nodes for each character in the matrix
In each node define their neighbors according to rules e.g. 8 neighbours or diagonal neighbor not considered case.
This is now a graph.
Start with node that has value M, traverse node using DFS or BFS for the given word.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If I understand the question correctly, we should figure out whether the string exists in the matrix or not. I've tried a brute force solution.

``````public class MatrixOfCharacters {

public static char[][] input = {	{'A', 'C', 'P', 'R', 'C'},
{'X', 'S', 'O', 'P', 'C'},
{'V', 'O', 'V', 'N', 'I'},
{'W', 'G', 'F', 'M', 'N'},
{'Q', 'A', 'T', 'I', 'T'}	};

public static boolean[][] visited = new boolean[input.length][input.length];

public static char[] query  = "MICROSOFT".toCharArray();

public static void main(String...args){
System.out.println(findString());
}

private static boolean findString() {
for(int i=0; i<input.length; i++){
for(int j=0;j <input.length; j++){
if(octSearch(i, j, 0)){
return true;
}
}
}
return false;
}

private static boolean octSearch(int x, int y, int i) {

if(x == -1 || x == input.length){
return false;
}
if(y == -1 || x == input.length){
return false;
}

if(input[x][y] == query[i] && visited[x][y] == false){
visited[x][y] = true;
if(i == query.length-1){
return true;
}
}else{
return false;
}

boolean lookAround = octSearch(x-1, y-1, i+1) ||
octSearch(x-1, y, i+1) ||
octSearch(x-1, y+1, i+1) ||
octSearch(x, y-1, i+1) ||
octSearch(x, y+1, i+1) ||
octSearch(x+1, y, i+1) ||
octSearch(x+1, y-1, i+1) ||
octSearch(x+1, y+1, i+1);
if(!lookAround){
visited[x][y] = false;
}
return lookAround;

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````if all elements are unique then we can make a 1D hashmap <char,int> of  (N*M elements) size where, char: character , int : index of character in original matrix

loop on string "MICROSOFT"

1.if 'M' exists in hashmap on index i1
loop for{
x = i1 / N , y = i1 % N;
if( 'I' exists on index (x+1)*N + y  ,  (x-1)*N + y,  x*N + (y+1),  x*N + (y-1),  (x+1)*N + (y+1),  (x-1)*N + (y+1))
then move further
else return false
}
2.else return false``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS or DFS in the matrix

``````//suppose that a is correct
bool containsString(vector<vector<char>> const &a, string const &s) {
int n = a.size();
int m = a[0].size();

struct QEl {
int x;
int y;
int idx;
};

queue<QEl> q;

int pindex = 0;

int diri[] = {0, -1, 0, 1, -1, -1, 1, 1};
int dirj[] = {-1, 0, 1, 0, 1, -1, -1, 1};

for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) {
if(s[pindex] == a[i][j]) {
q.push({i, j, pindex});
}
}
while(!q.empty()) {
auto &el = q.front();

if(el.idx == s.size() - 1) {
return true;
}

for(int i = 0; i < 8; i++) {
int di = diri[i] + el.x;
int dj = dirj[i] + el.y;
if(di >= 0 && di < n && dj >= 0 && dj < m) {
if(el.idx + 1 < s.size() && s[el.idx + 1] == a[di][dj]) {
q.push({di, dj, el.idx + 1});
}
}
}
q.pop();
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be done using backtracking

``````using System;
using System.Collections;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
char[,] charArray = new char[,] {{'a', 'b', 'c', 'd', 'e'},
{'f', 't', 'i', 'g', 'h'},
{'f', 'm', 'i', 'c', 'j'},
{'k', 'o', 'l', 'r', 'm'},
{'n', 's', 'o', 'p', 'q'}
};

Console.WriteLine(IsWordPresent(charArray, "microsoft"));
}
private static bool IsWordPresent(char[,] matrix, string target)
{
List<Point> points = new List<Point>();
string curr = target.Substring(0, 1);

for (int i = 0; i < matrix.GetLength(0); i++)
{
for (int j = 0; j < matrix.GetLength(1); j++)
{
if (matrix[i, j] == target[0])
{
}
}
}
bool result = false;
foreach (Point p in points)
result |= IsWordPresentUtil(matrix, target, p, 1, curr);

return result;
}

private static bool IsWordPresentUtil(char[,] matrix, string target, Point p, int index, string curr)
{
if (curr == target)
return true;

if (index >= target.Length)
return false;

foreach (Point point in GetPoints(p, matrix.GetLength(0)))
{
if (matrix[point.x, point.y] == target[index])
{
curr += target[index];
if (IsWordPresentUtil(matrix, target, point, index + 1, curr))
return true;

curr = curr.Remove(curr.Length - 1, 1);
}
}
return false;
}

private static List<Point> GetPoints(Point p, int n)
{
int[] xvalues = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
int[] yvalues = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
List<Point> result = new List<Point>();
for (int i = 0; i < 8; i++)
{
int x = p.x + xvalues[i];
int y = p.y + yvalues[i];

if (x < n && x >= 0 && y < n && y >= 0)
{
}
}

return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/* RECURSIVE APPROACH */

public class WordGraph {

int N = 0;
String [][] matrix = new String[5][5];
String word = new String("MICROSOFT");

public WordGraph() throws Exception {

initiateMatrix();
findWord();
}

private void initiateMatrix() {

matrix[0][0]="A";
matrix[0][1]="C";
matrix[0][2]="P";
matrix[0][3]="R";
matrix[0][4]="C";

matrix[1][0]="X";
matrix[1][1]="S";
matrix[1][2]="O";
matrix[1][3]="P";
matrix[1][4]="C";

matrix[2][0]="V";
matrix[2][1]="O";
matrix[2][2]="V";
matrix[2][3]="N";
matrix[2][4]="I";

matrix[3][0]="W";
matrix[3][1]="G";
matrix[3][2]="F";
matrix[3][3]="M";
matrix[3][4]="N";

matrix[4][0]="Q";
matrix[4][1]="A";
matrix[4][2]="T";
matrix[4][3]="I";
matrix[4][4]="T";

}

public void findWord() {

//findStartingPoint
int startRow = -1;
int startCol = -1;
String firstChar = String.valueOf(word.charAt(0));

for (int i = 0 ; i < 5 ; i++) {
for (int j = 0; j < 5 ; j++) {

if ( matrix[i][j].equals(firstChar)) {
startRow = i;
startCol = j;
break;
}
}
}

System.out.println("Starting Char found at = " + startRow + " " + startCol);
isCharMatched(0, startRow, startCol);
}

/**** Recursive Function ****/
private void isCharMatched(int nextCharLoc, int row, int col) {

nextCharLoc++;
System.out.println("\n==============================\nNextChar Location= " + nextCharLoc);

if ( nextCharLoc < word.length()) {

String nextChar = String.valueOf(word.charAt(nextCharLoc));
System.out.println("Finding Char " + nextChar + " Starting from "+row + " "+col);

/*** Loop can be further optimized ***/
for (int i = row -1 ; i <= row +1 ; i++ ) {
for (int j = col -1 ; j <= col+1 ; j++) {

System.out.println("Row="+ row + " Col=" + col + " " + " I="+i+" J="+j);

if (i >= 0 && j >= 0 && i < 5 && j < 5 && matrix[i][j] != null && matrix[i][j].equals(nextChar)) {
System.out.println("Matching Char found at = " + i + " " + j);
isCharMatched(nextCharLoc, i, j);
}
}
}
}
}

public static void main(String[] args) throws Exception {
WordGraph wg = new WordGraph();
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/* RECURSIVE APPROACH */
public class WordGraph {

int N = 0;
String [][] matrix = new String[5][5];
String word = new String("MICROSOFT");

public WordGraph() throws Exception {

initiateMatrix();
findWord();
}

private void initiateMatrix() {

matrix[0][0]="A";
matrix[0][1]="C";
matrix[0][2]="P";
matrix[0][3]="R";
matrix[0][4]="C";

matrix[1][0]="X";
matrix[1][1]="S";
matrix[1][2]="O";
matrix[1][3]="P";
matrix[1][4]="C";

matrix[2][0]="V";
matrix[2][1]="O";
matrix[2][2]="V";
matrix[2][3]="N";
matrix[2][4]="I";

matrix[3][0]="W";
matrix[3][1]="G";
matrix[3][2]="F";
matrix[3][3]="M";
matrix[3][4]="N";

matrix[4][0]="Q";
matrix[4][1]="A";
matrix[4][2]="T";
matrix[4][3]="I";
matrix[4][4]="T";

}

public void findWord() {

//findStartingPoint
int startRow = -1;
int startCol = -1;
String firstChar = String.valueOf(word.charAt(0));

for (int i = 0 ; i < 5 ; i++) {
for (int j = 0; j < 5 ; j++) {

if ( matrix[i][j].equals(firstChar)) {
startRow = i;
startCol = j;
break;
}
}
}

System.out.println("Starting Char found at = " + startRow + " " + startCol);
isCharMatched(0, startRow, startCol);
}

/**** Recursive Function ****/
private void isCharMatched(int nextCharLoc, int row, int col) {

nextCharLoc++;
System.out.println("\n==============================\nNextChar Location= " + nextCharLoc);

if ( nextCharLoc < word.length()) {

String nextChar = String.valueOf(word.charAt(nextCharLoc));
System.out.println("Finding Char " + nextChar + " Starting from "+row + " "+col);

/*** Loop can be further optimized ***/
for (int i = row -1 ; i <= row +1 ; i++ ) {
for (int j = col -1 ; j <= col+1 ; j++) {

System.out.println("Row="+ row + " Col=" + col + " " + " I="+i+" J="+j);

if (i >= 0 && j >= 0 && i < 5 && j < 5 && matrix[i][j] != null && matrix[i][j].equals(nextChar)) {
System.out.println("Matching Char found at = " + i + " " + j);
isCharMatched(nextCharLoc, i, j);
}
}
}
}
}

public static void main(String[] args) throws Exception {
WordGraph wg = new WordGraph();
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

<code><pre>
/*** RECURSIVE APPROCH IN JAVA***/
public class WordGraph {

int N = 0;
String [][] matrix = new String[5][5];
String word = new String("MICROSOFT");

public WordGraph() throws Exception {

initiateMatrix();
findWord();
}

private void initiateMatrix() {

matrix[0][0]="A";
matrix[0][1]="C";
matrix[0][2]="P";
matrix[0][3]="R";
matrix[0][4]="C";

matrix[1][0]="X";
matrix[1][1]="S";
matrix[1][2]="O";
matrix[1][3]="P";
matrix[1][4]="C";

matrix[2][0]="V";
matrix[2][1]="O";
matrix[2][2]="V";
matrix[2][3]="N";
matrix[2][4]="I";

matrix[3][0]="W";
matrix[3][1]="G";
matrix[3][2]="F";
matrix[3][3]="M";
matrix[3][4]="N";

matrix[4][0]="Q";
matrix[4][1]="A";
matrix[4][2]="T";
matrix[4][3]="I";
matrix[4][4]="T";

}

public void findWord() {

//findStartingPoint
int startRow = -1;
int startCol = -1;
String firstChar = String.valueOf(word.charAt(0));

for (int i = 0 ; i < 5 ; i++) {
for (int j = 0; j < 5 ; j++) {

if ( matrix[i][j].equals(firstChar)) {
startRow = i;
startCol = j;
break;
}
}
}

System.out.println("Starting Char found at = " + startRow + " " + startCol);
isCharMatched(0, startRow, startCol);
}

/**** Recursive Function ****/
private void isCharMatched(int nextCharLoc, int row, int col) {

nextCharLoc++;
System.out.println("\n==============================\nNextChar Location= " + nextCharLoc);

if ( nextCharLoc < word.length()) {

String nextChar = String.valueOf(word.charAt(nextCharLoc));
System.out.println("Finding Char " + nextChar + " Starting from "+row + " "+col);

/*** Loop can be further optimized ***/
for (int i = row -1 ; i <= row +1 ; i++ ) {
for (int j = col -1 ; j <= col+1 ; j++) {

System.out.println("Row="+ row + " Col=" + col + " " + " I="+i+" J="+j);

if (i >= 0 && j >= 0 && i < 5 && j < 5 && matrix[i][j] != null && matrix[i][j].equals(nextChar)) {
System.out.println("Matching Char found at = " + i + " " + j);
isCharMatched(nextCharLoc, i, j);
}
}
}
}
}

public static void main(String[] args) throws Exception {
WordGraph wg = new WordGraph();
}

}
</pre></code>

Comment hidden because of low score. Click to expand.
0
of 0 vote

Its not easy as it sounds..
Think of the following usecase

``````R O S O F T
C C C C C C
C I   I   I   I  C
C I   M M I C
C I   I   I  I  C
C C C C C C``````

Happy Coding :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check this solution with above solution

// with memoization
Needle in hasystackD true in count 21
Needle in hasystack1 true in count 29
Needle in hasystack2 false in count 192

// without memory
Needle in hasystackD true in count 36
Needle in hasystack1 true in count 29
Needle in hasystack2 false in count 570

``````import java.util.TreeSet;

public class FindString {

TreeSet<SearchedDataPosition> failedSearchHistory;
char[][] haystack;
String needle;
int size;
public static void main(String args[]) {
char[][] haystack1 = {{'R', 'O', 'S', 'O', 'F', 'T'},
{'C', 'C', 'C', 'C', 'C', 'C'},
{'C', 'I', 'I', 'I', 'I', 'C'},
{'C', 'I', 'M', 'M', 'I', 'C'},
{'C', 'I', 'I', 'I', 'I', 'C'},
{'C', 'C', 'C', 'C', 'C', 'C'}};

char[][] haystack2 = {{'R', 'O', 'S', 'O', 'F', 'O'},
{'C', 'C', 'C', 'C', 'C', 'C'},
{'C', 'I', 'I', 'I', 'I', 'C'},
{'C', 'I', 'M', 'M', 'I', 'C'},
{'C', 'I', 'I', 'I', 'I', 'C'},
{'C', 'C', 'C', 'C', 'C', 'C'}};

char [][] haystackD = {{'U', 'U', 'U'},
{'G', 'G', 'U'},
{'D', 'E', 'B'}};

String needle = new String("MICROSOFT");

FindString fs = new FindString();
System.out.println(" Needle in hasystackD " + fs.find(haystackD, "GUB", haystackD.length) + " in count " + count);
System.out.println(" Needle in hasystack1 " + fs.find(haystack1, needle, haystack1.length) + " in count " + count);
System.out.println(" Needle in hasystack2 " + fs.find(haystack2, needle, haystack2.length) + " in count " + count);

}

public boolean find(char[][] haystack, String needle, int size) {
count = 0;
// TODO: null checks and string length checks.
// TODO: minor optimizations of if needle length is greater that size * size just return false
this.haystack = haystack;
this.needle = needle;
this.size = size;
this.failedSearchHistory = new TreeSet<SearchedDataPosition>();
for(int i = 0; i < size; i++) {
for( int j = 0; j < size; j++) {
if(checkFurther(i, j, 0) == true) {
return true;
}
}
}
return false;
}

static int count = 0;
public boolean checkFurther(int i, int j, int pos) {

if(pos == needle.length()) {
return true;
}

SearchedDataPosition sdp = new SearchedDataPosition(i, j, pos);
if(i < 0 || i >= size || j < 0 || j >= size
|| failedSearchHistory.contains(sdp)  // check output for why this line.
) {

return false;
}
count++;
if(needle.charAt(pos) != haystack[i][j]) {
// we dont really care about zero as we will only land there once.
if(pos != 0) {
}
return false;
}

// check UP LEFT
if(checkFurther(i - 1, j - 1, pos + 1)) {
return true;
}
// check up
if(checkFurther(i - 1, j, pos + 1)) {
return true;
}
// check UP RIGHT
if(checkFurther(i - 1, j + 1, pos + 1)) {
return true;
}
// check RIGHT
if(checkFurther(i, j + 1, pos + 1)) {
return true;
}
// check RIGHT Bottom
if(checkFurther(i + 1, j + 1, pos + 1)) {
return true;
}
// check Bottom
if(checkFurther(i + 1, j, pos + 1)) {
return true;
}
// check Bottom LEFT
if(checkFurther(i + 1, j - 1, pos + 1)) {
return true;
}
// check LEFT
if(checkFurther(i , j - 1, pos + 1)) {
return true;
}

return false;
}

class SearchedDataPosition implements Comparable<SearchedDataPosition> {
int i;
int j;
int position; // position in needle where search failed.
public SearchedDataPosition(int i, int j, int position) {
this.i = i;
this.j = j;
this.position = position;
// TODO Auto-generated constructor stub
}
@Override
public String toString() {
return ("[" + i  +", " + j + ": "+ position + "]");
}
@Override
public int compareTo(SearchedDataPosition other) {
if(this.i == other.i) {
if(this.j == other.j) {
return this.position - other.position;
}
else {
return this.j - other.j;
}
}
else {
return this.i - other.i;
}
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.