Amazon is worried about account sharing and comes to you with n total login instances.
Amazon is worried about account sharing and comes to you with n total login instances. In addition to that Amazon already has a tool to compare the login information of two of the accounts in the list. That means, using their existing tool you can select any two logins from the list and pass them into an equivalence tester’ which tells you, in constant time, if the logins were produced from the same account. You are asked to find out if there exists a set of at least n/2 logins that were from the same account. Design an algorithm that solves this problem in 0 (n log(n)) total invocations of the ‘equivalence tester Note: 1. Your algorithm can use a global array, and a pointer to the indexes of that global array. 2. You can use master’s theorem to proof your run-time.
