eugene.yarovoi
BAN USERAssuming the list has at least 5 nodes: advance a pointer (call it frontRunner) 5 times. Now create a pointer to the beginning of the linked list (call it result). Now, advance both pointers one-by-one until frontRunner== NULL. e.g.:
Node* frontRunner = list->head;
const int numFromBack = 5;
for (int i=0; i < numFromBack; i++)
{
frontRunner = frontRunner->next;
}
Node* result = list->head;
while (frontRunner)
{
frontRunner = frontRunner->next;
result = result->next;
}
return result;
To be completely honest, I'm not exactly sure what you're talking about, but in any case, I certainly did not mean to imply that there aren't other ways of doing I/O and the like. I'm just saying that this is one way you could decide to use threads.
I think the question is significantly more basic than you take it to be. I think it's asking why you would use threads in a typical program, not what advantages threads have over special non-blocking I/O, etc.
One thread can wait for input while the other does background work. Without threads, you would not be fully utilizing the system because no background work would be getting done while you're waiting for input, blocked on disk I/O, etc.
- eugene.yarovoi December 30, 2011@Manan: I don't see how you can do it in one pass.
- eugene.yarovoi December 29, 2011That technically does make those strings implicit global variables, but I think this is probably what your interviewer wanted.
- eugene.yarovoi December 29, 2011char * test(int v)
{
switch(v)
{
case 1: return "Case 1";
case 2: return "Case 2";
case 3: return "Case 3";
default: return "Default";
}
}
Pick an index in the in-order traversal sequence as the root. Then, generate all possible left subtrees whose in-order traversal is exactly all of the numbers before the root in the sequence and all possible right subtrees whose in-order traversal is the numbers after the root (do this recursively). All the possible trees with the chosen root are every combination of a right subtree and a left subtree. Do this for every possible index as the root, and you have every possible tree.
If you want to count the number:
Trees(N) = Trees (N-1)*Trees(0) + Trees (N-2)*Trees(1) + ... + Trees(0)*Trees(N-1)
Trees(0) = 1
Trees(1) = 1
This can be evaluated using dynamic programming.
I'll give a counter example. How about a String constructed via a char[] through the String (char[] c) constructor?
- eugene.yarovoi December 23, 2011@kartikaditya: No. Security is a legitimate concern here. If a field is immutable and final, there is no way to change it without having the proper privileges, barring a bug in the JVM. There have actually been significant security exploits in Java that worked with the idea of time-of-check vs. time-of-use vulnerabilities, where the attacker would create a security-restricted object (think Socket, file stream, etc.) using some mutable object, the security manager would check that the proper permissions exist to create the object with the specified input, and then the user would maliciously alter the input to affect the internals of the object in an unauthorized way.
That doesn't necessarily mean String should be immutable for that reason alone. Certainly, mutable objects are necessary sometimes. To write secure code in situations where you're dealing with mutable objects, a deep copy of the object should be created, and any data validation checks should be run only on this internal, defensive copy. (Even if the security manager checks for valid data, if the checks are run on the original, not-copied input, an exploit is possible where the attacker would use another thread to modify the input right after it passes the security check and right before it is actually used in the constructor of the restricted object.)
I would say that String was mostly made immutable to make programming errors, both those related to security and those related to program correctness, less likely. Since we generally think of strings as value types and Java doesn't have value types, Java makes strings immutable because immutable value types behave in the same way as immutable reference types (and immutable reference types can have better performance than immutable value types, too).
Good question. I do a lot of interview questions, and I still have no idea what that would be.
- eugene.yarovoi December 23, 2011@sai: Nope. It's what I said it is. By my formula, there are 3 ways to go down 3 steps: (2, 1), (1, 2), and (1, 1, 1). By your formula, it would be 5 ways, which is clearly wrong.
- eugene.yarovoi December 23, 2011Are these patterns O(1) in size? At the moment, I can only think of an algorithm that O(ND), where the pattern is length D.
- eugene.yarovoi December 20, 2011While I have not verified the correctness of your code, I can say I would consider this the right approach to this problem, at least after asking the interviewer some questions about the data (e.g. "is there anything special about b, for example, is it always a power of 2?")
- eugene.yarovoi December 20, 2011F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 2
Alright, here's a formal proof. Suppose you want to find the maximum zigzag subsequence in an array of length n. Consider this with the idea that you've already started accumulating a zig-zag subsequence before and now you have a specific direction you need to go in. Let's say it's up, without loss of generality.
Now, the elements you can choose from for your next subsequence element are all the elements that are greater than your current element and to the right in the array you're inspecting. Consider the next such element (the element that is greater than your current element and involves skipping over the fewest number of elements). Examine the upward run that starts from that element (by upward run, I mean the run of consecutive increasing elements). That could be just that element alone, or could include any number of consecutive elements. My goal is to prove that taking the highest element in that run is necessarily optimal.
This can be done in 2 parts. 1) Prove that taking the largest element in the run is at least as good as taking any of the other elements in the run; and 2) prove that taking the largest element in the run is at least as good as not taking any element at all in the run.
Part 1: Suppose you take a non-largest element in the run. You can't take any other elements in the run, because you now need to go down. But your ability to go down (the number of entries in the array that come after the run that qualify as "down") can only increase if you take the largest element in the run. So taking the largest element in the run is always at least as good (because it leaves you with all your previous options and can give you more).
Part 2: Suppose you don't take any element in the run, not even the last element, call it P for "peak". That implies that the next element you take into your subsequence is some element later in the input than P (or if you reach the end of the array, that's clearly suboptimal too). Consider this element you end up taking. By the logic of part 1, this element would have to have a value larger than the value of P to not be suboptimal. Let's call it P'. But we know P is followed immediately by an element with lower value, which would also have a lower value than P' (since P' > P). So if we include all 3 of the elements P, element after P, and P', this is clearly a more optimal situation. We'll still be heading down after including all 3 of those elements, so this situation is exactly identical to choosing P' directly except that it includes 2 additional elements. Choosing P' as the next element for the subsequence is thus guaranteed to be worse than choosing P.
Therefore, it is optimal to choose the peak point as the next element for the subsequence.
No...you're allowed to skip elements to achieve a larger subsequence than what might be possible with a contiguous subsequence alone. It's in the problem statement.
- eugene.yarovoi December 16, 2011Here's a straightforward DP recurrence:
F(n, k) = F(n, k-1) + F (n-1, k-1) + F(n-2, k-1) + ... + F (0, k-1) = F(n-1, k) + F(n, k-1).
This equation allows a quadratic time, linear space (if you're clever) solution.
I would think "increasing and then decreasing" means "strictly increasing and then decreasing". So there wouldn't be any repeated integers.
- eugene.yarovoi December 12, 2011It's possible. Check out some of the answers or read about "Dutch National Flag" sorting.
- eugene.yarovoi December 12, 2011This does seem like a very difficult problem, doesn't it...
- eugene.yarovoi December 12, 2011That can be a reason to pass something by reference, but that's not the main reason why in this case. Read the other replies.
- eugene.yarovoi December 12, 2011I think the solution you're probably looking for that's in this spirit is to map each number N to the N-th prime number and multiply them all together.
so {2, 5, 1} would become second prime * fifth prime * first prime = 3 * 11 * 2 = 66
This would equal what you'd get with {1, 5, 2} for obvious reasons. Because of the fundamental theorem of arithmetic (every number has a unique factorization into primes), the product you get is actually a signature unique to the array you inspected.
Of course, you'd have to use something like BigInteger because a regular int or long would overflow very, very quickly for this solution. And this solution would sure get slow. You'd need something like FFT to even get N*(logN)^2.
It's possible to come up with very simple and fast randomized algorithms for this problem, too, that can get the answer right with very, very high probability in something like O(N logN) time.
I would consider these solutions to be probably invalid because the reason the constraint to avoid sorting is probably being given is because O(N) extra space is too much.
- eugene.yarovoi December 12, 2011"Nothing is impossible in Java."
Alas, plenty of things are, in fact, impossible in Java, such as placing things at specific memory addresses, etc.
It's not a design fault if D needs something like that. It's a language fault for not giving programmers something they need. There's nothing inherently wrong with wanting to inherit from two types. It was removed because it caused difficulties in C++ and was used somewhat rarely anyway.
Let's say you didn't pass in the address. What would you pass in? If you passed in nothing, there'd be no way for you to know about the object. If you passed in a copy of the object itself, then you'd have to know how to make a copy...so then writing code to copy the object would presuppose that you know how to copy the object.
- eugene.yarovoi December 11, 2011You mean:
if(a[m-1]<a[m]) && (a[m]>a[m+1]))
return a[m];
on that first condition
This answer is a little incomplete. I'd like to see some mention of the String[] argument with respect to command line arguments.
- eugene.yarovoi December 11, 2011You would either use static factory functions that know about this pool and make the constructor private, or you would override the new operator.
- eugene.yarovoi December 05, 2011http : // en. wikipedia. org / wiki / Banker%27s_algorithm
- eugene.yarovoi December 05, 2011Seems to be correct for positive numbers. You haven't taken negatives into account, though. No one said the int's unsigned...
- eugene.yarovoi December 05, 2011I see some bugs. What if N = 0? Shouldn't the answer be 1? What if the number's negative?
- eugene.yarovoi December 05, 2011The stuffs?
Like a virtual table, and all those things?
I haven't looked over your code, but good job on identifying the ambiguity.
- eugene.yarovoi December 05, 2011This is very tedious. On an interview, the interviewer is looking to test your carefulness, etc.
- eugene.yarovoi December 05, 2011Recursively traverse the tree. When you recurse, pass a variable indicating the current level + 1. So you'd start with level 0, and when you recurse, you'd pass 1 for the level, when those calls recurse you'd pass 2, etc. Then use that number as an index into an array of sets of nodes and add the node to the set that you get (which corresponds to the index, the node's level). Finally, look at each set one at a time (each set corresponds to a level and has all the nodes from that level) and print everything in the set.
- eugene.yarovoi December 05, 2011We could use Dijkstra's, but simpler algorithms will suffice. There's also a more efficient algo based on doing a BFS from both endpoints and looking at the set intersection of the nodes that result.
- eugene.yarovoi December 05, 2011@Sushant: Suppose there is a vertex "v" that is distance n/2 from both endpoints, e1 and e2. So, there is a path from e1 to e2, namely, e1 -> v -> e2 that has length bounded by n/2 + n/2 = n.
- eugene.yarovoi December 05, 2011A greedy algorithm is optimal here. I suppose a good answer would include a proof that this is so.
- eugene.yarovoi December 05, 2011What a loaded question. I suppose I would say that it's because Linux-based distributions tend to be open-source, which means the community can find bugs (which, if exploitable, are security vulnerabilities) more easily.
- eugene.yarovoi December 05, 2011@asm: and then you'd check for primality on each number?
- eugene.yarovoi December 02, 2011Isn't hashing the simpler approach? Essentially, we are asking to compare two sets of strings, each set having size O(n).
- eugene.yarovoi November 24, 2011Sounds like this would have O(n^2) runtime.
- eugene.yarovoi November 24, 2011Using something like Rabin-Karp hashing you can do it in O(n) time even for any k. But for k = 3 you don't even need anything fancy like that to get O(n) time using hashing. See my solution.
- eugene.yarovoi November 24, 2011@Anonymous (First): define "huge space requirements". We know the substrings to be of length 3. I can't see it being all that bad. For one, 3 ASCII characters can be encoded as an integer. Is asking to hash O(n) integers too much? Most efficient solutions are going to require at least asymptotically that much space. Perhaps your point was about the O(1)-ness of the operation. I suppose I should say that with this solution we are getting only expected O(n) time, not guaranteed.
- eugene.yarovoi November 24, 2011We know the numbers are 1-N. At least that's how I understood the question. The trick is to count which of the 2^N subsets of these numbers sum to a prime number. The sum (k) is bounded by N(N+1)/2. x is bounded by N
- eugene.yarovoi November 22, 2011Which can be solved by DP. (Not that I've looked over the proposed DP solution, I'm saying just in principle...)
- eugene.yarovoi November 22, 2011+1: A remarkably simple yet clever algorithm.
- eugene.yarovoi November 22, 2011Ok, here we go. Use dynamic programming with the following relation:
F(x, k) =
x == A.length && isPrime(k): 1
x == A.length && !isPrime(k): 0
else: F(x+1, k+A[x]) + F(x+1, k)
The answer is F (0,0).
The interpretation of this is as follows: F(x,k) represents the number of ways to sum up to a prime if the sum so far is k and we are currently considering whether or not to include the x-th element. This number is the sum of the number of ways to get a prime when we include and when we don't include the x-th number in the sum. When there is no x-th number, there are no more choices to be made and the answer depends on whether the sum so far is a prime.
The time and space complexity are O(N^3) because k can be up to N^2/2 and x can be up to N. So there are O(N^3) states and O(1) work to be done per state, for a total time complexity of O(N^3). A trivial algorithm can precompute a boolean array representing which of the possible O(N^2) sums are prime for use in the base cases of the DP algorithm in O(N^3) time or less.
Definitions are whatever we make them out to be, but to me "scraping" suggests gathering only a small subset of the information on a page (say, all phone numbers in a huge set of pages containing tons of other information), whereas "crawling" suggests some kind of comprehensive indexing.
Maybe some people define the difference by saying "scraping" is parsing the info of a page and "crawling" is the act of parsing the links of a page and following them to find more pages.
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
This is the first time I've seen an acronym for "write a code". It's particularly interesting because "write a code" is grammatically incorrect: it should be "write code". I generally hear a lot of people from India talk about "writing a code". Any particular reason this is so? Is that what they call it in schools?
- eugene.yarovoi January 08, 2012To a native English speaker, this expression actually sounds funny because in that context, "code" generally means something like a combination to open a lock or a bar code at a store. You want me to write a code? Okay: 33728930...
It's unlike me to make a post which is admittedly off-topic, but when I read the question, I just thought that since many people here are from India, I'd probably be doing someone a service by pointing out that in interviews and cover letters and everything else (at least in the US), it's "write code", not "write a code". Don't tell the guy interviewing you that your summer job involved "writing a code to allow users to access a website" (sounds like the website has a backdoor), or worse, "writing a code for encryption purposes" (sounds like you're designing an encoding scheme of some kind).