CareerCup

String1 -- "aaabb"
String2 -- "aaabbbb"
String3 -- "aaabbb"
These are sample strings. The problem stated that a given string has to be cut in such a fashion that the remaining characters in the string, say a and b have same character count. If not, then the method returns false.
In case the string already has characters with same frequency of occurrence as in case 3, then just return true. Return type can be assumed to be Boolean.

Tried to solve problem using substring() method in java by running a loop over the string, but could not arrive at a solution.

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?

It will gain you more knowledge, intensify your soft skills,strong work ethics and grow your network
What is the answer please?

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.

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.

Given an array of integers find all combination of numbers (regardless of length) that add up to a particular sum. (Subset sum problem)

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

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 an integer 'n', create an array such that each value is repeated twice. For example

n = 3 --> [1,1,2,2,3,3]
n = 4 --> [1,1,2,2,3,3,4,4]

After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value" distance from the second occurrence of the same number.

For example: n = 3 --> This is the array - [1,1,2,2,3,3]

Your output should be [3,1,2,1,3,2]

The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.

Return any 1 permutation if it exists. Empty array if no permutation exists.

Follow up: Return all possible permutations.

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.

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

There is a queue which contains some data. There are multiple applications running as distributed systems. These application reads data from the queue and stores them in the DB. But it should store the data in the same order in which it is present in the queue.

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.

it will gain you more knowledge,intensify your soft skills,strong work ethics and grow your network,what is it?

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.