TCS CodeVita 2013 Round 1 held on 13-14th August 2013
Problem No. 1 :- Pagination
Pagination is the process of dividing content into discrete
pages. Pagination is common in Web-based applications, and is used for limiting
the result set and displaying a limited number of records on the web page.
E.g.:
Consider the Department-Employee scenario. If the search
operation is performed on the basis of Department Id, and there are 100,000
employees per department, then it does not make sense to display the details of
100,000 employees in single page. So, pagination allows to display limited
results e.g. 20 records per page. "Previous" and "Next"
links or the Page numbers are usually provided on the user interface so that
users can navigate to other pages.
Q. Write a program for selecting the records that need to be
displayed on user interface. Records should be filtered as per the input
parameters, and should be sorted by Employee Name. Requirement is to ensure
faster initial page load.
Your program should extract the records from this file on
the basis of input parameters. For example, if the input is (Department ID-10,
Page Size-20, and Page Number -1), then the program should retrieve first set
of 20 records for Department ID-10 sorted by employee name. If the input is
(Department ID-10, Page Size-20, and Page Number -2), then the program should
retrieve second set of 20 records. As the data for a given department will be
sorted by employee name, there will be no overlapping between first page and
second page.
Asumptions:
->Input file data may or may not be sorted by Department
and Employee ID
->Expected Volumes: Department Data File may have approx.
100,000 records per department ID. Page Size is expected to be less than 100
records.
Problem No. 2 :- Isotope
Scientist recently found a new element X, which can have
different isotopes upto an atomic value of 199. Speciality of element X is that
when two atoms fuse they produce energy multiple of their atomic value and
forms an atom with atomic value of their multiple modulus 199.
For Eg:
If atom1 with value 56 and atom2 with value 61 fuse.
They produce energy of 3416 KJ (56 * 61)
Resulting atom will have atomic value (56*61) mod 199 = 33
Scientists created a nuclear reactor to create energy by
this method. Everyday they get several atoms of X from supplier in a particular
sequence. Since this element highly radioactive they cant risk by changing its
sequence. So each atom can fuse only with another atom nearby. Nevertheless
scientists can choose order of fusion thereby maximizing total energy produced.
Now, for given sequence of atomic values, output maximum
energy that can be produced.
For Eg:
If sequence of atoms are
56,61 & 2
Then they can produce 3416KJ by fusing 56&61 which
results in an atom of value 33. Then they can fuse 33 and 2 to get energy of
66KJ. So total energy generated is 3482.
But if they cleverly choose to fuse atoms 61 & 2 first
then they generate 122 KJ with a resulting atom of value 122. Then if they fuse
122 and 56, they can generate 6832 KJ. So total energy is 6954.
Hence Maximum energy that can be generated from this
sequence is 6954.
Input Format
Input starts with a number specifying number of inputs(n)
followed by n space separated integers specifying atomic values of n atoms.
Line 1
N,where N is the number of atoms in the sequence to be fused.
Line 2
a1 a2 a3 .... an
where ai -> Atomic value of i th atom.
and two atoms are space delimited
Constraints:\0 < ai < 199
1 < n < 1000
Problem No. 3 – Fun with Primes
A prime number (or a prime) is a natural number greater than
1 that can only be divided by 1 and itself.
Ex-First few Prime number are-
2, 3, 5, 7, 11, 13, 17, 19,...
A digit prime is a prime number whose sum of digits is also
prime.
For example the prime number 23 is a digit prime because
2+3=5 and 5 is a prime number. 17 is not a digit prime because 1+7 = 8, and 8
is not a prime number. Write a program to find out the number of digit primes
within a certain range less than 1000000.and also print the Mth digit prime
number between the range.
Input:
Input line contains three positive integers (T1 T2 M)
separated by space where lower limit is T1 and upper limit is T2 and M is the
position of the required digit prime number.
Line 1
T1 T2 M, where T1 is upper limit, T2 is lower limit and M is
the position of the required digit prime number.
Constraints:
0 < T1 <= T2 < 1000000
0 < M
Output:
Print Mth digit prime number between T1 and T2(inclusive).
Problem No. 4 – Play with Alphabets
Byteland country is very famous for it's own variety of
rules and customs. People from the normal world only knows 26 alphabets but the
scientists in the Byteland country always try to invent new alphabets. Let N be
the number of alphabets invented by the Byteland country scientists. Alice is
living in Byteland country and one of her friends gifted her a new pet on her
Birthday. In the Byteland country each pet must contain a name as suggested by
the astronomer. After consulting an astronomer Alice came to know that length
of the pet name must be of L letters and among L letters she need to keep X
number of letter prefix as suggested by the astronomer.
Now Alice has decided to form the names by following the
astronomer's suggestion, as Alice is weak in mathematics can you please help
her to find out the number of valid names that she can form. As the
combinations can be too high so mod the result by 1000000007.
Input Format:
Input contains three integers N, L, X in each line.
Given a file with certain records, find records that start
with or end with a particular pattern.
Problem No. 5 :- Company Problem
Information:
Each record in a file consists of 3 distinct parts
Name of the company
Company Information Number (CIN)
Region code (where the company is based out of)
File Format
File consists of records. Records are delimited by a
new-line character. Within a record, the 3 distinct parts are delimited by a
string #@%#. For e.g consider the following lines
GERMAN CHEMICALS PRIVATE
LIMITED#@%#U99999MH2000PTC123825#@%#RC201
GERMAN EXPRESS SHIPPING AGENCY (INDIA)
PVT.LTD.#@%#U61100MH1993PTC071596#@%#RC202
GERMAN FABS PRIVATE
LIMITED#@%#U17110MH1995PTC089052#@%#RC203
Here GERMAN CHEMICALS PRIVATE LIMITED is the name of the
company, U99999MH2000PTC123825 is the CIN and RC201 is Region Code.
Similarly, GERMAN EXPRESS SHIPPING AGENCY (INDIA) PVT.LTD.
is the name of the company, U61100MH1993PTC071596 is the CIN and RC202 is
Region Code.
And, GERMAN FABS PRIVATE LIMITED is the name of the company,
U17110MH1995PTC089052 is the CIN and RC203 is Region Code.
Constraints:
Company Name can be alphanumeric, can include white-space
and special characters. Length of Company Name can vary.
CIN can be alphanumeric, and cannot include white-space or
special characters. Length of CIN can vary.
Region Code can be alphanumeric, and cannot include
white-space or special characters. Length of Region Code can vary.
Problem No. 6 :- Sculptor
Rama is a talented painter. A less known fact is that Rama
also dabbles in modern sculptor. Recently, he has taken a fancy to protecting
the environment, recycling junk etc. Since then, he has been using only
recycled material in his sculptores.
The construction work at the site for the new campus for the
Green Society of India has generated its own pile of junk. Among this junk are
a large number of steel rods of varying lengths. Rama plans to use some of
these in his new sculptor to be placed at the entrance, which will consist of a
sequence of steel rods placed upright in a line. However, he wants the rods to
be arranged in increasing order of height and, further, demands that the
difference in height between each pair of adjacent rods be the same. Your task
is to help him identify the largest set of rods that can be used in his
sculptor.
For example, if there are 5 rods of lengths 2, 3, 6, 7 and
11 then the desired set consists of the three rods of lengths 3, 7 and 11.
Input Format:
The first line of the input consists of a single integer N
indicating the number of rods. This is followed by a single line consisting of
N integers indicating the lengths of the N rods.
Line 1 :- N,where N is the number of rods
Line 2
a1 a2 a3 .... an,where ai -> the lengths of the rods
and two length of rods are space delimited
Output Format:
The first line of the output consists of a single integer M
indicating the maximum number of rods from this collection that may be used in
Rama's sculptor. This is followed by a single line containing M integers
indicating the lengths of the rods in a sculptor with M rods, in ascending
order. If a group of rods with increasing order of height could not be found
then you can identify the largest group of rods with difference in height
between each pair of adjacent rods as zero. If there is more than one such
solution then it suffices to print out one which have maximum value of length.
The program should print Invalid Input when the input values do not lie within
the specified boundary.
Line 1
For Valid Input,print
M,where M is Integer stating maximum number of rods that can
be used
For Invalid Input,print
Invalid Input
Line 2
Containing M integers indicating the lengths of the rods in
a sculptor with M rods, in ascending order
Two length of rods are space delimited
Constraints:
1 <= N <= 2000
M > 0
