Amazon Interview Question Software Engineer / Developers
If the string is long, here is what you do.
haystack -> original string . length n
needle -> the substring you are trying to match. lenght k (<=n)
step 1)
for each char in needle
put char in hash
O(k)
step 2)
for each char in haystack
if char in hash
if list doesnt exist for char, create list for that char
append position to its list.
O(n)
note that all positions in the lists will be sorted
step 3) merging of the k lists.
This is only pseudo code, havent checked for boundary conditions, errors etc
int ptrs[k] -> maintain an index for each list, initially all 0.
count=0;
lists_not_empty=true;
while(lists_not_empty)
{
for i=2 to k
{
if (list[i].end)
lists_not_empty=false;
/* get the ptrs[i]'th elem in the ith list */
while( (lists[i])[ptrs[i]] < (lists[i-1])[ptrs[i-1]] )
ptrs[i]++;
if(lists[i])[ptrs[i]] + 1 != (lists[i-1])[ptrs[i-1]])
ptrs[1]++; break;
} //end of for
if( (lists[k])ptrs[k] + k == (lists[1])ptrs[1]
count ++;
}
Using substr and strindex functions, it can be done in O(n squared) time.
Using a hash table with keys as all two element sub-strings and values as number of times the sub-string was seen earlier, we can do it in O(n) time.
What hashtable? You need to define it.
For ASCII chars, use a 256 x 256 integer array(26 x 26, if A-Z and a-z only).
So if we see AA, increase C[0][0] by 1. For FO, increase C[4][14] by one.
We need only scan the string n-1 time and then report those larger than 2 in the array.
O(n) space does not make sense.
Generate a suffix tree out of the given word. Now look for the "branch" node with atleast 2 children and min depth of 2.
The given input string is FOOPARFOO.... We use hash table to solve the problem ..
First we hash 'FO' then 'OO' then 'OP' then 'PA' and so on. At some point when we try to hash ' FO' we see that the entry for 'FO' already exists at that point we conclude that a duplicate has been found
Time complexity is O(n) and space complexity is O(n)
Find positions of the chars F and O in string
- Anonymous November 20, 2009F -> 1,7
O -> 2,3,8,9
Building this takes O(n) time.
Now maintain 2 pointers over the 2 list, similar to merge process in merge sort. and at any point if O[i]=F[i]+1, increment your counter.
Another O(n) time. So total is O(n) with O(n) space to maintain the lists.