Google Interview Questions
- 0of 0 votes
AnswersConvert a doubly linked list to BST in place
- Anonymous October 17, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite an O(n) algo for finding two elemnts in an unsorted array which sum to a given element x.
- Anonymous October 17, 2010
I told hashing.Then he told me to do without it because space complexity becomes high in case of hashing.
I took around 30 minutes and was not able to find any other O(n) solution :(| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersPretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take.
- bjh August 14, 2010| Report Duplicate | Flag | PURGE
Google Front-end Software Engineer Algorithm - 0of 0 votes
AnswersThere is a parking lot of cars that is full except for a single spot. Write some code to take it from one arbitrary configuration to another moving only one car at a time into the empty spot. Analyse the time complexity, how would you improve it, etc.
- jobseeker June 20, 2010| Report Duplicate | Flag | PURGE
Google Trees and Graphs - 0of 0 votes
AnswersLeast common ancestor of a binary tree, BST ? complexity ?
- G January 29, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere are N egg baskets and the number of eggs in each basket is a known quantity. Two players take turns to remove these eggs from the baskets. On each turn, a player must remove at least one egg, and may remove any number of eggs provided they all belong to the same basket. The player picking the last egg(s) wins the game. If you are allowed to decide who is going to start first, what mathematical function would you use to decide so that you end up on the winning side?
- Mishra August 01, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersInsert a node in a complete binary tree efficiently.
it is not BST, it is just a regular binary tree
public TreeNode insert(TreeNode root, int val){
}
this my solution using bfs (O(n) time), is there any more efficient method?
- ajay.raj May 11, 2017 in United Statesimport java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } } class Solution{ public TreeNode insertCompleteTree(TreeNode root, int val){ if(root == null){ return new TreeNode(val); } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); if(cur.left == null){ cur.left = new TreeNode(val); return root; }else{ q.add(cur.left); } if(cur.right == null){ cur.right = new TreeNode(val); return root; }else{ q.add(cur.right); } } } return null; } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null){ return res; } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> list = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); list.add(cur.val); if(cur.left != null){ q.add(cur.left); } if(cur.right != null){ q.add(cur.right); } } res.add(list); } return res; } public static void main(String[] args){ Solution s = new Solution(); TreeNode root = null; int[] nums = {1, 2, 3, 4, 5, 6, 7}; for(int num : nums){ root = s.insertCompleteTree(root, num); System.out.println(s.levelOrder(root)); } } }
| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven a dictionary and a string, find all the substrings that are valid words in dictionary.
- Pedro July 28, 2016 in United States
I was thinking of a Trie solution but I'm not sure a Trie will work easily to match sub words that begin in the middle of the string.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersConsider a setup where a program is continuously receiving floats as inputs (a stream of numbers). Write a method that at any given time returns a moving average. That is the average of the last K numbers received. If the method is called before the program has received K numbers, simply return the average of however many numbers have been received thus far.
- Ray November 15, 2015| Report Duplicate | Flag | PURGE
Google Jr. Software Engineer Algorithm - 0of 0 votes
AnswersIn 5 minutes write a code which checks if a given number is a power of two.
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersYou are given a log of wood of length `n’. There are `m’ markings on the log. The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. Given such a log, determine the least cost of cutting.
- psuedo April 10, 2015 in India| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersIn gmail, while composing an email, upon adding a contact, related contacts are displayed. How would you implement that feature?
- pqrabcd November 14, 2014 in United States
- Write an algorithm for that.
- What data structure would you use to store the weights?
- In what format would you persist this data?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven a KxK array, rotate the array 90 degrees counter-clockwise in place.
- Curious June 20, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an integer 'k' and an sorted array A (can consist of both +ve/-ve nos), output 2 integers from A such that a-b=k.
- DarkLord June 07, 2011
PS:
nlogn solution would be to check for the occurence of k-a[i] (using binary search) when you encounter a[i]. methods like hash consume space.
Is an O(n) solution with O(1) extraspace possible?| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersGive two dice - one is a standard dice, the other is blank (nothing painted on any of the faces).
- Anonymous January 07, 2011
The problem is to paint the blank dice in such a manner so that when you roll both of them together, the sum of both the faces should lie between 1 and 12. Numbers from 1-12 (both inclusive) equally likely.| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
Answers[2] There is a bank which give the 100% rate of interest (annual). you have 1 dollar today with you and you deposit that in the bank.
- Appy June 29, 2010
after how much time would you become the richest man.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Brain Teasers - 0of 0 votes
Answers[1] Design a layer in front of a system which cache the last n requests and the responses to them from the system.
- Appy June 29, 2010
what data structure would you use to implement the cache in the later to support following operations.
[a] When a request comes look it up in the cache and if it hits then return the response from here and do not pass the request to the system
[b] If the request is not found in the cache then pass it on to the system
[c] Since cache can only store the last n requests, Insert the n+1th request in the cache and delete one of the older requests from the cache
The objective is to achieve all the three operations in O(1).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
AnswersSuppose two lists merge at some node .. how do you find that particular node ..
- AA March 20, 2010 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 0 votes
Answers1. There is a stream of numbers, design an effective datastructre to store the numbers and to return the median at any point of time.
- chandra sekhar March 04, 2010
my answers:
1. Arrays. (static DS)
insertion time O(1)
media time --O(1)
2. Dynamic DS.
Linked list: with two pointers.
head pointer and median pointer.
median is pointer , which will be incremented on addition of every two nodes.
insertion time 0(n), can be reduced to 0(1) with the help of tail pointer.
median time 0(1)
Skip Lists:
Insertion time o(log n)
Median time 0(log n)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite code to print out a binary tree so that each depth is printed on its own line. The spacing doesn't need to be correct, but the items within a depth must be in order and on a single line.
- Han April 09, 2009
1
/ \
2 3
/ \
4 5
\
7
1
2 3
4 5
7| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Trees and Graphs - 0of 0 votes
AnswersThe wildcard regex can include the characters * and + .
- alex May 17, 2018 in United States
‘+’ – matches any single character or empty character!
‘*’ – Matches any sequence of characters (including the empty sequence) For example,
Text = "baaabab":
regex = "ba*a++", output : true
regex = "ba*a+", output : true
regex = "a*ab", output : false
//empty string
Text=""
Regex= "+" , output : true| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 0of 0 votes
AnswersImplement a method for the following signature:
void * alignedAllocate(size_t sizeInBytes, size_t alignment) { }
The method should allocate memory for the given size and the pointer should be aligned.
For example ifp = alignedAllocate(1000,64);
p%8 should be 0.
- thewhatwhat September 05, 2015 in United States
Implement a second method that deleted the pointer give p.
Extend the delete method to handle multiple p's.| Report Duplicate | Flag | PURGE
Google Software Engineer C C++ - 0of 0 votes
AnswersWe have table:
- abctoxyz December 14, 2012 in United States
create table employee (id int, name varchar, salary decimal, mgr_id int);
We want to print name and salary of employees that make more than their manager or don't have a manager.
This can be done by the following SQL:
select name, salary
from employee e, employee m
where e.salary > m.salary and e.mgr_id = m.id;
Question: how to do this with Hadoop? Write down the function for the mapper and reducer respectively.
map: k,v -> (k’,v’):
reduce: k, <list v>, ->k’, v’:| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersClass A, B and C all cout their own names in their constructor. C is B’s subclass while it has an instance of A as its private member. When a C object is instantiated, what will the order of printed letters?
- A November 03, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a program to count the number of uni-value sub-trees in a given tree. Explain reasoning, and implementation decisions.
- ANONU September 30, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersHow would you store 1 million phone numbers?
- Andy2000 September 04, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersImplement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe.
- virtualhealing June 28, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test - 0of 0 votes
AnswersThere is a sequence {a1, a2, a3, a4, ..... aN}. A run is the maximal strictly increasing or strictly decreasing continuous part of the sequence. Eg. If we have a sequence {1,2,3,4,7,6,5,2,3,4,1,2} We have 5 possible runs {1,2,3,4,7}, {7,6,5,2}, {2,3,4}, {4,1} and {1,2}.
- Anonymous March 15, 2012 in United States
Given four numbers N, M, K, L. Count the number of possible sequences of N numbers that has exactly M runs, each of the number in the sequence is less than or equal to K and difference between the adjacent numbers is less than equal to L.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersI have two methods of an object, and they each access a critical section of code. I want to restrict access to the section so that in one method, I allow multiple threads to access the critical section. In the other method, I want only one thread to have access. If a caller calls the second method, it should lock out all clients from accessing the critical section in either of the two functions. Here is the basic structure of the class:
- KrrishDon August 10, 2011
class ClassThatNeedsFixing
{
public:
// Will allow many concurrent threads through, unless there is a
// call to the other method.
void AllowMany() {
// Here is the critical section that must be protected
...
}
// Will lock out any client, including callers to the other method.
void AllowOne() {
// Here is the critical section that must be protected
...
}
private:
// Assume there are members here that need protecting
// above.
...
};
In order to solve this problem, you are provided with two classes: Mutex and Semaphore. They have the standard behavior of the concepts that share their class names. Here are the public interfaces for each of these classes:
class Mutex
{
public:
Mutex();
void Acquire();
void Release();
};
class Semaphore
{
public:
// At it's creation, one can specify the count
// of the semaphore.
Semaphore(unsigned int count);
void Acquire();
void Release();
};
Fix the ClassThatNeedsFixing implementation so that the critical section is protected.
Your solution will be graded on flexibility and robustness (i.e., we should be able to re-use your solution in a generic case and it should be exception safe). You are allowed to create as many classes/objects/templates/etc that you need. Feel free to use the STL if necessary. Document your code as you would for real-world maintainability.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Threads