Microsoft Interview Report
- 0of 0 votes
Answersfind the balance index of an array where balanced index i is defined as the one whose left sum is equal to the right sum of the index .
- softy July 15, 2012 in India for bing
i.e
summation (1 to i-1) = summation (i+1 to length of an array) firdt I gave o(n2) solution , but then before i could give O(n) solution it was time up for me,
O(n) solution will be we have to loop through i = 1 to N and find if ( sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (1 to i+1 ) the return i.
Your thoughts?| Report Duplicate | Flag | PURGE
Microsoft Algorithm Arrays Coding Data Structures - -1of 1 vote
Answersthere are N people in a room one of them is a celebrity .At least one person knows other but all knows celebrity.Celebrity doesnt know any one.There is an api isKnown(a,b) which returns true if a knows b.y.
- softy July 15, 2012 in United States for bing
I gave the O(n2) answer.
But I think this can be done in O(n) .We have to compare call isKnown(a[i],a[i+1]) && iskNown(a[i+1],a[i]) returns true remove both frmo the array else remove that a[i] which return true, this will reduce the array to the celebrity. order will be O(n) then.Your thoughts ??| Report Duplicate | Flag | PURGE
Microsoft Algorithm