## Google Interview Questions

- 0of 0 votes
Give a Runable interface, and then give a scheduler post method. This post is parallel, for example:

Method header:

public void post (Runable r) {};

Call 5 times:

Scheduler.post (r1);

Scheduler.post (r2);

Scheduler.post (r3);

Scheduler.post (r4);

Scheduler.post (r5);

The five runables are allocated to five threads and run at the same time. And then asked: how to achieve these five tasks one by one run,

- -2of 2 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.

Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),

check whether the student qualifies for the reward.

e.g.

@INPUT (String) "OLLAOOOLLO"

@RETURN (Boolean) False

The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"

@RETURN (Boolean) True

Follow-up:

If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.

- 0of 0 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.

Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.

e.g.

@INPUT (String) "OLLAOOOLLO"

@RETURN (Boolean) False

The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"

@RETURN (Boolean) True

Follow-up:

If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.

- 3of 3 votes
Given an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.

For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20

n=23 then there are no combinations.

public boolean combinationSum(int[] nums, int target) {

}

- 0of 0 votes
Check if two given binary trees(expression trees with two characters 'a' and 'b' and obviously operators like +,-,*) are mathematically equivalent?

- 2of 2 votes
Find three non-overlap windows of size k in an int array, that together has a maximum sum

of the 3k entries.

example

int[] nums = [1,2,1,2,6,7,5,1]

k = 2

output

[1,2],[2,6],[7,5]

- 1of 1 vote
Given a list of words with lower and upper cases. Implement a function to find all Words that have the same unique character set .

For example:

May student students dog studentssess

god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice

output:

may amy

student students studentssess

dog god

cat act

tab bat

flow wolf

lambs balms

looped, poodle

- 2of 2 votes
Given an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target

public int countSubSet(int[] nums, int target){

}

- 0of 0 votes
Data structure design, N horse races, there are 10 checkpoints, whenever a horse through a check point will produce a (horse number, check point number) message, then design a data structure and algorithm to update the messages and then get the top 3 horse efficiently.

- 0of 0 votes
Input friend’s relation {{1,2}, {2,3}, {3,4}}, could you split all the users into two groups and for the user in each group, all the users do not know each other. So the expected output should be group1 {1,3}, group2 {2,4}. If it is cannot be spitted into two group, just return “impossible”

- 0of 0 votes
Given an array that contains both positive and negative integers, find the start and end index of the subarray that achieves the maximum subarray product using one pass

- 0of 0 votes
how to find leaf node value from preorder sequence of BST without rebuilding the tree

- 0of 0 votes
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times).

, but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take. However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public int maxProfit(int[] prices, int fee) {

}

- 2of 2 votes
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

, but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take.

public int maxProfit(int[] prices, int fee) {

}

- 0of 0 votes
for a binary tree, print the root to the leaf path, but add "_" to indicate the relative position.

example:`A / \ B C / \ / \ D E F G output _ _ A _ B D _A B _E A _C F A _ C _ _ G`

- 0of 0 votes
/**

* Definition for an interval.

* public class Interval {

* int start;

* int end;

* Interval() { start = 0; end = 0; }

* Interval(int s, int e) { start = s; end = e; }

* }

*/

Given a list of intervals, and a target interval

Our goal is to merge these intervals, so that the results of the merge can cover the target interval, return the minimum number of the original interval required for this merge

For example

IntervalList: [-1, 9] [1, 10] [0, 3] [9,10] [3, 14] [2, 9] [10, 16]

Target interval: [2, 15]

we find that there are several ways to cover [2,15], such as:

[-1, 9] + [9,10] + [10, 16] or [1, 10] + [10, 16].

We want to merge the least number of ways, so here should return 2

- 3of 3 votes
`/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */`

Find if a given binary tree has duplicate sub trees.

followup:

Find all duplicate subtrees in a binary tree`For example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].`

- 5of 5 votes
Paper Cut into Minimum Number of Squares

Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.

Examples:

Input : 13 x 29

Output : 9

Explanation :

2 (squares of size 13x13) +

4 (squares of size 3x3) +

3 (squares of size 1x1)=9

Input : 4 x 5

Output : 5

Explanation :

1 (squares of size 4x4) +

4 (squares of size 1x1)

geeksforgeeks provides a solution, but it is not right

http://www.geeksforgeeks.org/paper-cut-minimum-number-squares/

- 0of 0 votes
Given the weekly vacation numbers for various cities for an year (ie 12 * 4 = 48 weeks ) , design a tour which will maximize the number of vacations for a salesman. The salesman can choose to work in any city for the week , and can weekly change the city unlimited number of times , but has to remain in the city for the week . It's not necessary for the salesman to go to all cities , goal is to find the schedule which maximize the vacation for whole year. Input will be HashMap<string , int[48] vacation> where string is the city name and int[48] is city's vacation numbers for an year.

- -1of 5 votes
Create an iterator class that stores a list of the built-in Iterators.

Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).

Example:

Given a list [iterator1,iterator2, iterator3...]

when calling RoundIterator.next()

pops iterator1.next if iterator1.hasNext() is true

when calling RoundIterator.next()

pops iterator2.next() if iterator2.hasNext() is true

when calling RoundIterator.next()

pops iterator3.next if iterator3.hasNext() is true

...

when calling RoundIterator.next()

pops iterator1.next if iterator1.hasNext() is true

when calling RoundIterator.next()

pops iterator2.next if iterator2.hasNext() is true

when calling RoundIterator.next()

pops iterator3.next if iterator3.hasNext() is true

...

until there is no more element in any of the iterators

- -2of 2 votes
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?

- 1of 3 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

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

- 1of 1 vote
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.

- 2of 4 votes
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.