Microsoft Interview Question
Software Engineer in Tests1- Create a hash table.
2- Insert each char of S1 in the hash table.
3- Iterate every char in S2. If that char is in the hash table return the index.
If the index ==strlen(S2) return -1;//Not found
The order of checking an element in the hashtable is O(1) therefore the order of the function is O(n)
If the question is: "Get the first character from s1 that is repeated in s2." (otherwise, reformulate the question and/or give a sample), then:
- S January 17, 2011-Assume ASCII.
-Create a array a[128] where you set the frequency of the characters from s2.
-For every char in s1, check if the frequency is >= 2.
-O(n+m)