CareerCup

Identifying if all the elements of a set (in enterity) is present in a list of sets.

For example checking for set1 = {1,2} in {1,2,3}, {5,6} should return true as {1,2} is present in {1,2,3}. Similiary it will be true for {1,2,8,9}, {1,2,4}

But checking for {1,2} in {1,5,6}, {2,3,1} should return false as {1,5,6} does not contain all elements of {1,2} 2 is missing

Given a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

The rectangle at lower level has more priority than at higher levels.

i) Explain Polymorphism

ii) Output of the below code snippet :-

public class ParentTest {

	public int x = 0;

    public void print() {
        System.out.println("In Parent");
    }

}

public class ChildTest extends ParentTest {
	public int x = 1;

	public void print() {
        System.out.println("In Child");
    }
	
	public static void main( String args[] )
	{
		ParentTest s = new ChildTest();
		System.out.println(s.x);
		s.print();   
	}
}

Write a program to count the number of numbers between two numbers a, b that have the sum of their bits equal to a fibonacci number.

For example between 15 and 17 there are two numbers that have sum of bits equal to a fibonacci number.

15: 1111 sum=4
16: 10000 sum=1 (fibonacci)
17:10001 sum=2 (fibonacci)

So the output will be 2 in this case.

Test case -
Input 15 & 17
Input 173 & 10000003210005

The interviewer asked this to code in 5 hours in any programming language & mail him the full working program.

Write a program to output the number of consecutive trailing zeros in the factorial of a number?

For example:-

Input - 5!
Output - 1 (Since 5! = 120 & 120 has 1 trailing zero in the end)

Implement multiple producer and multiple consumer problem in java.

Id Key Value
-- --- -----
1 name hulk
2 age 22
3 name ironman
4 age 35

Write an efficient SQL Query to fetch the id of all users whose name starts with h and having age between 22 and 35.

Given two tables
1. Candidate having: Id , Name
2. Vote: Id, CandidateId

Give query to give the name of the winning candidate

Coding Round Assignment
------------------------------------

MERCHANT'S GUIDE TO THE GALAXY

You decided to give up on earth after the latest financial collapse left 99.99% of the earth's population with 0.01% of the wealth. Luckily, with the scant sum of money that is left in your account, you are able to afford to rent a spaceship, leave earth, and fly all over the galaxy to sell common metals and dirt (which apparently is worth a lot).Buying and selling over the galaxy requires you to convert numbers and units, and you decided to write a program to help you.The numbers used for intergalactic transactions follows similar convention to the roman numerals and you have painstakingly collected the appropriate translation between them.Roman numerals are based on seven symbols:

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1,000
Numbers are formed by combining symbols together and adding the values. For example, MMVI is 1000 + 1000 + 5 + 1 = 2006. Generally, symbols are placed in order of value, starting with the largest values. When smaller values precede larger values, the smaller values are subtracted from the larger values, and the result is added to the total. For example MCMXLIV = 1000 + (1000 − 100) + (50 − 10) + (5 − 1) = 1944.
The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear four times if the third and fourth are separated by a smaller value, such as XXXIX.) "D", "L", and "V" can never be repeated.
"I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted.
Only one small-value symbol may be subtracted from any large-value symbol.
A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1, 9, 0, and 3. To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.
-- Source: Wikipedia (http://en.wikipedia.org/wiki/Roman_numerals)Input to your program consists of lines of text detailing your notes on the conversion between intergalactic units and roman numerals. You are expected to handle invalid queries appropriately.

Test input:
-------------
glob is I
prok is V
pish is X
tegj is L
glob glob Silver is 34 Credits
glob prok Gold is 57800 Credits
pish pish Iron is 3910 Credits
how much is pish tegj glob glob ?
how many Credits is glob prok Silver ?
how many Credits is glob prok Gold ?
how many Credits is glob prok Iron ?
how much wood could a woodchuck chuck if a woodchuck could chuck wood ?

Test Output:
---------------
pish tegj glob glob is 42
glob prok Silver is 68 Credits
glob prok Gold is 57800 Credits
glob prok Iron is 782 Credits
I have no idea what you are talking about

Design a mobile app which based on the current location suggests Interesting places to the user. We already have a set of interesting places stored. The focus is on getting the nearby places say in radius of 100 Miles from current location quickly.

The interviewer is mainly interested on how to store the interesting locations in a DB.

Machine Coding 1 hour
------------------------------
U have an organizational structure, which shows hierarchy of the organization. This hierarchy contains employees E or managers M who has some Employees or Managers reporting to M.
Employee has ( id, name, JobDesc, salary etc).
Design the data structure you would be using to store this hierarchy

problem 1: Given an ID of an employee , print all the employee ID's who are directly reporting or indirectly reporting to the manager.

problem 2: prefix search of employees by String. If employees have nishant and nikhil. If searched by "ni" we need to print all details of both nishant and nikhil.

problem 3(bonus): search should print all emloyee's and their details if a given string is subString of the name of an employee.(Like a phonebook contacts search)

P.S- This was asked to one of my friend in Flipkart.

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

You have to print the sub-sequence also.

Generate all Kaprekar Number (refer Wiki for Kaprekar number's definition) from 1 to 999999.

I gave a brute force approach of generating all number in the range and checking if it is Kaprekar or not.

What approach you will take in migrating your production databases from MySql to Postgre SQL with zero downtime.

i) Difference between HashMap & HashTable

ii) How will you implement your own sorting algorithm in java?

Coin Change Problem
-----------------------------

Given an unlimited supply of coins of denominations C1, C2, ..., CN we wish to make change for a value V. Give an algorithm for producing change with minimum number of coins.

You have to print the denominations selected.

1 2 3
4 5 6
7 8 9
* 0 #

Given a starting number, find all 6-digit numbers possible, numbers can only be dialed horizontally or vertically.
Repetitions not allowed. Number can't start from zero and doesn't include * and #. For example, if last dialed number
is 3, the next one could be 1, 2, 6 or 9.

Design a web-site like Paypal.

The interviewer was interested in the

i) Major components & the way they will interact.
ii) Various way of scaling the web-site to support many users
iii) Handling the failure cases like when the DB goes down, etc.

Given a binary matrix of 0 and 1. Find the longest sequence of 1's either row wise or column wise.

For example

0 0 0 0 0 0
0 1 1 1 0 0
0 0 0 1 0 0

It should return 1 1 1

You are given a matrix where some pixels are white and some are black. Basically there are different disjoint images in the matrix.

a) Expand/Shrink the images
b) Count the no of images
c) Color the images
d) Rotate the images

Given three points in a 2D plane with their (x, y) coordinates say if the origin lies inside the triangle formed by the three points.

Disconnect two nodes in a graph by removing minimum number of edges.

Given a matrix pattern containing only 'plus' & 'dots',search no of times that pattern is present in a very large file which has a very large matrix which contains 'plus' and 'dots'.

Given a random generator rand(5) which generates numbers between 0 to 4. How do u generate numbers between 0 to 6, I.e. Implement rand(7).

Car parking problem. An array given represents actual order of cars need to be parked. Like for example order is 4,6,5,1,7,3,2,empty. If cars are parked in some order like empty,1,2,3,7,6,4,2. Some person needs to get them into correct order, list out all instructions to the person to get in correct order with least number of swaps.

Machine coding round : (Time 1hr)

expression is given and a string testCase, need to evaluate the testCase is valid or not for Expression

Expression may contain letters [a-z]
Expression may contain "."( '.' represents any char in [a-z])
Expression may contain '*'( '*' has same property as in normal RegExp)
Expression may contain '^' ( '^' represents start of the String)
Expression may contain '$' ('$' represents end of String )

Sample cases (Exp, testCase, Result) below

1. ab, ab , true
2. a*b , aaaaaab , true
3. a*b*c*, abc , true
4. a*b*c , aaabccc, false
5. ^abc*b, abccccb , true
6 ^abc*b, abbccccb , false
7 ^abcd$, abcd , true
8 ^abc*abc$ , abcabc, true
9 ^abc.abc$, abczabc , true
9 ^ab..*abc$, abyxxxxabc, true

Coding in Computer : (Time 1hr)

Expression is given and a string testCase, need to evaluate the testCase is valid or not for Expression

Expression may contain letters [a-z]
Expression may contain "."( '.' represents any char in [a-z])
Expression may contain '*'( '*' has same property as in normal RegExp)
Expression may contain '^' ( '^' represents start of the String)
Expression may contain '$' ('$' represents end of String )

Sample cases (Exp, testCase, Result) below

1. ab, ab , true
2. a*b , aaaaaab , true
3. a*b*c*, abc , true
4. a*b*c , aabccc, false
5. ^abc*b, abccccb , true
6 ^abc*b, abbccccb , false
7 ^abcd$, abcd , true
8 ^abc*abc$ , abcabc, true
9 ^abc.abc$, abczabc , true
9 ^ab..*abc$, abyxxxxabc, true

You have given a file containing sentences. Now you are given a sequence of characters. You have to find the starting location of each word containing one of the permutation of the word.

e.g File - 'She submitted her assignment.' Input Sequence - imt. Since the file contains the word 'submitted' containing the sequence 'mit' which is a permutation of 'imt' So it will return 1. Similiarly it will return for all other words.

Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally)

e.g.

5 9 10 1
3 7 4 4
8 2 1 9

So shortes path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+7+1 = 13