## Recent Interview Questions

More Questions »- 0of 0 votes
A nXn matrix consisting of 0 and 1 only is given. n is always odd. A variable k is also given as input. You have to find the minimum vaue of a function F(x,y) over k contiguous row wise elements such that arr[x][y] is 1 for all k contiguous elements.

F(i,j) for any index (i,j) is (n/2-i)^2 + (n/2-j)^2.

- 0of 0 votes
Design a unique hash function for every tweet in Twitter which will be used as part of a service.

- 0of 0 votes
Wedding Planner

Julia is a wedding planner who puts together phantasmagorical

extravaganza packages for new couples and their guests from 2 to

2,000. Hundreds of items are needed for each event, and Julia has a list

of supplier offers for all these items in various quantities. The price per

unit of every item is highly variable, depending on the supplier, the

number ordered, and the client/buyer who places the order. With her

years of record-keeping, Julia knows the best unit price she can get for

any item in any of a limited number of order sizes. Some items cost less

per unit when the number ordered goes up, some cost less per unit

when the number ordered goes down, and others have no rhyme or

reason for the unit prices available.

To price a new event, Julia consults her database of past offers.

If the amount needed for the new event is exactly the same as the

amount in a past offer, the unit price is also the same.

If she has a price for a higher amount and a price for a smaller

amount, her best guess will be that the unit cost will be linearly

interpolated from the unit costs for the closest lower amount and

the closest higher amount.

If the database only has one amount, then her best guess is that this

will be her unit cost.

And, if the amounts for which she has offers are all smaller or all

larger than the amount she needs, then she finds it most accurate to

linearly extrapolate from the closest two points to the amount

needed.

Finally, sometimes price offers lapse. When this happens, Julia, who

is not very database savvy, just overwrites the old unit price with a

zero or negative number. The amounts associated with zero or

negative unit price need to be disregarded.

automated so she can do it for hundreds of items with thousands of

individual prices.

Complete the function extrapolate , which takes a new amount n, an

array amount of old offer amounts in increasing order, and an array

ucost of corresponding unit prices. Your completed function should give

the expected unit price p for the new amount. The unit prices may

increase, decrease or oscillate, and may also contain invalid values like

0 or negative numbers. Your answer, as well as the unit prices in the

second array, should all be real numbers with exactly two decimal

places, representing dollars and cents. Use standard rounding to arrive

at two decimal places.

Input

A positive integer n, denoting the number if items for which a unit

price is needed.

1.

An array amount of l positive integers denoting the different order

amounts for which historical unit costs exist.

2.

An array ucost of l strings of real numbers denoting the different

unit costs for the corresponding amounts in array a.

3.

Output

A single positive number p with exactly two decimal places.

Note that the code for processing input and output is already present in

the system and designed to be compatible with the test case files used

to score your solution. There is no need to change only of the code other

than the body of the function extrapolate.

Constraints

1 ≤ l ≤ 100

2 ≤ n <= 2000

size(a) = l = size(u)

a(i) < a(j) ⇔ i < j

1

2

3

4

5

n = 25

a = {10, 25, 50, 100, 500 }

u = {"2.46","2.58", "2", "2.25", "3" }

Sample Output #1:

p = 2.58

Explanation #1:

The amount 25 is one of the values in the database. Its corresponding

unit price is 2.58.

Sample Input #2:

n = 2000

a = {10, 25, 50, 100, 500 }

u = {"27.32", "23.13", "21.25", "18.00", "15.50"}

Sample Output #2:

6.13

Explanation #2:

The item count 2,000 is not in the database. It is larger than any amount

in the database. The closest two price points to it are 15.5 for 500 and

18.00 for 100. Linear extrapolation from these two points means

reducing the price by 2.5 for every increase in amount of 400. There 3.75

jumps of 400 from 500 to 2,000, or 4.75 jumps of 400 from 100 to

2,000. The unit price for 2,000 is therefore 15.5 - 2.5 × 3.75 or 18 - 2.5 ×

4.75. Both expressions evaluate to 6.125. This rounds up to 6.13.

- 0of 0 votes
Strong relation group

A group of social network experts are searching for an algorithm to find

"Strong relation groups" among people. A group of people form a strong

relation group if each of them know everyone else in the group. The

problem seemed very tough to them, so they want to attack a smaller

problem. If there are n people in a network and there are m pairs of

relationship among them, what will be the minimum size of the largest

"Strong relation group" in the network? If you know about graphs, you

can think of people as nodes and their relationship as edges.

Parameters:

Complete a function strongRelation which takes two integers n and m

as parameters.

Input Format:

First line contains a single integer denoting N.

Second line contains a single integer denoting M.

Return value:

Return the answer to the problem.

Constraints

1 <= T <= 100000

2 <= N <= 10000

1 <= M <= N*(N-1)/2

Sample Input:

3

2

Sample Output 1:

2

Sample input 2:

4

6

Sample Output 2:

4

Sample input 3:

5

7

Sample Output 3:

3

Explanation

1

2

3

4

5

"Strong relation group" cannot be smaller than 4.

For the third sample, it is easy to verify that any graph with 5 nodes and

7 edges will surely have a "Strong relation groups" of size 3 or more

- 0of 0 votes
Can you predict the missing

grade?

Problem Statement

Introduction

The CBSE Class 12 examination, is taken by Indian high school students

at the end of K-12 school education. The scores or grades in this

examination form the basis of their entry to the College or University

system, for an undergraduate program. At the K-12 level, students

appear for examination in five subjects. These five subjects generally

include one language; three elective subjects oriented towards Science,

Commerce or Humanities; and any elective of their choice as a fifth

subject.

The Challenge

This challenge is based on real school data of the CBSE Class 12

examination conducted in the year 2013. You are given the grades

obtained by students with specific but popular combinations of subjects

(and all these students had opted for Mathematics). Their grades in four

subjects are known to you. However their grade in Mathematics (i.e, the

fifth subject) is hidden.

The records provided to you are the grades obtained by students who

had opted for the following combinations of subjects or courses and

obtained a passing grade in each subject. The individual subjects in the

data are:

English, Physics, Chemistry, Mathematics, Computer Science, Biology,

Physical Education, Economics, Accountancy and Business Studies.

The most dominant subject combinations, account for approximately

99% of the data are:

English, Physics, Chemistry, Mathematics, Physical Education

English, Physics, Chemistry, Mathematics, Economics

English, Physics, Chemistry, Mathematics, Biology

English, Economics, Accountancy, Mathematics, Business Studie

s

The grades of students in four subjects (other than Mathematics) are

provided to you. Can you predict what grade they had obtained in

Mathematics?

To help you build a prediction engine, we will provide you with a training

file, containing the grade points obtained by students with the above

subject combinations, in all five subjects.

Notes about the Grading System

The student is first assessed on a scale of 100. (S)He needs a score of at

least 33% to pass in the subject. Among those who pass:

Grade 1 is assigned to the top one-eighth of students who pas

s the course.

Grade 2 is assigned to the next one-eighth of students who pa

ss the course.

.....

Grade 8 is assigned to the last one-eighth of students who pa

ss the course.

If more than 1 student share the same score and lie in the margin, they

share the higher grade.

Input Format

The first line will be an integer N. N lines follow each line being a valid

JSON object. The following fields of raw data are given in json.

SerialNumber (Numeric): The identifier of the student record.

This is provided just for identification purposes and does n

ot have any direct use.

English (numeric) : The grade (between 1 and 8) obtained in E

nglish. This will always be present.

Three more numeric fields from among: Physics, Chemistry, Com

puterScience, Hindi, Biology, PhysicalEducation, Economics, A

1

2

3

4

5

The input for each record has the grade for all subjects opted by a

student, other than Mathematics which you have to predict as the

answer.

Constraints

1 <= N <= 10

The SerialNumber field will contain a unique numeric identifier such

that 1 <= SerialNumber <= 5 * 10 .

All other fields in the JSON fragment will represent the grades obtained

in four subjects and will be populated by numeric values between 1 and

8, both inclusive.

Output Format

For each student record that is given as a JSON object, containing the

grade obtained in four subjects, output the predicted grade in

Mathematics (this will be a numeral between 1 and 8, both inclusive) in

a newline.

Training File and Sample Tests

The training file with sample test data is available here.

The three files in this package are:

training.json

sample-test.in.json

sample-test.out.json

Training data as well as sample testcases have been provided in the

above file for offline training and to help you build your prediction

model. Feel free to include file data inside your code.

Sample Input

12345

{"SerialNumber":1,"English":1,"Physics":2,"Chemistry":3,"Comp

uterScience":2}

json_object

json_object

json_object

.

.

.

5

5

1

2

3

4

5

Sample Output

1

3

4

7

8

....

....

....

Explanation

It is predicted that first candidate obtained grade 1 in Mathematics, the

second candidate achieved grade 3 in Mathematics, the third candidate

achieved grade 4 in Mathematics and so on.

Scoring

For each of the N records in the input file, we will compute:

p = abs(Predicted Grade Point in Mathematics - Actual Grade Point in

Mathematics)

Where 'abs' indicates the Absolute Value or Magnitude. If p = 0 or 1 your

answer for that particular student record will be considered correct. i.e,

we allow a tolerance of one grade point away from the correct answer,

to take into consideration the marginal errors which might occur during

the testing or grading process.

Score = 100 * ((C-W)/N)

Where C = Number of Correct predictions, not more than one grade

point away from the actual grade point assigned.

W = Number of wrong (incorrect) predictions and

N = Total number of records in the input.

While the contest is in progress, only the score based on the sample

test case will be displayed to you. After the contest is completed, we

will revise the scores based on performance on a hidden test set only.

However, when you make submissions, you will be able to see whether

your program attains a positive score on both the sample and the

hidden test cases (to avoid a situation where unexpected errors occur

on the hidden test set at the end).