## SDE1 Interview Questions

- 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

- 2of 2 votes
Given a sorted array with only 0's and 1's.Count the number of 0's.

e.g: 0 0 0 0 1 1

Ans: 4.

- 2of 2 votes
Given n (of size m) Linked lists

Print all set(head of linked list) of link list that intersect with each other.

e.g.

1-->2-->3-->4-->5

6-->7-->8-->4-->5

8->9->10->11->12

13->14->15->12

16->17->18

1 6

8 13

16

- 0of 0 votes
A non-empty zero-indexed array A consisting of N numbers is given. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that

A[0] = -5 A[1] = -3 A[2] = -1

A[3] = 0 A[4] = 3 A[5] = 6

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

Write a function

int absDistinct(int A[], int n);

that, given a non-empty zero-indexed array A consisting of N numbers, returns absolute distinct count of array A.

Assume that:

array A is sorted;

N is within the range [1..100,000];

each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].

For example, given array A such that

A[0] = -5 A[1] = -3 A[2] = -1

A[3] = 0 A[4] = 3 A[5] = 6

the function should return 5, as explained above.

?

- 0of 0 votes
A magnitude pole of an array A consisting of N integers is an index K such that all elements with smaller indexes have values lower or equal to A[K] and all elements with greater indexes have values greater or equal to A[K], i.e.

when and

when K < L < N.

For example, 5 is a magnitude pole of array A such that

A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9.

This array doesn't have any more magnitude poles.

Write a function

int magnitudePole(int A[], int n);

that given an array A consisting of N integers returns any of its magnitude poles. The function should return -1 if array A doesn't have any magnitude poles. Assume that . Assume that each element of the array is a non-negative integer not exceeding 1,000,000.

For example, given array A such that A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9

the function should return 5, as explained above.

?

- 0of 0 votes
Design and code the sudoku solver.