## Recent Interview Questions

- 1of 3 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 - 1of 1 vote

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

AnswersNext Sunday is Ayan’s 4th birthday and a lot of guests are invited for his birthday celebration. All of them are getting gifts for Ayan and his y-1 number of siblings. There are x number of guests coming to the party and each of them presented each kid some integer number of gifts (possibly zero). The guests are numbered with integers from 1 to x and all kids are numbered with integers from 1 to y. For all 1 ≤i ≤x the minimum number of gifts, which i-th guest presented to some kid is equal to gi and for all 1 ≤j ≤y the maximum number of gifts, which j-th kid received from some guest is equal to kj.

- anoophky September 06, 2019 in United States

Let ai,j be the number of gifts which the i-th guest give to the j-th kid. Then gi is equal exactly to the minimum among values ai,1,ai,2,…,ai,y and kj is equal exactly to the maximum among values g1,j,g2,j,…,gx,j.

You are interested in the minimum total number of gifts that guests could present, so you need to minimize the sum of ai,j for all (i,j) such that 1 ≤i ≤x and 1 ≤j ≤y. You are given the numbers g1,…,gx and k1,…,ky, determine this number.

Input Format

The first line contains two integers x and y, separated with space — the number of guests and kids, respectively (2≤x,y≤100000). The second line contains x integers g1,…,gx, separated by spaces — gi is equal to the minimum number of gifts, which i-th guest presented to some kid (0≤gi≤1000). The third line contains y integers k1,…,ky, separated by spaces — kj is equal to the maximum number of gifts, which j-th kid received from some guest (0≤kj≤1000).

Output Format

If the described situation is impossible, print −1. In another case, print the minimum total number of gifts, which guests could have presented and all conditions could have satisfied.

Sample Input

3 2

1 2 1

3 4

Sample Output

12| Report Duplicate | Flag | PURGE

- 0of 0 votes

AnswersMr. Stark is the owner of Stark industries, a manufacturer of weaponry.

- anoophky September 06, 2019 in United States

A local Mafia group has hijacked one of the factories in the desert.

The mafias want to transport the weapons from the factory to their base camp, and use a single truck to do it.

But, every kilometer the truck travels with the weapons, one weapon falls off and breaks. The truck can only travel integral values of distance, and will lose 1 weapon for every km travelled.

The weapons can be unloaded at any point from the truck, and can be picked up again later.

Given the number of weapons X, max capacity of the truck Y and distance between the factory and the base Z, find the maximum number of weapons that can be transferred intact from the factory to the mafia base.

Function Description:

findMaxWeapons function takes the following parameters:

X - the number of weapons

Y - max capacity of the truck

Z - distance between the factory and the base| Report Duplicate | Flag | PURGE

- 0of 0 votes

Answeryou are given string of digits, a value x and N. you have to divide that string in ((i-1)*x+1,min(i*x)) parts.

- acharyashailendra1 September 05, 2019 in India

for example a String is ="1234567891" and x=5,N=10 then

there will be 2 partition of string since x=5

[12345] end [67891]

you have to find kth min number from these combinations. for example k=3 then ans should be 17

combination will happen like every digit from 1st partition will concanate with other partition digits

so if there were three partition for string 123456789 then it could be like

[123][456][789]

and if k=3 then ans would be 149| Report Duplicate | Flag | PURGE

- 0of 0 votes

Answersrecently I came across one good design question. I need your thoughts how to proceed. Assume a big IT hub, like any co-work space / Microsoft / amazxon/ google etc office (which has multiple floors , each floor has multiple meeting rooms , work stations etc) . At any point of time , an admin should be able to know 1. how many people are there in that facility 2. How many people at each floor wise 3. If he chooses any cons room, he must be able to fetch how many people in that conf room at that time . This normally used for any kind of evacuation etc

- gopi.komanduri September 02, 2019 in United States

I tried with http protocol , but interviewer said http is over kill , he hints on some IoT communication etc .. however , want to know what is the best way to solve it| Report Duplicate | Flag | PURGE

System Design - 0of 0 votes

AnswersA string can contain only a, b or c. There cannot be 2 consecutive same character. First and the last character cannot be the same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple-answer display lexicographically smallest string. For no answer possible display “Not Possible”.

- anoophky August 31, 2019 in India| Report Duplicate | Flag | PURGE

Directi SDE1 String Manipulation - 0of 0 votes

Answersrepeat string n^n times without using extra space

- acharyashailendra1 August 30, 2019 in India| Report Duplicate | Flag | PURGE

Myntra - 0of 0 votes

AnswerDesign and implement rate limiter for limiting api calls for a service distributed multiple users.

- acharyashailendra1 August 27, 2019 in India| Report Duplicate | Flag | PURGE

SDE-2 - 0of 0 votes

AnswerDesign data structures which support millions of products coming in streaming manner, we need to find at any moment what are top n products at any day

- acharyashailendra1 August 27, 2019 in India| Report Duplicate | Flag | PURGE

SDE-2 - 0of 0 votes

AnswersYou run a linux binary provided by a customer and don’t get any output. The customer assures you it should provide output. You don’t have the source code for this binary. How would you debug this? What tools / techniques can you use ? *

- donk August 26, 2019 in United States for Engineering| Report Duplicate | Flag | PURGE

Notfamous Technical Support Engineer Unix - 0of 0 votes

AnswersA customer raises a support ticket as they have a serious situation which has caused them data loss. You determine the issue is a bug in the product which is already fixed in a later version. Please write a response to the customer support ticket.

- donk August 26, 2019 in United States for Engineering| Report Duplicate | Flag | PURGE

Notfamous Technical Support Engineer Trouble shooting - -1of 1 vote

AnswersAs you know, most Operating Systems are written in Java, what’s special about pointers in Java ? *

- donk August 26, 2019 in United States for Engineering| Report Duplicate | Flag | PURGE

Notfamous Technical Support Engineer Java - 0of 0 votes

AnswersHow would I store 100 million documents (~40 Gigabytes) in 32 Gigabytes of RAM? The documents are in JSON format. In other words how do couchbase, redis, and mongodb work in memory?

- donk August 26, 2019 in United States for Engineering| Report Duplicate | Flag | PURGE

Notfamous Technical Support Engineer Cache - 0of 0 votes

AnswersA co-ordinate plane was given. On each point (x, y) there are x+y number of apples on it. A person is standing on (0, 0) and he wants to buy a square plot having N number of apples inside it (including the periphery). Question was to return the value of perimeter of that square plot given N.

- 200MITTALGAUTAM August 26, 2019 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 - -2of 2 votes

Answers+27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana

- tonnyelt August 25, 2019 in United States for SSD CHEMICAL SOLUTION| Report Duplicate | Flag | PURGE

SSD CHEMICAL SOLUTION +27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana - -2of 2 votes

AnswersWe are specialized in the production and distribution of ssd chemical solution used to clean all types of black notes any color currency, stain and deface bank notes. Our team are highly qualified and are always ready to handle the cleaning perfectly. Our solutions are 100 % pure and some of them are listed below.

- tonnyelt August 25, 2019 in United States for SSD CHEMICAL SOLUTION

buy-calcium-oxide-online

buy-first-grade-counterfeit-bank-notes

buy-high-quality-seconal-sodium-here

buy-liquid-red-mercury-online-at-the-best-price

buy-money-developer-machines-at-reasonable-prices-from-us

buy-pk58-solution

buy-ssd-activation-powder-online

buy-ssd-chemical-solution-at-affordable-prices

buy-undetectable-euros-bank-notes-online

get-the-best-black-money-cleaning-chemical-solution

product=high-quality-vectrol-paste-for-sale

ssd-universal-chemical-solution-sale

We need the above information for easy communication.

* Note that our customers privacy is our main concern.

Tel: +27655765355

Email:makintu211@gmail.com| Report Duplicate | Flag | PURGE

SSD CHEMICAL SOLUTION +27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana - 1of 1 vote

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

AnswersHellow everyone guides me about how to rank our website in a search engine according to Google algorithms

- ImmacBytes August 21, 2019 in United States| Report Duplicate | Flag | PURGE

- 2of 2 votes

AnswersA mobile phone company wants to deploy network of cell towers to provide good signal coverage for its customers. But it doesn't want to have too many towers because they can interfere with one another. All towers are laid out over a 2-dimensional surface and that towers have same sized circular signal zone. You can determine whether their signal zones will overlap in 0 1) time. Give a parallel algorithm for choosing maximal subset of towers that cover non-overlapping areas.

- MaryJane August 19, 2019 in United States

I was not sure if this can be solved using DP?| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswersWhat data structure will you use to suggest friends in FB

- Nits August 19, 2019 in India| Report Duplicate | Flag | PURGE

RazorPay Software Development Manager - 0of 0 votes

AnswersIf ads were removed from YouTube, how would you monetize it?--Associate account strategist, January 2016

- jerryalston11 August 18, 2019 in United States| Report Duplicate | Flag | PURGE

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

Answerselect b.dname,sum(sal) from dept b right join emp a ON (a.deptno=b.deptno)group by deptno from emp a ;

- garkoti.himani01 August 15, 2019 in United States| Report Duplicate | Flag | PURGE

- 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

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

Open Chat in New Window