CareerCup

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.

Given movement of Robot -
G-GO one unit
L-Turn left
R-Turn right

Given an input of string have to find whether there exists a circle which the robot would traverse. Input of string is the set of G,L,R have to return yes or no.

Given a list of strings. Check whether any two strings, if concatenated will form palindrome or not.

There is a hierarchical structure in an organization. A party is to be organized. No two immediate subordinates can come to the party. A profit is associated with every person. You have to maximize the total profit of all the persons who come to the party.

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.

How will you implement organizational chart? Implement two methods -
isPeer - Should return true if two employees have same managers.
isManager - should return true if manager is management chain of given employee.

Relation between 2 animals is given.
A is child of B
C is child of B
A is child of D

An animal can be child of 0 to 2 parents. With this given data, find out if two animals are related to each other.
Follow up question was - Maternal side animals, should not be related to patrernal side family.

You have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR

Given array of integer, count number of distinct sub array such that it has at most k odd elements and two sub array differ if only when they have at least one member differ.

Example:
{3, 2, 3, 4}, k = 1;
output; 7
[ [3], [2], [4], [3,2], [2,3], [2,3,4],[3,4] ]; Note we did not count [3,2,3] since it has more than k odd elements.

Example 2:
{6, 3, 5, 8}, k = 1;
[ [6], [3], [5], [8] , [6,3], [5,8] ] = 6
We did not count [3,5] as it has > k odd elements

Example 2:
{2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12}
There are these many arrays ;
[2], [2] , [5], [6], [9] , [2], [11], [9], [2], [11], [12]
[2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 9] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [5, 6, 9] , [6, 9, 2] , [9, 2, 11] , [2, 11, 9] , [11, 9, 2] , [2, 11, 12] , [2, 2, 5, 6] , [2, 5, 6, 9] , [5, 6, 9, 2] , [6, 9, 2, 11] , [9, 2, 11, 9] , [2, 11, 9, 2] , [11, 9, 2, 11] , [9, 2, 11, 12] , [2, 2, 5, 6, 9] , [2, 5, 6, 9, 2] , [5, 6, 9, 2, 11] , [6, 9, 2, 11, 9] , [9, 2, 11, 9, 2] , [2, 11, 9, 2, 11] , [11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2] , [2, 5, 6, 9, 2, 11] , [5, 6, 9, 2, 11, 9] , [6, 9, 2, 11, 9, 2] , [9, 2, 11, 9, 2, 11] , [2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9] , [5, 6, 9, 2, 11, 9, 2] , [6, 9, 2, 11, 9, 2, 11] , [9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9] , [2, 5, 6, 9, 2, 11, 9, 2] , [5, 6, 9, 2, 11, 9, 2, 11] , [6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2] , [2, 5, 6, 9, 2, 11, 9, 2, 11] , [5, 6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9, 2, 11, 12]

But only 18 get qualified as there are duplicates like [9, 2, 11] etc.

Qualified arrays are
[2] , [5], [6], [9] , [11], [12] , [2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [6, 9, 2] , [2, 11, 12] , [2, 2, 5, 6]


MY finding so far;
we can use sliding window technique, such that we start counting all sub array of len = 1 to n such that each sub array are different and have at most k odd elements

Here is the code, that i've written for this approach O(n^2)

static int subArraysBrute(int arr[], int k) {


        int count = 0;
        Set<Integer> set = new HashSet<>();

        //Count single length
        for (int i = 0; i < arr.length; i++) {
            count += set.contains(arr[i]) ? 0 : 1;
            set.add(arr[i]);
        }

        int len = 2;
        int odd;

        Set<List<Integer>> setArray = new HashSet<>();
        while (len < arr.length) {

            setArray.clear();
            for (int i = 0; i < arr.length - len + 1; i++) {
                int j = i + len - 1;
                odd = 0;
                List<Integer> ar = new ArrayList<>();
                for (int x = i; x <= j; x++) {
                    if (arr[x] % 2 != 0)
                        odd++;
                    ar.add(arr[x]);
                }

                if (!setArray.contains(ar)) {
                    if (odd <= k) {
                        count++;
                        System.out.print(ar + " , ");
                    }


                }

                setArray.add(ar);
            }
            len++;

        }
        return count;

    }

Other findings;
1. We can't sort the array, as they will ruin the subarray property
2. We can't use simple sliding technique as they will mis so many sub arrays ( moving from left to right window) - I've tried this, this fails like any thing;

Probably, in second idea (sliding window), can be improve further such that once we counted sub arrays, we can run one more time and count those sub array which are left out.

Count number of possible rhythm in a poem.
Explanation:
Twinkle, twinkle, little star, [ A ]
How I wonder what you are! [A]
Up above the world so high, [B]
Like a diamond in the sky. [B]

In the above poem, we see the first two line ( ending with "star" and "are" ) is in the rhythm that's why they are given as character "A" and similarly last two lines (ending with "high" and "sky" ] s in the rhythm that's why they are given as character "B".

Questions: Given "n" number of lines in a poem, Count number of possible rhythm in a poem.
P.S. output should be in lexicographical order only
Example:
n=1
only one possible "A"
Answer: A, count =1

n=2 [ possible chars are A,B]
AA
AB
BA <- This is not possible as it collide with AB. How? Look at the pattern
AB says first line has different rhythm and second line has different rhythm then first line.
Similarly BA is also shows the same ; first line has different rhythm and second line has different rhythm then first line.
Hence discard

n=2
AA
AB , count=2

n=3 [ possible chars are A,B, C]
AAA
AAB
ABA
ABB
ABC, count=5

Look we can't have AAC as it collide with AAB (first two are same and last is different in both)
Similarly other BCA/ BAC etc we'll discard them because of collide and lexicographical ordering.


n=4, there will be 15 [ we need to print all of them too ]

My Finding;
1. I found out that, this is just a bell number ( see the pattern 1,2,5,15.... )
2. I found, this is Dynamic programming question, we can generate the next n+1 from n; How

n=2 has
AA
AB

n=3
Take AA; there are three possiblilties to append a character is A,B,C
But since the last character is A; so lexicographically A and B can be appended at the most, since appending C could conflict with B.
AA(A)
AA(B)

Take AB; there are three possibilities to append a character is A,B,C
But since the last character is B; which is lexicographically smaller than A, so lexicographically A, B,C can be appended easily,

AB(A)
AB(B)
AB(C) <- this is possible since its not colliding with any thing

So ans; 5
AA(A)
AA(B)
AB(A)
AB(B)
AB(C)

Now lets try n=4 [ now its become complicated ;A,B,C,D]
Take AAA; possibilty A,B, not possible C/D conflict with B
AAA(A)
AAA(B)

Take AAB, Possibility is A, B C but what about D; is it possible ? Yes/No
AAB(A)
AAB(B)
AAB(C)
AAB(D) <- it collide with last C so discard ;
Hence with AAB
AAB(A)
AAB(B)
AAB(C)


Take ;
ABA(A)
ABA(B)
ABA(C)
ABA(D) Not possible ; collide with C

If you observe there is a pattern with last character to first character from right to left;




Solution: Brute force is obvious solution; and generating number is also fine since you can use Bell number [ i was not able to come up with this solution though, found later]

Any one can help me over here?

Design a data scrubber.

Say a customer couldn't use Alexa with Philips light bulb. Now customer calls to Alexa/Amazon customer support they figure out the issue is not with Alexa it's with the Philips LED bulb.

Now amazon will redirect their customer call / chat to third party customer support (Philips in this case).

Now somehow we need prevent the possibility of third party customer support trying to exploit our customers. For ex: asking their bank accounts, credit card, Social Security number etc..

How will you do that for AMAZON level ?

Prroblem: write an algorithm to calculate the minimum cost to add new roads between the cities such that all the cities are accessible from each other

int numTotalAvailableCities = 6;
int numTotalAvailableRoads = 3;
int[,] roadsAvailable = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
int[,] costNewRoadsToConstruct = { { 1, 2,5 }, { 1,3,10 }, {1,6,2} ,{ 5, 6, 5 } };
int numNewRoadsConstruct = 4;

public class MinimumCostToConstructNewRoad
    {
        public static int getMinimumCostToConstruct(int numTotalAvailableCities,
            int numTotalAvailableRoads,
            int[,] roadsAvailable,
            int numNewRoadsConstruct,
            int[,] costNewRoadsConstruct)

        {
            int totalCost = 0;
            bool[] Visited = new bool[numTotalAvailableCities];
            int[] Keys = new int[numTotalAvailableCities];
            int[] Parent = new int[numTotalAvailableCities];

            int[,] AdjMatrix = GetAdjecencyMatrix(roadsAvailable, costNewRoadsConstruct, numTotalAvailableCities);


            for (int i=0;i< numTotalAvailableCities;i++)
            {
                Keys[i] = Int32.MaxValue;
            }

            Keys[0] = 0;
            Parent[0] = -1;

            for(int i=0;i< numTotalAvailableCities-1;i++)
            {
                var u = FindMin(Visited, Keys);

                Visited[u] = true;
                for(int v=0;v< numTotalAvailableCities;v++)
                {
                    if(Visited[v]==false && AdjMatrix[u, v]!=Int32.MaxValue && AdjMatrix[u,v]<Keys[v])
                    {
                        Parent[v] = u;
                        Keys[v] = AdjMatrix[u, v];
                    }
                }

            }

           for(int i=1;i< numTotalAvailableCities;i++)
            {
                totalCost = totalCost + AdjMatrix[Parent[i], i];
            }
            return totalCost;
        }


        private static int FindMin(bool[] Visited, int[] Keys)
        {
            int min = Int32.MaxValue; int index = -1;
            for (int i = 0; i < Keys.Length; i++)
            {
                if (Visited[i] == false && Keys[i] < min)
                {
                    min = Keys[i];
                    index = i;
                }
            }
            return index;
        }


        private static int[,]  GetAdjecencyMatrix(int[,] roadsAvailable, int[,] costNewRoadsConstruct,int numTotalAvailableCities)
        {
            int[,] AdjMatrix = new int[numTotalAvailableCities, numTotalAvailableCities];

            for (int i = 0; i < numTotalAvailableCities; i++)
            {
                for (int j = 0; j < numTotalAvailableCities; j++)
                {
                    AdjMatrix[i, j] = Int32.MaxValue;
                }
            }


            int count = 0;
            for (int i = 0; i < roadsAvailable.GetLength(0); i++)
            {
                int start = roadsAvailable[i, count]-1;
                int end = roadsAvailable[i,count+1]-1;
                AdjMatrix[start, end] = 0;
            }

            for (int i = 0; i < costNewRoadsConstruct.GetLength(0); i++)
            {
                int start = costNewRoadsConstruct[i, count]-1;
                int end = costNewRoadsConstruct[i, count+1]-1;
                int cost= costNewRoadsConstruct[i, count + 2];

                AdjMatrix[start, end] = cost;
            }

            return AdjMatrix;
        }
    }

Imagine you have a computer keyboard that has all the letters mismatched

example:
typing q gives you a
typing w gives you b

all 26 letters in the alphabet are there, but typing one letter will give you another one

you are asked to write an algorithm to find whatever word you tried to type and count how many cycles you did to find the word

a restriction was set you need to type the whole word every time, not go character by character

note: a graph was suggested to represent the letter mappings

You have an array of numbers. You have to give the range in which each number is the maximum element. For Example, If array is [1, 5, 4, 3, 6] The output would be

1 [1, 1]
5 [1, 4]
4 [3, 4]
3 [4, 4]
6 [1, 5]

How to find out distinct ngrams from a email_alias.
For instance xyz@gmail.com here the email_alias is xyz.for xyz if we want to find bigram then function should have input the email_id,and the number of grams lets say 2.
Than it has to return the distinct count of ngrams present in the email_alias.

Let's assume we have a queue named 'Demo' which receives messages from various users.

Create a Listener which will listen to the queue 'Demo' continuously and as soon as the message is send to the queue the Listener will print out the message.

The queue is running on port : 8161
Username : admin
Password : admin

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

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

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.

Given a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.?

please discuss approach first & then code it..

Design an email client where you can only send emails to people who are present in your contact list. Build for only the following functionaliy
1) Send/Receive Emails
2) Add/Remove Contacts
3) See Inbox
4) See Sent Mail

Design a distributed LRU Cache.

What would be the sample class design of notification system?