Google Interview Questions
- 0of 0 votes
AnswersGiven a sorted doubly linked list, write an algorithm to convert this list into a binary search tree (BST). The BST will be used to represent a set. You may expect that client will use it to search for presence of a key in the set.
You may assume that you are given the following Node implementation that you can not exted or modify:public class Node { public Node prev, next; public int key; }
You algorithm is not allowed to create any other instance of the Node.
- autoboli January 10, 2015 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersYou are given a string 's' and you are given a dictionary of english words. You goal is to write an algorithm that returns all words from the dictionary the can be formed by characters from that string 's'.
- autoboli January 07, 2015 in United States
Example:
s = "ogeg"
following words can be formed from 's': go egg ego . . .
Further it is given that string 's' always consists of four lower case characters. Lets say that the dictionary is contained in a file and can be fitted in the memory. It is up to you which data structure you use to represent the dictionary.
How would you design an efficient algorithm? Follow up: What if the dictionary file can not be fitted in the memory?| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersGiven a table of [Url, Content] pairs produce a new table of [Url, Set of duplicate Urls].
- jali_smith January 07, 2015 in United States
Example Input:
a.com => <html>a</html>
b.com => <html>b</html>
c.com => <html>c</html>
d.com => <html>a</html>
e.com => <html>a</html>
Example Output:
a.com => [d.com, e.com]
b.com => []
c.com => []| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
public class Node { public Node left, right; public String val; }
Example: The following BST
- autoboli January 06, 2015 in United States
G
/ \
A T
can be converted into a list
A = G = T
Do it in place! Hnce the memory complexity of your algorithm shoul be O(1).| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersHow can I represent the following in a data structure ?
- Andy January 05, 2015 in United States
<html><body><div><span>TEXT1</span><br/></div></body></html>
Do I do the same using a stack or create a tree for the same ?| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersDesign an algo to decide if the GO game is over. i.e.
- thefunnyclick1990 December 23, 2014 in United States
Given a boolean matrix, write a code to find if an island of 0's is completely surrounded by 1's.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 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 - 2of 2 votes
Answersgiven a vector of integers, v[i] represent the stock price on day i. Now you may do at most K transactions. you must sell your stock before you buy it again and that means you can NOT have two stocks at the same time. write a program to find max profit you can get.
- rjrush December 17, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersThere is a code with a runtime error. We add printf to display the value of a variable and we don't get the runtime error anymore. explain what the reason can be.
- maya December 15, 2014 in United States| Report Duplicate | Flag | PURGE
Google Intern Testing - 5of 5 votes
AnswersGiven an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.
- rjrush December 06, 2014 in United States
If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not greater than 100
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 2 votes
AnswersGiven n number of legacy services with user data<userid, info, date>
- next_big_gig December 05, 2014 in United States
Design an API to return user data in a given date range, it should collect data from each service and merge and return the data sorted by date.| Report Duplicate | Flag | PURGE
Google Member Technical Staff System Design - 3of 5 votes
AnswersGiven a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
- Phoenix December 02, 2014 in United States
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 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 - 1of 1 vote
Answers
- Phoenix November 22, 2014 in United KingdomThere are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit. Design a data structure to represent the floor and door design. A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 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 - 1of 3 votes
AnswersImplement a vector-like data structure from scratch.
- Victor November 21, 2014 in Brazil
This question was to be done in C or C++.
Discussion topics:
1. Dealing with out of bounds accesses.
2. What happens when you need to increase the vector's size?
3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Data Structures - 4of 4 votes
AnswersGiven a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
- xyz_coder November 20, 2014 in United States
Find the length of the shortest palindrome that you can create from S by applying the above transformation.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -7of 7 votes
AnswersI think it's one system design question. Design one google's API, qps (query per second).
- yoyiyoshi November 20, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 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 - 5of 5 votes
AnswersWe have words and there positions in a paragraph in sorted order. Write an algorithm to find the least distance for a given 3 words.
- pqrabcd November 14, 2014 in United States
eg. for 3 words
job: 5, 9 , 17
in: 4, 13, 18
google: 8, 19, 21
...
...
Answer: 17, 18, 19
Can you extend it to "n" words?
Context: In Google search results, the search terms are highlighted in the short paragraph that shows up. We need to find the shortest sentence that has all the words if we have word positions as mentioned above.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -4of 4 votes
AnswersThere are N parking slots and N-1 cars. Everytime you can move one car. How to move these cars into one given order.
- yoyiyoshi November 14, 2014 in United States
BTW: I got this question from internet but i could not figure it out partially because the description is kind of incomplete to me. Anyone knowing this question or the solution?| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersGiven a BST and a number x, check whether exists two nodes in the BST whose sum equals to x. You can not use one extra array to serialize the BST and do a 2sum solver on it.
- yoyiyoshi November 14, 2014 in United States| Report Duplicate | Flag | PURGE
Google - -2of 4 votes
AnswersGiven a map, each road has a value denoting how many hours it takes to travel from adjacent cities. Each city has its own holiday. If you arrive at the city during its holiday, you can get one gift. However, in each week, you can only travel one time. Now you are initially placed in one city at the beginning of this year, how do you plan your traveling to get the maximal gifts.
- yoyiyoshi November 14, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersThere are many tourist sites and each has their own holiday. If you arrive there during the holiday, you can gain one gift. It costs you many hours Wij traveling from site_i to site_j. What's more, you can only travel once in one week. Now you are initially placed in one site, how do you plan your routine in this year to gain most gifts.
- yoyiyoshi November 14, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersGiven a BST and a number x, find two nodes in the BST whose sum is equal to x. You can not use extra memory like converting BST into one array and then solve this like 2sum.
- yoyiyoshi November 14, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersGiven an arraylist of N integers,
- united November 13, 2014 in United States
(1) find a non-empty subset whose sum is a multiple of N.
(2) find a non-empty subset whose sum is a multiple of 2N.
Compare the solutions of the two questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given the toplogical information of a terrain in the following format - There are n points ( x_i , y_i ) and for each point (x_i , y_i ) the altitude h_i is given.
- harshit.knit November 12, 2014 in United States
For any rectangle (axis parallel) defined by the x-y coordinates of
the corner points, we must answer the query about which is the highest altitude point lying within the rectangle.
Implement this using a range-query data-structure that answers such a
query in O( log^2 n) time| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 2 votes
AnswersWrite code to get maximum and second maximum element of a stack. The given function should be in O(1) complexity . Later extend for finding kth max in O(1).
- Nascent November 08, 2014 in India| Report Duplicate | Flag | PURGE
Google