Microsoft Interview Question Software Engineer in Tests
Its the first repeated substring
For ABCBDA - answer is A, A is first repeated substring
For ABCBCBCD - answer is BC(if substring should not overlap) and BCBC(if substrings can overlap)
You can add each individual letter to an array list.
As you keep adding, if you find a letter that already exists, check to see if the next letter matches the next letter of the previously matching letter, until you find a letter that does not match.
That should do the trick
Just an extension to Prashanth's algorithm to improve complexity. Use a hash map for storing the locations for each alphabet <key,value> => <alphabet,arrayOfLocations>. Everytime we find an existing alphabet we insert the new location at the end of existing arrayOfLocations for that alphabet. So that when we want to access an alphabet of same type we dont have to go through the array from beginning, we can access using hash map in constant time.
Again, correct me if am wrong
please provide a example for your implementation. I think Prashanth solution is ok. But how to deal with overlap case?
As far as I understand, Prashanth's algorithm has O(NxN) complexity. I think you can do it using suffix tree for O(N), but it's hard to implement on the interview :)
Let's think the MATCHED substring is end of the array.
With this string "AbcdefghjklmnopqrstuvwxyzA"
Your temp array going to be increased like "Abcdefghjklmnopqrstuvwxyz" worst case is N * N
Can you guys please look at this too.
This Problem has to be solved recursively
So the Problem being this.
Given a particular number say 637-8687 (NERVOUS) would be the word.
So for the older keypad’s seen on telephone’s I would have to create Mnemonics.
So for doing this, the first part being list out all the Permutations possible for a particular number series.
Ex: ListMnemonics(“723″) would result in
PAD PBD PCD QAD QBD QCD RAD RBD RCD SAD SBD SCD
PAE PBE PCE QAE QBE QCE RAE RBE RCE SAE SBE SCE
PAF PBF PCF QAF QBF QCF RAF RBF RCF SAF SBF SCF
For this my logic is
for the above number 723, somehow create all the permutations for 23 and then append for each of those permutations the letters of 7. That would give all the permutations possible for 723. The base case being if there is a single number then I would print its letters.
But please let me know what you guys think
It is simple question just do it.
char keyMap[10][5] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void rcsv_KeyPermute(char *keyNum, char *buf, int level, int end)
{
char *keys = keyMap[ *keyNum - '0' ];
char ch;
while( (ch = *keys++) != NULL )
{
*(buf + level) = ch;
if( level != end )
{
rcsv_KeyPermute( keyNum+1, buf, level+1, end );
}
else
{
*(buf + level + 1) = NULL;
cout << buf << " ";
}
}
}
void KeypadPermute(char *numbers)
{
int length = strlen(numbers);
char buf[100];
rcsv_KeyPermute(numbers, buf,0, length-1);
}
question is not clear.
- Anonymous October 13, 2010Does the substring should be longest? otherwise, just find the first repeated character in the given string. This can be done in O(n) by hashing.