rtpdinesh
BAN USER
Comments (7)
Reputation 30
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
You can reduce the complexity of finding the count of characters lesser than the one we are looking for in one step rather than searching for it every time.
Keep a count[] array such that count[i] holds the number of values lesser than ith character in that string.
Logic:
count[256] = { 0 };
for(int i = 0; str[i]; i++)
count[str[i]]++;
for(int i = 1; i < 256; i++)
count[i] = count[i-1];
Now use this count array to look for the number of letters lesser than the letter we are looking for. This way we can avoid the inner loop in your code.
Hence the complexity becomes O(n) from O(n2).
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
HashMap solution would require to sort the keys based on count and if equal count then on alpabetical order.
- rtpdinesh February 16, 2013But a solution with trie(to ensure uniqueness in max heap entry) and a max heap (sorted order) in combination would provide a sorted order.