CareerCup

You are given 2 strings which are exactly same but 1 string has an extra character. Find that character.

You are given an array of million numbers and provided a range of index (say left, right). For multiple queries, each with input left and right indexes, output the maximum in that range.

Given (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).

We have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.

Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.

Given two numbers m and n. Find all numbers between these two numbers such that difference between adjacent digit is 1
For ex m =0 n =22
O/p - 0,1,2,3,4,5,6,7,8,9,10,12,21

N number of balloons are kept at different heights. You are asked to find out number of arrows to burst them. When an arrow hits the balloon it goes one level down.
Assume that the balloons are having same size.

for example given the balloons heights as array(Array will be given in decreasing order of size) :
5 4 3 3 2 2 1 1 1
minimum number of arrows to shoot them is: 3

explanation:
using first arrow shoot: 5 4 3 2 1
using second arrow shoot: 3 2 1
using third arrow shoot: 1

Example 2:
5 4 2 1

minimum number of arrows to shoot them is: 2
using first arrow shoot: 5 4
using second arrow shoot: 2 1

Expecting the solution to be in O(1) space complexity.

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)

Print an unbalanced binary tree in level order with new lines after each level.

Say you have two large files (100 TB each) and only 1 MB of RAM. What's an efficient algorithm that will print the missing lines (diff)? The files don't necessarily contain duplicates.

The two files are not sorted and could have different ordering in both files.

e.g.:

File1 File2
A B
B A
C C
D E
F D
F

Output:
File 2: E
The input are two large files (containing strings).

The output is a list of strings telling you the presence of a line in File X and not in File Y.

P0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.

Given directory change command -

cd a/b/../c/d/e/../../

Output the visit count for each directory such as -
Root - 1
a - 2
b - 1
c - 2
d - 2
e - 1

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:

Input: [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.

Given range of routing numbers, determine which bank it belongs to.

Ex-
I/p -(123400,123500, BOA), (12538, 12548, GCU)…

For 123450 - Output BOA
12540 - Output GCU

write a JSON validator

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))

Given character a-z find out nth permutation. Where all permutation are only ascending. For e.g

Given characters a,b,c. valid permutations are : a,b,c,aa,ab,ac,bb,bc,cc,aaa,aab,aac,abb,acc,baa,bab,bac,bbb,bbc,bcc,caa,cab,cac,cbb,cbc,ccc

Ex- 4th permutation is : aa

In a binary tree if the neighbours are set on fire for every node , find the path to optimally set the entire tree on fire.

Given an input stream of Swiggy order timestamps and costs, at any instant find the costliest order in the last X mins

You have a plot with a limited amount of points on it.
Find the cluster of points, which contains the biggest amount of point grouped together.

Conditions:
The cluster means, that points are placed not farther than 5 units (Can be measured px, cm, etc.) between each other. The distance is calculated by where

|x1-x| < 5

and

|y1-y| < 5

The cluster should contain at least 3 points.
If there are a few clusters with the same amount of points - return all of them.

Example:
The points are:
(15,116), (1345, 123), (456, 11), (34, 17), (19, 112), (556, 111), (454, 15), (12, 120).
In this case, the best cluster is (15,116), (19, 112), (12, 120)

You are given an N-Dimensional list with 2 methods:
i) getDim -> returns the dimensions .e.g [5,4,3].
ii) getElement([i,j,k]) -> return list[i][j][k] . You have to implement a method to sum all elements in the list.

LCA of directed graph.

Tree Game
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.

Follow up: if player B takes the first hand instead, which node should he pick?

Write your own class for key value store which has four methods:
put(key,value)
get(key)
getRandom() this should return a random value with equal probability

deleteWithKey(key)


I was allowed to use hashmap internally to store data.

this was my second technical phone interview because they wanted to get some more idea about my technical skills.

At first Interviewer asked me to write a problem to solve sudoku and return error if sudoku is invalid.

I told him I already had seen the problem before and he said he really appreciates my honesty.

this was my second technical phone interview because they wanted to get some more idea about my technical skills.

I dont remember the exact problem anymore. but the problem's solution included going through an array and at every step taking 2 minimum element and adding the result. this also includes the result itself.

so lets say for following array:

2,54,4,10,1,7

you first take 1 and 2 and add
then add the result 3 to the array
so now your array looks like :
3,54,4,10,7

then you take 3 and 4 and add them and add result back

I basically used a heap where i take two mins and add them and add the result back to heap.

I have give amazon online test twice in last 8 months and both the times the first question was about heaps and second something about finding shorted path in a grid between two cells

The problem was very similar to the problem from geeksforgeeks:

Shortest distance between two cells in a matrix or grid
Given a matrix of N*M order. Find the shortest distance from a source cell to a destination cell, traversing through limited cells only. Also you can move only up, down, left and right. If found output the distance else -1.

instead of source and destination, they asked for robot to be able to get rid of obstacle at a certain cell.


I have give amazon online test twice in last 8 months and both the times the first question was about heaps and second something about finding shorted path in a grid between two cells

I am given jobs with starttime and end time and we unlimited VMs. at any point a VM can only take one job. so bascially I had to find overlapping jobs and assign them to different machines and those that are not overlapping could be assigned to same machines. The tricky part was when there are two different overlaps and they could be assigned to 2 machines instead of all overlapping jobs being assigned to different machines.The method should return minimum number of VMs used to finish all jobs.

I mentioned sorting the jobs based on start time. and then returning number_of_overlapping jobs +1. but again in some cases if there are two different overlaps which could be assigned to two machines then we need to take care of that.

Expression tree evaluation and also write the class for the node and tree itself. (just basic structure like node and data)

LRU cache. Basically started off with how would I store values and get them from memory for faster access. So I mentioned HashMap. and then interviewer added more info about deleting least recently used element.