## Google Interview Questions

- -1of 1 vote
You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the answer. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.

{{

Test cases

==========

Inputs:

(int list) l = [3, 1, 4, 1]

Output:

(int) 4311

Inputs:

(int list) l = [3, 1, 4, 1, 5, 9]

Output:

(int) 94311

}}

My Solution:

{{

package com.google.challenges;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

public class Answer {

public static int answer(int[] l) {

// Your code goes here.

ArrayList<Integer> list0 = new ArrayList<>();

ArrayList<Integer> list1 = new ArrayList<>();

ArrayList<Integer> list2 = new ArrayList<>();

int sum =0;

Arrays.sort(l);

for(int i = 0; i<l.length; i++){

if(l[i] % 3 == 0){

list0.add(l[i]);

}else if(l[i] % 3 == 1){

list1.add(l[i]);

}else{

list2.add(l[i]);

}

sum += l[i];

}

if(sum%3==0){

StringBuilder strNum = new StringBuilder();

for(int i = l.length-1; i >= 0; i--)

{

strNum.append(l[i]);

}

return Integer.parseInt(strNum.toString());

}else if(sum%3 == 1){

if(list1.size()>0){

Collections.sort(list1);

list1.remove(0);

}else if(list2.size() >= 2){

Collections.sort(list2);

list2.remove(1);

list2.remove(0);

}else{

return -1;

}

}else if(sum%3 == 2){

if(list2.size()>0){

Collections.sort(list2);

list2.remove(0);

}else if(list1.size() >= 2){

Collections.sort(list1);

list1.remove(1);

list1.remove(0);

}else{

return -1;

}

}

list0.addAll(list1);

list0.addAll(list2);

StringBuilder strNum = new StringBuilder();

Collections.sort(list0);

for(int i = list0.size()-1; i >= 0; i--)

{

strNum.append(list0.get(i));

}

return strNum.length() > 0 ? Integer.parseInt(strNum.toString()) : -1;

}

}

}}

But here I am able to pass 4 test cases out of 5. Therefore I am looking for scenario which is left to check.

Can someone help me?

- 0of 0 votes
On google search, how to enable key word auto completion after a few letters typed.

Follow-up: How to rank the words if they are weighted by frequency?

- 0of 0 votes
This is a two-part question.

Part one: Design one or more classes to represent the intersections and streets

in a city. Streets can be either one-way or two-way.

Part two: Using the classes from the previous question, determine whether there is a pair of intersections (A,B) such that there is exactly one route from A to B.

- 0of 0 votes
1) Finish writing the below method: bookReservation(Reservation reservation)

2) You are free to add, modify, etc the following classes and method`import java.time.Duration; import java.time.LocalTime; import java.util.List; import java.util.Map; // Your goal is to write business logic for a very simple Restaurant booking system // You are encouraged to refactor exisiting code, create other classes, write helper methods etc // You also need to make sure that the implementation works correctly class Reservation { public String name; public int partySize; public LocalTime startTime; } class Table { public int tableNumber; public int maxPartySize; } class Restaurant { public List<Table> tables; public LocalTime openTime; public LocalTime closeTime; public Map<Integer, Duration> reservationDurationsPerPartySize; // Returns a Table if Reservation could be booked, null otherwise // Booking rules: // 1) Reservation could be made only when the Restaurant is open. // 2) Only one Reservation can be seatted a Table at any time. // 3) Reservation can be seatted only at a Table of the same or a bigger size. // 4) Reservation should stay on the same Table for the whole Duration. // 5) Reservation Duration is determined by PartySize. public Table bookReservation(Reservation reservation) { //fill this method }`

- 0of 0 votes
I need to create a database that have five columns each entry is such that there can be repeated tuples in each column(No primary key).There will be no two same entries

There are 5 Methods that needs to be implemented

1. Create() - create the database

2. Add(string a,b,c,d,e) - Add single entries with 5 tuples(all strings)

3. Update (culumntype1, columnvalue1,culumntype2, columnvalue2)

- each entry having culumntype1 = columnvalue1 will be updated by columntype2=columnvalue2 and return total such eantries.

4. Delete (culumntype1, columnvalue1)

- each entry having culumntype1 = columnvalue1 will be deleted.and return total such eantries.

5. Search(culumntype1, columnvalue1)

- Search each entry having culumntype1 = columnvalue1 and return total such eantries.

How to implement in best possible way such that there can be 50,000 such entries?

- 2of 2 votes
Write a function that receives a position in 2 dimensional (x,y) array, which was initially initialized with 'o' (signals "water"), the function changes the value/state of that position to 'x' (signals "land") and returns the number of isles in the board.

For example, for 3x3 board, it will initially look like the following:

o o o

o o o

o o o

After calling the function with the position (1,2), the board will look like the following:

o o x

o o o

o o o

and the functions returns 1

An isle is defined as 'x' surrounded horizontally and vertically with 'o'

In the following board there is only one isle

o o o

o x x

o x o

- 3of 3 votes
Given a string, find the longest substring with k distinct characters.

e.g - “aaaabbbb”, k = 2, “aaaabbbb”

“asdfrttt” k = 3, “asd”, “frttt”

[Telephonic Question]

- 0of 0 votes
Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.

eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"

I was thinking of the following approach,

Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict

For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.

This should take O( N * k) where N is length of S.

- 1of 1 vote
Find all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.

You may assume the codes given is valid.

Input is a single string, e.g.

String codes =

“/* file created by aonecode.com\\n” +

“ welcome to the tech blog*/ \\n” +

“//main method\\n” +

“public static void main(String[] args) { \\n“ +

“ System.out.println(“//welcome”); //output\\n” +

“}”

Output is a list of strings

List<String> ret =

[

“ file created by anecode.com\n welcome to the tech blog”,

“main method”,

“output”

]

- 0of 0 votes
Considering a server that should ignore requests older than 1 second, create a structure to handle this behavior and give its complexity.

Use any language you want.

- 0of 0 votes
Implement, recursively, fast exponentiation and give its complexity.

Use any language you want.

- 0of 0 votes
Design the movement algorithm of a snake from snake game and give its complexity. You can base your idea of algorithm in whatever design for the game. eg. a matrix to represent the grid, use a linked list to represent the snake...

Use any language you want.

- 0of 0 votes
Create a structure to store the median of people ages and give its complexity. If keeping ordered ages, also give the insertion complexity.

Use any language you want.

- 1of 1 vote
Write a program which will bold the sub-string found in string (HTML Style).

`Example: string = "HelloWorld HelloWorld" substringList = ["el", "rl"] Make it like HTML Style:- NewString = "H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d`

But things become more tedious if

`Example: string = "HelloWorld HelloWorld AAAAAAABBBBBBBBBBCCCCCCC" substringList = ["el", "rl", "AAAA", "BBBBB", "BC", "BBC"]`

- 2of 2 votes
Phone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.

- 2of 2 votes
Q: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.

`/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……`

- 1of 1 vote
Q: List all comments in the given segment of codes. It's pretty tricky since there is a lot of things to be considered, especially the escape characters.

- -2of 2 votes
Write code to traverse a NxM matrix in a zig-zag fashion

- -1of 1 vote
Given a random string (reasonable length L), knowing all possible font sizes (e.g. font Fn has min_width, max_width, min_height, max_height), knowing fixed screen size, find the max font size that can display said string

- 0of 0 votes
Implement a2i - what are the edge cases you can think of? Signed integer only, subject to OS dependent MIN, MAX values

- 0of 0 votes
Running with Bunnies

====================

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

For instance, in the case of

[

[0, 2, 2, 2, -1], # 0 = Start

[9, 0, 2, 2, -1], # 1 = Bunny 0

[9, 3, 0, 2, -1], # 2 = Bunny 1

[9, 3, 2, 0, -1], # 3 = Bunny 2

[9, 3, 2, 2, 0], # 4 = Bulkhead

]

and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:

Start End Delta Time Status

- 0 - 1 Bulkhead initially open

0 4 -1 2

4 2 2 0

2 4 -1 1

4 3 2 -1 Bulkhead closes

3 4 -1 0 Bulkhead reopens; you and the bunnies exit

With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is [1, 2].

Test cases

==========

Inputs:

(int) times = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]]

(int) time_limit = 3

Output:

(int list) [0, 1]

Inputs:

(int) times = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]]

(int) time_limit = 1

Output:

(int list) [1, 2]

- 0of 0 votes
Random generate a NxN matrix with only four types of element: 1,2,3,4.

However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)

ex:

valid:

1 2 1 1

3 1 4 2

1 2 4 2

3 1 2 3

invalid because the first column has element 1 appears three times and all 1s are connected to each other :

1 2 1 3

1 3 4 2

1 2 4 4

2 3 2 2

- 1of 1 vote
An interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.

Follow up: Minimize steps needed.

ex:

{1 2 3 -1 4 5}

move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}

push 1 to the output list because you move car 1 to the empty spot

suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.

- -3of 3 votes
Given a string and dictionary of words, form a word by removing minimum number of characters. Characters can be removed in-order only.

- 0of 0 votes
Find longest consecutive path in a binary tree.

1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid

2. the path can be child-parent-child, not necessarily a parent-to-child path

similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/

- 0of 0 votes
Implement delete operation for N-ary tree. Your function should return a list of roots after deletion operation. Notice that your delete function only delete one node instead of a subtree. The delete function takes a list of nodes to be deleted.

`private class TreeNode { int val; TreeNode[ ] child; } List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) { }`

- 3of 3 votes
Return the length of longest possible chunked palindrome string.

Examples :

Input : VOLVO

Output : 3

Explanation :

(VO)L(VO)

Input : merchant

Output : 1

Explanation : No chunks possible.

Input :

ghiabcdefhelloadamhelloabcdefghi

Output : 7

Explanation :

(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)

- 2of 2 votes
Given a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.

Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>`-AAA -BBB -CCC -DDD -EEE`

- 2of 2 votes
As an input, you have points on a 2D graph. You aim to find a straight line that can fit as my points as possible. Return, the maximum number of points you can fit.

- 1of 1 vote
Given a pattern and a string - find if the string follows the same pattern Eg: Pattern : [a b b a], String : cat dog dog cat