CareerCup

Phone interview question from January.

We have a maze with three types of spaces:
1. Walls
2. Offices
3. Hallway space

Given a maze, determine which non-wall space would minimize the sum of all distances between that space and every office. You can only move up, down, left, and right.

(Edit: ChrisK described the problem more clearly than I did: "find the field that minimizes the sum of the shortest path[s] from this field to each office space.")

Example:

WWWWWWWW
WWW O WW
WWW   OW
WWW WWWW
WO  WWWW
WWW WWWW
WO     W
WWWWWWWW

O = office, W = wall, spaces are hallway spaces

You can represent the maze however you want. That is, you can use any data structures you want, and you don't necessarily have to use O for office, W for Wall, and spaces for hallways.

(I'm not sure if you can actually start from an office space, but that should be a trivial issue because you can always just start a position adjacent to an office.)

1 year exp. Interviewed at Cambridge, MA

Round1
LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.

Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.

Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Follow-up: decode with utf-16. It took quite a while for me to understand the rules.

Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.

Automation Testing Question:
How do you verify a search result list which changes consistently based on each search word and filters?

For example, how do you make sure that the list is sorted based on price or rating or etc without any identical list to compare with? Since providing an identical list as Test Input for each word is not the best approach.

How do you reverse the words in a linked list?
For ex, Convert " H-e-l-l-o- -W-o-r-l-d " (There is a space between the word), into " o-l-l-e-H- -d-l-r-o-W "

Write a Java code to use as less Space Complexity as possible. (So not too many spaces should be used)

Linked List Structure:

class Node {
	char val;
	Node next;
}

Balance a string with parentheses. "a(b)" -> "a(b)"; "(((((" -> ""; "(()())" -> "(()())"; ")ab(()" -> "ab()"; etc...

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.

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

Make 100 HTTP GET requests to http://en.wikipedia.org/wiki/Main_Page and print the following in Java

statistics for the response time to stdout:

• 10th, 50th, 90th, 95th, 99th Percentile

• Mean

• Standard Deviation

Your solution must be parallel. You must make at least N (say 10, but should be configurable)

requests at a time.

Explain design choices, known limitations and edge cases.

What challenges did you face? How would you improve the code if you had more time?

Find all the abbreviations of string:
eg
ABC
SOME Valid abbreviations are :
1BC
2C
3
A1C
AB1
A2
NOT VALID
11C(two numbers cannot occur continuously)

Given a method
public int getOccurence(int x,int y);
where y is always a single digit number.

So find the number of occurrences of number y in the range x
E.g.
if x=25,y=2
function should return 9(as 22 contains two occurrences of 2) - 2,12,20,21,22,23,24,25

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.

how to keep track of the sum in a sliding window for the data that are on disk
rather than memory

Insert a node in a complete binary tree efficiently.
it is not BST, it is just a regular binary tree
public TreeNode insert(TreeNode root, int val){
}
this my solution using bfs (O(n) time), is there any more efficient method?

import java.util.*;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}
class Solution{
    public TreeNode insertCompleteTree(TreeNode root, int val){
        if(root == null){
            return new TreeNode(val);
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode cur = q.remove();
                if(cur.left == null){
                    cur.left = new TreeNode(val);
                    return root;
                }else{
                    q.add(cur.left);
                }
                if(cur.right == null){
                    cur.right = new TreeNode(val);
                    return root;
                }else{
                    q.add(cur.right);
                }
            }
        }
        return null;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode cur = q.remove();
                list.add(cur.val);
                if(cur.left != null){
                    q.add(cur.left);
                }
                
                if(cur.right != null){
                    q.add(cur.right);
                }
            }
            res.add(list);
        }
        return res;
    }
    public static void main(String[] args){
        Solution s = new Solution();
        TreeNode root = null;
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        for(int num : nums){
            root = s.insertCompleteTree(root, num);
            System.out.println(s.levelOrder(root));
        }
    }
}

A table has some number of balls at various positions on a line segment.
All are moving with same speed in one or the other direction.
Wherever a collision occurs they change direction.
A ball falls from the edges of the table.
Find the time when all balls fall of the table
given initial position of each ball and speeds

Suppose you have a 2-D grid. Each point is either land or water. 
There is also a start point and a goal.
There are also keys that open up doors. Each key corresponds to one door. 
Implement a function that returns the shortest path from the start to the 
goal using land tiles, keys and open doors.

Data Representation
The board will be passed as an array of chars.

A board can have the following tiles.
0 = Water 
1 = Land
2 = Start
3 = Goal

uppercase = door
lowercase = key
Example Maps (keys at each step are not required)
`No doors`
char[][] board1 = {{'0', '2', '1', '1', '1'},
				   {'0', '1', '0', '0', '1'},
				   {'0', '1', '0', '0', '3'},
				   {'0', '1', '0', '0', '1'},
				   {'0', '1', '1', '1', '1'}};
path : [0,1]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4]

`One door`
char[][] board2 = {{'0', '2', '1', '1', '1'},
				   {'0', '1', 'a', '0', 'A'},
				   {'0', '1', '0', '0', '3'},
				   {'0', '1', '0', '0', '1'},
				   {'0', '1', '1', '1', '1'}};
path : [0,1]->[0,2]->[1,2]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4]

public List<int[]> solve(char[][] board) {

Given a large file with sentences and query string, design a system (Class, data structs, functions, etc) and algorithm to return the smallest window (start and end offsets) in the input file where the query words (in any order) are seen in the text file. What is the time complexity?

Given a binary tree, return all the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
          1
         / \
        2   3
       / \     
      4   5  
Return [4,2,1,3] and [5,2,1,3].

Public List<List<Integer>> getLongestPath(TreeNode root) {
        
    }

Generate a random 4-digit even number : the adjacent 2 digits must be different.
public int getNumber(){
}

write a function that randomly return a random Fibonacci number in range [min, max)
public int getRandom (int min, int max){}

write a function that randomly return a random prime number in range [min, max)
public int getRandom (int min, int max){}

Given a large MxN matrix of 1s and 0s like this:

1 1 0 0 1 0 1
1 0 1 0 0 1 1
0 1 1 1 0 1 0
...

Calculate the number of 1s in a given subset PxQ matrix. In effect, write a function:

int ones(int startx, int starty, int len, int width);

Looking for something better than O(n^2).

Find two strings are meta string or not
for eg:-
Converse
Conserve

are meta strings because if we swap s and v in the string both string will become equal. If swapping of more than one pair can be done then it is not a meta string

Find the median of a bst in O(n) time and O(1) space

Given a count and maxvalue, write a program to return count number of unique random integers between 0 and maxvalue.

tokenize string, "" and [] are token flags, such as
mytable "foo" [bar] "" [[[[]]].

"" Turned into ",]] turned into], [[not escaped
The results of the example given above:
mytable
foo
bar "
[[]
public List<String> tokenizestring(String s){
}

F (n) = 3n + 1 (if n is odd) or n / 2 (if n is even)
Collapse sequence refers to each number according to this formula
until the sequence becomes equal to 1,
Find the number (which is not greater than 10000), which will have the longest Collapse sequence.

public int getlongestCollapsesequence(int n){

}

Find the Lexicographic next word of the input word from a list of words
Example
Words list
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey

Input
dog
output
donkey
Can you use trie to solve it?
public String findNextWord(List<String> words, String input){
}

You are given an island which contains cliffs of various heights. A water droplet is placed on one of the cliffs. The water droplet always flows from higher height to lower height. Write a program that can calculate the lowest height cliff in the island that the water droplet can reach in the most efficient way you can think of. Example: if the droplet is placed on a cliff of height 5 and it is surrounded by cliffs of heights 6,3,2,2; it can flow to either of the cliffs of height 3,2,2 and then further flow from there.