Programming Geek
Rated 4.1/5 based on 446 reviews

TCS CodeVita 2014 Questions : Round2 (Set1)

Question : Valid Segments

Consider text comprised of sentences and sentences comprised of words. Words in a sentence will be space delimited. Text will comprise of two types of words, viz. alpha words and beta words. Alpha words are denoted in the input. All words in the text which are non-alpha words are beta words. Task is to find out the number of valid segment with number of beta words in the given range [lb, ub].

A segment is said to be valid if
- It contains all the K-strings
- It should start and end with any one of the K-strings

Input Format: 
First line contains the text. Next line contains K, lb, ub. Next K lines consist of alpha words in the text.

Note: 
1. String comparison should be case insensitive.
2. String comparison should be based only on words comprised of alphabets. Non-alphabet characters such as Full Stop ("."), Exclamation Marks ("!") etc. are called as Stop words. Stop words must be removed from sentences before comparison.
3. If more than one segment starts with the same index (i.e. position of the word in the text), then consider the shortest segment. In other words, segments should begin from unique indexes.

Output Format: 

Print the number of valid segments with number of beta words in the given range [lb, ub].

Constraints:
1<= total number of words in the text <= 30,000
1<= length of alpha and beta words <= 500
1<=K<=total number of alpha words
1<=lb<=ub<=total number of beta words

Sample Input and Output


SNo.InputOutput
1
The European market crashes on Mondays. Crashes in the European market are quite common.
2 3 4
European
Crashes

1

Explanation: 
Valid segments are:
European market crashes
crashes on Mondays. Crashes in the European
Crashes in the European

There is only one valid segment with number of beta words in the range [3, 4], which is segment 2.



A is the square matrix of size N. Every entry in the matrix will contain a lower case alphabet. Given Z strings, for each string your task is to find out the closest square-matrix starting from (1, 1). Closeness between the sub-matrix and the string is defined as, number of similar characters between the two. The input is guaranteed to have at least one character that is same in string Zi and matrix A, where Zi is the ith string. The same cell in the sub-matrix of A cannot be counted more than once to match with the character in the S.

Input Format: 
First line of input will consist of T Test cases. Each test case will consist of four parts, viz.
1. Size of the matrix (N)
2. The matrix itself (A = N * N) where elements are delimited by space.
3. Number of Strings (Z)
4. Z lines each comprising of string S

Output Format: 
For every string print the bottom right co-ordinates of the square-matrix closest from (1, 1).

Constraints:
1<=T<=5
1<=N<=500
'a'<=Aij<='z', where Aij is the entry of the matrix at ith row and jth column(1-index based). 
1<=Z<=25000
1<=|S|<=500

Sample Input and Output
SNo.InputOutput
1
1
4
a e r d
p l x l
l p x z
c q x o
3
apple
alex
aero

3 3
3 3
4 4

Explanation:
String S: "apple"
Sub matrix: (1, 1) to (3, 3)
a e r
p l x
p x
Sub matrix contains all characters of string S, hence the output




Given a list of unique employee ids and their age information, your task is to design a program to support the certain operations. Broadly speaking there are two operations, Insert and Query. You can assume that insert operations are unique on the employee_id column. Query operations are of 3 types. Both insert and query operations are described below.

1. A {employee_id} {age} 
    Operation will add the employee_id and age.
    Syntax: A {employee_id} {age}
    Returns: None

2. Q 1 {employee_id} 
    Query will search for the records whose employee id is {user_employee_id}.
    Syntax: Q 1 {employee_id}
    Returns: Boolean (True or False)

3. Q 2 {employee_id} 
    Query will search for the records whose employee id starts with {user_employee_id}.
    Syntax: Q 2 {employee_id}
    Returns: Total count of the records which matches the search criteria.

4. Q 3 {employee_id} {lb} {ub}
    Query will search for the records for which employee id starts with {user_employee_id} and age is in the range (lb, ub).
    Syntax: Q 3 {employee_id} {lb} {ub}
    Returns: Total count of the records which matches the search criteria.

Input Format: 

Every input line consists of either Add (A) or Query (Q) operation. -1 represents the end of input.

Output Format: 

Print the total number of resultant records in case of Query operation.

Constraints:
1 <= Total digits in the Employee ID <= 50
20 <= Age <= 100
10 <=lb<= 100, where lb is a multiple of 10.
lb <=ub<= 100, where ub is a multiple of 10.
Total number of add operations <= 40000
Total number of query operations <= 40000

Sample Input and Output

SNo.InputOutput
1
A 112345 20
A 112346 40
A 212347 40
A 212348 23
A 112449 30
Q 1 112345
Q 2 1123
Q 3 112 10 50
-1

True
2
3

NOTE: 
Minimum time required for evaluating this program is 24 seconds. Please be patient. Request you to wait up to a few minutes before resubmitting the same solution.