Chih.Chiu.19
BAN USER@om
Hi, well, to be honest I am a bit puzzled by your comment, lol. Ok, maybe I did not express myself clearly, let me use your example for illustration.
So the tree we want to construct is 5, 10, 8, 20, 6, 7, 4.
1) Get 5, update max=5.
5
2) Get 10, put the previous tree as the left subtree of it, update max=10.
10
/
5
3) Get 8, recursively call itself to construct a tree with capacity=8. Now we have two trees, although the second one only exists in the recursive call. For the second tree max=8.
10 8
/
5
4) Peek at 20. 20 is larger than the capacity 8 for the current recursive call, so the call finishes, and it returns the tree it generated, which (8) here, and the upper level function will put this tree as the right subtree for its max=10.
10
/ \
5 8
5) Get 20. The previous tree will be used as its left subtree. Update max=20.
20
/
10
/ \
5 8
6) Get 6. 6<20, so again a recursive call is made to construct a tree, capacity=20.
20 6
/
10
/ \
5 8
7) Get 7. 7>6 so 6 is the left subtree of it. Also updates the max for the second tree to be 7.
20 7
/ /
10 6
/ \
5 8
8) Get 4. 4<7, so another recursive is called to generate tree starting with entry 4.
20 7 4
/ /
10 6
/ \
5 8
9) No more entries. The bottom level call finishes, and the tree {4} will be used as the right subtree for the tree {7,6}.
20 7
/ / \
10 6 4
/ \
5 8
10) The next recursive call finishes, and the subtree it returns {7,6,4} will be used as the right subtree of 20.
20
/ \
10 7
/ \ | \
5 8 6 4
I hope this is clear :)
- Chih.Chiu.19 July 27, 2013@vgeek
How about building the tree bottom up ;)
The idea is to have a helper function
buildStartingAt(int[] entries, int i, int capacity)
that reads the array left to right starting from location i and build the tree bottom-up, but when the next read entry exceeds the given "capacity", it stops and returns the index to the next entry, as well as the tree that it has built. What it does is to keep reading entries until the "capacity" is exceeded or the array is exhausted. It keeps the maximum of all the elements it has read so far, and for each newly read entry it compares it with the stored maximum:
Case 1) The new entry is larger than the maximum. Then the new entry should be used as the root to a bigger tree, and the so-far accumulated tree should be its left subtree.
Case 2) The new entry is smaller than the maximum. Then the new entry belongs to the right subtree of the node that contains the current maximum. Call the helper function recursively to generate the right subtree, using the stored maximum as the capacity for this call, then move on.
This only takes O(N) time!
@vgeek
Thanks! So your solution is essentially the same as blackfever's one, right? (Well, he gives no code but...) So the time complexity is O(N^2) in the worst case, O(N lg N) on average, right? How can I improve it?...
@vgeek
Hi, sorry I still do not understand your algorithm, could you explain it more please? Also, what's your time complexity? Thanks.
@oOZz
It's O(N^2) in the worst case: finding maximum for each recursion takes O(N), in the worst case O(N) recursions; O(N lg N) on average: O(lg N) recursions = height of the tree when input is randomized.
@ashot madatyan
I forgot to say that I really like your code a lot, not only because it is well formatted, but also it is well commented, tested, and it has a short but precise explanation block for the algorithm that comes with it --- thanks a lot!
@ashot madatyan
Nice solution! Just curious: what's your approach to find two missing numbers?... Thanks.
@oOZz & ashot madatyan
Hey, oOZz is right about the bound: because even in your solution below (it is cool btw, and I already bookmarked it :)) you need to know the lower bound of the array, right? Then instead of summing the entries of the array directly you can just sum (entry-lower bound) which will fits into the INT range (well, unless N is extremely large...)
@oOZz
Nice! Just one question: is the name "Saddleback Search" your invention or it is commonly used?...
This is essentially the "merge" step in merge sort (for the k-merge problem), but which starts from the end of the array instead of the head of the array, and which stops when there are 5 elements already. So the "officially suggested" solution uses a max heap of size 3, and in each step it extracts the maximum, then fill the blank with the next element in the array that extracted max belongs to.
- Chih.Chiu.19 July 26, 2013@oOZz
Hey, but your solution is O(N^2), while the solution given by om is only O(N). However I totally agree with you that calling om's solution as "DP" is an unfortunate misuse of the language. lol.
@LinHA05
Agree! Not only is the DP solution not any faster, but also its code is not any shorter... The simple solution you suggested is a O(N^2) solution btw.
@Anonymous
Nice! I didn't think about it. I actually think the easiest solution is to append the points with angle < alpha to the tail of the polar angle array, then the rest of the algorithm need not to be changed. There is a waste of memory alpha/(2*pi)*N, though...
@Akbar-The-Emperor
Thanks. Just to be sure, you consider the matrix to be N by N, right? Then the algorithm is O(N^3), since you are enumerating all the elements of the matrix and for each (i,j) value and you check the sides of the square.
As for the diagonal traversal, I still think it does not save much time; in fact the column scan algorithm given as the solution to problem (20.11) in Craking the Coding Interview looks fine to me, and I do not see how using diagonal traversal will help to make the code any faster or cleaner. Care to elaborate a bit more? :)
@vgeek
Thanks for the reply, but two questions for you:
1) Could the word "post-fix" possibly mean something else here? I really don't know... I looked it up and it seems to me it is only used when representing an algebraic expression, so I assume it is the "post-order" that should be used here.
2) If I am correct, why do I get two "-1"? LOL
This is not a O(N) algorithm, is it?...
- Chih.Chiu.19 July 23, 2013First of all let me clarify the question: my understanding is that the tree generated by *postorder* traversal is given by the "i"-"l" array (or what exactly does the post-fix mean here?). If this understanding is correct, the following is my solution.
First of all it is easy to see that the last element of the array is the root. Then the difficulty in the recursive call is to separate the left subtree from the right subtree. To do so note that any tree has (number of "i") == (number of "l") - 1, therefore we can scan from the 2nd from the last element backwards and count the number of "i" and "l", until we have the condition (number of "i") == (number of "l") - 1 satisfied, and this will be the right subtree, and the rest is the left subtree.
@Some guy & Ayahuasca
Nice! However let me challenge your idea of using tries :)
How can you efficiently and correctly solve the "non-overlap" criteria? <Some guy>'s solution does not address the non-overlap criteria between the head string and the middle string (if I understand correctly, at least not in a very efficient way), while <Ayahuasca>'s solution is, pardon me if I am wrong, not correct: the desired string may appear twice in the range (1,n/3) and once in (2n/3,n), right?
You can first calculate all the polar angles (btw by arctan2, not arctan ;)) then sort them, then do a "slide window" scan like this: you keep a pointer to the left boundary and a pointer to the right boundary of a region whose opening angle is less than alpha. If the opening angle is less than alpha, increase the right pointer, otherwise increase the left pointer, and keep track of the max number of elements inclosed in this process. The angle of the point pointed by the left pointer in the final max-including cone is your beta.
- Chih.Chiu.19 July 23, 2013How about this: we first sort the array according to the values A[i] into B, while keeping the index information so that if A[i] is the j-th smallest element in A, then B[j] = i. Then the question becomes: find two elements B[k] and B[l] in B so that: (1) k < l (2) B[l]-B[k] is maximized. This is just the one-time-max-profit-stock problem (see Introduction to Algorithms), which can be recast into a "maximum subarray" problem.
- Chih.Chiu.19 July 23, 2013@Ayahuasca
Hey nice. First of all a quick check: this is a O(N^3) solution, right? O(N^2) spent on the traversal on diagonals and O(N) on checking the validity of the square, right?
Second, why take diagonal traversal? Why cannot we just pick a pair (row, col), use it as one corner of the square, then check if the square is valid for a given size? This also takes O(N^3) time (and this is (20.11) in cracking the coding interview). Is there any benefits gained from the diagonal search? Thanks.
@me.mrig & anirudh
Good point. Somehow I did not see anirudh's reply.
@Guru
Actually I think the "merge" step in the merging sort is not much different from what we are doing here. Think this way: we can first merge the two arrays into one, then we just need to compare the distance between adjacent elements in the merged array. This takes 2*N time. Then we realize that we do not need to store the merged array and the calculation of the distance between adjacent elements can be done "on-the-fly", and this reduces the time to 1*N and it is essentially what me.mrig gives...
@eugene.yarovoi
Yeah you are right, I did not see that they are already sorted :)
Hey I happen to saw this algorithm is an open course: first sort array 1, then for each element in array 2, use binary search to find the element in array 1 that forms the smallest gap with it, store it, then look for the minimum among all such differences. The algorithm takes O(n lg n) time.
- Chih.Chiu.19 July 22, 2013Hey, these are standard DP problems. Identify each subproblem as the number of ways you can reach the location (k,l) starting from (0,0), then it can be calculated as the sum of the number of ways reaching (k-1,l) and (k,l-1), and you can use either bottom-up approach or a top-down memorization approach to solve it. When there are blocks, you just need to put additional checks inside the code before you sum them. These questions are given in LeetCode Online Judge that not only allows you to type in your (Java or C++) code in a panel, but also checks if it is correct and if its performance is not exponential.
- Chih.Chiu.19 July 22, 2013Agree! However how can you show that releasing the constraint from asking a cover of the whole set to asking a cover of at least k elements still generate a NP-hard problem? (I can't)... For example for k=1 it is not (but for k=n it is) :)
- Chih.Chiu.19 July 22, 2013@Ayahuasca
Hi, nice catch, but your suggestion does not work either. For example the probability of taking
4 = 2+2 = 1+3 = 3+1
if different from the probability of taking
2 = 1+1
(I skipped your "-1" here).
However you could use multiplication to maintain the equal-probable condition.
In fact this problem naturally takes two steps:
1) How to generate a random number in [0,M-1] given a generator randN giving results in [0,N-1] with N>M?
Answer: use randN() % M but discard the last N - (N / M) numbers (see Ayahuasca's solution).
2) When M>N.
First generate uniformly distributed random variable using randN()*N + randN(), this function generates random numbers in the range [0,N^2-1] with equal probability; then the problem goes back to 1).
@Learner & Y! engineer
Why not just create a HashMap<Person, Page>?... Why page id is so important here?
@Nitin
Nice. I actually start to think that the question is ill-posed, for the following reason: we need to know the probability distribution for the breaking-egg drop-height in order to optimized the search process. In the finite number (N) of floor case the implicit assumption is that (I think) any number ranging between 1 to N is equally probable. However in the infinite number of floor case the "equal probable" assumption does not apply any more since it cannot be give a well-defined probability distribution density that sums up to 1. Having said this, I think the most probable interpreting of the problem is that "for any given and finite N, how to determine the breaking-egg drop-height". For this I do believe that except for extremely small N, the doubling scheme is better than the tripling scheme, since after you have broken the first egg which requires O(lg(N)) tries, you need to do a linear search using the (only left) second egg, which requires O(a^(i+1)-a^i) tries, with a being 2 or 3, but a=3 has a much larger "gap" to be filled than a=2.
@Ayahuasca
Ok I see what you did now. You are right :) I was just confused by your "flow chart" table at the beginning, since for no situations will we have a configurations like that. Anyway, I see now that your solution is correct, thanks.
Haha you are right :) Ok, fine, here is my first draft of the code in Python...
def generatePath(source, target, n): # source, target = (i,j); n=size
travelled = { target: target} # { child : parent }
bufferQueue = [target] # backward search
while bufferQueue:
underProcessing = bufferQueue.pop()
if underProcessing == source:
return travelled
for eachNeighbor in getNeighbors(underProcessing, n):
if travelled.has_key(eachNeighbor):
continue
else:
travelled[eachNeighbor] = underProcessing
bufferQueue.append(eachNeighbor)
return {} # no path
def getNeighbors(location, n):
neighbors = []
i, j = location
for k, l in ( (i+2,j+1), (i+2,j-1), (i+1,j+2), (i+1,j-2), (i-1,j+2), (i-1,j-2), (i-2,j+1), (i-2,j-1) ):
if k>=0 and k<n and l>=0 and l<n:
neighbors.append( (k, l) )
return neighbors
def printPath(source, paths):
if paths:
while paths.has_key(source):
print(source)
if source == paths[source]:
return
else:
print("-->")
source = paths[source]
if __name__ == '__main__':
# test
source = (1, 2)
target = (2, 5)
printPath( source, generatePath(source, target, 8))
Output (from (1,2) to (2,5) in a 8x8 board):
(1, 2)
-->
(0, 4)
-->
(2, 5)
@vgeek
Hi, nice solution! Just one question: Why the indexes helps here? Why not just use hash set?... Thanks.
Look, you starts your BFS from the "source", and terminate it at the "target", the path is the one you want, and it is also guaranteed to be the shortest path... right? To generate the path at least you could copy/paste the "predecessor tree" idea from Introduction to Algorithm book, or find your own clever ways. Also you can use any data structure to store the position on the board, ranging from int[2] to class() { public int x; public int y; } to the ones using getter/setters, to simply (x,y) in Python --- your choice :)
- Chih.Chiu.19 July 19, 2013Hold on... there is no such thing as "overlap" in knapsack problem right? But here overlap need to be considered.
- Chih.Chiu.19 July 19, 2013I am *suggesting* one... write a short function returns the up to 8 possible locations a knight can travel to from a tile as the "neighbors" of that tile, then call any standard BFS will do the work. The rest is just... coding.
- Chih.Chiu.19 July 19, 2013BFS?
- Chih.Chiu.19 July 19, 2013I believe the problem was not correctly interpreted: a glass can only fill the one below it *if* it is full! Therefore it can never happens some glass 5 is non-empty while glass 2 and 3 are only half filled.
- Chih.Chiu.19 July 19, 2013Nice!
- Chih.Chiu.19 July 19, 2013Man this is a super slow implementation... in fact, I cannot even find other ways to make it even slower... lol
- Chih.Chiu.19 July 19, 2013As pointed out by vstudio, using topological sort will have vertices ordered in a nice way. However I do not see how the level info can be extracted easily. The following is what I propose:
For any "node" (like a, b, c, etc.) attach it with a level index and a list of its direct parents.
For each read in new relationship, if the given parent does not have a level index then use the child to determine the level index for both, or 0 and 1 if neither has appeared so far; if the parent already has a level index, use it to determine the level index of the child --- if the child already has a level index too then update the level info for this child, and all its parents (and parents' parents recursively) using the parents list attached to this node.
Finally *stably* sort all the nodes according to their level info then print them out.
Note that here I assume the inputs are reasonable: not only it must be acyclic, but also it cannot contain data like: <a,b> <b,c> <a,c>.
Hey, your solution ultimately replies on the fact that for any nut there is a bolt that matches it, but I think this assumption is not true for all the bolts, at least since N is not M. You could get around this by using a random algorithm which keeps looping until one bolt is found such that it has a matching nut, but then what if only 1/10 of the nuts have matching bolts? So 9/10 of the times your step 2) which relies on the *existence* of a match is very inefficient.
- Chih.Chiu.19 July 17, 2013@varun:
Hi, Sibendu is asking you *how* you can sort the array in O(n) time with O(1) extra storage space. I am interested too. Please tell us how this is (roughly) possible... Thanks.
Btw nice solution!
Could you clarify your question please?
- Chih.Chiu.19 March 09, 2013The comparator is easy to implement since all classes implementing List interface have the indexOf function; however my conversion between char[] and Character[] is really messy here... Anyone get a better idea?
- Chih.Chiu.19 March 01, 2013Using comparator in java:
import java.util.*;
public class CustomizedDictSorting {
public static void main(String[] args) {
Character[] dict = {'c', 'b', 'a'};
System.out.println(sortStringUsingCustomizedDict("abccc", dict));
}
public static String sortStringUsingCustomizedDict(String s, Character[] customizedDict) {
// two versions of char array
char[] charList = s.toCharArray();
Character[] characterList = new Character[s.length()];
// char -> Char
for (int i=0; i<s.length(); i++) {
characterList[i]=charList[i];
}
// convert dict to arry
final List<Character> customizedDictArray = Arrays.asList(customizedDict);
Arrays.sort(characterList, new Comparator<Character>() {
public int compare(Character a, Character b) {
return customizedDictArray.indexOf(a)-customizedDictArray.indexOf(b);
}
}
);
// Char -> char
for (int i=0; i<s.length(); i++) {
charList[i]=characterList[i];
}
// get return string
return new String(charList);
}
}
The difficulty is indeed to achieve log M + log N efficiency and it is not trivial at all.
- Chih.Chiu.19 March 01, 2013No no no... you don't know if the wrong one is heavier or lighter.
- Chih.Chiu.19 February 27, 2013This algorithm is wrong... isn't it? For example assume the word that contains all the given letters is "bbbbbbbbbbaeogzkljwn", how does your algorithm go into the branch of the tries starting with "bbbbbbbbbbb"?
- Chih.Chiu.19 February 27, 2013
@Anonymous
- Chih.Chiu.19 August 02, 2013Agree! But I guess you need to explain it a little bit...
Ok, the point is that, first assume n>=2 and m>=2, in this case you can convince yourself that the Alex has no difficulty moving to the bottom of the table, but
1) He can continue doing similar movement to the right if n is odd.
2) He is stuck at the bottom-left corner if n is even.
In case 2) the tiles he cover is 2*n; in case 1) he can move all the way to the right, then he is facing the situation just like before: 3) if m is odd he can continue to move upwards, 4) otherwise he is stuck in the bottom-right corner.
In case 3) the problem actually reduces to a smaller size problem if you rotate the board by 180 degrees, and Alex eventually can travel anywhere on the board.
In case 4) the number of tiles he travel is 2*n + 2*(m-2).
Finally, you need to take care the boundary cases when n==1 or m==1, which is not hard (see Anonymous' solution above).