## SDE1 Interview Questions

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

- 0of 0 votes
There is a zoo and there are several groups(number of groups:K) of people for tour. Each group is having different size (g1,g2,g3…gK). There is one bus with capacity C. Journey starts from a point and bus will come back to the same point. A group can only be included in the bus if all the members of the groups can be accumulated in bus. After coming back from the tour, each group in the bus will again wait in the queue at the bus-stand. Bus-driver earns a rupee for each person travelled. You have to find the earning of the bus driver after R rounds.

For example :

Number of groups G = 4

Group size for each group : 2 4 3 5

Bus capacity : 7

Number of rounds R : 4

queue : (from front side) 2 4 3 5

First round : 2 4 (we can’t take 3rd group as 3 members can’t be accumulated after 2 and 4.)

queue : 3 5 2 4 (1st and 2nd group are enqueued. i.e. 2 and 4)

Second round : 3

queue : 5 2 4 3

Third Round : 5 2

queue : 4 3 5 2

Fourth Round : 4 3

After 4 rounds, total earning is 6+3+7+7 = 23.

- 0of 0 votes
Design a Traffic signal . List all entities and classes involved. How will you handle pedestrian crossings etc.

- 0of 0 votes
esign a contact list for a cell phone which can add & search really quick and is scalable.

- 0of 0 votes
Design a mobile cab booking application (just screens and functionalities) on board.

- 0of 0 votes
A sender will send a binary string to a receiver meanwhile he encrypt the digits. You are given a encrypted form of string. Now, the receiver needs to decode the string, and while decoding there were 2 approaches.

First, receiver will start with first character as 0; S[0] = 0, P[1] = S[1] + S[0], P[2] = S[2] + S[1] + S[0] and so on.

Second, Receiver will start with first character as 1; S[0] = 1, P[1] = S[1] + S[0], P[2] = S[2] + S[1] + S[0] and so on.

You need to print both the strings, after evaluation from both first and second technique. If any string will contain other that binary numbers you need to print NONE.

- 0of 0 votes
Given a normal die and a blank die. Fill in the blank die such that probability of sum of the number from both die is same for all the resulting sum and sum has a range from 1 to 12

- 0of 0 votes
Given a pond where all the stones are lined at a distance of one unit (C in each row and there are R such rows), each stone has a special value which denotes the length of the jump the frog can make i.e if frog is on stone (x,y) and value is k then frog can jump to (x+dx,y+dy) where dx+dy=k and frog doesn’t leave the bounds.Find the min number of jumps to reach the stone at (R,C).

- 2of 2 votes
Given a lane where there are various houses each containing a fixed amount of gold. Now a robber has to rob the houses such that when he robs a house the adjacent one cannot be robbed.Calculate the maximum amount of gold collected by him.

- 0of 0 votes
Given a network of roads connecting cities and capacity of each road(same for all roads)as well as their cost of repair(unique for each road) we are given number of buses(n) running between pair of cities using shortest path only. (Capacity of road= No of buses allowed on that road).

Unsafe roads are road where no of buses on the road > Capacity of the road.

Now given n we have to minimize the overall cost of all unsafe roads.

- 1of 1 vote
Given a review paragraph and keywords, find minimum length snippet from paragraph which contains all keywords in any order.

- 0of 0 votes
Design notification system (notify the customer with a message)

Client (delivery boy, company updates etc)

Services (Email, SMS, Watsapp)

Scaling up, fault tolerance & failure management

Flexible modifiability of clients & services

- 1of 1 vote
Dictionary of words is given

i.e. [“cat”, “dog”, “rat”, “catratdog”, “catter”]

Compound word: A word, which can be split into more than 1 valid words

get compound word, with longest string length.

- 0of 0 votes
N people are there.

knows(A,B) return true if A knows B, else false.

Celebrity: A is called a celebrity

If A knows none

Everyone knows A

Get celebrity, with less number of knows() method usage.

- 0of 0 votes
You are given a catalog of books, which have following attributes.

Name

Author

Publisher

Publish year

Category

Price

Count (sold)

Implement following APIs on top of this catalog

addBookToCatalog(Book)

searchBook(by partial book name/author)

getMostSoldBooks(by author name/category, limit)

Expectations:

Maintain DB on memory

Code should be readable. Design, handle naming convention,handle exceptions & should be running

- 0of 0 votes
Find last cell visited in 2D matrix traveresed in Spiral Fashion

- 0of 0 votes
Design an online poker game.

- 0of 0 votes
Given a server with a stack with some initial state say 1 Users can modify the stack using regular ops eg push 2 , pop etc and each op causes a version change. i.e version 1 : 1 , version 2 : 2,1 , version 3 : 3,2,1 , version 4 : 2,

You have to design it s.t person can ask for any version of the stack.

Hint : keep copies every k times and keep the ops in an nonvolatile memory

- 0of 0 votes
Given any language , you use libraries , which might use more lib etc . Find the order of building the libraries