## SDE-2 Interview Questions

- 0of 0 votes
A file of encoded message contains only numbers. Original message contains only lowercase letters and spaces. So character ‘a’ is mapped to 1 ‘b’ to 2 and so on till ‘z’ is mapped to 26. Given an input of numbers find out the number of ways you can decode it in original message. Eg. 123 can be decoded in 3 ways as 'abc', 'lc' or 'aw'

- 1of 1 vote
How will you design, and what data structure will you use for a contact list in a cell Phone. It should support insert/modify/delete/search functionality like that provided in a cell phone.

Suppose some of the entries are

Aman

Amazon

Neha Aman

and we type 'ama'

then the result should show all the above three enteries.

Also it should be possible to search using phone numbers.

- -1of 1 vote
an array is given.for each number at index i,find a number at index j such that aj 3.N number of books is given.each books is having some pages pi.How books should be alloted to m students so that maximum number of pages alloted to a student is minimum.Each student will read atleast one book.and one book can be read by only one person.find minimum value.

- 0of 0 votes
Store a Tree of URI and give a java implementation for it to return handler for the URI , eg : url mapping like in spring-config.xml

- 2of 2 votes
There is a binary tree. We are given 3 nodes a, b and c. We need to find a node in the tree such that we remove all edge from that node we get a, b and c in three different trees

- 0of 0 votes
Hi, I was asked a this one at the interview. Below is the problem statement:

1) I have a array of n bitstring elements of width m bits, for example:

{1001, 0101, 1100, 0011, 1111, 0000, 0001}

2) We have to apply a filter such that out of these n elements, only k elements pass through the filter while the rest gets blocked, for example

{1001, 0101, 1100, 0011, 1111, 0000, 0001} -- filter -- > {1001, 1100, 1111}

3) Filter has been designed based on a concept of mask and ID.

mask: It tells which bits to consider out of the m bit bitstring elements. Only those bits which are set to '1' would be used for checking while the rest be ignored. for example, a mask of {1000} would mean only 4th bit would be considered for checking while the filter won't care about the other bits of an element.

ID: It is the allowed value for the designed mask. for example, an ID of 1xxx (where x is don't care) with a mask of 1000 means that any element which has 4th bit as '1' would be allowed while if the 4th bit is '0', that element would be blocked. Since the mask doesn't check the 1st, 2nd and 3rd bit, any value, '1' or '0' would be allowed to be passed through the filter

For the above example, a single mask of 1000 and ID of 1xxx solves the problem. We need to find a generic solution for any set of n elements and k allowed elements. All of the k element might not get covered by a single mask and ID. We need to find the optimum solution using minimum number of mask,ID sets with their values.

- 2of 2 votes
Given a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements

are filled. Here X means you cannot traverse to that particular points. From a cell you can either traverse to left, right, up or down

Given two points in the matrix find the shortest path

between these points

For example if the matrix is

1 1 1 1 1

S 1 X 1 1

1 1 1 1 1

X 1 1 E 1

1 1 1 1 X

Here S is the starting point and E is the Ending point

- 0of 0 votes
Given an array of heights of poles. Find the no of poles which are visible if you are standing at the ith pole

- 2of 2 votes
Traverse a given 2D matrix from given source to destination in such way that every cell should be visited exactly one time (we have to cover all cells of matrix exactly once and have to reach at destination).

- 1of 1 vote
Given N sets of integers, remove some sets so that the remaining all sets are disjoint with one another. Find the optimal solution so that the number of sets remaining at the end is maximum

- 0of 0 votes
Difference between struct and class.

When would you use one over the other

What is padding? Do both struct and class have padding

- 0of 0 votes
Explain the underlying working of how inherited function gets invoked. So if Dog and Cat, inherited from Animal, inherit Eats. How does the right Eats get called for Dog/Cat

private inheritance vs composition

When would you use private inheritance

- 0of 0 votes
What is a static function? Explain in detail

- 0of 0 votes
Implement an atoi function in C++

- 0of 0 votes
Difference between threads and process.

When would you use one vs the other

Where on the stack are values stored for their local variables?

If there are two threads each with two local variables, where will these variables be stored

- 0of 0 votes
You have a rabbit who wants to cross a river by jumping over the various rocks in it. All the rocks are in a straight line and the distance between them is also given. Your rabbit can only perform jumps of specific lengths. You have to output the minimum number of jumps required to cross the river (if possible). Rabbits can jump both in forward and backward direction.

The number of rocks is M and the number of possible jump lengths is N.

For e.g. M=4 , N=2,

distance between m1-m2= 1

m2-m3= 2

m3-m4 =1

rabbit can perfrom jump of length 3 and 1.

output= 2 (minimum jump to cross the river)

- 0of 0 votes
Given a List of Students that are already sorted based on names, write a function to return list of students that is sorted based on grade (four possible grades are a,b,c and d). If two students has same grade, they should be sorted internally based on name.

I have written a code based on bucket sort. Something like this. Not sure whether this is optimal.`public List<Student> sortByGrade(List<Student> students) { List<Student> aGradeStudents = new LinkedList<Student>(); List<Student> bGradeStudents = new LinkedList<Student>(); List<Student> cGradeStudents = new LinkedList<Student>(); List<Student> dGradeStudents = new LinkedList<Student>(); for(Student st : students) { switch(st.getGrade()) { case 'a' : aGradeStudents.add(st); break; case 'b' : bGradeStudents.add(st); break; case 'c' : cGradeStudents.add(st); break; case 'd' : dGradeStudents.add(st); break; }; } List<Student> sortedStudents = new LinkedList<Student>(); sortedStudents.addAll(aGradeSudents); sortedStudents.addAll(bGradeSudents); sortedStudents.addAll(cGradeSudents); sortedStudents.addAll(dGradeSudents); }`

- 1of 1 vote
Given an array of sorted numbers, find the index of first occurrence of the given number.

- 2of 2 votes
Write a function, for a given number, print out all possible way to make up that number eg: 2 - 1 1,2

- 0of 0 votes
A furniture can be made of material like metal, wood, .... Also there are different furniture types chair, table, sofa. A wood furniture should be tested against choaking. metal furniture is tested against fire, etc. Design these in OOAD.

- 0of 0 votes
There are N nodes. Each node has a non negative integer value. Define a optimistic algorithm which ensures that all node has all other node's value.

Constraint: While a node is sending data to another data, it can't receive data, vice versa.

- 0of 2 votes
Machine Coding:

Design and code application similar to IPL website.

1. There are players who belong different teams [CSK, RCB,etc].

2. User can create their own team from the player set

3. When a match happens, there are possible outcome in each ball [one run, six, wicket, run-out, etc]

4. on each outcome, players involved will get points [eg: six = batsman 5 points, wicket = batsman minus 5 and bowler +5, etc]

5. Based on outcome, the user created team also should be able to calculate his points.

6. Solution should be working code, extensible and performance.

- 0of 0 votes
Find the K most frequent strings from a large data that can't fit into the memory in one go. Lets say there is a data of 200GB but available RAM memory is 1GB only.

- 0of 0 votes
You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2x2 chocolate bar can be divided into two 2x1 pieces, but it cannot be divided into two pieces, where one of them is 1x1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces.

Your goal is to create at least one piece which consists of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.

Complete the function getMinSplit, which takes in 3 integers as parameters. The first parameter is width of the chocolate, the second is height of the chocolate and third is nTiles, the number of tiles required.

Constraints

- width will be between 1 and 109, inclusive.

- hight will be between 1 and 109, inclusive.

- nTiles will be between 1 and 109, inclusive.

Example 0

5

4

12

Returns: 1

You can split the chocolate bar into two rectangular pieces 3 x 4 and 2 x 4 by creating a single vertical break. Only one break is necessary.

Example 1

12

10

120

Returns: 0

The chocolate bar consists of exactly 120 tiles.

Example 2

2

2

1

Returns: 2

Example 3

17

19

111

Returns: -1

Example 4

226800000

10000000

938071715

Returns: 2

- 1of 1 vote
Human gene consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.

Your job is to make a program that compares two genes and determines their similarity as explained below.

Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of the genes to make them equally long and score the resulting genes according to a scoring matrix.

For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in -GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal length. These two strings are aligned:

AGTGAT-G

-GT--TAG

In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.

* denotes that a space-space match is not allowed.

The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.

Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):

AGTGATG

-GTTA-G

This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14.

You are expected to complete the function getDNAAlignment, which takes in two strings as argument.

Constraints

Length of both strings will not exceed 1000.

Both string will be non-empty strings.

strings will only consists of character from set {'A', 'C', 'G', 'T'}

Sample Input 00

AGTGATG

GTTAG

Returns: 14

Sample Input 01

AGCTATT

AGCTTTAAA

Returns: 21

- 0of 0 votes
You are a coin collector in a country, where the silver coin denominations runs from 1 to 1000000. You have N coins with you with various denominations.

Apart from the silver coins, the country also issues gold coins which can be used as any value. With the given silver and gold coins, find out the maximum continous denomination streak you can achieve.

For example, if you have 4 silver coins of value 2, 3, 5 and 9 and 1 gold coin. You can have a maximum streak of 4 coins by using the gold coin as value 4.

Input format.

The first line contains 2 integers, S and G. S is the number of silver coins you have and G is the number of gold coins you have. S lines follow, each line is the value of the corresponding silver coin

Output format:

One integer, representing the maximum streak you can have using the coint.

Sample Input 1

4 1

2

3

5

7

Sample Output 1

4

- 0of 0 votes
You have a set of pairs of characters that gives a partial ordering between the characters. Each pair (a, b) means that a should be before b. Write a program that displays a sequence of characters that keeps the partial ordering (topological sorting).

- 0of 0 votes
Implement multiple producer and multiple consumer problem in java.

- 1of 1 vote
For a given binary search tree, replace each node with sum of all node which are greater then of equal to current node.

- 0of 0 votes
Id Key Value

-- --- -----

1 name hulk

2 age 22

3 name ironman

4 age 35

Write an efficient SQL Query to fetch the id of all users whose name starts with h and having age between 22 and 35.