CareerCup

We are given a undirected tree with N (1 to N) nodes rooted at node 1. Every node has a value assigned with it, represented by array - A[i] where i:[1:N].

We need to answer Q queries of type : -> V X : longest length of the common prefix between V and any ancestor of X including X, in their binary representation of 62-bit length.

Common prefix between 2 numbers is defined as:

Example :

4: 0..................0100 (62-bit binary representation)
6: 0..................0110
Considering both as 62-bit in it's binary representation.
Longest length of the common prefix is: 60 (as 60 left most bits are same.)
Now we are given the N (num nodes), edges, nodes values (A[i]) and queries, and we need to answer each query in optimal time.

Constrains :

N <= 10^5, number of nodes
A[i] <= 10^9, value of each node
Q <= 10^5 ,number of queries
Edge[i] = (i, j) <= N
Approach :

Create tree and track the immediate parent of each node.
for Each Query : [V, X], traverse each node n(in the path from X to root) and XOR each node's values with V and find the most significant set bit for each of the XOR operation and pick the minimum one among all of them.
So the result for Query : [V, X] : 62 - (1 + Step-2 result).
Is there any other efficient way to solve this problem? As the above approach in worst case takes O(n^2) time.

Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n). 1 <= n <= 10^12

Bob and Alice have teamed up on a game show. They won the first
round, allowing them access to a maze with hidden gold. If Bob can
collect all the gold coins and deliver them to Alice's position, they can
split the gold. Bob can move North⇆South or East⇆West as long as he
stays in the maze and the cell is not blocked. The task is to determine
the shortest path Bob can follow to collect all gold coins and deliver
them to Alice. If it is not possible, return -1.

You will be given an n × m array where each of the values ∈ {0, 1, 2}
representing open, blocked and open with a gold coin. Alice's position is
given as (x,y) = (row, column). Bob starts at the top left in cell (0, 0).


For example, maze = [[0,2,1],[1,2,0],[1,0,0]] with Alice at (2,2) is
represented as follows:

0 2 1
1 2 0
1 0 0

minMoves has the following parameter(s):
maze[maze[0][0],...maze[n-1][m-1]]: a 2D array of integers
x: an integer denoting Alice's row coordinate
y: an integer denoting Alice's column coordinate

Constraints
1 ≤ n, m ≤ 100
0 ≤ the number of coins ≤ 10
1 ≤ x < n
1 ≤ y < m


The first line contains an integer n, the numbers of rows in maze.
The second line contains an integer m, the number of columns in
maze.
Each of the next n lines contains m space-separated integers
describing the cells of each row in maze.
The next line contains an integer x.
The next line contains an integer, y.


Sample Input 0
3
3
0 2 0
0 0 1
1 1 1
1
1

Sample Output 0
2
Explanation 0
The shortest path Bob can take is (0, 0) → (0, 1) → (1, 1).


Sample Input 1
3
3
0 1 0
1 0 1
0 2 2
1
1

Sample Output 1
-1
Explanation 1
It is not possible for Bob to reach Alice, so we return −1.


Sample Input 2

3
3
0 2 0
1 1 2
1 0 0
2
1
Sample Output 2
5
Explanation 2
The shortest path Bob can take is (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 1).

Intelligent Substrings:

There are two types of characters in a particular language: special and normal. A character is special if its value is 1 and normal if its value is 0. Given string s, return the longest substring of s that contains at most k normal characters. Whether a character is normal is determined by a 26-digit bit string named charValue. Each digit in charValue corresponds to a lowercase letter in the English alphabet.

Example:

s = 'abcde'

alphabet = abcdefghijklmnopqrstuvwxyz

charValue = 10101111111111111111111111

For clarity, the alphabet is aligned with charValue below:

alphabet = abcdefghijklmnopqrstuvwxyz

charValue = 10101111111111111111111111

The only normal characters in the language (according to charValue) are b and d. The string s contains both of these characters. For k = 2, the longest substring of s that contains at most k = 2 normal characters is 5 characters long, abcde, so the return value is 5. If k = 1 instead, then the possible substrings are ['b', 'd', 'ab', 'bc', 'cd', 'de', 'abc', 'cde']. The longest substrings are 3 characters long, which would mean a return value of 3.

There are N cars parked in a row in a parking lot of the newly  constructed club. as it is demonstrated in the picture below.




 

There is a gasoline and diesel fueling station installed.at the left and right side of the park.
An automatic fueling robot carries the fuel from station and fill up the parked car with fuel.
The cars are divided into 2 types depending on whether it is a gasoline or diesel car.
1 is denoted as gasoline cars and 2 is denoted as diesel cars.

The automatic robot will be used to provide a cost free fueling service which is filling up
 all cars with 1 litre of each corresponding fuel.
The robot will move in between the 2 fuelling stations as below :
  1) The robot carries 2 litre of gasoline at the gasoline station and starts moving from there.
 2) The robot can fill up the cars of the same type of gas it carries 1 litre each.
 3) The robot can go back to the fuelling station at any time, Independent from the current amount of fuel it carries.
 4) When the robot arrives at the fuelling station, it gets 2 litre of supply of the corresponding fuel.(If the robot has some remaining fuel it will be discarded).

the picture is not there. so, i will explain how the arrary must look like. suppose the arrary is arr od
size x. then at index = 0, there is gas station and at index = x - 1 there is dielsel station. Remaining all indexes are filled with vehicle type. 1 represents gas type and 2 represents diesel type.

Create Valid html from below input.

String str="abcde"

points:- [{0,2,b},

{2,4,u}]

output : <b>ab<u>c</u></b><u>de</u>

Explanation:- character from 0 to 2 index should be bold, 2 to 4 index should be underline. Tricky point is that character at index 2 should be both bold and underline.

A string can contain only a, b or c. There cannot be 2 consecutive same character. First and the last character cannot be the same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple-answer display lexicographically smallest string. For no answer possible display “Not Possible”.

A co-ordinate plane was given. On each point (x, y) there are x+y number of apples on it. A person is standing on (0, 0) and he wants to buy a square plot having N number of apples inside it (including the periphery). Question was to return the value of perimeter of that square plot given N.

Given a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase.
Constraint: A word cannot be a part of more than 10 sentences.
Examples:

Input:
Sentences:
1. Strings are an array of characters.
2. Sentences are an array of words.
Phrases:
1. an array of
2. sentences are strings
Output:
Phrase1 is present in sentences: 1,2
Phrase2 is present in sentences: None
Since each word in phrase 1 exists in both the sentences,
but all the words in second phrase do not exist in either.

Steps to get out of complete binary tree



You are given two integers A and B. A describes the number of nodes in complete binary tree.
You are B steps away from your destination in the worst case.

Initially, you can be at:

The root node of the tree and can only move bottom of the tree.

Any leaf node of the tree and can only move up the tree.

Find and return an array of integers C of size 2
where

C[0]: The number of nodes which are at B steps from the root, i.e. the number of nodes such that,
starting at that root, you have to take
B steps downwards to reach the node.

C[1]: The number of nodes such that the maximum distance from the node to any leaf in the subtree of the node is B.

In a garden, there are several apples trees planted in a grid format. Each point (i,j) in the grid has |i| + |j| apples.

Allie can buy a square plot centred at (0,0). Find the minimum perimeter of the plot (1 unit having length = 1) such that she can collect at
least X apples. All plants on the perimeter of the plot are also included.

Sample:

Input = 1 Output = 8
input = 11 Output = 8
Input = 13 Output = 16

Given an array of integers A. calculate the sum of A[i] %A[j] for all possible i,j pair. return sum%(10^9+7) as an output solve this problem on o(n).

input :-
A=[1,2,3]
Output:-
5
Explanation:-
(1%1)+(1%2)+(1%3)+(2%1)+(2%2)+(2%3)+(3%1)+(3%2)+(3%3)

Question 2: Optimize the problem for total project cost and total project days to minimal.
Given the cost/hour of each worker:
[ 30, 25, 40 ]

Question 1:
There is a bunch of tasks, each task has a code with different time to complete and task dependencies. There are few workers, how to allocate the task to these workers to minimize the total time taken to complete the task.
Example:
No of worker: 3
Task id, Task Time, Task dependency:
1, 2, 0
2, 4, 1
3, 7, 0
4, 12, 1

Question 2: Optimize the problem for total project cost and total project days to minimal.
Given the cost/hour of each worker:
[ 30, 25, 40 ]

"Good Range"

There is a number space given from 1 to N. And there are M queries followed by that. In each query, we were given a number between 1 to N (both inclusive). We add these number one by one into a set.

Good range: A range in which there is exactly one element present from the set.

For each query, we need to find the good ranges. We need to return the sum of boundry of all good ranges.

Input:
First line will take two integer for input N and M.
Then following M lines would be numbers between 1 and N (both inclusive).

Output:
Following M lines contains sum of boudaries of good ranges.

Note:
Range can consist of single element and represented as (x-x) where boundary sum will be x+x.

Example:

Input:
10 4
2
5
7
9

Output:
11
18
30
46

Explaination:
step-1) set: 2
good range: (1-10)
sum: 1+10=11

step-2) set: 2 5
good range: (1-4), (3-10)
sum: 1+4+3+10=18

step-3) set: 2 5 7
good range: (1-4), (3-6), (6-10)
sum: 1+4+3+6+6+10=30

step-4) set: 2 5 7 9
good range: (1-4), (3-6), (6-8), (8-10)
sum: 1+4+3+6+6+8+8+10=46

given array and max element in array. Find no. of elements present between a given range in O(1). You can do one time processing of array.

LCA of directed graph.

Design Movie Review system using OOP concepts. Code should pass all test cases.

A graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted vertices given in K. If it creates a path, we have to discard the edge.

Example: N = 4; K = {(1,4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)

Find numbers that formed from sring

There are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.
Given N and number of players from each country and size K. Find the maximum number of teams you can form.

Given an array of edges between any two points in 2 dimensional space. A single edge is represented by the co-ordinates of two points it is connecting for example (2,3),(4,5) represents and edge connecting points (2,3) and (4,5).Find out the total number of squares possible if all edges are parallel to X or Y axis.
NOTE : Include overlapping squares, squares having one side in common and squares contained within another square. Co-ordinates can have float values.

Example below -
I have considered a very simple input and output combination to keep it short.
Input
{
(0,0),(0,3)
(0,0),(3,0)
(0,3),(3,3)
(3,0),(3,3)
}
Output : 1

Possible Approach : Create a map as below -

Key(Slope of Edge in Degrees) - Value(Array of Edges)
0 - {(0,0),(3,0)},{(0,3),(3,3)}
90 - {(0,0),(0,3)},{(3,0),(3,3)}

While inserting edges in the map, make sure the edges are sorted by max(x1,x2) first and then max(y1,y2).
Pick 2 edges from one slope let's say slope 0, then pick 2 edges from slope 90 and see if square is formed or not. If square not formed, then look at next 2 edges of slope 90 and so on.
Sorting here is an expensive operation.

Please share any better solutions.

Given an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15

Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12
i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)

Given a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles


Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it

Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)

For example

s = 'ababac'

Then substrings are as follow:

1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c

Now, The lengths of LCP of all substrings are as follow

1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

String contains only lowercase alphabates.

There are N nodes in a graph connected by exactly N-1 edges. There is exactly 1 shortest path from one node to any other node. The nodes are numbered from 1 to N. Given Q queries which tell source node and the destination nodes. Find the most visited node after traveling those Q paths. For example, say Q=3
and 3 queries are
1 5
2 4
3 1

So travel from node 1 to node 5, then from node 2 to node 4, then from node 3 to node 1. Finally, find what is the most visited node after the Q queries.
Finding every path and incrementing every visited node count is a naive solution. The interviewer asked me to optimize it.

Roulette -Gamblers Fallacy. start with $50, bet opposite color every time same color 4 in a row. loop 100 time or until $0. Suggest create roulette wheel object with history, a gambler object with maybe gamblingplan object. (you can find more detailed suggestions elsewhere)

Given k,n,m. where k is no. of coconuts you initially have. n is the some no. such that if you have >=n coconuts, you becomes stressed otherwise you become normal. m is the no. of shops.You go from 1st shop to m-th shop without skipping any shop. At i-th shop, either you buy Si coconuts or sell Si coconuts. If you are stressed then you must become normal at next shop. If you have less than Si coconuts and you want to sell then you must sell all the coconuts you have. The task is to calculate maximum possible changes of your mood from stressed to normal or vice-versa.

ie: shop ={100,200,100,1,1} , k=1900 , n=2100 then answer should be 3 as initially mood is happy at first shop we buy 100 coco and total are 2000<n so still happy, at shop 2 coco 2200,now mood is stressed and so

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

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)