Google Cracker Sheet
 Home
 Google Cracker Sheet
How To Crack Google
Last 6 Months Questions
You are given a 2D integer array logs
where each logs[i] = [birth
_{i}, death
_{i}]
indicates the birth and death years of the i
^{th} person.
The population of some year x
is the number of people alive during that year. The i
^{th} person is counted in year x
‘s population if x
is in the inclusive range [birth
_{i}, death
_{i}  1]
. Note that the person is not counted in the year that they die.
Return the earliest year with the maximum population.
Example 1:
Input:
logs = [[1993,1999],[2000,2010]]
Output:
1993
Explanation:
The maximum population is 1, and 1993 is the earliest year with this population.
Example 2:
Input:
logs = [[1950,1961],[1960,1971],[1970,1981]]
Output:
1960
Explanation:
The maximum population is 2, and it had happened in years 1960 and 1970. The earlier year between them is 1960.
Constraints:
1 <= logs.length <= 100
1950 <= birth
_{i}< death
_{i}<= 2050
Given a hierarchy of managers, as a tree, with every mode value is the salary of the manager, find out the number of managers underpaid.
How are they underpaid? if salary of manager is lesser than the average of its children nodes salary.
You are given an array of words
where each word consists of lowercase English letters.
word
_{A} is a predecessor of word
_{B} if and only if we can insert exactly one letter anywhere in word
_{A} without changing the order of the other characters to make it equal to word
_{B}.
 For example,
"abc"
is a predecessor of"abac"
, while"cba"
is not a predecessor of"bcad"
.
A word chain is a sequence of words [word
_{1}, word
_{2}, ..., word
_{k}]
with k >= 1
, where word
_{1} is a predecessor of word
_{2}, word
_{2} is a predecessor of word
_{3}, and so on. A single word is trivially a word chain with k == 1
.
Return the length of the longest possible word chain with words chosen from the given list of words
.
Example 1:
Input:
words = ["a","b","ba","bca","bda","bdca"]
Output:
4
Explanation
: One of the longest word chains is ["a","ba","bda","bdca"].
Example 2:
Input:
words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output:
5
Explanation:
All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
Example 3:
Input:
words = ["abcd","dbqca"]
Output:
1
Explanation:
The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i]
only consists of lowercase English letters.
Given the water capacity for each of n unmarked buckets in the form of an array, find all the ways a target quantity of water can be measured. Eg, buckets = [3,5] Target = 4. Output : (+5,+5,3,3), (+3,+3,+35) etc..
You are given an array A of N nonnegative integers and an integer K. You can perform the following operation on this given array any number of times:
• Choose an index i (1<=i<=N), and increase the element at this index by 1
Task Determine the minimum number of operations that needs to be performed, so that every subarray of size 3 or more has a maximum element, greater than or equal to K .
Example:
n=4
k=5
a = [2,1,1,3]
ans = 4
Given an m x n
binary matrix
filled with 0
‘s and 1
‘s, find the largest square containing only 1
‘s and return its area.
Example 1:
Input:
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output:
4
Example 2:
Input:
matrix = [["0","1"],["1","0"]]
Output:
1
Example 3:
Input:
matrix = [["0"]]
Output:
0
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j]
is'0'
or'1'
.
For every nonroot node in a binary tree, return the new height of the binary tree if the subtree rooted at that node were deleted.You are given a pointer to the root of the tree, you need to return a list of pair of integers {X, F(X)} for every node X in the given tree. Here, F(X) represents the updated height of the original tree if the subtree rooted at node X is deleted.
The order of the elements in the result list doesn’t matter.
In the following example, X = 5 i.e. subtree rooted at node 5 is deleted.
height: 3 height: 2
1 1
/\\ /\\
2 3 ===> 2 3
/\\ /
4 5 4
\\
6
The goal is to compute this for all nonroot nodes and thus arrive at: [{2, 3}, {3, 1}, {4, 3}, {5, 2}, {6, 2}].
Paul Miller loves to solve puzzles, and this time, he gets himself into a rectangular maze of size MxN. Paul Miller starts from the cell (1, 1) and needs to exit at cell (X, Y). He can move 1 unit up, down, left, right, in 1 unit of time. Some cells in the grid are blocked represented by 1, and the rest are free to move from represented by 0. Starting cell is never blocked at the beginning. State of some cells toggles, i.e., if the cell was blocked, it becomes open and vice versa. Location of the cell and times (maybe multiple for a cell) at which it toggles is known to Paul Miller right from the start.
Task
Determine the minimum time required by Paul Miller to exit the maze. If he never exits, print Mission Impossible.
Notes
1based indexing is followed.
Toggle time is negligible i.e state of any cell changes immediately at the time mentioned.
Examples
Example 1
Consider a grid of 1×3 cells with exit at (1, 3), no toggles, and no blocked cells.
The minimum time required to exit the maze at (1, 3) is 2.
Example 2
Consider a grid of 1×3 cells with exit at (1, 3), with the cell (1, 2) blocked and no toggles.
Since there is no way out.
So the answer is “Mission Impossible”.
Example 3
Consider a grid of 1×3 cells with exit at (1, 3) and no blocked cell initially. Only cell (1, 2) toggles after 2 unit time.
The minimum time required is to exit the maze at (1, 3) is 2.
Definition of Variables
M: Represents the number of rows in the maze
N: Represents the number of columns in the maze
X: Represents xcoordinate of an exit gate
Y: Represents ycoordinate of an exit gate
T: Represents the number of toggles
maze: Represents a 2D matrix of size MxN
toggle: Represents a 2D array of size Tx3 where each row contains 3 integers u,v, and w, where (u, v) represents the cell, and w represents the time of toggle at that cell
Given an array of strings words
and a width maxWidth
, format the text such that each line has exactly maxWidth
characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' '
when necessary so that each line has exactly maxWidth
characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be leftjustified, and no extra space is inserted between words.
Note:
 A word is defined as a character sequence consisting of nonspace characters only.
 Each word’s length is guaranteed to be greater than
0
and not exceedmaxWidth
.  The input array
words
contains at least one word.
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[ "This is an", "example of text", "justification. " ]
Example 2:
Input:
words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[ "What must be", "acknowledgment ", "shall be " ]
Explanation:
Note that the last line is "shall be " instead of "shall be", because the last line must be leftjustified instead of fullyjustified. Note that the second line is also leftjustified because it contains only one word.
Example 3:
Input:
words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
Constraints:
1 <= words.length <= 300
1 <= words[i].length <= 20
words[i]
consists of only English letters and symbols.1 <= maxWidth <= 100
words[i].length <= maxWidth
You have a stream of integer, implement the following two methods to return the median value (value of the middle. It’s not the mean). The median value does not need to be exact. It can be within a range of 2^n1 to 2^n+1.
For example:
addValue(1)
addValue(6)
addValue(10)
getMedian() can return any value between 4 to 7.
We're given a Grid that is initially empty. Now, we want to play a game on it by placing the character 'X'.
Each time, we can place an 'X' at one of the coordinates in the grid (i, j) and we need to return whether the game has ended or not.
The game is considered to be won when there exists an 'X' path from the first column of the grid to the last column.
We need to efficiently play this game now.
For a path to be winning, we need to consider only the elements in the 4 directions from it...i.e. we can't take up the diagonal elements.
E.g.,
X _ _ _
_ X X X
_ X X _
_ _ _ _
_ X _ _
_ _ _ _
In the above grid, we can see that there is a diagonal path but diagonal paths aren't considered valid and the game isn't ended at that point of time. In the above grid itself, if we now place a new 'X' at (0, 1) index, we'll have the below grid
X X _ _
_ X X X
_ X X _
_ _ _ _
_ X _ _
_ _ _ _
And now we can go from the leftmost column to the rightmost column traversing only via X's.
E.g.,
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.
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).
Constraints :
N,M<=5000
MAX(ai,bi) <=5000
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.
Given N, K and array A length of N and contains nonnegative 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 ith 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.
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.
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'
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
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
You are given the following:
 Integers
n
,c
,d
 Array a as
{a1, a2, ..., an}
of lengthn
 Array b as
{b1, b2, ..., bn}
of lengthn
Task
Determine the number of pairs i
, j
(1 <= i < j <= n
), satisfying the inequalityai  aj + c <= bi  bj + d
Constraints1 <= T <= 10
2 <= n <= 2.10^5
0 <= c, d <= 100
1 <= ai, bi <= 10^9
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<= 2×10^3
1<= m<= n
1<=k<=n
Test cases
n = 9
m= 2
k = 3
s = '232387421'
So there are total 3 ways possible
You are given an n x n
integer matrix grid
where each value grid[i][j]
represents the elevation at that point (i, j)
.
The rain starts to fall. At time t
, the depth of the water everywhere is t
. You can swim from a square to another 4directionally adjacent square if and only if the elevation of both squares individually are at most t
. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square (n  1, n  1)
if you start at the top left square (0, 0)
.
Example 1:
Input: grid = [[0,2],[1,3]] Output: 3 Explanation: At time 0, you are in grid location (0, 0). You cannot go anywhere else because 4directionally adjacent neighbors have a higher elevation than t = 0. You cannot reach point (1, 1) until time 3. When the depth of water is 3, we can swim anywhere inside the grid.
Example 2:
Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] Output: 16 Explanation: The final route is shown. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^{2}
 Each value
grid[i][j]
is unique.
Follow Up – Can Move in All 4 directions
Given an input string, return an output string such that all the lower case characters should be sorted. Indices of nonlower case characters should remain the same as in the original input string.
Eg. Input > ‘Test@123 Google’
Output > ‘Teeg@123 Gloost’
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.
Given a string s, return the length of longest substring such that every character in the substring has equal number of occurance.
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() {
}
}
Given a horizontal line, you have to paint coordinates and tell the amount of paint required at every step.
Ex – [(4, 10), (7, 13), (20, 30)]
ans – [6, 3, 10]
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 index6
).  We can replace element at index
3
with number2
so now array will bea = [1,2,2,2,2,2,2,4]
, maximum number of contiguous elements will be 6 (from index1
to index6
).  For last replacement, we can replace either element at index
0
or index7
with number2
, so maximum number of contiguous elements will be7
, which is the answer.
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.
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +
, 
, *
, and /
. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Example 1:
Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * 11))) + 17) + 5 = ((10 * (6 / (12 * 11))) + 17) + 5 = ((10 * (6 / 132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Constraints:
1 <= tokens.length <= 10^{4}
tokens[i]
is either an operator:"+"
,""
,"*"
, or"/"
, or an integer in the range[200, 200]
.
You are a hiker preparing for an upcoming hike. You are given heights
, a 2D array of size rows x columns
, where heights[row][col]
represents the height of cell (row, col)
. You are situated in the topleft cell, (0, 0)
, and you hope to travel to the bottomright cell, (rows1, columns1)
(i.e., 0indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the topleft cell to the bottomright cell.
Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2 Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1 Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] Output: 0 Explanation: This route does not require any effort.
Constraints:
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^{6}
Given a m x n
matrix mat
and an integer threshold
, return the maximum sidelength of a square with a sum less than or equal to threshold
or return 0
if there is no such square.
Example 1:
Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 Output: 2 Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 Output: 0
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10^{4}
0 <= threshold <= 10^{5}
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
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.
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.
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?
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)
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
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.
Design a game 5×5. 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
Give a string, for example : input : a(b+c+b) output : a2bc.
Remove Leaves of Binary Tree , like (366. Find Leaves of Binary Tree) , but need remove
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
A binary tree, return all roottonode paths. For example,
1
/ \
2 3
\
5
return : [“1″,”12″,”125″,”13”]
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.
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root
of a binary tree, return the maximum path sum of any nonempty path.
Example 1:
Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 > 1 > 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 > 20 > 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
 The number of nodes in the tree is in the range
[1, 3 * 10^{4}]
. 1000 <= Node.val <= 1000
Follow up – Find the Maximum Path sum of the path with the exact length of K.
Given a sorted integer array arr
, two integers k
and x
, return the k
closest integers to x
in the array. The result should also be sorted in ascending order.
An integer a
is closer to x
than an integer b
if:
a  x < b  x
, ora  x == b  x
anda < b
Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]
Example 2:
Input: arr = [1,2,3,4,5], k = 4, x = 1 Output: [1,2,3,4]
Constraints:
1 <= k <= arr.length
1 <= arr.length <= 10^{4}
arr
is sorted in ascending order.10^{4} <= arr[i], x <= 10^{4}
Given two integer arrays nums1
and nums2
, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Explanation: [4,9] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
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)
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.
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.
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses  1
. You are given an array prerequisites
where prerequisites[i] = [a_{i}, b_{i}]
indicates that you must take course b_{i}
first if you want to take course a_{i}
.
 For example, the pair
[0, 1]
, indicates that to take course0
you have to first take course1
.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = [] Output: [0]
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses  1)
prerequisites[i].length == 2
0 <= a_{i}, b_{i} < numCourses
a_{i} != b_{i}
 All the pairs
[a_{i}, b_{i}]
are distinct.
Implement a function getChar(String s, int i) which returns the ith character in s (0indexed).
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
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?
Your car starts at position 0
and speed +1
on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A'
(accelerate) and 'R'
(reverse):
 When you get an instruction
'A'
, your car does the following:position += speed
speed *= 2
 When you get an instruction
'R'
, your car does the following: If your speed is positive then
speed = 1
 otherwise
speed = 1
 If your speed is positive then
For example, after commands "AAR"
, your car goes to positions 0 > 1 > 3 > 3
, and your speed goes to 1 > 2 > 4 > 1
.
Given a target position target
, return the length of the shortest sequence of instructions to get there.
Example 1:
Input: target = 3 Output: 2 Explanation: The shortest instruction sequence is "AA". Your position goes from 0 > 1 > 3.
Example 2:
Input: target = 6 Output: 5 Explanation: The shortest instruction sequence is "AAARA". Your position goes from 0 > 1 > 3 > 7 > 7 > 6.
Constraints:
1 <= target <= 10^{4}
You are given an m x n
integer matrix grid
where each cell is either 0
(empty) or 1
(obstacle). You can move up, down, left, or right from and to an empty cell in one step.
Return the minimum number of steps to walk from the upper left corner (0, 0)
to the lower right corner (m  1, n  1)
given that you can eliminate at most k
obstacles. If it is not possible to find such walk return 1
.
Example 1:
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1 Output: 6 Explanation: The shortest path without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) > (0,1) > (0,2) > (1,2) > (2,2) > (3,2) > (4,2).
Example 2:
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: 1 Explanation: We need to eliminate at least two obstacles to find such a walk.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 40
1 <= k <= m * n
grid[i][j]
is either0
or1
.grid[0][0] == grid[m  1][n  1] == 0
You are given an array points
, an integer angle
, and your location
, where location = [pos_{x}, pos_{y}]
and points[i] = [x_{i}, y_{i}]
both denote integral coordinates on the XY plane.
Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, pos_{x}
and pos_{y}
cannot be changed. Your field of view in degrees is represented by angle
, determining how wide you can see from any given view direction. Let d
be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d  angle/2, d + angle/2]
.
You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.
There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.
Return the maximum number of points you can see.
Example 1:
Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1] Output: 3 Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
Example 2:
Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1] Output: 4 Explanation: All points can be made visible in your field of view, including the one at your location.
Example 3:
Input: points = [[1,0],[2,1]], angle = 13, location = [1,1] Output: 1 Explanation: You can only see one of the two points, as shown above.
Constraints:
1 <= points.length <= 10^{5}
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= pos_{x}, pos_{y}, x_{i}, y_{i} <= 100
Design a sparse vector class with below methods
 void SetValue(int index , int value)
 int GetValue(int index)
 int GetNumberOfZeros()
Given a dictionary of words (sorted lexicographically) and a prefix string, return all the words that start with the given prefix.
Followup: What if the input is not sorted?
Given a nary tree, print the nodes in the required format.
Followup: 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
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses  1
. You are given an array prerequisites
where prerequisites[i] = [a_{i}, b_{i}]
indicates that you must take course b_{i}
first if you want to take course a_{i}
.
 For example, the pair
[0, 1]
, indicates that to take course0
you have to first take course1
.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = [] Output: [0]
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses  1)
prerequisites[i].length == 2
0 <= a_{i}, b_{i} < numCourses
a_{i} != b_{i}
 All the pairs
[a_{i}, b_{i}]
are distinct.
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.
Complete Video Explanation – https://www.youtube.com/watch?v=0BRq4GuGqCo