wealthychef
BAN USERHow do you do it with bet vector? I see this idea here occasionally and am not familiar with that approach.
- wealthychef June 25, 2012This is not the edit distance. You cannot use substrings of each word if they are not dictionary words. And you are not constrained to use substrings as in edit distance. You just need a kind of "hamming distance" arrangement of the dictionary.
- wealthychef June 25, 2012How would one make an efficient pass through the dictionary and create an adjacency graph? Perhaps you'd have to make m tries, each rooted at a different char position in each word?
- wealthychef June 25, 2012You definitely need to clarify the "cannot move data between machines" thing. For any parallel algo to work, you need to send messages.
- wealthychef June 24, 2012The question is not "how many numbers have a given popcount." Read again.
- wealthychef June 24, 2012LOL -- you're applying for a job at Google, and you couldn't be bothered to google for "popcount number." I find it ironic. :-)
- wealthychef June 24, 2012There are multiple errors in this code as I walked through it. But it was useful for understanding. IMO the logic should be
for (int j=1; j<=N; j++) {
// if we just use the previous row, we will have one more cent left over
C[j] = C[j-1] + 1;
for (m=0; m<len; m++) {
track[j][m] = track[j-1][m] - 1;
}
// try to do better by spending a coin from an earlier solution
for (int k=0; k<len ; k++) {
if (j >= D[k]
// row j-D[k] contains a solution
&& (track[j-D[k]][k] > 0)
// row j-D[k] has a coin of denomination k available
&& C[j] > C[j-D[k]]) {
// the solution from the earlier row beats our current best in this row
// copy all values from earlier row:
for (m=0; m<len; m++) {
track[j][m] = track[j-D[k]][m] - 1;
}
C[j] = C[j-D[k]];
}
else if (j < D[k] ){
track[j][k] = track[0][k];
}
}
}
The linked list/trie combo approach above successfully captures the first unique URL.
- wealthychef June 17, 2012Storage is going to be O(n) -- but a hash table is not as space efficient as it has to store the entire string in case of collision, but in all partial matches are collapsed together, no?
- wealthychef June 17, 20122+3 and 3+2 are not unique combinations. Did you mean permutations?
- wealthychef June 17, 2012I think you might manage O(m-n) where n is the length of all the duplicates. The reason is that you can divide and conquer and get a lot of early terminations early when you see the beginning and end of a substring are equal, and pass that fact up to a parent to use sometimes on a sibling. So if n is a large number, it could knock the runtime down a lot.
- wealthychef June 17, 2012Yes 8^n
- wealthychef June 16, 2012We are being asked to create a complete ordering from a partial ordering. Each race gives you a
Here's what I would do under pressure in an interview:
1) Build a min heap -- O(2n) = 100 races
2) Search for the 25th smallest car by repeatedly removing the min 24 times, O(24*log(49)) == maybe 125 races.
So maybe 225 races, ballpark. You could store results with adjacency lists and maybe save some races if you value fuel over space complexity.
LOL -- how about failing the interview because you made a ridiculous simplifying assumption and showed you prefer not to think deeply in the mathematical sense?
- wealthychef June 16, 2012I agree; you are basically saying you need more information. In a real Google interview, if the question was posed like this, I would ask how many cars can race per track. This is a trivial solution and you know they would not ask it this way.
- wealthychef June 16, 2012I would cull to avoid n^2:
1) convert all points to miles of course
2) Sort points by X and by Y.
3) Go through points in order of X. Using a sliding window, draw a directed "X edge" between points that are within n miles of each other in X.
4) Do #3 with points in order of Y, connecting them with directed "Y edge" relations.
5) Go through all points, for each piont, if it has an X and Y relation TO a neighbor, then compute that distance and if it's close enough then print out that fact.
This is very likely to be O(nlogn) unless the distance is large or points are all very close.
1. Yes, but high-low is smaller than high+low, and so is low + (high-low)/2. If high and low are big numbers, then you don't want to add them or you could get overflow
- wealthychef June 16, 2012Clever but not recursive. It's dumb but they want recursive.
- wealthychef June 16, 2012The whole idea of using recursion to find Fibonacci seems stupid. You are going to run out of stack space on large numbers. This should be done in a while loop.
int fib (n) {
int fibs[2] = {0,1};
if (n==1) return 1;
while (n-- > 1) {
new = fibs[0] + fibs[1];
fibs[0] = fibs[1];
fibs[1] = new;
}
return new;
}
All these bitsum solutions are just a form of hash table. I dno't understand the interviewer claiming a hashtable is too large. It doesn't have to be.
- wealthychef June 16, 2012What if sum is negative?
- wealthychef June 15, 2012LOL -- we are both wrong, because I can show you five ways to do it with 6 nodes.
1: 0-1, 2-3, 4-5
2: 0-5, 1-2, 3-4
3: 0-1, 2-5, 3-4
4: 0-5, 1-4, 2-3
5: 1-2, 0-3, 4-5
No, with 6 points in the circle, there are 4 ways
- wealthychef June 12, 2012Problem statement implies that every point is used in the solution.
remember[n+1] = {0}; // solutions for smaller circles with 2n points
remember[1] = 1;
remember[2] = 2;
int HowMany(int n) {
if (remember[n]) return remember[n]; // efficiency
int i = 0; // i is the distance between the endpoints of our chord
// now test every chord and subdivide
for (i=1; i<2n-1; i+=2) { // cannot connect an even number of points away
inside = i-1; // number of points on one side of the chord
outside = 2n -2 -inside;
count += HowMany (inside/2) + HowMany(outside/2);
}
return count;
}
Actually, I think the constraint of equal size makes the problem easier. You can partition the problem into two arbitrary halves, and then start exchanging elements. After each exchange, you see if the problem is solved, if not, you recurse on the remaining n/2-1 elements for each side. You could use memoization to prevent repeated computations. I think this avoids an NP complete problem, no?
- wealthychef June 26, 2012