CT
BAN USER1 pass - counts for suffixes mod 10000. This will fill the 10 K elements with counts
Look for all less than 10^5 counts. Store suffixes for them in one part of 10K array.
For each, do a pass and utilize other part of 10K for bitmap
There should be plenty for bitmap cause we need 10^5 bits but we have way more than 10 bits per element
Total complexity is O ( n m ) where m is number of misses.
Adj list, but in following way:
Distributed hash map.
A key is either a node or pair of nodes.
If it is a node, a value is a pair that consists of key node and the first node in adjacency list.
If it is a pair. The key consists of node for who the adjacency list and the current node in adj list. A value consists of node for who the adjacency list and the next node in adj list.
@VV, I will explain why I down-voted your question, please be wise and don't retaliate. Also, if you will correct the issue with problem statement, not only I will revert my down-vote, but will also up-vote this.
Any existing sorting method can use these 3 methods in addition to the algorithm. It is obvious that problem statement is incomplete and is also stating WHAT YOU CANNOT UTILIZE --->
OR: It potentially says that these 3 methods can complete with certain magical time complexity and now having such, come up with better time complexity for the sorting.
Please, complete the problem statement.
@Scott, @pavelkushtia, please, read comments throughout this page, including the comments of the problem reporter. Recursion in this case makes it greater than O(1) memory, at least O(logn) to keep stack. O(1) is clearly problem requirement, as was clarified numerous times in this page, including the clarification of the problem reporter. Such solution does exist, see my solution, @zortlord and myself tested it really thoroughly for correctness and time/space complexity,
- CT April 14, 2015Let's say we are dealing with ASCII characters. Keep matrix 258x258. 256 for each possible character and 2 special ones: beginning of the string and the end of the string.
As you walk each string from beginning to the end, note every adjacent pair of characters, including the imaginary character before the string - beginning - and after - end.
Increment corresponding cell in the matrix [int representation of first char][int representation of second char]
Generating:
Look at the row corresponding to beginning symbol and chose a cell randomly based on its weight, which is a cell value divided by total in the row. Its column is next char.
Repeat until encounter end symbol.
@tjcbs2
max 5, second max 4
left:5. middle 5,4 right 4,1,3,1,2
left and middle 0 water, done.
at 4,1,3,1,2
max 4, second max 3
left:4. middle 4,1,3 right 3,1,2
left is 0 water. both middle and right have two maxes on the side so they themselves have only middle parts. first contains 2, second one, total 3
@Javeed agree this same logic can be well done without recursion. After first recursion, on the left it is always water on the right and step-in to the left and on the right it is always water on the left and step in to the right. So, after initial divide you can just iterate down on the left side and iterate up on the right.
- CT March 20, 2015Find the bar with max heights and second max heights
Calculate water in between the two as sum of second max minus every bar heights
These two bar divided bars on three parts. Recursively, solve for bars in the left part and in the right, inclusively with dividers.
Note that after 2nd recursion and on, highest will always be on the border, so will have 2 parts, not three, without loss of generality of the recursive step.
Time complexity O(n). Even though search max will go each bar on every recursion, we only do it on just a portion of bars for which water is not counted, which reduces exponentially. Same reasoning as quickselect is O(n)
Yes @guilhebl, but not necessary from a root, potentaily from any node. Consider this tree:
0-1-2-3-4
1-5-6-7
at node 0 maxDistance is 4 and second Max 0. at node one, max and second max 3, making it 6.
But in any case, walking up should discover any new node with new max. I will eventaully write the code, it will clarify
The way nodes are added makes it into a tree.
Consider the first node as a root. Every new node is a leaf.
Lets have a node to have following structure:
class Node{
Node parent; // so we can walk up
int maxDistanceToLeaf = 0;
int secondToMaxDistanceToLeaf = 0;
//These two nodes MUST be different
//They are two immediate children to this node from which the two max paths came
Node childForMaxDistanceToLeaf;
Node childForSecondToMaxDistanceToLeaf;
}
On every node addition, walk up a tree all the way to the root and on every node on the way update two max distances to leaf if any of them needs to be updated, as well as 2 associated children nodes.
Note maximum maxDistanceToLeaf+secondToMaxDistanceToLeaf. If it is larger than previous diameter, this will be new diameter. otherwise, new diameter does not change.
Time complexity: In case nodes are added to random nodes n log n. If not making such assumption: n*diameter. Because in average, path from leaf to root is equal or less half of diameter.
Memory complexity is just n
EDIT: Added working solution
---
Ok, now I have a prof it is not going to work:
Let's say we have n candles and perfect n(n+1)/2 combined length. and the first candle is n(n+1)/2 - (n-1) and the rest of candles are 1.
The candles that are taller than possible amount of days can never be fully utilized.
Please, don't down-vote because I can just remove this but I do not remove because I think this thoughts can help in discussion.
EDIT: This is working solution and it is still O(n) because while loop will have very small amount of iterations. It is based on the thinking I posted (below the solution) - it was not 100% correct, but it is now corrected:
static public int solveIgnoringUnusableWax ( int[] candles ) {
int totalLength = 0;
for ( int c : candles ) {
totalLength += c;
}
return Math.min( candles.length,
//inverse of n(n+1)/2
(int)Math.floor((Math.sqrt(8*totalLength+1)-1)/2) );
}
static public boolean cutUnusableWax( int[] candles, int currentSolution ) {
boolean cut = false;
for ( int i = 0; i < candles.length; i ++ ) {
if ( candles[i] > currentSolution ) {
candles[i] = currentSolution;
cut = true;
}
}
return cut;
}
static public int solve( int[] candles ) {
int currentSolution;
do {
currentSolution = solveIgnoringUnusableWax ( candles );
} while ( cutUnusableWax(candles, currentSolution) );
return currentSolution;
}
Find biggest integer n(n+1)/2 that is smaller or equal than combined length of all candles. Answer is minimum between n and number of candles. Time complexity O(n) for summing up step.
The strategy for choosing candles is always peek tallest.
Scetch of Proof.
in case n is less than number of candles
Let's say you can no longer peek candles. It means you have all left candles size 1. Why. Because in previous steps you burned the candles that you need now and they were size 1. Since we peek allays tallest, we would prefer size 2. Meaning there could not be size 2 candles left. You can make the same argument about burning size 2 candles and so on.
If all left candles are size 1, the combined length of all candles can be used optimally.
If no rounding involved, this approach would be:
log2(52) + log2(51) + log 2(50) + ... + ... log2(2) = log2(52!) which is perfect solution
However, since rounding is involved, the worst case scenario is:
ceil(log2(52)) + ceil(log2(51)) + ceil(log 2(50)) + ... + ceil(log2(2))
and the best case scenario:
floor(log2(52)) + floor(log2(51)) + floor(log 2(50)) + ... + floor(log2(2))
The average case is pretty obviously will be holding close to log2(52!)
Each machine should shares a decision graph. Build a decision graph as following:
For the first card, it can be in 52 different position. We need 6 level incomplete tree to place it into any of 52 positions. Build a decision tree that places it into one of 52 positions.
For the second card, it can be in 51 remaining positions which we can number in sequence, skipping one that is already occupied (does not matter which one it is). Similarly, build the tree.
So we build such trees until 2 cards left, in which case we just choose first or second, one decision node.
Connect all this tree as following: Every terminal of previous tree points to the root of next. Note that the terminal should imply which position card had taken based on the condition in the terminal and then you move to the root of next tree, it is ok that there is only one link from terminal and not two.
For a given shuffle, determine the path in the given decision graph and encode this path in binary.
What if the 3 ranges are not overlapping, it will take 3 sorts and 6 transfers for 3 machines to discover this. I think minimize does not mean to minimize worst case scenario but to minimize in a given situation. I thought to count number of operations in my algorithm and realized it will be different in different situation, but it should be because it can take different minimum amount of steps in every situation.
- CT February 03, 2015I can draw very detailed state diagram for individual machine (not the three for each of the three roles but one because at the begging we don't know so every player is equal, they may be in different states) but how would I share drawing.
However, let's see if anyone can come up with simpler solution.
Initial step:
Each machine sort numbers.
Each machine send to the other two the count, min value and max value.
Everyone consistently determine that the machine with lowest min is "low", highest "high" and the third "mid". If they are equal, determine based on max. If max are equals based on lexicographical comparison of hostname.
From this moment and on each machine keeps track of its count, min and max in every iterative operation.
In addition, "mid" keep tracks of those stats at "low" and "high". also "low" keeps track of min at "mid" and "high" max at "mid". "low" and "high will not communicate with each other and will not keep track of each other.
Odd step:
If max of "low" greater than min of "mid", mid sends first part of its numbers in the amount of 10% memory to "low". "low" sorts them via no extra memory sorting algo.
If min of "high" less than max of "mid", mid sends last part of its numbers in the amount of 10% memory to "high". "high" sorts them via no extra memory sorting algo.
If none of those condition holds, go to final step.
Even Step is similar, but "low" and "high" send 15% of memory worth to "mid" and "mid" sort after getting from both. (Note that on the second time odd step also can use 15%)
Final step. "Low" and "high" know the grand size of array from init step so they know if they are less than 1/3 or more. So does "mid". So they can unambiguously determine who sends and how many to make up 1/3 at "low" and "high"
On coordination. Each player know when is even step or odd - if they received, now is their turn to send. In addition, a peer does not have to wait for the disjointment on the other side, it can proceed to the final step as soon as it determines disjointment.
@autoboli, let's just talk about simple version for the time being. It seems to me you are talking about extending selection from k-1 elements to selection from k elements. Each element has 1/k probability to be selected, including the last one, I got this part about the last one, it will be selected with probability 1/k. The other ones will be selected with probability (k-1/k)/(k-1) =1/k, Wow, it works ...
- CT January 27, 2015n log n solution:
Separate negatives from positive and if encountered 0, return true because of tripple 0. Sort postive and negative by absolute value. This is most time consuming step - n log n.
From now on, treat all numbers by absolute value and lets consider them as two sorted arrays.
Take the last element of first array and attempt to find two elements on the second array with the sum equal to that element. It is well know how to do that, peek up two elements from both end and walk down higher one if sum is bigger, walk up smaller one if sum is smaller. You can meet at the same index, in which case take the double. If cannot find pair this way move down to the next in the first array but you can continue in the second array where you left off (with minor adjustment).
Repeat same logic for these two arrays, but swap in which one we select one element and in which two.
The entire solution fits into 32 bit int (every number is 2 bits). The row fits into one byte. Only 24 (out of 256) possible byte values a valid rows. Rows cannot repeat in the same solution, so permutate 4 different rows and note wich permutations are valid solutions. That is 24x23x22x21 about quarter of a million permutations.
Now, we can do better than that. Let's say rows are conflicting if at least one of the numbers is the same at the same positions, such as:
1234
and
3241
are conflicting because 2 at second position is the same.
1234
and
3421
are not conflicting.
So, when we do the permutations, when we loop through second row and on, we can select rows that are not conflicting to the previously selected. This will enourmously reduce amount of permutations and in addition we would have to validate only subsquares.
It can be an interesting to note that there are only 14950 versions of sorted s. 26!/(4!22!). Knowing Google: no matter what your solution is, I am certain that Google would want to hear this before you even attempt to discuss efficiency of your algorithm. Also, knowing them, they gave the 4 letters in the condition for reason.
The only reason I am saying this - review and practice combinatorics in preparation to the interview. I think they want you to see it approximating on the whiteboard : 26!/(4!22!) = 26*25*23, roughly 30*25*20 which is easy to calculate in the head.
@zortlord, Your excellent verification program actually assured me this is O(n). At depth 10 number of nodes to iteration ratio converges to 0.40: 2^10 - 1 nodes divided by 2537 iteration.
At depth 15 it still stays 0.40: 2^15 - 1 nodes divided by 81887.
Because nodes to iteraton ratio converges and does not change after convergance, we can surely say that number of nodes is assymptotically proportinal to number of iterations, which implies O(n).
This is really good way to verify algorithms, I am surelly up-voting your verification driver.
Create sorted key to exact match map for keys length 1, 2, 3, 4.
For instance, aab={baa,aba} but not ba
Create a multi-root tree where 4 letter keys are roots, and up to 4 children are generated by removing one of the letters. (could be less because in aabc remove a once) - similarly for other children until have one letter grandchildren leafs.
Note, that this is not really a tree but a graph because abc is a child of both, aabc and abcz, so the amount of nodes will not exceed one million.
Walk it from 4 letter key till one letter and collect set of words.
Why is it better than just computing all of the words for each of the 4 letter keys, including subsets. The thing is, 3, 2, 1 letter keys are shared across path, so less repetition. And they can be loaded/unloaded on demand, per memory requirement (for instance, un-load lest frequently walked node). Note that the set of words for exact 4 letter match will be small, it is subset that will generate a lot, and they are shared.
There is a way to solve it in O ( n + m ) which is loosely based on Quick Select ( Note: Not Quick Sort )
- CT December 28, 2016Select random element in first and second array.
Move all smaller element of first array left, bigger right.
Move all bigger elements of second array left, smaller right.
If the difference of the two elements is negative, recursevilly work with left parts of both arrays
If the difference of the two elements is positive, recursevilly work with right parts of both arrays.
(In case exact 0 that is a perfect diff)
Note: include this pivot pair in those recursive sub-arrays because it may be best pair and must be considered too
Ending conditions: one of the array parts has two or less element, in which case brut force solution, which will be O ( p ) where p is the size of the larger ending sub-array and therefore should not affect the performance of the whole algorithm.