Python

Challenge Given a linked list, your task is to sort it in ascending order. Solution 1 - TLE Using a bubble sort approach. class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: not_sorted = True if not head: return while not_sorted: tmp = head not_sorted = False while tmp.next: if tmp.val > tmp.next.val: tmp.val, tmp.next.val = tmp.next.val, tmp.val not_sorted = True tmp = tmp.next return head Time Complexity: O(n^2) Solution 2 Using a merge sort approach sort approach. ...

Challenge Given the head of a singly linked list and two integers, reverse the nodes of the list from position left to position right. E.g: reverseBetween(head, 2, 4) 1 -> 2 -> 3 -> 4 -> 5 Returns 1 -> 4 -> 3 -> 2 -> 5 Solution class Solution: def reverse(self, head, steps): tmp = head prev = None tail = head i = 0 while tmp and i < steps: current = tmp n = current.next current.next = prev prev = current tmp = n i+=1 head = current tail.next =n t = head return head def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: tmp=head j = 1 prev = None if right -left ==0: return head while tmp and j < left: prev = tmp tmp=tmp.next j =j+1 a = self.reverse(tmp, right+1 - left) if not prev: return a prev.next = a return head Time complexity: O(n) Space complexity: 1 ...

Challenge Given a non-negative number represented as a string, return the smaller possible integer after removing K digits. E.g "1041" 1 Will output 41 Solution 1 I really liked my first solution, however performances can’t be worst. It’s a brute force approach doing backtracking, basically I tried to remove 3 digits in every possible position. from copy import deepcopy class Solution: def helper(self, num, k, arr, start): if len(arr) == k: self.res.append(deepcopy(arr)) return for i in range(start, len(num)): arr.append(i) self.helper(num, k, arr, i+1) arr.remove(i) return def remove_from_list(self, num, to_remove): num = list(num) r = [] for i, e in enumerate(num): if i not in to_remove: r.append(e) return r def removeKdigits(self, num: str, k: int) -> str: if k == len(num): return "0" self.res = [] self.helper(tuple(num), k, [], 0) r = int(num) for i in self.res: ret = self.remove_from_list(num, i) ret = int("".join(ret)) r = min(r, ret) return str(r) Solution 2 After failing on a lot of different test cases it looks like this greedy implementation below works. ...