Recent Interview Questions
More Questions » 0of 0 votes
Optimization Game
Currently, Monk is playing a unique kind of strategy game called optimisation game.
In this game we are provided with an array containing integral numbers.
Now all these numbers represent the count of their respective index power of 2.
The goal of the game is to minimize the total sum of the count of the array by converting lower powers of 2 into their higher powers
i.e. for example (2)*2^1 = (1)*2^2.
Note that we can extend the array beyond the final index i.e. N−1 too in case it optimizes our result.
Please see the below example for more understanding.
Let the number of elements given in the initial array be 3. Consider the array to be [1,2,0].
It means that 2^0 has count = 1, 2^1 has count = 2, 2^2 has count = 0.
Now, we can convert (2)*2^1 into (1)*2^2 as 2^1∗2 = 2^2. We get the new array as [1,0,1].
Now the total sum is 1+0+1=2 which is the required minimum value obtained at the end of the game as we can't reduce it any further.
Input:
First line will contain the number of test cases as T.
For each of the test case, N will be given in the first line and N integers will be given in the second line.
Output:
Output the minimum value obtained after playing the optimization game in a separate line for each test case.
Constraint:
1≤T≤5
1≤N≤10^5
0≤A[i]≤2∗10^9
Sample Input
2
3
1 2 1
2
2 1
Sample Output
2
1
Explanation
In the second case we have A[0]=2, A[1]=1. We can convert A[0] into A[1] and then finally (1+1=2) A[1] into A[2]. Thus, the final array shall be : [0,0,1]. Hence, the answer is 1.
 0of 0 votes
On google search, how to enable key word auto completion after a few letters typed.
Followup: How to rank the words if they are weighted by frequency?
 1of 1 vote
Cross the street
ABC Company is involved in the logistics business.
The company has many outlets and stockyards in a city. The city is like an
N
×
M
N×M grid. We consider a single cell of the given grid to be a single block in the city. The stockyard is at the upperleft corner and the outlet is located in the lower right corner. Everyday, one of the employees has to travel from the upper left to the lower right corner for supplies. Each block in the city has a height, where the height of the block located at position (i,j) in the grid is equal to
A
[
i
]
[
j
]
A[i][j]. The company wants to change the heights of some of the blocks, so that the employee can enjoy a highspeed drive from the stockyard to the outlet. But this change comes at a certain cost.
Specifically, if they change a block height from x to y, then they must pay exactly

x
−
y

x−y dollars. Please help them find the minimum cost, such that by spending that specific amount, they can get a path from stockyard to the outlet with all blocks along the path having the same height.
In a single move, the employee can move from a block to any of its adjacent blocks. Note that during this journey, the employee is allowed to move in all four directions, fulfilling the condition that he never goes out of the grid at any point in time.
Input :
First line contains two positive integers N and M  number of rows and columns in the city. Then, N lines follow, each containing M integers, where the
j
t
h
jth integer on the
i
t
h
ith line denotes
A
[
i
]
[
j
]
A[i][j].
Output :
The first and only line of output should contain minimum cost.
Constraints :
1<= N, M <=100
1<= height of blocks <=100
Sample Input
5 5
1 1 1 1 1
9 9 9 9 1
1 3 3 3 1
1 9 9 9 9
1 1 1 1 1
Sample Output
6
Explanation
Optimal path taken by the employee will be : (1,1) > (1,2) > (1,3) > (1,4) > (1,5) > (2,5) > (3,5) > (3,4) > (3,3) > (3,2) > (3,1) > (4,1) > (5,1) > (5,2) > (5,3) > (5,4) > (5,5) The height of each block along this path can be changed to
1
1, at a total cost of
6
6. There is no way to get a cost less than this.
 0of 0 votes
Alex has recently decided to learn about how to design compilers. As a first step he needs to find the number of different variables that are present in the given code.
So Alex will be provided N statements each of which will be terminated by a semicolon(;). Now Alex needs to find the number of different variable names that are being present in the given statement. Any string which is present before the assignment operator denotes to a variable name.
Input Format: :
The first line contains a single integer N
Each of the next N lines contains a single statement.
It is guaranteed that all the given statements shall be provided in a valid manner according to the format specified.
Output Format: :
Print the number of different variable name that are present in the given statements.
Sample Input
2
foo = 3;
bar = 4;
Sample Output
2
Explanation
Foo and Bar are only two variables used inside the statements so answer is 2.
 0of 0 votes
Design classes to represent the following problem and solve the questions 1,2,3
A user might have some outstanding auto loan amount and you have 3 types of offers: personal loan, credit card and auto loan offers. You need to provide the user
with the following details:
1. Send user all the offers to the user
2. Send user all eligible offers (where minCreditScore < userCreditScore < maxCreditScore)
3. Send user all offers which satisfied 2) and where the (userOutStandingLoanAmount < maxOfferedAutoLoanAmount)
personalloan = [{
"personalloan": {
"id": 1,
"provider": "Avant",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"personalloan": {
"id": 2,
"provider": "Prosper",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]
creditcard=[{
"creditcard": {
"id": 2,
"provider": "CapitalOne",
"minimumCreditScore": 600,
"maximumCreditScore": 700
}
}, {
"creditcard": {
"id": 3,
"provider": "Chase",
"minimumCreditScore": 300,
"maximumCreditScore": 900
}
}]
autoloan = [{
"autoloan": {
"id": 1,
"provider": "CapitalOne",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"autoloan": {
"id": 2,
"provider": "Blue Harbor",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]