## Google Interview Questions

- 0of 0 votes

AnswersGiven a target sum, populate all subsets, whose sum is equal to the target sum, from an int array.

- milincjoshi September 28, 2017 in United States

For example:

Target sum is 15.

An int array is { 1, 3, 4, 5, 6, 15 }.

Then all satisfied subsets whose sum is 15 are as follows:

15 = 1+3+5+6

15 = 4+5+6

15 = 15| Report Duplicate | Flag | PURGE

Google Software Developer - 1of 1 vote

Answerscreate a class of integer collection,

- aonecoding September 22, 2017 in United States

3 APIs:

append(int x),

get(int idx),

add_to_all(int x)，

in O(1) time。

Follow-up:

implement

multiply_to_all(int x)

e.g.

insert(1)

insert(2)

add_to_all(5)

insert(3)

get(0) -> returns 6

get(2) -> return 3

multiply_to_all(10)

insert(4)

get(1) -> returns 70

get(2) -> returns 30

get(3) -> returns 4| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersLonely Pixel

- aonecoding September 22, 2017 in United States

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))| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswersWe define the following:

- new September 22, 2017 in United States

There are friends_nodes friends numbered from 1 to friends_nodes.

There are friends_edges pairs of friends, where each (xi, yi) pair of friends is connected by a shared integer token described by friends_weighti.

Any two friends, xi and yi, can be connected by zero or more tokens because if friends xi and yi share token ti and friends yi and zi also share token ti, then xi and zi are also said to share token ti.

Find the maximal product of xi and yi for any directly or indirectly connected (xi, yi) pair of friends such that xi and yi share the maximal number of tokens with each other.

Complete the maxTokens function in the editor. It has four parameters:

Name Type Description

friends_nodes integer The number of friends.

friends_from integer array Each friends_from[i] (where 0 ≤ i < friends_edges) denotes the first friend in pair (friends_from[i], friends_to[i]).

friends_to integer array Each friends_to[i] (where 0 ≤ i < friends_edges) denotes the second friend in pair (friends_from[i], friends_to[i]).

friends_weight integer array Each friends_weight[i] (where 0 ≤ i < friends_edges) denotes the ID number of a token shared by both friends_from[i] and friends_to[i].

Note: friends_edges is the number of pairs of friends that directly share a token.

The function must return an integer denoting the maximal product of xi and yi such that xi and yi are a pair of friends that share the maximal number of tokens with each other.

Input Format

The first line contains two space-separated integers describing the respective values of friends_nodes and friends_edges.

Each line i of the friends_edges subsequent lines (where 0 ≤ i < friends_edges) contains three space-separated integers describing the respective values of friends_fromi, friends_toi, and friends_weighti.

Constraints

2 ≤ friends_nodes ≤ 100

1 ≤ friends_edges ≤ min(200, (friends_nodes × (friends_nodes − 1)) / 2)

1 ≤ friends_weighti ≤ 100

1 ≤ friends_fromi, friends_toi ≤ friends_nodes

1≤ friends_weighti ≤ friends_edges

friends_fromi ≠ friends_toi

Each pair of friends can be connected by zero or more types of tokens.

Output Format

Return an integer denoting the maximal product of xi and yi such that xi and yi are a pair of friends that share the maximal number of tokens with each other.

Sample Input 0

4 5

1 2 1

1 2 2

2 3 1

2 3 3

2 4 3

Sample Output 0

6

Explanation 0

Each pair of n = 4 friends is connected by the following tokens:

Pair (1, 2) shares 2 tokens (i.e., tokens 1 and 2)

Pair (1, 3) shares 1 token (i.e., token 1)

Pair (1, 4) shares 0 tokens

Pair (2, 3) shares 2 tokens (i.e., tokens 1 and 3)

Pair (2, 4) shares 1 token (i.e., token 3)

Pair (3, 4) shares 1 token (i.e., token 3)

The pairs connected by the maximal number of tokens are (1, 2) and (2, 3). Their respective products are 1 × 2 = 2 and 2 × 3 = 6. We then return the largest of these values as our answer, which is 6.| Report Duplicate | Flag | PURGE

Google - 1of 1 vote

AnswersSuperCity consists of a single line of n buildings, where each building i is heighti units tall; however, SuperCity is under attack by two supervillains looking to show off their superpowers! The supervillains are standing on opposite ends of the city, unleashing their powers in an attempt to destroy all n buildings. In a single move, a supervillain unleashes their power and destroys the nearest contiguous block of buildings in which the respective heights of each building are nondecreasing. In other words:

- new September 22, 2017 in United States

If a supervillain is standing on the left end of the city and the nearest intact building is building i, then performing a move will destroy each consecutive building i, i + 1, i + 2, … satisfying heighti ≤ heighti+1 ≤ heighti+2 ≤ … until there are either no more buildings in their path or there is some building j satisfying heightj > heightj+1.

If a supervillain is standing on the right end of the city and the nearest intact building is building i, then performing a move will destroy each consecutive building i, i − 1, i − 2, … satisfying heighti ≤ heighti-1 ≤ heighti-2 ≤ … until there are either no more buildings in their path or there is some building j satisfying heightj > heightj-1.

Once a supervillain destroys a building, the building's height becomes 0.

Complete the function in the editor below. It has one parameter: an array of integers, height, where each heighti denotes the height of building i. The function must return an integer denoting the minimum number of total moves needed for two supervillains standing on opposite ends of the city (as described by the array of building heights) to destroy all n buildings.

Input Format

The first line contains an integer, n, denoting the number of elements in height.

Each line i of the n subsequent lines contains an integer describing heighti.

Constraints

1≤ n ≤ 105

1 ≤ heighti ≤ 105, where 0 ≤ i < n.

Output Format

Return an integer denoting the minimum number of total moves needed for two supervillains on opposite ends of the array to destroy all n buildings.

Sample Input 0

8

1

2

3

4

8

7

6

5

Sample Output 0

2

Explanation 0

The respective heights of each building are given as height = [1, 2, 3, 4, 8, 7, 6, 5]. The supervillains can perform the following minimal sequence of moves:

Sample Case 0

The diagram above depicts the changes to SuperCity's skyline after each move by a supervillain.

In the first move, the supervillain on the left destroys buildings 0 through 4, because height0 ≤ height1 ≤ height2 ≤ height3 ≤ height4; note that the destruction stops at this point, as height4 > height5.

In the second move, the supervillain on the right destroys buildings 7 through 5, because height7 ≤ height6 ≤ height5.

As it took a minimal two moves for the supervillains to level all the buildings, the function returns 2.

Sample Input 1

6

1

2

1

2

10

9

Sample Output 1

3

Explanation 1

The respective heights of each building are given as height = [1, 2, 1, 2, 10, 9]. The supervillains can perform the following minimal sequence of moves:

Sample Case 1

The diagram above depicts the changes to SuperCity's skyline after each move by a supervillain.

In the first move, the supervillain on the left destroys buildings 0 through 1, because height0 ≤ height1.

In the second move, the supervillain on the right destroys buildings 5 through 4, because height5 ≤ height4.

In the third move, the supervillain on the left destroys buildings 2 through 3, because height2 ≤ height3.

As it took a minimal three moves for the supervillains to level all the buildings, the function returns 3.| Report Duplicate | Flag | PURGE

Google Algorithm - 0of 0 votes

AnswersFind max size of contiguous shape below, where X represents a shape and . is empty:

- steez September 21, 2017 in United States

.XXXXXX....

...X..XX..X

...XXXX....

..X.....X..

..XXX..XX..

.....XX....

/*method stub*/

public int GetMaxShape(char[][] array) {

}

i was able to come up with a recursive solution but i'd love tips on a dp solution| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswersGiven a list of rectangles, pick a random point within one of the rectangles, where the likelihood of a point is based on the area of the rectangle.

- bottomcoder September 15, 2017 in United States

There we no sample inputs and outputs that were provided.| Report Duplicate | Flag | PURGE

Google - 0of 0 votes

AnswersWrite a function to generate Random Number without using any library functions.

- CodeNinja September 15, 2017 in United States for Solutions Engineering Team

Extension: Write an overloaded method for the above function which accepts a Range.| Report Duplicate | Flag | PURGE

Google Web Developer Algorithm - 0of 0 votes

Answerstransactions = [

- Pedro September 01, 2017 in United States

{"payee": "BoA", "amount": 132, "payer": "Chase"},

{"payee": "BoA", "amount": 827, "payer": "Chase"},

{"payee": "Well Fargo", "amount": 751, "payer": "BoA"},

{"payee": "BoA", "amount": 585, "payer": "Chase"},

{"payee": "Chase", "amount": 877, "payer": "Well Fargo"},

{"payee": "Well Fargo", "amount": 157, "payer": "Chase"},

{"payee": "Well Fargo", "amount": 904, "payer": "Chase"},

{"payee": "Chase", "amount": 976, "payer": "BoA"},

{"payee": "Chase", "amount": 548, "payer": "Well Fargo"},

{"payee": "BoA", "amount": 872, "payer": "Well Fargo"},

There are multiple transactions from payee to payer. Consolidate all these transactions to minimum number of possible transactions.

HINT: Consolidate transitive transactions along with similar transactions| Report Duplicate | Flag | PURGE

Google Software Developer - 2of 2 votes

AnswersGenerate a random binary tree, with equal probability.

- pb August 30, 2017 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersYour input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.

- talal.nabulsi5 August 27, 2017 in United States

Ex:

input is {3,4,5,1} --> output: 72

input is {1,1,1,5} --> output: 15

Follow up, if there are numbers <0| Report Duplicate | Flag | PURGE

Google SDE-3 Algorithm - 0of 0 votes

AnswersToday Google phone interview I was asked to code multithreading solution to return union of two sorted arrays in java for given number of processors. Does anybody can provide a short neat code sample om that?

- marcin.jolkowsky August 26, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE-3 - 1of 1 vote

AnswersGiven an array of objects with a known set of properties , implement a function that finds all possible partial matches (one object's property value matches the same property on another object), and produce a results object that describes those matches in any format you want.

- ad09 August 23, 2017 in United States| Report Duplicate | Flag | PURGE

Google Intern Algorithm - 1of 1 vote

AnswersImplement multithreaded rm -r <folder>, i.e recursively delete files/folder under <folder> by walking through it and assume there can be billions of files under folder and you can only delete folder if all contents in it are first deleted

- Erik August 17, 2017 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - -2of 2 votes

AnswersMedian of Stream of Running Integers

- anaghakr89 August 16, 2017 in United States

Note: The integers are in particular range from 1..n

The time complexity of the code should be o(n)| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswersDesign a space shooter program .

- anaghakr89 August 16, 2017 in United States for Nest Labs

Note: The game includes spaceship , bullets and asteroids. Spaceship rotates in 180 degree generating bullets. The position of the bullets gets updated after certain time period every time . No Need to write the code for collision detection

Basic code in expected . Not the entire working code.| Report Duplicate | Flag | PURGE

Google Software Developer - 0of 0 votes

AnswersYou are in charge of a classroom which has n seats in a single row, numbered 0 through n-1.

- ad09 August 12, 2017 in United States

During the day students enter and leave the classroom for the exam.

In order to minimize the cheating, your task is to efficiently seat all incoming students.

You're given 2 types of queries: add_student(student_id) -> seat index, and remove_student(student_id) -> void.

The rules for seating the student is the following:

1) The seat must be unoccupied

2) The closest student must be as far away as possible

3) Ties can be resolved by choosing the lowest-numbered seat.| Report Duplicate | Flag | PURGE

Google Intern - 3of 3 votes

AnswersRound4

- aonecoding August 09, 2017 in United States

Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.

For example if N = 4,

Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].

[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswersRound3

- aonecoding August 09, 2017 in United States

For N light bulbs, implement two methods

I. isOn(int i) - find if the ith bulb is on or off.

II. toggle(int start, int end)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswersRound1

- aonecoding August 09, 2017 in United States

Find if two people in a family tree are blood-related.

Round2

Given some nodes in a singly linked list, how many groups of consecutively connected nodes there is.

For linked list

0->1->2->3->4->5->6,

given nodes 1, 3, 5, 6

there are 3 groups [1], [3], and [5, 6].| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersExplain the linear piecewise function.

- anaghakr89 August 09, 2017 in United States for Nest Labs| Report Duplicate | Flag | PURGE

Google Software Engineer - 1of 3 votes

AnswersThe array of integers in given . The array indicates nothing but the heights of the cylinders. The robotic arm has two ends-> left and right.

- anaghakr89 August 07, 2017 in United States

The left end points to the left end of the cylinder array and right end searched for the cylinder with least height.

ex:

array = {4,5,6,7,1,2}

left end => index 0

right end =>index 0->n giving index 4 with min height

Now the entire block is rotated by 180 degree.

now the array = { 1, 7, 6, 5, 4, 2}

now the left end moves forward.

and right end will search from left index onwards till the end of the array

so left index = 1

right index => 1-> n giving index 5 as min. height

again do the block rotate .

Write the code for this particular algorithm.

However, there is one condition

1. If there are duplicates in the array then the final order of those duplicates should remain the same.

ex. If the cylinder with height 4 is appearing at index 3 and 5 in the initial array then the cylinder at index 3 should always appear before the one at index 5 in the final array.| Report Duplicate | Flag | PURGE

Google Software Developer - 2of 2 votes

AnswersWe have N gas stations, and we are given all the distances between each pair of station. So we have nC2 distances provided to us. For example if I have 3 stations namely A, B, C the distances provided will be AB, AC, BC. We have to find the exact position of each gas station provided with these nC2 distances.

- logan9 August 05, 2017 in United States

eg. we have 5 stations so 5C2 distances are given in random order - 10, 20, 70, 80, 30, 20, 100, 70, 50, 90

Output the exact positions of gas stations A, B, C, D, E

i.e

A - 0

B - 10

C - 30

D - 80

E - 100

refer this image for more clarity

https://drive.google.com/open?id=0BxPkptdH01OBZzEwX29iRGI4cEU| Report Duplicate | Flag | PURGE

Google Software Engineer Problem Solving - -1of 1 vote

Answerscount number of combinations which are not possible.

- bit32413 August 05, 2017 in United States

There are 'n' empty slots.

A slot can be filled with 'O', 'E', or 'X'

A combination is possible if

1. 'O' s are placed in odd slot , 'E' a are placed in even slots.

2. 'O' and 'E' alternate among them,

i.e (OXOE) not allowed because between O s there is no 'E'; but (OEXXO) is allowed.

some allowed combinations

OEXXX, XXOEO, OXXEX

For 3 slots, not allowed combinations are

OXX

XXO

XEX

XXX

OXO

Only those combinations are considered in which O s and E s are in their respective odd and even slots.

i.e EEXXX will never be considered because a 'E' is in odd slot

A combination isn't allowed if 'O' is not followed by 'E' or vice versa| Report Duplicate | Flag | PURGE

Google SDE-2 Algorithm - 3of 3 votes

AnswersGiven two sorted arrays A and B. Find the first K pairs (a, b) from A and B which have the smallest sum of a & b. Supposed K is small compared to |A| x |B|

- anonymous August 05, 2017 in United States

For example:

A = [1, 2, 3, 6, 10]

B = [1, 4, 5, 7]

K = 5

Result [(1,1), (1,4), (1,5), (2,1), (3,1)]| Report Duplicate | Flag | PURGE

Google Intern - 1of 1 vote

AnswersGiven a sorted distinct array of integers and a key K. C closest elements to K are in range [L,R] inclusive, L<=R. Return L as the left index of C closest elements to K.

- anonymous August 04, 2017 in United States

For example:

A = [1, 2, 5, 8, 9, 13]. K = 8 and C = 4. The result L = 3 because 4 closest elements to 8 are [5, 8, 9, 13]| Report Duplicate | Flag | PURGE

Google Intern Algorithm - 1of 1 vote

AnswersRound 5:

- aonecoding August 03, 2017 in United States

Given a set of synonyms such as (fast, quick), (fast, speedy), (learn, study), decides if two sentences were synonymous.

(The sentences were structurally the same and has the same number of words in them.

The synonymous relation [fast ~ quick] and [fast ~ speedy] does not necessarily mean [quick ~ speedy].)

Follow-up:

If the synonymous relation passes down so that [fast ~ quick] and [fast ~ speedy] implies [quick ~ speedy], decide if two sentences were synonymous.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersRound 4:

- aonecoding August 03, 2017 in United States

Implement a class Employment with these 3 methods: assignManager(p1, p2): assign p1 as p2's manager. beColleague(p1, p2): make p1 and p2 peer colleagues. isManager((p1, p2): decide if p1 is the manager of p2.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 2of 2 votes

AnswersRound 3

- aonecoding August 03, 2017 in United States

Given a matrix of 0s and 1s where 0 is wall and 1 is pathway, print the shortest path from the first row to the last row.

Can walk to the left, top, right, bottom at any given spot.

Follow-up:

If every pathway takes a cost (positive integer) to get through, print the minimum cost path from the first row to the last row.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGoogle on-site June

- aonecoding August 03, 2017 in United States

Round 1

Leetcode 10

Round 2

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.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window