poorna.chandra.akp
BAN USER- 0of 0 votes
AnswersA special number is defined as a number where, in binary notation,
- poorna.chandra.akp in India
a. has only set bits (OR)
b. all set bits are followed by unset bits (OR)
c. the sequence formed by count of the number of set bits separated by any number of unset bits is a contiguous subsequence of the sequence of natural numbers.
2, 3, 11271 and 15667135 are special numbers because their binary represenation is 10, 11, 10110000000111 and 111011110000111110111111 respectively.
2 is a special number because of condition (b).
3 is a special number because of condition (a).
11271 is a special number because its binary representation is 10110000000111 because of condition (c). The sequence of the count of number of set bits separated by a unset bits is 1, 2 and 3. This is clearly a continguous subsequence of the natural numbers.
Similarly, 15667135 is a special number. (The sequence is 3,4, 5 and 6.)
So, given two integers n and m where n <= m, find out the number of special numbers between n and m inclusive.
Input Format:
The first line of input contains an integer T where T is the number of test cases. Then T lines follow containing two space separated integers n and m where n <= m.
Output Format:
For each test case, output, in different lines, a single integer P where P is the number of special numbers between the range specified.
Constraints:
1 <= T <= 1000
1 <= n <= 10^6
1 <= m <= 10^6
n <= m
Sample Input:
4
2 10
11 15
20 30
2 100
Sample Output:
6
4
5
43| Report Duplicate | Flag | PURGE
InMobi Senior Software Development Engineer - 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 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 - 1of 1 vote
AnswersHuman gene consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.
- poorna.chandra.akp 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
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 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 - 1of 1 vote
AnswersAn extension of Dijkstra's algorithm:
- poorna.chandra.akp in United States
In a graph each vertex represents a city.
And each edge defines the connectivity between two vertices.
Each edge has two more information
1) the distance between the two vertices
2) A Boolean flag indicating if the destination is uphill or downhill to the source.
One constraint: you can change the path from uphill to downhill or downhill to uphill only once.
E.g: initially if you are going up the hill and at some point choosed to go down the hill, you can not change to take a path which is uphill again..
Similarly you are going down the hill and at some point choosed to go up the hill, you can not change to take a path which is down hill again..
O/P: find the shortest path between source to destination.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 2of 2 votes
AnswersInterview gave towers of Honai with 4 pegs namely: source, helper1, helper2, destination.
- poorna.chandra.akp in India
What are the minimum number of steps to move N number of discs from source to destination.
he was looking for a recursive function which defines the number of moves required for N and the minimum value for that function.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 2of 2 votes
AnswersI/P: An array of Integers: which will be used to construct a binary search tree in the order they appear.
- poorna.chandra.akp in India
o/p: all permutations of the input elements which will result in the same Binary Search tree as the one formed with the input array.
Eg:
I/P: 4, 3, 1, 2, 6, 5, 7
o/p:4 , 6, 3, 7, 5, 1, 2
4, 3, 2, 1, 6, 5, 7
and soo on.| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer - 0of 0 votes
AnswersDevelop a program to demonstrate your implementation of a CSV parsing framework which can be used to generically parse given CSV file into Java beans and prints out information about parsed objects using toString(). The program should follow OOAD open-closed principle to avoid/minimize modification of code when new types are added in future.
- poorna.chandra.akp in United States
You should accept input from STDIN and print the output to STDOUT.
Assume following input format and study sample inputs given below:
Data-type
Header-Row
Data-Row-1
Data-Row-2
....
Data-Row-N
The first line indicates the entity type, 2nd line is comma separate list of column names, 3rd line onwards is the comma separated data values.
Test Case 1 Input
Type:Employee
name,age,salary
Ashok,36,20000
Kishor,30,15000
Bharath,25,30000
Expected Output
Name : Ashok;Age : 36
Name : Kishor;Age : 30
Name : Bharath;Age : 25
Test Case 2 Input
Type:Department
code,name
acc,accounts
prl,payroll
Expected Output
Code : acc;Name : accounts
Code : prl;Name : payroll
Your solution should parse the input into Java Beans (POJOs). For example, in test case 1, you will be make use of following Java bean (if you chose Java as programming language, and equivalent if you were using other language).
class Employee {
private String name;
private int age;
private int salary;
public Employee() {
}
public void setName(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public void setAge(int age) {
this.age = age;
}
public int getAge() {
return this.age;
}
public void setSalary(int salary) {
this.salary = salary;
}
public int getSalary() {
return this.salary;
}
public String toString() {
return "Name : " + this.name + ";" + "Age : " + this.age;
}
}
You can create a similar bean for Department as required for test case 2.| Report Duplicate | Flag | PURGE
Epic Systems SDE-2 - 1of 1 vote
AnswersGiven:
- poorna.chandra.akp in India for APi Team
R number of Red Cards
B number of Black cards
K
Cards needs to be placed in a circle. Start from a position and for every K moves remove that card And repeat the process until all the cards are eliminated.
Question: Position the cards such that the red cards are completely eliminated before the blacks cards are selected for elimination.| Report Duplicate | Flag | PURGE
Groupon SDE1 - 2of 2 votes
AnswersThis question was a modification of question 1 in this telephonic interview
- poorna.chandra.akp in India for digital
i/p: Binary Tree
O/p: print all the pairs along a path to leaf nodes, which don't follow BST property.
Eg:-
7
2 19
8 5 12 17
13 21
46
http://pastebin.com/raw.php?i=BqrNz9pu
o/p: (8,2), (8,7)
(13, 5) ( 13, 7)
and soo on.| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer - 1of 1 vote
AnswersI/P: chronological order of stock value of a particular company
- poorna.chandra.akp in India for digital
O/P: Maximum profit when you buy on a day and sell on another day.
Eg:
i/p: 79 14 3 21 104 54 12 9 94 1 96 101 5
o/p: 101| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer - 0of 0 votes
AnswersI/P: Binary Tree
- poorna.chandra.akp in India for digital
O/P: Print the all pairs which do not follow BST property.
Eg:-
I/p:
7
2 19
8 5 12 17
13 21
46
Looks like formatting is screwed for the binary tree.
http://pastebin.com/raw.php?i=BqrNz9pu
o/p: (8,2) (8,5) (8,7) (13,5) (13,7) (13,12) (19,17) (21,17) (46,17) (46,21)
I told the interview that I would store the inorder traversal of the input binary tree to an array and print out the inversions.
By inversion, I mean if i<j and then if a[i] > a[j]| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer - 1of 1 vote
AnswersA(1) = ()
- poorna.chandra.akp in India
A(2) = (())
A(3) = (()) ()
A(4) = (())() (())
A(5) = (())()(()) (())()
A(N) = A(N-1) + A(N-2)
I/P: N, i
O/P: A(N).charAt(i);
Interviewer was not looking at iterative or recursive solution. He was looking at a closed form solution.| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer - 1of 1 vote
AnswersGiven an input string.
- poorna.chandra.akp in India for digital platform
* It has numbers from M to N in increasing order. But no prior information about the values of M and N.
* There is one missing number.
Output the missing number.
Eg.
I/p: 960961962964
O/p: 963
I/p: 12345789
o/p: 6| Report Duplicate | Flag | PURGE
Flipkart SDE-2
does it takes care of additional constraint too (regarding the uphill and downhill)?
- poorna.chandra.akp April 29, 2014could you please prove why choosing only 2 discs would minimize T(n) ?
- poorna.chandra.akp April 29, 2014
RepMiraDavis, Computer Scientist at Accenture
I am School librarian and also teach students the fundamentals of using a library and its resources .I write and ...
Repsherrifjenkins, Applications Developer at ASAPInfosystemsPvtLtd
I am Sherri from Richmond USA. I am working as a Clinical laboratory technician worker in P. Samuels Men's ...
Repcrystalblibby, Analyst at Achieve Internet
By professional i am teacher. Successfully supervised and assisted students, grade artwork, encouraged creativity and new technique.Familiar with art ...
Let G = (V;E) be the graph that we construct given the road segments and their intersections.
- poorna.chandra.akp November 26, 2014We have costs on the edges that represent the length of the corresponding road segment. We
also have a value on every node that represents the elevation of that node. Let s be the node
representing the house, call it source, and let t be the node representing the university, call it
sink.
The idea is that we perform two separate shortest path computations. One from the source to
the rest of the nodes following only uphill edges, i.e, edges whose dierence of elevations of the
target node minus the source node is positive. One more, from the sink to the rest of the nodes
following uphill edges. On every node we store these two shortest path distances and we choose
the path that corresponds to the node that has the minimum sum of this values.
The next 4 steps describe more precisely the above procedure. Let for each node, the shortest
path distance from the source using only uphill edges be denoted as sp from s(v). Moreover,
let sp to t(v) denote the shortest path distance from node v to the sink t, for every v 2 V .
1. For all nodes v 2 V set sp from s(v) = 1 and sp to t(v) = 1.
2. Let G1 = (V;E1) be the graph induced by G if we remove all downhill edges. Run
SSSP algorithm on G1 using as source the node s. For every node in V set sp from s(v)
accordingly.
3. Let G2 = (V;E2) be the graph induced by G if we remove all uphill edges. Run SSSP
algorithm on G2 using as source the node t. For every node in V set sp to t(v) accordingly.
4. Find minv2V fsp from s(v) + sp to t(v)g. Choose the corresponding uphill and downhill
paths in order to get the desired s-t path.