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?

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 two two integer arrays. Find the longest common subsequence.
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]

Given

colors = ["red", "blue", "green", "yellow"];

and a string

str = "Lorem ipsum dolor sit amet";

write a function that prints each letter of the string in different colors. ex. L is red, o is blue, r is green, e is yellow, m is red, after the space, i should be blue.

Implement an iterator<WordAndCount> which takes iterator<String> and its next() method returns the count for same word in a row. I was also asked to implement hasNext method.

WordAndCount class had two properties:
1. Word
2. Count

I was asked to implement hasNext() and next() method which basically returns a WordAndCount object.

To make it clear, following is the example:

lets say Iterator<String> has following values:

{foo,foo,foo,bar,foo,bar,bar}

iterator<WordAndCount> next() method should return this:

{{foo,3},{bar,1},{foo,1},{bar,2}}

It seemed like an easy problem and because we ran out of time during coding i think interviewer didn't ask me the follow up question. Interviewer was nice and he told me he doesn't expect me to code in time limit but he only wants to see how i approach the problem.

Write a program to find the given new program can be scheduled or not?
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.

As the P4 overlaps with P1, So P4 cannot be scheduled.

Lonely Pixel
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))

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

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?

Given matrix in which each cell is either filled with 'C' (Computer) or empty.
Computers can communicate if they are in the same row or in the same column.
Computers can also communicate through middleware computers.
Given index of a computer, find all computers it can communicate with.
How many communication paths are there?
Find the order of turning computers off, in which every computer will manage to communicate with another computer in order to pass the data it stores before it is turned off, keeping minimum computers on in the end.

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

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)

Given a word of length n, and n six-sided dice with a character in each side, find out if this word is constructible by the set of given dice

[[2, NULL, 2, NULL], 
 [2, NULL, 2, NULL], 
 [NULL, NULL, NULL, NULL], 
 [NULL, NULL, NULL, NULL]]

What does the array look like after the corrected function has run?

":=" denotes the substitution, and "=" is the equal comparator.

========
Initial state of an array "a":

[[4, 2, 4, 2],
[4, NULL, 4, 2],
[2, NULL, 8, 2],
[16, NULL, 4, NULL]]

========
Main function:

FUNCTION foo()
   FOR y := 0 to 3
       FOR x := 0 to 3
           IF a[x+1][y] != NULL
               IF a[x+1][y] = a[x][y]
                   a[x][y] := a[x][y]*2
                   a[x+1][y] := NULL
               END IF
               IF a[x][y] = NULL
                   a[x][y] := a[x+1][y]
                   a[x+1][y] := NULL
               END IF
           END IF
       END FOR
  END FOR
END FUNCTION

What is the issue with the above code, and how would you fix it?

Given two binary trees, explain how you would create a diff such that if you have that diff and either of the trees you should be able to generate the other binary tree. Implement a function which takes Node tree1, Node tree2 and returns that diff.

Create an iterator class that stores a list of the built-in Iterators.
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators

Find whether string S is periodic.
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"

Given string S, find out the P (repetitive pattern) of S.

Given a dictionary of words & a miss-spelled input, write a function which will find 3 words from the dictionary which are closest (by difference of 1-character) to the given input.

eg - dict = {vil, sit, flick, pat, pluck, sat, vat}, input = vit, ans = {sit, vil, vat}

// For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
// For example, for K = 8 and vector [2, 4, 5, 7], the solution is 5 ([2], [4], [2, 4], [2, 4, 5], [2, 5])
The time complexity should be O(n2). Approach and code was asked