Suppose you’re consulting for a bank that’s concerned about fraud detection, and

Question

Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a
collection of n bank cards that they’ve confiscated, suspecting them of
being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to
a unique account in the bank. Each account can have many bank cards

corresponding to it, and we’ll say that two bank cards are equivalent if
they correspond to the same account.
It’s very difficult to read the account number off a bank card directly,
but the bank has a high-tech “equivalence tester” that takes two bank
cards and, after performing some computations, determines whether
they are equivalent.
Their question is the following: among the collection of n cards, is
there a set of more than n/2 of them that are all equivalent to one another?
Assume that the only feasible operations you can do with the cards are
to pick two of them and plug them in to the equivalence tester. Show how
to decide the answer to their question with only O(n log n) invocations of
the equivalence tester.

Kleinberg, Jon; Tardos, Éva (2012-02-08). Algorithm Design (Page 247). Pearson HE, Inc.. Kindle Edition.

Explanation / Answer

We can use a inary search tree to check that. Each node of the tree will contain following data:
- Account
- count(inintially 0)
- left child
- right child

We will insert the nodes in the tree starting from the first card.
If any card having sme particular account is not present in the tree, we will insert it.
if any card having some account number is already present in the tree, we will just increase the count.
if count becomes more than n / 2 at any time, the function will return true.

If we use a normal binary search tree, the worst case complexity will be n^2.
So, we can reduce this complexity to n log n by using a self balanced binary search tree.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.