## SDE-2 Interview Questions

- 0of 0 votes
Given a 2 D array with m Entry points (which are on the edges) and n exit points which are on the edges give the total number of paths that are possible.

- 0of 2 votes
Given an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].

**Example:**

For n=6

6 7 8 1 2 3

Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays

we can get 1 2 3 6 7 8 , that is sorted.

How can we figure out minimum number of swaps in most effective way ?

- 0of 0 votes
Scenario : Multi Seller E-commerce Website

Given a list of products in a customer basket find the minimum number of seller required to deliver his order,so as to optimise shipping part.

Assuming you have already have below data

Customer orders products : P1,P2,P3,P4,P5,P6

Products and seller mapping

P1 = [1,2,3,4]

P2=[2,4,5,6]

where 1,2,3 etc denotes seller_ids.

p1

- 0of 0 votes
For a given matrix, find the maximum product of k elements. The elements can be formed from continuous 4 elements horizontally, vertically or diagonally. Eg: For k= 4, the maximum product is (6*4*7*9) from the last column,

1 2 0 -1 4

3 1 2 4 6

0 2 3 1 4

1 3 2 0 7

2 1 3 2 9

- 0of 0 votes
Given a function rev(int i) which reverses the segment of array ar[] from 0-i, Implement a function sort() using rev().

- 0of 0 votes
Design your own String Pooling system. It should return a String with request of more length. String pool should have strings of different sizes available. When requested, it should just be returned to client and when client is done using string, it should be added back to string pool for other client to use.

- 1of 1 vote
You have a file with 100 billion URLS, find first unique URL.

- 1of 1 vote
Design a data structure for following operations in O(1) time.:

insert

remove (FIFO)

find MODE

- 0of 0 votes
Design an LRU cache, where you remove an element not only by time lapsed since last used but also by a cost associated with each element. F(t, c) is a method to find weight for each element. Where c is cost and t is time since last used.

- 1of 1 vote
Design a TinyURL like Service.

- 0of 0 votes
you have experience with a 3x3 Sudoku.Think about 2*2 sudoku:

The array has 4 rows and 4 columns.

The numbers 1, 2, 3 and 4, each appears exactly once in each row.

The numbers 1, 2, 3 and 4, each appears exactly once in each column.

The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 1, 2.

The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 3, 4.

The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 1, 2.

The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 3, 4.

Your task is:

1. Count all possible different solutions of the 2*2 sudoku.

2.Print all solutions.

3.Store all solutions.

- -1of 1 vote
Design a site similar to junglee.com. Assume you are given a crawler, design a distributed system , what ds will you use , some basic api’s etc.

- 0of 0 votes
Write a code to find if a link list is palindrome . Linklist consists variable string at each node. for eg

a->bcd->ef->g->f->ed->c->ba

The above given linklist is palindrome and func shd return - True

- 2of 2 votes
Design and Implement a Telephone database structure in which a Customer Entry has PhoneNum,Name,Address.

a) Given any PhoneNum return all the Customer details

b) Given any Name list all the Entries (As Name can be duplicate, only PhoneNum is unique)

c) Also Name searching should support Prefix Based.

- 2of 2 votes
Constructing Bridges:

A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.

Construct as many Non-Crossing Bridges as possible.

Input:

Above Bank >> 7 4 3 6 2 1 5

Below Bank >> 5 3 2 4 6 1 7

are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Output:

(1,1) (3,2) (4,3) (6,4) (7,5)

- 3of 3 votes
given a pre and post order kindof a traversal (2 arrays) create an n-ary treee out of it with struct of the form :

struct node {

int data;

struct node *child[MAX];

int child_num;

}

- 0of 0 votes
Implement the divide of two integers without using the divide operator.

After implementing the O(n) algorithm to subtract the divisor from the divider, he asked me to implement a better algorithm.

I started working towards bit manipulation, but ran out of time.

He also hinted that I could have used binary search. Not sure how though.

- 0of 0 votes
Given a stack of magazines create an anonymous love note (pick words or alphabets from the magazine and create the note)...

He gave me the choice of handling words or alphabets

Assume you have a scanned copy of the magazine as a string.

Once I implemented both words and alphabets, he asked me to scale it to mass production and maximize the throughput of a fulfillment center handling this

- 2of 2 votes
Design a robot that will take your order and make sandwiches for you.

Once I was done with this, I was supposed to extend it to have multiple robots doing this job like an assembly line handling multiple sandwiches and other edible items

Once I handled that, he asked me to create a web service for this that will handle online ordering. He also wanted me to implement fulfillment centers

- 1of 1 vote
Write code/ logic to count number of words in a string delimited by " ". Anything apart form " " are ignore for the counting. String could be very big as big as 5 GB of data. So add logic to handle such large strings..

ex: aaa b c ddd e = Count (5)

aaaaaaaaaaa = Count(1)

a

b

c

d

Count(1) as there are no spaces rather carriage returns are found.

PS: In case above question is not clear do let me know.

- 1of 3 votes
Given two input string check if anyone is substring of other.

example aaaaaabbb, aaaabbb

return true

PS: Don't use any internal string library :)

- 0of 0 votes
Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.

- 0of 0 votes
`6 / \ 3 5 / \ \ 2 5 4 / \ 7 4`

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer: 632+6357+6354+654=13997

- 0of 0 votes
6

/ \

3 5

/ \ \

2 5 4

/ \

7 4

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer = 632 + 6357 + 6354 + 654 = 13997

- 0of 0 votes
Write a program to make the following possible with any given tree.

6

/ \

3 5

/ \ \

2 5 4

/ \

7 4

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer = 632 + 6357 + 6354 + 654 = 13997

- 0of 0 votes
Suggest a Data Structure to do the following opperations with time complexity O(1).

insert(int element); //insertes an element in O(1);

delete(int element); //deletes an element in O(1);

lookup(); // returns any element in random from the list at O(1);

- 0of 0 votes
O/p the expected value of the number of people to deliver the information

I/P dependency graph

1234

1-0111

2-1000

3-1001

4-1010

o/p

2.66

- 0of 0 votes
How would test this method ?

public static bool DateBetweenDates(DateTime startDate, DateTime endDate, DateTime dateToTest)

{

if (startDate.Year > dateToTest.Year)

return false;

if (endDate.Year < dateToTest.Year)

return false;

if (startDate.Month > dateToTest.Month)

return false;

if (endDate.Month < dateToTest.Month)

return false;

if (startDate.Day > dateToTest.Day)

return false;

if (endDate.Day < dateToTest.Day)

return false;

else

return true;

}

- 0of 0 votes
Given graph below, and the Y-axis co-ordinates in and array, find the lowest point of every dip in the graph.

(I know graph looks horrible but i tried my best)`70 / 60 /\/ 50 / 40 /\ / 30 / \ / 20 /\/ \/ 10 /`

Array is : 0 10 20 10 30 40 50 40 30 20 10 20 30 40 50 60 50 60 70

Result List : 0 10 10 50

- 0of 2 votes
Given a +ve integer, find the next highest number in the numerical order using the same numbers present in the given integer.

Example : 218765

O/P : 251678