O(keys * averageKeyLength) per query
You can improve to O(averageKeyLength) by using a trie instead of a HashMap
Mock interview practice http://www.codingpill.com
O(keys * averageKeyLength) per query
You can improve to O(averageKeyLength) by using a trie instead of a HashMap
try binary search for an efficient O(logN) approach
You can also follow https://www.facebook.com/codingpill for Silicon Valley style interview questions
Start with the stacktrace. Figure out who is causing the segfault (either use the debugger or print all the variables that are involved). Now you need to find out where in your code things start going out of track. You can use a binary search technique setting a few checkpoints (could be either debugging breakpoints or print statements) until you isolate the place where the bug initiates from.
My bad, should be something more like
for (i=1; i<N; ++i) {
if (a[i] > s[i]) {
coins.push_back(i);
++s[i];
for (int j=i; j+i<N; ++j)
if (s[j] > 0) ++s[j+i];
}
}
O(n^2)
@eyfmharb See my comment above, the Sieve of Eratosthenes can be O(n log log n) if implemented carefully.
for (i=1; i<N; ++i) {
if (a[i] > 0) {
coins.push_back(i);
for (int j=i; j<N; j+=i) --a[j];
}
}
proving that the complexity is O(n log log n) is quite complicated. You can find the proof if you google it.
Let's assume you have a square of length 1x1. Draw a circle of radius 1 inside the square. pi is the ratio between the area of the circle and the area of the square.
Now pick a few hundred thousand numbers inside the square. Count how many of them are inside the circle. Compute the ratio and you have a pretty good approximation of pi.
If you need some inspiration you can follow us on Facebook for daily system design and coding interview questions