## eugene.yarovoi

BAN USERThe cycle length could be exponential. Let me illustrate with an example. Consider a sequence p1p2p3...p_n, where each p_k represents the sequence of numbers 1 2 ... the k-th smallest prime. A sample sequence, for example, is 1 2 1 2 3 1 2 3 4 5 1 2 3 4 5 6 7. Now, consider the following permutation: for each sequence p_k, map index 1 to index 2, 2 to 3, ..., k to 1. Do this independently for each p_k. So the sample sequence would become 2 1 3 1 2 5 1 2 3 4 7 1 2 3 4 5 6. The next permutation after that would be 1 2 2 3 1 4 5 1 2 3 6 7 1 2 3 4 5. If you look at the chain of permutations, you can see that the original permutation will recur after len(p1) * len(p2) * len(p3) *.. *len(p_n) transformations. However, the length of the input is only len (p1) + len (p2) + len(p3) +.. + len (p_n).

_

If instead of picking the first primes we just picked any d primes close to a value r, we'd have close to r^d cycle length and r*d input size. r^d/ (r*d) = r^(d-1) / d. Let's say we just set r = d, then the ratio of time to size is r^(r-2), which is actually even slightly superexponential O(2^(theta(nlogn)))

GetStringUTFChars would call built-in String methods though. So if that's allowed, why use JNI at all? Why not StringBuffer s = new StringBuffer(inputString); and then operations on that?

- eugene.yarovoi May 04, 2012The problem of finding a minimum set of palindromes can be reduced to finding a shortest path on a graph, as I explain in the comments to one of the responses near the top.

- eugene.yarovoi May 04, 2012So by your own logic then, the best answer to "How many stacks can a process have" would be something like "as many as it has threads".

- eugene.yarovoi April 23, 2012Is it that interesting? We're going to have to buffer characters anyway so that we can match a sequence of characters to the sequence in reverse, so once we've buffered the characters into an array that we have random access to, it's just scanning from both the front and back for the max sequence. It's a little more interesting if we don't have enough space to do that and have to make multiple passes, but it's still not all that exciting.

- eugene.yarovoi April 23, 2012No, I think that's cheating. I do think the intent of the problem is probably to print every player exactly once. The correct answer is to have read the wiki article on "tournament graphs". There is a simple O(N^2) algo that will solve this problem. It uses an inductive approach: first construct a path for just 2 players, then incorporate a third player into that path (you can show there's always a way to do that), then incorporate a fourth...but all the players can be unique.

- eugene.yarovoi April 23, 2012But that would only work if victories are transitive. Apparently, there exists a method to do it even if they're not (see wiki on "tournament graphs").

- eugene.yarovoi April 23, 2012Apparently there always exists an ordering that can be discovered in P-time even if there are cycles. I just found out about this too. Read the wiki article on tournament graphs.

- eugene.yarovoi April 23, 2012Uh...insertion sort? That doesn't make any sense to me. Can you explain?

- eugene.yarovoi April 23, 2012Interesting. I had not heard of tournament graphs before and just ignored the term because I thought you used it only because we were discussing a tournament. I see now that it is fairly trivial to prove (by induction) that every tournament graph has a Hamiltonian path, and that an O(N^2) algorithm for this task can be obtained directly from this proof.

- eugene.yarovoi April 23, 2012Do you have to use all of those, or what?

- eugene.yarovoi April 23, 2012Agreed that many of these things should be clarified first.

- eugene.yarovoi April 22, 2012You'd have to be careful to maintain a state variable indicating which part of the string you're currently matching and to return false if you ever see an unexpected state. You wouldn't want something like XXXXBBBXXXCX to match.

- eugene.yarovoi April 22, 2012I assume the answer's no. Otherwise, we claim that p = "" and q = "" and we return true. So the approach of keeping a stack and then keeping track of which section of the string we're on is probably the proper approach.

- eugene.yarovoi April 22, 2012This is true in the most general case, and Hamiltonian path is NP-complete. There are no known sub-exponential time algorithms that detect Hamiltonian paths exactly.

However, if the orderings are transitive -- in other words, victories accurately reflect the skill of the players in such a way that if A beat B and B beat C, then A beat C for all triplets A, B, C, then this problem simplifies to a topological sort, an algorithm that can be done in time proportional to the number of edges. There are N(N-1)/2 edges if there are N players, and so the time would be O(N^2).

(At least) two problems here:

_

1. This is a greedy approach, and greedy approaches will generally be incorrect for this problem.

2. The complexity is cubic.

Perhaps worth noting that power and % operations for powers of two can be accomplished significantly more efficiently through bit shifting.

- eugene.yarovoi April 21, 2012Must we break it into the minimum number of palindromes? That sounds challenging.

- eugene.yarovoi April 19, 2012I'm going to give you the same objection as I've given others: the cycle length can be exponential with the number of digits. Even for 100 digits your program would take pretty close to forever. Can you make it scale?

- eugene.yarovoi April 19, 2012@Kumar: It's a tradeoff between how quickly you want the system to respond to changes vs. how much processing power you want to spend waiting. Here, the response is as fast as possible in exchange for full processing power being used.

- eugene.yarovoi April 18, 2012A mutex can often allow different objects to run the same code concurrently. There can therefore less needless blocking. A mutex requires more space, though, because a binary mutex would be very dangerous. If you had a segment like lock (x) { f(x); someThingElse(x); } and unbeknownst to you, f also locks x, f would set x.lockBit to 0 after leaving f(x), ruining the locking guarantee of the outer lock statement. Considering that you might not even have access to the source of f, this would be a problem. Some kind of lock counting or thread owner tracking is thus necessary, and more space is needed for that.

- eugene.yarovoi April 10, 2012By and large, though, I totally agree. Most tech companies will accept either. For some place like Intel or Microsoft if you're going to be on the Windows team, you might have to know at least C if not C++.

There are absolutely places where you will get rejected for not knowing C++, and there also (perhaps fewer) places where you will absolutely get rejected for not knowing Java. But most of the really big tech companies are not looking for specifics, but just for coding talent and algorithmic knowledge in general.

I would also mention that financial firms that have real-time trading / analysis systems that run on C++ (and that's a great many of them!) often want you to have C++ down cold, glacier cold. They often view you as a "C++ Developer" specifically, if that's the kind of role they've decided to put you in.

- eugene.yarovoi April 10, 2012The piracy doesn't surprise me. I've seen people ask other people for copies of the book right here in the CareerCup chat box.

- eugene.yarovoi April 10, 2012There are lots of ways to solve this problem. If M is really small, like single digits small, the best approach is probably to take each element in one list and check it against each element in the second list. For cases (ii) and (iii), prepare a hashset of the smaller list, and use that to see which elements of the larger list are in the smaller list.

- eugene.yarovoi April 08, 2012I would say you had a legitimate response. You could have used more reasons, of course.

- eugene.yarovoi April 08, 2012Java doesn't have multiple inheritance, that's right.

- eugene.yarovoi April 02, 2012@yossee: That's the correct analysis.

O(n) isn't going to be achievable because there's O(m*n) bits of data to look at. O(m*n) complexity is the lowest you can hope for, so O(n*mlogm) is really pretty close to optimal.

Right. Static variables declared in a function are essentially globals that are lexically scoped to be useable only within a particular function.

- eugene.yarovoi March 31, 2012I once drew a lolcat to explain one of the differences. I drew a picture with an arrow-shaped sign that said "mouse problem" on it pointing to a mouse hole , and then a kitty standing next to the mouse hole chewing on a mouse. The caption said "I can haz poynturs to akxes ur inturnlz?" My interviewer was not from the U.S., however, and did not know what a lolcat was. It was very sad.

- eugene.yarovoi March 31, 2012Although when you use hashing, you're looking at some of the data more than once too...whenever you hash a node for lookup in the table, you're comparing it to hashes of nodes already in that bucket. So you can end up looking at the hashes of the nodes already in a bucket multiple times, which is indirectly a way of making multiple passes over data. It's not really any better than copying the data over to an array and doing a backwards traversal to find the point of divergence, like recommended in the other solution.

- eugene.yarovoi March 30, 2012I guess you're technically not traversing the linked lists twice in this approach, but you're traversing the data twice.

- eugene.yarovoi March 30, 2012Oh, I see. Right, this only works if you assume that the other political parties only have 1 candidate per party.

- eugene.yarovoi March 26, 2012This question did seem suspicious to me. There seem to be an increasing number of people that think that they should go ahead and post their homework questions here.

- eugene.yarovoi March 26, 2012No, that's not it. C will create a global string "abc" and give c a pointer to it.

- eugene.yarovoi March 26, 2012The exact numbering of the question may depend on which edition you have.

- eugene.yarovoi March 25, 2012Agreed. I hardly ever read code replies. If you want to post code, post it following an explanation of the algorithm, and with comments in the code.

- eugene.yarovoi March 25, 2012I think the implicit void conversion does work in plain old C, and doesn't work in C++.

- eugene.yarovoi March 25, 2012Using the weighted median is wrong. Consider

2 . . . . . . . . 1

The optimal choice is to set the meeting point where the 2 people are, not anywhere in between the 2 and 1.

If you wanted to list based on prefixes, you pretty much need a prefix tree. A hash table won't really work. Another possibility is just a sorted array, of course, if the files are re-indexed relatively infrequently. I'd probably opt for a prefix tree.

- eugene.yarovoi February 25, 2012This is the difference between HashMap and Hashtable in Java. But when used as a general term in computing, the terms can be synonymous.

- eugene.yarovoi February 25, 2012It's not necessary to update the pointer. Keep the same pointer, move the data (the values held by the nodes) instead.

- eugene.yarovoi February 21, 2012Using recursion involves using extra space.

- eugene.yarovoi February 21, 2012By "Window search", did you take the meaning to be the search feature that searches your files on Windows? I'm somehow skeptical that something like that would use map reduce.

- eugene.yarovoi February 21, 2012It all depends on whether you count the bits from the left or from the right and whether you start counting with 0 or 1.

- eugene.yarovoi February 20, 2012No, nobody's going to do your homework assignment / work assignment for you. I doubt this is an interview question.

- eugene.yarovoi February 20, 2012How large is N? I remember a coding competition where you had to answer a similar problem even for very large N (e.g. 10^9). So clearly there exists some very fast method. However, this can probably be solved using dynamic programming and the like for somewhat smaller N.

- eugene.yarovoi February 19, 2012Two problems: 1) This algorithm isn't optimal; 2) This algorithm could have very high complexity if time is not discretized into a small number of chunks. I think it's better to make no such assumptions.

There's a linear-time (NlogN if you have to sort) time algorithm for solving this problem with just real-number timestamps.

"Loosely coupled inheritance - interfaces - are considered a much better option these days."

That depends on whom you ask. I wouldn't agree, and neither would the people that made Python, Scala, etc. It's completely true that there are some issues with multiple inheritance. It's not just about tightly-coupled systems, but also about the greatly increasing possibility of name conflicts, etc. There can (depending on implementation) be issues like the dreaded diamond problem, etc.

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.

Open Chat in New Window

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.

- eugene.yarovoi May 05, 2012