Google Interview Questions
- 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 - -4of 4 votes
AnswersFind the coordinates of the rectangle which is parallel to axis and has minimum area.
- Ray April 08, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersSuppose you have a stream of (timestamp, tag) events. You need to filter this stream (online), leaving only events with tags that haven't been already encountered in the last X seconds.
- Ray April 08, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersPeople enter and leave a room over the course of a day. Each person has a badge with a unique integer id, which is logged by the security system on enter/exit. Each log entry is an enter record (“E <id>”) or and leave record (“L <id>”) for the given badge id.
- gqian3 April 07, 2017 in United States
The room is empty at the beginning and ending of the day, and there are no other ways into or out of the room.
E: Enters the room
L: Leaves the room
Well formed log:
E 111
E 222
L 111
E 111
L 222
L 111
Question: You have a log and write a function to check is it the well formed log or not.| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersGiven a sorted array, find all the numbers that occur more than n/4 times.
- alisonlee659 March 24, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 5 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
- aonecoding March 22, 2017 in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
- aonecoding March 22, 2017 in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersFind three non-overlap windows of size k in an int array, that together has a maximum sum
- ajay.raj March 14, 2017 in United States
of the 3k entries.
example
int[] nums = [1,2,1,2,6,7,5,1]
k = 2
output
[1,2],[2,6],[7,5]| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
Answershow to find leaf node value from preorder sequence of BST without rebuilding the tree
- ajay.raj March 11, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - -2of 2 votes
Answersdeleted
- ajay.raj March 10, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
Answersfor a binary tree, print the root to the leaf path, but add "_" to indicate the relative position.
example:
- ajay.raj March 10, 2017 in United StatesA / \ B C / \ / \ D E F G output _ _ A _ B D _A B _E A _C F A _ C _ _ G
| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 4 votes
AnswersYou have L, a list containing some digits (0 to 9). Write a function answer(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the answer. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.
- Parth Patel February 21, 2017 in United States
{{
Test cases
==========
Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311
Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
}}
My Solution:
{{
package com.google.challenges;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Answer {
public static int answer(int[] l) {
// Your code goes here.
ArrayList<Integer> list0 = new ArrayList<>();
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
int sum =0;
Arrays.sort(l);
for(int i = 0; i<l.length; i++){
if(l[i] % 3 == 0){
list0.add(l[i]);
}else if(l[i] % 3 == 1){
list1.add(l[i]);
}else{
list2.add(l[i]);
}
sum += l[i];
}
if(sum%3==0){
StringBuilder strNum = new StringBuilder();
for(int i = l.length-1; i >= 0; i--)
{
strNum.append(l[i]);
}
return Integer.parseInt(strNum.toString());
}else if(sum%3 == 1){
if(list1.size()>0){
Collections.sort(list1);
list1.remove(0);
}else if(list2.size() >= 2){
Collections.sort(list2);
list2.remove(1);
list2.remove(0);
}else{
return -1;
}
}else if(sum%3 == 2){
if(list2.size()>0){
Collections.sort(list2);
list2.remove(0);
}else if(list1.size() >= 2){
Collections.sort(list1);
list1.remove(1);
list1.remove(0);
}else{
return -1;
}
}
list0.addAll(list1);
list0.addAll(list2);
StringBuilder strNum = new StringBuilder();
Collections.sort(list0);
for(int i = list0.size()-1; i >= 0; i--)
{
strNum.append(list0.get(i));
}
return strNum.length() > 0 ? Integer.parseInt(strNum.toString()) : -1;
}
}
}}
But here I am able to pass 4 test cases out of 5. Therefore I am looking for scenario which is left to check.
Can someone help me?| Report Duplicate | Flag | PURGE
Google Software Engineer Google FooBar 24x7 Google chrome technical support number 1-888-201-2039 Arrays Computer Science Java Problem Solving - 1of 3 votes
AnswerOn google search, how to enable key word auto completion after a few letters typed.
- aonecoding February 19, 2017 in United States
Follow-up: How to rank the words if they are weighted by frequency?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
- IKnowThings January 28, 2017 in United States
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
I was thinking of the following approach,
Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict
For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
This should take O( N * k) where N is length of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
AnswersFind all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
- aonecoding January 27, 2017 in United States
You may assume the codes given is valid.
Input is a single string, e.g.
String codes =
“/* file created by aonecode.com\\n” +
“ welcome to the tech blog*/ \\n” +
“//main method\\n” +
“public static void main(String[] args) { \\n“ +
“ System.out.println(“//welcome”); //output\\n” +
“}”
Output is a list of strings
List<String> ret =
[
“ file created by anecode.com\n welcome to the tech blog”,
“main method”,
“output”
]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 5 votes
AnswersPhone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.
- aonecoding January 15, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Programming Skills - 3of 5 votes
AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
- aonecoding January 15, 2017 in United States/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersRandom generate a NxN matrix with only four types of element: 1,2,3,4.
- wtcupup2017 December 30, 2016 in United States
However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)
ex:
valid:
1 2 1 1
3 1 4 2
1 2 4 2
3 1 2 3
invalid because the first column has element 1 appears three times and all 1s are connected to each other :
1 2 1 3
1 3 4 2
1 2 4 4
2 3 2 2| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersAn interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.
- wtcupup2017 December 28, 2016 in United States
Follow up: Minimize steps needed.
ex:
{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot
suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersFind longest consecutive path in a binary tree.
- wtcupup2017 December 10, 2016 in United States
1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid
2. the path can be child-parent-child, not necessarily a parent-to-child path
similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersImplement delete operation for N-ary tree. Your function should return a list of roots after deletion operation. Notice that your delete function only delete one node instead of a subtree. The delete function takes a list of nodes to be deleted.
- wtcupup2017 December 09, 2016 in United Statesprivate class TreeNode { int val; TreeNode[ ] child; } List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) { }
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.
Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>
- wtcupup2017 December 08, 2016 in United States-AAA -BBB -CCC -DDD -EEE
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first.
- jeffrey November 28, 2016 in United States
EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]
the maximum sum of the 3 numbers in the above stacks is 3+100+3=107.
Any better solution for this problem?| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 2of 2 votes
AnswersYou are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.
- camiloni42 November 19, 2016 in United States
When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.
Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).
This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a list of coin values, and quantity of each type of coin. Write a
- snakeonbasket November 18, 2016 in United States
program to return the set of all possible sums which can be made using those
coins.
ex. coins = [10, 50, 100, 500]
quantity = [5, 3, 2, 2]
sum could be 400 , 300 ,200 , 100| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerWrite a function that compares Spanish strings, how would you handle special cases like 'ch' ?
- Gear November 17, 2016 in United States
c < ch < d, ch will be represented as 2 ASCII characters| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven 'n' circles (each defined by center and radius)
- sheva November 12, 2016 in United States
Write an algorithm to detect if circles intersect with any other circle in the same plane
Better than O(n^2) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersReturn the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}
- umesh.shaw November 11, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 1of 1 vote
AnswersGiven the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village.
Eg.# # # # # # # A # # B # # # # # # # C # # # # # #
# -> represents the bushes
- angry_scorpion November 10, 2016 in United States
A, B, C -> position of houses
I provided a O(n*a*b) approach, where n-> no. of houses , a,b->dimensions of the grid.
The interviewer asked me for some special cases. Can it be done more efficiently?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 3 votes
AnswersCreate a function to calculate the height of an n-ary tree.
- theNightsKing16 November 03, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Trees and Graphs