Google Interview Questions
- 1of 1 vote
AnswersSuppose you have a list of tasks which need to be executed. Some of these tasks have dependencies which must be executed before they are. Please provide a method which, when given a list of tasks, will provide a valid ordering in return.
- prasad.hybris May 02, 2018 in United States
Example:
Input: [ A, B, C, D ]
A <- B, C
B <- C, D
D <- C
Return: [ C, D, B, A ]| Report Duplicate | Flag | PURGE
Google Technical Support Engineer Trees and Graphs - 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 - 1of 1 vote
Answerswrite a function that randomly return a random Fibonacci number in range [min, max)
- ajay.raj April 27, 2017 in United States
public int getRandom (int min, int max){}| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersYou are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
- tested.candidate March 21, 2015 in Switzerland
*** SPOILER ALERT ***
The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersConsider a social network graph like facebook. You are throwing a party and want to invite some of your friends. Design a algorithm to select top n friends from m friends using the social graph.
- mandardalvi8 March 09, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 1of 1 vote
AnswersWrite a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":
- Anonymous January 27, 2015 in Israel
The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven unsorted array, find how many elements can be found using binary search
- neer.1304 April 21, 2019 in United States
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersDefine a flight class, the flight has four attributes start, end, start time and arrival time,
- ajay.raj December 16, 2017 in United States
There is also a list of strings, represents there is a crew member on that site.
given a list of flights, along with the list of strings mentioned above, asking if the flight crew availability is available for all flights.
example: flight 1 {A, B, 3, 10}, flight 2 {A, C, 1, 7}, flight 3 {C, D, 9, 11} crew member list {"A", "A"} Then return true because flight 3 can take off as flight 1 and flight 2 take off first, then flight 2 descends to bring flight crew A to C.
If flight 3 is {C, D, 6, 12} then return false because no flight crew member is in C at time 6.| Report Duplicate | Flag | PURGE
Google SDE1 - 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 - 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 - 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 - 1of 1 vote
AnswersYou are given an island which contains cliffs of various heights. A water droplet is placed on one of the cliffs. The water droplet always flows from higher height to lower height. Write a program that can calculate the lowest height cliff in the island that the water droplet can reach in the most efficient way you can think of. Example: if the droplet is placed on a cliff of height 5 and it is surrounded by cliffs of heights 6,3,2,2; it can flow to either of the cliffs of height 3,2,2 and then further flow from there.
- Saad April 16, 2017| Report Duplicate | Flag | PURGE
Google Intern Matrix - 1of 1 vote
AnswersGiven a directed graph G, duplicate the graph using minimum space.
- vgupta.2119 September 18, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 1of 1 vote
AnswersGiven a n-nary tree, check whether it is a mirror of itself (ie, symmetric around its center).
- ajay.raj January 26, 2018 in United States
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}| Report Duplicate | Flag | PURGE
Google Jr. Software Engineer - 1of 1 vote
AnswersThe grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.
Input:
In the first line you are given two numbers: the dimensions of grid - n and m. The next n lines contains m numbers. Each number is unique.
Output:
Output the most beautiful path.4 2 3 1
Return 1 2 4
- ajay.raj December 22, 2017 in United States
There are 2 ways to reach at (2,2) cell. The pathes are 4, 3, 1 or 4, 2, 1 respectively. So The most beautiful of them is 4, 2, 1 because if looking the sorted of them it looks like these : 1, 3, 4 and 1, 2, 4 respectively. So 1, 2, 4 is lexicographic smaller than the other. So the ans is 1 2 4.| Report Duplicate | Flag | PURGE
Google SDE1 - 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
AnswersSuppose you have a 2-D grid. Each point is either land or water. There is also a start point and a goal. There are also keys that open up doors. Each key corresponds to one door. Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors. Data Representation The board will be passed as an array of chars. A board can have the following tiles. 0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door lowercase = key Example Maps (keys at each step are not required) `No doors` char[][] board1 = {{'0', '2', '1', '1', '1'}, {'0', '1', '0', '0', '1'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4] `One door` char[][] board2 = {{'0', '2', '1', '1', '1'}, {'0', '1', 'a', '0', 'A'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]->[0,2]->[1,2]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4]
public List<int[]> solve(char[][] board) {
- ajay.raj May 04, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGoogle is conducting a contest where they display a special doodle to the user
- dp November 23, 2015 in India
submitting the billionth query of the day. Design a system to achieve this. (NOTE:
Google has thousands of servers and each query can hit a different server).
Optimise it. How will you handle server failures?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given printouts from an algorithm which ran over a sorted binary tree. One printout is from an in-order run and another from a pre-order run. Can you reconstruct the tree? If so, then write an algorithm.
- tested.candidate March 22, 2015 in UK| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersThere are many tourist sites and each has their own holiday. If you arrive there during the holiday, you can gain one gift. It costs you many hours Wij traveling from site_i to site_j. What's more, you can only travel once in one week. Now you are initially placed in one site, how do you plan your routine in this year to gain most gifts.
- yoyiyoshi November 14, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersDesign a web browser like Chrome with the tab functionality.
- Bevan February 15, 2013 in United States
Also describe the data structure to be used.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersCard Game
- acoding167 July 12, 2019 in United States
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 - 1of 1 vote
AnswersImplement a rate-limiter-like iterator and how to improve the space complexity
- sun2gz July 05, 2018 in United States
Given a <Word, TimeStamp> pair data type iterator as input. Implement an iterator based on it which can ignore the item if the same word has occurred in the past 10 seconds.
My implementation is to use a HashMap to memorize the word and its latest timestamp + 10s. For each new item, it will be checked against the HashMap to see if it has duplicated word occurred in the past 10s.
The interviewer asked me how to improve the space complexity if the string value varieties are infinite. He mentioned some boundary stuff.
Could anyone share some thoughts?| Report Duplicate | Flag | PURGE
Google Software Developer - 1of 1 vote
AnswersGiven Two string, ask whether they can become the same after just one swap of two chars in one string.
- ajay.raj December 06, 2017 in United States
For example:
"abcd", "bacd" Yes, you can swap ab in the first string to make it the same as the second string
"abcd", "adbc" can not
Follow-up, given Two string, ask whether they can become the same after N swaps of two chars in one string g, assuming that the swap does not overlap.
(str [0] <-> str [2] str [2] and str [0] will not be swapped with other locations)| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGive all n cities the distance between them, and then you have to follow all the cities in the order of small to large index of the city, which means you must visit the cities in ascending order, and now you can choose not to visit k cities (k < n), ask choose not to go to which k cities can make the path shortest? Return the shortest journey.
- ajay.raj November 30, 2017 in United States
int findShortestPath(int[][] matrix, int k){
}| Report Duplicate | Flag | PURGE
Google SDET - 1of 1 vote
AnswerI was asked during a virtual onsite to design a chat server. I was interviewing for a senior software engineer position. Here are some of the requirements:
- codemonkey August 11, 2020 in United States
- real time communication.
- offline handling
- multi-device supports.
Luckily, I was well prepared for system design interview questions. Thanks to system design interview - an insider's guide book on amazon and system design primer. Still waiting for the response. Wish me luck!| Report Duplicate | Flag | PURGE
Google SDE-3 System Design - 1of 1 vote
AnswerGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
- neer.1304 July 03, 2019 in United States
Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?
Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswerGiven list of schedules for different flights in a month, determine maximum number of flights that can be in the air anytime in that month.
- sanjureddy.v April 14, 2018 in United States
Input : list of schedules for flights.- spread over a month.
output: a number - maximum flights that can be in the air
Assumptions: 1. All the given times are in a specific timezone( like GMT).
2. Given Schedules can be any time in the month| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 1of 1 vote
AnswerSuppose there is a map with N bikes on it and now we have N individuals,
- ajay.raj February 01, 2018 in United States
Design an algorithm so that everyone can get the bike in the shortest distance| Report Duplicate | Flag | PURGE
Google Android Engineer