dn
BAN USERWait, when person 1 is asked ot subtract their random number, if each salaray is Sa, Sb, Sb, and the random numbers are Ra, Rb, Rc, then the sum of all is Sa+Sb+Sb + Ra+Rb+Rc, so first person subtracts their random number, leaving Sa+Sb+Sc + (Rb+Rc) so he doensnt know Sb or Sc since they are obscured by Rb+Rc and are summed together anyway. B then pulls out Rb, C pulls out his own Rc, so aren't we are left with Sa+Sb+Sc?
- dn June 13, 2013Have each engineer pick a random number and add that random number to their salary and then reveal that sum and add all 3 of these sums together. Now ask first engineer to subtract his random number from the sum, have second do the same, and then have the third do the same and divide by 3.
- dn June 13, 2013What about another approach? What if we just sort the dictionary of new alphabet words by length and hopefully find a very small set of words with a very long length. For instance, en.wikipedia.org/wiki/Longest_word_in_English has the longest words. If we can find just one word that is unique in length, then we can easily map it back from the scrambled to the original alphabet. If we have a few, well, then we could then go and try each of them out exhaustively.
- dn June 10, 2013Is the exhaustive algo O(2^n * n) where n is # of digits in original set? Thats because you could make 2^n different pairs of subsets, and for each pair, you do sums of O(n).
I wonder if you could sort the origianal set and then walk up the sorted list, splitting it at each of the N points (forming the two subsets) and computing the difference of each of these subsets at each step, looking for the max? If so, you could optimize the sum, as you are just adding one new value to the sum of the first and removing it from the sum of the second.
Wait, you will have to sort the incoming stream until you get the first 100 numbers. Then if the next number is greater than any of the prev, you have to push down the set by 1, so in this worst case, you will have to do this about 100 times N. Wouldn't a binary heap will allow the insert option in big-O log base 2 of 100 times N? So be faster.
- dn May 22, 2013Might he have been looking for a counting sort type approach since you know that there are only K distinct numbers (presumably K is relatively small)? This could be a very large improvement over an NlogN type sort.
I tried this recently to compare a very large set of numbers (10,000,000) that were bounded within a range vs STL's generic sort<uint32_t> algorithm and got about a 80% reduction in run time, so its definitely a good solution if you know your data is range bounded.
Per multicore (and Im guessing here) but we could divide a couting or key-index sort between different cores if we break up the O(N) steps up into M pieces (where you have M cores) as each of the M pieces should be parallelizable (is that even a word?)
How about just sorting the input string and then walk up the sorted string extracting pairs of chars and adding them to the beginning and end of a string, so build it from the inside out. If the problem were relaxed to allow odd, then first scan the sorted string for odd numbered set and use that as the middle of the result.
- dn May 11, 2013So the question is missing a word, "write a generic function API in C so it can ???? any data types..." Did you mean to write "write a generic function API in C so it can hold any data type..."?
I would agree though, not sure how to do that in C, but C++ provides function overloading, so maybe overload the insert() function for each data type to be inserted? That solves the problem of knowing the sizeof the data. Now the insert function can malloc the sizeof the data type and store it in there. However, when you extract the data you would still need to know the type of the data so you know how much data is held, so you might want to add that into the buffer as well.
@dadakhalandhar. So assuming question is find the lowest common ancestor of a binary tree, what if we DFS the tree, recording path as we go along, and search for both nodes. Upon finding both nodes, then compare the paths of the two, starting from the root node and on down. The root node must match but eventually the paths will diverge. Where the paths diverge is the LCA. Is that what you mean by using the stack?
- dn May 11, 2013Question says binary tree, not BST, so maybe its not organized as you assumed? or maybe it was transcribed wrong.
In any case, even if a BST, when finding the common ancestor, consider the case where the one of the nodes is an ancestor to the other one, for instance, a parent/child relationship.
I like this, but step #3 requires a sort of each word and then the hash? If we could get rid of that sort, we could save that nlogn time per word. What if we could do a hash that was insensitive to the order of the letters? Then we wouldn't need to sort them, saving that nlogn time. What if the sort were as silly as adding up the values of each letter. We could get false hits and then have to check each possible hit against other possible hits, maybe we would come out ahead here.
In any case, this is processing all the words in the dictionary, which would seem to be against the "not every words should be processed..." stipulation.
Not a bad question - IMHO, about the right level for an interview. I can't believe how complicated in terms of algorithmic development or code some of the questions are here. Under the stress of an interview, I cant believe most people could do many of the questions posed here.
- dn June 23, 2013In any case, can we assume the numbers are both positive? If so, read each of the numbers into a vector (using push_back). Equalize the length of the two vectors to simplify the addition. Note that the digits in the vector will be in order, from MSD to LSD, so add on a corresponding number of 0s to the beginning of the smaller to make equal length with the longer. Now that they two are equal length, just iterate over the digits of both (from last to first digit), summing and storing sum mod 10 and propagating forward sum / 10. Oh, make sure sum has length = length of either (since same, equalized now) plus one, to accomodate for additional digit possible due to carry. Now write that sum vector back out, from MSD down to LSD.