eugene.yarovoi
BAN USERI would consider memcpy to be a "standard string copy function", even if it's not always used to copy strings.
- eugene.yarovoi July 07, 2012I like the out-of-the-box thinking, but it doesn't meet the specifications: copy the *contents* of an array A to *contents* of Array B. That seems to me to imply that the two arrays will have independent contents afterwards and editing one array will not affect the other.
- eugene.yarovoi July 07, 2012No. Summing two random variables doesn't produce results that are distributed uniformly at random. And rand(5) % 3 is biased towards getting 0 and 1.
- eugene.yarovoi July 07, 2012Because integers are discrete, to make a long story short.
You see, the rand(5) in this problem doesn't give you something random in a continuous interval; rather, it gives you an integer.
If further explanation is required: rand(5) only produces 5 possible outputs. If those are the inputs to the rand7() function you're trying to build, your rand7() function can have at most 5 possible outputs, which is certainly wrong.
What sort of story or advice are you looking for? I thought you were concerned about interviews because that's mostly what this site is about. But if not, what sort of advice are you looking for? How to become better at design in general? Any specific aspects you're interested in?
- eugene.yarovoi July 07, 2012What I mean is: how much experience do you have designing programs? What's the largest program you've coded from scratch?
- eugene.yarovoi July 07, 2012You've read about OO? That sounds very wrong. You don't learn OO by reading. You learn OO by coding an OO project. Have you ever designed a significant program from the ground up?
- eugene.yarovoi July 07, 2012Have you had trouble with design questions in the past? If so, the most productive thing would be to start by explaining which aspects you tend to struggle with.
- eugene.yarovoi July 07, 2012No DP is required to do this in log time. DP seems like overkill.
- eugene.yarovoi July 07, 2012Varun's described algo has a different flaw: the remove operation takes linear time. See the top voted solution, where everything is O(1).
- eugene.yarovoi July 07, 2012You can even do this in O(n log n) + O(number of negative numbers * n). Still, why the assumption that the number of negative numbers is small?
- eugene.yarovoi July 07, 2012Who knows. Maybe the roundoff errors cancel out just right. Point is that you're doing something you're not supposed to by comparing imprecise types with ==, and as a result, the output is difficult to predict.
- eugene.yarovoi July 06, 2012Yeah, 1 is also undefined. The others...I don't see how. What's their definition of undefined? I mean, a+5 could be less than a+4 if it overflows, and that's situation and architecture dependent, but I wouldn't say that's undefined.
- eugene.yarovoi July 06, 2012Why would a + 6 be undefined?
- eugene.yarovoi July 06, 2012Surprise, surprise, but it's 3 and 6.
Shifting something left by more than or equal to its bitwidth is undefined. An int can only be shifted 31 or less. That's assuming an int is 32 bits on your architecture, of course.
4 and 5 are actually perfectly fine because an expression like &a[i] gets translated to (a+i) without ever dereferencing that address. So we're just comparing pointers and never dereferencing them.
*You cannot compare 2 floats or doubles using == *
Floats and doubles are by their nature imprecise, and doing arthmetic with them causes them to have what's known as roundoff error. 0.1 * 7 may be 0.69999993427 or 0.700000000003482, and thus not equal to 0.7. And 0.1 * 7 is not the same as 0.1 + 0.1 + 0.1 + ... + 0.1 7 times. And for given a, b, c, a+b+c may differ from a+c+b. Perhaps an even more appalling thing is that it's even possible that if you do x=0.1 +0.1; y = 0.1 + 0.1 and then compare x==y later, they may or may not be different!
So is C broken? No. Just don't compare imprecise types with precise comparisons. Instead, always use this style of comparisons:
Const double epsilon = 1e-6; // for example
If (abs(x-y) < epsilon ) { consider them equal; }
A couple things. 1) there is absolutely no reason a HashMap couldn't work with negative numbers 2) to avoid needlessly wasting space, you should use sets instead of maps here. You only need keys here, not key-value pairs. 3) C++-style sets are called TreeSet in Java, and many languages have some sort of support for these.
- eugene.yarovoi July 05, 2012That works fine if there's a fourth person trusted by everyone else. What if there's not?
- eugene.yarovoi July 03, 2012Here's a simple solution. We start out assuming everyone's salary is in a certain range, say 0 - 1 trillion. The first person picks a number uniformly at random in that range and informs only the second person about this random number. Since this number is just random, it conveys no information. The second person adds their salary to the number and informs the third person about this sum. The third person receives no info from this because of the random element added in. The third person adds their salary to this running total and informs the first person about the sum. The first person knows the random number and subtracts it out, leaving the first person with the sum of the second and third person's salary. The first person could have obtained this info from the average anyway, so no extra information has been conveyed. Finally the first person adds their salary and divides by 3.
- eugene.yarovoi July 03, 2012In what manner are these trees constructed from the arrays?
- eugene.yarovoi June 30, 2012Ah, I understand now, you're assuming base 10. I think most other posters here, myself included, were assuming base 2. There's nothing wrong with your solution if the number's base 10. The fact that it's 0s and 1s made most people think it's binary.
- eugene.yarovoi June 30, 2012My interpretation of the question was that the probability of each entry must be the same, not each distinct entry. In the distinct case it really is as simple as having a count. Having some sort of balanced order statistic tree seemed like the obvious solution, but the real question is whether we can implement it while keeping all operations in expected O(1) time.
It seems that we can. Instead of your HashMap mapping values to a single index, it could map values to a HashSet of indices. Then we need a getAny() operation on this HashSet, that returns and deletes any one value in the set (with no requirement on which value it should be). We need this operation to run in expected O(1) time. Though it's tricky to prove, I do think that picking a hash bucket within the set at random until we get one that has at least one index in it, and then just taking the first index we see, accomplishes this goal, provided that we rehash periodically to keep the number of buckets within a certain ratio of the number of elements in the set.
If we have this method for the HashSet, given a delete, we get our HashSet of indices for the value to be deleted, and we pick and remove one such index, call it w, in O(1). Now we go to the end of the array, delete the value there, call it x, and put it at index w. We search the Hash*Map* for x and get a set of values where x occurs. We delete array.size()-1 from that set, and we add w to the set.
I think this covers it.
A count is insufficient. You need information on where all the elements having a particular value are.
- eugene.yarovoi June 30, 2012Let's hear the question and both answers
- eugene.yarovoi June 29, 2012Seems like people cheat without realizing that it won't get them a job. They'll still have to clear the in-person where cheating is harder.
- eugene.yarovoi June 29, 2012And don't forget the use of delete instead of delete[]
- eugene.yarovoi June 29, 2012What if someone doesn't use new to build the object?
- eugene.yarovoi June 29, 2012@zprogd: I could. But the real answer is because it's inefficient.
- eugene.yarovoi June 29, 2012on mouse movements...
- eugene.yarovoi June 29, 2012It's (N^2)*logN. You can use a heap that at all times has the next element from each of the N arrays to select the element that appears next in the sorted output array in logN time per element. There are N^2 total elements. You get the same result if you do it by merging the arrays into arrays of size 2N after one pass, 4N after 2 passes, 8N after 3 passes, etc.
- eugene.yarovoi June 29, 2012Good suggestions all.
- eugene.yarovoi June 29, 2012I do think there's a general resume drop for exactly this sort of situation. That said, if you like a particular position, can't hurt to apply to specific positions as well.
- eugene.yarovoi June 29, 2012I'm saying that the declaration int c[2][2]={1,2,3,4}; makes a 1-D array and not an array of arrays (2-D array). One of the things I think is so very wrong with C and C++
- eugene.yarovoi June 29, 2012I guess you might get that too, because the array in the caller method is only pretending to be a 2-D array when it's a 1-D array.
- eugene.yarovoi June 29, 2012One small bug: the queue only accommodates s-1 integers, not s integers.
You could consider using tmp = (tail+1 == size) ? 0: tail + 1; to avoid the expensive modulo operation.
Yeah, this is not an easy problem to solve outright by logic. So far all I've determined is that this number would have to have a fair amount of digits and begin with 1. Also, if one such number exists, infinitely many do, as you could add any number of zeros at the end.
- eugene.yarovoi June 29, 2012There's just a little snag here. This works great for unique elements. How will you deal with duplicates?
- eugene.yarovoi June 29, 2012That thought is in the right direction, but how will you remove from the ArrayList quickly? See the top-voted solution.
- eugene.yarovoi June 29, 2012Interesting point.
- eugene.yarovoi June 29, 2012Try marketing your job experience and programming hobby projects more and your college days less. With time, employers will also care about your education less. Once you get a call, the rest is mostly about your skill in the technical interview. Once you get a call, your education doesn't matter too much.
- eugene.yarovoi June 29, 2012Only the first is an answer you should give in an interview though :)
- eugene.yarovoi June 29, 2012Sure. Both 3 and 5 free the memory the pointer points to before attempting to use that memory. Creating a backup of the pointer doesn't help because the backup still points to the same memory location. It's not the pointer that gets altered during a call to free() -- it's the memory it points to. 2 is the correct option, assuming we correct the first line to use a *: struct node* m = n;
- eugene.yarovoi June 29, 2012To be more specific, code trying to access those memory locations would receive a signal from the operating system that it's not permitted to access them. The program will then typically terminate.
- eugene.yarovoi June 29, 20122-D arrays allocated on the stack are actually allocated as a contiguous 1-D array. When you pass this to a method, methods have no idea what something like array[X][Y] refers to because it needs to refer to array[X*ySize+Y], but the called method has no size information. In my opinion, this is a very unfortunate feature of C. 1-D arrays shouldn't be masquerading as 2-D arrays.
- eugene.yarovoi June 28, 2012@Herman: doesn't explain how you deal with the fact that the words can appear in any order, and that there can be non-words in between.
- eugene.yarovoi June 28, 2012Just search 3SUM on wikipedia. I swear I'm not making you look for porn.
- eugene.yarovoi June 28, 2012I think I can say this, since it's not specific to any problem: If you had a segfault, something's wrong and it's not just a wrong algorithm. Find what that something is. Whatever's wrong could explain the Wrong Answer as well.
- eugene.yarovoi June 28, 2012Doesn't seem wrong to me. Seems logically equivalent to two other solutions on this page.
- eugene.yarovoi June 28, 2012Does it matter if it exists? It's still a pure virtual method if it does. And yes, it does: stackoverflow. com/questions/1219607/why-do-we-need-a-pure-virtual-destructor-in-c
- eugene.yarovoi June 28, 2012
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
More specifically, something like:
- eugene.yarovoi July 07, 2012