Google Interview Questions
- 2of 2 votes
AnswersGiven two numbers m and n, write a method to return the first number r that is
- GillY January 21, 2012 in India
divisible by both (e.g., the least common multiple)| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersMinimum number of swaps of chars in only one string to make two strings the same
- ajay.raj February 02, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersSay you have an array for which the ith element is the price of a given stock on day i.
- ajay.raj March 10, 2017 in United States
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) {
}| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersGiven a function getRandom that returns a random double in [0,1). Write a function getRandomPermutation(int n) that takes a positive integer n as argument and returns a random permutation of first n natural numbers.
- AlgoBaba November 15, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersWhat is the fastest way to compute cube root?
- Ray November 14, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersHow would you store the relations in a social network like Facebook and implement a feature where one user receives notifications when their friends like the same things as they do?
- tested.candidate July 13, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer System Design - 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 - 2of 2 votes
Answershow would you design a microwave for the blind?
- harushimo July 24, 2015 in United States| Report Duplicate | Flag | PURGE
Google Program Manager design - 2of 2 votes
AnswersWrite a function that receives three integer inputs for the lengths of the sides of a triangle and returns one of four values to determine the triangle type (1=scalene, 2=isosceles, 3=equilateral, 4=error). Generate test cases for the function assuming another developer coded the function
- Madan December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 - 2of 2 votes
AnswersHow would you tell whether a graph has a node with n degree??
- shivamdurani220 October 11, 2018 in United States
tell your approach| Report Duplicate | Flag | PURGE
Google SDE-2 - 2of 2 votes
AnswersGiven a 'friendship' graph, how would you generate friend suggestions for people, and how would you distribute the data across machines?
- nr June 04, 2013 in United States for google map| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersWhat is the difference between a computers heap and it's stack?
- brighama March 29, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Computer Architecture & Low Level - 2of 2 votes
AnswersHe showed me a game on his android phone. some sort of maze. There is ball at starting point ball can move in 4 direction at max if there is no wall. End point is hole you need to write code to solve this problem. Idea is convert it into graph and do the DFS to find the path from start to end.
- MaYanK July 29, 2010| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 2of 2 votes
AnswersGiven an infinite chessboard, find minimum no. of steps for a knight to reach from the origin to (x, y).
- neer.1304 July 03, 2019 in United States
Extension A list of forbidden coordinates are introduced where knight can’t reach. Handle this in your code. Make sure the infinite loop is handled since the board is infinite.| 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 - 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 - 2of 2 votes
AnswersWrite 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.
- vesh February 08, 2017 in Irland
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| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 2of 2 votes
AnswersDesign a graph problem, given an function getFriend(int user) which returns all the users 1st degree friends, write a function to check:
- ikf4 May 01, 2021 in India
1. whether two users are first-level, second-level and third-level connections
2. function that outputs a users 2nd degree and 3rd degree friends| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersYou have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
- neer.1304 April 21, 2019 in United States
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR| Report Duplicate | Flag | PURGE
Google SDE-2 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
AnswersPhone Interview, New Grad - Software Developer
Imagine you are given 10,000 files each containing 1 Million integers. I would you sum all of them and give the final result?
---> Interviewer wanted to test scalability, distributed concepts.
He has written the basic code and wanted to improve upon that.
Here's the basic code.public getSum(String[] file_names) { int sum = 0; for(String f: file_names) { sum = sum + sumOfFile(f); } return sum; }
Questions:
- confides123 March 25, 2017 in United States for Developer Tools
What's wrong with above code? Ans: Integer overflow
How would you implement sumOfFile?
What if 'sumOfFile' takes lot of time to finish computing?
How do you fasten the program?
Overall scalability etc| Report Duplicate | Flag | PURGE
Google Software Developer Distributed Computing - 2of 2 votes
Answersgiven two strings a and b.
- ajay.raj December 14, 2017 in United States
print out the minimum number of flips of the characters in a such
that a is an anagram of b.| Report Duplicate | Flag | PURGE
Google SDE1 - 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
AnswersSuppose I have some (lng, lat) coordinate. I also have a big list of ranges,
- Aasen November 12, 2013 in United States
[ { northeast: {lng, lat}, southwest: {lng, lat} } ... ]
How can I most efficiently determine which bucket the (lng, lat) point goes into?
Also, on a design perspective. Would it make more sense for the "list of ranges" to be on some database like mysql, monodb, or on something like memcached, redis?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 2of 2 votes
AnswersDuring boot, after the BIOS performs a successful power-on-self-test, describe everything that occurs until the console is presented to the user.
- longbelly March 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Computer Architecture & Low Level - 2of 2 votes
AnswersGiven two two integer arrays. Find the longest common subsequence.
- acoding167 May 12, 2019 in United States
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
Answers-How would you design Google Analytics (there are huge number of users and we need real-time analysis report)?
- Matt Chad January 20, 2016 in United States
-How would you detect trends?| Report Duplicate | Flag | PURGE
Google Software Engineer Large Scale Computing - 2of 2 votes
AnswersPart 1: You are given a computer #1 with array Foo, a computer #2 with array Bar and a spare computer #3. You need to apply a function F to corresponding/matching elements of the two arrays. How would you do that?
- tested.candidate March 21, 2015 in UK
Part 2: Once you scale up, how would you balance the number of machines sorting with the machines applying the function?
Part 3: What if the master (which is distributing the work) dies and never recovers?| Report Duplicate | Flag | PURGE
Google Software Engineer Distributed Computing - 2of 2 votes
AnswersGiven a kernal code in "0"th machine. How soon you can replicate the kernal across N machines. Now if the machines has upload and download bandwidth constraints, how can you impove the copy time.
- sjsu February 07, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 2of 2 votes
AnswersA mobile phone company wants to deploy network of cell towers to provide good signal coverage for its customers. But it doesn't want to have too many towers because they can interfere with one another. All towers are laid out over a 2-dimensional surface and that towers have same sized circular signal zone. You can determine whether their signal zones will overlap in 0 1) time. Give a parallel algorithm for choosing maximal subset of towers that cover non-overlapping areas.
- MaryJane August 19, 2019 in United States
I was not sure if this can be solved using DP?| Report Duplicate | Flag | PURGE
Google Software Engineer