Python Coding Interview Practice - Difficulty: Hard

Actually this one is just dfs for next and previous then mark it visited and count

This is what I got:
6 array = [1,5,8,5,9,3,2,7,3,10]
7 sorted_array = []
8 - for i in range(len(array)):
9
value = min(array)
10
sorted_array.append(value)
11
array.remove(value)
12
13 print(sorted_array)

hey Tim, how about this code? will it work for all the corner cases?

a = sorted(map(int, input('Num list: ').split()))
Clist = []
for num in a:
cons_list = []
while num+1 in a:
cons_list.append(num)
num += 1
else:
if len(cons_list) >= len(Clist):
Clist = cons_list

print(Clist)

The only thing this doesnt solve is if you have the same range for various numbers, like if you have -3,-4,-5 and 6,7,8 in the same list, technically they're the same, but I guess the lists they give don't specifically have lists with this kind of issue built in....otherwise I guess you could technically make another dictionary that specifies each range and return all of them with the largest range, but that's kind of an extra step and challenge

I just started learning Python and thought I was making good progress until I watched this video. I never even heard of a hashtable. Man I feel so far away from even being remotely close to being in a position to apply for a job. How can people pick all this up from zero to hero in less than 6 months all while not even studying 8+ hours a day, everyday? Maybe I should just be a cop or something, idk, this is pretty depressing.

great video. thank you

Hey Tim,
your video was very good with the code and explanation
I just tried this one myself and got the code much easier 😄
It's working perfectly😁

Here's the code:

def LongestRange(arr):
num = arr[0]
longwidth = 0
for i in arr:
width = 0
while width+i+1 in arr:
width+=1

if width > longwidth:
longwidth = width
num = i

return [num,num+longwidth]

Did i miss something?🤔

Great Video, Great Solution, Great Explanation.

Can anyone explain how the search for left and right is in O(1)? It's a while loop which in the worst case would have to go through every item. I understand that checking for a specific number is O(1), but if one exists it has to keep going up to n times doesn't it?

if I will use python for the contest, Will I face any problems? Please answer me.

Birreliant and a very efficient solution. However, for the case where the longest sequence is 1, this would still be O(n*n), so it's only O(kn) or O(n) if it is guaranteed that k<n.

what should this return print(largestRange([8, 9, 3, 5, 4, 7]))? [3,5] or [7,9]? they both have the largest range. Above returns [3,5].

Please upload more questions and approach used to solve them sir

Thank you for explanation

More of these please

Bro, I will learn English to watch your videos

what an elegant solution!

It doesn't work if the largest number on the list is in index 0.

The exercises look great but they are not Python specific, those could be implemented with any programming languages.
But, for example, "Implement a cache mechanism with decorators" is a direct Python question.

The question is , does Algoexpert have questions that really are Python specific?

Small optimization: we could use Hashset instead of Hashmap and delete seen values from there. We also could declare set capacity to avoid Hashset resizes during population and optimize performance:

public int[] longestRange(int[] arr) {

// Declare a hashset capacity of 125% mof arr.length to avoid hashset resizes and optimize performance
Set<Integer> set = new HashSet<>((int) (arr.length / 0.75) + 1);

// Populate hashset
for(int element : arr) {
set.add(element);
}

int left = 0;
int right = 0;

for(int element : arr) {

if(!set.contains(element)) {
continue;
}

int leftElement = element;
int rightElement = element;

while (set.contains(leftElement - 1)) {
set.remove(leftElement);
leftElement--;
}
while (set.contains(rightElement + 1)) {
set.remove(rightElement);
rightElement++;
}
set.remove(element);

if(rightElement - leftElement > right - left) {
left = leftElement;
right = rightElement;
}

}
return new int[]{
left,
right
};
}

Great job

Can anyone pls explain me how the program is taking input. Because it not taking list input from the user. I have tried running this code my computer but it do not work. please help, I am new to the programming.

The trivial solution is O(n) in space (the input array) and O(n*log n) in time by sorting (O(n*log n)) the list and then simply scanning it once while remembering the longest sequence seen so far. The fancy alternative would use a hash table of all sequences seen so far, indexed by the beginning of each sequence. The top of each sequence is also indexed, with the negative length of the sequence. This is also O(n) space but should approach O(n) in time since it can be done with a single streaming pass over the input. It is similar to how I merge contour line segments generated from a triangulated lidar point cloud.

Loved it 🙏🏻

I don't know why but it doesn't work for [0, 4, 3, 2, 11, 12, 13, 10, 9, 1, 8] . It always returns [0, 4] instead of [8, 13]

Can i shine in competitive programming Contest by using python? 🙃

More videos of this kind

I want more of these videos

Here's another linear approach in JS. It works in one pass (no pre-initialization of a hash table), but it keeps more information in the table. It's a simplified union-find

function largestRange(arr) {
if (arr.length === 0) return []

const rangeMap = {} // { num => [lo, hi] }
let largestRange = [arr[0], arr[0]]
for (num of arr) {
if (rangeMap[num]) continue;
rangeMap[num] = [num,num] // init with default range

if (rangeMap[num-1]) largestRange = union(num, num-1, rangeMap, largestRange) // union num with left
if (rangeMap[num+1]) largestRange = union(num, num+1, rangeMap, largestRange) // union num with right
}
return largestRange
}
function union(x, y, map, range) {
let newLo = Math.min(map[x][0], map[y][0])
let newHi = Math.max(map[x][1], map[y][1])

map[newLo] = [newLo, newHi] // keep endpoints of ranges up to date in map
map[newHi] = [newLo, newHi]

return newHi-newLo > range[1]-range[0] ? [newLo,newHi] : range // return newLargestRange
}

You write numbers down in a strange way

Damn man I feel so lost

just use sort.... u have a nested loop which makes ur program n^2 if im not mistaken. u can do this by sorting and then a single for loop to keep it at nlogn instead of n^2

Thank you for the content! I think I just found one of the most easy to understand explanations. Love the idea with drawing on the board. Thanks again!

You should drink sometimes.

Bro which compiler you are using

Would this not work:
def largestRange(l):
largerange = []
for i in l:
if i+1 in l:
largerange.append(i)

return [min(largerange), max(largerange)+1]

Furthermore, the question doesn't ask us to use linear time or space complexity; therefore, I believe that we allowed to use different complexities of time and space.

Thank you for your valuble video ! I think the cost of your solution is O(2n), isn't it ?

important thing with this solution is that we are making use of extra information which is specific to numbers i.e. x-1, x, x+1 and not really present in the input data

Instructions unclear
list.sort() go BRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

I have heavy brain promblems

couldn't we start from the smallest number (using min(array)) in the list and keep removing the elements as they are counted,it might get the program more easy (i guess)

I'm not trying to sound cocky, but this looks really simple, i learned about ranges and that stuff in year 6 and could do this question in my sleep(I have not learned coding but I know a lot about coding and how the languages function, the main part of this question is learning the names of the expressions used to write the algorithm) Someone please confirm if I'm correct? Just saying the algorithm for this question would be easy????

This is literally a semi low level math problem. Just gotta code it.

Alternative

x = [1,11,3,0,15,5,2,4,10,7,12,6,16,17]

result = []
all_range = []
strt = min(x)
fin = max(x)+2

for num in range(strt,fin):
if num in x:
result.append(num)
else:
if len(result)>1:
all_range.append(result)
result = []
continue

a = []
for i in all_range:
if len(i)>len(a):
a=i
print(a)

if your right is 4 and left is 0, then 4-0 = 4 but it needs to be 5 as 0,1,2,3,4

I dont know, in my opinion premature optimisation is root of all evil. You need to ask yourself how much time does a reader of your code take to understand your code. So if you do not know beforehand that this is a bottleneck in performance, I'd rather go simple.

Hi Tech With Tim, thank you for this very thoughtful tutorial! I noticed that after the two while loops (on lines 11 and 16 respectively) you did not check to see if you had already visited the adjacent numbers ("continue"-ing if so). Does this mean that an O(n^2) solution can pass all test cases as well? Do correct me if I am mistaken, as I am not a Python user.

Done with lists and range:

l = [0,2,3,4,6,7,8,9,10,12,13] # can ask user input for list too
def largestRange(l):
ranges=[]
temp = []
l.sort() # here l is manually given and sorted
start = False
for i in range(len(l)-1):
if l[i+1]-l[i]==1:
if start==False:
start=True
temp.append(l[i])
temp.append(l[i+1])
else:
temp.append(l[i+1])
elif l[i+1]-l[i]!=1 and start==True:
start=False
ranges.append(temp)
temp = []
ranges.append(temp)
ranges.sort(key=len)
xyz=[]
xyz.append(ranges[-1][0])
xyz.append(ranges[-1][-1])
print(xyz)

largestRange(l)