Microsoft Interview Question
Country: United States
how does this work if there are mutiples of the same character in the 2D array? how do you seperate them in the hash?
public class FindPatternInGivenArrayOfChars {
private boolean findPattern(char[][] array, char[] pattern)
{
for(int i=0; i< array.length; i++)
for(int j =0; j<array[i].length; j++)
{
if(String.valueOf(pattern).trim().isEmpty())
return true;
pattern=checkInPattern(array[i][j], pattern);
}
return (String.valueOf(pattern).trim().isEmpty())?true:false;
}
private char[] checkInPattern(char val, char[] pattern)
{
char[] newPattern=new char[pattern.length];
int index =0;
boolean marked=false;
for(char eachChar: pattern)
{
if(marked || eachChar != val)
newPattern[index++]=eachChar;
else
marked=true;
}
return newPattern;
}
public static void main(String[] a)
{
char[][] givenArray ={{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i','t'}};
String pattern ="microsoft";
if(pattern.isEmpty())
System.out.println("Provide valid Pattern..");
FindPatternInGivenArrayOfChars obj = new FindPatternInGivenArrayOfChars();
if(obj.findPattern(givenArray, pattern.toCharArray()))
System.out.println("Pattern '" +pattern + "' Found.... :)");
else
System.out.println("Pattern '" +pattern + "' Not Found.... :(");
}
}
Just another c++ implementation where each cell is visited only once. Cheers.
{
#include <iostream>
using namespace std;
#define WIDTH 5
#define HEIGHT 5
void findPattern(char givenArray[][HEIGHT], std::string pattern){
std::size_t found;
for (int i=0; i<WIDTH;i++){
for(int j=0; j<HEIGHT;j++){
found = pattern.find(givenArray[i][j]);
if(found!=std::string::npos){
pattern.erase(pattern.begin()+found);
}
}
}
if(pattern.empty()) cout<<"pattern found"<<endl;
else cout << "pattern not found, number of unmatched characters: "<<pattern.length()<<endl;
}
int main() {
char givenArray[WIDTH][HEIGHT] ={{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i','t'}};
std::string pattern = "microsoft";
findPattern(givenArray, pattern);
return 0;
}
}
public class FindPattern {
HashMap<Character, Integer> dictionary = new HashMap<Character, Integer>();
String answer;
public boolean makeHash(char[][] matrix, String s){
answer = s;
for(char[] x : matrix){
for(char y : x){
if(dictionary.containsKey(y)){
dictionary.put(y,dictionary.get(y)+1);
}
else dictionary.put(y,new Integer(1));
}
}
return verify();
}
private boolean verify(){
for(char x : answer.toCharArray()){
if(dictionary.get(x) > 0)
dictionary.put(x, dictionary.get(x) - 1);
else return false;
}
return true;
}
}
Here is a JUnit
import static org.junit.Assert.*;
import org.junit.Test;
public class JUnits {
public boolean testPattern(String s){
char[][] pattern = {{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i','t'}};
FindPattern fp = new FindPattern();
return fp.makeHash(pattern, s);
}
@Test
public void test() {
assertTrue("Will return TRUE", testPattern("microsoft"));
assertFalse("Will return TRUE", testPattern("miiiiiiicrosoft"));
}
}
Create array of 128 size. set the index with character of 2D array. then search the pattern in array.
bool exist(vector<vector<char> > &board, string s){
for(int i = 0; i < board.size(); ++i){
for(int j = 0; j < board[0].size() ; ++j){
if(board[i][j] == s[0]){
if(existHelper(board, s, 1, i, j)) return true;
}
}
}
return false;
}
bool existHelper(vector<vector<char> > &board, string s, int index, int i , int j ){
if(index == s.size()) return true;
if(i > 0 && board[i - 1][j] == s[index]){
char temp = board[i][j];
board[i][j] = '#';
if(existHelper(board, s, index + 1, i - 1, j)) return true;
board[i][j] = temp;
}
if(i < board.size() - 1 && board[i + 1][j] == s[index]){
char temp = board[i][j];
board[i][j] = '#';
if(existHelper(board, s, index + 1, i +1, j)) return true;
board[i][j] = temp;
}
if(j> 0 && board[i][j - 1] == s[index]){
char temp = board[i][j];
board[i][j] = '#';
if(existHelper(board, s, index + 1, i , j - 1)) return true;
board[i][j] = temp;
}
if(j < s.size() - 1 && board[i][j+1] == s[index]){
char temp = board[i][j];
board[i][j] = '#';
if(existHelper(board, s, index + 1, i, j + 1)) return true;
board[i][j] = temp;
}
return false;
}
#include<stdio.h>
#include<string.h>
main()
{
char str3[30],str2[20]="microsoft";
int i,j,p=0,k=0;
char *q;
q=&str2[0];
char str1[20][20]={{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i','t'}
};
for(i=0;i<5;i++)
for(j=0;j<5;j++)
{str3[k]=str1[i][j];k++;}
for(k=0;k<strlen(str2);k++)
for(i=0;i<strlen(str3);i++)
{
if(str2[k]==str3[i])
{str3[i]=' ';p++;break;
}
}
printf("%d\n",p);
if(p==strlen(str2))
printf("1\n");
else
printf("0\n");
getch();
}
Easy and simple code, thanks for it. I have one doubt, the problem statement said, that a cell can't be used twice for pattern searching, but here a single array is used for more than once to search with str2. So is it fine? or the statement was for something else?
My searching algorithm was of order o(n^3)
i searchd for each letter of string 'microsoft' in 2-D string
and wherever i found that charachter i replaced it with '1' and incremented the loop for the string to find next letter.
then i counted the number of '1' in the 2-D String
if it equals the length of 'microsoft'
this means string found
else
not found...fortunately my algorithm worked in c++
would it be wise to compare for each letter in matrix with ''microsoft" and if found then count can be incremented..if count==strlen(),..then pattern found..order O(n)..
Assuming that string is mutable - we can modify a string on the go, then we can simply do the following:
String pattern = "microsoft";
for each char m[i][j] in m do:
if(pattern.contains(m[i][j])){
int index = pattern.indexOf(m[i][j]);
pattern.charAt(index ) = " ";
if (pattern.equals(" ")){ // 9 spaces
return true;
}
}
end for each;
return false;
There is very simple code. O(n^2+m) without hash, just a little fixed buffer.
#include <stdio.h>
#include <string.h>
int main() {
char const pattern[] = "microsoftx";
char const m[5][5] = {
{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i','t'}
};
int counts[256];
memset(counts, 0, sizeof(counts));
for (size_t i = 0; i < sizeof(pattern)-1; ++i) {
++counts[pattern[i]];
}
for (size_t i = 0; i < sizeof(m); ++i) {
--counts[((char const *)m)[i]];
}
for (size_t i = 0; i < sizeof(counts)/sizeof(counts[0]); ++i) {
if (counts[i] > 0) {
printf("there are not all letters in matrix: '%c'\n", (char)i);
return 0;
}
}
printf("there are all letters from pattern in matrix!\n");
return 0;
}
We can use a hash to keep the count of each character and decrement the count whenever we use the letter. O(n) time and O(n) space.
- alex September 12, 2013