Sir first of all thanks to you and Kushal Sir to feel the Enviroment of a Real Interview and I can solve all the 2 Questions so I'm Happy that my Efforts are worth it!!
for the first question there is a faster approach , you have to use the sorting more efficiently, there is this O(log n+m ) solution : class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: right = len(matrix[0]) -1 bottom = len(matrix)-1 top ,left=0,0 def searchHelper(matrix,top,bottom,left,right,target,visited): if top > bottom or left > right: return False mid1=(top+bottom)//2 mid2=(left+right)//2 if (mid1,mid2) in visited : return False visited.append((mid1,mid2)) if matrix[mid1][mid2] == target : return True if matrix[mid1][mid2]>target: return searchHelper(matrix,top,bottom,left,mid2-1,target,visited) or searchHelper(matrix,top,mid1-1,left,right,target,visited) else: return searchHelper(matrix,top,bottom,mid2+1,right,target,visited) or searchHelper(matrix,mid1+1,bottom,left,right,target,visited)
Much needed videos like this! Just want to thank you for this! Telling the approach in an interview is a skill, thank you for guiding us about how to give an interview!
For the first problem, is the solution with binary search better? We can start from the middle in the mattrix, like from the centre of the quadrate and based on the value get rid from all left bottom values or right upper. Than define the middle of new quadrate and repeat a procedure. Time complexty in this case will be O(log(n*m)) which is much better.
You could have given your detailed feedback at the end of the interview then only it will be helpful for the people who are preparing for interviews. Like always ask clarifying question before start discussion the solution. I am also taking interviews at my org and find that candidate doesn't ask clarifying questions and also they just jump on coding and doesn't discuss the solution before writing the code. These are my expectations as an interviewer: 1. Candidate should ask clarifying question before discussing the approach to solve the problem. 2. Candidate should confirm with the interviewer if the approach looks good then only start the coding. 3. Candidate should think and code loudly so that if he/she get stuck then interviewer can give some hint. 4. Always try to write optimized code. 5. Never give up in an interview and seek hint/help if get stuck somewhere. don't seek more than 2 hints. 6. Consider edge cases and dry run the code with at least 2-3 test cases.
In interviews.. code is said to be written in notepad.. to see if he knows everything or not... In vs code or other softwares, autocorrect is done and auto organisation with different colours are found which makes coding easier.. in notepad we have look for all brackets and commas
I recently practiced both the questions on leetcode. You did it very well. I think in the last question . The duplicates for first loop i.e for i should be the check of arr[i] and arr[i+1]. The for loop itself will handle the last increment.
10:40 @fraz the reason you are giving that you will be able to move in two directions is a assertion not a reason. Reason is you can stand either on four corners or in between the array, inbetween you will have conflicting choices as incrementing row or col will result in bigger values and vice versa but when you start from top right or bottom left you have two non conflicting choices, if you go left you decrease, down increase and vice versa foe other situation
Instead of storing the result in set better to store all elements of array in set then there will be no possibility of repetition and no need of checking every time whether it's a duplicate triplate or no
Sir, I solved the first question in O(log (n*m)) complexity by applying Binary search in the last column and Binary Search in the row in which the target may be present.
Great video of the mock. Just one highlight point, clarifying questions can be better, for example in triplet question you could have asked do i have to return all the triplets or just one, or what return value is expected the triplet values or its indexes or just a boolean.
In interviews.. code is said to be written in notepad.. to see if he knows everything or not... In vs code or other softwares, autocorrect is done and auto organisation with different colours are found which makes coding easier.. in notepad we have look for all brackets and commas
Good video but even before starting with your brute force approach, you should have got some clarifications out of the way. Like 1. Are all elements positive? 2. Whole numbers? 3. Are all elements unique? Approaching a solution without getting all the cases and conditions is a strict no. Since this is a mock, you should be very careful in what you teach others.
i really liked this mock interview please upload more video like this it helps to prepare bhaiya can i crack the google and microsoft beacuse recently i have started learning dsa from scracth and i am in mid of the 5th sem but i am facing problem while solving questions in optimized way most of the times i watch the solution
In the first question, it should be col-=1 and row+=1, coz we are coming down to next row if target>current element else 1 col backwards? Amazing video btw
First of all thank you for making the video. I have a question for the 1st problem. If you had a matrix say 1 , 2, 3, 4 5, 7, 9, 13 6, 8, 10, 11 How would it solve if target is 11 ? Say we start from 4 , target is large and so we move down to 13, target is smaller so we move to 9, target is larger so we move down to 10 and now since the target is larger we go out of the array and return false. We just can not move around down and left .. we also need to consider when should we move right and up. And that would increase the complexity as every time the bound increases beyond the matrix limit we will need to take a decision of either to move either up or right. And in worse case I guess we will end up with m×n complexity ? Am I right ? Or may be it leads to an endless loop ..hmm
its been only a week now of me learning java and i was able to ans the first question i have learnt till arrays and wasnt aware of the concept of binary search i am sure i will learn it in the future. i am writing this message because i am just happy happy hahaha
In the first question, why not start at the middle element ? The travel distance will always be shortest no matter where your target element lies on the matrix. If you start at the corner and the element lies at the end of the diagonal, you've spent 2X more time than you would have if you started at the middle.
My one liner pythonic solution for question 2, [i for i in list(itertools.combinations(list(set(x)), 3)) if sum(list(i)) == k] P.S: This solution is only meant for fun.
If all elements in Matrix is unique then we no need to bother row and column and straightaway we can do binary search tree using a single pointer right. Am I right on this understanding?
can you get some more medium level questions next time wich are some what harder to solve so that we can get a gist of how to handle the pressure in those situation where we are not getting to the optimal solution btw nice video😀
In the first question we can apply that 2-d array binary search as well using division and mod as well .. Won't that be actually better approach if it is sorted row wise and Column wise both
hmm it won't work without this constraint "every element on one row is greater than the elements on previous rows " If this constraint was given , we can consider the 2d array as a 1d array and Bo binary search
In first question else statement says row - - which means you are going a row above but that doesn't make any sense. On the other hand where are you checking that target is present or not in that row if column[lastElement]>target.
3rd approach will be like, Apply BS on 1st column, in log(#col) time we'll have the row where we can expect target element. Then in that row again apply BS to see if element is present or not, log(#col). total TC = log(#col) + log(#row) +O(1)
If you see the question correctly this won't work Consider the matrix like this [1,3,7] [2,4,6] [8,9,10] And let target be 7 Here if you apply bs on first column, you'll get the row where ans should be present is third not first .. Your approch will be correct if there was this constraint " all the elements on one row is greater than elements from before rows"
I completed btec in ECE with 7cgpa (63%). Can i apply amazon CSA role I had seen your video on this topic and it's my aim to get a job in CSA bro please reply
Good try! Just keep in mind not to come to conclusion or provide a solution in the first minute or 2. take time to clarify and answer all questions and showcase with example before talking about your solution or complexity. just 2 cents!
It should be row++ instead of col++
Yes thanks for the correction
Yes same doubt raised to me thank you👍
Yes i also found that error
Moving backwards increments the rows,?
@@ankushmudgil9352 so smrt😅
we can also use a base case if(targ < a[0][0] || targ > a[n-1][n-1]) return false;
Sir first of all thanks to you and Kushal Sir to feel the Enviroment of a Real Interview and I can solve all the 2 Questions so I'm Happy that my Efforts are worth it!!
That's great 🔥
for the first question there is a faster approach , you have to use the sorting more efficiently, there is this O(log n+m ) solution :
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
right = len(matrix[0]) -1
bottom = len(matrix)-1
top ,left=0,0
def searchHelper(matrix,top,bottom,left,right,target,visited):
if top > bottom or left > right:
return False
mid1=(top+bottom)//2
mid2=(left+right)//2
if (mid1,mid2) in visited :
return False
visited.append((mid1,mid2))
if matrix[mid1][mid2] == target :
return True
if matrix[mid1][mid2]>target:
return searchHelper(matrix,top,bottom,left,mid2-1,target,visited) or searchHelper(matrix,top,mid1-1,left,right,target,visited)
else:
return searchHelper(matrix,top,bottom,mid2+1,right,target,visited) or searchHelper(matrix,mid1+1,bottom,left,right,target,visited)
return searchHelper(matrix,top,bottom,left,right,target,[])
using recursion is not always a good thing, but yes it can be optimized to 1 more layer using iterative approach.
Much needed videos like this!
Just want to thank you for this!
Telling the approach in an interview is a skill, thank you for guiding us about how to give an interview!
Thanks a lot for appreciating ☺️, hope it helps
For the first problem, is the solution with binary search better?
We can start from the middle in the mattrix, like from the centre of the quadrate and based on the value get rid from all left bottom values or right upper. Than define the middle of new quadrate and repeat a procedure. Time complexty in this case will be O(log(n*m)) which is much better.
Nicely explained , both problems are from this month's leetcode daily challange 😃😃
Thanks ☺️
hello ankur sharma bhai ek baat puchne thee pls are u there?
Great conversation with you Fraz, Excited for our next mock interview on my channel. ❤️🔥
Yess 🔥 , excited for your turn.
You could have given your detailed feedback at the end of the interview then only it will be helpful for the people who are preparing for interviews.
Like always ask clarifying question before start discussion the solution.
I am also taking interviews at my org and find that candidate doesn't ask clarifying questions and also they just jump on coding and doesn't discuss the solution before writing the code.
These are my expectations as an interviewer:
1. Candidate should ask clarifying question before discussing the approach to solve the problem.
2. Candidate should confirm with the interviewer if the approach looks good then only start the coding.
3. Candidate should think and code loudly so that if he/she get stuck then interviewer can give some hint.
4. Always try to write optimized code.
5. Never give up in an interview and seek hint/help if get stuck somewhere. don't seek more than 2 hints.
6. Consider edge cases and dry run the code with at least 2-3 test cases.
In interviews.. code is said to be written in notepad.. to see if he knows everything or not... In vs code or other softwares, autocorrect is done and auto organisation with different colours are found which makes coding easier.. in notepad we have look for all brackets and commas
I recently practiced both the questions on leetcode. You did it very well. I think in the last question . The duplicates for first loop i.e for i should be the check of arr[i] and arr[i+1]. The for loop itself will handle the last increment.
Yes i was doing about to the same after discussing space and time but then we concluded it
Can you send the leetcode link for these questions ?
10:40 @fraz the reason you are giving that you will be able to move in two directions is a assertion not a reason. Reason is you can stand either on four corners or in between the array, inbetween you will have conflicting choices as incrementing row or col will result in bigger values and vice versa but when you start from top right or bottom left you have two non conflicting choices, if you go left you decrease, down increase and vice versa foe other situation
Exactly 😊.
This is the reason why we can only start from top right or bottom left.
@@mohammadfraz The way you took it man hats off, shows why you have so many submissions on leetcode.
Instead of storing the result in set better to store all elements of array in set then there will be no possibility of repetition and no need of checking every time whether it's a duplicate triplate or no
I think we can reduce the for loop iterations a bit in case we have many numbers by having a condition "nums[i]
You can treat whole matrix as 1d array
Where low = 0, high = n * m - 1
And do binary search
We can find row and col like
Mid/m , mid%m res.
really helpful more similar videos would definitely boost the confidence before campus placements
Max possible min time complexity is
(Logm+logn)
If we modify the binary search
inplace of col++ will be col- - And similarly inplace of row-- will be row++
Just heard your approach and tried to code myself on LC, and it was correct in the first attempt.
Sir, I solved the first question in O(log (n*m)) complexity by applying Binary search in the last column and Binary Search in the row in which the target may be present.
Great video of the mock.
Just one highlight point, clarifying questions can be better, for example in triplet question you could have asked do i have to return all the triplets or just one, or what return value is expected the triplet values or its indexes or just a boolean.
keep doing good work👏👏like each & every video of yours. Amazing content, u r providing a great guidance to each one of us😃
Thanks a lot dolly
Microsoft Engineer using GOOGLE Docs:
Document is not important or any paper its about the concept which is required
In interviews.. code is said to be written in notepad.. to see if he knows everything or not... In vs code or other softwares, autocorrect is done and auto organisation with different colours are found which makes coding easier.. in notepad we have look for all brackets and commas
@@Nohesitation666 Yes and also indentation is an advantage in other code editors...🙂
Good video but even before starting with your brute force approach, you should have got some clarifications out of the way. Like
1. Are all elements positive?
2. Whole numbers?
3. Are all elements unique?
Approaching a solution without getting all the cases and conditions is a strict no. Since this is a mock, you should be very careful in what you teach others.
1st ques is asked in my one of interview in my placement session 😍😍
i really liked this mock interview please upload more video like this it helps to prepare
bhaiya can i crack the google and microsoft beacuse recently i have started learning dsa from scracth and i am in mid of the 5th sem but i am facing problem while solving questions in optimized way most of the times i watch the solution
We need more videos like this
Thanks ☺️
Question 1 can be solved with O(M+N) TC and constant space.
In the first question, it should be col-=1 and row+=1, coz we are coming down to next row if target>current element else 1 col backwards?
Amazing video btw
First of all thank you for making the video. I have a question for the 1st problem.
If you had a matrix say
1 , 2, 3, 4
5, 7, 9, 13
6, 8, 10, 11
How would it solve if target is 11 ?
Say we start from 4 , target is large and so we move down to 13, target is smaller so we move to 9, target is larger so we move down to 10 and now since the target is larger we go out of the array and return false.
We just can not move around down and left .. we also need to consider when should we move right and up.
And that would increase the complexity as every time the bound increases beyond the matrix limit we will need to take a decision of either to move either up or right.
And in worse case I guess we will end up with m×n complexity ?
Am I right ? Or may be it leads to an endless loop ..hmm
Hi Prajwal...the condition was both the rows and column are sorted, but the matrix you have made I see that your last column is not sorted
@@shivamjain5656 ahh yes. Thanks for pointing that out. My bad
its been only a week now of me learning java and i was able to ans the first question i have learnt till arrays and wasnt aware of the concept of binary search i am sure i will learn it in the future. i am writing this message because i am just happy happy hahaha
Wow bhaiyaa great video....
The elements to be unique was the first thing clicked in my mind😇
Thanks ☺️
ques 1 coptimized approach was actually using binary search, worst case the given by fraz in actually N2 if element is near right corner
In the first question, why not start at the middle element ?
The travel distance will always be shortest no matter where your target element lies on the matrix. If you start at the corner and the element lies at the end of the diagonal, you've spent 2X more time than you would have if you started at the middle.
If only the actual level of the questions would have been like these..
bhaiya for the second question in the 3rd while loop (nums[e]==nums[e+1])it should be e-- instead of e++.
fraz bhaiyya oo first question ka approach is really super and it's easy to understand keep sharing this knowledge bhaiyya
there should e - - instead of e ++ in loop i.e., for avoiding duplicates.😊😊😊😊😊😊😊😊😊😊😊😊
My one liner pythonic solution for question 2,
[i for i in list(itertools.combinations(list(set(x)), 3)) if sum(list(i)) == k]
P.S: This solution is only meant for fun.
If all elements in Matrix is unique then we no need to bother row and column and straightaway we can do binary search tree using a single pointer right. Am I right on this understanding?
Ohh bahi, ye question maine aaj hi kia LeetCode pe!.. logn + logm me ban jaayegi ye binary search se...
can you get some more medium level questions next time wich are some what harder to solve so that we can get a gist of how to handle the pressure in those situation where we are not getting to the optimal solution btw nice video😀
Interviewer questions bnata nahi hai kahi se utha ke hi lata hai except Google
It's great sir please upload this types of video
Thanks ☺️
In the first question we can apply that 2-d array binary search as well using division and mod as well ..
Won't that be actually better approach if it is sorted row wise and Column wise both
hmm it won't work without this constraint "every element on one row is greater than the elements on previous rows "
If this constraint was given , we can consider the 2d array as a 1d array and Bo binary search
this apply when you have the whole matrix is sorted .
can we use a membership check right..!, Weather the element is present or not.
This is a cakewalk question. Are Microsoft coding interview questions this easy ?
are these to boost confidence or microsoft really ask such easy questions ?
When was it said that the array is going to be sorted in the second question?
In first question else statement says row - - which means you are going a row above but that doesn't make any sense. On the other hand where are you checking that target is present or not in that row if column[lastElement]>target.
Keep doing more such interviews
Sure bro
this playlist is best
Please continue mock interview series
My solution: O(n logm) where nm) swap(n,m);
for (int i = 0; i < n; i++) {
int index = binary_search(arr[i], i, m, key);
if (index != -1) {
cout
ha toh basically, tu har ek array me binary search kar raha hai
I don't think they will ask these well known questions in off campus interviews
We can use hashmap with I and j variables sliding through all of them
Wow agar sachmein is level ka aata hoga microsoft ke interviews pe tab to mera mast se nikal jyega knew both the questions 😄
Great 🔥 all the best Sahil
@@mohammadfraz Thnx bhaiya 🙌 internship season shuru hone wala hai college pe july se need this all the best
Please start with an introduction
This was good, just a suggestion , it would be good if the input and output is given in docs before explaining the question by the interviewer
Sometimes interviews don't give input or output. But we can always get it clarified
@@mohammadfraz hi Fraz . Iam new to this .. what is these questions. What kind of coding is this .. is this realated to DSA?
i am not a programmer, just using my math knowledge.......!
Since the columns and rows of a matrix are sorted,
we can use conditions like
1) A1,1
Bhaiya in the first problem ie. Find element in sorted matrix ,row and col should be interchanged.
Search in a 2d matrix, 3 Sum (leetcode question)
Need more videos in similar format!!
Okay bro
The first one could be done in log(m*n). nlog(m) is not optimal.
thank you. It is my dream company to work for. Really appreciate all your efforts sir.
Easy Question puchha tumne , interview me humko tough ques q aatay hai :( But it really helped a lot to understand how interview should be.
Do we have to use google docs in actual interview also?
Nice replica 👍🏼
When we will expect the interview to be taken by you on Kushal vijay's channel that will be to awesome
Thank you bro for this type of content
3rd approach will be like,
Apply BS on 1st column, in log(#col) time we'll have the row where we can expect target element. Then in that row again apply BS to see if element is present or not, log(#col).
total TC = log(#col) + log(#row) +O(1)
If you see the question correctly this won't work
Consider the matrix like this
[1,3,7]
[2,4,6]
[8,9,10]
And let target be 7
Here if you apply bs on first column, you'll get the row where ans should be present is third not first ..
Your approch will be correct if there was this constraint " all the elements on one row is greater than elements from before rows"
Hii fraz aapko kitne coding question puche the product based company ke interview mei.can u tell
Man that 3rd approach of first question was 🔥🔥
First is not optimal log(m*n) is optimal
I was asked the exact same 1st question for my Microsoft interview :)
Faraz Sir ye live kro phir bahut acha hoga btw it was great thanks a lot
Vo bhi try karenge
very informative
Good to see Virat Kohli solving problem. haha jokes aside, amazing content. subbed!
Yeee sahi tha !
hi
you are having a great day TILL NOW ........
Wait hows the first q solution correct, he didn't even perform binary search right?
very interesting
when should i solve your sheet after completely learning dsa or while learning
it pls reply
While learning
ver informative
does top companies like microsoft accept candidates with extended education..as in b.tech completed in 6 yrs .
I didn't knew they make you write code in microsoft word? i thought we could use normal IDEs.
the 1st question is so easy i just solved it in leetcode if i were in the interview im like boom
Why Microsoft is using Google docs🤔🤔🤔🤔🤔🤔
I completed btec in ECE with 7cgpa (63%). Can i apply amazon CSA role
I had seen your video on this topic and it's my aim to get a job in CSA bro please reply
i am also a fresher in ece branch?how much do we learn related to cse there?pls Reply
wow bhaiya bhut accha experience diya like real interview
It was real only
@@mohammadfraz yes bhaiya
well.... why is it too easy 😭... i got way tougher question in workday interview than this
Interview mein leetcode wagera mein nhi hota kya coding round ?
No no , doc pe hoga mostly
pls increase your sound your sound was less and interviewer sound was good
It's just because our audio was recorded at his side
For question 1 your code is wrong.
It should be-
else if(mat[row][col] < target) row++;
else col--;
Yes
Thanks for pointing out
@@mohammadfraz aap flow flow mai galat code likh diye bhaiya 😅
1st question was good
Good try! Just keep in mind not to come to conclusion or provide a solution in the first minute or 2. take time to clarify and answer all questions and showcase with example before talking about your solution or complexity. just 2 cents!
make a video who take a job from non tech branch
Bhaiyaa i was able to solve first question 🙂
thank you so much bhaiya
You're welcome
You are doing great work bhaiya Allah Bless You 💯
Thank you 😌
Thumbnail and the question is not matching
Plz bhaiya more video upload karo
Bhaiya i am stuck in dsa i not understanding how to complete dsa in 1 month