All Tracks Algorithms Sorting Merge Sort Problem

Write a checker !

Data Structures, Easy-Medium, approved


Efficient management of a database requires to deal with issues such as Low Latency, Caching and most of all redundancy. Today, you need to perform some testing of a test database provided to you.

Given the database of ABC company, this database contains a table Users. This users table stores for each user $$4$$ pieces of information i.e their Name, Age, Hometown and Address in this order. The size of this table is rather large, and you need to help in resolving some issues.

ABC company is suspicious that this Users table contains many redundant entries. An entry is considered to be redundant if for any $$2$$ separate entries in the table entry $$i$$ and $$j$$, such that $$i \ne j$$, $$(Name_{i}$$=$$Name_{j})$$ or $$(Age_{i}$$=$$Age_{j})$$ or $$(Address_{i}$$ = $$Address_{j})$$ or $$(Hometown_{i}$$= $$Hometown_{j})$$.

Now, you need to help ABC company, and write for them a checker, that handles the following :

  1. It should be able to detect all pairwise redundant entries.

  2. For each pairwise redundant entries $$i$$ and $$j$$, you need to print a new line to output with $$2$$ space separated integers $$i$$ and $$j$$. (The entries are indexed starting from one).

$$2$$ entries $$(i,j)$$ and $$(x,y)$$ are considered to be pairwise distinct, if $$i \ne x$$ or $$ i\ne y$$, or $$j \ne x$$ or $$j \ne y$$.

Input Format :

The first line contains a single integer $$N$$ denoting the number of entries in the Users table. Each of the next $$N$$ lines contains $$4$$ space separated tokens mentioned above.

Output Format :

On the first line, print a single integer $$K$$, i.e the number of redundant entries present in the Users table. On each of the next $$K$$ lines. print $$2$$ space -separated integers $$i$$ and $$j$$, denoting that entry $$i$$ and $$j$$ are pairwise redundant.

Constraints :

$$ 1 \le N \le 2 \times 10^3 $$

$$ 1 \le |Name_{i}| , |Hometown_{i}|, |Address_{i}| \le 5 $$

$$ 1 \le Age_{i} \le 100 $$

Input Strings shall consist only of lowercase English alphabets. You can print the entries in any order.

a 12 c d
b 13 d e
d 12 f k
zz 13 m co
1 3
2 4

Here, $$age_{1} = age_{3}$$, and $$age_{2}=age_{4}$$. So there are exactly $$2$$ pairwise redundant entries in this table.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications