Longest Consecutive Sequence (Python)

Watch someone solve the longest consecutive sequence problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Longest consecutive sequence

Interview question

Given a list of integers L, find the maximum length of a sequence of consecutive numbers that can be formed using elements from L.

Interview Feedback

Feedback about Double Astrolabe (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

2/4

Help your interviewee get better! 2 areas that need work: 1. speed: aim for 3-4 problems in <30 mins 2. big picture: evaluate different approaches, pick one, and justify it All the best!

Feedback about Astronomic Avenger (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

3/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Detailed and informative feedback after the interview was really helpful.

Interview Transcript

Astronomic Avenger: Hello?

Double Astrolabe: Hey, hi how are you?

Astronomic Avenger: Hey, good how are you?

Double Astrolabe: I'm good.

Astronomic Avenger: So yeah, by way of introduction I'm a software engineer at Microsoft. The team I'm on, what we're doing is that we're building a container to run SQL server inside of. That way SQL server can run on non Windows platforms without changing the application source code too much.

Double Astrolabe: Oh nice okay.

Astronomic Avenger: Yeah so that's a little bit about myself, what's your what's your background?

Double Astrolabe: Ah so I have done my Master's here and I've graduated like six months back, so right now I'm working in a fintech company in New York, so I'm looking for a switch to the west coast for personal reasons, so yeah.

Astronomic Avenger: I see. Okay cool cool. So in terms of today's interview what I have in mind is to treat this like a mock phone screen for Microsoft.

Double Astrolabe: Mm-hmm.

Astronomic Avenger: I'll ask you questions of the same difficulty, hold you to the same standards, and at the end of it gives you feedback. Does that sound reasonable?

Double Astrolabe: Yeah that sounds perfect.

Astronomic Avenger: Okay cool. If you can go ahead and pick your language, let's get started.

Double Astrolabe: Sure. I'll be picking Python. Yeah okay all right.

Astronomic Avenger: So what we're going to do first is basically look at a list manipulation problem.

Double Astrolabe: Okay.

Astronomic Avenger: So given a list of integers and a maximum length of a sequence of consecutive numbers that can be formed using elements from the list.

Double Astrolabe: Okay, can you give an example?

Astronomic Avenger: Sure. So the idea that say you're given this array of [5, 3, 1] and then let's put 99 here. And a 100 here. So here you have two sequences to choose from. The 99, 1 through 5 and 99 and 100 and you take the length of these.

Double Astrolabe: Does it matter in which order I choose the numbers, does it?

Astronomic Avenger: Well the numbers have to be consecutive right? So...

Double Astrolabe: Okay so I'm just wondering how you got 1 to 5 over here.

Astronomic Avenger: So because you have the numbers 1 2 3 4 5 in your array.

Double Astrolabe: Oh yeah so I'm asking if it is necessary that the numbers had to appear in the same order that way? Because in this case 1, I mean the numbers are out of order, right? So is it fine?

Astronomic Avenger: Yeah yeah the numbers, the sequence, the ordering of the numbers in your array does not matter, let's put it that way.

Double Astrolabe: Ok ok cool. Right so I guess since you mentioned... The first approach that I can think of is just sorting the entire array and you know just going through the array one element at a time and I can keep count of the sequence. That's the first stop words that I can think of right now.

Astronomic Avenger: Okay.

Double Astrolabe: Oh that's what definitely work right?

Astronomic Avenger: Yeah that could definitely work.

Double Astrolabe: That would work yeah, but that's going to be O(n log n) complexity. I'm trying to think if we can do it in linear time. I'm thinking of using some other data structure to store the elements that I've visited. Let's say I loop through the array and I store five and then I come across 2 and I come across 99 after store somewhere else. Okay maybe I guess I can start with the... I can have like two pointers. I'm thinking, so but again okay... So when I count. So the problem is when I encounter a number like 99, I have to figure out that it's a part of a different sequence and not the same sequence right, okay?

Astronomic Avenger: The thing is each number right that you have, it can only be part of one sequence.

Double Astrolabe: Yeah exactly yeah. So maybe... So I have to find which sequence the number falls in right okay?

Astronomic Avenger: Or you have to find the sequence itself and then mark that number as visited and you never have to visit that number again.

Double Astrolabe: So okay so let's say I have 5. Now so I have to find out which...

Astronomic Avenger: So one approach that that would make sense is to start with the number right?

Double Astrolabe: Yeah.

Astronomic Avenger: And then do a search. And then do a search for numbers before it and after it.

Double Astrolabe: Yeah exactly yeah. But I mean so it's for each number then I would be doing that right? Okay so for example if have 5.

Astronomic Avenger: Hold on that secondary though right? That's what we would need to do. So I guess your concern about that is that if you do it for every number it would be O(n^2).

Double Astrolabe: Exactly.

Astronomic Avenger: It doesn't need to be right? Because here you would be using the other property that the numbers have to be consecutive, you don't need to iterate through the entire array. Right? So for five you would only look for six and four, then you would go to six and look for seven right? You'd go to four and look for three right? So if you could do that in constant time, that would be great.

Double Astrolabe: So I guess you're always saying is once I find a four, I don't come back to five from four I go back and look for three?

Astronomic Avenger: Right.

Double Astrolabe: Okay so from three I can go back and look for two okay.

Astronomic Avenger: So what... So I guess the question then becomes a list won't give you that right from a four you cannot go to a 3 without doing a linear search.

Double Astrolabe: Exactly yeah.

Astronomic Avenger: So what data structure would give you that constant time lookup.

Double Astrolabe: Yeah so I have to use like a hashmap right? Just store the indices of the numbers.

Astronomic Avenger: A hashmap or hashset? You have to be careful here.

Double Astrolabe: Um so hashset would just tell me the number is there or not, so I guess that should be fine because I don't actually have to go to the index of the number right? So I guess you're in the hashset and just look up if the number is there or not.

Astronomic Avenger: Right so that's the first part. Then what do you do? Once you've visited that number then would you do?

Double Astrolabe: Okay so let's say... Okay so I'm just going... So let's say I'm at five now right? Okay so I'm at five. So I look up for six and four. Okay so now let's say this is a set that I have, set of all numbers. So I'm looking for six and four. So now let's say I find four in this case. Then I have to look up for three and I have to keep going until... So I have to increment my the length of my sequence and then I have to keep going until this condition returns False. And then once that happens... Okay so while doing that I'll have to mark all my nodes visited all the things that I go through will be visited so here in my set I can just basically remove it from our original array I guess. I'll just make it visited actually yeah instead of removing it. I'll mark it as visited and then I'll be at 99. So I think I'll look for 98 and 100. Once I find 100, I'll look for 101 and I'll just keep going that way.

Astronomic Avenger: Yeah that will definitely work I think.

Double Astrolabe: Okay so you want me code it out or?

Astronomic Avenger: Yeah let's write the code for it.

Double Astrolabe: Okay. So is it okay if I convert the initial array to a set?

Astronomic Avenger: Is it okay like I'm okay with that but why would you do that and if so you know how would you do it?

Double Astrolabe: I'm saying can I modify the original array or should I like copy it into a new set? That's what my question is.

Astronomic Avenger: Why do you want to modify what the original array right? That's my question for you.

Double Astrolabe: Sorry uh you're asking...?

Astronomic Avenger: Why would you modify the original array.

Double Astrolabe: Because I want a constant lookup time right, so I want it to be a set.

Astronomic Avenger: Right so you can create a set without modifying the array right?

Double Astrolabe: Yes, my question was if I can do this okay cool. Because I thought in Python you can just do it as a set of array or something to convert it to a set so, I'll just create a new set then.

Astronomic Avenger: Oh no I mean yeah you can do that right, you can do set of... You can put this array here.

Double Astrolabe: Okay okay yeah that's... Okay cool.

Astronomic Avenger: So will doing a single search be enough? Like will doing a single check be enough?

Double Astrolabe: I have to check if the... I'll check for both plus one and minus one if that's what you're asking?

Astronomic Avenger: Well that's fine, but what I'm saying is for any given element I thought we agreed that we would do an exhaustive search we would have to update...

Double Astrolabe: I have to update my... ...search is what I'm trying to do. That's what I was going to do. So for example I found four and I have to go to four and five.

Astronomic Avenger: How do we continue that search, what do you have in mind?

Double Astrolabe: I was thinking of having another data structure for that, let's say a stack or a queue and I can keep putting it in the queue like a DFS basically.

Astronomic Avenger: Okay so the data structure you already have the count already right, and you're marking your visited array to be true. So I don't see why you need a different data structure. What you need is to basically look for the other elements right, so essentially what I'm saying is...

Double Astrolabe: This is for the ith value right, something like that I can make i go to...

Astronomic Avenger: Well not your i right? Because your i is for the main loop.

Double Astrolabe: Exactly okay yeah. Okay yeah, so okay so if I find this element now, I'll mark this element as true, now I have to continue to do the same process for i + 1 right okay.

Astronomic Avenger: So if you just convert the line to if conditional, line 22 to a while. What would you get in that case?

Double Astrolabe: Oh yeah so I guess then in that case as long as it is in the set I'll keep doing and the length keeps updating. Yes I guess I can do that yeah. So similarly I have to do for...

Astronomic Avenger: Will this be enough?

Double Astrolabe: So okay let's say I have five now, or no...

Astronomic Avenger: Your array at i doesn't change right? And you would need to do the same for your backwards.

Double Astrolabe: Yeah okay. Okay I get I think I get what you're saying. Okay so yeah, so basically for five not, this will be for 6 7 8, so now I have to do something like... Should be forward... Okay so this I can check if the node is already visited, I can break out of this loop too right? So let's say...

Astronomic Avenger: No hold on... We discussed this right? The node will not be visited.

Double Astrolabe: Sorry?

Astronomic Avenger: The node will not be visited right?

Double Astrolabe: Yeah if it is I'm saying um.

Astronomic Avenger: It will not be.

Double Astrolabe: I guess for five it will go to six. Oh yeah yeah yeah because it has...

Astronomic Avenger: The reason I'm being stringent on that is simply because if you don't really get that the node will not be visited twice, right, you are not not guaranteed that your algorithm will run in linear time.

Double Astrolabe: Yeah yeah yeah yeah makes sense.

Astronomic Avenger: If you agree that this is linear, then you shouldn't have to make that check. If you make that check, that tells me that you don't understand why this is linear.

Double Astrolabe: No yeah, I think I get what you are saying. So basically...

Astronomic Avenger: What would you do next?

Double Astrolabe: Yes I guess okay... So after I update the max length right... So I have to max length... So now have to... So I guess once one entire thing is done, so let's say what this entire thing is done, I get the length of one consecutive sequence right? So this is where I'll be updating my maximum length to... And then I'll make length to zero. This means I guess I'm done with one entire sequence. So now I guess I can just...

Astronomic Avenger: Okay.

Double Astrolabe: Yeah so I guess this should work. Let me just call the function.

Astronomic Avenger: Oh that's fine, don't worry about that. So what's the runtime of your function?

Double Astrolabe: Yeah so this would be O(n), where n is the length of the array because we are going to go to each node.

Astronomic Avenger: And the space?

Double Astrolabe: So space is... So I'm using another visited array, so I guess that's going to be the only extra space I'm using, that for each element in the array, so that's going to be O(2n).

Astronomic Avenger: Ok cool so I'm going to end the interview there, but I would love to give you feedback. But before that, d you have any questions for me?

Double Astrolabe: Ah so is this like the optimal solution that we can go through? Is there a better solution than this?

Astronomic Avenger: This is the most optimal solution.

Double Astrolabe: Okay you cannot do better than O(n) right because you have to find a sequence passing at the end I guess I wasn't clear. And so space?

Astronomic Avenger: For space, no I don't think you can do better. This is the most optimal.

Double Astrolabe: Okay okay. Cool yeah, that should be it, thanks.