aejeet
BAN USERBrian Kernighan's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.
Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to him that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"
long count_bits(long n) {
unsigned int c; // c accumulates the total bits set in v
for (c = 0; n; c++)
n &= n - 1; // clear the least significant bit set
return c;
}
we can make use of voronoi diagram. The construction will take O(nlgn) and will require O(n) space. Using this diagram we can find the nearest neighbor of each point in O(lgn). Now we can iterate linearly over each point finding its nearest neighbor. If we find a point whose nearest neighbor is less than at Manhattan Distance of 5 Units then we return False. Finding n nearest points takes O(nlgn).
- aejeet July 23, 2010The Point the interviewer will never ask to write code for a trie/suffix tree or knuth-Morris Pratt during an interview. So in my opinion if we are asked to only explain a method by which this can be done then Suffix Tree offers best possible efficiency. But if he asks to write code then i will try writing a code using dynamic programming. Though DP will have a quadratic solution, it will be easier to code.
- aejeet July 22, 2010Hi,
What do you mean by "Binary search for the length of the answer" ? We do not know the length of the answer so how can we feed this value into the input? I believe Robin Carp can be used when we have a Pattern which we want to match in the Text. But here we have no such input pattern.
I agree with Vinod. Suffix Tree will offer the best possible solution. Suffix tree on input string can be build in linear time and space. Search for deepest internal node can be done in linear time too.
But i was wondering if there exists any Dynamic Programming Solution (though less efficient but easier to code compared to suffix tree) for this problem ?
Any Suggestions
"One way to do it is to scan the array in reversed order, maintaining a balanced binary tree which can answer queries like "how many elements in the tree are smaller or equal to x".
This will do it in O(nlogn) time"
@ftfish can you elaborate this method which uses a binary tree?
"One way to do it is to scan the array in reversed order, maintaining a balanced binary tree which can answer queries like "how many elements in the tree are smaller or equal to x".
This will do it in O(nlogn) time"
@ftfish can you elaborate this method which uses a binary tree?
This can be solved in O(n^3). The question is similar to the question which asks the number of ways in which an expression can be parenthesized.
- aejeet July 28, 2010We maintain a matrix NOP[n,n] where n is the size of the list. Now between ever pair of i & j such that j>i we iterate for all k such that k lies between i & j.
NOP[i,j] = for all k : i<k<j { NOP[i,k] + NOP[k,j]}
This will run in O(n^3). Can anyone better this ?