Google Interview Questions
- 1of 1 vote
AnswerGiven an array, find the number of tuple such that A [i] + A [j] + A [k] = A [l] in an array, where i <j <k <l.
- ajay.raj January 26, 2018 in United States| Report Duplicate | Flag | PURGE
Google Data Engineer - 1of 1 vote
AnswerYou are in the upper left corner, sitting in a boat, you want to reach to the lower right corner, but the matrix has a certain height at each location (i, j), and the boat can only go through the cell with water in it, looking for the earliest time that the boat can reach from the upper left corner coordinates (0,0) to the lower right coordinates (n-1, n-1). Each day, water goes up by one height unit
- ajay.raj December 03, 2017 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - 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 - 1of 1 vote
Answerdef inc:
- sunshihaosd February 09, 2014 in United States
while True:
v = v + 1 //---A
set(s) // ---B
def disp:
while True:
wait(s) //---C
print v //----D
print all possible value, which is shared value. At the begin , v = 0
s is binary semophore. initial value is 0| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 1of 1 vote
AnswersThe difference between move and forward in C++
- parni November 01, 2018 in United States| Report Duplicate | Flag | PURGE
Google C++ - 1of 1 vote
Answersgiven n player competition, a bool canbeat (int a, int b) can return a whether beat b. Asked to return a sequence, the sequence only requires two adjacent to the front beat behind. Example, 1 beat 2, 2 beat 3, 3 beat 4, 3 beat 1, 4 beat 1 You can return "1234", that is, although 3,4 can beat 1, but not adjacent does not matter
- ajay.raj December 19, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGive a bunch of rectangles, randomly return a point within the rectangle, the probability to be proportional to the size of the rectangle.
- ajay.raj December 15, 2017 in United States
Follow up1: If you want to repeatedly call the function to generate random points how to do.
Follow up2: If the rectangles overlap how to do?| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven a function randBetween (double d1, double d2), return a random double between d1 and d2,
- ajay.raj December 06, 2017 in United States
returns a random point in a rectangle.
Give a bunch of rectangles, using randBetween to print a random point in the rectangle
follow up: What to do if you call this func many times| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersHave you ever faced a time when you felt a particlar code base or product was not ready to be released, if so what did you do and how did you work with the development team or stakeholder to make sure your views were heard
- TheShocker1999 December 15, 2015 in United States| Report Duplicate | Flag | PURGE
Google Developer Advocate - 0of 6 votes
AnswersHow to find if a number is power of 4 in O(loglogn).
- AVK October 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 6 votes
AnswersGiven a very very very large integer(with 1 million digits, say), how would you convert this integer to an ASCII string
- Ravi January 24, 2013 in United States for youtube| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C - 0of 6 votes
AnswersThere are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0.
Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'.
Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves.
Input Format:
N -number of leaves
A - Given array of integers
Output Format:
An integer denoting the number of uneaten leaves.
Sample Input:
N = 10
A = [2,4,5]
Sample Output:
4
Explanation
1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.
Java Code:
- balakrishna.pininti September 09, 2014 in United Statespublic class Solution { //need to complete the function below static int countUneatenLeave(int N, int[] A { } public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); final String fileName = System.getenv("OUTPUT_PATH"); BufferedWriter bw = new BufferedWriter(new FileWriter(fileName)); int res; int _N; _N = Integer.parseInt(in.nextLine()); int _A_size = Integer.parseInt(in.nextLine()); int[] _A = new int(_A_size]; int _A_item; for(int _A_i = 0; _A_i < _A_size; _A_i++) { _A_item = Integer.parseInt(in.nextLine()); _A[_A_i] = _A_item; } res = countUneatenLeaves(_N,_A); bw.write(String.valueOf(res)); bw.newLine(); bw.close(); } }
| Report Duplicate | Flag | PURGE
Google SDE1 Developer Program Engineer Algorithm - 0of 6 votes
AnswersGiven a set of intervals (time in seconds) find the set of intervals that overlap. Follow-up: what if we were to find the interval with maximum overlap.
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 6 votes
AnswersHow does a search engine perform exact phrase search? i.e. search for the term "the bees knees" exactly.
- sarasaurus August 24, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Distributed Computing - 0of 6 votes
AnswersCreate an iterator class that stores a list of the built-in Iterators.
- aonecoding February 27, 2017 in United States
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 4 votes
Answersi18n (where 18 stands for the number of letters between the first i and the last n in the word “internationalization,”) Wiki it.
- Gcrack May 22, 2015 in United States
Generate all such possible i18n strings for any given string. for eg. "careercup"=>"c7p","ca6p","c6up","car5p","ca5up","care4p","car4up","caree3p","care3up"..till the count is 0 which means its the complete string again.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays - 0of 4 votes
AnswersGiven a matrix of size N*N and a starting point "s" in the matrix which represents a color.
Find the area of the shape represented by the color of the starting point "s".
Note 1: A shape can be anything as long as it is connected, e.g. a square, a circle, a doughnut or a line.
Note 2: It is only a shape if they are connected from the starting point.
Note 3: Connected means, adjacent and the same color.
E.g.zero based index. Starting point = top left "R" [3][2], color = R, area = 10 000000000 000000000 000000000 00RRRR000 00R00R000 00RRRR000 000000000 000000000 000000000
Update: OK as requested further clarifications, a cell is only a single color, it is a matrix and contains
a single value stating the color of the cell. Think of each cell as a pixel and each pixel represents a length of 1.
The shape above has an area of 10, because that it is not a regular square but has two holes in the middle, if you do it mathematically:
(3*4) - (1*2) = 10 or simply by visually counting the R squares.
You are not trying to create shapes, you are using the starting point "s" to find the complete shape (traverse the matrix until you have found all connected pixels) and calculate the area.
If you need more clarification I can try but I think that should clarify.
State your Time and Space complexity of your algorithm.
Consider also this:0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 00RRRR0000000 00R00R000RR00 00RRRR000RR00 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 zero based index. Starting point s = top-left "R" [5][2], area = 10.
In the above case, the other shape, same color is not connected to the shape specified by the starting point, hence is not part of the area calculation.
- DotQ May 09, 2014 in United States
Apologies for the formatting.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 4 votes
AnswersFind the n-th smallest multiple given a set of numbers. For example, set = {4, 6}, n = 6:
- supatroopa December 12, 2015 in United States
The sequence is:
4, 6, 8, 12, 16, 18, etc...
Answer is 18| Report Duplicate | Flag | PURGE
Google Algorithm - 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 - 0of 4 votes
AnswersFinding a pair of elements from two sorted lists(or array) for which the sum of the elements is a certain value. Anyway solution that can do better than O(a.length + b.length)?
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 4 votes
AnswersYou have a bunch of light bulbs. Store them as you wish. Implement a function that tells you if the light is on or off given its index and another one that toggles the state of the light bulbs given a start and end index.
- ad09 August 09, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 4 votes
AnswersGiven a range of floats, find the range of size 1 with max num of elements
- aj June 09, 2015 in United States
for eg: [-13.7, -14.5, -12.3, -12.5, -12.9]
one possible answer: [-12.3, -13.3]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 4 votes
AnswersGiven an array of n elements (a1,a2,..ai,...,an). You are allow to chose any index i and j, such that (i!=j) and allow to perform increment operation on ai = ai+1 and decrements operation on aj = aj - 1 infinite number of times. How many maximum number of elements you can find that have same number.
- smit February 14, 2014 in India
example 1:
1 4 1
ans: 3
example 2:
2 1
ans : 1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 4 votes
AnswersYou have been given a series of 'n' numbers and the series is in a random order. Write a program to find the median of the series with minimum complexity.
- Purushotham Kumar October 05, 2013 in Canada for Graduate Recruitement Team| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Java - 0of 4 votes
Answersyou have a stream of bytes (1010101101011110100010......)to send over the net. but if you compress it. you will be charged less for less data usage. please try to compress it in a way that you can decompress at other end ahd you dont loss data
- coinsofakshay May 11, 2015 in United States| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 0of 4 votes
AnswersYou are currently in practice mode. This is a demo only.
- New Grad July 30, 2016 in United States
A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 8 elements:
A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:
A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.
P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function:
int solution(int A[], int N);
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 4 votes
AnswersProblem Link:https://code.google.com/codejam/contest/4214486/dashboard#s=p1
- codingfunnyguy September 18, 2014 in United States
At new years party there is a pyramidal arrangement of glasses for wine. For example, at the top level, there would just be one glass, at the second level there would be three, then 6 and then 10 and so on and so forth like the following image
.
The glasses are numbered using 2 numbers, L and N. L represents the level of the glass and N represents the number in that level. Numbers in a given level are as follows:
Level 1:
1
Level 2:
1
2 3
Level 3:
1
2 3
4 5 6
Level 4:
1
2 3
4 5 6
7 8 9 10
Each glass can hold 250ml of wine. The bartender comes and starts pouring wine in the top glass(The glass numbered L = 1 and N = 1) from bottles each of capacity 750ml.
As wine is poured in the glasses, once a glass gets full, it overflows equally into the 3 glasses on the next level below it and touching it, without any wine being spilled outside. It doesn't overflow to the glasses on the same level beside it. It also doesn't overflow to the any level below next level (directly).
For example: When the glass of L = 2 and N = 2 overflows, the water will overflow to glasses of L = 3 and N = 2, 4, 5.
Once that the bartender is done pouring B bottles, figure out how much quantity in ml of wine is present in the glass on level L with glass number N.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three integers, B, L, N, B is the number of bottles the bartender pours and L is the glass level in the pyramid and N is the number of the glass in that level.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the quantity of wine in ml in that glass.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 4 votes
AnswersTake an example of the traditional Iterator interface which has the following methods
- lks May 17, 2016 in United States
Interface Iterator<E>{
public boolean hasNext() {}
public E next() {}
public E remove() {}
}
You are given a list of iterators. You have to design a InterleaveIterator class which implements this
interface and implement the methods:
hasNext() and next()
such that these 2 methods returns interleaved values for the list of iterators:
Implement:
class InterleaveIterator<E> implements Iterator<E>{
@override
public boolean hasNext() {}
@override
public E next() {}
}
Example:
ArrayList<Integer> i1 = [1,2,3,4,5].iterator()
List<Node> i2 = [n1,n2].iterator()
Collection<E> i3 = [e1,e2,e3].iterator()
next() method of InterleaveIterator, should return in this sequence [1,n1,e1,2,n2,e3,3,e3,4,5]
Make this InterleaveIterator class generic and make sure that the class can accept a list of iterators
and interleave them| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 4 votes
AnswersDesign Short URL. (I am not sure what it even means)
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design