eugene.yarovoi
BAN USERThe interviewer should certainly not allow the candidate to seek outside help from other people. The interviewer may choose to allow or disallow outside sources like books, Google.
- eugene.yarovoi July 26, 2012That was interesting. Doesn't change my analysis of this specific approach, though. The approaches discussed in the article are different.
- eugene.yarovoi July 25, 2012You don't need to maintain anything. I'm saying, you might use a map with a char* if you were maintaining such a thing. There are times when it's useful. It's useful for the same reason why using pointers instead of passing everything by value is sometimes useful.
And what in the world do functors have to do with anything? You still haven't explained that. The problem statement is to make a map with char*, not to do anything else.
Lucky that I don't expect searching for "ttt" to work then. I don't expect value-based searches to work. In this case, I would only expect searching for the pointer to work. This is still quite useful if I'm getting these pointers from another data structure that's supposed to work with this one or something like that.
- eugene.yarovoi July 25, 2012You can use char* as a key without using functors. That's why I'm having a lot of trouble seeing how functors are relevant here.
- eugene.yarovoi July 25, 2012That's not what happens when you declare the template type to be char&, as in
std::map<char&, valueType> foo;
@Anon: I don't understand what you're saying.
- eugene.yarovoi July 25, 2012I'm sorry to tell you that I don't understand why you think functors are relevant here. While functors are a very useful construct that I myself have happily used in the past, I don't see how they answer the question here. The original problem statement just asks whether it's possible to use char* as the key type in a map. And the answer is yes, it is. When someone answered that it's useless, I felt compelled to tell them that there are sometimes occasions to do it. But what do functors have to do with this discussion?
- eugene.yarovoi July 25, 2012I mean, what if you didn't want to pass a string by value, but you wanted to just pass it by identity (two strings are equal if they are in the same place in memory). If these are C-style strings and if we wish to use them as keys in maps, char* would make sense. Not a common case, but plausible.
- eugene.yarovoi July 25, 2012While an interesting read, it's fairly irrelevant to this specific discussion.
- eugene.yarovoi July 25, 2012It's the one that has only one ball in it.
- eugene.yarovoi July 24, 2012There are plenty of times you'd want to use char* in a map. For instance, if you're associating the identity and not the value of c-style strings (as a key) with some other value.
- eugene.yarovoi July 24, 2012Why not char*? Char& is another story though...
- eugene.yarovoi July 24, 2012@irraju: in that case I'll just leave one red ball in one of the bins, and use touch to know which bin has only one ball. I'll pick that one. 100% success rate!
- eugene.yarovoi July 24, 2012If the item to be found is less than X, parts 1, 2, and 3 need to be searched. What's happenning here is that we're searching the left half (1 & 2) and the upper half (1 & 3) in this case. So the approach is valid. Had the overlap been avoided here, the complexity could have been n^(log base 2 of 7), a small improvement over the naive algorithm, but not better than the O(n^2) approach mentioned before.
- eugene.yarovoi July 24, 2012Even the expression b = (a++) + a is undefined.
- eugene.yarovoi July 24, 2012What specifically don't you understand about it?
- eugene.yarovoi July 24, 2012The order in which a++ and a get evaluated is not defined, and so this will be undefined behavior as different execution orders will lead to different results.
- eugene.yarovoi July 24, 2012If you really need that kind of dark bizarre voodoo behavior, you can use synchronization when creating the objects and a finalizer to decrement the object count when an object gets GC'd. But since GC is not guaranteed to run at any particular time, doing this kind of stuff is usually a worse idea than it seems.
- eugene.yarovoi July 24, 2012Not what's being asked.
- eugene.yarovoi July 24, 2012I don't know of any better approach than O(n^2) as posted above.
- eugene.yarovoi July 24, 2012Anonymous is right. That is a valid approach that correctly counts the number of "dominating" pairs. I do think it was a bit vague and unclear though, so I will describe the algorithm in more detail.
This algorithm counts the pairs in O(NlogN). This algorithm can also be used to print out all dominating pairs in O(NlogN + P) where P is the number of such pairs. So if the number of dominating pairs is subquadratic, we will achieve a subquadratic algorithm. If not, then of course we must require quadratic time.
We sort the inputs by ascending x_i. For elements whose x_i values are identical, sort them among themselves by descending y_i (this will properly handle duplicate x_i as I will show). Make a blank order statistic tree. This is a tree that lets us efficiently, in logN time, ask how many nodes are less than a certain value. It also allows logN insert. Now, start from the beginning of the sorted array, and for every value, ask the order statistic tree how many values seen before had a smaller y. We dominate all such values since by construction we have a greater x than all the pairs in the tree so far. In fact we are checking only against pairs with smaller x. Smaller or equal to, that is. But pairs with equal x won't matter because we sorted the y in descending order for equal x, and so the tree won't contain any values with equal x and smaller y. If the criterion had been >= x_i to dominate, we would have sorted y by ascending order within values that have the same x, thus counting all the pairs with equal x. After doing the lookup and adding to a running total (and possibly printing all relevant elements by in-order traversal), we will add the current element to the tree.
We will end up doing O(N) tree lookups and O(N) tree inserts, for a total O(NlogN) cost. The sorting we did initially on the array also cost O(NlogN), so the grand total is O(NlogN). If you printed the elements, in-order traversals cost (logN + nodes traversed), for a grand total of O(NlogN + P) for this entire algorithm.
Ok, can you count the number of such pairs in less than O(n^2)?
- eugene.yarovoi July 23, 2012-1 for providing insufficient detail to determine what the solution is.
- eugene.yarovoi July 23, 2012The exact same way a hash table does anything in O(1) time. Our hash function? Whatever hash function you normally use for integers. So pick a random integer a and a large prime and do something like ((a * element) % p ) % numBuckets
- eugene.yarovoi July 23, 2012It's not better than that. Sorry. It's O(n^4.75) or thereabouts, as explained by the analysis above. Not every divide and conquer algorithm is guaranteed to be better than the naive algorithm. That's why not every problem is solved by divide and conquer.
- eugene.yarovoi July 22, 2012You could either throw an exception or return a value that is checked for in the calling function.
- eugene.yarovoi July 22, 2012In what manner is the enclosing 3d figure to be constructed from the selected k points?
- eugene.yarovoi July 22, 2012It won't be called every time. The calculation will be done once for the entire tree and the sum values stored in a new tree structured analogously to the original input.
- eugene.yarovoi July 22, 2012If only this algorithm were correct, it would be a pioneering research breakthrough, as solving this in subquadratic time is an important open research problem. Unfortunately, there's no reason to do i++ or j-- when you don't find the number in the binary search. You need a binary search for every *combination* of i and j, so making this correction, you'd end up taking O(n^2 logn) time.
- eugene.yarovoi July 22, 2012Have you heard of "undefined behavior'? Undefined behavior means the answer doesn't have to be anything.
- eugene.yarovoi July 22, 2012Well, if X is the input size F(X) = 3 F(X/2) = 9 F(X/4) = .O (3 ^(log base 2 of X)) = X ^(log base 2 of 3). But X is O(n^3), so this is actually approximately O(n^4.75), a huge complexity. Compare to the O(n^2) solution.
- eugene.yarovoi July 22, 2012if (resultFound) { return; }
Does that help you at all? I'm really not quite sure what you're asking.
The general approach to solving a circuit problem is to use Kirchoff's laws. But this is way too sophisticated for an interview.
- eugene.yarovoi July 22, 2012Absolutely agreed with Manan. I really can't see how there's any debate. Isn't it obvious by elementary logic?
- eugene.yarovoi July 21, 2012Could we define what it means for a set of K points to enclose another set of N points?
- eugene.yarovoi July 21, 2012I don't understand the question.
- eugene.yarovoi July 21, 2012No you won't. Don't just use terminology like "divide and conquer" and assume that yields logarithmic time. Give a specific algorithm that is better than O(n^2), and I'll be impressed.
i* O(n) = O(n^2) when i is O(n), like it is here.
And you may need to delete the least recently seen node if your cache is a fixed-size cache.
- eugene.yarovoi July 21, 2012@notbad: not really
- eugene.yarovoi July 21, 2012Resistance between which two points? I would think that's rather relevant.
- eugene.yarovoi July 21, 2012No it won't. How will you apply binary search to achieve n logn?
- eugene.yarovoi July 21, 2012@axecapone: yes, there are lots of problems from coding competitions and lots of homework problems here. But these are very easily distinguishable from the rest and so it doesn't impact reliability. See a problem that has constraints, sample input & output, and a very detailed, very clear problem statement? That's from a coding competition. See a problem where someone just wants the code and isn't interested in anything else? That's homework. Everything else is reliable.
I've been asked a lot of problems on this site in real interviews.
I was even saying that I don't think there's much correlation between the objective difficulty of the question and whether it's asked on the phone or in-person. Actually, if you take the fact that performance is relative into account, shouldn't you conclude that in-person interviews are more difficult because only the toughest competitors get to that stage? You're the expert, of course, but doesn't it follow from the premises?
- eugene.yarovoi July 21, 2012Just because some problems seem hard to you doesn't mean they're tagged incorrectly. In my experience interviewing with some of these big companies, there was no strong correlation between the difficulty of a problem and whether it was asked over the phone or in person. You can definitely be asked very simple or very difficult problems in either. Trust this website. It has a pretty representative sample.
- eugene.yarovoi July 20, 2012Yep. While you may be able to rule out some of the rectangles, you still can't pinpoint it down to less than O(n) of them.
- eugene.yarovoi July 20, 2012Hash tables are much slower than arrays. Also, that gives you expected instead of deterministic time.
- eugene.yarovoi July 20, 2012I think you should just try to be as honest as possible about why you want to switch. After all, wanting a career change is not uncommon. You should also try to take on activities that would prepare you for your new career and help you develop relevant skills.
- eugene.yarovoi July 20, 2012Well, you could do it in O(n^2). I'm assuming positive integers here for simplicity. First, sort the array. Then, In the equality a^2 + b^2 = c^2, try every element for c. Now for each choice of c, have two pointers, one initially pointing to the smallest element and one pointing to the element right before c. Let the first pointer be a and the second be b. Compute a^2 + b^2 for this choice of a, b and compare to c^2. If a^2 + b^2 = c^2, you're done. If a^2 + b^2 > c^2, decrement the b pointer. If a^2 + b^2 < c^2, increment the a pointer. if the two pointers meet, there are no a,b that satisfy the equality for the current choice of c.
Since given a particular choice of c, you're shrinking the distance between the two pointers by 1 every time and that distance was at most O(n) to begin with, each choice of c is evaluated in O(n) time. Since there are O(n) choices of c, the algorithm is O(n^2).
Beating O(n^2) is probably very difficult because even for the (presumably) simpler problem of finding three numbers satisfying a + b = c, it is an open research problem whether a subquadratic time algorithm exists.
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
RepLoler, Employee at Google
Rep
I wouldn't do either. I would create an immutable wrapper for my list by calling Collections.unmodifiableList (List<T> ls). But that is internally implemented as implementing the List interface and does not extend ArrayList. This only makes sense, since not every list wrapped in this wrapper is necessarily an ArrayList. It could be a LinkedList, etc.
- eugene.yarovoi July 26, 2012