CareerCup

Find LCA for list of nodes of a tree

Function defined as below -
TreeNode findLCA(TreeNode root, List<TreeNode> nodes)

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

Get the sum of all prime numbers up to N. primeSum(N).
Follow-up: If primeSum(N) is frequently called, how to optimize it.

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

You are required to collect N numbers from a bag. Initially, the bag is empty. Whenever you put a number X in the bag, then the owner of the bag asks the question.

The questions are as follows:

. What is the greatest integer that is smaller than X and present inside the bag?

. What is the smallest number that is greater than X and present inside the bag?

If you answer both the questions correctly, then you can put X inside the bag. Your task is to answers the questions that are asked by the owner of the bag. If no such numbers exist in the bag print -1.



Example:
5 (Number of elements in the bag)
1
4
2
3
7


output:
-1 -1
1 -1
1 4
2 4
4 -1

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)

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

"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

Design a system to upload images with tags. The tags should be searchable and search should return images linked to those tags.

Give m balls and n bins. Find out how many ways to assign balls to bins. Notice the buckets has no order. Like (1,2,3) and (3,2,1) are considered the same.
eg, m = 3, n = 2, return 2. (1, 2) and (3, 0)

Given items as Shirt, Trouser, Shoes, Tie, Belt, Shocks, and dependencies as -
Tie can be worn after Shirt
Belt can be worn after Shirt and Trouser
Shocks can be worn after Trouser
Shoes can be worn after Shocks

Find various orders in which the activity of wearing clothes can be completed.

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

Design amazon online book store.

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.

Verify if S2 = {5,8,2} is a subset of S1 = {1,5,4,6,8,2} and S3 = {5,8,2,7} is not a subset of S1.

Verify if the given strings is an anagram.
Ex: Str1: LISTEN, Srt2: SILENT.
Alter the program if there is more than one letter that repeats in any one of the strings.

Write a code to return a value 'True' if the number '1' throughout the array appears consecutively. Ex: S = {1,1,1,0,0,3,4}.
Else, return 'False' if the array does not have the given number (char = '1' in this case) in the consecutive order. Ex: S = {1,1,0,0,1,3,4}

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

Design a vending machine with following functionalities
Three types of Users : User, Operator, Admin
User can select and buy multiple items at a time. Money can be inputted multiple times (you will get the item if there is a time gap > 30 secs). He can also do window shopping (see only the prices of items and buy nothing)
Operator can load the items and mark the items as expired if needed, gets notified if a product goes out of stock.
Admin can own multiple vending machines, he should have a analytics report of the items purchased in a month. He can also change the prices directly and it should reflect in all the vending machines which he owns.
Exception handling in all the edge cases
Both HLD and LLD were expected.

You have been given a set of inter-dependent tasks along with the time taken to execute them. We have more number of parallel processors available than the number of tasks given. There could be multiple starting tasks. There could also be cyclic dependencies. Calculate the minimum time required to complete all the task.

Find a subarray with a give sum

Count number of strings of length N with following properties:

A. Consists of char 'A' and 'B' only.
B. There is atleast one occurrence of 3 consecutive Bs.

Input: Only line having integer N.

Output: Number of string with given properties. As then number can be very large print it with modulo 10^9+7.

Sample Input 1:
3

Sample Input 2:
1

Explanation: Only possible string "BBB"

Its farewell day, there are total N students, every student has bought a gift to give. He/She will give this gift to some other student. After gifting process is over, you are given an array, representing number of gift student receive i.e. ith number denoting number of gift he/she got. Your task is to find, whether given gift count array is valid or not. If it is valid print any of possible way of gifting that lead given array.

PS: Student can't gift to himself. Student has exactly one gift with himself.

Input: First line will have one integer M, denoting number of students. Next line wil have N spaced integers denoting number of gift student gets.

Ouput: -1, if given gift received array is not valid else print N spaced integers denoting ith gifted to jth.

Sample Input 1:
3
1 1 1

Sample Output 1:
2 3 1

Parking lot problem: Given 3-dimensional parking lot, lets say, length width and floor. Implement following two methods:
void unpark(int i, int j, int k); where i, j, k are the parking coordinates.
void park(); The car should be parked in empty cell with lowest floor and between length and breadth prefer minimum length.Example, (3, 4, 2) is preferred over (1, 1, 3) as floor is 2 in first case. (1, 2, 3) is preferred over (2, 1, 3). (2, 3, 3) is preferred over (2, 4, 3).

Given an array find if array gets sorted by reversing any subarray of this array. Ex: In {1, 2, 3, 4, 8, 7, 6, 9} we can reverse subarray from index 4 to 6.

LLD for third party delivery vendor for registration and notification system.

Design gaming platform. A number of games can be hosted on this platform. User can login and select a particular game.