## Algorithm Interview Questions

- 0of 0 votes

AnswersN cows sitting on some point on the x-axis, each cow has some appetite, in other word hunger index. A cow can sleep of 1 unit of time or eat for one unit of time or move left or move right.

- xyz September 15, 2019 in India

We've got some vessels those are having infinite supply and they are placed on the x-axis. Find minimum time in which all cows appetite would be filled.

Input:

cow Apetitte = {1,1}

Vessle locations = {-1,1}

Answer would be 2 since both cow can go in different direction they would eat for one seconds. One second for moving and one second for eating.

This problem looks to be similar to rotten eggs/tomatoes.| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 2 votes

AnswersA special palindrome is a palindrome of size N which contains atmost K distinct characters such that any prefix between the size 2 to N-1 is not a palindrome.

- Prashanthwagle360 September 08, 2019 in India

You need to count the number of special palindromes

For example, abba is a special palindrome with N=4 and K=2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.

If N=3, K=3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So answer will be 6.

Input format

Two integers N and K

Output format

Answer modulo 10^9+9

Constraints

1<=N,K<=10^9

Sample TC

3 3

Output

6| Report Duplicate | Flag | PURGE

HackerEarth Problem Setter Algorithm - 0of 0 votes

AnswersGiven a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

- Nits September 07, 2019 in United States| Report Duplicate | Flag | PURGE

Facebook Software Development Manager Algorithm - 0of 0 votes

AnswersImplement auto complete for IDE, you will be given strings of classes and input, input can be like MVC, MoClick, MouseClickHand

- neer.1304 August 17, 2019 in United States

For MouseClickH => MouseClickHandler

MVC => can match to any classes where first word starts from M then V then C| Report Duplicate | Flag | PURGE

Pinterest Software Engineer / Developer Algorithm - 0of 0 votes

AnswersA stream of data representing the price of a commodity is being read. The data is of the format (price:Int, timestamp:Option[Long]).

- abzy August 17, 2019 in India

If the timestamp is missing, it means the price has to be deleted.

If timestamp is old, it means the previous data with same timestamp has to be updated with this new price.

Else it's the new price of the commodity.

At any point of time the latest, max and min of the price has to be printed.

If the delete instruction is received through the stream, the min/max should be updated accordingly.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 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

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

AnswersGiven a binary matrix of 0 and 1 where we can move in 4 directions left, right, top, down and we can only pass through 1's. Find the shortest path from given source coordinate (a,b) to destination (m,n) given we can flip any one of the zero to one.

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

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase.

- Rising star August 07, 2019 in India

Constraint: A word cannot be a part of more than 10 sentences.

Examples:

Input:

Sentences:

1. Strings are an array of characters.

2. Sentences are an array of words.

Phrases:

1. an array of

2. sentences are strings

Output:

Phrase1 is present in sentences: 1,2

Phrase2 is present in sentences: None

Since each word in phrase 1 exists in both the sentences,

but all the words in second phrase do not exist in either.| Report Duplicate | Flag | PURGE

Flipkart SDE1 Algorithm - 0of 0 votes

AnswersYou are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge. Your task is to find the shortest path from a to b satisfying the above condition.

- Rising star August 07, 2019 in India| Report Duplicate | Flag | PURGE

Uber Software Engineer / Developer Algorithm - 0of 0 votes

AnswersYou are given a n x m grid consisting of values 0 and 1. A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed. You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell. Your task is to calculate the total number of ways of reaching the target.

- Rising star August 07, 2019 in India

Constraints :-

1<=n, m<=10, 000| Report Duplicate | Flag | PURGE

Uber Software Engineer / Developer Algorithm - 0of 0 votes

AnswersThere is a meeting scheduled in an office that lasts for time t and starts at time 0. In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. Note that the duration of the presentation can't be changed. You can only change the start and end time. Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.

- Rising star August 07, 2019 in India

Constraints :-

1<=t<=1, 000, 000, 000

0<=k<=n

1<=n<=100, 000

e[i]<=s[i+1], 0<=i <n-1

s[i] < e[i] for 0<=i<=n-1| Report Duplicate | Flag | PURGE

Uber Software Engineer / Developer Algorithm - 0of 0 votes

AnswerPrint numbers that matches with the index in given non-duplicate unordered array.

- HR August 03, 2019 in United States| Report Duplicate | Flag | PURGE

None Algorithm - 0of 0 votes

AnswersWrite a program to encode a string from --> ABABXBYZXXX --> X4B3A2Y1Z1 (what should be the storage requirements for optimal conversion of 10TB file)

- HR August 03, 2019 in United States| Report Duplicate | Flag | PURGE

None Algorithm - 1of 1 vote

AnswerSuppose there is a function given to you that:

`def get_friends( person_id ) { /* returns friends of person */ }`

How you are now going to recommend friends to a person based on number of mutual friends? So, come up with the function:

- NoOne August 02, 2019 in India`def friend_reco( person_id, max_no_of_friends ){ }`

| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven billions of Identity cards of the form :

`card : { my_id : "my id", "moms_id" : "mom id", "dad_id" : "dads id" }`

If one gives you two Person's id, how can you tell if these 2 persons are blood related.

So, write a function that is:

- NoOne August 02, 2019 in India`def is_blood_related( person_id_1, person_id_2 ) // go on..`

| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven an array of integers find the maximum value of a[i] - a[j] + a[k]

- ASimpleCoder August 01, 2019 in India

with constraints i < j < k and a[i] < a[j] < a[k]| Report Duplicate | Flag | PURGE

Uber Software Developer Algorithm - 0of 0 votes

AnswersYou're running a pool of servers where the servers are

- neer.1304 July 28, 2019 in United States

numbered sequentially starting from 1. Over time, any

given server might explode, in which case its server

number is made available for reuse. When a new

server is launched, it should be given the lowest available number.

Write a function which, given the list of currently

allocated server numbers, returns the number of the next server to allocate.

For example, your function should behave something like the following:

>> next_server_number([5, 3, 1])

2

>> next_server_number([5, 4, 1, 2])

3

>> next_server_number([3, 2, 1])

4

>> next_server_number([2, 3])

1

>> next_server_number([])

1

Server names consist of an alphabetic host type (e.g. "apibox") concatenated with the server number,

with server numbers allocated as before (so "apibox1",

"apibox2", etc. are valid hostnames).

Write a name tracking class with two operations,

allocate(host_type) and deallocate(hostname).

The former should reserve and return the next

available hostname, while the latter should release

that hostname back into the pool.

# For example:

#

# >> tracker = Tracker.new()

# >> tracker.allocate("apibox")

# "apibox1"

# >> tracker.allocate("apibox")

# "apibox2"

# >> tracker.deallocate("apibox1")

# nil

# >> tracker.allocate("apibox")

# "apibox1"

# >> tracker.allocate("sitebox")

# "sitebox1"| Report Duplicate | Flag | PURGE

Stripe Software Engineer Algorithm - 0of 0 votes

AnswersWrite a map implementation with a get function that lets you retrieve the value of a key at a particular time.

- neer.1304 July 28, 2019 in United States

t:0 A =1

t:2 A = 2

get(A, t:1) -> 1

get(A, t:3) -> 2| Report Duplicate | Flag | PURGE

Stripe Software Engineer Algorithm - 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

AnswersImplement a thread-safe data structure which can keep track of number of incoming

- neer.1304 July 22, 2019 in United States

requests grouped by IP Address over a time window. Add support for grouping by other

attributes such as BrowserAgent.| Report Duplicate | Flag | PURGE

Rubrik 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 2 votes

AnswersQuestion: Can you break the given string into words, provided by a given hashmap of frequency of word as <word: n>

- nitinguptaiit July 18, 2019 in United States

Example:

HashMap -> {"abc":3, "ab":2, "abca":1}

String: abcabcabcabca

output: Yes; [ abc, abc, abc , abca ]

Example:

HashMap -> {"abc":3, "ab":2}

String: abcabab

output: No

Example:

HashMap -> {"abc":3, "ab":2, "abca":1}

String: abcx

output: No| Report Duplicate | Flag | PURGE

Facebook 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

AnswerA set of points in the 2D plane. Find the first k number of points with the shortest distance to the point (0, 0), where k is a positive integer.

- fz July 13, 2019 in United States

e.g.

Input

{[-16, 5], [-1, 2], [4, 3], [10, -2], [0, 3], [-5, -9]}

k = 3

Output:

{[-1, 2], [0, 3], [4, 3]}

.| Report Duplicate | Flag | PURGE

Algorithm

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

Open Chat in New Window