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: 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 :
public void insertOrReplace(long index, long number)
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:
what if client number is far greater than agent number?
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 -
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
/
2 3
/ \ /
4 5 6 7
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
/
2 3
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
- likes = [1,2,2] Output 2 (Because there are 2 post with 2 likes)
- 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
void SetValue(int index , int value)
int GetValue(int index)
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 -
5
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/