## SDE-2 Interview Questions

- 0of 0 votes
You are given two integer arrays A and B .

1<=i<=len(A) so i is iterator of array A

1<=j<=len(B) so j is iterator of array B

find all the pairs(i,j) such that : i < j and A[i]>B[j]

- 1of 1 vote
They conducted a hiring round and this was asked there ?

Hi friends This question was asked in recent hiring challenge at hackerearth , that is over now,Please discuss your strategies.I am not able to devise algorithm please provide some hints to solve it.

Pulkit is really good at maths. Recently, he came to know about a problem on matrices. Amazed by the problem he got, he asked Ashish the same problem. Ashish also being good at maths solved the problem within 5 minutes. Now, its your time to solve the problem.

You will be given n*m binary matrix. You need to tell if it is possible to delete a column such that after deleting that column, rows of the matrix will be unique. If yes than print "Yes" else print "No".

[Input]

First line contains an integer t denoting no.of test cases.

Next line contains 2 integers n and m denoting no.of rows and columns.

Next n line contains binary string of length m each.

[Output]

For each test case output "Yes" or "No".

[Constraints]

1<=t<=100

1<=n<=1000

2<=m<=1000

Sample Input (Plaintext Link)

2

3 3

101

000

100

2 2

11

11

Sample Output (Plaintext Link)

Yes

No

- 2of 2 votes
Design a Meeting Reminder Pop-up similar to one found on outlook.

Data Structure to be used and come up with classes.

- 0of 0 votes
How to find non- common elements between two string arrays. Eg: String a[]={"a","b","c","d"};

String b[]={"b","c"};

O/p should be a,d

- 0of 0 votes
Question was very similar to this one

http://www.hackerearth.com/thoughtworks-hiring-challenge/algorithm/swap-it-2/

Bob loves sorting very much. He is always thinking of new ways to sort an array.His friend Ram gives him a challenging task.He gives Bob an array and an integer K .The challenge is to produce the lexicographical minimal array after at most K-swaps.Only consecutive pairs of elements can be swapped.Help Bob in returning the lexicographical minimal array possible after at most K-swaps.

Input: The first line contains an integer T i.e. the number of Test cases. T test cases follow. Each test case has 2 lines. The first line contains N(number of elements in array) and K(number of swaps).The second line contains n integers of the array.

Output: Print the lexicographical minimal array.

Constraints:

1<=T<=10

1<=N,K<=1000

1<=A[i]<=1000000

Sample Input (Plaintext Link)

2

3 2

5 3 1

5 3

8 9 11 2 1

Sample Output (Plaintext Link)

1 5 3

2 8 9 11 1

Explanation

After swap 1:

5 1 3

After swap 2:

1 5 3

{1,5,3} is lexicographically minimal than {5,1,3}

Example 2:

Swap 1: 8 9 2 11 1

Swap 2: 8 2 9 11 1

Swap 3: 2 8 9 11 1

- 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