eugene.yarovoi
BAN USER@pritybhudolia: I was thinking the goal was to find, for each element X, the least element Y such that Y > X and Y is to the right of X in the array. In other words, find the element to the right that would the next element in order. "Next greatest element" suggests this kind of interpretation to me. The example works for both our interpretations, unfortunately.
- eugene.yarovoi April 08, 2013You can ask about the focus of each session, but be prepared to not get an exact answer. The company may leave a lot of the questions up to the interviewers, and there is not always a clear plan. I wouldn't bother with such a question for that reason. You can rest assured you will be asked coding, technical questions, and resume / behavioral questions, so why do you even need to know when exactly you will be asked them?
I've never asked for the identities of interviewers. On one hand, it's proactive and strategically wise to learn who will be interviewing you; on the other hand, I feel it can be a little too much pandering to the interviewer, at least for a tech interview. Maybe others will disagree. In any case, you can do just fine in the interview process if you don't know who your interviewers will be.
Since you don't use the value you put in the map for anything, you could just use std::set.
- eugene.yarovoi April 06, 2013I wouldn't say it's inherently good or bad. It's an opportunity, like Anonymous above has already said. You could do a good job and impress people, or you could do a terrible job and have it hurt your chances.
If it's really true that they singled you out for this kind of thing, then that's probably a good sign. It means they find your research topic especially interesting or useful for the company.
Can you provide more information? Some things that would be good to know:
1. The intended length of the presentation
2. The intended audience
3. Your level of involvement in research. Do you have a PhD, were you a researcher in your previous job, or are you an undergraduate who engaged in research?
4. What position you're interviewing for.
But if an object contains a primitive type, that primitive type will be on the heap. So not all primitives are stored on the stack. I'm not sure whether that is or is not what you meant in your answer.
- eugene.yarovoi April 04, 2013I would start with friends of friends as potential suggestions. These can all be retrieved by a breadth-first search restricted to a depth of 2. In that same breadth-first search, I would also calculate how many of the user's friends know each potential suggestion and rank the suggestions by this number. Simply put, if you're not friends with someone who is friends with 30 of your friends, that's usually a better person to recommend to you than someone who is friends with only one person you know.
We could modify the approach above to be more likely to recommend people that are friends with people you interact with a lot. The BFS would be the same, but the ranking algorithm could, instead of giving each potential suggestion 1 ranking point per mutual friend, vary the points based on how much you interact with the mutual friend.
We might consider being less likely to recommend friends that have been recommended recently and were not added by the user. We might also throw in some element of chance to give lower-ranked recommendations the possibility of showing up occasionally.
We might also consider removing from recommendations people you've un-friended in the past. People that you've blocked definitely shouldn't show up.
I'm sure Facebook's recommendation system is a lot more complicated than that and probably considers tens or hundreds of factors. It might even use machine learning to learn the factors that are most likely to make users add the people recommended to them. These are just some starting thoughts.
In-place quicksort has logarithmic space complexity.
If you replace each integer by its square, it could overflow. For k-bit integers, you could need up to 2k bits to store the square of that number. Basically, if you were given an array of ints, in the worst case, you'd have to make an array of longs to hold the squares.
In what language? Can you give an example of an exception that's not caught by try-catch?
- eugene.yarovoi March 27, 2013Each new level comes with increased expectations both in terms of how much code you produce and in terms of your ability to figure out solutions to increasingly complex and ambiguous problems.
- eugene.yarovoi March 24, 2013But then, you only know which guard is the liar. You don't know anything about which door is the door to heaven, and you're all out of questions.
- eugene.yarovoi March 24, 2013Generally speaking, the sequence of titles is SDE (Software Development Engineer) -> SDE II -> [SDE III -> ]* Senior SDE -> company-dependent higher titles.
* = some companies may not have this title
Merely looking at the titles tells you nothing about real career growth, however.
This method still takes linear time. There are faster methods that take logarithmic time.
See geeksforgeeks .org/program-for-nth-fibonacci-number/ methods 4 and 5
You have not mentioned a mechanism by which you will search the stack efficiently. When you get a new query, how do you know whether it's already in the stack? If you search the whole stack every time you get a query, it will be O(n) to answer queries.
- eugene.yarovoi March 18, 2013It's really up to you. Do lots of research on both companies and consider all the factors, like compensation, work environment, geographic location, advancement opportunities, etc. Only you know what factors are the most important to you, so only you can make the decision that's right for you.
Glassdoor is a great place to read reviews of companies filtered by specific role, experience level, etc.
Unless you engaged in deception to be able to have two interview processes at the same time, or unless the company asked you to interview for only one position at a time, I don't think there's anything wrong with it. It's the company's responsibility to determine policies regarding such things and, if they only want people to interview for one position at a time, not to grant people multiple interviews simultaneously.
- eugene.yarovoi March 18, 2013In my experience, there's not a huge amount of difference. What are some of the differences you've noticed?
- eugene.yarovoi March 18, 2013It's not the case that every thread will have its own separate own copy. The variable is declared static, and so there is just one main copy of the variable, shared among all the instances. The issue here is that unless the variable is declared volatile, a thread may cache a local copy of the variable in a register and not synchronize that copy with the central copy in memory until the next time a synchronized statement occurs. It may also, however, not cache a local copy, or sync the local copy with the main copy any time before that, such as when the thread no longer needs to keep the variable in a register. So the thread will probably eventually see the new value of false, but unless you use a volatile variable or a synchronized block, it might not see it as soon as it's set, and there are no hard guarantees on when exactly it will see it.
- eugene.yarovoi March 18, 2013Yes. Also consider that an array has (almost) nothing but data, whereas the linked list has data and next pointers. There's just more memory locations that need to be examined to complete a traversal of a linked list.
- eugene.yarovoi March 17, 2013In an array, the values are stored contiguously, and therefore there should be fewer memory ops and fewer cache misses as well. Generally this is likely to trump the cost of a pointer addition. Besides, in the linked list, even things like list = list->next can involve an arithmetic calculation for the address (internally it becomes something like list = contents of memory ( list + offset of field named "next").
- eugene.yarovoi March 15, 2013+1. Gotta love balanced ternary (not why I upvoted, of course).
- eugene.yarovoi March 14, 2013I don't understand your method, but I very much doubt it's correct because this is an NP-complete problem. O(n^2) would be polynomial in the size of the input. There are correct dynamic programming solutions that run in O(S*n), but that makes sense because S can be an exponential function of the input size.
- eugene.yarovoi March 14, 2013You might also say that it takes too much time. But "too much" is a relative term. Does a Ferrari cost too much? For me it does, but it's chump change for a billionaire.
There's actually a technique to arrange the dynamic programming so that you only need O(c) space. It's well-known and you should be able to find it in many discussions of the knapsack problem.
That's right. One small correction: doing the heap operations isn't log(n); it's log(100). That is, the cost of the heap operations is proportional to the log of the heap size, not the total array size. This means the complexity of selecting the largest k elements from an array of size n using this method would be O(n log k).
- eugene.yarovoi March 12, 2013You can always ask your interviewer for permission to look something up. They could say no, but if your request is reasonable they might allow it, or they might indicate that they don't care about whatever detail you're about to look up (the exact names of certain functions, the exact order of arguments to certain functions, and so on).
- eugene.yarovoi March 12, 2013I certainly encourage you to try; like you said, you can't succeed unless you try. In fact, if your spoken English is as good as your written English in these messages, I don't think it will hinder you. It may not be perfect, but it's at a decent level.
- eugene.yarovoi March 11, 2013I just don't see any reason why it would be right. You haven't indicated any reasoning for your answer. The burden of proof is on the person proposing the solution to give an argument for why it's correct.
- eugene.yarovoi March 10, 2013Yeah, that works. It's the same as the last of the three approaches I discuss in my answer. The time complexity is O(M + N) and the space complexity is O(N).
- eugene.yarovoi March 10, 2013@Loler: I was just going to have a list of occurrence locations for each of the n slots instead of just having an occurrence count. When input list number x encounters a value y, just do arr[y].add(x). All the lists can be processed together in this way, and then the values can be restored in sorted order.
- eugene.yarovoi March 10, 2013This problem is an application of the classic problem to modify a stack to be able to give you the max or min element in the stack at any time. (The classic problem has been asked many times before, for example at careercup DOT com/ question?id=304806).
When we throw a disk down the well, we want to know how far down the well it will get. Without any data structures, we'd have to traverse the rings one-by-one for each disk and determine whether the current disk can fit through each ring. This is potentially O(N) for each of the M disks, leading to an overall O(MN) complexity.
What we could do instead is prepare an array where the k-th element tells us the minimum diameter in the first k rings. This is easy to compute in O(N) time because minArr[k] = min (minArr[k-1], rings[k]). Already, this array of minima forms a non-increasing sequence, and allows us to binary search how far each disk will fall in O(logN) time per ring, resulting in a total complexity of O(N + M log N).
The previous complexity is not bad, but the logarithmic factor can be eliminated to give the optimal O(N + M) solution. This complexity is optimal because it is proportional to the cost of simply looking at all the input. The idea is to construct the minima array as before, but instead of doing binary search, consider the minima array to be a stack, with the beginning of the array as the bottom of the stack and the end of the array as the top of the stack. For each disk, pop off as many entries as needed until the disk diameter is >= to the top of the stack. This is where the disk will end up. Since the disk will occupy space in the ring where it ends up (and two disks can't be in the same ring), pop off one additional stack element at this point and loop to the next disk. Stop when the stack runs out of elements, or when there are no more disks. Since there are only O(N) elements to insert and to pop, and O(M) disks to look at, the overall time complexity is O(M + N). The stack uses O(N) of extra space.
This is O(MN), not O(M + N). (The problem statement says to get O(N), but I assume they meant O(M + N) since you have to inspect the rings.)
- eugene.yarovoi March 10, 2013Different interviews are conducted with different formats and there's no way to be certain, but there's a good chance that a Skype call will involve the questions being spoken to you. I don't want to discourage you, but you should know that applying for an English-speaking software job when your English isn't that good is likely to put you at a disadvantage, and for good reason. Working as a software engineer involves constant and precise communication with other people. If people can't understand what you're saying, or if what you're saying is unclear, they can't work with you effectively.
So what can I say that's actually constructive? First, your English doesn't seem bad from what you've written. Second, if you have a little bit of time to study, I would recommend making sure you know the key terminology. Know the names of important technical concepts in English: linked lists, trees, graphs, tries, etc.
Here's how I know your answer can't be right: according to your code, the only possible answers are b[(m+n)/2 - m], b[(m+n)/2-m+1], and a[m-1]. So as long as m and n are fixed, according to you, there can only be 3 different array positions that can be the answer (none of the array indexes depend on anything other than m and n). Now consider the following construction:
a = {0, 0, 0, 0, ..., 0} (length m)
b = {1, 2, 3, 4, 5, ... , n} (length n)
Let's say we choose n to be significantly greater than m. Since the elements of b are also all greater than the elements of a, the median will lie somewhere in b. Specifically, like you said, at the (m+n)/2 - m th element in b. Let's say the answer to the median in that case happens to be b[r] (r = (m+n)/2 - m). Now, suppose we change the last element of a to be n+1. The median now has to be b[r+1]. Change the second-to-last element of a to be n+1 also, and the median now has to be b[r+2]. If another element in a is changed, the median is b[r+3]. This shows that there are more than 3 positions that can be the answer, and therefore no solution that proposes that the median will always be in one of 3 positions can be correct.
Are you assuming b[0] >= a[m-1]? I think there is no such constraint. a and b are sorted, but they can interleave in arbitrary ways.
- eugene.yarovoi March 09, 2013No, that isn't correct. Why would it be?
- eugene.yarovoi March 09, 2013@Mr.karthik.p: The issue is that a merge is really not so simple when you don't have extra space.
@Bevan: That makes sense if you want an O(n log n) solution. You wouldn't be taking advantage of the fact that the array is just two sorted arrays back-to-back (instead of being just random data), but it's still a decent algorithm all in all. You probably want to use an in-place heapsort because quicksort does use just a little bit of extra space (logarithmic).
What do you mean by "String is not immutable?" String is definitely immutable in Java.
- eugene.yarovoi March 08, 2013We can actually improve the bounds to guaranteed O(n) instead of expected O(n) by noting that the sum is bounded between -n and n. We can just use an array instead of a hash table.
- eugene.yarovoi March 07, 2013@Loler: regarding your comment to rdx, I actually don't think it's artificial at all to ask to sort the lists separately. That's how I interpreted the question too, and it's a little more difficult that way. The question is how you will ensure strictly O(n) complexity even when the n elements are distributed across r different lists (let's assume r <= n). A direct attempt to use counting sort directly on each list will use up O(n) time *per list*, resulting in a total complexity of O(r*n), which may not be O(n). You will need a modified and trickier form of counting sort to get the O(n + r) time bound, which can be taken to be O(n) under the r<= n assumption.
- eugene.yarovoi March 07, 2013@kevin: no, that's not right.
- eugene.yarovoi March 07, 2013We know we can't merge an arbitrary array in less than O(n log n) using comparison-based techniques because it could be that r=n, in which case asking to merge is just the same as asking for a general sort.
- eugene.yarovoi March 07, 2013It's not the number of digits that look the same upside down that's important, it's the number of digits that look like some digit (itself or some other digit) when upside down. This number really depends on the font being used. If there are k such digits (and k is even), the formula will be k^(n/2) / 10^n (as anonymous already suggested).
- eugene.yarovoi March 06, 2013That's about right, but as ashutosh141 noted, we might have to modify the formula a bit if leading 0s aren't allowed. We also have to ask whether 6s really look like 9s upside down (in some fonts they do; in others they don't). Of course some of the other digits might not look the same upside down either (do 2s or 5s, for example? Not in the font I'm using now).
- eugene.yarovoi March 06, 2013@YetAgain: Yes. There's nothing wrong with doing this kind of logic from the two ends instead.
- eugene.yarovoi March 05, 2013Yes, you could. But then, you only know which guard is the liar. You don't know anything about which door is the door to heaven, and you're all out of questions.
- eugene.yarovoi March 05, 2013The optimal complexity is actually O(log(min(m,n))).
- eugene.yarovoi March 01, 2013Why not just store an integer count of each letter? That would use less space and be more efficient time-wise as well.
- eugene.yarovoi March 01, 2013We can. How would you build this custom comparator, though? That's an important part of the question.
- eugene.yarovoi March 01, 2013A very elegant way of doing this is to substitute 'a' for the letter that comes first as per the dictionary, 'b' for the letter that comes second, and so on. Then sort normally by lexicographical order (possibly using an existing library). Then, reverse the letter substitution.
- eugene.yarovoi February 28, 2013
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
Send another follow-up e-mail.
- eugene.yarovoi April 10, 2013