## SDE1 Interview Questions

- 0of 0 votes
Finding Peak element in an array

- 1of 1 vote
This is a question I received in an online challenge.

A list of numbers are given. We need to find the total number of groups in which the digits of each number have same frequency.

For example if numbers are:

1

10

3

33

There are 4 groups:

G1={1}has one 1.

G2={3} has one 3.

G3={10}has one 1 and one 0.

G4={33}as two 3s.

- 0of 0 votes
Design an Algorithm for Amazon Advertisement Page

- 0of 2 votes
Given N ropes of lengths L1, L2, L3, L4, …, LN. I had to join every rope to get a final rope of length L1 + L2 + … + LN.

However, I can join only two ropes at a time and the cost of joining the two ropes is L1 + L2. I was supposed to join ropes in such a way that the cost is minimum.

- 3of 3 votes
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.(Using DP)

- 0of 0 votes
You have 10^9 user, 10^3 websites that users are subscribed to and 2000 servers. Some users will unsubscribe from certain websites. How would you architect this system to be scalable and performant?

- 1of 1 vote
This is was asked in Amazon SDE online test from Hacker rank.

Initech is a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager.

Please implement the closestCommonManager method to find the closest manager (i.e. farthest from the CEO) to two employees. You may assume that all employees eventually report up to the CEO.

Tree structure:

Bill -> Dom, Samir, Michael

Dom -> Bob, Peter, Porter

Peter -> Milton, Nina

Sample Data:

CEO Bill has 3 employees reporting to him: {Dom, Samir, Michael}

Dom has three reports { Peter, Bob, Porter}

Samir has no reports {}

Michael has no reports {}

Peter has 2 reports {Milton, Nina}

Bob has no reports {}

Porter has no reports {}

Milton has no reports {}

Nina has no reports {}

Sample calls:

closestCommonManager(Milton, Nina) = Peter

closestCommonManager(Nina, Porter) = Dom

closestCommonManager(Nina, Samir) = Bill

closestCommonManager(Peter, Nina) = Peter

- 0of 0 votes
ATM has x currency notes of 100 rupee,y currency notes of 500 rupee,and z currency notes of 1000 rupee notes.

Customer wants to withdraw n amount at any given time. as per bank rules,Customer can not withdraw more than INR.40000/-per transaction.

If ATM is running out of cash it should throw a message that insufficient Balance, Kindly enter multiple of m value of currency note.where m>=4000 and m<=total number of cash available in ATM.

An intelligent banker has found in customer survey that customer prefers to receive more than 5 currency notes 100 rupee,more than 2 currency noes of 500 rupee and rest of the currency notes is of 1000 rupee where ever possible.

If amount is less than 500,customer will receive 100 rupee currency notes. Bankers goal is to tender the minimum number of currency notes to save customer waiting time and increase customer satisfaction by following customer survey.Banker has hired you to program ATM dissaptch function.

FOR Example: Lets ATM has 200 currency notes of 100 rupees,90 currency notes of 500 rupee and 50 currency notes of 1000 rupee.Customer has placed a withdrawal request of Rs 22,200.00. Dispatch function has given him 7 currency notes of 100,3 currency notes of 500 and 20 currency notes of 1000 rupee

- 0of 0 votes
Design a datastructure which stores employee details Name,PhoneNumber,Addres and the employee details are(all the 3 given above) fetched when the user searches the data structure by Name or phone number

- 2of 2 votes
We have an iterator class as below:

`class CIterator { int Next(); //Returns the value of the next element in the iteration by advancing the iterator bool HasNext() const; //check whether any next element for the current iterator };`

We need a CPeekIterator class which is having below functionalities

`Class CPeekIterator { int Next (); //Same as CIterator does bool HasNext() const; //same as CIterator does int Peek(); // Returns the next element in the iteration without advancing the iterator };`

Write the CPeekIterator class

- 0of 0 votes
How can you read from disc such that you optimize the latency of the data read/writes?

- 0of 0 votes
Below is almost correct program, there is only one line code is wrong, you have to fix it.

String str contains only a and b characters. below program checks whether str contains equal number of a and b characters.`void checkBalance(string str) { char temp[MAXLEN]; int i, j; for (i = j = 0; temp[i] = str[j]; j++) if (str[j] == temp[i]) i++; else i--; if (i == 0) printf("Balanced\n"); else printf("Not Balanced\n"); }`

- 0of 0 votes
Given string a and b, with b containing all distinct characters, find the longest common subsequence's

length. Expected complexity O(nlogn).

- 1of 1 vote
Given a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.

- 1of 1 vote
Given an array of numbers, for every index i, find nearest index j such that a[j] > a[i].If such an index doesn’t exist for i, 1 should be printed.

- 0of 0 votes
Implement ReentrantLock using simple locks.

- 0of 0 votes
Given a large that consists of millions of lines, retrieve only the first and last lines.

- -1of 3 votes
Given a 1D array, implement function Sum(x1,x2) where x1 and x2 are indices of array. Find sum of all elements in between the given indices inclusive of them. Do in Time complexity of O(1)

- 4of 4 votes
Given a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers.

Test the algorithm after developing the code

- 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).

- 0of 0 votes
Nuclear Rods

A core meltdown has occurred at the Fubaru nuclear plant. There are

n nuclear fuel rods that are damaged and need to be removed using

specialized radiation-hardened robotic equipment

with solid-lead isolation chambers. Remote imaging has already

uniquely identified every damaged fuel rod and assigned it a number

between 1 and n. The imaging data also records which fuel rods were

fused to each other during the meltdown. Every recovery sortie by the

robot can pick up one set of nuclear fuel rods that are directly or

indirectly fused to each other.

The recovery costs per sortie are proportional to the square root of the

number of fused rods recovered. So the cost is K to recover K rods.

Isolation chambers are available for all positive integer costs (1, 2, 3, …).

An isolation chamber can be used multiple times, and each use will

incur the same cost. The robot can also recover a lower number of rods

than a chamber's capacity on a sortie.

Find the minimal cost to recover all the radioactive rods by completing

the given function.

Input

The first parameter integer n specifies the number of rods. The second

parameter pairs is an array of pairs of rods that are fused together. Each

item in the array contains exactly two integers, P and Q separated by a

space (" "), which means that the rod numbered P is fused to the rod

numbered Q. *Note - Each item in the array is a string which needs to be

parsed to P and Q

Output

2

Constraints

2 ≤ N ≤ 100,000

1 ≤ P, Q ≤ N

P ≠ Q

Sample Input

4

2

1 2

1 4

Sample Output

3

Explanation

Rods #1, #2, #4 are connected to each other (2-1-4) so they are in a

single group of 3. The sortie to recover them will cost 2 (with isolation

chamber capacity 2 = 4). Rod #3 is not fused to any other, so it can be

recovered at a cost of 1 (with isolation chamber capacity 1 = 1).

- 0of 0 votes
StringChain

You are given a library with n words (w[0], w[1], ..., w[n - 1]). You

choose a word from it, and in each step, remove one letter from this

word only if doing so yields a another word in the library. What is the

longest possible chain of these removal steps?

Constraints:

1 ≤ n ≤ 50000

1 ≤ the length of each string in w ≤ 50

Each string composed of lowercase ascii letters only.

Input Format:

Complete the function "longest_chain" which contains an array of

strings "w" as its argument.

Output Format:

Return a single integer that represents the length of the longest chain of

character removals possible.

Sample Input #00:

6

a

b

ba

bca

bda

bdca

Sample Output #00:

4

- 0of 0 votes
(x-1)! % x = -1 in efficient way.

- 4of 4 votes
Given three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.

- 0of 0 votes
Given two strings, return true if they are one edit away from each other, else return false. An edit is insert/replace/delete a character.

Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false

- 0of 0 votes
Given a linked list and a positive integer n, reverse the order of nodes in between n and last but n nodes.

example: 1->2->3->4->5, n=2. Output is 1->4->3->2->5

- 0of 0 votes
Given a postfix expression as a string, evaluate it and return the result. example : "423+*" ->20. The Postfix expression is well formed(need not check for bad expression)