Google Interview Questions
- 1of 1 vote
AnswersYou are given a large string. You need to cut the string into chunks such that each substring that you get is a palindrome. Remember that each 1 length string is always a palindrome. You need to find the minimum number of cuts that you need to make such that each substring is a palindrome.
- AL May 06, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersYou have to paint N boards of length {B1, B2, B3… BN}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
- xyz April 01, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answersimplement your own malloc and free for application x, which should control the heap memory usage of the application x.
- geek August 18, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C - 1of 1 vote
AnswersConvert a doubly linked list to a binary search tree in place.
- Anonymous October 14, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersValidate whether given string is valid JSON fromat string or not.
- siva.sai.2020 November 26, 2015 in India
I/P: {a:b}
O/P: Yes Valid JSON
I/P: {a:b, c:d}
O/P: Yes Valid JSON
I/P: {a:b,c:{e:f}}
O/P Yes Valid JSON
I/P: {a}
O/p: not a valid json
I/P: {{a}}
O/P: not valid JSON| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersRahul is playing a very interesting game. He has some N different type of match boxes. All match boxes may have different number of matchsticks (S1, S2, S3... Sn).
- Avinash Paritala November 19, 2015 in India
Rahul chooses two random numbers F and K. K should be less than N. The game is that Rahul wants to select any K match boxes out of N match boxes such that total number of matchsticks in these K selected match boxes should be multiple of F.
At the sametime Rahul wants that sum matchsticks of all the selected match boxes should be minimum possible.
Input Specifications:
1) Array S = {S1,S2,S3,...Sn} of size N corresponding to the number of match sticks in N matchboxes(0<=N<=1000}
2) F-Value (as explained above)
3) K-Value ( as explained above)
Output:
1 2 3 4 5 Here 3 is the number of matchsticks in matchbox I II III IV V minimum possible total number of matchsticks such that the conditioned explained in the problem statement is satisfied. Output -1 if it is not possible or invalid input.
For example, there are 5 match boxes i.e., N = 5
Let's say K is 3 (Rahul has to choose any 3 matchboxes)
Let's say F is 5(sum of matchsticks in 3 selected matchboxes should be multiple of 5).
Rahul can choose II, III and V matchboxes which would give the total sum of 10 which is multiple of F i.e., 5. And 10 is the minimum possible matchsticks possible in the above case.
So you have to answer the minimum possible matchstick(sum of the matchsticks in the selcted matchboxes) but the conditions given above should be satisfied.| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersWrite all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity
- dev123 August 24, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersWrite a program in that determines the members and parents of nested groups without using recursion.
These are the requirements.
1. A group can have 0 or more members.
2. A group can be member of one or more groups
3. A group can be member of itself.
4. If there is a path from a group either directly or through multiple hops, then that user is considered as member of the group.
5. A group can have users or groups as members
EX: Input looks like thisvar groupMembers = new Dictionary<string, HashSet<string>> { { "G4", new HashSet<string> { "U1","G1"} }, { "G1", new HashSet<string> { "G2","G3","G6"} }, { "G3", new HashSet<string> { "G3","G5"} }, { "G2", new HashSet<string> { "G4","U2"} }, { "G5", new HashSet<string> { "U2","G6"} }, { "G6", new HashSet<string> { "U3"} }, };
Signature of function is:
private List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
You need to make sure that you take care of cycles in the graph and not go into infinite recursion.
Output should look like a list of groups where a group is as follows.private class MyGroup { public string Identity { get; set; } public Dictionary<string, MyGroup> MemberOf { get; set; } public Dictionary<string, MyGroup> Members { get; set; } public HashSet<string> Users { get; set; } public MyGroup(string name) { this.Identity = name; this.MemberOf = new Dictionary<string, MyGroup>(); this.Members = new Dictionary<string, MyGroup>(); this.Users = new HashSet<string>(); } }
Each group object should contain all the groups it's a memberOf (directly or indirectly), all the groups that are it's members (directly or indirectly) and all users that are it's members.
- enok July 23, 2015 in United States| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersYou are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed).
- Anonymous January 27, 2015 in Israel
Return the number of sequences of elements (groups of consecutive elements), pointed by the array.
For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2.
Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 1of 1 vote
Answershow will you test if the random number generator is generating actual random numbers
- Tester August 09, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Testing - 1of 1 vote
AnswersYou are given a matrix of size M rows and N columns. A is the first element i.e. mat[i][j] where i=j=0, and B is the end point i.e. i=M and j=N. There is a robot at A and it can only move one step right or go down one step. There are walls in the matrix denoted by X. The robot cant make his move when it encounters a wall on right or on its way down. Find the number of paths from starting point A to the end point of the matrix B for the robot.
- Punit2012 April 30, 2010
hint:recursion with condition checking for the end point and the wall.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite code to compare two arrays if they contain the same elements
- AM January 13, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 1of 1 vote
AnswersFind a counter example proving that the following substring algorithm is incorrect:
- awayes October 20, 2015 in United Statesconst char* findSubstr(const char* str, const char* substr) { int len = strlen(str); int substrlen = strlen(substr); int j = 0; const char* result = NULL; for (int i = 0; i < len; ++i) { if (str[i] != substr[j]) { j = 0; result = NULL; } else { if (j==0) result = &str[i]; ++j; if (j >= substrlen) break; } } return result; }
| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersYou have two sorted list. Write code for returning the first k elements. K may be a large number like 10 million.
- hirajhil February 05, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 1of 1 vote
AnswersYou are given a 2-Dimensional array with M rows and N columns. You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1's and 0's. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through the cell. Given a function numberOfPaths which takes in the above 2-D array, return the number of paths from the top-left cell to the bottom-right cell (i.e. (0,0) to (M-1,N-1)).
- Madan January 27, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven an extremely large file that contains parenthesis, how would you say that the parenthesis are balanced?
The file cannot fit in the memory. How would you process the file and how would you store the intermediate results.
Walk me through the entire algorithm.
- CodeNinja December 14, 2017 in United StatesExamples: {[()]}, {[](){}}, [] are some valid examples.
| Report Duplicate | Flag | PURGE
Google Software Engineer Stacks - 1of 1 vote
AnswersWrite a program which will bold the sub-string found in string (HTML Style).
Example: string = "HelloWorld HelloWorld" substringList = ["el", "rl"] Make it like HTML Style:- NewString = "H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d
But things become more tedious if
- rasmiranjanbabu January 24, 2017 in United StatesExample: string = "HelloWorld HelloWorld AAAAAAABBBBBBBBBBCCCCCCC" substringList = ["el", "rl", "AAAA", "BBBBB", "BC", "BBC"]
| Report Duplicate | Flag | PURGE
Google Software Analyst Algorithm - 1of 1 vote
AnswersGiven a 2D matrix of integers, sort it such that:
- every row is sorted in ascending order from left to right
- every column is sorted in ascending order from top to down
- all items in the same row are unique
You may assume the input matrix is always valid, meaning that such a sort is always possible.
For example:
for input matrix1 3 5 3 2 4
the output could be any of the following:
valid output #1:1 3 4 2 3 5
valid output #2:
1 2 3 3 4 5
valid output #3:
1 3 4 2 3 5
One kinda trivial solution is to sort the 2D matrix column wise. For example, you can push all items into a heap and pop one after another, putting it into the matrix column after column. This would be a `O(n lg n)` time complexity where `n` is the number of items in the matrix, i.e., `n = rows*cols`. Can you design a more efficient algorithm?
- zhtt2009 February 29, 2016 in United States
Follow-up: What if all items in the same column are also required to be unique?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersDesign a cache module for an image server. The server accepts image requests from users and sends them back the images. The cache should always hold in-memory the 10 most recently requested images. The cache should also support multiple requests simultaneously
- assaf.keret1 June 28, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Coding - 1of 1 vote
AnswersThe third question is a brain teaser: if 1000 couples are to give birth to male and female babies(50% change each), and they would keep giving birth until they have a girl, what's the boy to girl ratio in 20 years
- fenghanlu October 30, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
Answers|_|
- NaiveCoder February 24, 2012 in India
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|
Each cup has capacity C and once a cup gets full, it drops half extra amount to left child and half extra amount to right child
for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C) will be divided equally to left and right child cup of next level
i.e. C/2 to left child and C/2 to right child
Write a function which takes input parameter as amount of liquid poured at top (L) and height of particular cup (h) index of that cup (i) and it should return amount of liquid absorbed in that cup.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersThere were 3 racers A, B and C. When A finished the race, B was 8 mts behind A and C was 16 mts behind A. When B finished the race, C was 10 mts behind B. Assuming that three of them ran at constant speed, find the length of the track.
- Samwise August 09, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Brain Teasers - 1of 1 vote
AnswersLet's say I have a word "I love chicken", I can break the number of characters in each word, like so: [1] [4] [7]
- J@sper October 11, 2016 in United States
[1,4] [4,7], [1,4,7].
Now let's say I have a max = 5. The phrases with equal or fever than 5 characters are "[I], [love], and [I, love]. The longest phrase is [I,love], which contains 2 words.
Complete the Length function given. It has 2 parameters:
1) An array of integers, named array
2) A maximum number, named max.
int Careercup( int [] array, int max) {
}
Example test case 1:
[3,1,2,3]
4
Output expected : 2| Report Duplicate | Flag | PURGE
Google Software Developer Arrays - 1of 1 vote
AnswersGiven a BST with unique values find in a given tree a value closest to a given value X.
- tested.candidate July 14, 2015 in Poland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersHow would you optimize an elevator system for a building with 50 floors and 4 elevators ? Optimize in terms of lowest wait times for the users. Nothing related to power consumption.
- tbag March 08, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer System Design - 1of 1 vote
AnswersWrite a class DominoChecker that has a method called addBox(int[]) that takes a box of five dominoes, described as a list of 10 integers (explained after), adds it to a collection, and returns true if a box with the same dominoes was already in the collection and false otherwise. A box of dominoes is encoded as a list of 10 integers from 0 to 9, where a pair of numbers represent a domino. For example: 0,2,9,1,3,3,7,4,5,6 represents a box containing dominoes: (0,2); (9,1); (3,3); (7,4); (5,6). http://en.wikipedia.org/wiki/Dominoes for more basic info (like pictures)
- veeru September 27, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersYour input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
- _M_ November 26, 2020 in India
Ex:
input is {3,4,5,1} --> output: 72
input is {1,1,1,5} --> output: 15
Follow up, if there are numbers <0
Already posted question ( 3yrs back)
my doubt is can we solve this using multiplication only ( special case 0 and 1 we need to use addition for these alone
ie. if ar[i]==1
max(result*ar[i-1]+1,result*ar[i+1]+1)
)| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer - 1of 1 vote
AnswersA city represented by a rectangular matrix is divided into plot of lands, and the cost of each plot is known. Find the largest rectangular area of land we can buy, within a budget B.
- sachin323 May 27, 2018 in United States
4 6 7
3 5 2
2 4 5
B = 16| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersDesign a counter across all Google's servers.
- nr May 29, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm