TCS CodeVita 2013

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