Interview Question: Consecutive Array
Vložit
- čas přidán 13. 09. 2024
- Coding interview question from www.byte-by-byt...
In this video, I show how to find the longest consecutive sequence of numbers in an unsorted array.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
50 Practice Questions: www.byte-by-by...
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
I was stuck on how to utilize hash map, your idea of optimization of start looking to next element only if the current element is first element of sequence was very great , this optimization is very cool & it helped me alot!! Thanks for the video :)
Love your videos. So great for interview prep. Thank you!!
Side note: You look like Jim Parsons from The big bang theory. So it's like learning from my favorite TV person.
Haha love that show
Thanks to your Video I was able to also add and the contents of subsequence easily as shown below
package Testexample;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class ConsecutiveArray {
public static int consecutive(int[] a) {
// Put all the values into a HashSet
HashSet values = new HashSet();
for (int i : a) {
values.add(i);
}
System.out.print("Contents of Hashset:");
for(int k : values){
System.out.print(k);
}
System.out.print("
");
// For each value, check if its the first in a sequence of consecutive
// numbers and iterate through to find the length of the consecutive
// sequence
int maxLength = 0;
for (int i : values) {
/*Is there a better way to reset a list so it does not carry old values?*/
List result = new ArrayList();
System.out.println(" Current value in hashset is "+i);
if (values.contains(i - 1))
{
System.out.println("Decremented value of is " +(i-1)+" is present in hashset then this is not the leftmost value in the sequence, increment current pointer ,don't bother to iterate hash set continue the for Loop");
}
else
{
System.out.println("Decremented value of i is " +(i-1)+" is not present in hashset so this will go in while loop");
}
// If it is not the leftmost value in the sequence, don't bother
if (values.contains(i - 1)) continue ;
int length = 0;
// Iterate through sequence
while (values.contains(i++)) {
System.out.println("Now inside the while loop");
length++;
/* System.out.println("length is "+length); */
result.add(i);
//System.out.println("Result is
"+result.toArray().toString());
};
maxLength = Math.max(maxLength, length);
System.out.print("Sub sequence: ");
for(int z=0;z
Change length to 1 and then use ++i-- it's ever so slightly more efficient. There is no need to check if your current value is in the hash set , since you got it from the hash set.
nicely explained sir, thank you 👍👍👍👍
You're welcome!
very nicely explained.Thanks a lot !
Very crisp solution.
But, the run time seems to be O(n*n) . Here is why , when you consider worst case at every step in the algorithm and you have very large groups consecutive integers your array, we talking in the order of 100,000 or more.
Consider consecutive numbers from 1 to 100,000 (set 1) , 101,000 to 201,110 (set 2) , 301,100 to 500,000 (set 3).
(i) Now consider the first element picked up is 100,000 , this has to be checked by decrementing i 99,999 times .
(ii) then consider 99,999 gets picked , this gets decremented 98,000 times. This keeps happening until we pick 1.
(iii) Then we increment 1 to 100,000.
(iv) But we still haven't found our solution. We have to go through steps (i),(ii) and (iii) for set 2 and set 3 assuming worst cases again.
(v) When the array is too big if we consider the sets of consecutive numbers to be of order n the time complexity is O(n^2).
Thoughts?
You're missing the part where we only traverse if we are at the first element in the consecutive sequence. If sequence[i-1] = sequence[i] - 1, then we don't bother traversing. So we only traverse any given element at most twice
@@ByteByByte Hypothetically speaking, even is the HashSet somehow contained (1,2,3,4,5,6,7), this solution's run time would still be considered O(n)? May you please explain briefly?
I think I got it, but please correct me if I am wrong but the run time is O(n) + O(n) for worst case, which is O(2n), and essentially simplifies to O(n) when dropping the constant?
@@shayanasgari5594 yep
8:09 i literally never pressed 'x' instead of 't' u trippinn
Hahaha. HashSex
Subscribed your channel after watching first video only, nice explanation. Just wanted to add here, isn't creating hashset order of nLogn only. So doing it either by sorting or using hashset, means same complexity. If items are repetitive,hashset will outperform sorting, otherwise both are same. What do u say?
Why you gave the example sorted? What if it was sorted in reverse? 6 5 4 3 2 1? It would be O(n^2)?
Doesn't matter; you put them into the HS anyway.
Ahh, I didn't think about the "if(values.contains(i-1)) continue;" line. Very neat! That line alone makes its runtime reasonable.
You may also want to explain a bit more why your solution is a run-time of N.
Seeing a while loop inside a for loop had me concerned.
I had to do it manually to double check if N run-time was correct. Which it is correct.
Thanks! I see what you mean tho. I originally saw a similar solution elsewhere and I also had to work through it to see that the runtime works out correctly
i like to think of the algorithms in this way: for every element in a sequence, the runtime would be O(n_i) (n_i is sequence #i length) for the first element and O(1) for the rest, so the total run time would be the summation of the length of all of the sequences plus an additional O(1)*rest of elements which is O(n), and the length of all sequences equals n.
i hope this explanation is clear, its a more mathmatical approach and easier to prove via a whiteboard i think.
Awesome explanation thanks !!
thanks!
Is there anyway to do this and return an array of the consecutive values as well as the value?
how to do this problem using union find?
awesome ,, please upload more videos plzzzzzz
thanks :)
thanks for uploading . . . .keep uploading :)
will do!
why not just iterate from min(a) through max(a) and skipping non present numbers, O(n) solution
Python solution:
from collections import Counter
def longest(a):
C = Counter(a)
start, end = min(a), max(a)
count = 1
maxcount = 1
for j in range(start, end + 1):
if C[j] == 0:
continue
if C[j + 1] > 0:
count += 1
else:
count = 1
maxcount = max(maxcount, count)
return maxcount
Not sure I totally understand, but seems like a similar concept
@Stesilaus You need a full pass through the array to find the min and the max.
What if we want to print that longest sequence in the same code ? How do we do that?
If we track where our sequence starts and the length, it's pretty easy
Thank you! :)
you're welcome :)
I converted this code into python and tried to running it but never print out the result. Can anyone tell me what's wrong with this?
def consecutive(arr):
values = set()
for i in arr:
values.add(i)
mLen = 0
for i in values:
if i-1 in values:
continue
length = 0
while i+1 in values:
length = length + 1
mLen = max(mLen, length)
print mLen
consecutive([4,2,1,6,5])
while i+1 in values never increments i, so you get into an infinite loop
I fixed it my code as given below and it works now. Thanks!
while i in values:
length = length + 1
i = i + 1
Way not remove each element when u doing len++?
Instead of run over it again?
It's not generally a good idea to add or remove items as you're iterating over the list
Byte By Byte
Thanks for answer.
Still, in this case I think that it save a lot of unnessery run time.
And each element can be only on one sub set. No?
(remove from hashSet, not from list)
I really enjoy your videos!!!
I mean you're not actually iterating over those elements multiple times anyway so it doesn't affect the runtime
@@bashibaharav3820 i was going to agree with you, it would be a nice optimization, but both operations are O(1), not sure in terms of real efficiency but the step takes O(1) per added element, and deleting an element from hashset would also cost some constant time.
HashSex 8:08 lol
this is again n^2 . run for input 7,6,5,4,3,2,1,0
Nirmal Kumar Ravi I don't believe so because you only search for a consecutive array when you get to the smallest of the consecutive elements, in this case 0. Can you explain your reasoning?
again, the above solution takes O(n) time, even for that input.
First you add everything to the hashset. Then you iterate over all the values in the array. 7-1 = 6, which is in the hashset, so you skip it. 6-1 = 5, which is in the hashset, so you skip it. Continue until you reach 0. Then 0-1 = -1, which is not in the hash set, so you start with 0 and say is 0+1 in the hashset? 1+1? 2+1? etc.
Basically you're iterating over the whole array twice.
Nirmal Kumar Ravi please look at following link you will be clear with O(n) and O(n2).
stackoverflow.com/questions/37765752/what-is-the-complexity-of-running-a-loop-twice-of-the-same-input-array
@@sandeepmandge2278 These loops are not the same. The condition allows skipping the work in iterations so the nested loop will scan further the hash-set. O(n^2) makes sense only if we are doing the work in the outer loop, but in our case, it is just to initiate the inner loop.