Google Interview Questions
- 0of 0 votes
AnswersGiven a positive integer n, write a function to print the nth row of Pascal's triangle.
- Anonymous November 29, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersReturn the nodes only a particular level of the BST.
- Anonymous October 19, 2010
given: level, from which nodes to be returned.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDelete duplicates from a sorted array in O(log n) time and O(1) space.
- Anonymous October 17, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a function that takes in an integer input and gives out an integer:
- Bandicoot April 23, 2010
int func(int input);
This function is deterministic. It always gives the same output value for a given input. Say func(8) = 7 whenever it is called.
Now this function is called multiple times in a loop. This would generate a stream of integers [which are the outputs of that function for different inputs to the function]. He asked me what is the length of this loop ? When i said i didn't understand by what he meant, he said, give me the count of how many numbers are repeated and how many numbers are not repeated. He said there is very limited memory: you can store only a certain number of integers at a time, but not all of them.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersint getNthNonZeroElement(vector<int> & elements, int n) {
- Han April 09, 2009
vector<int>::iterator i;
int count;
for (i = elements.begin(); i < elements.end(); i++) {
if ((*i) != 0) {
if (count == n) {
return (*i);
}
count++;
}
}
return -1;
}
The above code should return the nth non-zero element. For example, given vector v = [0, 8, 6, 0, 9, 7,20], should return 9 if n pass-in is 3;
Question: optimizing it.
My answer:
int getNthNonZeroElement(vector<int> & elements, int n) {
vector<int>::iterator i;
for (i = elements.begin(); i < elements.end(); i++) {
n -= ((*i) != 0);
if (n == 0) return (*i);
}
return -1;
}
btw, the original question should init count = 0| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Coding - 0of 0 votes
AnswersGive a decimal number, such as 123. Asking a total of smaller num than 123 made up by 1 and 0 composed of decimal numbers.
- ajay.raj February 06, 2018 in United States
111, 110, 101, 100, 11, 10, 1, 0.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven an array of strings, find out in how many cases is any of the anagrams of the string at location i, a substring of the string at location i+1.
- lkjhgfdsa September 30, 2017 in United States
Test Case I: ["ab", "ab", "abc", "bca"]
Answer: 3
Test Case II: ["ab","aqb"]
Answer: 0| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersGiven the interface below, implement a task scheduler.
interface Task { void Run(); Set<Task> GetDependencies(); }
Additionally, the task scheduler should follow two rules.
- John March 07, 2015 in United States
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersThe latest reality show has hit the TV: “Cat vs. Dog”. In this show, a bunch of cats and dogs compete for the very prestigious Best Pet Ever title. In each episode, the cats and dogs get to show themselves off, after which the viewers vote on which pets should stay and which should be forced to leave the show.
- lxfuhuo December 17, 2014 in United States
Each viewer gets to cast a vote on two things: one pet which should be kept on the show, and one pet which should be thrown out. Also, based on the universal fact that everyone is either a cat lover (i.e. a dog hater) or a dog lover (i.e. a cat hater), it has been decided that each vote must name exactly one cat and exactly one dog.
Ingenious as they are, the producers have decided to use an advancement procedure which guarantees that as many viewers as possible will continue watching the show: the pets that get to stay will be chosen so as to maximize the number of viewers who get both their opinions satisfied. Write a program to calculate this maximum number of viewers.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
One line with three integers c, d, v (1 ≤ c, d ≤ 100 and 0 ≤ v ≤ 500): the number of cats, dogs, and voters.
v lines with two pet identifiers each. The first is the pet that this voter wants to keep, the second is the pet that this voter wants to throw out. A pet identifier starts with one of the characters ‘C’ or ‘D’, indicating whether the pet is a cat or dog, respectively. The remaining part of the identifier is an integer giving the number of the pet (between 1 and c for cats, and between 1 and d for dogs). So for instance, “D42” indicates dog number 42.
Output
Per testcase:
One line with the maximum possible number of satisfied voters for the show.
Sample Input 1
2
1 1 2
C1 D1
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1
Sample Output 1
1
3| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 0of 0 votes
AnswersHow do you add two numbers that are larger/longer than Integer datatype? I said I would use BigInteger , then he asked how will you add if the number is larger than BigInteger?
- Madan January 16, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersHow does a site like Facebook store "Likes" ?
- bertrandreddy January 19, 2013 in United States
Whats the best approach for Space complexity and Time complexity ? Can we do it in O(1) space or at least O(n) space ?| Report Duplicate | Flag | PURGE
Google Member Technical Staff Algorithm Data Mining Data Structures Large Scale Computing - 0of 0 votes
AnswersWrite a function to determine node in a tree at maximum depth , with ties to the right ( ties to the right means , right most node at MaxDepth D )
- ibleedscarletgray October 26, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersIf given a variable that is changing after every 1 second...
- ediston April 17, 2012 in United States
Design a clock using that avriable..
I am not sure if this question was more related to OS or not...| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Operating System - 0of 0 votes
Answersadd 2 link lists widout recursion in O(n) n constant space
- mann June 20, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersm x n integer array, 0 or 1, given a src and dest cell, find the number of all paths from src to dst with all '0' cell visited once, the cell with value '1' can not be visited.
you can move up, down, left, right
e,g,s 0 0 s -> 0 -> 0 or s 0 -> 0 | | ^ | 0 0 0 0 <- 0 <- 0 0 0 0 | | ^ | 0 0 d 0 -> 0 -> d 0 -> 0 d total 2
s 0 0
- anonymous April 19, 2011
0 1 0
0 0 d total paths 0| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou have given a dictionary and a string, you need to separate words that are in dictionary.
- Anonymous April 06, 2011
ex - catsanddog (here cat and cats both can be in dictionary)
output - cats and dog| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answerswhat is problem with this code?#
- Cartman September 25, 2010
#include<iostream>
using namespace std;
const int a[]={1,2,3,4,5};
int b[a[2]];
int main(){}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C++ - 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 - 0of 0 votes
AnswersYou should transform an structure of multiple tree from machine A to machine B. It is a serialization and deserialization problem, but i failed to solve it well.
You could assume the struct is like this:struct Node{ string val; vector<Node*> sons; }
and in machine A, you will given the point to root Node, and in machine B,you should return a pointer to root Node.
- lxfuhuo July 30, 2015 in China| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersThe diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows a tree with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
- adam2008 February 22, 2013 in United States
In particular, note that the diameter of a tree T is the largest of the following quantities:
the diameter of T's left subtree
the diameter of T's right subtree
the longest path between leaves that goes through the root of T
Given the root node of the tree, return the diameter of the tree| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersA binary tree is given with left and right populated but the nextRight pointers in each node are not populated. Populate the nextRight pointer in each node.
- Rajat January 07, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow do you sort a billion rows of data of integers (a few gigabytes) in a file with only 1024KB of main memory.
- Amigo October 21, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersReverse n-Ary Tree and Return List of Leaf Nodes as Output
- newbie December 21, 2011 in United States for Google Plus
example
Tree will be like
1
/ | \
2 3 4
/ / \
5 6 7
/ \
8 9
out put will be 1st reverse the tree e.g. 2 points to 1 , 5 points to 2 , 8 poinst to 5 and so on for each node , without modifying the tree and then return list containing leaf node
as OutPut Head-> 8->3->6->9->NULL
do it efficiently , i saw a approach & code here but i think its not correct , guys can you make it correct ?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow can you merge two BST inplace so that preserving the BST property?
- learner October 06, 2011 in India
Provide algo only, dont write code| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Trees and Graphs - 0of 0 votes
AnswersThere is an array and the distance between any two consequent elements is one(+1 or -1) and given a number. You have to check whether the number is in array or not with minimum complexity.
- aaaa May 25, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a building of H number of floors and an elevator composed of N boxes such that only one box stops at a particular floor and that if a box stops at x-th floor than the box on top of that would stop at (x+d)-th floor for some constant d.
- Amm April 26, 2011
Given H and N, find the number of different elevator configurations. Two elevators are different if their bottommost box is at first floor than there exits an "i" such that a box is at i-th floor in one elevator and no box is at i-th floor in other elevator.
For example,
if H = 9 and N = 3,
then there are 2 configurations possible.
1) First box stops at 1-st,2nd,3rd floor. Second box stops at 4-th,5th,6th floor and third box stops at 7th, 8th, 9th floor.
2) First box stops at 1st,4th, 7th floor. Second box at 2nd,5th,8th floor and third box at 3rd, 6th, 9th floor.| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersGiven two lists. Write a function to check whether both the lists are equivalent or not.
- Anonymous October 17, 2010
(Two lists are said two be equivalent if both of them contain same elements with same frequencies in both the lists).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm