## SDE-2 Interview Questions

- 2of 2 votes

AnswerA dictionary is combination of characters from a-z. let's say a=1,b=2.. and so on z=26. you are given n and k. you have to find sum of length k from given combination.

- acharyashailendra1 August 21, 2019 in India

for example n=51 and k=3 then your answer should be =axz

as there can be many combination for given sum so it is suggested to print those string which comes first in dictonary| Report Duplicate | Flag | PURGE

LendingKart SDE-2 Data Structures - 1of 1 vote

Answersbeautiful numbers are those numbers which contains digit only 4 and 5 also they are palindrome.length of number can't be odd. for example

- acharyashailendra1 August 21, 2019 in India

44,55,4554 are beautiful numbers where as 38, 444 are not.

your task is to find nth number in this series. let's say if n=4 then output should be 4554. for n=1 output will be 44 always.| Report Duplicate | Flag | PURGE

LendingKart SDE-2 Data Structures - 0of 0 votes

AnswersThere are N stations in a certain region, numbered 1 through N. It takes di,j minutes to travel from Station i to Station j (1 ¥leq i, j ¥leq N)$. Note that di,j=dj,i may not hold.

- neer.1304 August 15, 2019 in United States

You are now at Station 1. From here, you have to visit all the stations exactly once. We assume that you have already visited Station 1. However, due to your schedule, there are M restrictions that must be satisfied. The format of each restriction is as follows:

• Station si must be visited before Station ti. (1≤i≤M)

Find the minimum time required to visit all the stations. Note that the last station to visit can be any of the stations.

Constraints

• 1≤N≤14

• 0≤di,j≤108 (1≤i,j≤N)

• di,i=0 (1≤i≤N)

• 0≤M≤N(N−1)⁄2

• 1≤si,ti≤N (1≤i≤M)

• si≠ti (1≤i≤M)

• There exists a path visiting all the stations under the given restrictions.

Input

Input is given from Standard Input in the following format: N d1,1 … d1,N : dN,1 … dN,N M s1 t1 : sM tM

Output

Print the minimum time required to visit all the stations.

Sample Input 1

4

0 2 3 4

1 0 3 4

1 2 0 4

1 2 3 0

3

1 2

2 3

3 4

Sample Output 1

9

Due to the restrictions, we can only travel as follows: Station 1 → Station 2 → Station 3 → Station 4. Thus, the answer is 2+3+4=9 and we should print 9.

Sample Input 2

3

0 1 20

1 0 20

10 20 0

0

Sample Output 2

21| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm - 0of 0 votes

AnswersYou are given an array of length N consisting of integers, a={a1,…,aN}, and an integer L.

- neer.1304 August 15, 2019 in United States

Consider the following subproblem:

• You are given an integer S.

• Find the largest value in the interval [S,S+L−1] in the sequence a, that is, find max(aS,…,aS+L−1).

Solve this subproblem for every S=1,…,N−L+1.

Constraints

• 1≤N≤105

• 1≤L≤N

• −109≤ai≤109

Input

Input is given from Standard Input in the following format: N L a1 … aN

Output

Print the answers in N−L+1 lines. The i-th line should contain the answer to the subproblem where S=i.

Sample Input 1

5 3

3 4 2 1 5

Sample Output 1

4

4

5

• The subproblem where S=1 asks the largest value among a={a1,a2,a3}={3,4,2}, so the first line in the output should contain 4.

• The subproblem where S=2 asks the largest value among a={a2,a3,a4}={4,2,1}, so the second line in the output should contain 4.

• The subproblem where S=3 asks the largest value among a={a3,a4,a5}={2,1,5}, so the third line in the output should contain 5.

Sample Input 2

4 1

-1000000000 1000000000 -1000000000 1000000000

Sample Output 2

-1000000000

1000000000

-1000000000

1000000000| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm - 0of 0 votes

AnswersThere are N rooms in a row. The i-th room (1≤i≤N) from the left is called Room i. You are given M closed intervals [ai,bi] (1≤i≤M). At time 0, all rooms j such that ai≤j≤bi for some i (1≤i≤M) are occupied, and the other rooms are vacant.

- neer.1304 August 15, 2019 in United States

You are given Q queries. The i-th query (1≤i≤Q) represents an event happening at time i, as follows:

• In the i-th query (1≤i≤Q), a closed interval [ci,di] (1≤i≤Q) is given.

• This query asks: "Are all rooms j such that ci≤j≤ci" vacant?

• If all those rooms are vacant, the query should be responded by OK, then all rooms j such that ci≤j≤ci get occupied.

• Otherwise, the query should be responded by OK, then nothing happens.

Process these queries.

Constraints

• 1≤N≤109

• 0≤M≤1000

• 1≤ai≤bi≤N (1≤i≤M)

• There are no rooms k such that ai≤k≤bi and aj≤k≤bj at the same time (1≤i<j≤M).

• 1≤Q≤1000

• 1≤ci≤di≤N

Input

Input is given from Standard Input in the following format: N M a1 b1 : aM bM Q c1 d1 : cQ dQ

Output

Print the responses in Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

5 2

1 1

4 4

3

3 3

2 3

5 5

Sample Output 1

OK

NG

OK

At time 0, Room 1 and 4 are occupied.

• At time 1, a query asks: "is Room 3 occupied?" Since Room 3 is vacant, we should print OK, then Room 3 gets occupied.

• At time 2, a query asks: "are Room 2 and 3 occupied?" Since Room 3 is occupied, we should print NG.

• At time 3, a query asks: "is Room 5 occupied?" Since Room 5 is vacant, we should print OK, then Room 5 gets occupied.

Sample Input 2

1000000000 1

2 999999999

4

1 1000000000

500000000 500000000

1 1

1000000000 1000000000

Sample Output 2

NG

NG

OK

OK| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm - 0of 0 votes

AnswersYou are given N records. The content of the i-th record is represented by a string Si. These records are managed in pages, as follows:

- neer.1304 August 15, 2019 in United States

• The first page: contains the first, ..., K-th records.

• The second page: contains the (K+1)-th, ..., 2K-th records.

• The third page: contains the (2K+1)-th, ..., 3K-th records.

• :

• The ceil(N⁄K)-th page: contains the ((ceil(N⁄K)−1)K+1)-th, ..., N-th records.

Here, ceil(X) represents the smallest integer not less than X. Print the contents of the records contained in the M-th page, in the order given.

Constraints

• 1≤N≤100

• 1≤K≤N

• 1≤M≤ceil(N⁄K)

• 1≤|Si|≤100 (1≤i≤N), where |S| is the length of S.

• Si is a string consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N K M S1 S2 : SN

Output

Print the contents of the records contained in the M-th page, in the order given. Use L lines, where L is the number of records that should be printed. The i-th line (1≤i≤L) should contain the content of the i-th record contained in the M-th page.

Sample Input 1

5 2 2

aaa

bbb

ccc

ddd

eee

Sample Output 1

ccc

ddd

• The first page contains the first and second records, which are aaa and bbb.

• The second page contains the third and fourth records, which are ccc and ddd.

• The third page contains the fifth record, which is eee.

Since the second page is requested, we should print ccc in the first line and ddd in the second line.

Sample Input 2

7 4 2

this

is

not

displayed

this

is

displayed

Sample Output 2

this

is

displayed| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm - 0of 0 votes

AnswerMake a system that returns the average number of hits on the site per minute from the past 5 minutes

- neer.1304 August 15, 2019 in United States| Report Duplicate | Flag | PURGE

Indeed SDE-2 Software Design - 0of 0 votes

AnswerYou're given an array of integers sorted ( [1,2,3,5,6,7,10]) you need to serialize and compress this array into a string (1-3, 5-7,10)

- neer.1304 August 15, 2019 in United States| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm - 0of 0 votes

AnswerGiven two points on a directed acyclic graph determine their least common ancestor, give it's time complexity, and describe any improvements you could make (if possible).

- neer.1304 August 15, 2019 in United States| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm - 1of 1 vote

AnswersUse synchronized, wait() and notify() to write a program such that below mentioned conditions are fulfilled while reading and writing data to a shared resource.

- neer.1304 July 26, 2019 in United States

When a write is happening, no read or other write should be allowed(read and write threads should wait)

When a read is happening, no write should be allowed (write threads should wait) but. other read threads should be able to read.

Donot use any API classes e.g. ReadWriteLock, AtomicInteger etc..| Report Duplicate | Flag | PURGE

Microsoft SDE-2 Java - 0of 0 votes

AnswersDesign election voting system. Election would be country wide. System should be scalable, available and consistent.

- neer.1304 July 26, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Software Design - 0of 0 votes

AnswersImplement following method of ScheduledExecutorService interface in Java

- neer.1304 July 23, 2019 in United States

schedule(Runnable command, long delay, TimeUnit unit)

Creates and executes a one-shot action that becomes enabled after the given delay.

scheduleAtFixedRate(Runnable command, long initialDelay, long period, TimeUnit unit)

Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given period; that is executions will commence after initialDelay then initialDelay+period, then initialDelay + 2 * period, and so on.

scheduleWithFixedDelay(Runnable command, long initialDelay, long delay, TimeUnit unit)

Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given delay between the termination of one execution and the commencement of the next.| Report Duplicate | Flag | PURGE

Uber SDE-2 Algorithm - 0of 0 votes

AnswersGiven a string select two non-overlapping strings that are same and remove them. Perform this operation recursively till there are no desired strings.

- neer.1304 July 20, 2019 in United States

Print the number of possible substring after completing above operation.

Ex - abcc

Duplicate non-overlapping substring - abc

After removing abc from we are left with 1 substring abc.| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersIn a 2-D matrix of m*n select m-1 elements from each row such that that the resulting sum is minimum and each column is selected atleast once.

- neer.1304 July 20, 2019 in United States

Ex -

2 3 5

3 2 5

4 4 7

Selecting (2,3) from 1st row, (2,5) from 2nd row and (4,4) from 3rd row would result in minimum sum of 20| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersFind LCA for list of nodes of a tree

- neer.1304 July 17, 2019 in United States

Function defined as below -

TreeNode findLCA(TreeNode root, List<TreeNode> nodes)| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersGiven two numbers m and n. Find all numbers between these two numbers such that difference between adjacent digit is 1

- neer.1304 July 01, 2019 in United States

For ex m =0 n =22

O/p - 0,1,2,3,4,5,6,7,8,9,10,12,21| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersCode an algorithm for a game consisting of two players. The input is a positive integer x. Each round, a player deducts a perfect square from the number. The player can choose any perfect square as long as it is less than or equal to the current number and greater than 0. The current player wins if the number becomes 0 after his deduction.

- Thomas June 19, 2019 in United States| Report Duplicate | Flag | PURGE

Salesforce SDE-2 Dynamic Programming - 0of 0 votes

AnswersP0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.

- neer.1304 June 11, 2019 in United States| Report Duplicate | Flag | PURGE

Curefit SDE-2 Algorithm - 0of 0 votes

AnswersGiven a nested list of integers, return the sum of all integers in the list weighted by their depth.

- koustav.adorable June 09, 2019 in United States

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]

Output: 8

Explanation: Four 1's at depth 1, one 2 at depth 2.

Example 2:

Input: [1,[4,[6]]]

Output: 17

Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.| Report Duplicate | Flag | PURGE

SDE-2 Algorithm - 0of 0 votes

AnswersUse the location data getting generated from multiple delivery boys moving on the ground to estimate time which a delivery boy will take to move from point A to point B in an area. Additionally, try to do this in real time so that it can be used in assigning delivery boys and minimising delivery time in real time.

- neer.1304 May 31, 2019 in India| Report Duplicate | Flag | PURGE

Swiggy SDE-2 design - 0of 0 votes

AnswersIn a binary tree if the neighbours are set on fire for every node , find the path to optimally set the entire tree on fire.

- neer.1304 May 31, 2019 in India| Report Duplicate | Flag | PURGE

Swiggy SDE-2 Algorithm - 0of 0 votes

AnswersGiven an input stream of Swiggy order timestamps and costs, at any instant find the costliest order in the last X mins

- neer.1304 May 31, 2019 in India| Report Duplicate | Flag | PURGE

Swiggy SDE-2 Algorithm - 0of 0 votes

AnswerDesign a system to upload images with tags. The tags should be searchable and search should return images linked to those tags.

- arnold086 May 25, 2019 in India| Report Duplicate | Flag | PURGE

Amazon SDE-2 System Design - 0of 0 votes

AnswerI dont remember the exact problem anymore. but the problem's solution included going through an array and at every step taking 2 minimum element and adding the result. this also includes the result itself.

- Desi May 13, 2019 in United States for Robotics

so lets say for following array:

2,54,4,10,1,7

you first take 1 and 2 and add

then add the result 3 to the array

so now your array looks like :

3,54,4,10,7

then you take 3 and 4 and add them and add result back

I basically used a heap where i take two mins and add them and add the result back to heap.

I have give amazon online test twice in last 8 months and both the times the first question was about heaps and second something about finding shorted path in a grid between two cells| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersThe problem was very similar to the problem from geeksforgeeks:

- Desi May 13, 2019 in United States for Robotics

Shortest distance between two cells in a matrix or grid

Given a matrix of N*M order. Find the shortest distance from a source cell to a destination cell, traversing through limited cells only. Also you can move only up, down, left and right. If found output the distance else -1.

instead of source and destination, they asked for robot to be able to get rid of obstacle at a certain cell.

I have give amazon online test twice in last 8 months and both the times the first question was about heaps and second something about finding shorted path in a grid between two cells| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersDesign amazon online book store.

- Desi May 13, 2019 in United States for Robotics| Report Duplicate | Flag | PURGE

Amazon SDE-2 System Design - 0of 0 votes

AnswersI am given jobs with starttime and end time and we unlimited VMs. at any point a VM can only take one job. so bascially I had to find overlapping jobs and assign them to different machines and those that are not overlapping could be assigned to same machines. The tricky part was when there are two different overlaps and they could be assigned to 2 machines instead of all overlapping jobs being assigned to different machines.The method should return minimum number of VMs used to finish all jobs.

- Desi May 13, 2019 in United States for Robotics

I mentioned sorting the jobs based on start time. and then returning number_of_overlapping jobs +1. but again in some cases if there are two different overlaps which could be assigned to two machines then we need to take care of that.| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersExpression tree evaluation and also write the class for the node and tree itself. (just basic structure like node and data)

- Desi May 13, 2019 in United States for Robotics| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersLRU cache. Basically started off with how would I store values and get them from memory for faster access. So I mentioned HashMap. and then interviewer added more info about deleting least recently used element.

- Desi May 13, 2019 in United States for Robotics| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 1of 1 vote

AnswersGiven movement of Robot -

- neer.1304 April 22, 2019 in United States

G-GO one unit

L-Turn left

R-Turn right

Given an input of string have to find whether there exists a circle which the robot would traverse. Input of string is the set of G,L,R have to return yes or no.| Report Duplicate | Flag | PURGE

Flipkart SDE-2 Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window