CareerCup

Design an algorithm that provided your current location and a list of ATMs locations in the area, get you the closest K ATMs to your location.
Assume you have a method getDistance(a, b) that calculates the distance between a and b.

Follow Up:
Make your solution O(k) space and O(n) time

Design an algorithm to find the shortest substring in a synopsis such that it contains all the words in a provided list.

So, search for the shortest substring that contains ['Hello', 'World'].

Google full-time phD candidate w/ work experience.

Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?

Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)

Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.

Q4.
Design merchandising product data storage service

Question regarding largest possible sum of subarray of size K.

First asked how you can write a tree in a file?
Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d

Google On-site in May

Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x)，//add x to all numbers in collection
These methods should run in O(1) time.


Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time

There are around 40 million files in a directory which needs to be transferred to another system via FTP in order of oldest file first. What's the ideal way to iterate over files and store it in a data structure from where it can be transferred?

Coding I
Flatten a linked list.
Each node in the list carries a piece of data and a pointer. The data could be in a normal data type such as an integer, or a pointer that points to another list node.

The interviewer gave no specification on how the list node class was defined. You may look at each list node as if it has two pointers - one of them points to the next node; the other points to the ‘data’ which could be either a node or an integer. There also needs to be a function to tell you about the node data is actual data or a pointer.
I solved the problem with recursion. During the process, any nodes that don’t carry an integer get removed.

Given a m x n array filled with 1's & 0's. Find all the rectangles which are filled with all the 1's.


Note : - It is guaranteed that there won't be any overlapping rectangles.

Find Famous person in the list of persons.

A person is a famous person if he doesn't know anyone in the list and everyone else in the list should know this person.

The function isKnow(i,j) => true/ false is given to us. No need to worry about it.

Goal is to find the famous person in O(n) complexity.

Given a stream of objects, O1, O2, O1, O3, O4... Provide an algorithm to identify the first unique object at any given point in time.

So for example, in the above, after receiving the first Object, it is unique. After receiving the second, the first is still the first unique object. After receiving the 3rd, the 1st object is no longer unique (you've not seen O1 twice), so O2 is not the first unique object. etc...

FB on-site two weeks ago last round of coding . (This problem is also in the internal question bank of G.)

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.
You have a remote that could walk the robot into any of the four directions - up, left, down or right.
Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.
Otherwise returns true and the robot moves on to the direction given.
Find out the area of the room.


e.g.
X
XXX X
XXXXX 'X' marks the floor plan of the room.

A room like such has an area of 10.

Last Monday phone interview of G.

Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.

Find the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"

Find if a mathematical string is balanced in terms of parenthesis. For example "(1+2)" is balanced and "(1+2" is not balanced.

You have a array with integers:

[ 1, -2, 0, 6, 2, -4, 6, 6 ]

You need to write a function which will evenly return indexes of a max value in the array.
In the example below max value is 6, and its positions are 3, 6 and 7. So each run function should return random index from the set.

Try to implement with O(n) for computation and memory.
Try to reduce memory complexity to O(1).

The number of valid combinations of a strings for given input array a[], where a=>1, z => 26, and 0 <= a[i] <= 9

{1,1,1} => {aaa, ak, ka} => 3
{1,1,0} => {aj} => 1

/* The objective of this exercise is to build a road network connecting every pair of cities.
Each city should be connected to each other city once.
*/
public class Program
{
/* Your function RoadBuilder should return a list of new roads required to be built,
if the existing roads are given by builtRoads and the total number of
cities is nCities. Roads should not connect cities to themselves.
*/
public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)
{
//implement the function here
return new int[0][];
}

public static void Main()
{
int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};
Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}
}
}

There are three row of houses. There are N houses in each row. Each house can be painted with three colors: red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses with following constaints

No two adjacent houses in a row have the same color.
Houses in a column have three different colors
You have to paint the houses with minimum cost. How would you do it?

Note: The cost of painting house 1 red is different from that of painting house 2 red in any row. Each combination of house and color has its own cost.

Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)
Node restore(List<Integer> list)

Example Tree:

5
/ \
3 2
/ / \
1 6 1

You are given set of strings, You have return anagrams subsets from it. An anagram set is that one where every string is an anagram of another string. If the subset contains only one string, don't include that in the result.

You are given a NxN boolean matrix, where matrix(i,j) will be one if 'i' is a parent of 'j' in a tree, otherwise, it is zero.
Construct this tree.

Design/Implement an LRU cache so that Read/Write/Find operation only takes constant time.

Now, Let's say, we will be considering the frequency as well. It means to keep the most used processes and in a case of the tie, use lease recently used to remove an element.

Now, as this new algorithm can cause many hits, or no new process will come to the cache if the last process of the cache has two hits., What can you do to prevent this, and how would you implement that.

Apple On-site at Cupertino
Team Data Warehousing

III. Given three letters ABC, where AB->C, AC->B, BC->A (sequence doesn’t matter). Get the length of the path to convert from a given string to a single character.


For example, “ABACB” goes to “ACCB” (based on AB ->C, convert s[1] and s[2] to C)
“ACCB” goes to “BCB” (based on AC->B)
“BCB” goes to “AB”
“AB” goes to “C”
So it takes 4 steps to change the given string into a single character.
If a given string cannot be resized to 1 character, such as “AAA” or "ABACABB", return -1.

Apple On-site at Cupertino
Team Data Warehousing

There were 6.5 rounds in total, that 0.5 on package negotiation with the HR and the remaining rounds with 2 managers and 4 engineers.

Only three pure coding questions were asked.
I. Use a stack to sort given data.

II. Given an array with positive integers only, find the MIN integer that is missing from the array.

You are given an array of values, (not necessary integers or positives) and a value. You have to print all the pairs whose sum is given value. Write a general method which can accept integers, float, doubles, long, or any other thing where this make sense.

You are given an array of stock prices, You have to return maximum profit one can make when buying once and selling once. Consider, you are buying one stock only.

You are given set of strings, you have to print out the could of each distinct patterns. Please consider anagrams as same pattern and even the char count does not matter.
Ex:

abbba
ab
ba
abcd
abdc
adbc
aabddc

output:

ab: 3
abcd: 4

Implement pow(x, n)

Pick three numbers a, b, c from an array of integers to get the maximum product a * b * c.

Began with the O(N^3) solution. Then the interviewer give clues on optimization by sorting the array.