Synopsys R&D Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
A binary heap, with participants as leaves of the tree.
Split the two groups based on the ranking/seeding or whatever.
Eg: if n1,n2,..., n7,n8 are number according to ranking,
n1 is leaf in the first group and n2, the leaf in the second group
n3, n4 & so on...
The time complexity will be O(1) to find the winner and the runner.
Root of the heap is the winner.
The child element of the root, other than the winner is the runner up.
No. Wrong. O(n-1) for winner and o(n+logn-2) for runner. If you don't understand, search for selection trees in geekforgeeks
I guess MG is correct.. Selection tree will give the second ranked player not the runner up. Supposed the players are 1 ... 8 with 1 as lowest rank and 8 as highest rank.. suppose there is a match between 7 & 8 in the first round. and a match between 1 and 8 in the final.. and 8 wins.. MG's method will give runner up as 1 since 1 lost in final.. Selection tree will give answer as 7 since 7 is second highest ranked player...
what is the gaming pattern - round robin matches? or knock out? and to which level
- rajanikant.malviya September 26, 2012