old notes

devstudy

#python #devstudy #datatypes

yes its good practice, it allows python and editors to make your life easier used for the reader, and for linters

used in classes

but for example, if I were to pass a class instance in there without the type hint, I wouldnt know what methods I can access, however with the type hints it will give me these options. (editor sepcific)

class Test:
    def __init__(self):
        self.test = False

def func(x : Test):
  print(x.test)

t = Test()
func(t)

example of type error

class MyClass:
    a: int
    b: str
    c: float

    def __init__(self, a: float, b: list[int], c: dict[str, str]) -> None:
        self.a = a
        self.b = b
        self.c = c

examples of type hints

x: int
s: str
l: list
l2: list[str]
t: tuple[]
t2: tuple[int]
t3: tuple[int, ...]
d: dict
d2: dict[str, int]
etc...

typehint with a return:

def func(x: int, y: int) -> int:
  return x + y

for tuples, you need to declare the type

so this will cause a linter alert because if you don't use ... you're declaring a fixed length

my_tuple: tuple[int] = (1, 2)

but this will work (for tuples)

my_tuple2: tuple[int, int] = (1, 2)
my_tuple3: tuple[int, ...] = (1, 2, 5, 1, 7, 1, 8, 1)

Protocol??

class Test: test: bool def init(self) –> None: self.test = False

def func(x: Test) –> None: print(x.test)

t: Test = Test() func(t)

Seperating typehints with initializations

also note that you can seperate typehints and initializations

type aliases

Coord = tuple[int, int]

def func(x: int, y: int) -> Coord:
  return (x, y)

Using TypeVar

a typevar is a type that is defined at call of the function and you can use that typevar to ensure multiple variables are of the same type by the linter it is also what will get assigned to a return value typevars get super fun with bindings, covariants, and generics

from typing import TypeVar

T = TypeVar("T")

def foo(x: T) -> None:
    m: T
    if isinstance(x, int):
        m = 1
    else:
        m = True

for m: T in above function it only assigns its type so any assignment of m later in the function will be bound to that type because there is no memory given to m it's not like int x; in C++ for example

add example of without the typeVar

x: int
print(x)

gives NameError – why

this is NOT valid:

from typing import TypeVar, Generic

T = TypeVar("T")

class Foo(Generic[T]):
    thing: T

#devstudy #algorithmns #datastructures #problemsolving

Read Before Starting

STOP SKIPPING STEPS EVEN ON EASY QUESTIONS!!!!!!!!!! YOU WILL REGRET IT EVERYTIME!!!!!!!!!!!!!

Most Common Mistakes

EFFY PLEASE VISUALIZE/WRITE MORE TEST CASES – misinterpreting the problem bc going too fast – misunderstanding the problem bc going too fast – implementation issues with scoping

If Stuck

  1. Can you reverse the interpretation?
  2. Can you start the approach with the another input and/or direction?
  3. Can you use a set or a map to store something you're manually reaching for at a later point?
  4. Can you break down the problem more?
  5. Did you make a table of cases to fully visualize the pattern or did you trust your assumptions? Don't trust your assumptions.

Interpretation Patterns

If input array is sorted then – Binary search – Two pointers

If asked for all permutations/subsets then – Backtracking

If given a tree then – DFS – BFS

If given a graph then – DFS – BFS

If given a linked list then – Two pointers

If recursion is banned then – Stack

If must solve in-place then – Swap corresponding values – Store one or more different values in the same pointer

If asked for maximum/minimum subarray/subset/options then – Dynamic programming

If asked for top/least K items then – Heap

If asked for common strings then – Map – Tree

Else – Map/Set for O(1) time & O(n) space – Sort input for O(nlogn) time and O(1) space

#devstudy #algorithmns #datastructures #problemsolving

  1. Can you reverse the interpretation?
  2. Can you start the approach with the another input and/or direction?
  3. Can you use a set or a map to store something you're manually reaching for at a later point?
  4. Can you break down the problem more?
  5. Did you make a table of cases to fully visualize the pattern or did you trust your assumptions? Don't trust your assumptions.

#datastructures #algorithmns #devstudy #BigONotation #timecomplexity #spacecomplexity

jarednielsen-big-o.png

Time Complexity: Time taken to run as a function of the length of the input

  • number of operations it takes to complete for length Input
  • find the WORST CASE scenario > drop the non-dominant terms

Not the most useful chart but that pastel-tone charcoal = yes

timecomplexity.png

Better chart but less aesthetic:

big-o-cheatsheet.png

From Fastest to Slowest:

O(1) time: One Operation

  • takes a constant amount of time even with more input
  • ex: mathematical calculation of sum: s = n(a+1)/2 as opposed iterative calculation which is O(n) linear bc for every additional input value, the rate of growth re: time scales proportionally.

Examples

  • accessing Array Index
  • Inserting a node in Linked List
  • Pushing and Popping on Stack
  • Insertion and Removal from Queue
  • Finding out the parent or left/right child of a node in a tree stored in Array
  • Jumping to Next/Previous element in Doubly Linked List

O(log n) time: Recursion?

Examples

  • Binary Search
  • Finding largest/smallest number in a binary search tree
  • Certain Divide and Conquer Algorithms based on Linear functionality
  • Calculating Fibonacci Numbers – Best Method premise = NOT using the complete data, and reducing the problem size with every iteration

O(n) time: Linear, i.e. Brute Force, Noob ones that I write bc my brain is stuck on iteration

Examples

  • Traversing an array
  • Traversing a linked list
  • Linear Search
  • Deletion of a specific element in a Linked List (Not sorted)
  • Comparing two strings
  • Checking for Palindrome
  • Counting/Bucket Sort and here too you can find a million more such examples....

O(n*log n) time: linear time complexity multiplied by log n

  • factor of log n is introduced by bringing into consideration Divide and Conquer.
  • some of the most optimized and frequently used

Examples

  • Merge Sort (recursive)
  • Heap Sort
  • Quick Sort
  • Certain Divide and Conquer Algorithms based on optimizing O(n^2) algorithms

O(n^2) time: Quadratic.

  • nested loops bc each loop is performing n iterations so n*n
  • less efficient algorithms if their O(n*logn) counterparts are present??
  • general application may be Brute Force here

Examples

  • Bubble Sort :'(
  • Insertion Sort
  • Selection Sort
  • Traversing a simple 2D array

Space Complexity: The space an algo needs to run

  • sorting algorithmns need at least O(n) space to save the list of length n that they have to sort but can often work in place meaning that it needs no additional space
  • number representation can be saved in either (1) binary (or any other base equal or less than 2) so this needs O(log n) space bc n = 2^logn; or (2) as a sum of n so you need O(n) space bc you need to save each n

O(1) space: In-place

  • a function that counts the elements of an array: don't need to allocate or copy new data even if the array is large, the counter is the same var

O(log n) space:

Examples

  • Binary Search
  • Finding largest/smallest number in a binary search tree
  • Certain Divide and Conquer Algorithms based on Linear functionality
  • Calculating Fibonacci Numbers – Best Method premise = NOT using the complete data, and reducing the problem size with every iteration

O(n) space:

  • everytime we make a new function call = new stack frame
  • recursion: if n = 100, then O(n)

#datastructures #recursion #devstudy #algorithmns

Characteristics of a Recursive Problem

  • Can the problem be broken down into a smaller version of itself?
  • Can I re-use the solution to solve the problem?
  • Do I have an abstracted solution that already exists??

THE PROCESS: DO NOT SKIP STEPS you will regret it

1. What is the simplest input? This is your base case. There might be more than one.

2. Visualize the Problem Without Words. Find the smallest subproblem and focus ONLY on the sub-problem. – do not think about the implementation beyond the subproblem

3. What is the relationship between the Second-To-Last to Last Case? If I am given the answer for the Second-To-Last case, can I find the Last Case? Can I solve?

4. Generalize the pattern: This is your recursive function.

5. Trust the abstraction. If the logic is sound, solving the sub problem will solve the problem.


MISTAKES I KEEP MAKING

  1. Breaking the Problem using syntax short cuts to express my thoughts and letting this draw me into assumption patterns without consciously realizing the pull.

What to do: Visualize the problem WITHOUT WORDS. Just do it.

  1. Thinking too much about the implementation in the rest of the problem instead of trusting that the recursion will work if the logic for the subproblem is sound.

What to do: Set a timer and spent 80% of time on thinking.

  1. Not spending enough time visualizing different examples.

What to do: See 1.

  1. Not trust that my logic IS sound and seeing all errors are evidence that there is a fundamental misunderstanding of the problem rather than realizing that sometimes, it's IS an implementation error.

What to do: Build more confidence by listening to positive feedback without immediately dismissing it. Spend more time coding so I know the idiosyncrasies of the language better.

  1. Implementation Errors: Going too fast to notice incorrect assumptions of what I am asking CREATOR to do.

What to do: More puts, debug line by line. Go slower....

#datastructures #tree #graph #leetcode #devstudy #ruby

Things to Remember

  • 80% planning, 20% implementation
  • Read slowly.
  • Examine assumptions and let them go. Keep an open mind.
  • Resist the urge to jump to conclusions. Resist the urge to plug in a known structure or syntax even as you're reading the question.
  • The question is only ONE way of describing the problem. What are other ways of looking at this description?

  • Abstraction first, Implementation later

  • Understand the cases of the problem as a PROBLEM not from with the limits of the syntax you keep reaching for.

  • What is the problem? What am I trying to achieve?

  • What are my cases at each step in abstracted terms?

Questions to When Debugging

  • Look at every single line and ask yourself: what am I asking the computer to do?

#graphs #datastructures #devstudy

Definitions:

Graph: A network that helps define and visualize relationships between various compoenents. In other words: it is a set of vertices and edges where each edge is a connection between vertices.

Neighbours: Vertices are neighbours if connected by an edge

Degree: Number of edges connected to a vertex

Path: Sequence of vertices connect by edges. Paths have an expected length (n of edges in a path)

Cycle: path that starts and end at the same vertex. All cycles are paths but not all paths are cycles.

Connectivity: two vertices are connected if a path exists between them. A graph is connected when all vertices are connected.

Directed graph: Directed means that the edge is uni-directional. Directed graphs can be cyclic or Acyclic.

Weighted graph: Edges are not treated equally. (Usage case: traffic, maps, etc)

Tree Graphs:

Properties of Tree Graphs: 1. connected and acyclic meaning that all vertices are connected by edges but there are no paths that start and finish at the same vertex. 2. Removing edge disconnects graph 3. Adding edge creates a cycle

Ruby Implementation:

Methods Needed: – initialize with root node – add a new node (vertex) + validate that it has required edges – add a new edge – to be called when new node is added – remove a node + validate that its edges are removed – remove edge when node is being removed – sum of all node values

Recursion 003

#recursion #datastructures #devstudy #balancedparenthesis #boolean

The Problem:

Write a method that accepts a string containing open or closed parenthesis and returns true if the string has a balanced set of parenthesis. Use recursion if possible.

Using the 10DIME approach to making sure I understand the problem:

Input: a string of parenthesis

Output: boolean. true if balanced, false if not balanced

Definitions: – balanced means that the string has the same amount of left brackets as right brackets – not balanced means that there is an uneven amount of brackets

Instructions:

  1. make string an array and remove the commas

Solving through iteration idea: 2. IF ODD: I want to split the string into characters, check if there is an odd total amount of chars, if so, return false 3. IF EVEN: I could: – iterate through, collect all left brackets, save the count – collect all right brackets, save the count – if they are the same, return true

Solving through recursion idea:

What is my repeating function?

What is happening each time the recursion is called? i

Methods: N/A

Edge Cases: – if array is empty – if array only contains one type of bracket

ITERATIVE IMPLEMENTATION:

def is_balanced?(string) return false if string.empty? arr = string.chars.delete_if { |s| s == "," } if arr.count.odd? false else left = [] arr.each do |bracket| if bracket == "(" left << bracket arr.delete(bracket) end end left.count == arr.count ? true : false end end

p is_balanced?("") == false p is_balanced?("(") == false p is_balanced?("(,)") == true p is_balanced?("(,(,(,),)") == false p is_balanced?("(,(,(,(,(") == false p is_balanced?("(,(,(,),),)") == true

Recursion 003

#recursion #datastructures #devstudy #balancedparenthesis #boolean

The Problem:

Write a method that accepts a string containing open or closed parenthesis and returns true if the string has a balanced set of parenthesis. Use recursion.

Using the 10DIME approach to understanding the problem:

Input: a string of parenthesis

Output: boolean. true if balanced, false if not balanced

Definitions: – balanced means that the string has the same amount of left brackets as right brackets – not balanced means that there is an uneven amount of brackets

Instructions:

  1. make string an array and remove the commas

Planning out Iterative Function instructions: 2. IF ODD: I want to split the string into characters, check if there is an odd total amount of chars, if so, return false 3. IF EVEN: I could: – iterate through, collect all left brackets, save the count – collect all right brackets, save the count – if they are the same, return true

Planning Out Recursion Function Instructions:

  • I realized that I didn't need to remove the commas from the input string if my input just didn't have commas to begin with. The original problem did not say there would be commas so I need to think more carefully about the question next time.

1. Base case: there are zero elements left. arr.empty? 2. Function: What is the repetition required to solve this problem? compare one element to the next and if they do not match, remove both: arr.each_with_index do

`if arr[0] != arr[1] # remove both

3. Next-To-Last Case: arr[0..c-3] 4. Recursion Function: compare[0..c-3] where compare is a function that compares the first and the second item in an array. If they are not equivalent, both items are deleted.

So this is what I want to repeatedly call:

def compare(array) if array[0] != array[1] array.delete_at(0) array.delete_at(1) else (reduce size until base case is met) end end

5. What does this look like when the program is running?

Given an array of elements: arr = [x0, x1, x2, x3, x4, x5] 1. The first call will compare x0 != x1, let's say this is true so those elements are removed from array. So we can say that [x0,x1,x2,x3,x4,x5] == [x2, x3, x4, x5].push(x0,x1) where we call the recursion on [x2, x3, x4, x5] part

  1. [x2, x3, x4, x5] == [x4, x5].push(x2, x3)

  2. [x4, x5] == [].push(x4, x5)

  3. [].empty? is our base case = code finished.

Methods: N/A

Edge Cases: – if array is empty – if array only contains one type of bracket

ITERATIVE IMPLEMENTATION:

def is_balanced?(string) return false if string.empty? arr = string.chars.delete_if { |s| s == "," } if arr.count.odd? false else left = [] arr.each do |bracket| if bracket == "(" left << bracket arr.delete(bracket) end end left.count == arr.count ? true : false end end

p is_balanced?("") == false p is_balanced?("(") == false p is_balanced?("(,)") == true p is_balanced?("(,(,(,),)") == false p is_balanced?("(,(,(,(,(") == false p is_balanced?("(,(,(,),),)") == true

recursion implementation: NOT COMPLETED

def is_balanced?(input) return false if input.empty?

input.class == Array ? input : input = input.chars

count = input.count return false if count == 1

if count == 2 if input[0] != input[1] return true else false end elsif count > 2 return false if input.uniq.size == 1 input.each_cons(2) do | first, second | if first != second input.delete_at(0) input.delete_at(1) is_balanced?(input) else is_balanced?(input.shuffle) end end end end

p is_balanced?("") == false p is_balanced?("(") == false p is_balanced?("()") == true p is_balanced?("((") == false p is_balanced?("((())") == false p is_balanced?("(((((") == false p is_balanced?("((()))") == true

#recursion #datastructures #devstudy #average #sum

The goal is to find the average of an array of integers using recursion.

This is what I have from last attempt found here: https://write.as/effyverse/recursion-101

Attempt 1:

def average(arr) count = arr.count if count == 1 arr[0..count-1].sum/count else average(arr[0..count-2].sum / (count-1)) * arr[count-1] end end

a = [1,2,3,4,5] p average(a) == 3

b = [0,10] p average(b) == 5

c = [1] p average(c) == 1

Mistakes made:

__Implementation Errors: – I am calling my recursion function with the wrong input. Instead of passing in an array, I am passing in the average, fully computed.

__Understanding Errors:

  • I originally thought that my next-to-last case is represented by arr[0..count-2].sum. This is wrong because my next-to-last case is actually the ARRAY object of arr[0..count-2] and NOT the sum of it. The sum aspect is a part of the function, not the input case. It makes no sense to view the input as a sum when the method input is the array of integers — this confusion of what my input cases are supposed to be informed the implementation error above.

  • I originally thought that my base case would be the last input to be computed by the recursive function instead of thinking of it as the END of the recursive call, as the case where the recursion call is no longer needed.

Attempt 2:

Find average of array of numbers using recursion

def average(arr) count = arr.count if count == 0 0 elsif count == 1 arr[0] else sum_of_all_num = average(arr[0..count-2]) * (count-1) + arr[count-1] avg = sum_of_all_num / count end end

p average([1]) == 1 p average([0,10]) == 5 p average([1,3,5,7]) == 4

Explanation of thought process for recursion call:

What is our function? average = arr.sum / arr.count

What does this tell us? arr.sum = average * arr.count

What do we know? – If we remove the last case from our average function input and express it outside of the recursive function call, we have: sum_excl_last_num = average(arr[0..count-2]) * (count-1)

  • remembering that our goal is to find the average of all num so we need: sum_of_all_num = sum_excl_last_num + arr[count-1]

  • calculate average:
    avg = sum_of_all_num / count

  • refactor: sum_of_all_num = average(arr[0..count-2]) * (count-1) + arr[count-1] avg = sum_of_all_num / count