Microsoft Interview Question Software Engineer in Tests
and for testing we can reverse the hash table....
that is every time we encounter a letter we decrease the letter count in the hash table...after all the letters are traversed we iterate through the hash table and check if all the letters counts are 0 or not.
Solution1 (worse):
For each char find the occurence by iterating the array.
complexity is O(n^2)
Solution2:
if you are free from modifying the array. Then sort the array and find the occurence.
It takes o(n logn) + o(n) = O(n logn)
Solution3:
If memory is not a constraint, then go with hash table.
It takes O(n) time and O(n)space.
hash table solution is inefficient because it requires a lot of space eg. what if your character set is unicode?
I used a binary search tree and did it in O(nlogn)
you can use a hashtable(like an array); the key is the letter.
- S October 24, 2010for every letter, table[letter]++;