CareerCup

You are given with a large paragraph and N words.
You have to find a min length subparagraph of the paragraph which contain all those N words in any order. Here length of a paragraph is the count of words in the paragraph.

Amazon

Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

Write a program to return nearest elements from a binary search tree for input element.

There is a dictionary already implemented. Write a method , which takes input String without space, to replace the characters from the strings which are not present in dictionary with –

Example: Dictionary – a*
………….Input- aaabaa
………….Output- aaa_aa

There is a dictionary already implemented. Write a method, which takes input String without space, to prints all subsets of the input string which is present in dictionary.
Example: Dictionary – a*
………….Input- aaabaa
………….Output- a,a,a,aa,aa,aaa,a,a,aa

There is a door to enter a restroom. Once you enter the restroom there are N toilets starting from 1, 2,... to N. The toilet which is near to entry door starts from 1 and then it serially goes till N. You can use toilet based on below conditions:
1. If none of the toilets are occupied then choose one which is nearest to the entry door(which is toilet#1).
2. If at least one toilet is occupied then choose that unoccupied toilet which is farthest from the occupied ones.
3. If there are more than one unoccupied toilets whose farthest distance from the occupied ones are same then choose one which is near to the door.

For example:
Let's say there are 5 toilets.
-> First person comes and occupies toilet#1(Based on rule#1).
-> 2nd person comes and occupies toilet#5(Based on rule#2).
-> 3rd person comes and occupies toilet#3(Based on rule#2). Note that the farthest distance would have been formed when the new person would have occupied toilet#2(or toilet#4) but with that, the distance between toilet#2(unoccupied) and toilet#1(occupied) would be just 1.
-> 4th person comes in. Now from toilet#1 to toilet#5, only toilet#2 & toilet#4 are unoccupied. Now there are 2 toilets(#2 & #4) whose farthest distance from unoccupied ones are equal(=1). So rule#3 will apply and toilet#2 will be occupied.

You have to find the sum of those toilet numbers which are occupied.

So in above example after 4th person, toilet numbers which are occupied are #1, #5, #3 & #2.
So answer would be 1+5+3+2 = 11.

Print words in order which are occurring once in huge document. The RAM size 100MB and file size 10 GB.
Example: I am good. You are good.
Answer : I am You are
Note : It's not datastructure problem where we can simply make use of LinkedHashMap. The file size is going to be huge.

given a set of digit from 1 to 9 {1,2,3,4,5,6,7,8,9}, write code to find k elements whose sum is equal to n.

e.g.
k=3, n= 9
{1, 2, 6}, {1, 3, 5}, {2, 3, 4}

vector<vector<int>> findKElementsSum(int k, int n)
{

}

How would you like to efficently find the total number of possible ways with which given string may be converted to whole dictionary words.

Example :
String = “Dogeatscare”

possible combinations – “Dog, eat, scare ” and “Dog, eats, care”

output is 2.

class QueryVector
{
QueryVector(vector values)
{
// Implement
}
vector GetIndices(list filters)
{
// Implement
}
}

Say for example vector is like

{“an”, “apple”, “day”, “keeps”, “doctor”, “away”, “apple”, “iphones”, “cool”, “doctor”, “recommends”}.

GetIndices(“apple”) should return (1, 6)
GetIndices(“doctor”,”cool”) should return (4,8,9)
GetIndices(“random”) should return empty vector ()
GetIndices(“random”,”keeps”,”day”,”doctor”) should return empty vector (2,3,4,9)

Important:

1. There can be millions of values in the input vector of string
2. GetIndices can be called repeatedly and it should be optimized
3. How storage optimization is considered and bitmaps etc are used.

You have to implement the following function:
int MinColoring(int k, char* str);int MinColoring(int k, char* str);static int MinColoring(int k, String str) {}static int MinColoring(int k, string str) {}
The function takes a string 'str' of size 'n' and an integer 'k' as its arguments and returns the minimum no. of paint operation required to achieve the final colored sequence as represented by 'str'.
A paint operation is defined as coloring exactly 'k' consecutive balls out of 'n' balls with a single color.
Assumptions:
n > 0
0 < k <= n
Note:
Paint operation always starts from the ball at index 0
Any ball can be repainted any no. of times
Each character in 'str', represented by small letter alphabets, denotes the final coloring of the ball at that index
If the colored sequence cannot be obtained by any no. of paint operations, return -1
Paint operation can not be performed for less than 'k' balls

Example:
Input:
k: 3
str: rrggg
Output:
2
Explanation:
Since we can color 3 balls at a time, we can first color the balls {0, 1, 2} with color "r". Next, we can color the balls {2, 3, 4} with color "g". As a result, color sequence of the ball will be rrggg. And this was achieved in 2 paint operations.

Design a task execution service, which accepts tasks from clients and runs them and returns result. Following is how the

Client Registration (client name, callback method)
Submit Job to service
Once executed service will return the result to client

Lets assume that 20k jobs are getting submitted per second, you need to scale it in such a way that we are able to process as much jobs per second as possible.

Further questions:

So the components are going to be a load balancer, workstations, cache, task runner and DB. How will you make sure that data is consistent among them, mimimal duplication of data and every job is ran only once.

If any machine is down, say DB, workstation etc. how that is going to be handled.

Developing Java game
creating a RESTful service using which players can play a simple game described
below.
The game should have the following rules:
• The player has an infinite amount of coins.
• The player bets 10 coins to play a normal game round.
• In any round (free or normal), the player has a 30% chance of winning back 20 coins.
• In any round (free or normal), the player also has a 10% chance of triggering a free round where
the player does not have to pay for bet. The free round works in the same way as a normal round except
it costs 0 coins. The free round should follow immediately after the normal round.
• The player can both win coins and free round at the same time.

I participated interview event with Amazon and receive email from Amazon recruiter that the team was happy with my performance and would be giving me offer at Amazon Vancouver Office, Canada. However,17 days later i still not get an official offer. I did several follow up with the recruiter within the period, just to get some "they are finding team for me" response. What could go wrong? Why is it in my case that the offer is being process so slow?

I have a service in Which you need to send below data in SMS with a keyword and in return you will get the availability of flight or you can book a seat in flight.

Data - AirlineName, Date, Time, From, To

1. Give Test Data
2. Give Test Scenarios

3. If you have not being given any Mobile phone to send text or any API client to query the webservice, how will you test this?

I have clicked some photos in a Camera. I am trying to transfer photos to laptop using USB cable but the Camera is not getting connected. Give debugging steps.

Write a Java code that take a string of parenthesis as input and return if the string is valid or not . The input will have '(' and ')' and also '*' and * serves as wild card and can be used in place of both '(' and ')' or it can be null.

For example,the String (*)(*)(** is a valid String.

Follow up: What if '[]' and '{}' are also in the string along with '()' and * can be used in place of any of them or can be considered as null?

Find the indices of all anagrams of a given word in a another word.
For example: Find the indices of all the anagrams of AB in ABCDBACDAB (Answer: 0, 4, 8)

All jumbled numbers of n digits in max (worst case) O(n) and min (avg case) O(log n) time.

A number is a jumbled number if the _absolute_ difference between adjacent digits is <=1.
For an input n=3
output should be
100
101
110
111
121
122
...
and so on.

The problem is similar to the one listed here https://www.careercup.com/question?id=5729332770111488

But this problem also has a O(n or log n) limitation and the solutions listed in the above mentioned problem at the time of posting this question, do not satisfy the criteria

PS: 001 is not a 3 digit number.
210 is absolutely fine as the absolute difference between adjacent digits is <=1.

How to Design Netflix.(System Design)

How to Design App-Store like google play.(System Design)

How to design a Debugger both HLD and LLD?

You are given a stream of numbers which represent the stock prices of a company with timestamp. You need to perform some set of operations on the stream of data efficiently as below: 1. findStockPriceAtGivenTimeStamp(Timestamp) 2. deleteAndGetMinimumStockPriceForToday() Timstamp: 1 2 3 . 4 . 5 Prices: 12 34 4 . 1 . 18

Design online multiplayer generic board game (like chess). How will you store sessions.(RDBMS or REDIS) How will the
competitor be chosen and notified(HTTP or what?).
What are the appropriate classes?

Design Recommendation system. How will you generate generate recommendations for millions of users. DB Schema, How will you improve latency? if the user is searching a item, when will you show next recommendations. How will you update, latency basically and consistency.

You are provided with 2D char array. You have to provide the 2D char array as response which contains the multiplication od the input array. For eg: input=> {{a,b},{c,d}}, output => {{a,c},{a,d},{b,c},{b,d}}

You are provided with different Excel files and the data format those files contain. You are also provided with low level parser. You have to design a system which takes the excel file and its data type as the input and returns the list of Data objects in the file.

Design JProfiler. How will you design datastructure and why, function stacktrace. HLD+LLD

Design a Fresh Grocery System. Means Daily usable Items, you cannot store them in inventory like bread, milk etc.
HLD+ DB Schema + Concurrency issues + Scalable architecture. How will you scale to multiple countries

How to develop a web based multiplayer chess game. There will be 2 player in each session. There will be multiple sessions.

My answer(I was not selected)
Each player will have a database with columns
user id(primary key), passwd,no of games played, won,drawn,last active time,sq1,sq2,...sq64,move made flag,pawn num, sqstart,sqend
where sq1-denotes square 1 and its value represents the pawn num in sq1
question- what all fields in database will be encrypted
answer-passwd
question- why not others
answer-may be system admin needs to access them
question – how will u start a session between players?
Answer-When a player logs in, his last active time is updated. Each player is shown a list of last active players to chose from.Or system can arbitrarily select one.When a player is selected, he gets a request. Each player receives a list of requests from other players. He choses from one. That player gets an acknowledgement others get negative acknowledgement. If acknowledgement does not come in time then that player is dropped and another player is selected.
Question- http connection, can not send request from server. How the 2 players will send request to each other and how session will be initiated?
Question-how the game will be stored?
The 64 squares sq1,sq2,..sq64 will each store the pawn number in them. From random number calculatio, it will be decided which one is white and which one is black 1st time. When a player makes move,has made move flag will be true. The last move is stored as sqstart,sqend,pawn number. Each time a move is made check for valid move.The other player continuously polls for has made move flag to know if it is his turn
remarks- ur design is not scalable.