ghantacoder
BAN USEREither the interviewer mentioned the point that the head of the village doesn't know anybody else, or you forgot to write that over here.
Once we have this additional piece of information with us, then we can proceed along the following path.
Suppose, knows ( p1, p2 ) returns true, it means that p1 knows and so p1 can't be the head of the village as the head of the village knows no one else. So when we will call this function the next time, we call knows ( p2, p3 ).
If suppose the function had come out to be false, then p1 would have been a possible candidate for the head of the village. Also, it would have implied that p2 cant be the head, as p1 doesn't know him. In this case, we would have called knows ( p1 , p3 ).
The terminating condition, when we have evaluated all the people, knows ( p(n-1) , p(n) ) - if it returns true, then p(n) would be the lone candidate for the head post of the village otherwise p(n-1).
Now, take care that with whomsoever we are left in the end, is only a candidate, and not the real head. Because maybe that he would have known p1 or p2 or any earlier person. So we have to go through everyone once again to confirm if he was the head of the village or not.
Time Complexity : 2O(n) -> O(n)
Nothing as such is mentioned about it.
- ghantacoder April 06, 20121.
i) Create a char array of size 26 for hashing the occurences of the letters.
ii) Create an array ( depends upon the number of special characters ) for storing the special
characters. ( I assume that there is no sorted order for them, though even if there was one, it
could be handled ).
iii) A temporary int variable would hold the sum.
2. Traverse the given array.
i) Hash the occurences of the alphabets by maintaining a count.
ii) Append the special characters to the array allocated for them.
iii) Keep updating the sum as and when you encounter a number.
3. Printing remains.
i) Traverse the alphabet array in order printing the occurences of the letters.
ii) Print the sum.
iii) The special character string may now be printed as well.
O(N) time and constant space.
What exactly was the question ?
- ghantacoder February 29, 2012In dev compiler, this program is crashing.
However on commenting the *chptr = *inptr line, I get 4 4 as the answer as the pointer variables are storing addresses, which are stored as int type.
What is the value of y after being converted into unsigned ?
- ghantacoder January 29, 2012Adding two numbers may cause integer overflow.
Your logic will only work till 10 nodes.
We can save the numbers in strings if we were to go by your method and then add the numbers in the strings and store them in another string.
Guys, please don't give negative votes to the best solutions. Atleast try to understand the solution before giving it a vote. This solution is the best available on this post :)
- ghantacoder April 13, 2012