Neetcode

Question 1

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n)

Answer 1

def fib(self, n: int) -> int:
if n == 0:
return 0
elif n == 1:
return 1
else:
f0, f1 = 0, 1
for _ in range(2, n+1):
f0, f1 = f1, f0+f1
return f1

ou

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return self.fib(n-1) + self.fib(n-2)

Question 2

Stack - Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:
Input: s = “()”
Output: true

Example 2:
Input: s = “()[]{}”
Output: true

Example 3:
Input: s = “(]”
Output: false

Example 4:
Input: s = “([])”
Output: true

Constraints:

1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.

Answer 2

class Solution:
def isValid(self, s: str) -> bool:
stack = []
pairs = {“)”: “(“, “]”: “[”, “}”: “{“}

    for char in s:
        if char in "([{":
            stack.append(char)
        else:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()

    return not stack

Question 3

Reverse Linked List
Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.

Example 1:

Input: head = [0,1,2,3]

Output: [3,2,1,0]
Example 2:

Input: head = []

Output: []
Constraints:

0 <= The length of the list <= 1000.
-1000 <= Node.val <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.

Answer 3

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev, curr = None, head

    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev