heorhi
BAN USERThis problem has a precise solution.
1. We get rid of speeds by switching to time. For each lane we calculate the time intervals, when there is no car in this lane.
2. Having the time intervals we do simple search:
a) for the first lane, a frog can appear at the lane at any moment when there are no cars (i.e., all intervals);
b) knowing which intervals are accessible at lane i-1, we can easily calculate when a frog can appear at lane i: we simply intersect the accessible intervals at lane i-1 and "no car" intervals at lane i;
c) finally, if there is at least one interval accessible to a frog at lane n (the last lane), then the road can be crossed and vice versa;
The complexity of the solution is linear to the number of cars.
I think, your analysis is nice, but I am pretty sure you cannot replace O(m*n*2^k ) by simply O(2^k) since. By definition, then you must be able find some constant c such that c*2^k > m*n*2^k for all n,m,k. But this is not possible since n and m are parameters that may scale up to infinity. Unless you state explicitly the correlation between k,m,n, you should not better make this kind of simplifications...
- heorhi September 14, 2014This is a typical trie problem (for details, you can read about Trie in WIkipedia).
Let the number of words be n and the number of characters be m.
The solution is the following:
1. You build a trie from the dictionary words of length <=m (other words are not of interest since they definitely cannot be built from m characters). This will require O(n*m) time and O(n*m) space;
2. You use character set to explore all possible words. You assume that first letter can be any in the set (m possibilities) then you explore m-1 possibilities for each of them and so on. Even though it might look like O(n!) but in reality, each of the node of the trie will be touched only ones, that is the overall complexity will be O(n*m);
As a rule, trie is difficult to beat in problems like this, so I believe it to be optimal.
Trie is a well-defined thing, so please check it out to understand the details of the solution... (you anyway need to do so if you really wish to succeed in Google job interviews%))
Two ways come to my mind:
1) Memoization. Use caching to prevent recalculations. Every time you need to calculate F(m,n) first checki in cache if the answer exists. Then you won't recalculate. If the answer is not available, calculate it and then store in cache. SO you will avoid exponential growth by guaranteing that no calculation for m,n is performed twise. The obvious disadvantage is memory usage which can be as much as O(xy).
2. The second (much better) solution is to use recurrent statement in the conditions above, to derive a simple formula for immediately returning a solution without any recursive calls. As far as I can see (using simple 2D coordinates), if m>=n F(m,n) = (n+1) * n - n - 1; if m < n F(m,n) = (m+1) * m - m - 1 + (n - m);
If the question is how to print a powerset, it can be done extremely simply. I will demonstrate by example.
Imagine you have set {a,b,c,d}: then each element of a powersent (i.e., subset) can be encoded with 4 bits, each bit showing if a corresponding element participates in a subset: 1011 encodes {a,c,d} and 0011 encodes {c,d}. All possible subsets can be found by looking through all possible combinations of bits. It can be done by simply counting from 0000 to 1111 and printing a corresponding subset for each number. You can see that it will encode all 2^4 subsets. You can straightforwardly extend it to any set of n elements.
The same idea, more readable code with comments
public static String longestPrefix(String s) {
// get all words
String[] words = s.split(" ");
// initial prefix length is set to the length of the first word
int prefixLength = words[0].length();
// iterate through the remaining words checking the prefix
for(int i = 1; i < words.length; i++) {
// if the length of ith word is less then prefix so far,
// prefix cannot be longer then that
if(prefixLength > words[i].length())
prefixLength = words[i].length();
//check charachters one by one and break on differing charachter
for(int j = 0; j < Math.min(prefixLength, words[i].length()); j++) {
if(words[i].charAt(j) != words[0].charAt(j)) {
prefixLength = j;
break;
}
}
}
return s.substring(0, prefixLength);
}
I tried to find a smart solution but in the end they all fail... I think an "intelligent brute force" in the for of DFS has to be used here. Imagine that your digits are in array A of digits. My algo is generally the following:
- heorhi October 06, 20141.) you sort your digits in descending order, with this you receive the biggest possible number for this digits M.
2.) Your target number will have common prefix with this one (since the primary target in k swaps is to maximize the most significant digits);
3.) Now you start your dfs from the most significnat number(say, A[0]), if it is the same as M[0] you try to maximise the remaining 1..n-1 digits with k swaps. If it is not equal to M[0], you try to swap it with any digit in A that equals M[0] and for each such swap solve a subproblem for 1..n-1 digits with k-1 swaps.
4.) as soon your arrive at a problem with 0 swaps you check if the current number is the largest number generated so far, and if so, memorize it.
Although this solution has very roughly estimated complexity of O(n!/(n-k)!) (where n is the number of digits, and k is the number of swaps), I believe that the in-depth math analysis would prove it to be much faster. One more point is to involve dynamic programming, but this seems to work at the cost of very high memory consumption.