CareerCup

N number of balloons are kept at different heights. You are asked to find out number of arrows to burst them. When an arrow hits the balloon it goes one level down.
Assume that the balloons are having same size.

for example given the balloons heights as array(Array will be given in decreasing order of size) :
5 4 3 3 2 2 1 1 1
minimum number of arrows to shoot them is: 3

explanation:
using first arrow shoot: 5 4 3 2 1
using second arrow shoot: 3 2 1
using third arrow shoot: 1

Example 2:
5 4 2 1

minimum number of arrows to shoot them is: 2
using first arrow shoot: 5 4
using second arrow shoot: 2 1

Expecting the solution to be in O(1) space complexity.

You have a database table that stores information about the price change of various product with time. It's append only table. Whenever the price of the product p1 is changed to c1 at time t1, a new row will be appended.
product_id price time
p1 10 4
p2 40 4
p1 20 5
p1 25 6
p2 55 7
...

Write an SQL query that will give the price of every product at time t1.
e.g. at time 6
product_id price
p1 25
p2 40

Note: Consider the case where two updates are made at the same time. Don't assume that the table is sorted by time.

given two strings s1 and s2 we have to convert s1 into palindrome such that s1 contain s2 as a substring. in a minimum number of operation. wherein a single operation we can replace any word of s1 with any character.
constraint : |s1| <= 1000
|s2| <= |s1|
ex: s1 = "abaa" , s2 = "bb"
output : 1

Given 3 unsorted arrays A, B and C you need to find all possible combinations such that A[i] + B[j] = B[k] + C[l].

How to design a system which allows millions of requests

Design an app which allows different types of jobs to be triggered at user specified delay

Given a dictionary containing some words, and a start word and end word, you need to find the minimum number of conversion needed to convert start word to end word with the following restrictions :-
1. Each intermediate word must be in the dictionary
2. You can change only one character in the word to convert to another word.

Example If You are given start word as ‘SAT’ and end word as ‘PAN
and the dictionary contains words = [‘RAT’,’PAT’,’DAM’]

then SAT -> PAT ->PAN is the answer.

How to find total number of greater number after all number in an array ?
Eg. Given array is,
5 3 9 8 2 6
o/p
3 3 0 0 1 0

Two friends Kohli and Dhoni want to test their friendship to check how compatible they are. Given a list of n movies numbered 1,2,3....n and asked both of them to rank the movies.
Design an algorithm to find compatibility difference between them.

Compatibility difference is the number of mis-matches in the relative rankings of the same movie given by them i.e. if Kohli ranks Movie 3 before Movie 2 and Dhoni ranks Movie 2 before Movie 3 then its a relative ranking mis-match Compatibility difference is the maximum number of mis-matches

Sample Input

5
31245
32415
Sample Output

2
Explanation

Movies are 1,2,3,4,5. Kohli ranks them 3,1,2,4,5, Dhoni ranks them 3,2,4,1,5. Compatibility difference is 2 because Kohli ranks movie 1 before 2,4 but Dhoni ranks it after.

Mario wants to reach to his princess who is waiting for him in a castle. But the way to the castle is full of dragons. Each dragon is an enemy of the dragon who is located just before him on that path. The dragons in this world are quite peculiar. They have some number of diamonds each. Although they are dragons, they won't burn, instead they will give Mario their diamonds, but if and only if, Mario didn't take any diamonds from the dragon standing directly before the current one. If Mario does, then that dragon will burn him. Mario is in your control. You have to make Mario collect maximum number of diamonds for his princess and reach castle safely.

Input- Each test case starts with a number N, the number of dragons, 0 <= N <= 10^4. The next line will have N numbers, number of diamonds each dragon has, 0 <= The number of diamonds with each dragon <= 10^9. Dragons described in the order they are encountered on the way to the castle.

Output- Print the maximum number of diamonds you can collect (and reach to castle safely).

Sample Input


5 1 2 3 4 5

Sample Output


9

Explanation

Input - 5 ==> Represents number of Dragons 1 2 3 4 5 ==> Represents the diamonds each of the Dragon has consecutively. The first dragon has 1 , the second has 2 and so on....

Output- 9

Explanation- If Mario collects diamonds from 1st, 3rd and 5th dragon (1+3+5). He will get 9 diamonds which is the maximum number of diamonds he can collect. Two of the other possible ways in which he can collect diamonds is, from 2nd and 4th dragon, (2+4),i.e.(6) or from 2nd and 5th dragon (2+5) i.e.,7 . He can’t obtain more than 9 diamonds in any case.

Therefore the output would be 9, the maximum he can collect.

Find the number of column-swaps required to find the largest rectangle of all ones in a matrix.
The question is similar to the one in this link-
http://www.geeksforgeeks.org/find-the-largest-rectangle-of-1s-with-swapping-of-columns-allowed/
But we need to find the number of minimum swaps required

Find the value of (x, y) in Pascal's triangle. I wrote code to construct the Pascal's triangle upto the required (x, y). Then interviewer asked me to change code so that I dont have to calculate the whole triangle but only the necessary parts.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

For example, in order to calculate f(4, 1) which is 4, we only need to calculate f(3, 0) and f(3, 1). And for f(3, 1) we need to calculate f(2, 0) and f(2, 1) and so on. After getting the hint, I wrote the recursive code and then he asked my for complexity of the code.

int pascals(int x, int y){
   if(x == 0 or x == y)
       return 1;
    return(pascals(x - 1, y) + pascals (x- 1, y - 1);
}

Implement pow(x, y) which should return x^y. Both iterative and recursive.

Print all permutations of a string and give the complexity of the algorithm.

Given a tree (incolmplete and/or unbalanced), how would you write it to disk so it can be moved to another machine and recreated?

There is a garden of strawberry plants represented by a 2D, square array.Each plant represents an element in the matrix ie it has a number of strawberries. If a plant doesnt have strawberries it is denoted by 0. If 0 is encountered you cannot travel through that path.



You can start from any cell along the left border of this ground (i.e the matrix) and travel until it finally stops at one cell in the right border, and you can only move to up/down/right. You can only visit each cell once. Calculate the maximum number of berries is obtained.

Backtracking using Dynamic programming is one of the methods i have thought of.

Also there some special conditions:

a.Even in the left border and right border, we can go up and down.

b. When we are at the top cell of one column, we can still go up, which demands us to

pay all current strawberries , then we will be teleported to the bottom cell of this column and vice

versa.

Input: user enters dimensions of ground ie size of matrix and the matrix itself

Output: is the maximum number of strawberries collected without encountering 0; in case we do we display 0.

Till now i have managed to find the largest value in the first column of the matrix but i am facing difficulty in testing the neighbours of that cell.

Also i am not able to store the position of the cell which i started from or even mark it.

Input

4 4

-1 4 5 1

2 -1 2 4

3 3 -1 3

4 2 1 2

output

23




Input

4 4

-1 4 5 1

2 -1 2 4

3 3 -1 -1

4 2 1 2

output

22

. Given n strings consisting of ‘R’ and ‘B’. Two strings can be only combined if last character of first string and first character of second string are same. Given n strings, you have to output the maximum length possible by combining strings.

I/P
RBR
BBR
RRR
output : 9

Implemented a bounded queue:
Read:
If queue is empty, wait till it can return a value with time out
If another thread is reading from the queue then wait till that thread is done
Remove the first element from the queue and return it
Do not block if a thread is writing into the queue

Write:
If queue is full, wait till one value is read with time out
If another thread is writing to the queue, wait till that thread is done
Write the element at the end of the queue
Do not block if a thread is reading from the queue

Given a start string, end string and a set of strings, find if there exists a path between the start string and end string via the set of strings.
A path exists if we can get from start string to end string by changing (no addition/removal) only one character at a time. The restriction is that the new string generated after changing one character has to be in the set.
start: "cog"
end: "bad"
set: ["bag", "cag", "cat", "fag", "con", "rat", "sat", "fog"]
one of the paths: "cog" -> "fog" -> "fag" -> "bag" -> "bad"

Given an array of integers (+ve & -ve) find two equal sized contiguous non-overlapping sub-arrays with maximum dot-product

Write an OO class system for individual-contributors, managers, directors.

Minimize the cost to chop the log into pieces of desired lengths. The cost to cut any piece is the max of the two lengths generated out of cutting the wood. e.g. If a 14 unit log is cut into 2 pieces of lengths 6 and 8, cost is 8.
Write a function that takes the total length of the log and an array of piece lengths and returns the cheapest sequence to do this along with the cost

Given an existing inventory Oracle Database system and UI. The UI should update itself as soon as the db gets updated
There is a tool that people use to dump inventory data (one row at a time or bulk insert via data in files)
Currently a new system is built with new UI using No Sql database.
Write a bridge that will update the new UI and populate the No SQL database, so that the new UI has real time updates as the tool has updated.

public class StringUtilities {
    /**
     * Count the maximum depth of parenthesis nesting, i.e. "abc(123(xyz))m(((n)))o" -> 3.
     *
     * @param input
     *            any string
     * @return deepest parenthesization level
     * @throws IllegalArgumentException
     *             if input is null or contains a mismatch "a)b(c" or "a(b"
     */
    public static int nestedParenthesisDepth(String input)
            throws IllegalArgumentException {
        //...
    }
}

public class MyClass {

public static int num=1;
public static boolean flag=false;

public static void main(String[] args) {
Thread t =new Thread(new MyThread());
t.start();
MyClass.flag=true;
MyClass.num=10;
}

}


class MyThread implements Runnable{

public void run() {

while(!MyClass.flag){
Thread.yield();
}

System.out.println(MyClass.num);


}
}

Output of this code and the reason for the output?

Input any string, count the maximum depth of parenthesis nesting, i.e. "abc(123(xyz))m(((n)))o" -> 3.

if input is null or contains a mismatch "a)b(c" or "a(b"

Also some other samples:
(((()))) -> 4
()()()() -> 1

You have a class that many libraries depend on. You need to modify the class for one application. Which of the following changes require recompiling all libraries before it is safe to build the application?

a. add a constructor
b. add a data member
c. change destructor into virtual
d. add an argument with default value to an existing member function

Do thread join without join function?

Given a BST, how would you return the kth smallest element. Cover all the corner cases with time complexity logn

Write a program that reverses alternate elements in a given linked list input: a->b->c->d, output should be b->a->d->c