CareerCup

Design and code the sudoku solver.

There is a zoo and there are several groups(number of groups:K) of people for tour. Each group is having different size (g1,g2,g3…gK). There is one bus with capacity C. Journey starts from a point and bus will come back to the same point. A group can only be included in the bus if all the members of the groups can be accumulated in bus. After coming back from the tour, each group in the bus will again wait in the queue at the bus-stand. Bus-driver earns a rupee for each person travelled. You have to find the earning of the bus driver after R rounds.

For example :

Number of groups G = 4

Group size for each group : 2 4 3 5

Bus capacity : 7

Number of rounds R : 4



queue : (from front side) 2 4 3 5

First round : 2 4 (we can’t take 3rd group as 3 members can’t be accumulated after 2 and 4.)

queue : 3 5 2 4 (1st and 2nd group are enqueued. i.e. 2 and 4)

Second round : 3

queue : 5 2 4 3

Third Round : 5 2

queue : 4 3 5 2

Fourth Round : 4 3

After 4 rounds, total earning is 6+3+7+7 = 23.

Design a Traffic signal . List all entities and classes involved. How will you handle pedestrian crossings etc.

esign a contact list for a cell phone which can add & search really quick and is scalable.

Design a mobile cab booking application (just screens and functionalities) on board.

A sender will send a binary string to a receiver meanwhile he encrypt the digits. You are given a encrypted form of string. Now, the receiver needs to decode the string, and while decoding there were 2 approaches.

First, receiver will start with first character as 0; S[0] = 0, P[1] = S[1] + S[0], P[2] = S[2] + S[1] + S[0] and so on.
Second, Receiver will start with first character as 1; S[0] = 1, P[1] = S[1] + S[0], P[2] = S[2] + S[1] + S[0] and so on.

You need to print both the strings, after evaluation from both first and second technique. If any string will contain other that binary numbers you need to print NONE.

Given a normal die and a blank die. Fill in the blank die such that probability of sum of the number from both die is same for all the resulting sum and sum has a range from 1 to 12

Given a pond where all the stones are lined at a distance of one unit (C in each row and there are R such rows), each stone has a special value which denotes the length of the jump the frog can make i.e if frog is on stone (x,y) and value is k then frog can jump to (x+dx,y+dy) where dx+dy=k and frog doesn’t leave the bounds.Find the min number of jumps to reach the stone at (R,C).

Given a lane where there are various houses each containing a fixed amount of gold. Now a robber has to rob the houses such that when he robs a house the adjacent one cannot be robbed.Calculate the maximum amount of gold collected by him.

Given a network of roads connecting cities and capacity of each road(same for all roads)as well as their cost of repair(unique for each road) we are given number of buses(n) running between pair of cities using shortest path only. (Capacity of road= No of buses allowed on that road).
Unsafe roads are road where no of buses on the road > Capacity of the road.
Now given n we have to minimize the overall cost of all unsafe roads.

Given a review paragraph and keywords, find minimum length snippet from paragraph which contains all keywords in any order.

Design notification system (notify the customer with a message)
Client (delivery boy, company updates etc)
Services (Email, SMS, Watsapp)
Scaling up, fault tolerance & failure management
Flexible modifiability of clients & services

Dictionary of words is given
i.e. [“cat”, “dog”, “rat”, “catratdog”, “catter”]
Compound word: A word, which can be split into more than 1 valid words
get compound word, with longest string length.

N people are there.
knows(A,B) return true if A knows B, else false.
Celebrity: A is called a celebrity
If A knows none
Everyone knows A
Get celebrity, with less number of knows() method usage.

You are given a catalog of books, which have following attributes.
Name
Author
Publisher
Publish year
Category
Price
Count (sold)
Implement following APIs on top of this catalog
addBookToCatalog(Book)
searchBook(by partial book name/author)
getMostSoldBooks(by author name/category, limit)
Expectations:
Maintain DB on memory
Code should be readable. Design, handle naming convention,handle exceptions & should be running

Find last cell visited in 2D matrix traveresed in Spiral Fashion

Design an online poker game.

Given a server with a stack with some initial state say 1 Users can modify the stack using regular ops eg push 2 , pop etc and each op causes a version change. i.e version 1 : 1 , version 2 : 2,1 , version 3 : 3,2,1 , version 4 : 2,
You have to design it s.t person can ask for any version of the stack.

Hint : keep copies every k times and keep the ops in an nonvolatile memory

Given any language , you use libraries , which might use more lib etc . Find the order of building the libraries

Given two unsorted arrays A and B in which B can accommodate in A

How will you merge the two arrays.

Design a book catalog search (api’s were given for the search,full needs to be implemented as running application)

A solution was required to make a fantasy league with some budget allocated. Players will have some score/rating and the cost of player. Maximum score was to be achieved with eleven players.

A library for game 2048 was to be designed. The game can have constraints/variations which shall be defined by the game designer. The variations can be adding same numbers or adding Fibonacci numbers etc. APIs were to be exposed to the game designer.

Write down code in any language for a simple employee hierarchy which has 3 types of employees.
1. CEO
2. Manager
3. employee
Where an employee can have only 1 mgr, and a mgr has 1+ employees.
We were asked to input employee details(name ,id, salary,rating etc) in any order (employees might be input before his manager), create the hierarchy and implement these functionality:
1. Print hierarchy given any employee/mgr/ceo (used an n-ary tree + hash table)
2. Given a bonus and performance rating of each employee divide it to the lowest level employees(in the hierarchy ) in the ratio of their rating. i.e 100 divided among 2:3 is 40 and 60. and print the bonus of each ( simple recursive solution)
3. Top 10 employees with ratio of bonus:salary (used maxheap)

Given a login page come up with all possible test case from login API point of view and UI point of view.

What is a columnar database. why we preferred redshift over mysql for data warehouse.

How many ways a 4*n wall be filled with 4*1 sheets so that the wall ends uniformly.

Maintain an employee hierarchy with attributes
Print complete hierarchy of given employee.
find top 10 employees on the basis of salary ,at any instant of time .
Perform CRUD opérations on the hierarchy.

Design a state machine – Each state can handle n events and based on the event type next state is determined

Design delivery system from city Hub to the customer – There was focus on how to figure out the location of the customer from address, finding the shortest path etc.,

You are given with PxQ matrix and a point inside the matrix (x,y) where you standing. If you step outside the matrix you’ll die. You are allowed to move in all four direction. Movement will be totally random. For Given N steps, what is the probability that you’ll alive?

You are given some equations which may contain > or = on different-different operand. For example there are valid input and invalid (a=5, b<a=50)


String e1 = "a>b=1";
String e2 = "a>b=2";
String e3 = "a>c>e=3";
String e4 = "a>c>f=4";
String e5 = "b>a=5";
String e6 = "a>b>c=5";
String e7 = "b=7";
String e8 = "a>b>c>d=99";
String e9 = "a>b=99";

You need to create JSON string from it.
{
‘a’: {
‘b’: [1,2,99],
‘c’: {
‘e’:3,
‘f’:4
}
},

‘b’: {
‘a’ : 5

}


}
Highlighted one are invalid bec as they come they ask for overwrite the data (a>b>c = 5; C has e and f so we can overwrite.

Input: You are given those string in string array
Output:

Construct JSON
Print it
If you print in same as above (nice manner) +point

Code library management system
a) add a book
b) issue a book
c) return a book
d) if a user has kept a book more than 10 days then there should be a fine of Rs. 1 per day post 10 days.

Given daily stock rates of last year give the average stock rate price for a given day range

How would you design Hospital management system ?

There are M chocolate packets each packet can have variable number of chocolates in each packet. There are N students (N < M). Distribute chocolate packets to student such that
a) each student gets 1 packet
b) suppose m1,m2,…mn are the packets which are chosen to be distributed in sorted order of number of chocolates in them (nm-n1 must be minimum)
M = 1, 3, 4, 6 (4 packets with specified number of chocolates in them)
N = 2
Ans = 3,4

Assume you have a starting 4 digit number, say 1234 and and ending 4 digit number 4567. For changing a bit of a number from 1 to 3 (for example), it will take 2 steps (from 1->2 and from 2->3). So to convert 1234 to 4567, you’ll have to change each and every bit individually in some number of steps. (Change 1->4 in 3 steps, 2->5 in 3 steps and so on). Now there is a list of blacklisted numbers. So while transforming start to end, if you reach a blacklisted number, then you cannot change that particular bit, you’ll have to move to another bit. E.g. Assume 1434 is a blacklisted number, and while transforming you reach it, then you have to change either 1, or 3 or the last 4. So you have to find the least number of steps in which start number can be transformed to end number.

I was asked to design a snake and ladder game. The game can have more obstacles than just snake and ladders.

There is a n player game of cards. The deck of card is not fair, i.e. any card can be there any number of times. A card has a number and a color. Each player gets k card each (n and k can be harcoded in the solution). The computer starts the game by throwing a card from the deck of cards. Assume the card is 4 of Green. Then the other player has to throw either a 4 of any color or Green of any number. If the player does not have any such card, then it can say pass. The player who finishes all his card wins. The logic of selecting the card by the user can be hardcoded (Eg, If you use a list data structure for storing the cards for a player, then you can say that the player always throws the first card from the list). The logic was required only to start and conclude the game.

Two players, two field; and have multiple ships located in their fields. They are guessing each others ship position and hitting. Tell who wins first. Design maintainable code which can incorporate future change.

Design a cricket series. Extend it to olympics.

Design and build tic tac toe game. The code should be up and running. It should be scalable to multi-users and nXn grid.

There is a tournament among n teams. and we have a function which takes two team and tells which team is the winner (suppose function takes constant time),then print the result sequence array. There may be number of result sequences so print anyone.Result sequence array will contain the teams in the following manner :
Team1 has won against team 3 , team 3 has won against team 4,team 4 has won against team 2.

and ofcourse output sequence must contain all the teams and no team should get repeated.

E.g. there are 3 teams.

T1, T2, T3

match (T1,T2) = T1
match(T2,T3) = T3
match (T1,T3)= T1

Output Sequence = T1 -> T3- > T2

Print the bottom view of the binary tree.
Example :


1
/ \
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
/
12

Output should be :
8 12 9 10 5 6 11 7

Solution is different from http://www.geeksforgeeks.org/bottom-view-binary-tree/

Given an array and a target number. you have to print all sequences that generates the target number.
you can use two arithmetic operators '+' and '-' to perform operations among array elements.

Note: you can't modify the array and you have to use all the elments of the array. and the order would be same as given in the array.

Example : 1 9 1 2 , Target Number = 9

1 + 9 +1 -2 =9

output should be "1 + 9 +1 -2 "

Question 2 / 2 (Weighted Stone Arrangement)
You are given an infinite number of stones.

The 1st stone has the weight 1
The 2nd stone has the weight 3
The tth stone has the weight W(t) = 2 * W(t-1) + W(t-2)
Thus, the weights of the first 10 stones are

1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363

Note that you only have one stone of each weight.

You have a weighing machine which is the age old 2-pan balance. You wish to use this machine to measure the weight of an item whose weight is T. The item will always be kept on the right pan. A stone may be kept on either one of the pans. Also, it is not required to use all the stones.

The stones have a weird magnetic property, due to which, the kth stone cannot be in the same pan as the (k-1)th stone. This means that the stone with weight 239 cannot be in the same pan as the stone with weight 99, or in the same pan as the stone with weight 577; and so on.

For example,

T = 11 can be measured as

LEFT PAN: 1, 17
RIGHT PAN: 7
Note that the other alternative

LEFT PAN: 1, 3, 7
RIGHT PAN:
is Illegal since 3 cannot be in the same pan as 1 (or 7 cannot be in the same pan as 3).

T = 21 can be measured as

LEFT PAN: 41
RIGHT PAN: 3, 17
It can be proven that to measure any weight T, there exists a unique arrangement of stones that satisfy the given constraints and measure weight T. Thus, T = 11 or T = 21 can only be measured by the respective arrangements above.

You are given T in the input. Output the arrangement of stones that measures T.

Input Specification

The input contains a single positive integer T.

Output Specification

Output the weights of the stones used on the left pan in increasing order, one number per line. Then output a blank line. Followed by the weights of the stones used on the right pan in increasing order. Note that it is assumed that the item will be kept on the right pan.

If there is no stone kept on the right pan, simply output the weights of the stones used on the left pan in increasing order as above, followed by a blank line.

Constraints

1 ≤ T ≤ 1015

Sample Input 1

11
Sample Output 1

1
17

7
Sample Input 2

21
Sample Output 2

41

3
17
Sample Input 3

1000
Sample Output 3

3
41
239
1393

99
577

Directi Off Campus Interview Process 2013-14
.......................................................................
This is year 4096 and humans have found a medicine for immortality in the year 2048. Tukro a famous online social networking site founded in the year 3072 was celebrating its 1024th anniversary. To celebrate the occasion its CEO, Shark, and his team had launched a unique personalised video of length 17min 4sec for each user. The video consisted of a collage of all popular posts made by the user on Tukro.

Raka shared this video with all his friends without reviewing it. Immediately after he finished watching the 1024 second length clip he realised that he made a huge mistake. The video was made of all posts made by Raka, irrespective of the privacy settings of the individual post.

A post is compromised if a friend who was not supposed to see the original post, has seen it now. Raka wants to know how many of his posts have been compromised. Tukro provides the list of users who have watched the video till now. Help Raka find how many posts were compromised.

Raka has N friends, identified by a unique integer between 0 and N-1.

Raka has L lists of friends, identified by a unique integer between 0 and L-1.

Each list can be of length at the most N.
One friend cannot be added more than once to the same list.
A list must have at least one friend.
A friend may be added to multiple lists.
Visibility of a post in Tukro works through two filters

Include Filter: An array of lists, from the L lists above. Friends can view a post if they belong to any friend list, specified in the Include Filter.
Exclude Filter: An array of lists, from the L lists above. Friends can view a post if their name does not belong to any friend list, specified in the Exclude Filter.
Some caveats of the above are

If no Filter is active, the post is visible to all friends
If only Include Filter is active, a friend can see the post only if he is present in at least one of the lists of Include Filter.
If only Exclude Filter is active, a friend can see the post only if he is not present in any of the lists of exclude filter.
If both Include and Exclude Filters are active, a friend can see the post if and only if
he is present in at least one of the lists of include filter and
he is not present in any of the lists of exclude filter
if he is present in both an include filter list, and exclude filter list, he should not be able to see the post
Input Specification

First line contains a single integer N, the number of friends.

Second line contains a list of integers separated by a single space. The first integer V, represents the number of friends who viewed the video. There are V other integers in the line representing the ID's of friends who viewed the video.

Third line contains a single integer L representing the number of lists.

L lines follow. Each line representing a list. The first integer of the line A, denotes the size of the list; followed by A integers, each denoting the friends in the list.

Next line contains a single integer P denoting the number of posts in the video. 2 * P lines follow. Each pair denoting the Include Filter and Exclude Filters of one post respectively.

First two lines denote the Include and Exclude Filters for first post
Next two lines denote the Include and Exclude Filters of second post
and so on..

An include filter is represented by a list of space separated integers. The first integer B represents the number of lists in the filter. B may be 0, to denote that the include filter is not active. If B is more than 0, the include filter is active and the next B integers in the line denote the ID's of lists present in the include filter.

Exclude filters are also represented in the same format.

Output Specification

Print a single integer specifying the number of posts that are compromised according to the definition above.

Constraints

1 ≤ N ≤ 10000
1 ≤ V ≤ N
1 ≤ L ≤ 6
1 ≤ P ≤ 100000

Note that the constraints on N and P are large.
Your solution will exceed time limits if its complexity is O(N*P).
Even O(V*P) solutions may exceed time limit!
Note the small constraint on L.
Sample Input 1

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

Sample Output 1
1

Explanation

There are 10 friends. Their ID's are from 0 to 9
8 of them viewed the video = {0,1,2,5,6,7,8,9}
There are 4 lists
List-0 has 2 friends {3,4}
List-1 has 1 friend {7,6}
List-2 has 3 friends {0,1,5}
List-3 has 3 friends {2,8,9}
There are 4 posts
Post-0 doesn't have any include filter but has List-0 - {3,4} - in exclude filter
3, or 4, have not seen the video
Hence Post-0 is not compromised
​Post-1 has an include filter of List-1 - {7,6} - and no exclude filter.
But other friends have seen the video
Hence Post-1 is compromised
​Post-2 doesn't have any filters. Such a post was intended to be seen by anyone.
​Hence Post-2 is not compromised.
Post-3 has a include filter of List-1, List-2 and List-3.
Their union is {0,1,2,5,6,7,8,9}
These are the exact friends who saw the video
Hence Post-3 is not compromised
Hence only 1 post is compromised.
Sample Input 2
5
2 2 3
5
1 0
1 1
1 2
1 3
1 4
4
3 2 3 4
1 0
3 1 2 3
0
3 0 1 3
0
3 2 3 4
1 0

Sample Output 2
1