Google Interview Questions
- 9of 9 votes
AnswersQuestion was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.
- David_Maxwell November 24, 2014 in United States
Examples:
1) Pattern : "abba", input: "redbluebluered" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
Answersyou are given n-strings 1you have to find whether a chain can be termed with all the strings given number n? A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. For example you are given
- Rahul Sharma October 03, 2013 in India
number of strings = 3
first string=sdfg
second string=dfgs
third string=ghjhk
they can be concatenated as ->
second first third
dfgs sdfg ghjhk (characters at concatenation points are same)
so concatenated string is-dfgsdfghjhk| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a packed file with 1Tb of 64-bit doubles (first 8 bytes are first double, next 8 bytes are next, etc) find the exact value of median. For simplicity assume the number of doubles is odd.
- emb March 19, 2016 in United States
You can't modify the file and you have only 8Gb of free memory.
Update: you may use no more than two passes through file and your algorithm shouldn't rely on some nature of file - it should work in all cases.| Report Duplicate | Flag | PURGE
Google Software Developer Coding - 9of 9 votes
AnswersGiven a timer time() with nanosecond accuracy and given the interface
interface RealTimeCounter: void increment() int getCountInLastSecond() int getCountInLastMinute() int getCountInLastHour() int getCountInLastDay()
implement the interface. The getCountInLastX functions should return the number of times increment was called in the last X.
- peachandpotato January 29, 2014 in United States
(My note: an ideal solution will have space usage which does *not* grow unbounded with the number of calls to increment(). It seems to me that a solution involving a round-robin database could be good, but it sacrifices accuracy.)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a huge N*N matrix, we need to query the GCD of numbers in any given submatrix range(x1,y1,x2,y2). Design a way to preprocess the matrix to accelerate the query speed. extra space should be less than O(N^2) and the preprocess time complexity should be as litte as possible.
- mario87 December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 10 votes
AnswersEliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
- jeso May 18, 2013 in Switzerland
Examples:
abc -> ac
ac->''
react->rt| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 8of 10 votes
AnswersRearrange an array using swap with 0.
- cm29xm August 14, 2013 in Australia
You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt. The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list of required operations.
Practical application:
Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1. The free slot is represented by 0 in the problem. If you want to rearrange the cars, you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”.
Example:
src={1,0,2,3}; tgt={0,2,3,1};| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 10 votes
AnswersFind next higher number with same digits.
- codechamp April 02, 2014 in United States for Knowledge Graph
Example 1 : if num = 25468, o/p = 25486
Example 2 : if num = 21765, o/p = 25167
Example 3 : If num = 54321, o/p = 54321 (cause it's not possible to gen a higher num than tiz with given digits ).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Ideas - 8of 10 votes
AnswersComplete the below function which takes an arraylist and displays the list in the expected output
- AP October 07, 2013 in United States
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation(“animal”, “mammal”));
input.add(new Relation(“animal”, “bird”));
input.add(new Relation(“lifeform”, “animal”));
input.add(new Relation(“cat”, “lion”));
input.add(new Relation(“mammal”, “cat”));
input.add(new Relation(“animal”, “fish”));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 8of 8 votes
Answers1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
- Pointer January 27, 2015 in United States for Autocomplete
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.
it can be solved simply using 2 loops which takes time of O(n^2).
that's ok but how can we solve this problem in O(nlogn).
I have an approach and know the algorithm I got during the interview but it take a 40 of me to find it and write the code, but it was hard to think about it during the interview in that way.
I want to know if somebody can think and write the code in less than 20 minutes !!!| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 8of 8 votes
AnswersYou are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
- King@Work March 05, 2011
Fastest way to find that single integer
-- using memory.
-- not using any external memory.
eg: [2,1,4,5,1,4,2,2,4,1]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 8 votes
AnswersGiven the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
- azil November 28, 2013 in United States
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207| Report Duplicate | Flag | PURGE
Google Algorithm - 8of 8 votes
AnswersYou are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.
- emb September 04, 2015 in United States
A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise)
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn't cross| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 8of 8 votes
AnswersGiven an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
That is, implement the following naive algorithm faster than O(n^2)def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result
Examples:
count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([-2,5,-1], -2, 2) = 3 # [-2], [-1], [-2, 5, -1]
You may assume that there are no overflows, that is sum(|x_i|) <= MAX_INT - 1
- emb September 26, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 8of 8 votes
AnswersQ: Design a component that will implement web browser history. the user goes to different site and once he press on history button you should display the last 5 (no duplicates allowed, and 5 can be any N later) if duplicates occur display the most recent one. so if user visit : G,A,B,C,A,Y and than press "history" we will display Y,A,C,B,G. and of course he can go later to two other websites and than press "history" we will show them than the previous 3.
- Dany November 21, 2013 in United States
A: I solved it with stack, list and hash table in O(n) but it was too complicated and I didn't like my solution. please suggest something simpler.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 8of 8 votes
AnswersWrite a function which returns kth element from the tail in a linked list.
- hasan.tanpinar April 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google Intern Linked Lists - 8of 8 votes
AnswersYou are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges.
- emb April 12, 2016 in United States
You are guaranteed that such spanning tree exists.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 7of 11 votes
AnswersThe "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself.
- carchen2015 July 10, 2015 in United States
Example:
Array:
[2, 7, 5, 5, 2, 7, 0, 8, 1]
The "surpassers" are
[5, 1, 2, 2, 2, 1, 2, 0, 0]
Question: Find the maximum surpasser of the array.
In this example, maximum surpasser = 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 7of 7 votes
AnswersGiven a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.
- pennepalli May 30, 2014 in United States
Example:
Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm C# C++ Java - 7of 7 votes
AnswersGiven a number M (N-digit integer) and K-swap operations(a swap
- Rahul Sharma October 03, 2014 in India
operation can swap 2 digits), devise an algorithm to get the maximum possible integer?
Examples:
M = 132 K = 1 output = 312
M = 132 K = 2 output = 321
M = 7899 k = 2 output = 9987
M = 8799 and K = 2 output = 9987| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 7of 7 votes
AnswersGiven a very long list of URLs, find the first URL which is unique ( occurred exactly once ).
- AK December 06, 2011 in India
I gave a O(n) extra space and O(2n) time solution, but he was expecting O(n) time, one traversal.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Large Scale Computing - 7of 7 votes
AnswersDetermine minimum sequence of adjacent values in the input parameter array that is greater than input parameter sum.
- bootcat April 20, 2014 in United States
Eg
Array 2,1,1,4,3,6. and Sum is 8
Answer is 2, because 3,6 is minimum sequence greater than 8.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 7of 7 votes
AnswersYou are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome.
- um01 May 14, 2015 in United States
Expecting a O(nk) solution where n = number of works and k is length
There can be multiple pairs| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 7of 7 votes
AnswersWrite a function that gets a billion integers. How can you find the midian in most efficient way (time)?
- adam2008 February 16, 2013 in United States
same question, but the input is an endless stream of integers, and we want to find the current median.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 7of 7 votes
AnswersYou are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.
Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)
Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.
Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)
The total run-time after returning everything should be O(n).
Examples:
- djway August 10, 2016 in United StatesInput: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 7of 7 votes
AnswersGive an array A of n integers where 1 <= a[i] <= K.
- aonecoding July 12, 2018 in United States
Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.
eg. A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4
All single digits appears. Each of the 16 double digit sequences, (1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) ... appears. Because (1, 1, 2) doesn't appear, return 3.| Report Duplicate | Flag | PURGE
Google Solutions Engineer - 7of 7 votes
AnswersGiven a binary N X N matrix, return the size of the largest '+' of ones.
- zaxven August 19, 2015 in United States
input:
0 0 0 0
1 1 0 1
1 1 1 1
1 1 1 0
output:
5
(binary search is not allowed)| Report Duplicate | Flag | PURGE
Google Algorithm - 7of 7 votes
AnswersYou need to develop the game Snake. What data structures will you use? Code your solution.
- GeorgyBoy December 30, 2013 in Israel| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Java Problem Solving - 7of 7 votes
AnswersWhat is the maximum number of edges you could add to n vertexes to make a acyclic undirected graph?
- wwu November 21, 2014 in United States
Follow up:
What is the maximum number of edges you could add to n vertexes to make a acyclic directed graph?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 6of 12 votes
AnswersGiven a list of integers, find out the biggest interval that has all its members in the given list. e.g. given list 1, 7, 4, 6, 3, 10, 2 then answer would be [1, 4]. Develop algorithm and write code for this
- prongs July 08, 2013 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm Arrays C++ Coding