CareerCup

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.

Given a list of files. Return all the unique lines from all files.

Given a set of points, find the smallest rectangle by area.

Given N shop coordinates on a 2-d plane, Find the nearest shop from a man whose coordinates are given.

Give you a text file, remove duplicated lines.

A string consists of ‘0’, ‘1’ and '?'. The question mark can be either '0' or '1'. Find all possible combinations for a string.

Given a nxn grid with 1's and 0's find the length of largest black square formed with 1's.

So for below example:

00000
11110
01111
01110

The largest square length is 3.

With dynamic programming it can be done in O(n^2) time

It was a technical screen but it was taken in person for an event.

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.

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.

Given unsorted array, find how many elements can be found using binary search
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search

Implement an api that let's users create multiple timers. You can only use one system timer in your implementation though. For example a user can write:

timer.startTimer(3, callback)
timer.startTimer(7, callback)
timer.startTimer(1, callback)

and the user will get three callbacks 1, 3, and 7 seconds later. In startTimer you only have one timer that you call like this:

System.startTimer(seconds, callback)

but it can only be called once it has finished with the previous timer.

Brace Expansion
Given a string, perfrom the brace expansion
For example,
Input: s = "a{d,c,b}e"
output: {ade , ace , abe}

Given a rectangle with width 'W' and height 'H', you have to fit a string 'S' in it with maximum possible font size
The font size ranges from 1 to 30
You are given two APIs getCharacterWidth(char c , int font_size) and getCharacterHeight(int font_size)
getCharacterWidth(char c , int font_size): returns the width of a character for a particular font size
getCharacterHeight(int font_size): returns the height of characters for a particular font size

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?

Write a program to sort a string without using java API?
I/P : "a390testai"
O/P: 039aaiest

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