## SDE1 Interview Questions

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

- 0of 0 votes
Find the total number of connected components in a graph (there can be forests)

- 3of 3 votes
This is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.

Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.

For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.

Input:

A Single number N for which we want to produce the sequence.

Output:

A space separated list of sequence or NA if there is no possible sequence.

Example Input:

3

Example Output:

2 3 1 2 1 3

Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).

- 0of 0 votes
This is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.

Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.

For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.

Input:

A Single number N for which we want to produce the sequence.

Output:

A space separated list of sequence or NA if there is no possible sequence.

Example Input:

3

Example Output:

2 3 1 2 1 3

Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).

- 1of 1 vote
Design a data structure in which we can do all CRUD operations in O(1) ?

CRUD- Create, Retrieve, Update, Delete

- 0of 0 votes
You have an app that uses a 3rd party video player. The VP has the functionalities - play, pause, seek and close. On close, the VP makes a callback to your app. To the callback it sends the below parameters

* videoLengthInSecs

* VideoPart[]. VideoPart {startTime, endTime}. Denotes a continuous part of the video that was watched without any disturbance caused by pause, seek.

Your app should be able to determine whether the user has watched the entire video or not.

60, [{0, 30}, {30, 60}]

return boolean

- 0of 0 votes
There are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get atleast one dish of his chioce. What is the minimum number of different type of dishes we can order?

Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row.

n = 6 k = 7

1 0 0 0 1 0 0

1 0 0 0 0 1 0

1 0 0 0 0 0 1

0 1 0 0 1 0 0

0 0 1 0 0 1 0

0 0 0 1 0 0 1

Output

3

Explanation

Take dish number 5,6,7.

- -1of 1 vote
An input device can read input of 8 bytes over 2 seconds. It needs control over an input buffer during this operation. A disk writer can write data of 16 bytes over 4 seconds to the disk. It too needs control over the data buffer for the duration of its operation.

Design a system that can capture input from input device and write it onto the disk. The interviewer explicitly asked for detailed code for the implementation.

---EDIT---

The input device thread cannot be blocked, if made to wait, data gets overwritten and we have to capture all data available to the input device

P.S.: I don't think we can use synchronized block from java since their locks cannot be interrupted, I have read up on trylock() mechanism but not entirely sure how the exact code would look like.

- 0of 0 votes
Implement a simple, persistent, thread-safe, cache, which should ideally be able to store up to 1 million product names.

- 0of 0 votes
On a screen, there are multiple rectangles drawn, when a user clicks on any point, find the smallest rectangle enclosing this point.

I could not come up with a solution. The end points of rectangles were given and also the the point where the mouse was kept was given.

- 0of 0 votes
Skynet

Skynet has grown to become the dominant force on earth and has almost completely wiped out the

human race. Skynet has been

building robots ever since it's inception and has been updating it's models every year while making

them better. Skynet wants to annihilate humanity completely. It plans to remove one last band of

humans lead by John Connor. Skynet thinks it can destroy these humans using only two of it's robots.

But Skynet doesn't want to send two robots with the same model number lest John Connor finds out a

weakness in that model and easily destroy both of them.

Skynet has at its disposal N robots and to save space Skynet has stored information about pairs of

robots belonging to the same model. If it doesn't have any info stored for a particular robot then it is

implied that the robot is the only one in that model.

Given these constraints, in how many ways can Skynet pick two robots to destroy John Connor and

his rag tag group of humans.

Inputs

N Total

number of robots. Each robot is assigned a number from 0 to N1

(2 <= N <= 100000)

P Number

of pairs for which Skynet has information (2 <= P <= 100000)

This is followed by P pairs. Each pair has two numbers P and P each where 0<=P <=N1

and

0<=P <=N1

and P != P

Output

Number of ways in which Skynet can select 2 robots such that both the robots are different models.

Example Input:

4 2

0 1

2 3

Example Output:

4

Explanation:

Here robots 0 and 1 are of one model, say model A. And 2 and 3 are of another model, say B.

Therefore the total number of

possibilities of picking 2 robots such that no two robots are of the same model are (

0, 2), (0, 3), (1, 2)

and (1, 4) = 4

- -1of 1 vote
numbers are coming

continuously containing 0’s and 1’s same as above. Now tell me what data structure

you will use to tell me the starting of 1’s in least common time ??

- 0of 0 votes
Can we find majority element optimally than O(n) ?

Following with what if array is sorted ?

- 0of 0 votes
Can we tell in almost constant time that a perticuler array dont have majority element ?

- 0of 0 votes
find sum of longest increasing subsequence ?

Not the maximum sum,sum of longest subsequence.

Eg. 1, 8,2, 3

ans-> 6

- 0of 0 votes
Given a N-ary Tree. Return true if it follows Sum Property otherwise false.

- 0of 0 votes
Given a mxn grid, each of it’s element be either ‘.’, ‘R’, ‘G’ or ‘B’,

where ‘.’ -> empty, ‘R’ -> Red, ‘G’ -> Green, ‘B’ -> Blue

A Blue strip has width 1 and length greater or equal to one.

A Red strip has length 1 and width greater or equal to one.

If a Red strip and a Blue strip overlaps, the overlapped portion will become ‘G’.

Find the minimum number of strips required to cover the whole grid.

1<= m,n <=100

Input

5 5

..B..

..GRR

..B..

R....

R....

Output

4