Python Coding Interview Practice – Difficulty: Hard

If you want access to all the questions on the site use the code "techwithtim" for 15% off. https://algoexpert.io/techwithtim

More of these please

I did solve it without sorting the array. Starting with a loop that walks through the array, if it finds both n and n+1 present then thats the beginning of a sequence and a number collection function is called. The number collection function has its own loop that keeps adding one to n, checking if its present in the array, then storing that number in an output array until there are none left in sequence.
I guess its not O(n) because I have a loop within a loop, so its O(n squared).
But I got it done my own way and it works great, and that feels good. ..

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