## eugene.yarovoi

BAN USERThis is the approach I'd expect on this question. Very solid O(1) lookup, O(n) extra space (assuming every value fits into O(1)) approach. I've posted another approach that is a bit slower but requires no extra space, assuming O(1) bits per integer.

- eugene.yarovoi November 21, 2011There's a way to do this easily without hashing. Why not just, for each word, keep a sliding window of letter counts (use a map). You know the length of the search string (call it K). So start with that many letters in the word (count them using a map), then for each consecutive letter, add the next letter and subtract the letter K characters before in the string. If the map ever contains the exact characters in your search string, you've just matched the pattern. You can even avoid the O(K) map comparison each time by starting the map not empty but with the negative of the count of letters you're looking for. Then you just check if the map is empty each time (O(1)).

- eugene.yarovoi November 15, 2011The flaw here is that you assume that you can merge B and C and then ask whether the result list has two numbers adding up to a certain sum. But if you do that, both numbers could have originated from B, or from C. Implemented more correctly, your approach would end up being O(N^2) or more.

- eugene.yarovoi November 15, 2011You could have gotten O(N^2) with hashing. You can get O(N^2 log N) by producing a sorted version of the result array and doing binary searches on it (O(N^2) searches, O(log N) each).

- eugene.yarovoi November 15, 2011Very clean, correct solution. Checking A[i] < min is unnecessary because it's always true unless they're equal (since your array is sorted). Better to skip that if statement. Also no need to maintain a set. Try just:

i = A.length-1;

while ( (i>=1) && (A[i-1] + A[i] >= K) )

{

--i;

}

return A.subArrayStarting(i);

Hell, you could even do a binary search. Won't really matter because your algo is O(N logN) because of the sort. There's an O(N) algo.

"I think what you are doing is just sorting the array by bit-reversal"

At some point in the comments, I said, "another thought that just occurred to me is that this is a radix sort sorting by least significant digit first." Is that the same as what you're saying?

You couldn't place them like 0 mod n, 1 mod n, ...

They need to be placed 0 mod 8, 8/2 mod 8, 8/4 mod 8, 3*8/4 mod 8, 8/8 mod 8, 5*8/8 mod 8...the pattern is much more complex.

My current approach is essentially a radix sort judging least significant digit first. It's as if you reversed the digits of all the numbers, radix sorted them, and then reversed the numbers back to what they were. So it's O(NK), where N is how many numbers you have, and K is the number of digits in each number.

Well, hold on a second. Space is not N/32. Space is X/32 where X is the number of different possible integers. Imagine now that these are 64-bit long integers or something. I'd recommend a different compression approach.

- eugene.yarovoi November 10, 2011You can always emulate division by doing a binary search and multiplication.

- eugene.yarovoi November 10, 2011Let's say you started with 1 2 3 4 5 6 7 8 9 10 11 12.

1 2 3 4 5 6 7 8 9 10 11 12 -> 2 4 6 8 10 12 (0 mod 2) | 1 3 5 7 9 11 (1 mod 2) -> 4 8 12 (0 mod 4) | 2 6 10 (2 mod 4) || 1 5 9 (1 mod 4) | 3 7 11 (3 mod 4) -> 8 (0 mod 8) | 4 12 (4 mod 8) || 2 10 (2 mod 8) | 6 (6 mod 8) ||| 1 9 (1 mod 8) | 5 (5 mod 8) || 3 11 (3 mod 8) | 7 (7 mod 8).

Now all the partitions are size 2 or smaller, so we're done. The final result is 8 4 12 2 10 6 1 9 5 3 11 7.

I invite you to verify that all constraints are satisfied.

@lyra_vega: So, would your algorithm have produced something like 1 3 5 7 2 4 6 8? You can see how that's incorrect... Splitting by odd and even numbers is the right initial thought, though.

- eugene.yarovoi November 10, 2011@pallavi.bansal20:

Yes, initially the odd numbers would be partitioned into, say, 1 5 9 13 | 3 7 11 15, but then each of those sections in turn would be partitioned again, giving something like 1 9 | 5 13 || 3 11 | 7 15. When there's only 2 numbers per partition, we're done. I invite you to verify that

1 9 5 13 3 11 7 15 satisfies the constraint.

I would think vector-like containers would have copy semantics (in assignments like vec[i] = value;. After all, if you want to pass things around by pointers, you can always make a std::vector<T*> instead of an std::vector<T>. That's why the standard library is made that way.

- eugene.yarovoi November 10, 2011That's not easy. I would look up a number of tests that a random number generator is expected to pass. There's all kinds of stuff. One simple one is to use it to generate random numbers that are, say, integers between 0 and 100, and make sure that the distribution of these numbers is even. You could do a chi-squared test to make sure any observed departures from an even distribution are not statistically significant.

- eugene.yarovoi November 10, 2011At least 4, from an information theoretic standpoint. 13! / 5! / 8! = 1287. When the professor picks 5 students from a group of 13, that is the number of possible outcomes. To know about each student, the professor must have enough info to distinguish between each possible permutation (13!).

Even with no information overlap, 1287^3 < 13!. 1287^4 > 13!, so the professor needs at least k = 4. Whether there actually is a combination of k=4 I am not sure, but K cannot be < 4.

Another thought that just occurred to me is that this is a radix sort sorting by least significant digit first.

- eugene.yarovoi November 10, 2011In fact, it seems this solution is very general. Instead of working for just a list containing 1...N, it can work on a list containing any integers whatsoever.

To elaborate a little on the general proof of this: suppose you have a partition such that you know all numbers there are k mod X. So initially, your partition is the entire list, and you know all numbers there are 0 mod 1 (whole number constraint).

Now, partition your partition as follows

N | N = X+K (mod 2X) and

N | N = K (mod 2X).

These are the only possibilities for values mod 2X if we know N = K (mod X). The sum of a value that is X+K mod 2X and another value that is K mod 2X is necessarily X + 2K mod 2X, and so the average would be K + X / 2 mod X. X is a power of 2 (because we started at 1 and always scaled in 2s) so the division works out.

Now, we said the average of any two numbers from two different sub-partitions of our partition is K + X / 2 mod X, but the constraint on the partition as a whole (and therefore applicable to every number there) is that each number is K mod X. So for the average to be anywhere in the partition (and a number must be in the partition to be positioned between two numbers that are both in the partition), it would have to be that K = K + X/2 (mod X). This implies that X/2 = 0 (mod X), which is impossible for X != 0.

Yep. I wasn't sure about the answer either when I read this question, though I suspected it was undefined. But we seem to be reaching a consensus in this thread that it's UB.

I might note that -Wall would almost certainly catch this, and you might score points with your interviewer for mentioning that you compile with -Wall.

"Restriction: Meeting granularity is 15 min. That is, you can't start a meeting at other than 15 min. boundary like 10:42."

I don't really like that assumption, because nowhere in the problem statement is there an indication that it would be good to assume that.

I don't mind the timezones assumption because everyone's local times can be converted to the same standard time.

Why sort the array? If you're going to make a balanced tree, you can skip that step. If it's just a BST and you want to make sure it's balanced even without balancing mechanisms, then sorting it would be appropriate, of course.

- eugene.yarovoi November 07, 2011I think, strictly speaking, that the answer is "yes, it's possible, but you'd have to make your own implementation of it, because it's not directly supported."

- eugene.yarovoi November 03, 2011You can take C code and call it C++, and then there won't be a performance hit. So C++ can be as fast as C, if it's C-compatible C++ code.

If you use C++-specific features, your code may be slower, but that depends. If you used those features because you really needed them and you end up doing some crazy workaround in the C version, you may essentially be writing an ad-hoc, poorly-documented, bug-ridden, slow implementation of C++. Then C++ might be faster because the C++ compiler may have better optimizations than your ad-hoc implementation.

Another important point is that there are plenty of C++-only features that are not necessarily any slower than their C counterparts. For example, templates allow a great deal of code re-use without any performance drawbacks (since a different version will be made for each type at compile time). As another example, operator overloading is no slower than using functions to achieve the same effects in C -- internally, the operators are converted to function calls anyway.

I see, something like reference counting. Yes, that can be done in 30 minutes. I would argue it's not true garbage collection.

Take a look at the implementation of shared_ptr. It already does that.

I suppose it's good to ask the interviewer what the wrist watch should do. Does it just have the time, or does it also have a Material, Price, etc.? From a business perspective (say, if this is part of an ordering system), the time wouldn't even be part of the data. From a timekeeping perspective, the time is important information, and perhaps the only information that needs to be stored. So, it's really important to examine what problem this class will solve.

- eugene.yarovoi November 03, 2011Here we have a restriction that makes this not NP-complete: namely, that we consider only coin combinations of 3 coins or smaller. If we considered D coins, there is a simple O(N^(D-1)) algorithm, so here there will be an O(N^2) algo.

Add all the coins to a set. Ask the set whether there's a single coin that will work. If yes, return true. If not, iterate through the set, taking each value and checking if the value that would have to be added to that value is also in the set. If that's ever so, return true. If not, to check for combos of three, try each combo of 2 (O(N^2)) and check if the value that must be the remaining value is in the set. Overall complexity is O(N^2).

The restriction isn't what makes DP possible. The restriction makes a brute-force reasonable. Brute force is O(N^3) here. See my solution, an improved brute-force approach using a set that gets the runtime to be O(N^2).

DP would be O (N^2*d), where d is the largest possible integer that can be encountered, which, in the absence of more constraints, could be quite large.

Anonymous is correct about the subset-sum problem. However, here we have a restriction that makes this not NP-complete: namely, that we consider only coin combinations of 3 coins or smaller. If we considered D coins, there is a simple O(N^(D-1)) algorithm, so here there will be an O(N^2) algo.

- eugene.yarovoi November 03, 2011Or just send bytes representing 8 outcomes at a time. You don't have to use strings. But yes, 1 bit per outcome is the way to transmit it.

- eugene.yarovoi November 03, 2011Agreed with anonymous. The thing to realize in this problem is that with very high probability, a random string will be largely incompressible. The best thing is just to encode the data using 1 bit per outcome.

- eugene.yarovoi November 03, 2011@anon: I didn't need to. Many algorithms would flunk just the case I gave. It's perhaps better to consider "a3b1b1b1b1b1a3" because both algorithms starting from the front and algorithms starting from the back will fail that unless they first filter instances of letter1

- eugene.yarovoi November 03, 2011You're assuming M < N. Consider the case "a3b1b1b1b1b1a3". Here N = 11 and M = 14.

- eugene.yarovoi November 01, 2011Dijkstra's algorithm only applies if all entries are non-negative, not just the overall distance between the source and destination. This assumption was not explicitly stated. You cannot infer that from "path".

Still, you could ask the interviewer whether all values are non-negative, and if they are all non-negative, you'd be set.

There are a number of infinite series expansions for pi. One classic one is

pi^2/6 = 1 + 1/4 + 1/9 + ... ad inf. (The sum of the reciprocals of all perfect squares).

Initialize a depth variable to 1. Do a traversal from the root, incrementing the variable by 1 every time you go from a parent node to a child node and decrementing the variable by 1 every time you go from a child node to a parent node. Every time you increment the variable, check to see if it's greater than a maxDepth variable, and if so, update maxDepth.

- eugene.yarovoi October 31, 2011This is if the lists are unsorted, as I think they are. You could do it without extra space in O(n) if the lists were sorted.

- eugene.yarovoi October 31, 2011If a number is divisible by a number less than itself, it is divisible by a number less than or equal to (int)Math.sqrt(n). Can you see why?

- eugene.yarovoi October 31, 2011Can we compress the data by using 1 bit per letter? That's probably the best possible here...

- eugene.yarovoi October 26, 2011Principle of induction?

- eugene.yarovoi October 26, 2011That's not how I understood it. I thought the problem was to return two integers in the array such that they sum to the target value. This is consistent with the remark about using a hash map...

- eugene.yarovoi October 25, 2011@S am: if the array is sorted, you can pick a number and do a binary search (O(log N)) to see if there's a matching number so that the two add to the right sum. Since there's N numbers you have to try, the running time would be O(N logN), which is still much better than the naive O(N^2).

@Anirudh: That's easy. Put all the integers into a hash map. As you read each integer, subtract it from the target value, and now you want to know if there's another integer in the array whose value is that difference. Check the hash map for this.

@gcardone: This has nothing to do with subset-sum. This is a much more restricted problem that deals with only 2 integers. Try every possible first integer, and do a binary search for the second integer. This still results in an O(N logN) algo.

C++ doesn't have to be slower; that's my whole point. C++ is only slower when you use certain C++ features. Stick to only the C features and it'll be just as fast.

C++ does not have dynamic polymorphism when you don't use it. Generally, functions are, in fact, bound at compile time -- only functions marked virtual have dynamic polymorphism. Otherwise, C++ wouldn't be a pay-as-you-go language.

Yes, dynamic polymorphism sometimes allows us to write more reuseable code at the cost of some performance, but that is a tradeoff that you choose to make on a per-function basis in C++. You ask yourself whether you need the behavior for each function. You could decide to not use it at all, if the problem you're trying to solve doesn't need it.

I might not have understood the question. The typical STL maps don't use hash tables, which is why I said what I did.

Perhaps the interviewer was asking about how I would implement a hash table.

C++ follows a pay-as-you-go philosophy. In other words, unless you opt to use the more advanced features of the language, the code isn't any slower than if you had written C. That is, you could write a C program that would also be a valid C++ program and the two would be equally fast.

- eugene.yarovoi October 24, 2011LOGbase2() might use loops internally.

- eugene.yarovoi October 24, 2011Either the interviewer doesn't know their stuff or it's a trick question. STL maps use trees internally, I imagine balanced ones.

- eugene.yarovoi October 24, 2011Hmmm...if you used an and mask, this could in theory be just 2 assembly instructions. This may or may not be more efficient than the previous best solution.

- eugene.yarovoi October 24, 2011If there are duplicates, this solution won't have log(K) performance. Consider the performance of this algorithm on an array that is filled with 2^n of each element for each value n >= 0. The first instance of every value K is at index 2^K-1. Your algo will take log (2^K - 1) time, so about K time.

- eugene.yarovoi October 24, 2011The .h file has the DECLARATION, the corresponding library files should have the DEFINITION. Unless I'm wrong and the actual implementation is in the .h file, which would surprise me.

- eugene.yarovoi October 24, 2011You would need to use a queue (part of a class or global) here to keep track of the timestamps of the last n trues. I will assume n is a constant (and not a parameter), but I will then say how to deal with n being a parameter.

```
/* Consider firing the programmer responsible if you see names like this in your production code */
void aFunctionThatMightBeUsedForCheckingLoginAttemptsForSuspiciousActivity (double k)
{
//get the current time
long time = System.nanoTime();
//if haven't seen n trues at all yet
if (queue.size() < n)
{
queue.push(time);
return true;
}
//at this point we know queue holds the n most recent timestamps of when function returned true
//oldest times come to the front
long timeOfOldestRecord = queue.peek();
//if n trues ago was less than k seconds ago
if (convertToSeconds(time - timeOfOldestRecord) < k)
{
return false;
}
//if reaching this point, n trues ago was k seconds ago or more
//need to update the queue of times when the function returned true
//push to the back
queue.push(time);
//pop from the front
queue.pop();
return true;
}
```

All of the functions used in the implementation here run in O(1) time, so this is also an O(1) implementation.

If n is a parameter, you must grow the queue indefinitely (by 1 with each call, but it's never safe to delete), and look at n nodes from the end when looking for the n-th most recent true. If the queue is backed by an ArrayList, you can achieve amortized O(1) on all of those ops. It may not be possible to achieve unamortized O(1); I'm not sure.

Rep**Gayle L McDowell**, CEO at CareerCupGayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...

Rep**Loler**, Employee at Google

Rep

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

O(d) time per lookup, I mean. O(n) multiplications initially to set it up.

- eugene.yarovoi November 21, 2011