🔴 Google Coding Interview with ex-Facebook ex-Stanford Co-Founder || Software Engineering Interview
Вставка
- Опубліковано 14 жов 2024
- ✅15% extra discount on CodingNinjas courses 👉🏻 bit.ly/codingn...
✅New UA-cam Account - Developer Bhaiya 👉🏻bit.ly/develop...
Have you ever wondered how Google Interviews work?
Would you like to watch how Rachit might perform in a real life Coding Interview?
Had a 45 minute fun mock interview session with Ankush Singla! This is our first collaboration together and we hope you all enjoy the video 😁
#SoftwareEngineering #Google #CodingInterview
𝗦𝗢𝗖𝗜𝗔𝗟 𝗣𝗥𝗢𝗙𝗜𝗟𝗘𝗦
✅ Portfolio Website - rachitiitr.com
✅ Instagram - / rachitiitr
✅ LinkedIn - / rachitiitr
✅ Twitter - / rachitiitr
✅ Github - github.com/rac...
✅ Facebook - Algorith...
𝗜𝗠𝗣𝗢𝗥𝗧𝗔𝗡𝗧 𝗣𝗟𝗔𝗬𝗟𝗜𝗦𝗧𝗦
✅ 𝗖𝗼𝗱𝗶𝗻𝗴 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄 𝗟𝗲𝗰𝘁𝘂𝗿𝗲𝘀 👉🏻 • Day 3: Coding Intervie...
✅ 𝗚𝗿𝗮𝗽𝗵 𝗧𝗵𝗲𝗼𝗿𝘆 𝗣𝗹𝗮𝘆𝗹𝗶𝘀𝘁 👉🏻 • Graph Theory and Algor...
✅ 𝗖++ 𝗦𝗧𝗟 𝗣𝗹𝗮𝘆𝗹𝗶𝘀𝘁 👉🏻 • The Best Demo on C++ S...
✅ 𝗠𝘆 𝗣𝗲𝗿𝘀𝗼𝗻𝗮𝗹 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄 𝗘𝘅𝗽𝗲𝗿𝗶𝗲𝗻𝗰𝗲𝘀 👉🏻 • Uber SDE II Interview ...
✅𝗣𝗿𝗼𝗱𝘂𝗰𝘁𝗶𝘃𝗶𝘁𝘆 𝗧𝗶𝗽𝘀 𝗣𝗹𝗮𝘆𝗹𝗶𝘀𝘁 👉🏻 • Uber SDE II Interview ...
✅𝗟𝗶𝗳𝗲 𝗟𝗲𝘀𝘀𝗼𝗻𝘀 & 𝗠𝗲𝗻𝘁𝗼𝗿𝘀𝗵𝗶𝗽 👉🏻 • Why I Chose To Become ...
𝗣𝗥𝗢𝗚𝗥𝗔𝗠𝗠𝗜𝗡𝗚 𝗣𝗥𝗢𝗙𝗜𝗟𝗘𝗦
✅ Github ► github.com/rac...
✅ Programming Blog ► rachitiitr.blog...
✅ CodeForces ► www.codeforces....
✅ CodeChef ► www.codechef.co...
He just solved 2 random interview questions with such speed and clarity in 40 mins 🙏🏻
It takes me 40 mins to make the mindset of coming out of my bed and write code.
This simply means software engineering is not for ,half of the public is running behind money
He already solve it many times
@@rahuljoshi5952 he is from electrical branch why he is doing software all are doing for money. We study to earn money.
I take a lot of time in coming up with good variable names is a perfect way of saying don't judge me based on variable names 😄
Alternative simpler breakdown:
Get the longest increasing subsequence (one pass) ...
- 5, 8, 14
Then find the intermediate sums in next iteration like (one pass) ...
- 4, 5, 0, 8, 22, 14, 0
- 2, 5, 13, 8, 24, 14, 33
Add the max of intermediate values (one pass) ...
- 4, 5, 13, 8, 24, 14, 33
Finally I understood Im way back in this competitive world 😢
The first question can be done in O(n) time and O(1) space using two pointers approach. Something similar to that of merging two sorted arrays. I've myself coded this problem and works completely fine.
exactly its just a variation of finding intersection points in two sorted arrays
here is the java code
void solve(){
int[]a = {1,3,5,8,10,12,14};
int[]b = {2,5,6,7,8,11,13,14,16,17};
int s1=0,s2=0, i=0, j=0;
int m = a.length, n = b.length;
while(i
in first question you can just use two pointer starting from both array start if and increment the pointer if that element is smaller than other and just keep on adding the elements while you move when the two pointer's become same it means its an intersection now just take max of both sums and make both sums 0 O(N) time and O(1) space
I think exactly same bcz i dont know dp now😂
You are missing lot of potetial cases, think about it for a minute and try to dry run this approach on a little bigger input...I'm sure you can understand why this is not possible by your approach :)
--you gotta check all combination you can make around the intersection points
@@chhotu4205 can you give a test case where this approach fails bro
@@chhotu4205 question is 2 sorted arrays with no repeating elements mean that can be view as two road that are interlinked at some points for finding max distance we can travel from start to end this approach seems pretty good actually
@@thebesthrithik254
1. how will you decide how much we move forword with both pointers in each array
2. there will be multiple branch at every incoming intersection
ok try the dry run on the input:
arr1: 1 7 6 18 34 37 85
arr2: 18 19 34 31 85
dont do this in your mind
do this on paper
see changes at every step ( according to you, there will be only n steps)
i tried and i find it not working
it may be the case that I didn't undrsatand your solution as you wanted to implement.
Rachit no doubt you did this great. But this maximise sum question would require only single iteration O(n). As the arrays are sorted, we can iterate through the arrays and maintain the sum to each array till any intersection.
sum_a and sum_b, where we would check on interesection, if(sum_a > sum_b) max += sum_a else max += sumb
Like this. and we would keep on working on working on these sum_a and sum_b till intersection and then resetting them to 0. This is how the question would not require the DP.
Yeah even I was also wondering why DP came into picture....
This is also working perfectly fine, right ?
No dynamic programming and recursion required
def maxSum(a, b):
# O(m+n)
intersection = set(a) & set(b)
n, m = len(a), len(b)
max_sum = sum(intersection)
i, j = 0, 0
sumA, sumB = -1, -1
while sumA or sumB:
sumA, sumB = 0, 0
while i < n:
if a[i] in intersection:
i += 1
break
sumA += a[i]
i += 1
while j < m:
if b[j] in intersection:
j += 1
break
sumB += b[j]
j += 1
max_sum += max(sumB, sumA)
return max_sum
I had a similar solution in my mind, I'm a c++ guy, so no way of finding intersection as simple as you did, but I guess we can solve the first question in just one iteration, just find sumA sumB until every intersection as you see that you're at the intersection say at number 5, find which of the sum so far is greater sumA or sumB and choose the maximum one, then proceed find the endt intersection and add the maximum sum so on...
This requires just one iteration and O(1) solution
yup
@@priyadharshanravichandran4483 not o(1) it's o (n)
@@sadhlife sorry meant to say o(1) space, I said 1 iteration as O(n)
was able to solve this question with simple while loop (iterating through the arrays and calculating the sum and when found a intersection making a switch)
const arr1 = [1,3,5,8,10,12,14]
const arr2 = [2,5,6,7,8,11,13,14,16,17]
let sum1=0;
let sum2=0;
let final=0;
let i=0;
let j=0;
while(i< arr1.length && j < arr2.length){
if(arr1[i] < arr2[j]) sum1+=arr1[i++];
if(arr1[i] > arr2[j]) sum2+=arr2[j++];
if(arr1[i]==arr2[j]){
sum1+=arr1[i++]
sum2+=arr2[j++]
final+=Math.max(sum1,sum2);
sum1=0;
sum2=0;
}
}
while(i
Bro please please do more of these kind of videos. It seriously helped me a lot. Thank you once again. And yes , You're a genius!! Your approach makes the problem look easy. Great!
He is happy listening to 2 nd question because he has solved it on leetcode LOL 😂..
Lol
These people are next level.
This was dope ! The way you interacted (while thinking behind the scenes) was truly commendable :) Learnt a lot again ❤
Indeed
Ankush sir is my favorite teacher and always help me , 😍😍
True
@Rachit This is my python one liner 😎 :
one_liner = lambda rec_str, digits: rec_str if digits%10
nice lol
I think the first question can be done in O(n) time and O(1) space and the second question can be done iteratively using queues.
How can you save space while maintaining time as linear? Can you explain your approach in brief? Thank you!
@@amanpratapsingh1243 Will this suffice?
int firstSum = 0, secondSum = 0, totalSum = 0;
int firstPtr = 0, secondPtr = 0;
int sz1 = nums1.size(), sz2 = nums2.size();
while(firstPtr
Amazing mock interview 😃
I myself have learned a lot from Ankush. Best mentor ever❤️
When will you open a branch in ghaziabad??
the second question based on words that can be generated through keypad one is the most common question and most of us has already came across that one
I have just started coding and I thought of this solution:
Why not just create a code that compares the sums between each switch and on that basis decides whether to make a switch or not
I thought the same, should be working.
doesn't work because here you are only comparing the sums we get till that point in each array individually. But you can't guarantee that at that intersection point, the sum you gathered in that array is optimal. It may be the case that at an intersection point i, the best sum is formed by switching between the two arrays.
@@ElonMusk-ez5xz Not the total sum, He means the sum between two intersection points.
@@Chandresh1571998 Ah I see, that will work I think. Good approach!
Second Question Python Simple Implementation:
def solve(number):
keyPad = {2: ['a','b','c'], 3: ['d','e','f'],
4: ['g','h','i'], 5:['j','k','l'],
6: ['m','n','o'], 7: ['p','q','r','s'],
8: ['t','u','v'], 9: ['w','x','y','z']}
numberString = str(number)
if len(numberString) == 0 or int(numberString[0]) < 2:
return []
result = keyPad[int(numberString[0])]
for number in numberString[1:]:
oldResult = result
newResult = []
if int(number) < 2:
return []
for r in oldResult:
for char in keyPad[int(number)]:
newResult.append(r + char)
result = newResult
return result
I thoroughly loved it. You’re brilliant Rachit.
Greedy way of solving the first question:
Make two arrays corresponding to the sum of segments which can be traversed in one array, before encountering the common element, for the given example it will be
Arr1: [9, 8, 36, 0]
Arr2: [7, 21, 38, 33]
After this we can just traverse these two arrays and selecting max element at each index viz:
for each i in (0,n) sum += max(Arr1[i], Arr2[i])
which will yield the answer. Let me know if there is any flaw in this solution.
looks cool! thought the same!
1st can also be done by prefix sums greedily
Coding ninjas course was my life changer, from noob to good coder, thanks ankush sir😍😍😍
One warning:
Questions featured in the video are just for illustration and bear no resemblance with the level of problems, actually asked.
The purpose of the video is just to demonstrate how to communicate yourself and manage your time.
FB asked Ankush the second problem
What do u mean the level is below or above in real interview?
Hello rachit. Isn't the second problem's base case wrong ? basically starting from base case , any of the upper level cases will always return empty vector isn't it ?
Should the base case be improved ? at the place where recursive calls are made and a for loop is run on "rem" variable ?
@@kaushiksrinivas3658 yes, you are right. base case has to be improved, else you get an empty vector
First Question Simple Solution in Python. I have only watched the first 5 mins. Haven't watch Rachit Solution. Space Complexity is O(max(n,m)) where n is the length of first Array and m is the length of second Array. Time Complexity is O(n + m).
def solve(firstArray, secondArray):
firstArrayCounter = set()
for i in range(0,len(firstArray)):
firstArrayCounter.add(firstArray[i])
intersectionPoints = set()
for i in range(0,len(secondArray)):
if secondArray[i] in firstArrayCounter:
intersectionPoints.add(secondArray[i])
sumOfIntersection = 0
i = 0
j = 0
firstSum = 0
secondSum = 0
while i < len(firstArray) and j < len(secondArray):
if firstArray[i] in intersectionPoints and secondArray[j] in intersectionPoints:
sumOfIntersection += max(firstSum, secondSum) + firstArray[i]
firstSum = 0
secondSum = 0
i += 1
j += 1
elif firstArray[i] not in intersectionPoints:
firstSum += firstArray[i]
i += 1
elif secondArray[j] not in intersectionPoints:
secondSum += secondArray[j]
j += 1
while i < len(firstArray):
sumOfIntersection += firstArray[i]
i += 1
while j < len(secondArray):
sumOfIntersection += secondArray[j]
j += 1
return sumOfIntersection
Ankush Sir is great teacher, mentor. He could make hard questions looks easier..Really love his teaching style
Sir is standing whole time during the interview, that's the kind of hardwork and patience is needed and its quite good for health.
Not so hard questions, or very noob questions, but still helped for how to behave
Why can't we converting original array to :
5 8 14
5 8 14
Time: O(N)
Basically second question is based on permutations so I'll use heaps algorithm for permutation.
If somehow I'm wrong please reply
Hello Rachit, Just one query , can you please help me if i can use spark programming to generally solve the problems... Is it generally industry accepted & is considered an enterprise solution. Thank you. 1) Create both the list as RDD's , Create a df join with rownum join both the df's then write a case to get the equal to rdd1 & rdd2 then we get the rownum prep the final list & sum 2) load the table with the chars , then we do a cross join. will give all possible chars.
Do you think we need dp in the first question? we can easily solve it by just traversing both arrays just keep the sum of both arrays from one intersection to other and just add max of both to result. As simple as that.
for the first question we can use 2 array whose size will be equal to no. of intersection and that will store the sum before each intersection
I did the second question today using maps and recursion combined... pretty Glad to solve it 😊😊
import math
import sys
for line in sys.stdin:
line.strip()
n=int(line.strip())
for i in range(1,n+1):
if i % 3==0: and i % 5==0:
print("FizzBuzz")
elif i % 3==0:
print("Fizz")
elif i % 5==0:
print("Buzz")
else:
print(i)
We can do the first question by keeping the prefix sums at each index and then looping through all the inter section points and then doing the dp for each intersection index
I feel like you seem to know everything already, the way you explained what to use for the DP
Give a man a course you feed him for the day
Teach a man to google and you feed him for life
Nice video!! really enjoyed it
First by two pointer method i,j index of respective arrays of which ever smaller move pointer of that if intersection cal subarray sum till that point which ever max add along with common number into total sum. I don't think we need recursion here.
Even I was thinking the same..no need of recursion..just a for loop and use two pointers
@@deveshbahuguna6148 yes we can use something like merge operation of merge sort and keep sum of both arrays and which ever is Max keep that and repeat same process
Questions were good but Google would have asked for iterative solution for dp problem.
Great video Sir👍👍
I will definitely recommend this video to all my colleagues.
I also like the way you explain approach to the interviewer.
Communication is pretty good
It doesn't happen as you said 'Interviewer is just knowing your thought process'. In one of my microsoft interview, interviewer asked me to run the code. My algorithm was correct, but it was just simple mistake it did not run for large dataset, he failed me there. These companies saying that we just want to know candidate's thought process, but in real life it doesn't happen.
Others: Nice nice, keep doing similar videos
Me: LoL, He is watching Seinfeld over Prime in tab 1
It must be very hard for you to pass 1 hour on these easy questions. Anyways, I hope I get these types of questions in my interview too.
this Thinking Out Loud stuff is good 👍
In first problem, can we use two pointers and start from the right?
Initially both pointers pointing to last elements and you move the pointer left with higher number
as soon as both pointer have same number, you decide what is the sum of numbers between previous intersection and current. and you add max in ans.
Thank-god, I found someone with some thoughts of mine :/
Are these problems (specifically 1st one) available on any platform? I wanted to test one solution but couldn't find it online.
Similar to train problem dp( forgot the exact name)
rachit says we dont have much time in second question and then he writes code from scratch like he is typing an essay
for the 1st question, as the numbers are unique in two arrays and we are always moving forward in the recursive function, how can we have overlapping subproblems? could you please provide a proper test case for this?
Its not about the numbers in the array. Its about the index position (the common ones) that you can reach through multiple ways and that is what we can keep a track of.
dp[array_num][index_num]
1st: 1 2 3 4 5 6 7 8 9 10 11. 2nd: 1 2 3 4 5 6 7 8 9 10 11 12
can you tell what will be the condition when you make a switch and when you not .....
31: 09 That's when python's itertools comes into play.
Please correct thumbnail sir it said ex-facebook cofounder quite misleading you know..anyways a fine channel this is
Ankush Sir Op❤️
in the second problem you showed that you have been out of the game for a while now
super awesome!!
Ankush sir is my favourite teacher
muje to question dekh ke chakkar ajata hai and me solve nai kar pata in any test / interview
Thinking !
Both of them were easy !
10:15 is the toughest part for me, and it was explained like it was nothing...
Awesome👍🏻
Why this was A Google interview and not Facebook or Amazon??
2nd question was too easy
time complexity and space complexity for second problem? And could you please make a video on memoisation.
For a given input of length N, we have around 3-4 choices available for every position. So at max you have 4^N possible choices that you will be returning. Each choice will have a length N. This makes the time complexity and space complexity to O(4^N * N) in worst case.
Great way of promotion
mein coding ninjas par DSA ka course kar raha hun XD
kasa ha ?
So you wanna be a software engineer at Google?
Do you know what the scariest thing in the world is?
@@amanpratapsingh1243 Not knowing how to Invert a binary tree in a coding interview.
First question is a leetcode question
1st question can be easily done with a greedy approach.
I want to become coder like you☺️
Coding ninjas sales are reduced😂 now no one is taking courses😂
how do you know?
@@shivamhooda3388 do some research 😂
First ques was tricky😶
Please make a detailed video for second problem.
I couldn't understand it.
I'll be waiting for the solution bro.
This qn is in leetcode...u can go check the discussion for really nice solutions
Very common problem check UA-cam
I want to see how to implement memoization in first problem
ex stanford ? xd