CodeVita 2013 Questions : Set1

Problem: Query Engine

Implement operations similar to database operations in your favourite language. Think of these operations as operations that we use in SQL (Structured Query Language) that we run on databases. These operations will be implemented on files which can be treated as database tables. These files will consist of comma-separated values which can be considered as different columns in the table. A newline character in the file can be treated as a record delimiter.

Given the above background, write a program to implement the following operations viz. Join on two tables, Sort by, limit and result printing. Consider the following database schema to understand the problem better. Consider 2 tables

CollegeMaster -
UserMaster -

Constraints:

1. collegeid is the primary key of CollegeMaster table
2. userid is the primary key of UserMaster table
3. collegeid in UserMaster is the foreign key to collegeid in CollegeMaster
4. ctreference,email and username satisfies unique key constraint on UserMaster table
5. Query on search attribute in UserMaster will always have Select clause comprising of columns in CollegeMaster and vice-versa.
6. CollegeId need not be printed in either case since that is the only column on which 2 tables can be joined.

Your program should implement a SQL query, say for example like

Select userid, username, email, ctreference from usermaster, collegemaster where usermaster.collegeid = collegemaster.collegeid and usermaster.collegeid=1 sort by userid limit 0, 5;
OR
Select collegename, cityid, stateid from collegemaster, usermaster where collegemaster.collegeid =usermaster.collegeid and usermaster.userid=1;

Input Format:

Input will consists 5 items as described below.

Line 1	Absolute path to CollegeMaster file
Line 2	Absolute path to UserMaster file
Line 3	Either C or U, where C represents, search field is in CollegeMaster and  U represents, search field is in UserMaster.
Line 4	Name of the search attribute
Line 5	Value of the search attribute

File Format
CollegeMaster File Master
Column 1 – CollegeId
Column 2 – CollegeName
Column 3 – CityId
Column 4 – StateId

Columns are separated by “,” 
UserMaster File Format
Column 1 – UserId
Column 2 – UserName
Column 3 – Email
Column 4 – CTReference
Column 5 – CollegeId

Columns are separated by “,”

Output:

Output of the program will be the filtered records that are returned as a result of a query. Records should be sorted by userid when printing query results where applicable. Maximum number of records to be printed is 5.

Example Output with query on Collegename:

1,Sachin Tendulkar,user1@gmail.com,CT20120000001
2,M S Dhoni,user2@gmail.com,CT20120000002
3,Virender Sehwag,user3@gmail.com,CT20120000003
6,Zaheer Khan,user4@gmail.com,CT20120000004
31,Ishant Sharma,user5@yahoo.com,CT20120000005Example Output with query on CTReference: 

Kirti College, 1, 1

Note:
This is a sample data file only. Actual data file may contain more / less data, but is guaranteed to adhere to this format.

Sample Input and Output:

SNo.	Input	Output
1	Collegemaster.csv Usermaster.csv C CollegeName Kirti College	1,Sachin Tendulkar,user1@gmail.com,CT20120000001 2,M S Dhoni,user2@gmail.com,CT20120000002 3,Virender Sehwag,user3@gmail.com,CT20120000003 6,Zaheer Khan,user4@gmail.com,CT20120000004 31,Ishant Sharma,user5@yahoo.com,CT20120000005
2	Collegemaster.csv Usermaster.csv U CTReference CT20120000001	Kirti College, 1, 1
3	Collegemaster.csv Usermaster.csv @ 4	Invalid Input
4	Collegemaster.csv Usermaster.csv U CTReference CT20120000007	Data unavailable

Problem : Loan Structuring

Develop a program to find EMI (Equated Monthly Installment) and the amortization schedule for loan repayment. Three primary inputs for doing loan arithmetic are Loan Amount, Rate of interest and Tenure. Rate of interest can vary over certain months and affect the tenure. Write a program to calculate EMI, total interest paid over entire tenure of the loan and amortization schedule. Amortization schedule is explained in text below.
This problem will take into account frequency of payment viz. MONTHLY/YEARLY/ DAILY. The EMI is payable at this frequency. The interest rate variation is captured in form of From Installment number to To Installment number. The interest rate may vary or may remain constant over the tenure of the loan repayment schedule.
Program should accept name of the file as input on console. The file will contain inputs such as loan amount, rate etc. See details in input specification section below. In case of a bad input, program should notify user with invalid input.

Information:

• EMI are the payments one makes in order to pay off the loan. On a specific date every month,one needs to pay the EMI. EMI depends upon loan amount, interest rate, loan tenure and the frequency in which one wants to pay EMI i.e can be monthly/quarterly/yearly etc
• Round off the interest paid to the nearest rupee.
• EMI can be calculated using the formula:

EMI = (L*I)* {((1+I)^N) / ([(1+I)^N]-1)}

where
L = loan amount
I = interest Rate(rate per annum divided by 12)
^ = to the power of
N = Loan Period in months

Example

Mr. Gonsalves borrowed Rs 57,00,000 Lakhs (Rs 5.7 million) at 10% per annum for a tenure of 20 years with EMI payable monthly. According to his loan plan after 100 months for next 50 months, the rate of interest changes to 10.5.

So here, Loan amount=Rs 57,00,000 Lakhs (Rs 5.7 million) 
Rate of interest= 10
Tenure=240(20*12)
Frequency=MONTHLY
From Installment:100
To Installment:150
Rate of interest= 10.5

EMI calculated, using formula mentioned above is 55006.23376921851. Rounded off to two digits after decimal point, EMI becomes Rs 55006.23. Amortization schedule for this loan case looks similar to the table shown below :

Amortization Schedule:

InstNo.	Opening Principal	Installment Amount	Principal Component	Interest Component	Closing Principal	Rate Of Interest
1	5700000	55006.23	7506.23	47500	5692493.77	10
2	5692493.77	55006.23	7568.79	47437.45	5684924.98	10
3	5684924.98	55006.23	7631.86	47374.37	5677293.12	10
4	...	...	...	...	...
5
99	4569291.63	55006.23	16928.8	38077.43	4552362.83	10
100	4552362.83	55006.23	15173.06	39833.17	4537189.77	10.5
101	4537189.77	55006.23	15305.82	39700.41	4521883.95	10.5
245
246						10.5
247	54551.64	55006.23	54551.64	454.6	0	10.5

Total interest paid on 57,00,000 at rate 10.50 is 78,77,467.47 in 247 installments. While printing the output report interest paid rounded off to the nearest multiple of hundered (100). In this case it will be 78,77,500 .Refer section on Output Format for precise instructions.

Note, two things from the table and the sentence above

1. Since the rate of change of interest is marked from 100^th month to 150^th month, but no additional information is provided about the rate from 151^st month till the end of the tenure. Hence rate of interest in this case will remain as 10.5 until any explicit rate change, to take place later is provided. In this case, since no information is provided, rate will remain 10.5% until end of tenure.
2. At the start of the problem, it was stated that the tenure is 240 months. But due to increase in rate of interest and no change in EMI, the tenure increased to 247 months. You are assured that rate of interest will never change in such a way that with the current EMI amount the loan can never be repaid. Such test cases are out of scope for this problem.

Input Format

Line 1	Name of the file from which inputs are to be taken. The input file format is described next.
Line 2	A particular installment number whose opening principle is to be calculated using amortization schedule.

Note:
The Input in file column in table below on Sample Test Cases is provided to help you visualize how the input file will look like.

File Format

Line 1	Loan Amount (L)
Line 2	Rate of Interest per annum (R) in percentage
Line 3	Tenure (N)
Line 4	Frequency of payment Frequency can be MONTHLY/YEARLY/DAILY for MONTHLY Rate of Interest =Rate of Interest per annum (R) /12 DAILY Rate of Interest=Rate of Interest per annum (R)/365
If there is a change of rate of interest then following lines will be a part of the input
Line 5	From installment
Line 6	To installment
Line 7	Changed Rate of Interest

Constraints

1. Here:

0 <= L <= 10,000,000,000

0 <= R <= 100

1 <= N <= 1188

2. In case of change of rate of interest, the To installment value should be greater than From installment value

Output Format

Line 1	For valid input,print EMI amount rounded to 2 digits after decimal point For Invalid input,print Invalid Input
Line 2	For valid input,print Opening Principal before installment X is Rs Y where X is the input provided in Line 2 (installment number) and Y is Prinicipal outstanding in Rs rounded to nearest multiple of hundered (100) For Invalid input,print Please Mention Frequency Of EMI As MONTHLY/YEARLY/DAILY
Line 3	Interest paid is Rs Z where Z = interest paid over entire tenure rounded to nearest multiple of hundered (100)

Sample Input and Output

SR.no	Input	Input in File	Output
1	EMIinput.txt 25	15000 10.5 240 MONTHLY  200 220 11 221 240 12	EMI is Rs 149.76 Opening Principal before installment 25 is Rs 14500 Interest paid is Rs 21000
2	EMIinput.txt 23	1000 10 25 abc	Invalid Input Please Mention Frequency Of EMI As MONTHLY/YEARLY/DAILY
3	EMIinput.txt 11	5 25 40 DAILY ??	Invalid Input
4	EMIinput.txt 12	1200000 25  40 DAILY	EMI is Rs 30423.11 Opening Principal before installment 12 is Rs 873300 Interest paid is Rs 16900

Problem : Expense Solver

5 friends share accommodation. Expenses between them are shared. They have a rule that expenses are shared equally among all friends those who are a party to that expense. Their problem is they are poor in math. Hence they end up fighting over expenses. Your job is to help them in splitting the expenses and prevent in-fighting. 

Write a program to help divide the expenses. The program should be generic enough such that number of members sharing accommodation can vary. Your program should take the following inputs and give the following output.

Assumptions:
The Person paying for a transaction is himself a party in that particular expense

Input Format:

Line 1 contains the name of the friends sharing the accomodation. Line 2 provides the number of trancations(T) to be accounted. Line 3 to line T+2 will give the details of the transactions and will contain the spender's name,the amount spent and the friends involved in the transactions

Line 1	N1 N2…Nn  where Ni is the name of all the friends sharing the accomodation,separated by white space character
Line 2	T  where T is the number of transactions
Line 3 to Line T+2	Ns1 A Np1 Np2 …  where Ns is the spender, A is the amount spent in a particular transaction and Npi are the other friends involved in the transaction

Output Format: 

Line 1

For Valid Input, print N1 A1 N2 -A2 … Nn -An where Ni is the name of the friend and Ai is the amount he has to recieve/pay. Negative(-) number represents payable.

Sample Inputs and Outputs:

SNo.	Input	Output
1	Pankaj Pranav Mayank Nihit Mukesh 5 Pankaj 600 Pranav Mayank Pranav 450 Mayank Nihit Mayank 300 Mukesh Pranav Nihit Nihit 1200 Pranav Pankaj Mukesh 3000 Pranav Pankaj Mayank	Pankaj -750.0 Pranav -1125.0 Mayank -875.0 Nihit 575.0 Mukesh 2175.0
2	Sagar Sumit Suresh 4 Sagar Sumit	Invalid Input

Problem : SQL Analysis

Given a proper SQL (Structured Query Language) statement, identify the objects and group by operations in the SQL statement. Assume SQL-92 standard specification to which all the input SQLs will adhere to. Assume that SQL queries are composed only on tables (no views). 

1. Your program should implement a SQL Analyzer which will break up the query into number of tables and number of group by clauses.
2. If a table is accessed more than once (say twice), print table name twice. Print table names in case-insensitive sorted order. (A-Z)
3. Print group by statements in sorted order of the columns used in group by clause (A-Z)

Input Format:

Input will consists 1 item as described below.

Line 1

Absolute path to file containing the SQL query

Output Format:

Lets say, the SQL query in the input is

select count(uname),name from present_address pr,country cn,customer_details cd, address a 
where a.addrid=cd.addrid and 
a.adtid=pr.adtid and 
cn.countryid=pr.countryid
group by name;

then,output should print the same query in first line of the output followed by the analysis.

select count(uname),name from present_address pr,country cn,customer_details cd,address a where a.addrid=cd.addrid and a.adtid=pr.adtid and cn.countryid=pr.countryid group by name;
Table : address
Table : country
Table : customer_details
Table : present_address
Group By : name

Note:
This is a sample data file only. Actual data file may different types of queries, but is guaranteed to adhere to SQL-92 format.

Sample Input and Output

SNo.	Input	Output	Comments
1	/tmp/query1.txt	select count(uname),name from present_address pr,country cn,customer_details cd,address a where a.addrid=cd.addrid and a.adtid=pr.adtid and cn.countryid=pr.countryid group by name; Table : address Table : country Table : customer_details Table : present_address Group By : name	The entire SQL is Line 1. Line 2 – 5 are names of tables used in the query, printed in sorted order (A-Z) of the tablename. Next Line(s) is Group By

Problem : 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. 

For example, 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.

Your task is to 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 sort-able by any field.Sort in asecending order.
Your program should extract the records from a 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 sort-able by any field. If the input is (Department ID-10, Page Size-20, and Page Number -2), then the program should retrieve second set of 20 records. 

Information:

• Expected Volumes: Department Data File may have approx. 100,000 records per department ID. Page Size is expected to be less than 100 records.
• Application also allows other search operations on the basis of Employee ID, Name ,Grade.Program should be able to sort on any of these fields

Input Format:

Line 1	Absolute file path
Line 2	C,D,S,N Column(C) on which sort need to be happen Department ID (D) is search Parameter Page Size (S) is number of records that need to be displayed on UI e.g. 20 Page Number(N) is the number of Page which should be displayed e.g. 2 (2nd Page to be displayed)

File Format

Number of Columns-4
Order of Column -DEPT_ID,EMP_ID ,EMP_NAME,GRADE
Columns delimited by comma(,)

Example Department Data File:

DEPT_ID,EMP_ID,EMP_NAME,GRADE
1,1,Smith Frank,A
1,2,Manager Mike,C
1,3,Driver Danny,D
2,7,Bliss,B
2,8,Java,D
2,9,Kyte Kelly,B
1,4,Boat Tony,A
2,5,Louie Chef,B
2,6,Lawson,C
2,10,Baker Sarah,D
2,11,Smothers Sally,A 
2,12,Silly Sall,C
2,13,Viper,B
2,14,Beck,B
2,15,Rambo,A

Note:
This is a sample data file only. Actual data file may contain more / less data, but is guaranteed to adhere to this format.

Output: 

Output of the program will be the filtered records that need to be displayed on UI (User Interface). Records should be sorted by Employee Names and should be filtered as per the input parameters.

Sample Input and Output

SNo.	Input	Output	Remark
1	Page.csv 2,2,3,2	2,8,Java,D 2,9,Kyte Kelly,B 2,10,Baker Sarah,D	Second Page with 3 records from ordered data of Dept ID-2. Ordered by Emp ID
2	Page.csv a,b,c,d	Invalid Input	--
3	Page.csv 3,1,4,1,1	Invalid Input	--
4	Page.csv 3,1,4,1,1	Data Unavailable	Based on sample data above, DEPT_ID 9 does not exist. Hence data will be unavailable for this input.
5	Page.csv 4,1,2,1	1,1,Smith Frank,A 1,4,Boat Tony,A	First Page with 2 records from ordered data of Dept ID-1. Ordered by GRADE

Problem : Credits

Alan has recently joined an Engineering college. On the first day he came to know that each semester will contain N number of subjects and Di (where 1<=i<=N) is the credit associated with that particular subject. In order to be eligible for the next semester each student must get at least X number of credits from the current semester. After knowing this Alan became tensed and nervous, but after discussing with seniors he came to know that getting X number of credits from N number of subjects is easy if they concentrate on particular subjects rather than all subjects. But Alan is having preference list of subjects. As compared with others Alan will give more preference to the subjects listed in preference list.

Based on past results Alan expects pass percentage Pi (where i<=i<=N) for each subject. Now Alan needs to get X number of credits in the current semester. Can you please help the Alan to select the subjects on which he needs to concentrate on, to get exactly X number of credits.

Input Format:

First line of input contains a single integer N, number of subjects present in a current semester, next N lines follows each line contains Si, Di, Pi where Si is the name of the subject, Di is the credit associated with the particular subject, Pi is the pass percentage of the subject. After N lines next line contains X, number of credits needed and the final line will contain the Alan's preference list (N subjects, separated by a space).

Line 1	N , where N is the Number of subjects present in a current semester
Line 2	S1 D1 P1 , where S1 is the name of the subject  D1 is the credit associated with the particular subject and  P1 is the pass percentage of the subject
…	Si Di Pi
Line N+1	Sn Dn Pn
Line N+2	X , where X is the number of credits needed
Line N+3	S1 S2…SN , where Si is the subjects of Alan according to his preference

Constraints:

1<=N<=25, where N is the number of subjects.
1<=|Di|<=100, where |Di| is the credits associated with the subject (where 1<=i<=N).
1<=X<=C (C=Sum of Di, where i=1, …, N), where X is the credits needed for next semester's promotion.
1<=|Si|<=50, where |Si| is the subject name length (where 1<=i<=N).
1<=Pi<=100, where Pi is the pass percentage of the subject (where 1<=i<=N).

Note:

1. If there present multiple set of subjects, then print the first set with highest average pass percentage, and if there are any sets with same average pass percentage then select the set based on the preference list. Please print the subject names separated by a space.
2. There will be at-least one way to get X number of credits.

Output:

Line 1

For Valid Input, print A set of subjects among N subjects on which Alan needs to concentrate on. Output the subjects based on the preference list ordering.

Sample Input and Output

SNo.	Input	Output
1	5 Maths 5 80 Physics 6 75 Chemistry 10 85 Drawing 1 70 English 4 80 11 Maths Drawing Physics English Chemistry	Maths Physics

Problem : Count The Factor

The factorial of a non-negative integer N, denoted by N!, is the product of all positive integers less than and equal toN.
Factorial of any number can be represented in simplest form of its prime factors. 
e.g. 4!=4*3*2*1= 2³*3¹
Factorials can also be specified by the number of times each prime factors occurs in it, thus 24 could be specified as (3 1) meaning 3 twos, 1 three.

Write a program that will take an integer as input and give output as the following.

Input:

Input will be a positive Integer N where N>1.

Line 1

N,where N is any integer.

Output:

Output will show a series consists of the number of times each prime factor appears after the factorization of N! separated by spaces.

Line 1

For Valid Input,print L,where L is the series consists of the number of times each prime factor appears after the factorization of N! separated by spaces.For Invalid Input,print Invalid Input

Sample Test Cases:

SNo.	Input	Output
1	6	4 2 1
2	a	Invalid Input
2	-5	Invalid Input