Python Coding Interview Practice - Difficulty: Hard

In this video I go through a hard coding interview question and discuss the problem, solution and do a full code walkthrough. This is designed to help you prepare for your coding interviews.

Get 15% off using the code "techwithtim"

◾◾◾◾◾
💻 Enroll in The Fundamentals of Programming w/ Python

◾◾◾◾◾◾

⚡ Please leave a LIKE and SUBSCRIBE for more content! ⚡

Tags:
- Tech With Tim
- Python Tutorials
- Coding Interview Question and Answer
- Python Coding Interview
- Python Programming Problem
- Coding Interview

#Python #CodingInterview #ProgrammingProblem

[abhishekbanerjee]

Please more of these. This was absolutely amazing!

[varghahokmran]

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.

[RahulSingh-ilsz]

I want more pls keep uploading this kinda content..

[maksa]

I just started to learn Python by myself (by watching videos, researching, etc), and these kind of "tutorials" make me fall even deeper in love with coding. I want to work something like machine learning combining with complex and very humanoid prosthesis (legs or arms for example). Thank you for your videos, Tim!

[AryCymru]

one of the best videos on this subject. Congratulations!

[cristoferjimenez]

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)

[mattforrest]

Starting with the dictionary comprehension makes it a 2n solution. I think it's possible to keep it just n.
Start by initializing an empty dictionary. For each integer in the array, look above and below in the dictionary. If neither exists, add n to the dict with a key of 0. If a number exists below with a value of 0, change that value to 1 and insert n into the dictionary with a value of -1. You get the idea there. Same with above, or with above and below if it joins two previously separate segments. Of course, keep track of the max in a separate integer variable as you go so that you don't have to iterate through the dictionary after you're done.


def
coords = dict()
current_max = 0
for n in array:
if n - 1 in coords:
min_value = (n - 1) + coords[n - 1]
del coords[n - 1]
else:
min_value = n
if n + 1 in coords:
max_value = (n + 1) + coords[n + 1]
del coords[n + 1]
else:
max_value = n
current_max = max(current_max, max_value - min_value + 1)
coords[min_value] = max_value - min_value
coords[max_value] = min_value - max_value
return current_max

[powerhead]

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
};
}

[inordirectional]

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
}

[evgizr]

You can save the +=1 and -=1 outside the loop (4 lines ) by doing while(left_count-1) in numbers: and reversing the lines inside the loop. But maybe it is less readable.. so whatever. nice solution and explanation :)

[akshobshekhar]

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)

[vardhamanjain]

This code is simpler than the explained one..

def largestRange(array):
main_rng=[]
for i in range(len(array)):
rng=[]
a=array[i]
while a in array:
rng.append(a)
a=a+1
if len(main_rng)<len(rng):
main_rng=rng
return [sorted(main_rng)[0], sorted(main_rng)[-1]]

[ekaterinachikhacheva]

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!

[RamkrishanYT]

11:53
YouTube algorithm: Demonetized it is

[pawanbhatt]

Your code looks Beautiful dude! ❤


I have just started programming and following in my code with I think worst Time Complexity, I tried to solve it before watching the solution, I just watched the problem and it took me a day to solve this, and when I watched your solution, I mean like it was so beautiful, thank you so much for providing these videos.


t = int(input()) #no of test cases
for _ in range(t):
array = list(map(int, input().split()))
sorted_array = []
while len(array):

array.remove(min(array))
range_dict = {}
length = len(sorted_array)
i = 0
j = i + 1
while j < len(sorted_array):
range_list = []
while j <= len(sorted_array):

if sorted_array[j] - sorted_array[i] != 1:
j += 1
i += 1
break
j += 1
i += 1
if len(range_list) >= 2:
range_create = [range_list[0], range_list[-1]]
diff = range_create[-1] - range_create[0]
range_dict[diff] = list(range_create)

[mohammedfuta]

wish there were more of these Difficulty:Hard solutions. 10/10 video 👍

[mp_an_explorer]

Nice logic, I solved it using an alternate approach using disjoint set technique

[MyLordaizen]

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

[TerjeMathisen]

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.

[FlamerKiddy]

@Tech With Tim Building a hash table that ensures O(1) lookup (worst case) with n Elements is not possible in O(n) worst case time. The complete Algorithm does not run in O(n) worst case!