Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
Eh, I think interviewers should let you code incorrectly, test it, find the bug, and fix it rather than interrupt and say "no." After all, how do you know the candidate wasn't going to fix it on their own 10 seconds later? I probably would have a negative taste in my mouth if my interviewer was this aggro. One example might be nit-picking a hash-set vs hash-map. Anything a hash-set can do a hash-map can do obviously, so it's not a substantive distinction.
@@norats122 "Anything a hash-set can do a hash-map can do obviously, so it's not a substantive distinction." This statement is strictly false. You cannot store occurrence counts of set elements in a HashSet, but you can in a HashMap, as a basic example. For our more advanced users, consider that in the case of the problem in the interview that you only needed to know if an element existed or not. In a hashset, that's exactly the answer it gives and no more, while in a hash map you'll need to store a sentinel value to check, which not only adds to code complexity, but also space complexity. So it's just a strictly inferior thing to use in this situation. The reason that interviewers tend to be overly pedantic as in the video is to weed out people who know what they're doing, from people who think they know what they're doing.
@@VACatholic You sound confused in your first example. Maybe reread/edit it? Any interviewer who interrupts somebody because a solution uses 2x space (same order of magnitude) is a bad interviewer. If you're bored and looking for people to argue with go somewhere else.
@@norats122 If you can't think of a problem that a HashMap would solve that a HashSet wouldn't, you're not qualified to have an opinion on this subject, honestly. I'm trying to give people an honest perspective from someone who has done technical interviews for large companies. The interviewer is trying to understand your knowledge of concepts, if you use the wrong concept and then act belligerent when pointed out, and then have the unmitigated gall to call the interviewer aggro, while acting more aggro yourself? Get over yourself.
This is valuable. Very tough question, and at first I thought the interviewer was harsh--but he ended up being an amazing interviewer that clear knows what he's doing. The interviewee is also very smart, but clearly has the difficulty we all face of being nervous.
the interviewer gave a lot of good nudges in the right direction fairly early. not sure if this is realistic to expect, but i sure wouldn't mind being interviewed like this
In the lines of 24 and 30, there are bugs since looking the index by the value of itself is meaningless. It will give error in the line 24 when it comes to 99 in the array since visited[99] gives out of bounds exception. There should be a kind of hashmap to take the indexes
A clear thinking approach should something like this: store in hash loop items check visisted while (going lower till not found) +1 while (going higher till not found) +1 update max if needed end return max
I was thinking store in a hash table and then get the indices of empty buckets. The greatest difference between indices of two neighboring empty buckets is the longest consecutive list. Is that too awkward? It's O(n) storage and linear time but perhaps not the most elegant
Should the "visited[forward]" and "visited[backward]" be the index where forward and backward are found in the arr_set? Otherwise it'll go out of bounce when it tries "visited[99]" right?
That is what I was thinking. Does it look at the value or the index? If index this shouldn't work, but it is looking for the value then it works fine. So when it does Visited[1] is it setting the value at position 1 in the array to true , or the value of 1 within the array at position 5 to true? I know it should do the value, but is the code actually doing that? I am not familiar with Python.
I am not well versed in python, but in java this code would have bugs. When the algorithm is looking backward from 5 and reaches value 2, it will deem element 99 as visited since visited[backward] would be visited[2]. In Java we would need to either convert the original array to an ArrayList to use .indexOf() or do another linear search to find the index of the current value.
Yes, but you're not storing the index in "arr_set", so even if you find foward, you won't have its index. Instead you can probably turn "visited" into an empty set, and put values in there as you find them.
This problem is easier to look at if you just put the values in a dictionary, it only checks each value once, and then you basically run it the same...keep track of the maximum count, or keep counts in a list and return the maximum...
He needed to slow down and think about the implementation before coding everything. A lot of the comments say the interviewer shouldn't have interrupted him, but if he didn't, the interviewee would have ended up with a 10x buggier implementation that would have taken 2h to debug.
That was one of the good interviews with a good quality feedback , I've ever seen. Apart from that, this question could be done with much less complexity if the coder has used hashmaps, simply by putting the array elements into hashmap and set the value of key = 0( marking them non-visited) and in the forward and the backward loop, if the next consecutive element is available in the keys of hashmap , do "arr_hashmap[ele]=1(mark it visited)"
That’s essentially what the interviewee is doing, instead of a hashmap they just have a visited array with their input array. However a better way yet is to forgo the visited altogether. A number can only belong to one and only one consecutive set. Therefore, why check it again? Simply go through the set, check the existence of (value-1). If that exists, then don’t do the complicated checking forward and back and just move on next. This way once we find a number that doesn’t have a preceding, it’s the start, then simply count forward. Voila, never need to keep a visited array.
So, this is a hard question on LeetCode. And what if someone solves this question without the need of nay help, I assume, it is because they have solved it before and didn't come up with the approach right away. So would it be a positive point for the candidate if she/he solves it without any help?
The solution given is wrong, though. Isn't it? and the solution is not running in O(n). Because in the while loop it is doing a linear search. So the total complexity is O(2n * n). n iteration using for loop, two n iterations in each of that 'for' iteration
Time wise O(n) is optimal but Space wise you can do it with just the set, you can do it without the visited array, but I did it in java maybe that's the reason
I have been there in the past as an interviewee, but the interviewee here comes off as cocky and is getting to coding without even confirming that his pseudocode/ approach is bulletproof. If I was the interviewer this would have been a reject. These are not positive characters I'd look for in a potential coworker. You have to listen and be humble, not just yea yea yea, I know what I am doing. He didn't even wait for the interviewer to finish and give feedback.
class Solution: def longestConsecutive(self, nums: List[int]) -> int: if len(nums) maxTest: maxTest = tmpNum tmpNum = 1 return max(maxTest, tmpNum) (This is how I approached it, but I have only taken a simple intro course)
The interviewee should be asked to run the code and given a chance to correct silly mistakes. Using the values as indexes in the boolean array will never work other than in a sequential array that starts at 0.
def longestConsecutive(self, nums: List[int]) -> int: maxStreak = 0 setNums = set(nums) for i in nums: if i - 1 not in nums: currentStreak = 1 while i + 1 in nums: currentStreak += 1 i = i + 1 maxStreak = max(maxStreak, currentStreak) return maxStreak
C . As you can see it is real to use only one while loop. int MaxLenghtOfConsecutive(int a[], int size){ int count = 0, next, max = 0; int visited[101] = {0}, save[101] = {0}; for(int i = 0; i < size; i++) save[a[i]] = 1; for(int i = 0; i < size; i++) { if( visited[a[i]] ) continue; visited[a[i]] = 1; count++; next = a[i] + 1; while(save[next]) { visited[next] = 1; count++; next++; } if(count == size) return count; max = ( (count > max ) ? count : max ); count = 0; } return max; }
def extract_max_seq(arr): seq = sorted(set(arr)) ls, final = [], [] for i in range(len(seq)): ls.append(seq[i]) if i == len(seq)-1 or seq[i+1] - seq[i] != 1: final.append(ls) ls = [] return final
I don't know how I feel about the interviewer. Around 10:00 he essentially gave out the approach/solution. Any pointers/hints after that, can you say that the interviewee solved the problem? Anyways here is my js solution /** * Given a list of integers L, find the max length of a sequence of consecutive numbers that can be formed using L * For e.g. [5, 2, 99, 3, 4, 1, 100] => max(|{99, 100}|, |{1..5}|) * Space: O(N) * Time complexity : O(N) */ const findMaxSequence = nums => { const map = {}; nums.forEach(element => { map[element] = 'e'; }); const traverse = (val, isIncreasing) => { const increment = isIncreasing ? 1 : -1; let counter = 0; while(map[val]) { delete map[val]; val += increment; counter++; } return counter; }; let maxSeqLength = -99999; do { const keys = Object.keys(map); if (keys.length === 0) { break } const val = keys[0]; delete map[val]; const vInt = parseInt(val, 10); const count = 1 + traverse(vInt - 1, false) + traverse(vInt + 1, true); maxSeqLength = Math.max(maxSeqLength, count); } while(true); return maxSeqLength; } const nums = [5, 2, 99, 3, 4, 1, 100]; console.log(`Max sequence ${findMaxSequence(nums)}`)
This is literally all you need: def longestConsecutive(self, nums: List[int]) -> int: maxStreak = 0 setNums = set(nums) for i in nums: if i - 1 not in nums: currentStreak = 1 while i + 1 in nums: currentStreak += 1 i = i + 1 maxStreak = max(maxStreak, currentStreak) return maxStreak
Well i can tell you this, apparently even after hearing the "solution" you still came up with super over complicated approach. Keep in mind in real interviews its not just coming up with the solution, solution needs to be clean and simple. K = 1 Mp = Create_map(arr) For n in arr: If(Mp.contains(n -k) // there are other elements that start the seq Continue Else While Mp.contains(n+k) ++count, n += k Return count There us no need to remove elements from the map (why?), and there is no need to keep track of increasing or decreasing. Why? If seq is 1,2,3,4,5, and you are on 3, you know that if you have 2 then there is potential for 1, 0, -1, -2, so just skip until you find base of the seq, at most you are doing 2n passes over a sequence, and each number only belongs to one sequence, so O(2n * 1) = O(n)
Wont this program be faster if u skip the numbers in the original array that are visited? I dont think u need to check for next or before numbers at all if i is visited.
You dont need to skip visited or even keep track of visited. What you need to do is think of sequence, each sequence has at most 1 start and 1 end, so either find the end and decrement or find the start and increment. At worst case lets say you choose start, then you iterate through 10,9,8,7,6,5,4,3,2 before coming to 1 then you increment 2,3,4,5,6,7,8,9,10. So worst case 2n where n is length of the sequence, which is still O(n) as constant terms and factors are irrelevant as n goes to infinity.
yes you are correct but the chances of that actually happening is actually so small that we can neglect the worst-case scenario. Just assume for HashMaps and HashSets that lookup is constant, although the worse case, as you said, is indeed O(n)
Let people code and do not interrupt them, aren't we allowed to test our code and see if we can make it better anyhow?I mean what is this, simply interrupting by saying NO is totally wrong. Interviewer does care about his inerviewee but his approach is really not that good.
Cant you do this with a set, min and max ranges? Loop through every number from min and max. Count the length of the streak, increment if its in the set. Reset to 1 if its not in the set.
i would have done a integer based sort in O(n) time then walked through the sorted array and kept track of the longest run of consecutive integers. this is very interesting approach though,
@@stardreamse It is actually O(m*z) where z is the number of integers, and m is the number of bits in the longest integer, but the amount of bits in the entire input is n ~= m*z so it is still linear. A hash table is still probably faster though because it uses CPU operations that look at 64 bits at a time where as a radix sort goes bit by bit by bit.
@@CarrotCakeMake It doesn't matter, really. A hash table *IS* still faster in any reasonable sense for this problem given. We're still talking about the use cases given, for raidx sort, the numbers are maybe 16bit, probably 32, could even be 64. The n*log(n) is faster than m*z even when you consider that. But the point I was making was that in software development - given to solve a situation like this, you should not have expectations about the dataset and have a solution that solves the broadest case possible, with few exceptions.
Without watching the video here is my solution: use sort and arrange the array in order. Then use a loop that starts at the first item in the sorted array and add + 1 to it, then check if it equals the next number. Do that until it doesn’t (false output). Then save the sequence into a list. Then repeat the process at the number in the initial array that broke the sequence. At the end you should have a bunch of lists, then just print the longest one.
Yeah and he came up with that (as should any decent programmer) within first minute after ironing out constraint. Real challenge is to do in linear time, again easy but will be a little challenging to those not familiar with the fact that any geometric subsequence can be accessed linearly by using a set
Has anyone looked at the full feedback that the interview gave? He is expecting the candidate to solve 3-4 problems in 30 mins? That to even leetcode hard level? Is Microsoft that difficult to crack. I found that crazy
he said he finished his masters, this means he is applying for a specific position that requires a certain level of knowledge. Now you won't see this problem asked for a new grad since it would be too hard. This is just a question that is meant to reach a certain education level, and since everyone starts as Software Engineers it goes to show that a Graduate degree will move you further in the company much much faster than a undergraduate degree since people need to able to trust the "graduate" soft eng group to handle more complex tasks or big-picture tasks. It sucks this is the way it is, but this is how we reduce the number of specific positions making it easier for recruitment.
The fact that this guy went silent for such large periods of time is such a bad thing. People don't realize that these interviews are seldom about you nailing the right answer and more so about understanding your thought process. By not communicating, you're essentially not even interviewing, you're just leetcoding with a buddy.
This is untrue in my opinion, the large silent pauses are something a lot of ‘teachers’ do too: its too progress the question and understand it. In the beginning the interviewee did not know what ‘consecutive numbers’ meant where as the interviewer tried to really get a thorough gasp of what the interviewee did not understand.
Dont take this advice. Always you should take time to think of a solution before spitting out words. No one wants to hear you babbling "Im thinking we can store these... no thats not going to work sorry I was thinking of something else, maybe if I try this yeah I think no wait that wont work for this case". Long silent pauses are not scary, interviewer wants to hear you say "So im thinking we start with this and this and store the numbers like this then iterate like this, I can see that working for this test case." So that way they can probe, ok what about this test case? What if you had this input? Can we do it faster? Can we do it in constant space? Babbling lol what an interviewer is going to ask you? "Lets slow down and go through this step by step" at that point you lost the interview if they have to organize your thoughts for you
yeah it's just that the format for most of the interviews (or at least the ones I've watched) consists of 3-4 parts (in increasing difficulty) and the interviewees are supposed to complete them in more or less an hour. I definitely feel like he got unlucky as that was definitely the hardest first question I've seen on this channel.
@@Pablo-dy2xo True, I have a few years of experience and very high grades on algo courses (top 10 percentile on my university) and had a hard time to solve it - I think it was not fair (though I think it's a mock interview, right?).
@@Pablo-dy2xo I know it’s a year later but this is a hard level question on leetcode I highly doubt they will give this as a first interview questions maybe easy or medium level to start
Its a medium not hard, and actually easy once you thinking in terms of sequence. Anyway the interviewer is right to nudge him because his two pointers approach is going in the wrong direction. The statement that each number is part of only one sequence is a huge help but he was locked in his thinking which is a big thing I see for newer engineers they try to do things in one-pass when it is ok to do 10 passes over an array if that gives you solution its still O(n). Knowing each number is only part of one sequence, ok that means if I can look for 6 or 4 when I access 5 then I should be able to just iterate and look for them. What if 5 is in middle of sequence? Ok how about we try to find the base of the sequence and count from there? Well that can be very large steps, what if we just check if this current value is the base instead of searching for base, and when we do access base, start counting from there? Cool, now how can we access 4 if we starting on 5? Maybe lets do one pass to figure what numbers we have by putting in a hashmap or set then we can do second pass where we count sequences when we hit base values and skip all other values? Boom, from that hint you have natural progression to coming to O(n) solution. Interviewer is there also to help guide you, they want the O(n) solution if they see you are going down the wrong path they will try to help you but ultimately if you are stubborn its your own fault.
I am a beginner so forgive me for any bad coding practice. def check_seq(array): array.sort() for i in array: if i+1 not in array: array.insert(array.index(i)+1, 0) t = 0 j = 0 for i in array: if i != 0 : j+=1 else: j =0 if i !=0 and j >1 and array[array.index(i)+1] == 0: t+=1 return t
oh, my god, what is he doing. the solution is simple... values = [6, 5, 2, 99, 3, 4, 1, 100] values = list(set(values)) values.sort() max_len = seq_len = 1 x = values[0] for i in range(1, len(values)): if values[i] - x == 1: seq_len += 1 else: max_len = seq_len if seq_len > max_len else max_len seq_len = 0 x = values[i] print(max_len)
Interviewer: What language are you gonna be using today? Me: Which one is below assembly? Interviewer: Umm, machine language? Me: Yeah, that one. I wanna use that one. Interviewer: 01000110 01110101 01100011 01101011 00101110 Hint: Copy and paste that into a binary to english translator
@@ReubenXR No he sets the first slot "visited[0]" to true on line 19, however on line 24 he made a mistake. What he meant to do is to set the position where forward (forward = 5 + 1) is to true. What he did was setting true on position forward (visited[6]).
Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
wow, the interviewer is good. He may sound harsh, but I think he genuinely cares about the interviewee. I wish I had him as a coach lol
Eh, I think interviewers should let you code incorrectly, test it, find the bug, and fix it rather than interrupt and say "no." After all, how do you know the candidate wasn't going to fix it on their own 10 seconds later? I probably would have a negative taste in my mouth if my interviewer was this aggro.
One example might be nit-picking a hash-set vs hash-map. Anything a hash-set can do a hash-map can do obviously, so it's not a substantive distinction.
@@norats122 "Anything a hash-set can do a hash-map can do obviously, so it's not a substantive distinction."
This statement is strictly false. You cannot store occurrence counts of set elements in a HashSet, but you can in a HashMap, as a basic example. For our more advanced users, consider that in the case of the problem in the interview that you only needed to know if an element existed or not. In a hashset, that's exactly the answer it gives and no more, while in a hash map you'll need to store a sentinel value to check, which not only adds to code complexity, but also space complexity. So it's just a strictly inferior thing to use in this situation.
The reason that interviewers tend to be overly pedantic as in the video is to weed out people who know what they're doing, from people who think they know what they're doing.
@@VACatholic You sound confused in your first example. Maybe reread/edit it?
Any interviewer who interrupts somebody because a solution uses 2x space (same order of magnitude) is a bad interviewer.
If you're bored and looking for people to argue with go somewhere else.
@@norats122 If you can't think of a problem that a HashMap would solve that a HashSet wouldn't, you're not qualified to have an opinion on this subject, honestly. I'm trying to give people an honest perspective from someone who has done technical interviews for large companies. The interviewer is trying to understand your knowledge of concepts, if you use the wrong concept and then act belligerent when pointed out, and then have the unmitigated gall to call the interviewer aggro, while acting more aggro yourself?
Get over yourself.
@@VACatholic you seem to be claiming the converse of the original statement. That a HashMap can do everything a HashSet can, not the other way around.
This is valuable. Very tough question, and at first I thought the interviewer was harsh--but he ended up being an amazing interviewer that clear knows what he's doing. The interviewee is also very smart, but clearly has the difficulty we all face of being nervous.
this is the kind of interviewer that would be a superb manager/tech lead. THIS is what you want from superiors, candor
The interviewee needs to slow down and listen more
the interviewer gave a lot of good nudges in the right direction fairly early. not sure if this is realistic to expect, but i sure wouldn't mind being interviewed like this
Yep, pretty much gave away the entire answer at 8:30.
This is realistic to expect from a good interviewer :)
In the lines of 24 and 30, there are bugs since looking the index by the value of itself is meaningless. It will give error in the line 24 when it comes to 99 in the array since visited[99] gives out of bounds exception. There should be a kind of hashmap to take the indexes
Yeah ! Even I found that bugging... and I was searching for this comment that someone would point it .
that was a long ass pause during the early minutes of the interview
It's like a News Reporter. "OK, Let's switch over to Bob Joe" *long ass pause* "Hello"
The interviewer is really good..I haven't encountered such detailed feedback and hints roadmap till now
A clear thinking approach should something like this:
store in hash
loop items
check visisted
while (going lower till not found) +1
while (going higher till not found) +1
update max if needed
end
return max
I was thinking store in a hash table and then get the indices of empty buckets. The greatest difference between indices of two neighboring empty buckets is the longest consecutive list. Is that too awkward? It's O(n) storage and linear time but perhaps not the most elegant
@@deltabinge I think your thinking works but make sure to include corner cases like no empty bucket, only 1 empty bucket.
Also, when an item is found, remove it from the set to prevent double counting consecutive sequences.
Thanks for posting man, very few people would post such an interview, keep it up 😇, and waiting for your winning interview
Should the "visited[forward]" and "visited[backward]" be the index where forward and backward are found in the arr_set? Otherwise it'll go out of bounce when it tries "visited[99]" right?
That is what I was thinking. Does it look at the value or the index? If index this shouldn't work, but it is looking for the value then it works fine.
So when it does Visited[1] is it setting the value at position 1 in the array to true , or the value of 1 within the array at position 5 to true? I know it should do the value, but is the code actually doing that? I am not familiar with Python.
I am not well versed in python, but in java this code would have bugs. When the algorithm is looking backward from 5 and reaches value 2, it will deem element 99 as visited since visited[backward] would be visited[2]. In Java we would need to either convert the original array to an ArrayList to use .indexOf() or do another linear search to find the index of the current value.
Yes, but you're not storing the index in "arr_set", so even if you find foward, you won't have its index. Instead you can probably turn "visited" into an empty set, and put values in there as you find them.
The `visited` array here doesn't make any sense.
right, good observation. Could have used a set to record visited elements
This problem is easier to look at if you just put the values in a dictionary, it only checks each value once, and then you basically run it the same...keep track of the maximum count, or keep counts in a list and return the maximum...
He needed to slow down and think about the implementation before coding everything. A lot of the comments say the interviewer shouldn't have interrupted him, but if he didn't, the interviewee would have ended up with a 10x buggier implementation that would have taken 2h to debug.
The interviewer seems to be a good guy.
Some times all they try for is to make the candidate feel worthless and to make him hate himself.
That was one of the good interviews with a good quality feedback , I've ever seen.
Apart from that, this question could be done with much less complexity if the coder has used hashmaps, simply by putting the array elements into hashmap and set the value of key = 0( marking them non-visited) and in the forward and the backward loop, if the next consecutive element is available in the keys of hashmap , do "arr_hashmap[ele]=1(mark it visited)"
That’s essentially what the interviewee is doing, instead of a hashmap they just have a visited array with their input array.
However a better way yet is to forgo the visited altogether. A number can only belong to one and only one consecutive set. Therefore, why check it again? Simply go through the set, check the existence of (value-1). If that exists, then don’t do the complicated checking forward and back and just move on next. This way once we find a number that doesn’t have a preceding, it’s the start, then simply count forward. Voila, never need to keep a visited array.
So, this is a hard question on LeetCode. And what if someone solves this question without the need of nay help, I assume, it is because they have solved it before and didn't come up with the approach right away. So would it be a positive point for the candidate if she/he solves it without any help?
Isn’t this just 128. Longest Consecutive Sequence? It’s a medium and not a hard medium
The solution given is wrong, though. Isn't it? and the solution is not running in O(n).
Because in the while loop it is doing a linear search. So the total complexity is O(2n * n).
n iteration using for loop, two n iterations in each of that 'for' iteration
Time wise O(n) is optimal but Space wise you can do it with just the set, you can do it without the visited array, but I did it in java maybe that's the reason
That interviewer feedback was sooo me!.. i knew it but i realized everyone faces this!... i know what to fix now!
wow , the interviewer from microsoft is really amazing . His thoughts are damn clear , systematic and not rushing also !! What's his name ?
astronomic avenger
I have been there in the past as an interviewee, but the interviewee here comes off as cocky and is getting to coding without even confirming that his pseudocode/ approach is bulletproof. If I was the interviewer this would have been a reject. These are not positive characters I'd look for in a potential coworker. You have to listen and be humble, not just yea yea yea, I know what I am doing. He didn't even wait for the interviewer to finish and give feedback.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) maxTest:
maxTest = tmpNum
tmpNum = 1
return max(maxTest, tmpNum)
(This is how I approached it, but I have only taken a simple intro course)
The interviewee should be asked to run the code and given a chance to correct silly mistakes. Using the values as indexes in the boolean array will never work other than in a sequential array that starts at 0.
def longestConsecutive(self, nums: List[int]) -> int:
maxStreak = 0
setNums = set(nums)
for i in nums:
if i - 1 not in nums:
currentStreak = 1
while i + 1 in nums:
currentStreak += 1
i = i + 1
maxStreak = max(maxStreak, currentStreak)
return maxStreak
Not sure if tha solution is correct. How can line 24 or 30 work
The interviewer speaks exactly like the philosopher Kapil Gupta MD. It’s almost scary how similar their voices are
The interviewee should calm down and listen to what hints he’s given. He’s interrupting the interviewer a LOT, which is annoying.
Finally, like this guy has to calm down and listen instead of interrupting a lot!!!
C .
As you can see it is real to use only one while loop.
int MaxLenghtOfConsecutive(int a[], int size){
int count = 0, next, max = 0;
int visited[101] = {0}, save[101] = {0};
for(int i = 0; i < size; i++) save[a[i]] = 1;
for(int i = 0; i < size; i++)
{
if( visited[a[i]] ) continue;
visited[a[i]] = 1;
count++;
next = a[i] + 1;
while(save[next])
{
visited[next] = 1;
count++;
next++;
}
if(count == size) return count;
max = ( (count > max ) ? count : max );
count = 0;
}
return max;
}
We can do it using Union find data structure ......it takes O(n) time ?
Not really. en.wikipedia.org/wiki/Disjoint-set_data_structure
def extract_max_seq(arr):
seq = sorted(set(arr))
ls, final = [], []
for i in range(len(seq)):
ls.append(seq[i])
if i == len(seq)-1 or seq[i+1] - seq[i] != 1:
final.append(ls)
ls = []
return final
Clever
Well the interviewer provided the solution when he mentioned would you use hashmap or hashset?
I don't know how I feel about the interviewer. Around 10:00 he essentially gave out the approach/solution. Any pointers/hints after that, can you say that the interviewee solved the problem? Anyways here is my js solution
/**
* Given a list of integers L, find the max length of a sequence of consecutive numbers that can be formed using L
* For e.g. [5, 2, 99, 3, 4, 1, 100] => max(|{99, 100}|, |{1..5}|)
* Space: O(N)
* Time complexity : O(N)
*/
const findMaxSequence = nums => {
const map = {};
nums.forEach(element => {
map[element] = 'e';
});
const traverse = (val, isIncreasing) => {
const increment = isIncreasing ? 1 : -1;
let counter = 0;
while(map[val]) {
delete map[val];
val += increment;
counter++;
}
return counter;
};
let maxSeqLength = -99999;
do {
const keys = Object.keys(map);
if (keys.length === 0) {
break
}
const val = keys[0];
delete map[val];
const vInt = parseInt(val, 10);
const count = 1 + traverse(vInt - 1, false) + traverse(vInt + 1, true);
maxSeqLength = Math.max(maxSeqLength, count);
} while(true);
return maxSeqLength;
}
const nums = [5, 2, 99, 3, 4, 1, 100];
console.log(`Max sequence ${findMaxSequence(nums)}`)
This is literally all you need:
def longestConsecutive(self, nums: List[int]) -> int:
maxStreak = 0
setNums = set(nums)
for i in nums:
if i - 1 not in nums:
currentStreak = 1
while i + 1 in nums:
currentStreak += 1
i = i + 1
maxStreak = max(maxStreak, currentStreak)
return maxStreak
@@xNamsu U know that's like n^2 complexity right
Well i can tell you this, apparently even after hearing the "solution" you still came up with super over complicated approach. Keep in mind in real interviews its not just coming up with the solution, solution needs to be clean and simple.
K = 1
Mp = Create_map(arr)
For n in arr:
If(Mp.contains(n -k) // there are other elements that start the seq
Continue
Else
While Mp.contains(n+k)
++count, n += k
Return count
There us no need to remove elements from the map (why?), and there is no need to keep track of increasing or decreasing. Why? If seq is 1,2,3,4,5, and you are on 3, you know that if you have 2 then there is potential for 1, 0, -1, -2, so just skip until you find base of the seq, at most you are doing 2n passes over a sequence, and each number only belongs to one sequence, so O(2n * 1) = O(n)
Wont this program be faster if u skip the numbers in the original array that are visited? I dont think u need to check for next or before numbers at all if i is visited.
You dont need to skip visited or even keep track of visited. What you need to do is think of sequence, each sequence has at most 1 start and 1 end, so either find the end and decrement or find the start and increment. At worst case lets say you choose start, then you iterate through 10,9,8,7,6,5,4,3,2 before coming to 1 then you increment 2,3,4,5,6,7,8,9,10. So worst case 2n where n is length of the sequence, which is still O(n) as constant terms and factors are irrelevant as n goes to infinity.
Exactly what I thought for a solution for the first question was what the interviewer suggested..... I feel empowered !
Isn't this O(n^2) worst case because set membership is O(n) when there is always hash collisions.
yes you are correct but the chances of that actually happening is actually so small that we can neglect the worst-case scenario. Just assume for HashMaps and HashSets that lookup is constant, although the worse case, as you said, is indeed O(n)
Let people code and do not interrupt them, aren't we allowed to test our code and see if we can make it better anyhow?I mean what is this, simply interrupting by saying NO is totally wrong. Interviewer does care about his inerviewee but his approach is really not that good.
Cant you do this with a set, min and max ranges?
Loop through every number from min and max. Count the length of the streak, increment if its in the set. Reset to 1 if its not in the set.
Max-min might be O(n) or O(n squared) or O(any function of array size)
i would have done a integer based sort in O(n) time then walked through the sorted array and kept track of the longest run of consecutive integers. this is very interesting approach though,
what kind of sorting are you talking about? Counting sort or what?
You can’t have expectations on the dataset. The values can be anything, therefore integer based sort of radix sort is still o(n log n).
@@stardreamse It is actually O(m*z) where z is the number of integers, and m is the number of bits in the longest integer, but the amount of bits in the entire input is n ~= m*z so it is still linear. A hash table is still probably faster though because it uses CPU operations that look at 64 bits at a time where as a radix sort goes bit by bit by bit.
@@CarrotCakeMake It doesn't matter, really. A hash table *IS* still faster in any reasonable sense for this problem given. We're still talking about the use cases given, for raidx sort, the numbers are maybe 16bit, probably 32, could even be 64. The n*log(n) is faster than m*z even when you consider that. But the point I was making was that in software development - given to solve a situation like this, you should not have expectations about the dataset and have a solution that solves the broadest case possible, with few exceptions.
@@stardreamse Radix sort is linear, not nlogn
Union find with hash map to get O(n) solution, why it leads to dfs?
I think have no idea at the first and just come up with dfs after getting the hints..
Only hope is MS doesn't ask their engineers to write such code / work on such problems in their daily work
Surprised that no tests were performed , at least in the video recorded
Without watching the video here is my solution:
use sort and arrange the array in order. Then use a loop that starts at the first item in the sorted array and add + 1 to it, then check if it equals the next number. Do that until it doesn’t (false output). Then save the sequence into a list. Then repeat the process at the number in the initial array that broke the sequence. At the end you should have a bunch of lists, then just print the longest one.
Yeah and he came up with that (as should any decent programmer) within first minute after ironing out constraint. Real challenge is to do in linear time, again easy but will be a little challenging to those not familiar with the fact that any geometric subsequence can be accessed linearly by using a set
Is this only for experienced or fresher
Has anyone looked at the full feedback that the interview gave? He is expecting the candidate to solve 3-4 problems in 30 mins? That to even leetcode hard level? Is Microsoft that difficult to crack. I found that crazy
he said he finished his masters, this means he is applying for a specific position that requires a certain level of knowledge. Now you won't see this problem asked for a new grad since it would be too hard. This is just a question that is meant to reach a certain education level, and since everyone starts as Software Engineers it goes to show that a Graduate degree will move you further in the company much much faster than a undergraduate degree since people need to able to trust the "graduate" soft eng group to handle more complex tasks or big-picture tasks. It sucks this is the way it is, but this is how we reduce the number of specific positions making it easier for recruitment.
So this is or isn’t a real interview?
This is mock interview. Not real. It's like a training for interviews.
The fact that this guy went silent for such large periods of time is such a bad thing. People don't realize that these interviews are seldom about you nailing the right answer and more so about understanding your thought process. By not communicating, you're essentially not even interviewing, you're just leetcoding with a buddy.
This is untrue in my opinion, the large silent pauses are something a lot of ‘teachers’ do too: its too progress the question and understand it.
In the beginning the interviewee did not know what ‘consecutive numbers’ meant where as the interviewer tried to really get a thorough gasp of what the interviewee did not understand.
Dont take this advice. Always you should take time to think of a solution before spitting out words. No one wants to hear you babbling "Im thinking we can store these... no thats not going to work sorry I was thinking of something else, maybe if I try this yeah I think no wait that wont work for this case". Long silent pauses are not scary, interviewer wants to hear you say "So im thinking we start with this and this and store the numbers like this then iterate like this, I can see that working for this test case." So that way they can probe, ok what about this test case? What if you had this input? Can we do it faster? Can we do it in constant space? Babbling lol what an interviewer is going to ask you? "Lets slow down and go through this step by step" at that point you lost the interview if they have to organize your thoughts for you
I think he did great, the interviewer was rushing him too much in my opinion (though he was very nice and wanted to help).
yeah it's just that the format for most of the interviews (or at least the ones I've watched) consists of 3-4 parts (in increasing difficulty) and the interviewees are supposed to complete them in more or less an hour. I definitely feel like he got unlucky as that was definitely the hardest first question I've seen on this channel.
@@Pablo-dy2xo True, I have a few years of experience and very high grades on algo courses (top 10 percentile on my university) and had a hard time to solve it - I think it was not fair (though I think it's a mock interview, right?).
@@Pablo-dy2xo I know it’s a year later but this is a hard level question on leetcode I highly doubt they will give this as a first interview questions maybe easy or medium level to start
Its a medium not hard, and actually easy once you thinking in terms of sequence. Anyway the interviewer is right to nudge him because his two pointers approach is going in the wrong direction. The statement that each number is part of only one sequence is a huge help but he was locked in his thinking which is a big thing I see for newer engineers they try to do things in one-pass when it is ok to do 10 passes over an array if that gives you solution its still O(n). Knowing each number is only part of one sequence, ok that means if I can look for 6 or 4 when I access 5 then I should be able to just iterate and look for them. What if 5 is in middle of sequence? Ok how about we try to find the base of the sequence and count from there? Well that can be very large steps, what if we just check if this current value is the base instead of searching for base, and when we do access base, start counting from there? Cool, now how can we access 4 if we starting on 5? Maybe lets do one pass to figure what numbers we have by putting in a hashmap or set then we can do second pass where we count sequences when we hit base values and skip all other values?
Boom, from that hint you have natural progression to coming to O(n) solution. Interviewer is there also to help guide you, they want the O(n) solution if they see you are going down the wrong path they will try to help you but ultimately if you are stubborn its your own fault.
I am a beginner so forgive me for any bad coding practice.
def check_seq(array):
array.sort()
for i in array:
if i+1 not in array:
array.insert(array.index(i)+1, 0)
t = 0
j = 0
for i in array:
if i != 0 :
j+=1
else:
j =0
if i !=0 and j >1 and array[array.index(i)+1] == 0:
t+=1
return t
There are faster algorithms
Sort is nlogn
oh, my god, what is he doing.
the solution is simple...
values = [6, 5, 2, 99, 3, 4, 1, 100]
values = list(set(values))
values.sort()
max_len = seq_len = 1
x = values[0]
for i in range(1, len(values)):
if values[i] - x == 1:
seq_len += 1
else:
max_len = seq_len if seq_len > max_len else max_len
seq_len = 0
x = values[i]
print(max_len)
sorting is nlogn, there’s a O(n) solution
why not sort the list and then just go through it once with counters, done
I did this the same way, but had to google how to sort in javascript because theres no native function to sort numbers in javascript
that 'll be a nlog(n) solution .... anyways the interviewee code is wrong and would have led to index out of bounds exception
Interviewer: What language are you gonna be using today?
Me: Which one is below assembly?
Interviewer: Umm, machine language?
Me: Yeah, that one. I wanna use that one.
Interviewer: 01000110 01110101 01100011 01101011 00101110
Hint: Copy and paste that into a binary to english translator
Someone explain line 13 to me.
What is it doing there?
He is setting every slot in the array "visited" to false an defining the length with len(arr). In this case setting 7 times false in "visited".
@@cifercero So when he does visited[1] = true (line 24), this makes the 1st slot true, right?
@@ReubenXR No he sets the first slot "visited[0]" to true on line 19, however on line 24 he made a mistake. What he meant to do is to set the position where forward (forward = 5 + 1) is to true. What he did was setting true on position forward (visited[6]).
@@cifercero Yeah, that is what confused me! Thanks!
This is a hard question on LeetCode? really?
Yeah, sounds like easy. I’ve seen people in the comments complaining about hard it is and how they came from top 10 universities lol
Too bad video quality
I think these guys should fix their microphones....
It sounds extemly bad
Wow.. the interviewee was not ready. Just sort the array, then sequentially go through the array. 5 minutes of coding. The solution is so obvious
That was his first response....... 4:00
@@Longwashere You are right. Me bad.
👀