"""Programming Puzzles (Week 12) === CSC148 Winter 2021 === Department of Mathematical and Computational Sciences, University of Toronto Mississauga """ from __future__ import annotations from typing import List class ListNode(object): def __init__(self, x, next=None): self.val = x self.next = next def has_cycle(head: ListNode) -> bool: """ returns if the linked list starting from has a cycle. >>> lst = ListNode(1, ListNode(4, ListNode(8))) >>> has_cycle(lst) False >>> lst.next.next.next = lst >>> lst2 = ListNode(3, lst) >>> has_cycle(lst2) True """ pass def daily_temperatures(temps: List[int]) -> List[int]: """ Given a list of daily temperatures , return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. >>> lst = [73, 74, 75, 71, 69, 72, 76, 73] >>> daily_temperatures(lst) [1, 1, 4, 2, 1, 1, 0, 0] """ pass def my_sqrt(x: int) -> int: """ Compute and return int(sqrt(x)) Precondition: x >= 0 Requirements: - You must NOT use any given sqrt() method or the power operator (**) - The runtime must be O(log x) >>> my_sqrt(0) 0 >>> my_sqrt(16) 4 >>> my_sqrt(48) 6 """ # Below is an inefficient solution with runtime O(sqrt(x)) # You need to improve it to O(log x) for ans in range(x+1): if ans * ans <= x and (ans + 1) * (ans + 1) > x: return ans return 0 if __name__ == "__main__": import doctest doctest.testmod()