## Indeed Interview Questions

- 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

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

Open Chat in New Window