Microsoft Interview Question Software Development Managers
Country: United States
"Do one pass of the matrix O(n)". Shouldn't it be O(n^2)? Assuming the matrix is of size nxn.
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.
@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.
#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");
}
}
}
}
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.io.InputStreamReader;
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++;
}
}
}
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;
}
}
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
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;
}
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])
{
points.Add(new Point(i, j));
}
}
}
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)
{
result.Add(new Point(x, y));
}
}
return result;
}
}
/* 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();
}
}
/* 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();
}
}
<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>
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) {
failedSearchHistory.add(new SearchedDataPosition(i, j, pos));
}
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;
}
}
}
}
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.
- Adam Smith November 01, 2014I'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.