CareerCup

I think they forgot to put the stars on struct node m . 2 was probably the intended answer.

No, it's not. In 3, you would free the memory pointed to by both n and m before dereferencing it.

You definitely can't. Rabin Karp is for finding substrings in strings. This is a different problem. We're being asked to find a "substring" that contains at least one of each of a set of strings, in any order. Completely different.

Same question posted not 5 days ago: www . careercup . com / question?id=14062676

Seems that way to me too, unless C++ has some sort of trickery for doing it. Nothing's coming to mind right now.

Generally most classes that are logically thought of as being abstract have one or more abstract methods, so this isn't a huge problem in most situations.

Right, that is the N^2 solution. No asymptotically better solution is known.

No, consider that having a complete graph on n-1 vertices and one disconnected vertex yields (n-1)(n-2)/2 edges.

You can only wrap an array in a structure like that if the size of the array is known at compile time, though, so this isn't a very general solution.

@shondik: you need 4 bits per square. The color of the piece is in combination with the other attributes. In other words, the distinct possibilities are (king, black), (king, white), (queen, black), (queen, white);, etc.

I don't think there's a proof that it's impossible, but no subquadratic algorithm is known for general inputs.

If-statements can be slow, but modulo is a particularly slow arithmetic operation. Actually, now that I think about it, if I really had to optimize, I'd try this and measure to see if it's faster (I think it should be on most systems):

const int MODULUS = 5;
value = 2*value + new_bit;
if (value >= MODULUS)
{ 
    value -= MODULUS;
}

Still general and maintainable, though now we're more tied to the fact that the representation is base 2 than before.

The if-statement could be optimized away with some bit tricks too.

Why is it always better? The non-automaton solution is one line of code.

Yeah, it seems correct with that last revision. It's actually logically equivalent, though implemented differently, to my solution given that change. One question: why bother with RevBiasedRandom()? Why not use 1 - BiasedRandom() in the one place that you call it?

It's not wrong at all. The probability of getting 1 *on the first loop* is p*(1-p), yes. The probability of getting 0 *on the first loop* is also p*(1-p). Brant's argument doesn't apply because I don't generate new random numbers between the two lines of code that have returns. Consider the following thought experiment: say I had a rand3() method that returned an integer uniformly at random between 0 and 2 inclusive. If I then wrote code like int x = rand3(); if (x== 0) { return 2; } if (x== 1) { return 4; } if (x == 2) { return 6; } would you then argue that 4 or 6 are any less likely to be returned than 2? Of course not, since the conditions are disjoint.

Making all the constructors protected is one way to prevent people from instantiating the class without subclassing it first. Of course there have to be no factory static functions, etc. too.

Just keep what the current number is modulo 5, and apply with each element:
numMod5 = (numMod5*2 + bitThatJustCameIn) % 5

Sure, there are issues. So in the end of step 4), you stop incrementing the start pointer once you hit something that's in the trie? The problem is that what if it's a searchword, but there are still occurrences of the searchword after the occurrence that you found? For example, consider x x a x a x b x b x c x a b x where x are not searchwords and a, b, and c are. You find a valid subarray at backpointer = 2, frontpointer = 10. Now you scan forward and you see a at index 12.

What would your algo do here? It would scan until it finds the b at index 6, right? But it should keep scanning until it finds the b at index 8. That's what I mean when I say there can still be occurrences of a searchword after the one you found.

This is the naive solution. Input sizes have been chosen to ensure that O(N^2) solutions time out. There's a linear time solution, as well as an O(NlogN) solution.

Do you just want to ensure that no changes are made, or do you want changes to be made but not reflected in the calling function? If the latter, you must clone because it's clear that 2 copies of the data need to exist simultaneously: one in the called function and one in the calling function. If the former, you can say that the array is const.

Not correct. I immediately know it's wrong by the simple fact that you call rand5() only once. Think about it. If there are only 5 possible inputs to your program (the 5 possible outcomes of rand()%5), how can there be all 7 possible outputs? Everything else is deterministic. In fact, see the comments to my post for an explanation of why every correct solution can have no strict upper bound on the number of times random5() may need to be called (but can still have a constant number of calls in the expectation).

That would work. It would just be less efficient because we'd have an expectation of 25/7 rolls instead of 25/21 rolls. it would be a constant factor less efficient.

Just keep track of the 2 largest. Compare elements to the smaller of the two, and if elements are bigger, check whether they should become the new second largest or the new largest. Some of the solutions on this page implement this approach.

Similar, yes. The difference is that I avoid the extra binary search.

Sort the intervals by lower bound, and for each interval, just check if the next interval begins before the current one ends (return false if that's true anywhere). Data structure? Make an interval a struct of two ints or float or whatever they are, and use an array.

I got the impression nodes would actually be labeled 1 through N. I admit the question was unclear.

Radix sort will work, and for 10 bits, it's still quite fast. But why use something like 10 passes when you can use 1?

@Victor: bitset won't work. You actually need the count of each element.

@ashot madatyan: why 1023? You want to have a special case for the 1024th one where we don't count it and fill up any space left at the end with it? It would use less than 0.1% less space but add implementation complexity.

Using the 2 pointers is better, agreed. I didn't bother because either way it's NlogN.

Agreed that it's the LCM of the cycle lengths. That is the efficient way to solve this. The originally proposed method, which was to go through all the permutations until we see the same permutation we started with, would be very inefficient.

What I would say is that I'm looking for a job change because I want more responsibility and the opportunity to grow more. I'd say I've always been open to both dev and test positions and it just so happens I've been in dev until now. In your case, sounds like it's probably the truth, too. You could also say that you want the opportunity to try out different things.

Oh...I interpreted all this code to be part of a method, with abc being a local variable.

The truth is usually a good place to start for these sorts of questions. From your question, it sounds like you honestly desire to switch to testing, after all.

So...why do you really want to switch to testing?

You could store the numbers precisely if you wanted to, and it wouldn't be all so bad. If your incoming numbers are d digits long, you would need d*logN bits for the exact sum, and another logN for the counter, so O(d*logN) total space. Calculation time would be at worst something like the square of that (d^2*(logN)^2), so still very reasonable.

There are no sorting approaches that require only O(log n) time.

For just 2 numbers?

The question asks for the first subarray, not the longest subarray. But that problem too can be solved using the same techniques.

@salvo4u: It's not wrong; sometimes, I use it too. There are different ways to implement memorization and the best way depends on the structure of your problem. Sometimes an array is best; a map might be better when the array would be very sparse. A map is really more general. It's just that using memorization in this problem is not necessary.

Yep. And you're usually asked to do this as efficiently as you can, given that the number of pieces could be large.

The cost of raising or lowering land IS significant. In fact, the length of the path doesn't matter, only the cost of raising and lowering the land as needed to make the path valid.

I suppose my question would then be why your graph has more than O(M*N) edges. I'll have to dig into your solution to find out.

I don't imagine there are many scenarios where you're asked to solve a puzzle just by tagging the pieces before they're scrambled. This sounds like a classic interview question where you're asked to make this reconstruction from the pixels, provided that every edge is duplicated so that you can figure out how to fit the pieces together.

Not true. Consider a counterexample where you have a 9x9 square formed from a 6x6 and 5 3x3s.

Hmmm...well, I guess that makes sense. If you want to do it using pure recursion + memorization...still, check out some of the other solutions, they do it much more simply. You also could have just used long p = power (power(a, b / 2), 2), and there would have been no need for DP.

I just saw Hashmaps and DP and stopped right there.

For just 4 elements, a heap might be a bit much. Just use an array of size 4 of the 4 greatest elements seen so far, compare elements to the low end of this "greatest 4" array as you iterate, and insert into the appropriate place in the "greatest 4" array when an element is bigger than the low end of the "greatest 4" array.

Why is this the best a Dijkstra's algorithm can achieve? I believe O(matrix_size * (elevation_of_lake - elevation_of_dam)) should be achievable. By matrix size, you mean M*N?

Yes, good mention of the memory leak there.

I'm afraid the logic makes no sense at all. Why would you begin by doing a binary search from between indexes arr[0]-1 and arr[0]+1? Those are not even guaranteed to be in bounds! You've probably misunderstood the question.

Besides, suppose it were correct. By what you say, the algorithm's NlogN, which means it's considerably worse than simply checking every single element in the array for the element you want to find.

In some languages, like Java, you can extend the Thread class and put whatever instance variables you want in the extending class. When you then instantiate this class, you'll create threads that each have their own copies of these instance variables. This kind of thing is useful when you need each thread to have some kind of functionality that involves keeping track of internal state, but the desired functionality logically has no dependency between threads. An example would be a random number generator. Using a per-thread random number generator will remove any kind of lock contention that might otherwise have existed.