Google Interview Questions
- 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 Statesimport 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 - 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 - 0of 0 votes
AnswersGiven a large file with sentences and query string, design a system (Class, data structs, functions, etc) and algorithm to return the smallest window (start and end offsets) in the input file where the query words (in any order) are seen in the text file. What is the time complexity?
- Ray May 01, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer System Design - 0of 0 votes
AnswersGiven a binary tree, return all the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
- ajay.raj April 29, 2017 in United States/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 1 / \ 2 3 / \ 4 5 Return [4,2,1,3] and [5,2,1,3]. Public List<List<Integer>> getLongestPath(TreeNode root) { }
| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGenerate a random 4-digit even number : the adjacent 2 digits must be different.
- ajay.raj April 28, 2017 in United States
public int getNumber(){
}| Report Duplicate | Flag | PURGE
Google Software Engineer - 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 - 0of 0 votes
Answerswrite a function that randomly return a random prime 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 - 0of 0 votes
AnswersGiven a large MxN matrix of 1s and 0s like this:
1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 ...
Calculate the number of 1s in a given subset PxQ matrix. In effect, write a function:
int ones(int startx, int starty, int len, int width);
Looking for something better than O(n^2).
- dora April 27, 2017 in United States| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersFind two strings are meta string or not
- ashishsaraswat.iips April 18, 2017 in India
for eg:-
Converse
Conserve
are meta strings because if we swap s and v in the string both string will become equal. If swapping of more than one pair can be done then it is not a meta string| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersFind the median of a bst in O(n) time and O(1) space
- ashishsaraswat.iips April 18, 2017 in India| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven a count and maxvalue, write a program to return count number of unique random integers between 0 and maxvalue.
- Ray April 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answerstokenize string, "" and [] are token flags, such as
- ajay.raj April 17, 2017 in United States
mytable "foo" [bar] "" [[[[]]].
"" Turned into ",]] turned into], [[not escaped
The results of the example given above:
mytable
foo
bar "
[[]
public List<String> tokenizestring(String s){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersF (n) = 3n + 1 (if n is odd) or n / 2 (if n is even)
- ajay.raj April 16, 2017 in United States
Collapse sequence refers to each number according to this formula
until the sequence becomes equal to 1,
Find the number (which is not greater than 10000), which will have the longest Collapse sequence.
public int getlongestCollapsesequence(int n){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 2 votes
AnswersFind the Lexicographic next word of the input word from a list of words
- ajay.raj April 16, 2017 in United States
Example
Words list
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey
Input
dog
output
donkey
Can you use trie to solve it?
public String findNextWord(List<String> words, String input){
}| Report Duplicate | Flag | PURGE
Google Software Engineer - 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 - 2of 2 votes
AnswersGiven a equation in the form of "3x+4y+2=-5y+2x+10", simplify the equation to be in form "y=Ax+B", and return A,B. Also allow parenthesis to be in the equation. Ex. "3y-4x+(3-(2x-3y))=10y", result is "y =0.75 - 1.5x"
- anony-mites April 16, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 6of 6 votes
Answers5th Round
- aonecoding April 13, 2017 in United States
Open-ended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
Answerinterviewed by senior engineer
- aonecoding April 13, 2017 in United States
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
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 Algorithm - 0of 0 votes
Answerswrite a function to generate a random 4 digit unique even number, the four digits cannot be the same, 1234 is valid, but 1134 is not valid
- ajay.raj April 13, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven a list of files. Return all the unique lines from all files.
- Ray April 12, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm