Mock Coding Interview with
Vložit
- čas přidán 24. 07. 2024
- Have been thinking of interviewing this guy since quite some time! Asked him a hard question to really challenge him and he came up with quite different solution than what I had thought of or seen before. I hope the video is interesting to watch. Do let us know in the comments!
Thank you @iamluv fir doing this!!
Use this link to check out CodingNinjas courses - bit.ly/3iAjsCv
The video contains following parts-
0:00-0:13 - Introduction
0:13-0:48 - CodingNinjas Promotion
0:48-2:20 - Question
2:20-22:40 - Solution build up and thought process with dry run
22:40-28:00 - Discussion to try space optimisation
28:00-36:40 - Code
36:40-38:48 - Corner Case that we both missed
38:48-40:15 - Feedback
You can get 𝐃𝐈𝐒𝐂𝐎𝐔𝐍𝐓𝐒 using code "KEERTI" -
➡️ On 𝐂𝐨𝐝𝐢𝐧𝐠 𝐍𝐢𝐧𝐣𝐚𝐬 - bit.ly/CodingNinjas-12
➡️ On 𝐈𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰𝐑𝐞𝐚𝐝𝐲 - get.interviewready.io/?_aff=K...
➡️ On 𝐄𝐝𝐮𝐜𝐚𝐭𝐢𝐯𝐞 - educative.io/keerti
➡️ On all 𝐆𝐞𝐞𝐤𝐬𝐅𝐨𝐫𝐆𝐞𝐞𝐤𝐬 paid courses - practice.geeksforgeeks.org/co...
You can also connect with me on-
𝐈𝐧𝐬𝐭𝐚𝐠𝐫𝐚𝐦 (for not so professional, chill side of my life) - keerti.purs...
𝐓𝐞𝐥𝐞𝐠𝐫𝐚𝐦 Channel - t.me/keertipurswani
𝐓𝐰𝐢𝐭𝐭𝐞𝐫 - KeertiPurswani?s=09
𝐋𝐢𝐧𝐤𝐞𝐝𝐈𝐧 - / keertipurswani
#MockInterview #CompetitiveProgramming #interview #preparation
"yeah yeah the memory is there, but we are getting O(n) solution", such a competetive coder moment xD
lol😂😂
To all viewers who can watch mock interviews without being scared..u all strong hearted people deserve my respect..hats off! ...
every time i watch a mock interview it feels so fucking scary i directly jump to leetcode to practice more xD
Samee😂💯
one way to do that is , whenever you find a number duplicated more than once , you can set the hashmap[number] = 1 , and then consider the rest as part of the answer , because whatever happens we know that if number is duplicated C times , we know for sure that C-1 operations will be needed .
His approach was just wow loved the way how he came up with that hashing approach
True❤️😇
Good you discussed the edge case too. One solution is to simply binary search at each index which is always n log n and doesn't depend on the values of A[i]. To handle duplicates, we can do this thing on an unique array i.e. remove duplicates before doing the binary search. After that we traverse every index of that unique array and check that how many indexes on the right of it are covered by binary search with the upper bound as A[curr_index] + n - 1. All the rest of the elements needs to be changed.
Also, thanks for doing it. It takes lots of efforts.
Great content di... really loving the mock interview series. Watched all the videos. Plz never discontinue this mock interview series. ❤️🙏
Also thank you so so much for making such mock interviews. I am imagining myself being an interviewee and getting goosebumps while trying to think of an answer.... I would highly recommend this channel and the mock interviews ( including the system design mock interviews ) for anyone looking to become more confident in interviews :)
Thank you so much Pranav. Your love and support means a lot to me. Will keep creating better content❤️😇
These sessions and learnings are so helpful.
Thank you so much to both.
Thank you so much, means a lot to us❤️😇😇
Hashing can drastically bring the TC from O(N^2) to O(N) but with a cost which is if Arr[i]>10**6 then the code will collapse. So with the constraints available on leetcode(same question obviously) the optimized TC comes down to O(NlogN) and SC to O(N). In my opinion this question doesn't qualify to be in the hard section of leetcode.
Here is a piece of code that qualified AC.
def minOperations(self, nums: List[int]) -> int:
innitial_size = len(nums)
nums = sorted(list(set(nums)))
unique_array_size = len(nums)
maxi = 0
for i in range(unique_array_size):
pos = bisect.bisect_left(nums,nums[i]+innitial_size)
if pos>=len(nums) or nums[pos]!=(nums[i]+innitial_size-1):
pos = pos-1
else:
pos = pos
elements_within_range = (pos-i)+1
maxi = max(maxi,elements_within_range)
elements_off_range = innitial_size-maxi
return elements_off_range
Always helpful ☺️✌️many problems I learnt from your channel get good confidence for big product based
Companies.
Di your content is so amazing. Every new video just introduces new way of solution.
These interviews boosted my confidence a lot
"I look so stupid kya"... That was hilarious :D. Having been on the interviewer seat. I too have heard stuff like these, especially when part of campus hiring events :D
Hahaha, yeah. Hoping these mock interviews help with such small things😇😇
@@KeertiPurswani liked the video only because of how you chose to handle this (rest of the video is superb too) but this set you apart as it felt like a more real experience :)
Keerti mam.. please help me learn data structure to a professional level where I would be able to attend interviews ...as thorough professional..
@Keerti Purswani
Mam Mock interview of
CODE WITH HARRY
Please
LUV and NISHANT sir are Pro coders
But u are missing another pro coder
Code with Harry
For the edge case, we can simply maintain 0 or 1 like the element is present or not because if any element is present more than one time then its duplicates must need to be converted to some other number.
However, the approach discussed will give a TLE on LeetCode as it will depend on the maximum number in the array that is given as 1e9.
This is the code for the approach discussed:
class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int mini = nums[0];
int maxi = nums[0];
for(int i = 0;i < n;i++){
mini = Math.min(mini,nums[i]); //1
maxi = Math.max(maxi,nums[i]); //1000
}
HashSetset = new HashSet();
for(int num: nums){
set.add(num);
}
int ans = n;
int curr = 0;
int num = mini;
int k = 0;
for(num = mini,k = 0;k < n;k++,num++){
if(!set.contains(num)){
curr++;
}
}
ans = Math.min(ans,curr);
while(num
Another nice interview, looking forward for more informative videos from you Keerti 😊😊😍😘
In the first question can we use this approach like if (min-arr[i])>arr.size-1 increment count?
You look sick tc. Great video tho✌🏼😅 luv is too good.
I am really happy that I was able to solve this question in 1 try
I was just watching his stl series ans i got this video , what a timing 😄
Thanks mam for being so active on utube !
Another way to handle duplicates in this problem is
To remove all the duplicate elements from the nums array, (keeping their singular instances in the array)
Let the number of elements removed be "k"
Find the answer "R", for the same question considering the shorter nums array consisting of unique elements.
return R + k
Can you post the link to question if it is present in any platform? that would be really helpful.
Not sure if you have covered this already as a part of the feedback ( since I am commenting as I am watching ), but at 12:02, I felt that asking the interviewer an example again when the interviewer asks you an example is something which could have been avoided. Ideally it would be good if in the beginning of the interview, the candidate enumerates all possible edge cases he/she can think of. Thoughts?
My approach,after taking the inputs in array,First find the min element in the array, The maximum element is that array.length,Then use unordered_map and store all the value and it's frequencies,after that Create s foor loop range between min to max element,after that use find function (o(1)),if the element is present or not,if present then no operation else count++, lastly print the count..is it a good approach?
Came up with both the approaches O(n) and O(nlogn) by myself ...first thought of the same hashmapping and prefix summing but later realised that N would exceed the space limit and hence came up with sorting and binary searching for lower/uppr bounds and then finding out where it lies and calculating the missing elements in btw :) but i somehow missed considering the case when duplicates are present in the input array...❤
Can we do like...first we create a map and store frequency of every element of the array and then check for every element from the minimum like let's say the map is mp and if for every (1
I just wanted to ask whether the array is sorted or not. If the array is sorted then it could be done in O(n).
Looking at the level of question, it feels like i should better change my career trajectory, this was so difficult
I’m not even a coder, but still I’m watching this 😂 idk why!
If size of array is 15 and there is an element whose count is 11. Can we convert it into continues according to this question.
That hashset question was out of the box. One should try in the real interview.
At 11:24 approach will not work if 5 is repeated twice. So for the cases when there is repetition of number it will not work.
I guess all this assigning max+1 is not required. Once can used actual hsh array instead of what Luv bhaiya used(Frequency array) , Just firstly making a frq array , then changing it to cumulative , then for all v[i] finding min of hsh[v[i]+n] - hsh[v[i]-1] just like he did. It will look pretty clean. Moreover , This solution is for when limit of all elements in array is 10^5 and with time complexity O(n) . (but the actual question has 10^9 range , Luv bhaiya assumed it at 28:37 ) For that time complexitiy : O(nlogn) , for every v[i] find lower_bound of v[i]+n-1 and that will help.
My code if someone requires for 10^5 range:
const int MAXN = 1e5 + 1;
int hsh[MAXN];
int main(){
int n;
cin >> n;
vector v(n);
for(int i=0;i> v[i];
int ans = 1e5+5;
for(int i=1;i
This can be done in nlogn after sorting and doing operation (in On) and counting em?
Could we have kept the count as 1 if an element is encountered regardless of its frequency? In that case cumulative sum would have been as expected.
right.
It would be really helpful if you also provided the problem link(if exists) in the video description 🙏🙏🙏
Can someone provide the leetcode question link for this question ??
If we make all hash tables second as zero initially and if duplicates are present it will not matters if check only condition that
if(mp[first or i] ==0){
count++;
}
else{
//Nothing to do
}
Am I right?
I am huge fan of @LUV he is legend in his studies always.
Quite good didi keep bringing didi .I have solved this question with different approach but today I learn new approach which is quite good 🔥
Luv bro has got good coding skills
Can I get a leetcode link to this problem?
can you please make a dedicated video on c++ and oops question but not that are definition based. something that involves pointer and all .
also get well soon :)
13:17 Since he is fixing the max or the min, his hash map represents the frequencies of the elements in the range [min, min + n - 1] ( or [max - n + 1, max] if max is fixed ), hence hash map will still be of size n, not max - min, right?
chup reh tu
yup
Does this problem exist on leetcode? If yes, please post the question number. THanks
Can you please also attach the link to the question in the description box ..it would be helpful?
dii,
what if i sort the array and check for two elements
such that
if a[i+1]-a[i]!=1
count++;
count will be the answer do it work
@LUV please check this out sir
Mam Your work is awesome 😊😊
but the code area is slightly dark. plz use light theme or increase brightness.
Please make a dedicated video on how to make linkedin profile so strong that recruiters of tech giant's approach freshers for job openings
we can do this in O(n) space and time by taking two pointer and hash map. can you share me question link so that I can check if it's possible
if the array is [2,7,8,9] then we need only one operation to covert 2--> 6 so it becomes continuous, but you consider the min in array then it will be 2 then it requires 3 operations to convert 7,8,9
that reaction of Keerti when he said you understand the Hashmap
right
//sort the array (nlogn)
// find max and min (n)
int i=min, int j=max
int count=0;
while(//some condition)
{
arr[j]=abs[length+min];
count++;
if(arr[j]=0){
j--;
max=arr[j];
}
}
return count;
Total T.C.= nlogn
Though I need to filter out the if my array contains duplicates initially. That will require a separate check outside of this while loop . But my t.c. will remains same.
Can I have the problem link to check whether my solution got accepted or not?
Can you also mentioned question link where it asked , so that we could solve.
I thought the same approach with both reverse and forward.
Idk these questions seems to hard for me right now.
Could be a frequency array from highest to lowest value then sliding window of reuqired size and then minimum number of zeroes amongst all sliding window would be the answer
Instead of de-duplicating can we not just store 1 for the element instead of its frequency? Any duplicate element in the array comes at the cost of missing out on a consecutive element, so I think that'll be taken into account anyway.
I was thinking of the same.
You have to romove it. Which is one Operation
@@prateekkatiyar9532 removing that duplicate is same as adding a number which is not present. Eg 1,1,3. Removing 1 is same as adding the missing 2.
we can use sliding window to find maximum elements that is inside (maxelement - minelement)
Sample Edge cases to consider
[-1, 5, 99, 100] ===> [97, 98, 99, 100] {2}
[1, 1, 1, 2] ==> [1, 2, 3, 4] or [-1, 0, 1, 2] {2}
My approach
to first find max and min
if max - min < num.len -1
in this case answer should be number of duplicates because we can surely fit those duplicates in the range
in case if max -min > num.len -1
then we have to find the max number of missing unique element in the range of n to n + num.len - 1
if these numbers are less than duplicates then duplicates is the answer
else these numbers - duplicates
we can store each count in a hash map
we can find the numbers in the range by simply by storing the hash element before that number
this algo would be most optimal in case of time complexity and give correct answer
Sample Edge cases to consider
please paste the leetcode link of the question in the description
Can I get the leetcode link of this question
Please comment down the problem number on leetcode so that we could try on our own.
I think sortign array and then using lower_bound would have simply solved our problem in time complexity=nlogn
No
Suppose after sorting nums becomes (1, 5,6,7,8,13) . So according to you the transformation becomes 1,2,3,4,5,6 in this case ans will be 3 as three elements are changed to 2,3 and 4 .but the actual answer is 2 , as we can change 1 -> 4 and 13 -> 9 so nums becomes 4,5,6,7,8,9.
my relative told me about code to care challenge 2021 philips can you explain more about it in your next video
I have no idea about whats going on.. but I abolutely enjoyed it 😊
Do provide question link too
Mam where is the link of this problem ? I want to solve this problem .
Sort the array, remove the duplicats and use the lower_bound
How about initialising the duplicates as -1....
Having helpful interviewers who provide hints boosts confidence in high stress interview settings. Ironically, it always turned out bad for me because the more helpful interviewers are, the quicker they provide hints. Even if I solved the complete question, using up that hint has always worked against me.
P.S. - The expression of ma'am at 9:23 is enough to predict the result in an actual interview.😂
So basically if interviewer gives hint then it is bad?
@@rocklee3254 anecdotal evidence
For first question first take set and store all uniquely and copy them in new array now we can sort them first and then find differnce between two consecutives now what we want is maximum continuous 1s in differnce and we will count maximum length of continuous 1s now we got our starting point that is minimum element which tells us the ending point as well now using map we can see either can we use the element or need to use operation
Hope this get right
Pls let me know mam
can you sort the array?
Is this question in any websites like leetcode etc? How can i run my code. I have a different logic
yup, its in leetcode..
sort the array and count increasing elements from minimum element that to be every increased element should have a difference of one with previousElement.
then (arr.size() - countOfIncreasing elements)
do similar approch this taking maximum element and count decreasing element with difference of 1 with previous elements then again get (arr.size() - countOfmaximumelement)
finally get minimum of both operation. it will give us answer
complexity
TC O(nlongn)
SC O(1)
question link? plz
Can I get some of the test cases? @Keerti ..
O(nlogn) Solution:
def minOperations(nums):
nums.sort()
n = len(nums)
max_len = 0
start = 0
for end in range(n):
while start < end and nums[end] - nums[start] >= n:
start += 1
max_len = max(max_len, end - start + 1)
return n - max_len
okay , what i can see is the question is somewhat like longest consecutive sequence present in an array
Maam can you share the problem link so that we can practice and see if our approach passes all test cases or not?
leetcode 2009
provide me some information about hero campus challenge
Can anyone give link to this leetcode problem?
Leet code 2009
Helpful (:
Min can also be changed like [2,10,11,12,13] here just 2 is to be changed
By continuous, I think he assumed the numbers would be in a sequential manner.
11:10 no it will not work if number repeats 2 or more time 😂😂
18:57 if(count>1)
replaceNeeded += count -1
20:29 what if random number is in array 😂😂
This can also be one solution
1. Sort the array
2. Find min as a[0]
3. Subtract min-1 to all numbers
4. Now we have min as 1 and our max can he n.
5. Make another array as visited.
6. Ittrate in the array and for each value in the array mark visited[value] =1.
7. At last count number of zeros in visited array.
Is it correct?? 😊
Why am I hearing some other voice before he speaks? It looks like someone is prompting and he is repeating the same. Did anyone hear that?
no bro
isn't it just sorting + sliding window.
Hey @keerti try to interview one mock with youtuber @william lin , we can learn a lot from him 🙃 i feel you,me and your audience will be surprised to the extreme 🌝
💕❤️
do in real interviews also we will get same type of questions?
Similar to LC Longest Consecutive Sequence
I think this will not work for the case
[1,20,21,22,24]
Luv OP
❤️❤️
Striver bhaiya kb aa rhe 😂
Before coding started at 28:03, given a try. Any thoughts around?
public static int countReplacement(int[] input){
Arrays.sort(input);
int min = input[0];
int length = input.length;
int count = 0;
int max = min+length-1;
for (int i = 0; i= min && input[i]
What if the elements are 1 10 11 12 13
A simple solution to this would have been to sort the array and the just keep count of elements which are not contiguous to its left neighbour.
for eg:
[1 10 100 1000]:here ans is 3.
this is because 3 elements (i.e 10 100 and 1000)are not contiguous to each other ( considering first element is always contiguous).
similarly
[1,2,100,1000]: here answer will be 2.
this is again because there are only two elements(i.e 100 and 1000) which are not contiguous to their left neighbour.
If this is wrong please correct me...thanks
What about
[1,2,10,11]
According to you ans would be 1
But ans should be 2
public static int complete(int[] arr) {
int count = 0;
int n = arr.length;
Arrays.sort(arr);
int max = arr[0] + n - 1;
for(int i = 1 ; i < n ; i++) {
if(arr[i] == arr[i-1] || arr[i] > max)
count++;
}
return count;
}
public static void main(String[] args){
int[] arr = {3,3,4,5};
System.out.println(complete(arr));
}
}
- poorly handles case of elements far away from each other O(MAX- MIN) > O(N) (which he claims his time complexity to be)
- uses extra space (doesn't work when MAX > 10^7)
- doesn't handle the case of negative elements
probably the worst approach one could've thought of.
this is a simple sort + two-pointer approach