CareerCup

You are given an array of million numbers and provided a range of index (say left, right). For multiple queries, each with input left and right indexes, output the maximum in that range.

Given (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).

We have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.

Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.

Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).

Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.

Given range of routing numbers, determine which bank it belongs to.

Ex-
I/p -(123400,123500, BOA), (12538, 12548, GCU)…

For 123450 - Output BOA
12540 - Output GCU

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"
follow up:
Given string S, find out the P (repetitive pattern) of S.

write a JSON validator

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]

Has anyone interviewed with Microsoft, Fargo North Dakota? Care to share the experience and some interview questions?

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?

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)

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 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 a List of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

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.

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.

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}