Google Interview Questions
- 0of 0 votes
AnswersGiven (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).
- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersWe have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
- neer.1304 July 03, 2019 in United States
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.
Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswerSelect a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
- acoding167 June 19, 2019 in United States
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 - 0of 0 votes
AnswersGiven range of routing numbers, determine which bank it belongs to.
- neer.1304 June 08, 2019 in United States
Ex-
I/p -(123400,123500, BOA), (12538, 12548, GCU)…
For 123450 - Output BOA
12540 - Output GCU| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven two two integer arrays. Find the longest common subsequence.
- acoding167 June 02, 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 - 5of 5 votes
AnswersTree Game
- aonecode May 17, 2019 in United States
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a list of files. Return all the unique lines from all files.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerGiven a set of points, find the smallest rectangle by area.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven N shop coordinates on a 2-d plane, Find the nearest shop from a man whose coordinates are given.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGive you a text file, remove duplicated lines.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersA string consists of ‘0’, ‘1’ and '?'. The question mark can be either '0' or '1'. Find all possible combinations for a string.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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
AnswersImplement an iterator<WordAndCount> which takes iterator<String> and its next() method returns the count for same word in a row. I was also asked to implement hasNext method.
- Desi May 03, 2019 in United States
WordAndCount class had two properties:
1. Word
2. Count
I was asked to implement hasNext() and next() method which basically returns a WordAndCount object.
To make it clear, following is the example:
lets say Iterator<String> has following values:
{foo,foo,foo,bar,foo,bar,bar}
iterator<WordAndCount> next() method should return this:
{{foo,3},{bar,1},{foo,1},{bar,2}}
It seemed like an easy problem and because we ran out of time during coding i think interviewer didn't ask me the follow up question. Interviewer was nice and he told me he doesn't expect me to code in time limit but he only wants to see how i approach the problem.| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite a program to find the given new program can be scheduled or not?
- veeru April 23, 2019 in United States
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.
As the P4 overlaps with P1, So P4 cannot be scheduled.| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 1of 1 vote
AnswersLonely Pixel
- acoding167 April 22, 2019 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 - 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 - 0of 0 votes
AnswersImplement an api that let's users create multiple timers. You can only use one system timer in your implementation though. For example a user can write:
- neer.1304 April 21, 2019 in United States
timer.startTimer(3, callback)
timer.startTimer(7, callback)
timer.startTimer(1, callback)
and the user will get three callbacks 1, 3, and 7 seconds later. In startTimer you only have one timer that you call like this:
System.startTimer(seconds, callback)
but it can only be called once it has finished with the previous timer.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersBrace Expansion
- neer.1304 April 21, 2019 in United States
Given a string, perfrom the brace expansion
For example,
Input: s = "a{d,c,b}e"
output: {ade , ace , abe}| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersFind whether string S is periodic.
- aonecoding4 March 01, 2019 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersGiven a dictionary of words & a miss-spelled input, write a function which will find 3 words from the dictionary which are closest (by difference of 1-character) to the given input.
- vinzee93 February 28, 2019 in United States
eg - dict = {vil, sit, flick, pat, pluck, sat, vat}, input = vit, ans = {sit, vil, vat}| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWrite a retry function, continue to fetch data until u have exhausted max entries. If it fails, continue to retry until retry's have been exhausted.
- pri9 February 16, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Coding - 1of 1 vote
AnswersGiven two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
- aonecoding4 January 30, 2019 in United States
Follow-up: If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?| Report Duplicate | Flag | PURGE
Google Software Engineer - 5of 5 votes
Answers[Google] Design Text Editor (Doubly Linked List)
- aonecoding4 December 04, 2018 in United States
Build a text editor class with the following functions,
moveCursorLeft(),
moveCursorRight(),
insertCharacter(char) //insert the char right before cursor
backspace() //delete the char right before cursor
Follow-up
Implement undo() //undo the last edit. Can be called multiple times until all edits are cancelled.
All functions above should take O(1) time.
Example
( '|' denotes where the cursor locates. 'text' shows what's been written to the text editor. )
Start with empty text
text = "|"
insertCharacter('a')
text = "a|"
insertCharacter('b')
text = "ab|"
insertCharacter('c')
text = "abc|"
moveCursorLeft()
text = "ab|c"
moveCursorLeft()
text = "a|bc"
backspace()
text = "|bc"
moveCursorLeft()
text = "|bc" (nothing happens since cursor was on the leftmost position)
undo()
text = "a|bc"
undo()
text = "ab|c"
undo()
text = "abc|"
undo()
text = "ab|"
undo()
text = "a|"| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
Answers[Google On-site 2018 Winter]
- aonecoding4 November 28, 2018 in United States
Set Matrix Zeroes II
There are orbs on an NxM board ('O' denotes orb. 'X' denotes empty slot).
Whenever two orbs are in the same column or the same row, you get to erase one of them.
Try to erase as many orbs as possible.
Find the minimum number of orbs remained on board eventually.
e.g.
OXOXXO
XXXXXO
XXXXOX
erase (0,0) and get
XXOXXO
XXXXXO
XXXXOX
erase (2,0) and get
XXXXXO
XXXXXO
XXXXOX
erase (5,0) and get
XXXXXX
XXXXXO
XXXXOX
no more moves available. Return 2 e.g.
OXOXXO
XXXXXO
XXOXOX
erase(4,2), (2,2), (0,0), (2,0), (5,0)
Return 1
e.g.
OXOXXX
XOXXXO
XXXOOX
erase(0,0), (1,1), (3,2)
Return 3
Follow-up Build a solver for this board game that erases the as many orbs as possible.| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGiven a tree with n nodes. Each node has k coins, where 0 <= k <= n . There are total n coins on the tree.
- aonecoding4 November 18, 2018 in United States
The goal is to move the coins such that each node has exactly one coin. What's the minimum moves required?
Each move can only move one coin to an adjacent node.| Report Duplicate | Flag | PURGE
Google Software Engineer - -4of 4 votes
Answerbinary search
- James666 October 22, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 5of 5 votes
AnswersYou are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
- john August 29, 2018 in United States. - Free path/road # - Building B - Google bike Employee location - (x, y) - (1, 2) . . . . . # . . E . . # # # # # . # . B . . . . . . . . . B
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 1 vote
AnswersGiven two string check if they can be made equivalent by performing some operations on one or both string.
- alex August 09, 2018 in United States
swapEven:swap a character at an even-numbered index with a character at another even-numbered index
swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index
Given : s="cdab" , x="abcd"
s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"
Given: s="dcba" , x="abcd"
no amount of operation will move character from an odd index to even index, so the two string will never be equals
Given: s="abcd" ,x="abcdcd"
x length to big so will never be equals| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersFind all triplet that sum to a given value in an array of integers, given that the array is too big to fit into memory
- intuiti July 19, 2018 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer