eugene.yarovoi
BAN USER@Anonymous, @iamsubhra84: you're both wrong. If there are K elements in the heap, doing a heap remove / insert is O(logK), and you'll have to do that for up to N elements as you're
traversing the array, so the algorithm has O(NlogK) complexity.
@iamsubhra84: Perhaps you were referring to the fact that there exists a O(K) algorithm for making a heap out of K already determined elements. That's true but irrelevant in the analysis of this algorithm.
Read about what undefined behavior is.
- eugene.yarovoi July 14, 2012This is NlogK alright.
- eugene.yarovoi July 13, 2012You should BFS search from both endpoints and do set intersection after each new level is visited. That way, if A and B are separated by distance d, after d/2 levels of friends have been searched from each, the intersection will be found. Set intersection of two sets of size m and n can be done in expected O(m + n), so if x is the approximate number of friends per person, this will run in roughly O(x^(d/2) + x^(d/2)) = O(x^(d/2)) instead of the O(x^d) we'd get from a BFS from only one of the endpoints. Searching from two endpoints has the square root of the runtime of the regular BFS algorithm.
Think about it this way. If you wanted to find whether two people share a mutual friend, would you 1) do a set intersection on the two people's sets of friends or 2) find all of A's friends, find all the friends of each such friend, and check whether B is in this giant set? The above algorithm is just a generalization of the insight that choice 1 is much better.
There is actually a method to find a median of a list in deterministic linear time. It's called median of medians.
- eugene.yarovoi July 13, 2012I thought of the same solution and thought it was sufficient because I interpreted the words as being English / natural language words. That would make them all relatively short and prevent the number of possibilities, which is exponential in the word length, from getting out of hand.
- eugene.yarovoi July 13, 2012Yes, it's recursing through the height of the tree. No, that doesn't make it O(N^2). It's O(N). Each call to "level" does O(1) work before possibly calling "level" again, but another call to "level" can only happen if "level" has never been called with the given argument before. So a maximum of O(N) calls to "level" can be opened, each of which costs O(1) time and O(1) space to evaluate, for a total cost of O(N) time and O(N) space.
- eugene.yarovoi July 13, 2012I'm actually storing a set describing where the values occur. If you only store a count, you won't be able to delete the values efficiently.
- eugene.yarovoi July 13, 2012The point you bring up is quite interesting.
In this particular problem with just 3 people, it's not possible to avoid the threat you mentioned. If everyone is informed of the result of the computation, it doesn't take anything fancy for two conspirators to figure out the salary of the third person. Really, they need not even consider the algorithm being used. They can just multiply the average by 3, subtract out their salaries, and they'll be left with the salary of the third person.
However, here's an interesting question. Say we have k people. You can see how the algorithm described can generalize to k people. But...if the third person tells the first person what he heard from the second person, the second person's salary can be compromised. For k > 3, this might be preventable if we use a different algorithm. For k > 3, if two people conspire together, only their knowing the sum of the remaining k-2 people's salaries is unavoidable. If k=100, there's still a lot of anonimity to be had in that. However, the simple algorithm that I described does not grant any such protection.
In fact, we might ask whether it's possible to design an algorithm that given k people, x of which are working together, ensures that these x people can learn absolutely nothing more than the sum of the remaining k-x salaries, which they could have obtained via a simple calculation anyway. This is, in fact, possible via a very beautiful algorithm.
This is one of the simplest problems in a field called Secure Multi-Party Computation. There's a whole research area around these sorts of algorithms where some group of untrusted parties, each having some portion of the input necessary for computing a function, compute the function without revealing their inputs to each other.
- eugene.yarovoi July 11, 2012Undefined behavior doesn't mean you get an error. Undefined behavior means the behavior can be arbitrary and undefined.
- eugene.yarovoi July 11, 2012It's undefined behavior in C. You can't modify the value of a variable multiple times between two sequence points.
- eugene.yarovoi July 10, 2012Because there's no "a" variable. After the code compiles, it looks like
cout << 0 <<" Address a "<< some_number <<endl;
cout <<*ptr<<" Address in ptr "<<ptr<<endl;
The references to "a" might be being completely removed at compile time. So then it could well be that ptr = some_number (that is &a, determined at compile time), and it could well be that *ptr = 10, but the 0's baked right into the code as a literal. There is no "a". All expressions using "a" have been rewritten with the literal constant.
- eugene.yarovoi July 10, 2012I would say that generally I would expect a stack data structure to have O(1) pop/push.
- eugene.yarovoi July 10, 2012Why the downvote? I would say my solution is probably the standard solution to this classic problem.
- eugene.yarovoi July 09, 2012That's longest palindrome. This questions asks to count the number of palindromes.
- eugene.yarovoi July 09, 2012That has a very high constant factor compared to other approaches.
- eugene.yarovoi July 09, 2012It's O(N) per row, and O(N^2) overall. I would recommend you learn about complexity and how to analyze it. These sorts of questions are all about finding solutions with optimal complexity, and if you can't evaluate the complexity of a solution, you can't compare two different possible solutions meaningfully, and then you're sort of flying blind in these types of problems.
It's hard to improve something you don't know how to measure.
So what will you do when I want to push something to stack 2 after you've completed that reverse operation? Reverse again? Seems like you might be doing a worst-case O(n) reverse for every push.
- eugene.yarovoi July 09, 2012Looks like you beat me to it. My answer explains this solution in considerably more detail.
- eugene.yarovoi July 09, 2012Here's a possible way to do it: consider the first third of the array to be devoted to elements of stack 1, the second third to stack 2, the last third to stack 3. If you run out of space devoted to any stack, double the size of the whole array.
To push on to the stack, we'll use a simple calculation like (totalArraySize * stackNumber / 3) + existingSizeOfGivenStack. To pop, we'll remove the element at (totalArraySize * stackNumber / 3) + existingSizeOfGivenStack - 1.
What's the complexity of resizing, you might ask? After resizing an array of n elements at a cost of O(n), each stack has n/3 capacity, and since that's doubled from before, previously the largest stack had n/6 elements. So there's at least n/6 free space in each stack, and it will be at least that many operations before we resize again.. So the O(n) cost of resizing is amortized over n/6 elements, for an O(1) cost per element. So pushing and popping is O(1).
The array of size n contains at least n/6 elements, so space usage is O(n) with the number of elements.
The problem is that you're not maintaining any ordering information in the second stack. If I want to pop off the last 100 elements I inserted into stack 2, how will stack 2 know which ones they were? They were definitely some of the ones on the left and some of the ones on the right, but in what order and how many from each side? You've lost that information.
- eugene.yarovoi July 09, 2012It's undefined behavior. See the answer that mentions sequence points.
- eugene.yarovoi July 09, 2012It's all good. copy_array(a,b,length); should be copy_array(a,b,length-1); to avoid going out of bounds. With that change and changing the "while" to "if", this solution works fine and is equivalent to a bunch of other solutions on this page.
- eugene.yarovoi July 08, 2012Your logic's also incorrect, now that I take a closer look. I think you meant "if" instead of "while". So if you had the "if", then your solution wouldn't have loops.
- eugene.yarovoi July 08, 2012Uh...
void copy_array(int q[], int r[] ,int i)
{
while(i >= 0)
{
r[i]=q[i];
i--;
copy_array(q,r,i);
}
While statements are also considered loops.
- eugene.yarovoi July 08, 2012I'm saying that if the copy constructors and assignment operations are protected, the subclasses could then contain code like BaseClass b = new BaseClass(); BaseClass b2 = b;
Reading the problem description, this should not be allowed, it seems. That's why I think they should be private. Yes, that does make the subclasses uncopiable unless they implement their own copy constructor and assignment operators.
I spy a loop...
- eugene.yarovoi July 08, 2012I would think that you'd be fine doing a binary search.
- eugene.yarovoi July 08, 2012It's recursion, but compile-time recursion. Read my first comment on this post.
- eugene.yarovoi July 08, 2012True, memcpy has nothing to do with strings. What I meant is that memcpy is still a standard function that is sometimes used for copying strings, so I would interpret this question as saying that this is not allowed. Memcpy is a fine solution if it's allowed.
Just seems too easy if you allow something like that, ya know?
Well that one isn't a big deal. Can easily be repaired by writing four printf statements.
- eugene.yarovoi July 08, 2012Why not? If a base class is uncopiable, it makes sense for derived classes to also be so, because a derived class includes the superclass in some sense. Also, you can still override the = operator for subclasses and define code for copying the objects, where appropriate. The issue I'm seeing is that if you make the copy constructors protected, you're introducing the possibility that someone implementing a subclass will create instances of the base class and copy them, thus bypassing the uncopiable rule.
- eugene.yarovoi July 08, 2012You and your template metaprogramming :)
- eugene.yarovoi July 08, 2012This is an N^2 algo. You can get O(NlogN). Also, I think you meant rowSum[col] += Array2D[row][col], not rowSum[col] = Array2D[row][col]
- eugene.yarovoi July 08, 2012@OhMyGod: No. The sum of random variables distributed uniformly at random is not itself distributed uniformly at random (by the central limit theorem).
- eugene.yarovoi July 08, 2012@sachin: Yes, you're right. I forgot to consider that one special case. All we need to do to fix this is add the extra check you're proposing. Either that, or we can prefix 0 to the sum array before we run the algorithm that involves the HashMap (that's the easiest way to do it, in my opinion).
- eugene.yarovoi July 08, 2012That doesn't seem like a very solid proof. After all, this algorithm will generate new strings (the results of the concatenation) that might not have been obtained with another approach in the first place.
- eugene.yarovoi July 08, 2012@Pavan: No. Immutable static variables are thread safe, and enums can be thought of as immutable static variables.
- eugene.yarovoi July 08, 2012Aside from actually cloning the array via something like a malloc and a memcpy? Not that I can think of at this moment.
- eugene.yarovoi July 08, 2012Interesting approach. I see you used a frequency counter. I hadn't thought of that. I was storing the index of the most recent occurrence of each element instead.
- eugene.yarovoi July 08, 2012Think of it this way: all sizeof operations are resolved to a constant at compile time. After compilation, the function call inside the sizeof doesn't exist.
- eugene.yarovoi July 08, 2012I don't consider there to be a firm distinction between "programming language" and "scripting language", but these terms don't have rigid definitions, so different people perceive them differently.
I might add that languages are often called "scripting languages" when they're domain specific. BASH scripting is mostly about doing system-related stuff on your computer, though it can execute more general logic too. But sometimes people refer to things as "scripting languages" even though they're general purpose. Python is one example, though people refer to it as a programming language too.
In my view that probably is the factor that comes closest to explaining whether something will be called a "scripting language" or a "programming language" - was it designed for a specific domain (controlling actions in a video game, web development (Python gets a lot of its scripting rap from that), text parsing (like Perl originally was)?
If they're protected, the subclass will be able to make copies of instances of the base class.
- eugene.yarovoi July 08, 2012I think it's OK to make them private too, right? I mean, it'll prevent the subclasses from being able to have a default = operator and copy constructor, but that makes sense: if a class is uncopiable, its subclasses should be too.
- eugene.yarovoi July 08, 2012That's true, this is O(n^2), for instance, in the case of a degenerate tree that becomes a linked list. However, there's a fairly simple fix. When searching until you find a parent whose depth is known, keep track of all previously unseen nodes in the path, and then backtrack through them and assign their depths. For instance, if you see 5 -> 8 -> 13 -> 45 -> 3 and that's where it stops because the depth of 3 is known to be, let's say for example, 2, you should store the sequence 5 -> 8 -> 13 -> 45 -> 3 somewhere and then backtrack, saying 45 is depth 3, 13 is depth 4, 8 is depth 5, 5 is depth 6. That way you can see that each node is traversed exactly once and the algo is O(N).
- eugene.yarovoi July 07, 2012This requires you to actually build nodes that have storage for child pointers, which uses more space than a more optimized solution. This also requires a hashtable, which significantly increases the constant factor over an array-only solution. It also means you get O(N) expected, not deterministic time.
You can solve this in O(n) deterministic time, and with a much lower constant factor too, by just using a couple arrays.
For those not familiar with this technique: this is a technique specific to C++. Basically, the code for the copying will be produced at compile time and be akin to having written dest[0] = src[0]; dest[1] = src[1]; ... dest[n] = src[n]; except that the compiler will automatically generate the code for you. This will 1) make the code size large if the string to be copied is large and 2) require you to know, like shondik said, the size of the string to be copied at compile time. As such it's not a very general solution.
- eugene.yarovoi July 07, 2012I would note, of course, that there are serious limitations to this. Many implementations of C don't support a huge amount of call depth in the stack, so you might have a stack overflow for large strings. Recursion also uses a whole bunch of extra space.
- eugene.yarovoi July 07, 2012
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 can't tell exactly what you're proposing. That doesn't sound like dynamic programming; it sounds like backtracking.
- eugene.yarovoi July 14, 2012Success on this problem probably depends on how exactly you go about using this backtracking.