## manidam07

BAN USER- 0of 0 votes

AnswersSuppose there is a social networking site like Facebook. Every user gets some friend recommendations (i.e. People you may know!). Now, if there is a user A and he has 100 friends and each of his friends has got 5 other friends,A can get these 500 recommendations. But the condition is that he should only get the top 10 recommendations with whom he has the maximum number of mutual friends(If A and B are friends and B and C are friends, then A and C have a mutual friend, B). Suggest an efficient data structure for this and how to implement it. The implementation should be flexible as at any moment, any user can make new friends and he may also unfriend someone!

- manidam07 in India| Report Duplicate | Flag | PURGE

Amazon Software Developer Algorithm - 1of 1 vote

AnswersGraph problem:

- manidam07 in India

Critical node: If a node reaches another node only through one node.

Eg: A-C-B and A-E-B are critical nodes. (A reach B through one node which is C or E)

If A reaches B through more than one node, then they are not critical nodes.

1) A-C-B

A-D-E-B (A reach B thro C which might lead to critical node but A has another path to B thro D and E, so they are not critical nodes).

2) X-Y-Z

X-A-Z (X and Z are critical nodes)

Now find all critical nodes.| Report Duplicate | Flag | PURGE

Amazon Developer Program Engineer Algorithm - 1of 1 vote

AnswersA Matrix of 1s and 0s is given, all zeros are water and 1s are land, first find out the number of ponds in the array (Reverse of islands problem). If one change can convert 1s in to zero then find out minimum number of changes that we need to make so that there will be only one pond in matrix..

- manidam07 in India for ICE

Any algo how to make 1 pond ?| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer

By using X(X+1) = 2*N i am trying to find sum of natural numbers.

For Ex if N is 6 then x will come as 3 so we need {1,2,3} as element. By using these 3 element you can make any number from 1 to 6...

same If N = 7 then ceil of X will comes as 4. here if is impossible to get 7 if we have only {1,2,3} as element so we add new element as 4. So now by using {1,2,3,4} we can make any element from 1 to 10.

Again if number is 11 then you need to add 5 in your set. so by using {1,2,3,4,5} you can make any number form 1 to 15....

So once we got X then total number of element in array - X will give the answer.

PS: i am considering array will have all the element lower then required N.

If array have element grater then N, then after finding X we need to check set {1 to X} present in array or NOT. if any element from this set {1 to X} not present then increase the count.

RepSpent 2001-2007 promoting augmented reality integrated through social media in West Palm Beach, FL. Won several awards for merchandising Roombas ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Jaks's Heap implementation is fine, but the main issue is how to get mutual friend count (Frequency).

- manidam07 September 20, 2016A is has 100 friend. And each 100 friend have 5 friend. So now A has 500 mutual friend. These all 500 user has mutual friend count AT LEAST 1.

Now to find these 500 user mutual friend count, we need to iterate over all 100 friend of A and find, it is friend of that user OR not. If yes then increase mutual friend count by 1.

But this way 1 user making 100 checks so 500 user will need to make 500*100 calls.

can we have any better solution to find frequency( mutual friend count).