CareerCup

Maximum distance between 2 nodes in a binary tree is nothing but the "diameter of the tree".

this will not work. for example.

arr[] = {1, 5, 10, 8, 9}
Output: 5*8*9

but with max-heap approach we get 10*9*8. The important point is the subsequence has to be in ascending order.

This looks to be a variation of longest increasing subsequence problem.

In the worstcase wont the root of the tree be the "LCA (least common ancestor)" of any 2 nodes in the tree? Wouldn't that mean that 2 people are ALWAYS related somehow?

General approach for this problem is to use circular linkedlist.

Just using a plain circular linked list will give O(kn) complexity. if k=n, that would lead to O(n^2) complexity. Something like this -

struct node *r = root;
struct node *todelete = NULL;
for (int i=n; i>0; --i)
{
    for (int j=0; j < k; j++)
        r = r->next;

    todelete = r->next;
    r->next = r->next->next;
    free(todelete);
}

This is due to the traversal we do every loop to reach the kth node. So finding a way to remove this traversal each time.

Use a array which has random access. Create array of length n and store all n elements in them. At each position of the array store the data. start the deletion process. in each loop jump to that kth location & delete that data. Incase we goto a location with no data (it might have already been deleted), then shift one place to right & see if there is data there. And so on... This approach is somewhat like "openaddressing hashtable collision resolution approach".

Time O(n), space O(2n)

dont think this will give correct answer. Once you sort both arrays, you have lost original order. Without the original order BST shape would be impossible to find and compare...

+1 for the anonymous solution posted above. I thought of typing the same... Sigh...

using arrays in place of linked lists might lead to lots of copying of data in case of deletion. Just a thought...

Can't this be done using a simple function? Maintain a single global hash having location=>shipping cost. Cache this hashtable for good access speed. Now, have the web interface pass the baseprice + location to this function. This function accesses the hash, calculated the total price & done.

What could be wrong in this approach? Isn't having Singleton Class an overload? The class has to check each time if an instance of the class already exists etc. When there are millions of transactions will this not harm the speed?

check this out - stackoverflow.com/questions/3531606/convert-binary-tree-bst-maintaining-original-tree-shape

For friends using Graphs as data structures seem a better option. hence forth referred to a YY.

1) Adding a friend needs an approval process, hence once someone adds X as a friend; we send an invite to X that you are interested. It means, updating the cache layer (so that you don't end up inviting the same person more than once) plus DB that an invite has been sent.

Deleting on the other hand has to instantaneously make changes to YY. Probably notify the friend that he has been deleted from your friend list.

2) Friend suggestions - is basically recommendations.
-> maybe you are from the same school/college/workplace etc. (distance 2)
-> maybe friends of friends from same school/college/workplace etc. (distance 2)
-> maybe you are a friend of your very popular friend.
-> import email addresses from your Gmail or other mail accounts.
As one can see all this recommendation list can be done offline & needs to be accessed when the user logs in.

3) Point mentioned by Akshat seems ok here.

In Facebook's infrastructure ALL (or most of it) exists in cache (i.e. RAM) for faster access. So one of the biggest challenges is to sync data between this cache layer & the actual mysql DB.