## Google Interview Questions

- 1of 1 vote

AnswersYou are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.

- ajay.raj November 13, 2017 in United States

Follow up:

What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersYou are given an arbitrary number of graphs using sets such as {a,b,c,d,a}, {a,b,a}, {e,f,g,h,e}... etc. Assume each element at position x_i in a set has a directed edge to x_{i+1}. so a-->b, b-->c etc. Write a program that selects a subset of at mot k vertices that contains at least one vertex from every directed cycle in the graph.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google - 0of 0 votes

AnswersWrite a program that always produces a two-way Euler tour that can be drawn such as it does not cross itself at any vertex.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google - 0of 0 votes

Answerslet's say you're given an arbitrary list of relations r1 and r2 from objects in a set of arbitrary size. find the size of th largest subset with the property that no two are related. for e.g., given set S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}, find the subset of S such that no two a connected.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google Trees and Graphs - 0of 0 votes

AnswersThere are n bus lines, known bus stops by bus, the bus is bi-direction, ask from station A to station B at least a few transfers.

- ajay.raj November 10, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersWrite all the possible numbers returned from a calculator pad where a start number move in a L direction in any directions(1-2moves)

- wingchuihk November 08, 2017 in United States

ie. From calculator pad. Start from 8 --> go in L shape (2up, 1right), and it returns 3

ie. Start from 2, (move 2 down, 1 left), it will be 7

ie. Start from 2(move 2 down, 1 right), it will be 9

ie. Start from 7(move 1 left, 2 up), it will be 2

ie. Start from 7(move 1 up, 2 left), it will be 6| Report Duplicate | Flag | PURGE

Google SDET Java - 0of 0 votes

Answersthe longest unique value path in a graph

- ajay.raj November 06, 2017 in United States

/**

* Definition for undirected graph.

* class UndirectedGraphNode {

* int label;

* List<UndirectedGraphNode> neighbors;

* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

* };

*/

public class Solution {

public int findLongestUniqueValuePath(List<UndirectedGraphNode> node) {

}

}| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven an array of length n + 1, containing elements 1 through n and a space,

- ajay.raj November 04, 2017 in United States

Requires the use of a given swap (index i, index j) function to sort the array,

You can only swap the gap and a number, in the end, put the gap at the end| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswerDesign a SparseVector class that implements

- ajay.raj November 03, 2017 in United States

Vector interface, which contains 4 methods: get(int index),

increment(int index, int delta), numNonZeros(), and dotProduct(Vector other)| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswerGive a vote list = [(a, 100), (b, 150), (a, 200)] # (name, timestamp) and time T

- ajay.raj November 03, 2017 in United States

Find the highest number of votes (or anyone with the highest number of votes) at T

ex: T = 100 -> a, T = 150 -> a or b, T = 200 -> a

followup1, give one more input K, find Top K votes at T

followup2, the same vote list, K, but given the Top K votes list, find the time T.| Report Duplicate | Flag | PURGE

Google SDET - 2of 4 votes

AnswerCongrats to aonecode's member F.L.

- aonecoding November 03, 2017 in United States

Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!

Thanks for sharing the interview experience with us.

Youtube Interview

- Phone: Find anagrams of string A from string B (sliding window)

- Phone: Find if two frames in a screen are equal. Frames may overlap. (equal method)

Onsite:

- LC41 first missing positive

- LC499+LC505 The maze

- LC161 one edit distance

- Similar to hangman but make guesses based on a dictionary.

Assume a dictionary has words - {house, morse, jesus} and ‘morse’ is the answer. If your first guess is ‘house’, output will be ‘_o_se’, which indicates 3 letters are correct. (Here the arrangement of letters does not matter. Your guess can be ‘co’ and if answer is ‘ok’ then the output is gonna be ‘_o’ which indicates letter ‘o’ in answer. )

Try to get the answer with minimum guesses.

(Interviewer expects pre-processing the dictionary. Key: letter; Value: frequency. Begin with combinations of most frequent letters first)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

Answers

- ajay.raj November 01, 2017 in United States`give an enum, where each element has a parent-children relationship, and children's expression is the value of parent append an index, such as enum vehicle { car = 1 toyota = 11 camry = 111 corolla = 112 honda = 12 truck = 2 GMC = 21 } Ask a value, return to his parent, such as GMC = 21, return to the truck`

| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersGiven a list points on a 2d plane, find

- ajay.raj November 01, 2017 in United States

largest rectangular area that can be formed

for the rectangle only considers those parallel to x and y| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven a set of strings (denoting URLs), like:

- lkjhgfdsa October 27, 2017 in United States

1. abc.pqr.google.com

2. pqr.google.com

3. pqr.google.net

4. yahoo.com

5. abc.yahoo.com

etc...

find an efficient way to find out how many times a particular string appears as a substring. For e.g., given the above set of strings, "google.com" appears twice; ".com" appears four times, "pqr.google.com" appears twice, and so on.

Follow up: How would you do this, if the input was no longer a URL (So, "abc.pqr.google.com" and "pqr.abc.google.com", both are valid)?| Report Duplicate | Flag | PURGE

Google Software Developer - 1of 1 vote

AnswersYou are a game developer working on a game that randomly generates levels. A level is an undirected graph of rooms, each connected by doors. The player starts in one room, and there is a treasure in another room. Some doors are locked, and each lock is opened by a unique key. A room may contain one of those unique keys, or the treasure, or nothing.

- robert October 24, 2017 in United States

Implement a representation for a level and write code that, given a level and starting room, returns true if the treasure can be reached by the player—likely requiring them to find certain other keys first—or false if there is no solution.| Report Duplicate | Flag | PURGE

Google Software Engineer Intern Algorithm - 3of 3 votes

AnswersQuestion 1.

- anonymous October 24, 2017 in India

You are given a string composed of uppercase English letters (‘A’ through ‘Z’).

Set of letters (‘A’, ‘E’, ‘I’, ‘O’, ‘U’) are called vowels. Other letters are called consonants.

We define foo value of a string as number of pairs of exactly same consecutive vowel letters.

For example,

Ex.1: BCDEEIOU - This has a foo value of 1 (because of EE). Note that although I is next to E, and O is next to I, and U is next to O, they aren’t exactly same neighbours, so they don’t contribute to foo value

Ex.2: BCDEEEIOU - This has foo value of 2. Because of first pair of EE and immediately next pair of EE

Ex.3: ABCDEFG - This has foo value of 0. There are no consecutive vowels

Ex.4: ABEUUOUOO - This has foo value of 2, because of UU and OO

You are given 2 inputs, N and K.

How many strings of length N can you form such that they all have foo value of K?

Let’s assume the constraints as:

1<=N<=15

0<=K<N| Report Duplicate | Flag | PURGE

Google Software Engineer - -2of 6 votes

AnswersHow will you test "Hello world" program?

- gagan.ping October 12, 2017 in India| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 1of 1 vote

AnswersGiven 2 words, return true if second word has a substring that is also an anagram of word 1.

- anonymous October 07, 2017 in United States

LGE , GOOGLE- True

GEO, GOOGLE - False| Report Duplicate | Flag | PURGE

Google Software Engineer - 0of 0 votes

AnswersGiven an array of strings, find out in how many cases is any of the anagrams of the string at location i, a substring of the string at location i+1.

- lkjhgfdsa September 30, 2017 in United States

Test Case I: ["ab", "ab", "abc", "bca"]

Answer: 3

Test Case II: ["ab","aqb"]

Answer: 0| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

AnswersCheck if two DOM Trees have the same text.

- wtcupup2017 September 28, 2017 in United States

e.g. <html><p>hello</p></html>, <html><p><b>h</b>ello</p></html> should be the same text

DOMNode class definition (string tag, string text, bool isText, vector<DOMNode*> children)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 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 - 3of 3 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

AnswerWrite 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

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

Open Chat in New Window