barcod
BAN USERLinked list is not space efficient. Also keep in mind that Facebook needs to serialize this data to persistent storage and read from there as needed. They may have had that in mind when asking the question. I wouldn't be surprised if in reality likes are read and displayed without being kept in memory at any time so the discussion of in memory data structures may be irrelevant.
- barcod January 19, 2013Solution does not exist. For a log(n) solution, you need to visit each level a constant number of times without traversing all the nodes, effectively eliminating as you go. Elimination is not possible in this case.
At the beginning, you are at the root and you can't have any idea where to go. You pick left or right. Without traversing all the nodes in that subtree, you can't even know if you are in the correct subtree. Getting the number of nodes there is already O(n). That's why Log(N) is impossible.
I think this question was meant to be asked for a complete BST.
Assuming this would be kept in a circular linked list, traverse it once and collapse vertices as you see addition operation. After the first pass you will be left with only multiplication edges. In the second pass do the multiplications and the result is what you are looking for.
- barcod January 16, 2013The error in the method quoted is probably the inability to generate all the numbers. You'd end up generating something like '5, 4, 5, 2, 2, 4'. This solves that problem:
// rand (m) returns a number between 0-m inclusive
int * randomize(A, n){
for(int i=0; i<n; ++i){
int k = rand(n-1-i);
B[i] = A[k];
A[k] = A[n-1-i];
}
return B;
}
Inner, left outer, right outer, full outer, cross join. You can also use query hints like "left outer hash join" where hash denotes how you would like to hint the query engine compute the join. Other hints are loop, merge and remote. These are just hints so there's no guarantee the engine will use it.
- barcod April 12, 2011
Reppaynealiciam, Apple Phone Number available 24/7 for our Customers at Adap.tv
Hello I am Sarah Cote, and I live in Missouri, USA. Last year, Web trailblazer. Passionate entrepreneur. Subtly charming bacon ...
Repjosephcday6, Android Engineer at Absolute Softech Ltd
I am SEO Executive in Elek-Tek company. I live in Morgantown USA. I won’t write any details about Best ...
You can easily keep millions of userid's in memory. Assume 64bit unsigned number represents a user id. If 1 billion users are online at a given time, that is 1 Billion * 8 Bytes = 8GB of data. Assume next pointers cost another 8GB, that's still 16GB. But I think the answer they were looking for was the distributed solution.
- barcod February 22, 2013