Google Cracker Sheet -

- By Sunyul Hossen
Note: [To Use this sheet optimally go and watch the "Cracking the Google coding interview
🔥: The definitive prep guide" video on Debug Buzz Channel.
Link - https://youtu.be/HM8gsynJkQc ]

Q) 12th August 2022 -

Q) 7th August 2022 -
We have a chat application and each transaction has a sender and receiver. Every
message has a sender user and a receiver user. for every chat message the
registerTransaction method is called. at any moment we need a getMostActiveUser
which returns the user with most number of other users he/she is transacting with. I
implemented a solution with a map of username -> hashtable of users user is
interacting with. And we keep a maxTransactions and activeuser variable to keep
track. I implemented following way which I think has O(1) for both methods. As an
extension I was asked if we need to implement new method called
removeUser(String user) which removes this user from all counting. I could not think
of any way other than removing that user from map and getting the next highest
count from the map. which has O(n) complexity. interviewer asked for better
optimization which I could not come up with. I was told I did not pass the Online
assessment. Can anyone suggest me better way to implement this?

registerTransaction(String sender, String receiver, String timeStamp)

String getMostActiveUser()

class ChatApplication{

String activeUser;

String mostTransactions;

Map<String, Set> userMap = new HashMap<>();

void registerTransaction(String sender, String receiver, String timeStamp)

Set users = userMap.getOrDefault(sender, new HashSet<>());

users.add(receiver);

if(users.size() > mostTransactions)

mostTransactions = users.size();

activeUser = sender;

Set<String> users2 = userMap.getOrDefault(receiver, new HashSet<>());

users.add(sender);
if(users2.size() > mostTransactions)
{
mostTransactions = users2.size();
activeUser = receiver;
}

}
String getMostActiveUser(){
return activeUser;
}
}

Q) 3rd August 2022 -

Given n points in a 2D plane, find the number of goups.

Groups are defined as -

Distance between any 2 points in the same group will be <=1000

Distance between any 2 points in different groups will be >1000

eg:

((0,0), (2,3), (4,2), (2000,1), (2000,3), (2002,5))

Ans: 2

Q) 3rd August 2022 -

Implement the methods of the class:

class EnglishSpanishTranslator {
public:

// adds a bi-directional mapping between these words to the knowledge

base
void addTranslation(string englishWord, string spanishWord);

// gets english for a spanish word else raise an exception

void getEnglish(string spanishWord);

// gets spanish for an english word else raise an exception

void getSpanish(string englishWord);
};

Q) 3rd August 2022 -

Implement a generic translator class where you can add translations from any
language to any other languge to the knowledge base and can query the same way.
It should allow multi-level translations.
Multi-level translations: If there's a word translation in the knowledgebase for
English <-> Spanish and Spanish <-> Hindi, when queried for Hindi -> English for the
same word, function should still be able to return it if there's an indirect relation.

Q) 30th July 2022 - https://leetcode.com/discuss/interview-

question/1693416/google-onsite-recursively-delete-leave-
nodes-in-a-multi-tree
Q) 30th July 2022 -
https://leetcode.com/problems/find-all-possible-recipes-from-
given-supplies/

Q) 30th July 2022 -

https://leetcode.com/discuss/interview-question/2337984/
Google-or-Onsite-or-Song-Shuffler

Q) 29th July 2022 -

Given an array of integers you need to find the longest increasing subsequence
where each consequitve element in the subsequence can have difference in range of
(1, K).

Eg:

1, 2, 4, 1, 10, 2, 3 4, 5, 7

k=2

answer will be

[1 2 3 4 5 7]

Q) 26th July 2022 -

Given a playlist of songs, you have to design a song shuffler.

This song shuffler is not like the normal song shuffler that shuffles the complete playlist
at the start and returns a shuffled list, but instead when asked for a next song to be
played, returns a random song from the list of songs.

The next random song to be played should satisfy a condition that the song was not
played in the last 'k' turns.

You have to make sure, that at each call, all the eligible (not played during last k turns)
songs have equal probability of being played next.

For example:

if songs = [A, B, C, D], k = 2,

then a possible random sequence of songs can be:

playNext: [ A , B , C , D ] -> return C

playNext: [ A , B , _ , D ] -> return A
playNext: [ _ , B , _ , D ] -> return B
playNext: [ _ , _ , C , D ] -> return C (as C was not played in the last
two turns, it has an equal probability with D to be played).
Q) Date: 26th July 2022 -

given a string s which contains only curly braces and questions was what is the
minimum number of operations to become it valid expression and return corrected
string. There are three operations:
insert { or } in any position
delete { or } in any position. flip any position so { change by } or vice versa.

Q) Date: 26th July 2022 -

given N, K and array A length of N and contains non-negative integers. for example
N = 5, K = 2, A = [4, 8, 1, 10, 2]. K is initial work capability which means that you can
work K days, when you work i-th day your capability decreases by 1 and you get
reward A[i], when you skip day your current capability increases by 1. you start at 0
and the question was what is the maximum total reward you can get.
In this example, the answer is 22 because you work 0 and 1 day, after that your
capability will become 0. After that you skipp day 2 and capability becomes 1 and
you work day 3 and you will get 10 reward, in total 4+8+10=22 reward and it's the
maximum you can achieve.

Q) Date: 25th July 2022 -

You are given a course prerequisites list in the form {(a,b),(c,d)...}. A semester is a
unit where you can take one or multiple courses. To take a course in a semester, you
must complete all the prerequisite courses of that course. You need to find minimum
number of semesters required to complete all the courses of the curriculum.
(a,b) -> course a is prerequisite to take course b.
Example: Given (1,2) (1,5) (5,2) (2,3) (2,4) (4,6) (5,6) the answer is 5./Which means
you need can complete the curriculum in 5 semesters.
Q) Date: 24th July 2022 -

Constraints :
N,M<=5000
MAX(ai,bi) <=5000

Q) Date: 14th July 2022 -

Given some names and their values. Write a function which takes name as input and
outputs full value, also replacing the name in the value if present.

AXA = '/leetcode/config'
BYB = '/%AXA%/interview/corner/file'
LCLS = '/tmp/file/usr/shared/%BYB%'

Input: BYB
Output: '/leetcode/config/interview/corner/file'

Input: LCLS
Output: '/tmp/file/usr/shared/leetcode/config/interview/corner/file'

Q) Date: 13th July 2022 -

Given a Doubly Linked list, find a minimum number of API calls ( move()) to sort the given
Linked List. we can only use the move() method to move the node value. We can iterate
over the LinkedList elements as many times as we want but the task is to minimize the
move() calls and sort the LinkedList.

Example LinkedList 5 -> 2 -> 4 -> 3 -> 1 -> 6

move() - function takes node_val that you want to move and the position of where you
want to place the node at. For example, if you want to pick node_val 5 and place it
between 1 and 6 you can use move(5,1,6). The interviewer mentioned the move function
is flexible and we can use an index as well to move the node. The way the function works
is It would delete the node_val 5 and place it between 1 and 6 like this 2->4->3->1->5-
>6. This is defined as a 1 move() call.

Our task is to minimize the move() call to sort the given LinkedList. For this linkedList 5 ->
2 -> 4 -> 3 -> 1 -> 6, minimum move() calll is 3 to sort the list.

2->4->3->1->5->6 <-- move 1

1->2->4->3->5->6 <-- move 2

1->2->3->4->5->6 <-- move 3

Q) Date: 9th July 2022 -

Special Paths

You are given the following:

● A Tree with N nodes

● An array denoting the value of each node

A path is called special path if following conditions are satisfied

● All nodes in the path are traversed exactly once.

● The value of starting node and terminating node in the path is same and starting
node ≠terminating node.
● The values of any node in the path are not greater than tha value of starting node.

Task

Count the number of special paths in the tree.

Note: Two paths are different if they contain atleast on different node.

Constraints:

2<=N<=10^5

1<=A[i]<=10^9 ∀i ∈[1,N]

It is guaranteed that given input forms a tree.

Example:-

N=5

edges =[{1,2},{1,3},{3,4},{3,5}]
A = [2,3,1,2,3]

Output: 2

Explanation:-

● Path -- 1{2} -> 3{1} ->4{2}

● Path -- 2{3} ->1{2} ->3{1} -> 5{3}

Thus the answer is 2.

Q) Date: 9th July 2022 -

Two arrays are given of length n and two numbers c and d.

Find the count of all pairs that follow the condition : a[i]-a[j]+c <= b[i]-b[j]+d such that i <
j.

Constraints:

2 <= n < 1e5

1 <= a[i], b[i] <= 1e9

Q) Date: 9th July 2022 -

You are given the following:

● Integers n, c, d
● Array a as {a1, a2, ..., an} of length n
● Array b as {b1, b2, ..., bn} of length n

Task

Determine the number of pairs i, j (1 <= i < j <= n), satisfying the inequality

ai - aj + c <= bi - bj + d

Constraints

1 <= T <= 10

2 <= n <= 2.10^5

0 <= c, d <= 100

1 <= ai, bi <= 10^9

Q) Date: 9th July 2022 -

Partition String

You are given a string S of lenght N of digits 0 - 9. You need to partiton strings into K
substrings such that

● Each substring has a minimum lenght of M

● Substring must start with even digit and ends with odd digit number

Determine the number of ways to partitioin the strings which satisfy the above condition

You should find answer modulo 1e9 + 7

constraints :

1 <= n<= 2x10^3

1<= m<= n

1<=k<=n

Test cases

n = 9
m= 2
k = 3
s = '232387421'
So there are total 3 ways possible

Q) Date: 9th June 2022 -

https://leetcode.com/problems/swim-in-rising-water/

Q) Date: 7th June 2022 -

Given an input string, return an output string such that all the lower case characters
should be sorted. Indices of non-lower case characters should remain the same as in
the original input string.

Eg. Input -> 'Test@123 Google'

Output -> 'Teeg@123 Gloost'

Q) Date: 6th June 2022 -

Given a matrix of size n*m, where each position is representing a city.
Initially all city are represented by zero. ( means they are not traversible ).

On each day one city will randomly become traversible. ( matrix[i][j] = 1 )

Write an algorithm that can detect when there is a path from any city of first column to
any city of last column.

Q) Date: 6th June 2022 -

Given a string s, return the length of longest substring such that every character in the
substring has equal number of occurence.

Q) Date: 25th May 2022 -

Problem statement:

Suppose you are working on Google Photos. you are wring the client application.
Request comes to you to upload N photos. you fire the request to server to upload
those N photos to server. Then the server responds back with acknowledgements
that a particular photo is uploaded.

Example. Suppose you are uploading 10 Photos, The server can respond back in any
order, such as 1,2,4,5,3,7,6,10,9,8 . Now at any given point of time we need to check
what is the maximum photo number which has been uploaded continously.

Example.

ack(1),

getMax()-> returns 1, because the maximum photo uploaded is 1

ack(2),

getMax()-> returns 2, because the maximum photo uploaded is 2

ack(4)

getMax()-> returns 2 only because 3 has not been recieved yet

ack(5)

getMax()-> returns 2 again because 3 has not been recieved yet

ack(3)

getMax()-> returns 5 because we recieved 3 and 4 and 5 also we recieved eralier.

using this example you have to complete the following class

public class PhotosClient {

// initializer
public PhotosClient(int n) {

}
// this method is called each time you receive acknowledgement
forom the server
public void ack(int x) {

}
 // this method will be called in between to check what the maximum
photo number has been uploaded successfully
public int getMax() {

}
}

Q) Date: 22nd May 2022 -

Given an integer array a, and 2 integers - c and k, where c is the favourite number and k is
the maximum number of replacements we can make. We have to find the maximum
number of contiguous elements which are equal to c. We can replace k number of
elements with any number we want.

Example - a = [1,2,2,3,2,2,2,4], c=2, k=2.

● In this case, without any replacement, maximum number of contiguous elements

will be 3 (from index 4 to index 6).
● We can replace element at index 3 with number 2 so now array will be a =
[1,2,2,2,2,2,2,4] , maximum number of contiguous elements will be 6 (from index 1
to index 6).
● For last replacement, we can replace either element at index 0 or index 7 with
number 2, so maximum number of contiguous elements will be 7, which is the
answer.

Q) Date: 22nd May 2022 -

CPU Scheduling Alborithims

needs to check can we complete all of the process in given start and arrival time with
allocated CPU numbers;

if time is running out they can take one a cpu from their bucket and else they can take
from outside of bucket

[10,20,2]

Here 10 is start time

20 is end time

2 is CPU Number

[[10,20,2], [40,20,3], 5]

Q) Date: 22nd May 2022 -

Robot sort:

You have boxes in magazine and a single empty spot (at the end) like:

1, 4, 2, 5, 3, _

You have a robot which needs to sort boxes. It can only pick up single box, put it in
empty box and then pick another one up. Sort boxes to have either _, 1, 2, 3, 4, 5 or 1, 2,
3, 4, 5, _

What is the fastest way to sort if robot knows immediately where are boxes with specific
numbers, but it takes time for him to move.
Q) Date: 19th May 2022 -
https://leetcode.com/problems/evaluate-reverse-polish-
notation/

Q) Date: 18th May 2022 -

https://leetcode.com/problems/path-with-minimum-effort/

Q) Date: 18th May 2022 -

https://leetcode.com/problems/maximum-side-length-of-a-
square-with-sum-less-than-or-equal-to-threshold/

Q) Date: 14th May 2022 -

To install packages of different versions of an Android app, each package has different
Android system requirements (only the major version is considered). For example:

v1: min 1.0 max 6.0

v2: min 3.0 max 7.0

v3: min 4.0 max 9.0

Find the Android system from 0.0 -> latest (the interviewer said it is MAX_INTEGER)
different Android installation packages supported by each interval, and then only return
all intervals:
[0.0, 0.0] [1.0,2.0] [3.0, 6.0] [7.0, 7.0] [8.0, latest] -> return these intervals
none v1 v1,v2 v2 none -> do not need to return

Q) Date: 11th May 2022 -

U need to design structure in which it will nee to implement following 2 methods :

1. public void insertOrReplace(long index, long number)

2. public long findSmallestIndex(long number)
so the first one is to insert the number on the index given by the user, index can
be any number of long type and if at the same index another number comes it will
replace that number
2nd method is need to be implemented int which user will be given any number
and we need to return the smallest index of that number
Ex :
index->number sequence
2->100
1->100
3->100
5->100
if any user does findSmallestIndex(100) , output will be 1
2-> 200
if new number 200 comes at index 2 then 100 will be present only at indexs 1,3
&5 and 2nd index will be removed.

Q) Date: 10th May 2022 -

https://leetcode.com/discuss/interview-question/1580545/google-
stage-oa-calculate-total-wait-time
follow up questions:

1. what if client number is far greater than agent number?

2. what if there's a constraint on time[i] that 1 <= time[i] <= 10, how would you use
this to your advantage?

Q) Date: 2nd May 2022 -

8 directions: N\W\E\S\NW\NE\SW\SE

check whether the input is valid?

input : P1NP2,P2NP3,P3NP1

P1 is North of P2

P2 is North of P3

P3 is North of P1

Output: False (since P3 will be in the South of P1)

Q) Date: 1st May 2022 -

board game, a board (int[][] matrix) only has 0 and 1. Each time call next() to add a 1
at matrix[0][0], and the other numbers shift (in Z path)...if any col or row are all 1s,
return true. or false.
example :
101
010
111
after call next():
110
101
011
after call next():
111
010
101

Q) Date: 28th April 2022 -

Graph is given as adj list format, return nodes order starting from any node.

Input:

[A: [B, D]

B: [A, C]

C: [B, D]

D: [A, C]]
Output: ABCD
Assumption: Graph represents Ring topology find the optimized way to traverse.
Follow up: Check if Graph represent ring topology check for all corner cases.

Q) Date: 24th April 2022 -

1. Design a game 5x5. Given getRandom(start, end) function to generate all
random numbers from 1 to 75

[[1, 5, 2, 8, 13] number random from 1 to 15

[19,17,16,25] number random from 16 to 30

[35,32,43,41,39] 31 to 45

[etc...]

Create a void function which generate the game and return 2D array which contains
game

no input (void function)

output will be 2D array

Q) Date: 8th April 2022 -

Give a string, for example : input : a-(b+c+b) output : a-2b-c.

Q) Date: 7th April 2022 -

remove Leaves of Binary Tree.
follow up: 1. remove new created leaves first (after remove 4,5, we need remove 2
immediately..then 6,7 ....)
1
/\
23
/\/\
4567
follow up: 2 remove new created leaves last

Q) Date: 7th April 2022 -

A binary tree, return all root-to-node paths. For example,
1
/\
23
\
5
return : ["1","12","125","13"]
Q) Date: 6th April 2022 -
Given an index and an input string find the char at the given index of the string. But
here's the catch: if the index exceeds the length of the string, then you transform the
string by removing the string's last character and appending it to the front and
appending this transformed string to the original string until you have a string
length that exceeds the desired index.

For example,if we have a string "abcd" and want to find the char at index 3 it would
obviously be 'd'. However, if we want to find the char at index 7 of "abcd" we would
transform "abcd" to "abcddabc" and the char would be 'c'. If we want to find the
char at index 12 of "abcd" we would transform "abcd" to "abcddabc" and then again
transform to "abcddabccabcddab" and the char would be 'd.

Q) Date: 31st March 2022 -

Binary Tree Maximum Path Sum, but with an extra requirement: the path with
exactly length of K

Q) Date: 30st March 2022 -

https://leetcode.com/problems/find-k-closest-elements/

Q) Date: 30st March 2022 -

https://leetcode.com/problems/intersection-of-two-arrays/

Q) Date: 30st March 2022 -

Given the user and there posts, maximize the likes of N posts where N appears
atleast N times.
For eg. Consider likes = [8,6,5,5,2,1] Output: 4 (Because there are 4 post with 4
likes. )
Explaination: 8 contains 4 likes, 6 contains 4 likes,5 contains 4 likes,5 contains 4 likes
and more importantly number of posts are 4
2. likes = [1,2,2] Output 2 (Because there are 2 post with 2 likes)
3. likes = [1,3,4,2] Output 2(Because there are 2 post with 2 likes)

Q) Date: 25th March 2022 -

Given T[] , an array that represents N agents and the time they need to
serve customers . All N agents can serve at oce
for M customers if they are waiting , they choose the agent with least
serving time . If a New customer comes in , calculate the total wait time.

Q) Date: 25th March 2022 -

Given a table of rules, write a function to check if it contains
conflicting rules. Two rules are conflicting if their conditions match but
values do not. Conditions can contain don't cares denoted by '-'. Has to be
done in O(n) time.

e.g
Rule Conditions Value
R1 C1,C2,C3 40
R2 BCD1,BC5 40
R3 BCD1,BC5 80
Here, R2 and R3 conflict.
e.g
R1 C1,C2,C3 40
R2 BCD1,BC5 50
R3 BCD1,- 50
R6 -,-,C3 40
No conflicts.

Q) Date: 25th March 2022 -

https://leetcode.com/problems/course-schedule-ii/

Q) Date: 25th March 2022 -

Implement a function getChar(String s, int i) which returns the ith character in s (0-

indexed).

We are interested in a special version which return a character even if i >= s.length()

getChar("abc", 1) -> 'b'

getChar("abc", 5) -> 'b'

The string should transform like below. Basically do the following => ABC + append the

same string again, just move the last char to the front

abc -> abc+c+ab -> abccab+b+abcca -> abccabbabcca+a +abccabbabcc

Q) Date: 24th March 2022 -

You are given a symbolic mathematical expression:
1+(2/3)
2*x
25.3y+(3a+c);
Design a data structure to implement this and evaluate the expression.
Note: We dont need to write the parsing code for this?
Q) Date: 23rd March 2022 -
Given points Example1: (1,2),(0,1),(2,3),(5,6),(4,5) where left one is sender and right one is
receiver. Find all the unique sender. The answer for above is (0,4). Since, first it got
originated from 0->1->2->3 and 4->5->6.

Q) Date: 18th March 2022 -

https://leetcode.com/problems/race-car/

Q) Date: 18th March 2022 -

https://leetcode.com/problems/shortest-path-in-a-grid-with-
obstacles-elimination/

Q) Date: 18th March 2022 -

https://leetcode.com/problems/maximum-number-of-visible-
points/

Q) Date: 17th March 2022 -

Design a sparse vector class with below methods

1. void SetValue(int index , int value)

2. int GetValue(int index)
3. int GetNumberOfZeros()

Q) Date: 17th March 2022 -

Given a dictionary of words (sorted lexicographically) and a prefix string, return all
the words that start with the given prefix.
Follow-up: what if the input is not sorted.
Q) Date: 17th March 2022 -
Given a n-ary tree, print the nodes in the required format.

Follow-up: given the printed string, make the tree and return the root.

Example:
1
/ | \
2 3 4
| / \ |
5 6 7 8
|
9
print the output in this format (append a dash "-" to each node value and
keep adding dashes for each level)
-1
--2
---5
--3
---6
---7
----9
--4
---8

Q) Date: 17th March 2022 -

Given a list of pair of runners [a,b] where a beats b, print all the runners in the
correct finsihing order. Simiar to https://leetcode.com/problems/course-schedule-ii/

Q) Date: 15th March 2022 -

Question
Everyone is well aware of Google Maps. We are Installing a new feature into Google
Maps. The feature would immediately output the minimum speed required to make
a trip.

You are given a sequence of distances between places in the trip. You are given a
threshold time. You need to make a trip within this time. Output the minimum
speed.

NOTE - [ Time will never be in Fractions/Decimals ]

Example :-

INPUT -

Distance - [5,6,3,9,4]

Threshold Time - 8

OUTPUT -

Explanation -

For the Distance - [5,6,3,9,4] with a minimum speed 5, I can cover 5 units distance at
0th index in 1 unit time. Can cover 6 units distance at 1st index in 2 unit time. Can
cover 3 units distance at 2nd index in 1 unit time. Can cover 9 units distance at 3rd
index in 2 unit time. Can cover 4 units distance at 4th index in 1 unit time.

Total Time Taken - 7 Units which is less than the Threshold of 8 units. So 5 unit
speed is the minimum speed possible to make the entire trip.

Q) Date: 28th Feb 2022 -

Question
We are given a list of Employees with their ID, manager ID, and Name. The question
ask us to print the names of all the employees in a hierarchy.

Note: [The Ultimate manager is the one with the highest ID Value and whose ID is
same as the Manager ID]

List of Employees INPUT:-

 { id: 8, managerId: 8, name: "Alice" },
{ id: 2, managerId: 8, name: "Bob" },
{ id: 3, managerId: 2, name: "Emp3" },
{ id: 4, managerId: 3, name: "Emp4" },
{ id: 5, managerId: 4, name: "Emp5" },
{ id: 6, managerId: 3, name: "Emp6" },
{ id: 7, managerId: 8, name: "Emp7" },
];

Output:-

// ---Bob
// ------Emp3
// ---------Emp4
// ------------Emp5
// ---------Emp6
// ---Emp7

Q) Date: 25th Feb 2022 -

implement probability(x,t) where x is an integer location on a 1d axis. we start from

x=0 with probability of 1. We can go right, left, or stay where we are at each integer

time step with probabilities p1, p2, 1-p1-p2. time increments as dt = 1. Every time

you move right, left, or stay where you are (every action), time increments 1 unit.

Q) Date: 18th Feb 2022 -

You have a list of cities and population.
Write a function that returns a random city name by the probability of its
sum of population.
For example, in the following case, NY population is 14, total is 22.
You should return NY with the probability of 14/22.

[NY, 9]
[SF, 1.5]
[Atlanta, 3]
[NY, 5]
[Boston, 1]
[SF, 3]

Q) Date: 18th Feb 2022 -

Write a FriendSuggest function for a social network

Example:
Rob - [A, B, C]
B - [A, C, D, F, Rob]
A - [B, C, D, E, Rob]
C - [A, B, J, Rob]
D - [B, A, F]
G - [H, J]
J - [H, G, K, M]

Expected Output - [D, E, F, J]

suggestFriend(‘rob’, dict_of_frnd) = [D, E, F, J]

Q) Date: 6th Feb 2022 -

https://leetcode.com/discuss/interview-question/1471821/
Google-screening-round-Job-scheduling

Q) Date: 6th Feb 2022 -

https://leetcode.com/discuss/interview-question/1673287/
Google-or-Virtual-Onsite-or-Maximum-Ancestor-for-Leaves

Q) Date: 6th Feb 2022 -

https://leetcode.com/discuss/interview-question/325845/
Google-or-Onsite-or-Decode-string

Q) Date: 5th Feb 2022 -

https://leetcode.com/problems/course-schedule/

Q) Date: 5th Feb 2022 -

https://leetcode.com/problems/maximal-square/