CareerCup

Given a tree with n nodes and each node has 0 - n coins. The total coin number is n. Now we need to move the coins such that each node has exactly one coin. What's the minimum moves required? Each move can only move one coin to an adjacent node. (Notice it's not necessary to be a binary tree)

For example tree: 
1
|  \   \ 
0  1   0
|
3
will needs at least 4 moves.

binary search

Explain the difference between ORM and JDBC.
Provide some examples and when to use one over the other.

There are N trees growing along the street. For safety reasons, one if the trees needs to be cut down. The local council wants the street to looks ordered, so all the remaining trees needs to be in non-decreasing order of height. Your goal is to count number of ways this can be done.

Write a function

class Solution { public int solution (int[] A); }

Each element in the tree denote the height of tree.

return 0 If this condition can't be satisfied.

Example :

Given A[3,4,5,4] Your function should return 2. You can cut down the tree of height 5 and second tree of height 4.

Given A[4,5,2,3,4] Should return 0 as after cutting any tree , it can't be ordered by height.

Given A[1,2,3....100000] Should return 100000. You can cut any one tree.

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

Suppose we want to build a scheduling app. We have the times people are currently busy, e.g.
{
Alice: [(13.5, 14), (15.75, 17)],
Bob: [(9, 12), (13, 14), (14, 16)],
Eve: [(9, 11), (12.5, 13.5), (14, 15), (16, 18)]
Mallory: [(0, 9), (12, 24)]
}

For simplicity, lets represent times as numbers between 0 and 24 and the times people are busy as (start_time, end_time) pairs. For example, (13.5, 14) means that Alice is busy from 1:30PM-2PM.

Given a list of people's schedules, write a function to return a list of the time intervals all the people in the list are free to meet.

For the example above, here's some sample output:
Alice, Bob => [(0, 9), (12, 13.5), (17, 24)]
Bob, Mallory => []
Alice, Bob, Eve => [(0, 9), (12, 12.5), (18, 24)]

Given an array which represents columns, find the position of two columns which when removed will trap the maximum amount of water. This is related to trapping raining water problem.

Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.

For eg. 6, 9, 3, 2, 10, 2, 3

How should I prepare for the interview with Alexa team at Amazon?

Given multiple tuples in the form of (A,B) where A is the parent and B is the child in a binary tree, find if the input is valid or not. 4 error conditions were provided:
1. If a parent has more than 2 children,
2. If duplicate tuples entered,
3. If the tree has a cycle,
4. If more than one root possible.

For violation of multiple validity conditions, print the condition coming first in the above order.
If the input is valid, print the tree in a serial representation. For eg: If input is (A,B), (B,C), (A,D), (C,E) , output: (A(B(C(E)))(D))

Suppose If you are hacker, you have to push data to server and find how much data server can accept using minimal number of times. We don't the size of how much server will accept.

Family And Relations interview problem as below:

Going through the old stuff in his attic, Indiana comes across a chart which looks like a family
tree of multiple generations which shows his ancestors.
Excited by the discovery, he decides to digitise the family tree and utilise it to identify
relationships of a person with another on the family tree. Indiana has approached you to help
him write a command-line application to convert the family tree into some digital format.
Model the family tree such that:
● Given an input in a format
Person=Alex Relation=Brothers
Expected Output should be
Brothers=John,Joe
$ run_application
Input: Person=Alex Relation=Brothers
Output: Brothers=John,Joe
$
List of supported relations:
● father
● mother
● brother(s)
● sister(s)
● son(s)
● daughter(s)
● cousin(s)
● grandmother
● grandfather
● grandson(s)
● grandaughter(s)
● aunt(s)
● uncle(s)
Indiana notices that no two family members have the same name. Indiana also realises that the
information on the chart is a bit outdated. He also need to add more information on the chart so
that the information is up to date.
● Given an input in a format
Husband=Bern Wife=Julia
The application should add Julia as a spouse for Bern.
Person=Bern Relation=Wife
Should return output as:
Wife=Julia
$ run_application
Input: Husband=Bern Wife=Julia
Output: Welcome to the family, Julia!
Input: Person=Bern Relation=Wife
Output: Wife=Julia
$
Indiana should also be able to add a child once its born to a mother.
● Input: Mother=Zoe Son=Boris
Input: Person=Paul Relation=Sons
Output: Sons=Boris,Roger
$ run_application
Input: Mother=Zoe Son=Boris
Output: Welcome to the family, Boris!
Input: Person=Paul Relation=Sons
Output: Sons=Boris,Roger
$
Assumption:
● Names are unique. Any new member added will also have a unique name.

Family And Relations interview problem description as below:

Going through the old stuff in his attic, Indiana comes across a chart which looks like a family
tree of multiple generations which shows his ancestors.
Excited by the discovery, he decides to digitise the family tree and utilise it to identify
relationships of a person with another on the family tree. Indiana has approached you to help
him write a command-line application to convert the family tree into some digital format.
Model the family tree such that:
● Given an input in a format
Person=Alex Relation=Brothers
Expected Output should be
Brothers=John,Joe
$ run_application
Input: Person=Alex Relation=Brothers
Output: Brothers=John,Joe
$
List of supported relations:
● father
● mother
● brother(s)
● sister(s)
● son(s)
● daughter(s)
● cousin(s)
● grandmother
● grandfather
● grandson(s)
● grandaughter(s)
● aunt(s)
● uncle(s)
Indiana notices that no two family members have the same name. Indiana also realises that the
information on the chart is a bit outdated. He also need to add more information on the chart so
that the information is up to date.
● Given an input in a format
Husband=Bern Wife=Julia
The application should add Julia as a spouse for Bern.
Person=Bern Relation=Wife
Should return output as:
Wife=Julia
$ run_application
Input: Husband=Bern Wife=Julia
Output: Welcome to the family, Julia!
Input: Person=Bern Relation=Wife
Output: Wife=Julia
$
Indiana should also be able to add a child once its born to a mother.
● Input: Mother=Zoe Son=Boris
Input: Person=Paul Relation=Sons
Output: Sons=Boris,Roger
$ run_application
Input: Mother=Zoe Son=Boris
Output: Welcome to the family, Boris!
Input: Person=Paul Relation=Sons
Output: Sons=Boris,Roger
$
Assumption:
● Names are unique. Any new member added will also have a unique name.

Family And Relations interview problem description as below:

Going through the old stuff in his attic, Indiana comes across a chart which looks like a family
tree of multiple generations which shows his ancestors.
Excited by the discovery, he decides to digitise the family tree and utilise it to identify
relationships of a person with another on the family tree. Indiana has approached you to help
him write a command-line application to convert the family tree into some digital format.
Model the family tree such that:
● Given an input in a format
Person=Alex Relation=Brothers
Expected Output should be
Brothers=John,Joe
$ run_application
Input: Person=Alex Relation=Brothers
Output: Brothers=John,Joe
$
List of supported relations:
● father
● mother
● brother(s)
● sister(s)
● son(s)
● daughter(s)
● cousin(s)
● grandmother
● grandfather
● grandson(s)
● grandaughter(s)
● aunt(s)
● uncle(s)
Indiana notices that no two family members have the same name. Indiana also realises that the
information on the chart is a bit outdated. He also need to add more information on the chart so
that the information is up to date.
● Given an input in a format
Husband=Bern Wife=Julia
The application should add Julia as a spouse for Bern.
Person=Bern Relation=Wife
Should return output as:
Wife=Julia
$ run_application
Input: Husband=Bern Wife=Julia
Output: Welcome to the family, Julia!
Input: Person=Bern Relation=Wife
Output: Wife=Julia
$
Indiana should also be able to add a child once its born to a mother.
● Input: Mother=Zoe Son=Boris
Input: Person=Paul Relation=Sons
Output: Sons=Boris,Roger
$ run_application
Input: Mother=Zoe Son=Boris
Output: Welcome to the family, Boris!
Input: Person=Paul Relation=Sons
Output: Sons=Boris,Roger
$
Assumption:
● Names are unique. Any new member added will also have a unique name.

How would you tell whether a graph has a node with n degree??
tell your approach

If you had n racers and m checkpoints, how would you list out the racers in the order in which they are in the race given that each checkpoint gets a notification when a specific racer crosses it?

Your code should run in O(1).

Note: Players cannot cheat, i.e. they cannot miss a checkpoint

Example:

Assume 5 checkpoints(C1, C2, C3, C4, C5) and 10 racers(P1, P2,...P10).

Now once the race begins, lets say P2 first crosses C1. So the current race order is P2.

Now P1, P3, P4 cross C1; so the race order is P2, P1, P3, P4.

Now P1, crosses C2; so the race order becomes P1, P2, P3, P4

Now P3, crosses C2; so the race order becomes P1, P3, P2, P4

Now P5, crosses C1; so the race order becomes P1, P3, P2, P4, P5

Now P1 crosses C3; so the race order remains P1, P3, P2, P4, P5

and so on.

Assume that you get notified of players crossing a checkpoint by a function update(player name, checkpoint). Your task is to show the players in order in O(1) i.e return a vector of players in-order in O(1)

Database query response times have increased. An API which is dependent on this database will see - *

This is a multi-select answer.

Increase in the latencies.
Increase in RAM utilisation on the API servers
Increase in CPU utilisation on the API servers
Increase in 200 response codes
Increase in 5xx responses

If a sorted array is rotated by k positions, what is the time complexity to find the starting point of the original array?
1 point
O(logn)
O(1)
O(n)
O(nlogn)

Setting a value in cache is failing. What are the acceptable production practices? *

1. Raise an exception immediately
2. Retry in equal intervals of time until the set call succeeds
3. Retry with exponential back off until the set call succeeds
4. Retry 2 or 3 times with exponential back off.
5. Retry 2 or 3 times with equal intervals of time.

This is a multi-select question.

We have a database that allows 2 concurrent writes and 3 concurrent reads. Each read/write operation takes 10ms to complete. What is the time taken to process all the requests in the orders mentioned (all requests can be assumed to be coming in at the same instant of time and are operating on a single row in a table) - 1. write, write, read, write, read, read, write, read 2. read, write, read, write, read: *


1. 30 ms 2. 10ms
1. 60 ms 2. 10ms
1. 10 ms 2. 10ms
1. 20 ms 2. 10ms
1. 10ms 2. 20ms
1. 60ms 2. 30ms

Given max. travel distance and forward and backward route list, return pair of ids of forward and backward routes that optimally utilized the max travel distance.:

eg: max travel distance is : 11000
forward route list : [1,3000],[2,5000],[3,4000],[4,10000]
backward route list : [1,2000],[2,3000],[3,4000]

Result : [2,3] ...2 is from forward and 3 is from backward...total distance is 9000...no other combination is there which is >9000 and <=11,000.......0(n^2) solution is straight forward, thinking that sorting both might help.

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

The power of three: 3 reasons why your business needs an app.

Given an array of integers, find out how many unique BST can be generated from the array.

Given an array of Integers, find out how many combinations in the array, satisfy the equation x+y+z=w, where x,y,z and w belong to the array and idx(x)<idx(y)<idx(z)<idx(w). Elements are unique.

It was a online coding round on software provided by samsung itself.
Given a graph print either of the set of the vertices that are colored with the same color. And if the graph is not bipartite print “-1”. Test cases also included the cases when a graph is not connected.
Note: No STL or other library functions were allowed

Given an array, coin of size n, coin[i] denotes the no. of coins on the position i. Can move any number of coins from the position i to (i+1) or (i-1). What is the minimum no. of moves required to redistribute the coins, so that each position i has at least 1 coin ?
Note: Summation of total coins on the array is exactly n.

How does inventory management work? I mean if there is only one item left, and multiple users checking out, how to handle such scenarios? Do we lock the entire product?

Morse code is a method of transmitting text information as series of long and short sounds or visual signals. Pauses are used during transmission to group letters and words. The common convention for writing morse code is to use dots (.) and dashes (-) for the short and long signals however without including pauses (e.g. as spaces) morse code quickly becomes ambiguous. For example the code -....--.... has 13 valid translations (bans, bates, bath, begs, digs, etc)
Write a function getAllEnglishTranslations which takes a morse code without any pauses and returns all valid translations.
std::vector<std::string> getAllEnglishTranslations(std::string morseCode)

Output must be sorted in ascending alphabetical order.
Assume there are only 7 alphabets and below are their mappings
M = dash-dash (--)
C = dash-dot-dash-dot (-.-.)
O = dash-dash-dash (---)
D = dash-dot-dot (-..)
I = dot-dot (..)
N = dash-dot (-.)
G = dash-dash-dot (--.)
Assume input code is a valid morse code

In my organisation, I have m different databases, n different applications, p different resources.

How do I go about building access control system for each of this database/application on an individual user basis?

The user can raise a request for access to a resource.
The request needs to be a series of stakeholders which should be configurable. Once the user has all approvals, he/she can access the resource.