## Google Interview Questions

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

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

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

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 July 31, 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 - 1of 1 vote

AnswersGenerate a random number with UNIFORM DISTRIBUTION between [0,n) where n is given and excluded list is given. The randomly generated number should belong to the range [0, n) but should be excluded from the given excluded list. For example, n = 10 and excluded list ={2,3,0} then the random number should be from {1,4,5,6,7,8,9} such that any number from the list {1,4,5,6,7,8,9} has UNIFORM probablility of occuring

- xyz July 31, 2017 in United States for NEST| Report Duplicate | Flag | PURGE

Google Software Developer - 0of 0 votes

AnswersImplement Ring Buffer with read and write pointers.

- anaghakr89 July 26, 2017 in United States

For example if the Ring buffer is implemented in the form of array of integers , one should be able to read / write more than one integer at a time. In short the data read / written should be in a chunk .| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - 0of 0 votes

AnswersPhone 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

- mbs729 July 13, 2017 in United States

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

Google Software Engineer / Developer Algorithm - 3of 3 votes

Answers1 year exp. Interviewed at Cambridge, MA

- aonecoding July 11, 2017 in United States

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

Google Software Engineer Algorithm - 1of 3 votes

Answers - missing July 07, 2017 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Arrays - 0of 0 votes

AnswersAutomation Testing Question:

- sambenison66 July 04, 2017 in United States

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

Google Software Engineer in Test Testing - 0of 0 votes

AnswersHow 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:

- sambenison66 July 04, 2017 in United States`class Node { char val; Node next; }`

| Report Duplicate | Flag | PURGE

Google Software Engineer in Test Java - 0of 0 votes

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

- ad09 June 26, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 3of 3 votes

AnswersGoogle full-time phD candidate w/ work experience.

- aonecoding June 22, 2017 in United States

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

Google Software Engineer Algorithm - 0of 0 votes

AnswersQuestion regarding largest possible sum of subarray of size K.

- filipslatinac June 21, 2017 in Canada| Report Duplicate | Flag | PURGE

Google Algorithm - 5of 5 votes

AnswersGoogle On-site in May

- aonecoding June 15, 2017 in United States

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

Google Software Engineer Algorithm - 0of 0 votes

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

- xyz June 09, 2017 in United States for Performance Optimization Team

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

Google Senior Software Development Engineer - 0of 0 votes

AnswersFind all the abbreviations of string:

- ashishsaraswat.iips June 06, 2017 in India for AdsWorld

eg

ABC

SOME Valid abbreviations are :

1BC

2C

3

A1C

AB1

A2

NOT VALID

11C(two numbers cannot occur continuously)| Report Duplicate | Flag | PURGE

Google SDE-2 - 0of 0 votes

AnswersGiven a method

- ashishsaraswat.iips June 06, 2017 in India for AdsWorld

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

Google SDE-2 - 1of 1 vote

AnswersLast Monday phone interview of G.

- aonecoding May 27, 2017 in United States

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

Google SDE1 Algorithm - 1of 1 vote

Answerhow to keep track of the sum in a sliding window for the data that are on disk

- ajay.raj May 11, 2017 in United States

rather than memory| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersInsert 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?

- ajay.raj May 11, 2017 in United States`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)); } } }`

| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersA table has some number of balls at various positions on a line segment.

- ajay.raj May 11, 2017 in United States

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

Google SDE1

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

Open Chat in New Window