CareerCup

What's the point of outputting the values from hash_map if they're already in the map that you're iterating through anyway? Perhaps you meant the (tree) map to be a (tree) set?

To expand this answer, sin(x) is approximated as x - x^3/3! + x^5/5! - x^7/7! + ... to some number of terms that allow sufficient precision. cos(x) is approximated as 1 - x^2/2! + x^4/4! - x^6/6! +... . These formulas come from calculus.

To minimize the magnitude of the error incurred when approximating, angles are first reduced to the range [-pi, pi] and only then approximated using the above formulas. This can significantly reduce error because of the high powers of x in some of the terms. The formula doesn't start to converge very well until you have a number of terms that is somewhat proportional (give or take) to the absolute value of x. If you have -pi <= x <= pi, you're guaranteed that the formula does a pretty good job of converging after about just 5-10 terms.

Most companies let you restart the process 6-12 months after you get rejected. You would typically start again from the first phone screen. The exact timing depends on company policy, and I don't know Facebook's policy specifically.

Do you have a strategy to beat O((N+D) logN) using segment trees, where N is the number of entries and D the number of queries?

A full answer would explain in what way segment trees are to be used.

It's not possible to get the exact value back. >>> is not a reversible operation. In other words, there are multiple inputs such that applying >>> 2 to them would give you 24. 99, 98, 97, and 96 all yield 24. So if all you know is that you got an answer of 24, you won't be able to determine which of those you started with.

Padding is certainly done automatically. It can, however, be done automatically in different ways on different machines. The padding is not guaranteed to be done in a way that would be consistent across different machines. If you declare the same struct on two different machines, you can't rely on it to be padded in the same way on both.

What's the truth?

First of all, according to the problem statement, the columns are unsorted. So this solution is clearly out.

Second of all, that wouldn't work even if the columns were sorted. Think about it: just because you know that the element is > arr[k][0] and < arr[k+1][0], for some k, doesn't mean the element is positioned somewhere like arr[k][i], for some i. The element could be at arr[0][j] for some j, for example.

Your performance will usually be evaluated based on feedback from the interviewers, and you won't get an offer unless they said good things. There's therefore no benefit to telling the recruiter, and it could sound a little bit like you're making excuses. It also betrays a lack of experience with the interview process and is slightly unprofessional for that reason as well. I would advise against it.

The best thing to do is to just learn from your mistake and not make the same mistake twice. Just about everyone makes some interview blunders early in the job search.

Interview circuits at tech companies frequently don't include HR. I don't know about Bloomberg specifically, though.

You met with a senior manager, which I would interpret either as a neutral or good sign. At some companies, these people will always be part of the interview loop; at others, only if you did well.

Absent any Bloomberg-specific additional information, I would continue to be hopeful, though by no means assume there will be an offer.

@bulelaugh: that's only possible for general balanced BSTs if the tree carries some extra information to enable this operation. See "Order Statistic Tree" on Wikipedia.

I suppose one question would be why you are attempting to extend a class that was not designed for inheritance (or else it would have been given a virtual destructor). I'm sure there may be situations when you might need to do something like that, but are you sure you need to use inheritance here? Is this an interview question?

@Alex: I very much doubt that where something is stored in memory is the reason for those precedence rules. That seems like a somewhat extraordinary claim given that AFAIK where something is stored in memory is an implementation detail and may not be consistent across all implementations. Can you point to any sources that would support your position?

@hprem991: Your explanation was unclear to me and I wasn't really able to follow you, so that's why I gave some benefit of the doubt and said "even supposing [it makes sense]". C++ doesn't support inner classes (well maybe the new versions do, I don't know), so I'm not completely sure how you can even attempt a comparison of this situation with any situation in C++. Regardless of the merits of any claims you make about C++ though, this is a Java question.

@Shan: That's an algorithm that potentially takes O(n). The problem statement asked us to do better. It can definitely be done. I was only commenting that no one here has given a correct sublinear algorithm for it so far.

Binary Search Trees that are augmented with special information to help them find the k-th element in O(log n) time are called "order statistic trees". You can read more about these on Wikipedia. If you make the tree a balanced order statistic tree all the operations this problem asks for can be done in O(log n) time.

I should give you +1 for thinking about corner cases :)

Checking what Alex has said, the program does in fact print "Orange". You could have checked that in ideone if you don't have a Java setup on your computer. In fairness to you though, Alex's response is not completely right because the behavior has nothing to do with where something is stored, but everything to do with the rules of the language. What section of memory a variable or class is stored in is an implementation detail.

The explanation you gave doesn't make a huge amount of sense to me even from a C++ perspective, but even supposing it did, that sort of explanation probably wouldn't extend to Java.

I believe the reason it prints Orange and not Apple is because the language rules assign precedence to associating the . operator with a field (and not a class). If you change the field name to a different name, the program does print "Apple" as one might expect.

@lgory: agreed. I'm actually surprised that Java allows this. That means if you're working on a class and you add in a static field that has the same name as an inner class (by mistake), you could actually inadvertently modify the behavior of existing code that references the inner class. It's an unlikely case, but still nasty.

-1 for giving yourself a +1

What I mean is the problem is rendered uninteresting if we admit this kind of O(NlogN) solution. However, in a practical setting it wouldn't necessarily be a bad idea.

It's not terribly inefficient. Still, I imagine we're trying to do better than O(NlogN) here because it's just too easy to do what you did.

@huha: that's only correct if the tree is a complete binary tree, in the sense that every leaf node is at the same level, and every node is either a leaf node or has two children. There's no reason to assume that would be the case since you're forming the tree dynamically (in fact, it's not even possible to have a complete binary tree unless the number of nodes can be expressed as 2^k - 1 for some positive integer k).

What level of position are you applying for?

I think the short answer is yes, you should be able to make a switch. You may, however, have to find ways to gain C and C++ experience outside of work, or through extra projects at work, to adequately prepare you for this kind of transition and convince people that you have what it takes.

@Last Anonymous: yes, it should be. 405 is correct. Having no 4 applies to the input, not the output.

@Dr. Andrew: An interesting solution.

@fanymanea: I wouldn't say it's *the* correct answer, but it's *a* correct answer.

What's your algorithm for implementing get_random()? It can be done, but you haven't explained how you will fulfill this rather critical requirement.

-1: It's not possible to search for an arbitrary value in a heap in less than O(n). Such searching would probably be needed to implement deleteElement() (if deleteElement deletes an element with a specified value).

@Kamy: If the phone book is such that it supports multiple numbers for a single name, then yes, we can make the simple change that you propose. I took the phrasing of the question to imply that there will only be one number associated with each name.

You could just use two HashMaps, one for mapping number -> name and the other for mapping name -> number. That's probably the most reasonable solution here.

Search for "XOR linked list" on Google or Wikipedia. This is a well-known data structure that you can find high-quality explanations for.

I'd give more details, but I'm low on time right now: consider divide-and-conquer. Can you see a very simple O(nlogn) algo now?

This would only be true if all paths comprising P1 went through the top left and bottom right corner of the constraint region when they go through it at all (and couldn't come in through the sides), and if furthermore there were exactly one path in P1 having each forbidden path in P2 (there are many distinct paths in P1 that share a forbidden path in P2). Neither of these things is true in this problem.

@Sunny: not sure I understand you. I did provide an explicit counterexample above.

In any case, I believe the burden of proof falls on the person proposing the solution to justify its correctness, not on others to give counterexamples or dis-proofs. If this were not the case, we'd believe a great many false things. I'm usually happy to provide detailed feedback to people, but the person who posted this answer didn't even give any kind of justification or proof for the algorithm's correctness, so I can't really say where they went wrong because I don't know why they believed the algorithm to be correct in the first place.

@nybon: I guess that really depends on how you interpret the term "lexicographically minimum permutation". My interpretation was that each number would be interpreted as coming "lexicographically before" if it is less than the other number. So 2 comes before 11. It's true that "lexicographically" would suggest that things should be in dictionary order, not numeric order, but the interpretation I used makes sense in the context of this question, as evidenced by how everyone else assumed exactly the same thing. Also, since the integers seem to be given as an array of ints, you might think of each int as being 32 0s and 1s, in which case lexicographic ordering would be identical to numeric ordering for nonnegative integers.

I think you're the first person here to interpret the question in the way that you did, so it's not so much that these solutions are wrong, but just a different interpretation of the question. Your interpretation isn't any less valid though.

Fundamentally, the solution is the same either way: the algorithm here tells you the rank of the element that should be placed at each position. If your sequence is 3, 2, 1, 4, that just means you should place the 3rd lowest element first, followed by the 2nd lowest, followed by the lowest, followed by the greatest. You can use whatever metric you want for how you decide the order of elements (numeric value or alphabetic order or something else entirely). Of course whether or not this paragraph is true depends on the exact specifics of how we define "lexicographic" ordering between permutations.

Hashmaps don't tell you anything about order statistics.

The complexity of the naive recursive algorithm is exponential in the size of the grid. When using dynamic programming, the complexity will be linear in the total number of locations in the grid.

But this is just the naive O(n^2) algorithm.

The series sums to theta(NlogN). However, you do this for each of N iterations of the outer loop, so the overall algo is O(N^2logN).

I think he's just supposed to simulate the results of these instructions.

The main problem with your code is the amount of duplicate code -- you have code parts that are repeated in many different places. One of the most important quality differentiators in code is to what extent you're able to avoid this. Code duplication is bad because (among other things) when you need to change how something works, you end up needing to change it in many places. If you then forget to change one of the places, you have a bug. Another reason to avoid code duplication is because it means you will have less code, and that usually means people will be able to read it in less time.

Let's say you wanted to change the contents of one of your error messages. You would have to make the same change in many places. Also, when I read the code, it takes me more time to read everything and figure out what you've done.

To avoid code duplication, find ways to split your code up into methods. Take duplicated code and put it into its own method, and call the method everywhere that you need that code.

A somewhat more minor (but nonetheless important) issue with your code is that you should probably throw exceptions when error conditions occur. Otherwise, despite the warning messages, methods will return normally even though some invalid state has been reached. With an exception, the program would crash (if the exception is not handled), and the person using your code would immediately know they did something wrong. This is of course assuming that the desired behavior when an illegal operation has been attempted is to abort the program -- if the desired behavior is to do nothing and display a warning, you're fine.

You could do an iterative reversal of the linked list, and then print the reversed linked list in a loop. Then, reverse the list again before you return in order to restore the original state of the list.

This approach requires you to modify the list. You won't be able to do that if the list is immutable, or if other threads might be reading the list at the same time as you execute this algorithm.

Reversing a linked list and printing it out once it's reversed both take O(n) time, so the algorithm is O(n) time overall. The space used (in addition to the space occupied by the input) is O(1) as reversal can be implemented iteratively in O(1) space, and so can printing each node.

One might not consider it to be quite the same as recursion, so it's possible this could have been what the interviewer was looking for. But yes, both approaches require O(n) space.

For an approach requiring O(1) space and O(n) time, see my solution. Be advised, however, that my solution has certain limitations, as I note.

@addy: there's a flaw in that analysis. You need one pass per each possible third number. There are N of these, so you will require O(N^2 log N) time (or O(N^2) if you sort only once and then do the N passes in O(N) each).

There are O(N) rows with N elements each. Merging something like that takes O(N^2*logN) time.

This doesn't make sense to me. Can you explain the reasoning?

What probability distribution should govern the selection of outcomes?

@jerr: why? it gives an answer of 2.

I think you're misinterpreting the usage of the word "sequence" here. I doubt that the term "sequence" in the problem statement was meant to mean anything special. I think the question is just "Given an array of integers, how would you compress that?"

So then the destructor is a virtual function and we've still used a virtual function.

@Srikant: what do you mean?

@prabu: I don't think you've fully thought this through. The 2D case is more complicated than the 1D case.

In the 1D case, a subarray of sum 0 corresponded to a duplicate value in the sum array, and you could just use an algorithm for detecting duplicates. A duplicate in the sum array would correspond to a zero-sum subarray.

There is no such direct correspondence in the 2D case. Finding two identical values in the summed area table does not correspond to a rectangle whose sum is zero.