CareerCup

boolean containWord(Board board, String result, final String TOFIND){

if (result.equals(TOFIND)){
return true;
} else {
foreach (Char char: board){
foreach (Char c: getNeighbors(char))
boolean result = containWord(board, result + c) || containWord(board, result);
if (result){
return true;
}
}
}
return false;
}

Can't we use an array of size 26 to store all the occurring alphabets and then check if the given word can be framed by those letters or not

Interviewer expected me to write most of code(not pseudo) and take care of the special cases. Time limit upto 45-50 mins.

I would use an Hash table for this problem, to initially scan the entire array into the hash, I would also track the duplicates on the hash elements , hash[x]+=1. Then I would take a string pointer in computer and go from start to finish. I will provide the code later for this problem.

The reason for using the hash is becuase in the above 8x8 array, the computer is spread in both x and y directions.

what cMonkey says is the straight solution...I would ask the interviewer is there any restrictions on time and space usages.....because hash table might take more space...

Do a dfs on the graph...for "computer"...
I would keep a track for each character, where in the matrix it occurs in a separate table. This helps me get the start node quickly. And then DFS with +1 and -1 on rows and cols as adjacent edges.

Maybe we need to be careful of backedges...maybe not...
Example: "mum" can be found by going from m to u and then back to "m". Will check if thats valid...

what do u mean ??
how do u build a graph for "computer" ? and y a graph?

How about sorting array and the input word ("computer") and then set two pointers to the beggining of each and iterate till the end of either of them. If we are at the end of "computer" means we found the match otherwise we didn't?

set<char> word="computer";
....for (int i=0; i<m*n; i++){
.......if (!word.size()){
...........found=true;
...........break;
.......}
.......}else
...........word.erase(matrix[i/m][i%m]);
.......}

2 stacks

what 2 stacks?

please give exact solution

how we use 2 stack

Why do we need a hashtable. We can just do it using an int array of size 256 since the array doesn't have any unicode chars.

instead of using hash for the matrix, if we use hash of the search string the woud be gr8. so first we scan the search array in hash to see the occurance of every char in the search string then would travers the matrix one by one and indexing every occuranc of char in the search hash . if char is found that means char for search sring is found we decrement the count initially mainained. now if either at the end of inbetween all the count gets zero meansstring is found.