Google Interview Questions
- 0of 0 votes
AnswersTo A and B two list, B is A shuffle obtained, find the mapping used shuffle,
- ajay.raj December 19, 2017 in United States
To be able to handle duplicate elements.
Follow-up: Requirements space O (1),| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerslist, push is pushed to the head, pop return each element with the same probability. If you push a sorted list into it, how to pop a sorted list out. Follow-up, asked if pop is from head, and push each element with the same probability in any position, how pop a sorted list out?
- ajay.raj December 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersDetermines whether two strings containing backspace keys are the same.
- ajay.raj December 17, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersA car can receive two instructions A and R. A moves forward for a second and then doubles in speed. R stopped and then reversed. Given a String composed of AR, find where will the car stop.
- ajay.raj December 17, 2017 in United States
Follow-up, given the location if the final stop, find the instruction string.| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
Answersclass EncodingChecker {
- ajay.raj December 17, 2017 in United States
EncodingChecker (String pattern) {...} // constructor
boolean isEncoded (String s) {...} // for any string s, check whether s is encoded from pattern, see below
}
pattern = 'abcabc'
s = '123123' -> True
= 'cbzabc' -> False
= 'xyzxyz' -> True
Second question: If the pattern is not one but one million, how to write isEncoded?| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersDefine a flight class, the flight has four attributes start, end, start time and arrival time,
- ajay.raj December 16, 2017 in United States
There is also a list of strings, represents there is a crew member on that site.
given a list of flights, along with the list of strings mentioned above, asking if the flight crew availability is available for all flights.
example: flight 1 {A, B, 3, 10}, flight 2 {A, C, 1, 7}, flight 3 {C, D, 9, 11} crew member list {"A", "A"} Then return true because flight 3 can take off as flight 1 and flight 2 take off first, then flight 2 descends to bring flight crew A to C.
If flight 3 is {C, D, 6, 12} then return false because no flight crew member is in C at time 6.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersYou are given a binary tree in which each node contains an integer value.
- ajay.raj December 15, 2017 in United States
Find the number of paths that sum to a given value.
The path does not need to start at root, but need to end at a leaf, and it must go downwards (traveling only from parent nodes to child nodes).
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
}
}| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGive a bunch of rectangles, randomly return a point within the rectangle, the probability to be proportional to the size of the rectangle.
- ajay.raj December 15, 2017 in United States
Follow up1: If you want to repeatedly call the function to generate random points how to do.
Follow up2: If the rectangles overlap how to do?| 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 - 0of 2 votes
AnswersGiven a matrix of each element is the height of the location, the side of the matrix has a river height h, water diffuse matrix results,
- ajay.raj December 14, 2017 in United States
Follow up If there is a place where there is not drowning a person and a dog, people want to reach the dog's position without water, the river is highly uncertain,
Ask the maximum height h such that the number of steps taken by a person is less than or equal to a given k. Traverse the height h,| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersQuestion: Given a sorted integer array, return sum of array so that each element is unique by adding some numbers to duplicate elements so that sum of unique elements is minimum.
- ajay.raj December 14, 2017 in United States
I.e., if all elements in the array are unique, return the sum. If some elements are duplicates, then increment them to make sure all elements are unique so that the sum of these unique elements is minimum.
Some examples:
input1[] = { 2, 3, 4, 5 } => return 19 = 2+3+4+5 (all elements are unique, so just add them up)
input2[] = { 1, 2, 2 } => return 6 = 1+2+3 (index 2 is duplicate, so increment it)
input3[] = { 2, 2, 4, 5 } => return 14 = 2+3+4+5 (index 1 is duplicate, so increment it)| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
Answersgiven two strings a and b.
- ajay.raj December 14, 2017 in United States
print out the minimum number of flips of the characters in a such
that a is an anagram of b.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersJSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day...
- ajay.raj December 14, 2017 in United States
Suddenly, all of the JSON parser libraries went missing.
You have been called upon to save us all from impending doom.
Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order.
Subproblem #1
Write a function, dictionaryToJson to convert a dictionary into a string.
For example, assuming you have dictionary like: dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)), the key field is always a string type, the value field could be a string type or a nested dictionary type. And the output would be "{a:apple,b:{b:blueberry,c:cranberry}}"
Subproblem #2
Write a reverse function, jsonToDictionary to convert a string into a dictionary.
Convert a string into the dictionary. e.g., given the input of “{a:apple,b:{b:blueberry,c:cranberry}}”, output dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)).
The names and values only contains letters. You can assume that there is no error in the input. You should not use regular expressions.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersTo a binary array, if you want to move 1 to the array side, 0 to the other side, Can only swap two adjacent elements each time, ask the least number of swap Why? For example, the number of min swaps for [0, 1, 1, 0, 0] is 2 (01100 -> 10100 -> 11000)
- ajay.raj December 14, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersbalanceSum, return to the array to meet the minimum sum equal to the minimum index. Title conditions are all positive numbers, the array length> = 3, there must be solution. If a = [1,2,1,3] returns 3 because a [1] + a [2] = a [4]
- ajay.raj December 14, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGive a string that outputs the largest alphabetical order of all consecutive substrings For example, "ab", substring has {"a", "ab", "b"}, output "b"
- ajay.raj December 14, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answersstream reading number, with timestamp, Design data structure to know the minimum value of the past year, the average,
- ajay.raj December 14, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerssorting nested dictionaries
- ajay.raj December 14, 2017 in United States
give a
{b: {cb: cranberry, bb: blueberry} a: apple, c: cherry}
{a: apple, b: {bb: blueberry, cb: cranberry}, c: cherry}
To sort the key output, if there is nested dictionaries, but also to sort| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersIf xi<xj,yi<yj, we say (xj,yj)dominates(xi,yi). Given a set of number pairs (xi,yi),
- ajay.raj December 14, 2017 in United States
how many indomitable pairs are there?| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersMark likes to listen to music while travelling. His iPod™ contains
- ajay.raj December 14, 2017 in United States
N songs and he wants to listen to L (not necessarily different) songs during
a trip. So he creates a playlist such that:
• Every song is played at least once.
• A song can be played again only if at least K other songs have been played
Mark wants to know how many different playlists are possible. Can you help Mark determine this number?
As the number can be very large,
display number modulo 1,000,000,007.
You are given N, K and L.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven the width, height, start point, end point of the grid, and a list of points, you have to go through these points, ask how many paths are there from the start point to the end point, you can only move from (i, j) down and right.
- ajay.raj December 12, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - -2of 2 votes
AnswerThe design of two functions, cyclecount (num, mod), cycleHistogram (low, high, mod). Probably, cyclecount (num, mod) do digits square sum mod operation. For example mod (12), mod (5) -> square (1) + square (2) mod 5 = 0 -> square (0) mod 5 = 0. Stop return 2. Finished digits square sum after take mod, mod and before the formation of a repetitive cycle. Return form the size before the cycle. CycleHistogram (low, high, mod) will give a [low, high]. Then return a histogram which stores the number of [low, high] inside the cycle size 1,2,3,4,5.
- ajay.raj December 12, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - -3of 3 votes
AnswersThere is a set, there are some balls, different balls have different weights, for example: [red ball 4, yellow ball 1, green ball 2, blue ball 2]
- ajay.raj December 10, 2017 in United States
Ask for the first k-weight combination in this case, if k is 5 then:.
[Red, yellow, green, blue] 9
[Red, green, blue] 8
[Red, yellow, green] 7
[Red, yellow, blue] 7
[Red, Blue] 6 (or [Red, Green])| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersConsider there is a streaming service, which outputs Log object to your service. The Log object has fields like {timeStamp, userId, hashtag(used in the tweet), @userAddressUsedInTweet} etc. Imagine this streaming service has very high QPS. Design your service in such a way that it can output top K userId's within a configurable time window(example: last 1 hour, last 24 hour etc). This service should be extendable to get any top K category (Example: TopK userId's, TopK hashtags etc). What would you use to design such a service. Top K is defined by its frequency, example: 1,2,3,4,1,2,1,2,1,1,5 are the userIDs then the top 2 users are userId 1 and 2.
- lks December 08, 2017 in United States
@EdgeCase:
1. Take into consideration how to store data in that window to get the topK user's.
2. The service should be highly available and should return the results quickly
3. Design and implement this service| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersQuestion:
- xyz December 08, 2017 in United States
* Implement a program which receives tasks, which are basically objects with "run()" method and
* a long field, where long field indicates the time after which the task should start running
* by calling the run() method
EdgeCases:
* Imagine a case, where (A,10) task A is scheduled to run after 10 seconds
* and then when at 3rd second, another task B comes where (B,2) seconds
* then which one would be executed first ?| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer - 0of 0 votes
Answersinput: words [['google', 30], ['gogle', '20'], ...]
- ajay.raj December 08, 2017 in United States
queries [['go, le'], ...]
output: [30, .....]
The query is suffix and prefix, giving the maximum match.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersN different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.
- new December 07, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm Arrays Coding Data Structures - 0of 0 votes
AnswersC * R 2-D array, there are R, G, B, Y four types of elements, if no vertical and horizontal has three adjacent elements are the same type, then the 2-D array is valid
- ajay.raj December 07, 2017 in United States
Let write a function to determine whether a 2-D array is valid.
follow-up how to generate such a valid 2-D array| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersThere are W white beans in the jar, R red beans. Random touch a bean. Touch white beans to eat directly. Touch red beans, put back, touch a bean, whether it is red, eat. Ask the last bean is the probability of white beans.
- ajay.raj December 06, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers
- ajay.raj December 06, 2017 in United StatesGive an Node { Node getLeft (); Node getRight (); String toString (); } Give a root node Node root * / \ + - / \ / \ 1 2 3 4 Return (1 + 2) * (3-4) If (1 + 2) + (3 + 4) does not need to be bracketed Only leaf nodes are numbers followup Give you * + 12-34 to return this tree
| Report Duplicate | Flag | PURGE
Google Software Engineer