InMobi Interview Report
- 1of 1 vote
AnswersHuman gene consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.
- poorna.chandra.akp May 19, 2014 in India
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| Report Duplicate | Flag | PURGE
InMobi SDE-2 - 0of 0 votes
AnswersYou 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.
- poorna.chandra.akp May 19, 2014 in India
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| Report Duplicate | Flag | PURGE
InMobi SDE-2 - 0of 0 votes
AnswerYou 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.
- poorna.chandra.akp May 19, 2014 in India
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| Report Duplicate | Flag | PURGE
InMobi SDE-2