that is interesting
#algos-and-data-structs
old rover
onyx root
(except i got the bounds wrong, but you see the idea)
agile sundial
~~range(2, sqrt(n))~~ye, the idea is there
onyx root
right 🙂
delicate geode
Turns out I can handle special cases of one array has 0, and I got my memory usage and speed up to 90%+!
I'm so happy 🙂 .
fiery cosmos
guys
i am trying to get from the nba player wikipedia list
a python list of all the current nba players
but I cant seem to figure out
how to specify the players while webscraping
this is the source code
fiery cosmos
oh thanks mate
lean dome
You can use any other singleton instead of None, if None is meaningful.
ROOT = object()
class Tree:
def inorder(self, node=ROOT):
if node is ROOT:
node = self.root
...
or, you can make it conditional on how many arguments you were called with:
def inorder(self, *nodes):
if not nodes:
node = self.root
else:
node, = nodes
...
(that's a confusing contract in this case, just pointing it out for completeness's sake)
fiery cosmos
line 21
contents, author, channel_name, time = bot.sniped_messages[ctx.guild.id]
^
IndentationError: expected an indented block
help
please
vocal gorge
line 21
contents, author, channel_name, time = bot.sniped_messages[ctx.guild...
Claim a help channel, see #❓｜how-to-get-help
scarlet maple
old rover
n factorial
dapper sapphire
So are both of the following roughly the same thing:
while (current != None):
while (current is not None):
this^ class would compare True with anything, including None. But is can't be spoofed; it checks for object equivalence.
spring jasper
they do different things
vocal gorge
considering is in CPython needs to just compare memory addresses and != calls __eq__, yeah, it's probably faster. But they are also different.
dapper sapphire
number1 = [1, 2, 3]
number2 = [1, 2, 3]
print(number1 is number2)
outputs: False
number1 = [1, 2, 3]
number2 = number1
print(number1 is number2)
outputs: True
dapper sapphire
this^ class would compare True with anything, including None. But `is` can't be ...
When you say object equivalence, do you mean it checks if two objects are the same or not?
Oh Oh
vocal gorge
When you say object equivalence, do you mean it checks if two objects are the sa...
a is b checks whether id(a) == id(b). In CPython, that's checking whether they have the same memory address - that is, are literally the same object.
old rover
does it matter if I use a linked list to create a stack
v using a list to create a stack
vocal gorge
depends on what you mean by "matters"
considering you're trying to implement a linked list, I suggest using it 😛
old rover
creating a stack with a linked list and creating a stack with a list
FILO still matters for both of these stacks right?
and it's O(1) to take the top element off the stack?
vocal gorge
It's in the definition of a stack, yes.
You can achieve all the complexities with both approaches.
dapper sapphire
You put that really well "the same memory address - that is, are literally the same object"
number1 = [1, 2, 3]
number2 = number1
number1.append(4)
print("number1:", number1)
print("number2:", number2)
print(number1 is number2)
It outputs the following, so changing one would change the other because both point to the same memory
number1: [1, 2, 3, 4]
number2: [1, 2, 3, 4]
True
Thanks a lot @vocal gorge
old rover
so then why would you ever use a linked list to create a stack
is there any inherent advantage
vocal gorge
not sure, tbh 🤷 🙂
linked lists are guaranteed O(1) insertion without any amortization, I guess
perhaps that matters for some
but most builtin stacks in languages are made on vectors
agile sundial
vector is a dynamic array
vocal gorge
~~what is a vector~~
resizable array. For example, Python lists. 
vocal gorge
yeah, they just happen to have the same name
old rover
Physics has vectors too
finite spruce
Physics has vectors too
those are at least related to the math ones lol
old rover
physics and chemistry is secretly math
finite spruce
physics vectors *are* math ones <:pithink:652247559909277706>
sorta, physics likes their coordinate transformation rules and such
vocal gorge
physicists use coordinates more, that's true
old rover
so it literally doesn't matter if you decide to create a stack from a linked list or a stack from a dynamic array/list
I think college classes teach stacks and queues in tandem
vocal gorge
your users probably won't care much
and yes, stacks and queues are extremely similar
old rover
class Stack:
def __init__(self):
self._items = []
def is_empty(self):
return not bool(self._items)
def push(self, item):
self._items.append(item)
def pop(self):
return self._items.pop()
def peek(self):
return self._items[-1]
def size(self):
return len(self._items)
so like
what is the difference between this
class Stack:
def __init__(self):
self._items = []
def is_empty(self):
return not bool(self._items)
def push(self, item):
self._items.insert(0, item)
def pop(self):
return self._items.pop(0)
def peek(self):
return self._items[0]
def size(self):
return len(self._items)
and this
finite spruce
the first will be faster for insertions and deletions
onyx root
The first is O(1) for push/pop, the second is O(N)
old rover
"It’s important to note that we could’ve chosen to implement the stack using a list where the top is at the beginning instead of at the end. "
how is the second O(N)
just curious
onyx root
@old rover inserting at the head of a list requires moving all the elements.
agile sundial
consider the list
L = [1, 2, 3]
``` and we want to add 4 to the front
`L.insert(0, 4)`
the list then becomes
`[4, 1, 2, 3]`
`1` used to be in the 0th index, but now it's the 1st, same with `2` and `3`oh right
insertion should be O(N) bc it's not a linked list
ok
there are no pointers you can reassign or anything
you have to resize the entire list
vocal gorge
not necessarily resize (perhaps there's still space left at the end of the allocated memory for the array), but you do need to copy the entire contents one place to the right, yes
jovial tartan
apologies if I'm interrupting but I'm really confused about what exactly Dijkstra's algorithm even does
it's finding a shortest path but to what?
jovial tartan
yeah but which other node?
agile sundial
one you pick
jovial tartan
as an input? all the implementations i've seen have only taken a start as an input
old rover
why is the first one not O(1) when it's also just a list?
agile sundial
because it's not the fact that is' not a linked list that makes it O(n)
jovial tartan
why is the first one not O(1) when it's also just a list?
is the first one a linked list?
haven't seen the start of this convo
agile sundial
inserting at the front of a list is O(n) because you must move all the elements to the right, one space to the right
adding to the end moves 0 elements to the right, so it's O(1)
vocal gorge
as an input? all the implementations i've seen have only taken a start as an inp...
That's just to not bother with implementing that. Generally, the algorithm finds distances from the given node to all other nodes.
finite spruce
as an input? all the implementations i've seen have only taken a start as an inp...
the variant you mention doesn't output a single path, but rather a "shorted-path tree", so it gives you the shorted path from your single "input node" to any other node in the graph
old rover
class Stack:
def __init__(self):
self._items = []
def is_empty(self):
return not bool(self._items)
def push(self, item):
self._items.append(item)
def pop(self):
return self._items.pop()
def peek(self):
return self._items[-1]
def size(self):
return len(self._items)
this is the first one for context
agile sundial
are you familiar with lists?
old rover
yes
old rover
the first one is not a linked list
agile sundial
yes, neither of them are
spring jasper
unrelated but why arent you using your linkedlist class to implement a stack
sounds like good practice
old rover
I was using my linked list to implement a stack
this is just another resource talking about stacks
spring jasper
oh okay, carry on then
old rover
when would I want to implement a stack with a list rather than a linked list?
agile sundial
there's no real difference
except implementing the linked list first may be annoying
old rover
you'd have to create the linked list with the node class and the linked list class with all the methods
and then create another class called Stack
spring jasper
You already have made the linkedlist tho
old rover
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def insert_first(self, new_element):
new_element.next = self.head
self.head = new_element
def delete_first(self):
if self.head:
deleted_element = self.head
temp = deleted_element.next
self.head = temp
return deleted_element
else:
return None
class Stack(object):
def __init__(self,top=None):
self.ll = LinkedList(top)
def push(self, new_element):
self.ll.insert_first(new_element)
def pop(self):
return self.ll.delete_first()
I'm a little bit confused by this
I've never seen classes take parameters
onyx root
classes don't take parameters. That's python 2 syntax. Where did you get it from?
onyx root
why are you looking at this code?
isn't this the tenth list implementation you've looked at?
old rover
no this is for a stack
vocal gorge
Classes can take object in Python3 too, it's just not needed anymore.
old rover
I can do most of the linked list functions by myself now
spring jasper
Did you do the reverse one
onyx root
@old rover read this code, understand what it does. Then delete it, and write it yourself.
onyx root
what is self.ll
you see in the code where it's assigned, yes?
dapper sapphire
Should one know how to implement doubly linked list and circular linked list before moving to trees?
spring jasper
a circular linkedlist is just a linkedlist whose tail points to the head, it doesnt sound that much more complicated
dapper sapphire
Is understating of single linked list is all that's required for trees?
spring jasper
doubly linked lists are just one more pointer
fiery cosmos
@dapper sapphire I used to teach data structures and yes absolutly, because you may get lost. You use the lists to learn about references and then the tree to learn about recursion
@dapper sapphire A "Thread" is a path through the tree nodes that ends up being a double linked list (if you have ptrs up and down) so you definetly want to have that down path and not jump on your foundations.
dapper sapphire
<@!673649624250056721> I used to teach data structures and yes absolutly, becaus...
Oh ok, I'll definitely learn doubly linked list and circular linked list before learning Trees.
fiery cosmos
@dapper sapphire At my college the courses are broken up like this, students need to implement and understand a ll of those, and big O notation as to what the worst case search should be (not derive, just know).
Data Structures 1: Array, Vector, Linked List, Double Linked List, Queue (FILO, FIFO) and Recursion Searches
Data Structures 2: Review of Recursion, Binary Tree (lab1), AVL Tree (self balancing, lab2/mid term), Huffman Coding Tree (compression, final project), BSP tree.
Of which, I really believe only the Huffman coding is the one that student's only need to know if they want to know how compression/mpeg/etc. And BSP tree is only useful if you will be doing 3d stuff.
Circular linked list are important in DSP because many API's use these as drivers to the audio buffers, like in Direct Audio (part of DirectX)
@dapper sapphire You are doing yourself a great favour doing this. Once you get into more complex programming you will understand it a lot better. Its kind of a "separate the kids from the grown up" type of topics. Script kiddies don't know these, professional programmers do. And you will find them in tons of employment tests.
@dapper sapphire There are tons of great demos online and youtube videos, stuff like this. https://www.cs.usfca.edu/~galles/visualization/BST.html
dapper sapphire
@fiery cosmos that was great advice and really helpful that you mentioned the learning structure. Appreciate the help!
fiery cosmos
@dapper sapphire if you speak french i'll send you my course notes haha. Its in C++ though.
dapper sapphire
haha no I dont speak french. But I'll take my time with these linked list concepts before learning about harder concepts.
old rover
it is good to spend time on linked lists
fiery cosmos
it is good to spend time on linked lists
I agree, of the data structures that I use on a regular basis in programming, Array, Linked List, Queue and Recursion Searches are the ones that at any given time I may be implementing or using. Trees I just have to understand how they work, mostly for indexes in mongo and how to structure my indexable fields. But shannon's "other" theorem that anything can be done in recursion that can be done in a for loop and vice versa is gold.
So for "recursion" typically i have students re-implement their tree search function iteratively if they did it with recursion, or vice versa if they did it with the loop. The course is also heavy on coding (its college not university) so they spend a lot of time in their code learning how to make good code without memory leaks etc in C++. Not that in python you would need to worry about that, but you will "sit" in that AVL code for a while since your AVL is based on your binary tree, so you will learn from your mistakes. Good stuff
agile sundial
wait, you use linked lists on a daily basis?
old rover
interesting
vocal gorge
wait, you use linked lists on a daily basis?
maybe they're a Haskell programmer and use List a lot
i guess
fiery cosmos
The concept of a linked list, or a chain of patterns. Yes its used a lot because we have really complex workflows we pass through Airflow or Nifi, which is the "concept" of a linked list. Its a chain of responsibility pattern but its based on the logical concepts of al inked list. I haven't used an ACTUAL linked list in a couple years, last time was when doing some low-level filesystem programming.
agile sundial
does that mean every chain of events is a linked list?
vocal gorge
isn't the normal list in haskall a linked list
yeah, that's what I meant.
fiery cosmos
Not a chain of events, a chain of responsibility pattern. Like custom workflows according to the data type that gets passed on to the right according to a flow path.
Remember these are concepts, not the actual implementation.
lean dome
when would I want to implement a stack with a list rather than a linked list?
both dynamic array and linked list are reasonable choices for the data structure backing a stack. If you implement it with a linked list, push() will be inserting a new node before the head, and pop() will be removing and returning the head node. If you implement it with a dynamic array, push() will be inserting a new element at the end of the array (resizing the array if necessary), and pop() will be removing and returning the last element of the array.
If you go with a linked list, push and pop are both O(1) in best, worst, and average case. If you go with a dynamic array, pop is O(1) in best, worst, and average case, and push is O(n) in worst case, but amortized O(1) in average case.
old rover
ok
mint jewel
Generally, going with the dynamic array is better however, due to cache locality. More than one level of indirection is slow.
old rover
what is cache locality
onyx root
why do you cross that out?
old rover
and they kicked me out for being a noob
vocal gorge
~~what is cache locality~~
Not having to load the elements one-by-one, but loading a part or the entire vector in the CPU's cache at once.
old rover
oh that's cool
lean dome
elements in an array are right next to one another in memory, so accessing them can be cheaper (due to caching) than accessing nodes in a linked list that were allocated at different times, and might be far from each other in memory.
vocal gorge
that's the main problem with linked lists - they are just slower, because to get the next element, you need to follow a reference
mint jewel
Linked lists are great for concurrent queues
lean dome
whether to use a dynamic array or a linked list for your queue depends a lot on your expected access pattern. A dynamic array will generally give better performance, but depending on your pattern of pushes and pops, and the maximum number of elements that wind up enqueued at once, the answer may be different.
vocal gorge
@old rover See also: this rant
https://rust-unofficial.github.io/too-many-lists/index.html#an-obligatory-public-service-announcement
lean dome
We should all as a community say no to linked lists as a "standard" data structure. It's a fine data structure with several great use cases, but those use cases are exceptional, not common.
I agree.
old rover
I agree that they are terrible data structures
but if my interviewer asks me about them then I should better know them
vocal gorge
these questions are probably pretty much "did the candidate get any DSA education"?
since if they have, they can probably implement it from memory regardless of how much they hate them and never use them
lean dome
Linked lists are taught early because they're one of the easier data structures to learn. They're not a data structure with many common uses, though.
old rover
the more you use them the more likely you are to be able to memorize them
so that is what I'm doing
but I'm not trying to memorize them
I'm trying to understand them
lean dome
learning them is definitely good and helpful. Just understand that you're going to also learn more data structures, and those others are generally better than linked lists for most real-world use cases.
vocal gorge
the more you use them the more likely you are to be able to memorize them
not really, since when you use them, you probably aren't reimplementing them each time, if you implement them at all. It's about understanding how they work, indeed.
old rover
how to reassign pointers
I think I got so burnt out I forgot how to reassign properly
I didn't know that could happen
lean dome
Python doesn't have pointers, it has references. Every time you do self.tail = new_node, you're changing what self.tail references.
old rover
yes I know
but people use pointers and references interchangably
it is actually references in python
lean dome
but people use pointers and references interchangably
they shouldn't... they mean different things, and some languages (like C++ and Rust) have both.
lean dome
stacks + queues
interestingly, a queue can't really be efficiently implemented with a dynamic array, like a stack can. Dynamic arrays support appends and removals at the end efficiently, but not insertions or removals at the beginning - so they're not suitable where elements are being added at one side and removed at the other.
vocal gorge
but people use pointers and references interchangably
references are kinda like smart pointers. Like, at runtime a reference is just a pointer, the only difference is in code - a reference is guaranteed to point to an object. They can also get tracked at compile time - for example, Rust ensures at compile time you can never take a mutable reference to an object when a reference (mutable or not) exists to it - because bad things can happen in that case:
This restriction allows for mutation but in a very controlled fashion. It’s something that new Rustaceans struggle with, because most languages let you mutate whenever you’d like.
The benefit of having this restriction is that Rust can prevent data races at compile time. A data race is similar to a race condition and happens when these three behaviors occur:
Two or more pointers access the same data at the same time. At least one of the pointers is being used to write to the data. There’s no mechanism being used to synchronize access to the data.Data races cause undefined behavior and can be difficult to diagnose and fix when you’re trying to track them down at runtime; Rust prevents this problem from happening because it won’t even compile code with data races!
mint jewel
Oh yeah, how do array backed deques work
vocal gorge
(I think another reason people don't like calling references pointers is because a reference doesn't strictly have to be implemented as a pointer to a memory address, but in other ways)
lean dome
Oh yeah, how do array backed deques work
they're a combination of a linked list and a dynamic array, basically. The data structure behind them is a doubly linked list of fixed-capacity arrays.
quick cobalt
Hello tell me where to go with the code from the design for embed?
lean dome
which allows efficiently inserting a new chunk at the beginning, and puts an upper bound on the number of elements that will need to be moved if you prepend when there's a chunk with remaining capacity at the beginning.
mint jewel
Ah, that's smart
lusty yew
Can anyone explain/summarize the logic behind recursion?
onyx root
Can anyone explain/summarize the logic behind recursion?
solve a problem by doing a little work to reduce it to a smaller version of the same problem. keep going until you get to the trivial case.
lusty yew
solve a problem by doing a little work to reduce it to a smaller version of the ...
hmm...but what advantage does calling a function itself provide that other methods cant?
onyx root
hmm...but what advantage does calling a function itself provide that other metho...
it might be the simplest way to express the idea
old rover
the normal way is the iterative way right
onyx root
often, iteration can do the job well too.
spring jasper
The iterative way is the iterative way
agile sundial
it's the same idea, you're repeating the same work on a smaller (maybe easier) version of the problem
lusty yew
so is there a particular place where its very viable to use?
onyx root
so is there a particular place where its very viable to use?
recursive data structures like trees or nested dictionaries naturally fit recursion
lusty yew
I can't wrap my mind around it
spring jasper
Time to pull out the trusty pen and paper
lean dome
the normal way is the iterative way right
That depends. Some functions have naturally recursive definitions. For these functions, the recursive way might be considered normal, and an iterative one is a potential optimization.
old rover
interesting
lean dome
when teaching people recursion, it's common to start with a function that prints the Nth element of the Fibonacci sequence. That's a common starting point because the Fibonacci sequence has a naturally recursive definition: the Nth Fibonacci number is 0 if N == 0, 1 if N == 1, and otherwise it's the sum of the N-1th and N-2th Fibonacci numbers.
lean dome
searching for an element in a binary tree is another example of a function that has a naturally recursive solution.
When called on an empty tree, the search fails.
When called on a tree whose root node holds the searched value, the search succeeds.
Otherwise, the search succeeds if searching either the left or right subtree of the given tree succeeds.
long storm
> We should all as a community say _no_ to linked lists as a "standard" data str...
i stand behind this
vital rune
Can anyone help with AVL tree code?
lean dome
possibly - what sort of help?
fair prairie
A question
When we have sort() in python then why mergesort is created?
And also bubble sort, etc
vital rune
def insert(self, root: Node, val: T) -> Node:
"""
REPLACE
"""
if self.origin is None:
#new_root = Node(val)
self.origin = Node(val)
self.size = 1
return self.origin
if val < root.value and root.left is not None:
return self.insert(root.left, val)
elif val > root.value and root.right is not None:
return self.insert(root.right, val)
elif val < root.value:
root.left = Node(val, root)
self.size += 1
elif val > root.value:
root.right = Node(val, root)
self.size += 1
root.height = max(self.height(root.left), self.height(root.right)) + 1
new_root = self.rebalance(root)
return new_root
@lean dome The insert function is not updating the tree correctly and it seems like everything is going to the right side of the tree
I would appreciate the help I currently have 1 hour haha
agile sundial
an hour for?
lean dome
what is origin? What is root?
vital rune
origin is the highest node in the tree and its an attribute of the AVL class
root: Node: The root Node of the subtree in which to insert val.
val: T: The value to be inserted in the subtree rooted at root.
vital rune
an hour for?
An hour to work on this lol
lean dome
so root isn't the root of the tree, it's the node to insert the new value below.
that's confusing naming...
vital rune
yeah I feel like that might be what my problem is haha
so from the test cases I have the origin value is the first thing thats wrong
but it seems the function is just adding everything to the right leaf of each node and not balancing
Is this something you think you could help me with? I'm kinda desperate 😂
lean dome
what's your rebalance method doing?
spring jasper
I'd start with properly naming variables so that part of the confusion is out of the way
vital rune
def balance_factor(self, root: Node) -> int:
"""
REPLACE
"""
if root is None:
return 0
h_L = self.height(root.left)
h_R = self.height(root.right)
return (h_L - h_R)
def rebalance(self, root: Node) -> Node:
"""
REPLACE
"""
bal = self.balance_factor(root)
if bal == -2:
if self.balance_factor(root.right) == 1:
self.right_rotate(root.right)
return self.left_rotate(root)
elif bal == 2:
if self.balance_factor(root.left) == -1:
self.left_rotate(root.left)
return self.right_rotate(root)
return root
renaming origin to root and root to subtree would help.
vital rune
I'm not naming the variables so that's not up to me haha
Some of these methods call other methods, would it be a good idea to show you the whole file?
halcyon plankBOT
lean dome
rebalance is returning a new node, but you don't seem to actually be attaching that new node to the tree at all
vital rune
how would that change my code?
lean dome
wait, nevermind - I read something wrong
lean dome
I give up. I'm not infinitely familiar with AVL trees, and that's too much code for me to quickly spot the bug.
vital rune
Well thanks anyway haha i appreciate it
lean dome
My suspicion is that your rebalance must be wrong if you're not winding up with balanced trees.
vital rune
The rebalance is passing the test cases I was given though
vital rune
is it origin?
lean dome
shouldn't it be:
if val < root.value and root.left is not None:
root.left = self.insert(root.left, val)
return root
elif val > root.value and root.right is not None:
root.right = self.insert(root.right, val)
return root
or something like that?
you need to be taking the values returned by the recursive calls to insert and attaching them to the tree - by assigning them to attributes of root
vital rune
Ok I get that I think
By changing that I still get
Traceback (most recent call last):
File "my_tests.py", line 585, in test_insert
self.assertEqual(1, avl.origin.value)
AssertionError: 1 != 0
Well anyway @lean dome thanks for trying! I really appreciate it
blazing tartan
@sour tide here's my rough implementation:
# can an unordered array be split into two arrays with equal sums
from itertools import permutations
import pytest
def split_into_equal(array):
class InvalidPermutation(Exception):
pass
sum_array = sum(array)
# give up if small array or the total is odd-numbered
if len(array) < 2 or sum_array % 2:
return (-1, None)
target = sum_array / 2
for p in permutations(array):
sa1 = []
sa2 = []
satisfied = False
try:
for v in p:
if not satisfied:
sa1.append(v)
if sum(sa1) == target:
satisfied = True
if sum(sa1) > target:
raise InvalidPermutation
else:
sa2.append(v)
except InvalidPermutation:
continue
return (sa1, sa2)
return (-1, None)
def test_true():
array = [5, 11, 5, 1]
sa1, sa2 = split_into_equal(array)
assert sa1 == [5, 5, 1]
assert sa2 == [11]
def test_negative():
array = [-5, -5, -1, -11]
sa1, sa2 = split_into_equal(array)
assert sa1 == [-11]
assert sa2 == [-5, -5, -1]
def test_false():
array = [1, 5, 3]
sa1, sa2 = split_into_equal(array)
assert sa1 == -1
assert sa2 is None
def test_bad():
with pytest.raises(TypeError):
split_into_equal()
assert split_into_equal([0]) == (-1, None)
assert split_into_equal([1, 2]) == (-1, None)
sour tide
neat! thanks!
blazing tartan
I have no idea what the complexity is, and the middle bit could probably be improved
if not satisfied: has a bad smell
also, thanks to you, I now have a keyboard shortcut in my editor to run the current file through pytest ;)
sour tide
subscribe to this man's youtube guys!
blazing tartan
…i forgot that was linked there, haha
main bison
cool problem @fiery cosmos
main bison
so how did you think of solving it? and why do you think it did not work?
fiery cosmos
because the first jump will make k become k-1
and i make a jump in time every time i hit one of the largest gaps
im only allowed to jump every cow year so everytime i jump i have to wait a certain multiple of 12
i would wait until i hit one of the largest gaps
and when i hit one of the largest gaps, if im not on a cow year yet, i wait more until i hit a cow year
as to where i should jump to, i made a list called floors
floors contains all the possible locations to jump to in relation to the years of the ancestors
for example, one of the ancestors lived 101 years ago
so one of the floors would be 108
because i can only jump to a cow year (aka a multiple of 12) and it would be only rational to jump to the cow year before the ancestor year
i came up with something like this
var = list(map(int, input().split()))
n = var[0]
k = var[1]
years = []
for i in range(n):
years.append(int(input()))
years = sorted(years)[-1::-1]
years.append(0)
# print(years)
ans = 0
ranges = []
floors = []
for i in years:
m = i
while m%12!=0:
m+=1
if m not in floors:
floors.append(m)
# print(floors)
for i in range(n):
ranges.append(years[i]-years[i+1])
ranges = ranges[-1::-1]
ranges = ranges[0:k-1]
# print(ranges)
jumplocs = []
for j in ranges:
for i in range(n):
if years[i]-years[i+1]==j:
jumplocs.append(years[i])
break
jumplocs = jumplocs[-1::-1]
# print(jumplocs)
for i in range(len(jumplocs)):
while jumplocs[i]%12!=0:
jumplocs[i]-=1
# print(jumplocs)
# print(floors)
# print(jumplocs)
cur = 0
#landing location - jump location
for i in jumplocs:
ans+=floors[cur]-i
for j in range(len(floors)):
if floors[j]<=i:
cur = j
break
print(ans)
the first few lines just for initialization and stuff
main bison
so how does your datastructure look like?
fiery cosmos
mainly just lists
main bison
do you have a list of lists?
fiery cosmos
i dont think so
main bison
would it make sense to chunk years together?
fiery cosmos
i guess
but i also think that would be a bit much
considering that i would leave that for the end
fiery cosmos
yeah i get what you mean
main bison
so if we chunk them together based on 12-year intervals, then we could see if that alone works.
like if len(my_list) is equal or smaller then K
if its not, then we know we have to join two times together
fiery cosmos
yeah i get what you mean
ohhh
yeah yeah ok
because you can't jump in between 12 year intervals
main bison
and this does look like a recursive problem
main bison
because you can't jump in between 12 year intervals
correct
fiery cosmos
for some reason i was worried about that lmao
main bison
if you need to join two together, then you can just test them all and see what gives the best result for amount of years spent
main bison
the amount of time you time-travle is also unimporant
the only thing that is important is the amount of time you need to wait to cover all cases
best case is that the year you travle to already is mod 12
as you can travle, register a visit, and travle again. spending 0 years
then there is when you need to wait 12 years
then 24 years
and so on
so finding the combinations that gives the least amount of waiting is the only key
fiery cosmos
no no it says none of the ancestors are cow years
at the minimum everytime i jump i need to wait 12 years
main bison
oh i missed that..
well, the amount of years still does not matter, only the difference between the chunks matter
None of Bessie's ancestors live in Ox years. right.. i see it now
austere sparrow
The _iterative_ way is the iterative way
that's recursion
old rover
what's the point of range(len(iterable):
I can figure out when to use range
and I can figure out when to use len
but I can never figure out how to use both of them on my own
it's not a hard concept to grasp it's just 0 to whatever the length of the iterable is
vocal gorge
indeed. I don't quite get what you're asking.
spring jasper
Its unpythonic and it originates from the dark times of C and the likes where they would loop over a range and use that as the index for accessing stuff
vocal gorge
yeah, it's just an ugly enumerate
spring jasper
If for some reason you want only indices of an array you use
for index, _ in enumerate(...):
But thats (almost) never the case
agile sundial
well if you only want indices range is ok
old rover
like I've seen it used in college and the TA just says oh use range(len(iterable):
like out of nowhere
It concerns me that I don't know when to use it
spring jasper
You use it when you need a range thats the length of your iterable?
old rover
but how am I supposed to know when to do that
green light
pretty much never
agile sundial
is your ta doing something like
for i in range(len(list)):
do something with list[i]
Suppose you have a list, lst. Write code to print all indexes i such that lst[i] < lst[i+1] - that is, the positions of all elements that are lower than the next one.
(naturally, such i can be from 0 to len(lst) - 2 - because for the last index, there's no next element)
old rover
is your ta doing something like
```py
for i in range(len(list)):
do something ...
yeah basically
agile sundial
ok, don't listen to that person anymore
old rover
I'm not in college for CS anymore but I just never used it much
agile sundial
ok, good
old rover
so enumerate basically does the same thing
it's just indexes and elements
of the iterable
spring jasper
Ye
green light
yeah, ideally never use range. you can get the same behaviour using enumerate and array slicing (if you need a stride for example)
old rover
wow looks like the TAs didn't know what they were talking about then
the professors used range(len(iterable) too
green light
its not the end of the world. its nice to have multiple viewpoints, but yeah, there's some best practices
jolly mortar
I used something similar to range(len(iterable)) once for creating slices of a certain length
[iterable[i:i+n] for i in range(0, len(iterable), n)]
lean dome
range(len(sequence)) isn't exactly bad. It's the best way to iterate over the indices of a sequence when you don't need the elements. That's rare, though. When you do need the elements, py for i in range(len(sequence)): elem = sequence[i] is a less Pythonic, more verbose way of doing either py for elem in sequence: or ```py
for i, elem in enumerate(sequence):
Usually it's a sign that the code was naively ported from a language where for loops loop over indices rather than values.
That's not necessarily a bad thing, per se - that can be a useful intermediate step in porting some algorithm to Python. Write it exactly how it looks in some other language by transcribing line by line, add tests to ensure it's working as expected, and then begin changing the implementation to follow Python idioms instead of C idioms, letting the tests tell you if you make a mistake in modifying it.
old rover
ok
odd nacelle
Heyo guys, anyone wanna try their hand in some dict comprehension?
Been at it for 15 minutes, the nested structure is killing me
Fwiw, i'll probably stick to what I have atm, it's just bothering me to know that it's possible but that I can't wrap my head around it haha
finite spruce
I think the following would work:
averages = {member: (val["total"] / val["count"]) for member, val in data.items()}
aha, that's way simpler than what i was attempting
i somewhat tried nesting my dict comprehensions to extract the values of the total and count keys
accessing the values of the keys directly in the top level dict didnt even occur to me
thanks!
old rover
class Stack:
def __init__(self, top =None):
self.ll = LinkedList(top)
def push(self,new_element):
self.ll.append_left(new_element)
def pop(self):
return self.ll.delete_node()
what is self.ll??
these methods actually make sense
odd nacelle
its defined on the __init__ isn't it?
old rover
like push would add an element on the top so I use append left which adds anode behind the head
oh
odd nacelle
it's a LinkedList object
odd nacelle
i assume so, you'd have to look at the LinkedList docs
old rover
Udacity doesn't really explain it
odd nacelle
ahh i see, python doesnt have a native linked list library
odd nacelle
was not aware of that, alright, so what does the linkedlist class youre provided with look like?
old rover
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
self.tail = node
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def append_left(self,data):
node = Node(data)
node.next = self.head
node = self.head
def append_right(self, data):
node = Node(data)
self.tail.next = node
self.tail = node
def delete_first(self):
deleted = self.head
if self.head is not None:
self.head = self.head.next
deleted.next = None
return deleted
def delete_node(self, node):
node.data = node.next.data
node.next = node.next.next
class Stack:
def __init__(self, top =None):
self.ll = LinkedList(top) #the Stack
def push(self,new_element):
self.ll.append_left(new_element)
def pop(self):
return self.ll.delete_node()
you can also implement a stack class without a linked list class
that is what G4G said
but the big O would probably be different for taking the top off and putting another element on top
agile sundial
big O is all the same
old rover
oh
agile sundial
can you figure out why that is the case?
old rover
why it's the same for stacks created by lists and linked lists?
and stacks created with just a stack class?
agile sundial
for stacks backed by a dynamic list vs stacks with linked lists
old rover
bc push and pop only work with the top part of a stack?
when you push you put one more element on the top of a stack
when you pop you take the top element off
is the only negative for a stack that if you wanted the bottom element you would have to pop every element until you get to the bottom?
what does FIFO mean for queues
first in first out
lean dome
Yeah. With a queue, if you enqueue A then B then C, then the next 3 calls to dequeue will return A then B then C
With a stack, if you push A then B then C, the next 3 calls to pop will return C then B then A
Queues are first in, first out. Stacks are last in, first out.
lean dome
Adding a value to a stack is called "pushing" it, removing the next value from the stack and returning it is called "popping" it.
Adding a value to a queue is called "enqueueing" it, removing the next value from the queue and returning it is called "dequeueing" it.
old rover
oh
lean dome
We use different words for both data structures as a reminder of the fact that the order of returned values is different.
old rover
it's that simple
lean dome
Yep.
lean dome
Conceptually, sure. But so are linked lists, conceptually.
old rover
I'm still annoyed that I can't write every linked list function on my own
I know most of them
lean dome
You'll get there. It doesn't hurt to circle back a bit later.
old rover
honestly I think I needed a break from bashing my head against the wall
lean dome
Yeah. Move on, and mark it as something to come back to later.
old rover
at least grokking has nice explanations and shows implementations for the algorithms
TIL grokking actually means understanding something
it's not an actual name
odd nacelle
More list comprehension puzzles anyone?
It's one part of python that just doesn't click for me for some reason
spring jasper
```python
class Node:
def __init__(self,data):
self.data = data
self.n...
I think your append_left is incorrect
old rover
I think your append_left is incorrect
did I flip a reassignment
lean dome
Yep, the last line.
old rover
I don't understand why this keeps happening
it's so frustrating
I understand reassignment
lean dome
Maybe reading = as "becomes" will help you?
spring jasper
Also in your stack impl, delete_node should take a node as param
old rover
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
self.tail = node
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def append_left(self,data):
node = Node(data)
node.next = self.head
self.head = node
def append_right(self, data):
node = Node(data)
self.tail.next = node
self.tail = node
def delete_first(self):
deleted = self.head
if self.head is not None:
self.head = self.head.next
deleted.next = None
return deleted
def delete_node(self, node):
node.data = node.next.data
node.next = node.next.next
class Stack:
def __init__(self, top =None):
self.ll = LinkedList(top) #the Stack
def push(self,new_element):
self.ll.append_left(new_element)
def pop(self):
return self.ll.delete_node(node)
it's underlined red
and it says node is undefined
oh
oh
I figured it out
if you're gonna pop you'd be using the delete_first method
spring jasper
You need checks in delete_node
What if youre trynna delete the tail node
The tail's next is None, so if you try tail.next.next youre gonna get errors
old rover
oh boy
that is actually from a leetcode question
and it assumed that the node you inputted was not the tail
dapper sapphire
the node becomes the head
With:
self.head = node
Does node becomes the head, or head becomes the node?
old rover
the node becomes the head
dapper sapphire
when you do the following:
number = 3
Does 3 become number, or does number become 3?
old rover
the number becomes 3
dapper sapphire
Then with:
self.head = node
Wouldnt head become node?
dapper sapphire
Yeah, it does and I see what you mean.
old rover
normally reading right to left works for me with equal signs
I have tried reading left to right with equal signs and I still mess up
x = 1
z = 99
x = z
x is now 99
bc you read it right to left
dapper sapphire
but when you say node becomes the head. It's like you are assigning head to node, like the following:
node = self.head
which is different from
self.head = node
Hope someone else can comment on the following that is it head becomes the node or node becomes the head or would both/either be fine:
self.head = node
there the node becomes the head
node = self.head the head becomes the node....
but I can't explain why that's bad
it's just wrong
lean dome
I think the clearest way to read it is "is set to", personally.
"self.head is set to node"
lean dome
Nah, you guys are right. That can still be read both ways.
old rover
I just don't understand why I'm screwing it up
lean dome
"is set to" only works one way
old rover
it's very frustrating
lean dome
x = 3 - x is set to 3. You can't read that as "3 is set to x" - that only works one way
lean dome
"3 is assigned to x"
old rover
x has a pointer to 3 in memory
lean dome
You could do "references" for that, but that will probably just confuse you when you start using languages with primitive types
fiery cosmos
Sheesh
lean dome
In Python, x = 3 could accurately be read as "x references 3" or "x refers to 3", but that's not true in C or Java, for instance
lean dome
The difference between a name and an object.
old rover
like variable names?
this one right
he should do something on ds/algos
that would be cool
dapper sapphire
like deque
old rover
so you can do
from collections import deque
but there's no from collections import LinkedList?
that's sad
old rover
that is true
lime kestrel
you can say da Q
Day cue
agile sundial
daca
rustic abyss
nice
agile sundial
specifically from which ends?
old rover
enqueue adds things to the tail
dequeue takes elements away from the front of the head
but with a deque you can enqueue on either end
so you can add elements on either end
bc a deque is a double ended queue
agile sundial
right, basically just a stack + queue
agile sundial
try it
old rover
Can’t maybe later
Turns out queue isn’t one of the container data types for collections
so if you want to make a queue you have to do it manually
just like you create a linked list
would there be a reason why someone would use a deque instead of a queue?
agile sundial
so you can pop from both ends
lean dome
can you do from collections import queue?
There's queue.Queue instead. I think it predates the existence of the entire collections module.
austere sparrow
There's `queue.Queue` instead. I think it predates the existence of the entire `...
jeez, how many queues does python have?
lean dome
Hm. 4?
austere sparrow
deque, asyncio.Queue, queue.Queue, multiprocessing.Queue?
lean dome
Yeah, those are the 4 I can think of.
austere sparrow
also pipes that you can use by creating a dummy process, I guess
but that's #esoteric-python
lean dome
There's os.pipe pipes, which you can use even within one process, as long as you're just sending bytes around
austere sparrow
there's also an option of sticking sockets together...
in two ways -- sockets and asyncio
austere sparrow
pushing to git while listening to a github webhook
old rover
So what is queue.queue
is it just a normal python queue
that doesn’t enqueue on both sides?
lean dome
Right. Enqueue on one side, dequeue from the other, has a lock in it to make it threadsafe.
And collections.deque allows adding to or removing from either side, but are a bit slower than queue.Queue
Same big O, but slower.
old rover
Just like how heaps have the same big O
Whether you implement them with a linked list class, a list, or just a heap class
lean dome
Yeah, or how something that's consistently exactly 10x slower than another thing has the same big O
agile sundial
you can't implement a heap with a linked lis
lean dome
You can, you just shouldn't, heh
agile sundial
well, maybe you can, but it would be dumb
old rover
you can implement a heap with a linked list
wait
I got confused
Oh boy I don’t think udacity covers heaps
what is up w these damn ds/algos things not covering topics
smh
oblique panther
You _can_, you just shouldn't, heh
you would just pretend that node.prev is left and node.next is right, yes?
old rover
that’s what I try to think
oblique panther
or maybe I'm thinking that heaps and trees have more in common than they do
agile sundial
a heap is pretty similar to a tree, yeah
lean dome
you would just pretend that `node.prev` is left and `node.next` is right, yes?
A heap is typically represented as an array with particular ordering constraints on the elements, and if you can represent it as an array in a particular order, you can also represent it as a doubly linked list in the same order
oblique panther
I do recall the array part.
lean dome
Both an array and a doubly linked list will allow you to swap elements around - it's just more expensive for the list.
agile sundial
and the O(n) indexing 🤢
lean dome
Yeah. You definitely shouldn't do it, but you definitely can, heh
agile sundial
well, that applies to many things
agile sundial
it is typical
spring jasper
But heaps are trees
spring jasper
How do you represent that constraint in an array
I guess a sorted array would do but a heap doesnt require elements be sorted
spring jasper
Huh yea, i guess i gotta read up on heaps then
old rover
<https://www.geeksforgeeks.org/array-representation-of-binary-heap/>
I thought G4G was discouraged
bc it's unpythonic
or what not
agile sundial
there's no code on that page so it's ok
lean dome
I just googled quickly to find a description of the array representation of a binary heap and shared the first link I found that explained it in a way I liked
Don't take that as an endorsement of g4g in general 🙂
old rover
It’s ok you’re not canceled
your advice is still valid in my eyes
not that it matters
dapper sapphire
Geeks for Geeks is discouraged?
dapper sapphire
oh ok.
strong grail
is important to learn oop to go deeper into machine learning ?
keen hearth
is important to learn oop to go deeper into machine learning ?
Hey, that's probably more appropriate for #software-architecture or #data-science-and-ml. It's definitely worthwhile learning about OOP to get the fullest out of Python.
old rover
OOP is definitely important
if you want to implement data structures in python you’d do it by using OOP
pseudo pilot
this is the problem:
https://leetcode.com/problems/wildcard-matching/
this is my recursive function:
def recursiveFunc(s, p, m, n):
if m > 0 and n <= 0:
return False
if m <= 0 and n <= 0:
return True
if m <= 0 and n > 0 and p[n - 1] == "*":
return True
if m <= 0 and n > 0:
return False
if m <= 0 and n > 0 and p[n - 1] == "?":
return False
if p[n - 1] == "*":
c1 = recursiveFunc(s, p, m - 1, n)
c2 = recursiveFunc(s, p, m - 1, n - 1)
if c1 or c2:
return True
elif p[n - 1] == "?":
c1 = recursiveFunc(s, p, m - 1, n - 1)
return c1
elif s[m - 1] == p[n - 1]:
c1 = recursiveFunc(s, p, m - 1, n - 1)
return c1
else:
return False
here s is the input string, p is pattern, m is length of s and n is length of p
its failing for some test cases, where am i wrong?
anyone pls help
summer lark
If a code has a for loop, then has a break statement, what would be the Big O complexity?
def nothing(n):
for i in range(n):
if n ==n:
break
print(n)
onyx root
you mean if i == n, and that would be O(n)
I guess? not sure why the code would be written like that in any case.
last fulcrum
For DS & A, what's the best python video course?
last fulcrum
Or what did you guys use to learn? I'm a total beginner.
fiery cosmos
im learning neural networks
If u want to learn how to build an AI i really can recomment videos of @vapid lintel
limber junco
I need to find the the sum of subsequence in increasing order having maximum value like [1,100,4,3,101,6,5] will have max sum as 1+100+101=202, [45,78,22,42,12,3,78] will have 22+42+78=142, [1,6,7,90,4,8,89] to will have 1+6+7+8+89=111. What would be the DP approach to solve this problem?
meager chasm
wha sup , im doing a maze game with turtle . i dont want the turtle to go outside the maze how to do this?
like i want the turtle to have a limits
how?
like border
kind wraith
@limber junco in the second sample it is like you differentiate from the sequence you have mentioned, shouldn't it be 45+78? Because 45 is the first lowest number in the list?
limber junco
<@507629867618140160> in the second sample it is like you differentiate from th...
@kind wraith Basically the problem is to check the subsequence which is in increasing order and has maximum sum, in this example the sequence 45,78 is in increasing order and has sum 123, but the sequence 22, 42,78 is also in increasing order and has sum 142 which is greater, hence 142 is the answer
It need not be consecutive numbers
glossy breach
Basically dynamic programming:
dp[i] is maximum sum increasing sequence ending with i
Formula: dp[i] = max(dp[j] for j from 1 to i - 1) + i
old rover
class Queue(object):
def __init__(self, head=None):
self.storage = [head]
def enqueue(self, new_element):
self.storage.append(new_element)
def peek(self):
return self.storage[0]
def dequeue(self):
return self.storage.pop(0)
so this is how Udacity does queues
is there a way to implement it with a linked list?
ofc you can
what is it with all these books using getters and setters
is there even a benefit to creating a queue from a linked list?
austere sparrow
Python's deque is a linked lists AFAIK
the benefit is that all inserts and pops are constant-time
old rover
I still don't understand how to say what the space complexity of an algorithm is
old rover
yeah I know that
a deque just allows you to enqueue on both sides
and dequeue
I keep thinking a deque and dequeue is the same thing
it's not
austere sparrow
yeah, deque is a noun, and dequeue is s verb 
austere sparrow
you mean, what are the benefits of a queue over a linked list?
old rover
no like
I've seen people use a node class and a linked list class
and then they turn that into a queue class
what is the point of that
vocal gorge
I still don't understand how to say what the space complexity of an algorithm is
just like getting time complexity is in general counting the number of operations and seeing how it scales, space complexity is the same for memory expenditure
vocal gorge
as far as Data Structures go, though, I don't think I can think of any that are not O(n) 😅
old rover
is there any videos I can watch on space complexity that explain it simply
vocal gorge
like, if it's less than O(n), you're somehow managing to not store all the elements. If it's more, then whatever "support structure" you're building around your elements is comparable, and growing faster than, the total size of your elements themselves. That'd also be very weird.
old rover
I'm watching this rn
it's in Javascript
but it shouldn't matter
bc it's language agnostic
or what not
vocal gorge
is there any videos I can watch on space complexity that explain it simply
no idea, I basically never watch programming videos
old rover
no idea, I basically never watch programming videos
🥴 built different
lean dome
as far as Data Structures go, though, I don't think I can think of any that are ...
Hm. Bloom filter.
vocal gorge
Hm. Bloom filter.
nice, I suppose I need to specify lossless DSes
lean dome
aren't all data structures objects
Not necessarily. There are non object oriented languages, and they can still have implementations of these data structures.
vocal gorge
wait... it's all objects?
I'd say whether something is an object or not, is, uhh
like, a different-level concept, one can say. As in, it's not a DSA question, but a more down-to-earth programming question, and can depend on the language (though I'm not sure if there are actual examples of languages where DSes are primitives or something)
oh, right, they can just be purely functional
lean dome
Or purely procedural
old rover
so people care more about the time complexity than space complexity
bc the costs to produce and run processors are much higher compared to RAM
agile sundial
what is it with all these books using getters and setters
they are bad
old rover
they are bad
yeah
great video but this doesn't really help me figure out the space complexity for enqueu/ dequeu
oh boy I can't spell
enquee
enqueue
dequeue
vocal gorge
so people care more about the time complexity than space complexity
not sure it's a good idea to generalize like that. For example, see https://blog.discord.com/why-discord-is-switching-from-go-to-rust-a190bbca2b1f - among other things, the article talks about switching from a HashMap to a BTreeMap, which technically has a slighly higher complexity, but is apparently smaller for their purposes, which allowed them to increase the size of the cache (how many most recent requests get cached for faster access) and get better average performance.
lean dome
In a non object oriented, procedural language, a linked list might look something like this:
struct Node {
struct Node* next;
void* data;
};
struct LinkedList {
struct Node* head;
struct Node* tail;
};
void linked_list_append(struct LinkedList* ll, struct Node* node) {
if (ll->tail) {
node->next = ll->tail;
ll->tail = node;
} else {
ll->head = ll->tail = node;
}
}
C? C++?
lean dome
that code would be valid in both. But C is the one that isn't object oriented.
lean dome
In a non object oriented, procedural language like C, you'd have pure data structures (the structs above) and global functions that manipulate them
old rover
the space complexity for methods performed on queues and stacks are O(N)
same with singly linked lists and doubly linked lists
vocal gorge
I think it should be O(1) (extra memory, that is)
lean dome
And in C's case, there's no namespacing, so the functions need to have the data structure's name in them.
old rover
vocal gorge
like, you aren't copying the entire queue (however transiently) every time you add an element
vocal gorge
that's for the structure, not the methods
vocal gorge
an example of an operation that does nothing, but uses O(n) extra memory:
def list_nullop(lst):
lst[:] = lst[:] # create a copy of the list and overwrite the contents with it. In other words, do nothing, but use O(n) time and memory for that
what is [:]
vocal gorge
note that it's O(n) extra memory because it:
- Creates a copy of the list (there's now 2 lists worth of memory used - hence O(n) extra compared to before the method was called)
- Overwrites the list with it
- The function ends and the copy gets dropped - memory usage is the same as before
At one point, the function is using O(n) extra memory, so that's the space complexity
vocal gorge
what is [:]
lst[:] is creating a slice of the entire list, same as lst.copy(). lst[:] = ... is slice assignment to the entire list - essentially overwriting the contents.
old rover
oh cool
mwahahaha
I like this KodingKevin guy
if you were searching for the head of a linked list
it would be O(1) right?
why would you even do that
nvm
this makes sense
you're not using any extra space when you insert things at the front or at the end so it should be O(1) space complexity
old rover
it seems like it's O(1) for all cases with space complexity
fiery cosmos
Hi there
vocal gorge
O(n) extra space would be, say, this method to insert an element in the middle of a list:
def my_insert(lst,i,val):
nexts = lst[i:] # O(n) extra memory to store the elements to get shifted to the right
lst[i] = val
lst[i:] = nexts
it's also possible to make an O(1) space implementation, though
old rover
oh ok
is it bad that I still don't understand how you're not taking extra space when you insert something before the head
is it bc linked lists have unlimited space?
vocal gorge
Well, where in the method for inserting before the head are you using extra memory?
lean dome
It's because there are no memory allocations at all. You're making new references to already allocated objects. You're not allocating any new objects.
Or, depending on the implementation, you may be allocating one new Node object - but even then, that's a constant, so it's still O(1)
old rover
what does it mean to allocate new objects
vocal gorge
create them, basically
(in Python all objects are heap-allocated, so every new object is an allocation)
old rover
but when you insert a new head you put in a new node and then switch the reference and then the new node becomes the head
vocal gorge
sure
old rover
didn't you "create" that head node?
vocal gorge
Yup
But it's one node always, not something scaling with the list's size, so it's O(1) extra memory 😛
vocal gorge
like, that it grows when the list's size grows
vocal gorge
precisely
old rover
ok now it makes sense
I'm thinking of making a github repo
of all the stuff I did so far
with ds/algos
old rover
I saw a pretty clean explanation for why binary search is O(log(n)
vocal gorge
because each step roughly halves the number of elements the target can be among
the airtight proof is pretty annoying, though
like, you need to handle all the rounding-down that is happening and prove that it really works out to log(n) anyway, always
CLRS has it
old rover
maybe I'll look at the proof later
it's O(log(N) bc it's array size v iterations
every time you double the array size the number of iterations go up by 1
apparently it's very "impressive" to memorize these and spit them out during an interview
why memorize when you can understand it
is it bad that I can't instantly write the code for binary search
lean dome
Can you clearly state the algorithm, one step at a time?
If you can identify the algorithm and the recursive base cases, that's 90% of the work of implementing it
vocal gorge
binary search is a bit tricky to get right
you need to be careful with off-by-one errors
old rover
def binarySearch(list, item):
low = 0
high = len(list) -1
while low <= high:
mid = (low + high)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None
here's the implementation I like
just write the thing without looking at it
vocal gorge
check this out
I was amazed: given ample time, only about ten percent of professional programmers were able to get this small program right. But they aren’t the only ones to find this task difficult: in the history in Section 6.2.1 of his Sorting and Searching, Knuth points out that while the first binary search was published in 1946, the first published binary search without bugs did not appear until 1962.
old rover
ok without looking at anything
binary search has a sorted list and a value
you compare the value to the middle of the list
if your value is bigger you go to the right side of the list
if your value is smaller you go to the left side of the list
on the right side of the list you again compare the value to the middle of the right side
and every time you compare you cut that right side in half until you find your number
talk is cheap tho
lean dome
and every time you compare you cut that right side in half until you find your n...
Or reach an empty subset of the list.
old rover
yes
wait
empty subset??
do you mean like nothing is there
so the value isn't in the sorted list?
still I'm not changing my opinion on "talk is cheap"
I could get the concept right but I could still struggle on the implementation
so idk if I should spend all my time and energy on binary search or just go to the next topic
if I can explain it I can learn it later
vocal gorge
your code is definitely broken
you forgot to actually divide by 2 in mid 🙂
besides that, it looks about right to me - you're preserving the invariant of the target being in list[low:high+1]
old rover
idk what the invariant of the target means
vocal gorge
an invariant is something that stays true as your algorithm works
invariants are a very common part of depeloping algorithms
old rover
oh
udacity never mentioned them so far
so you're saying that Grokking wrote it incorrectly?
old rover
where to divide by 2
vocal gorge
this is amazing lmao
old rover
no it's not
vocal gorge
where to divide by 2
mid = (low + high)
vocal gorge
> I was amazed: given ample time, only about ten percent of professional program...
this is such an awesome illustration of that quote above hahaha
old rover
oh boy
what have I done
so uh
is Grokking unreliable now
yeah if dude can't even get binary search right I don't think I should be looking at his book
vocal gorge
it's not the usual place to make mistakes in this alrorithm, tbh
usually you mess up the invariant and get either off by one element, or fail to find the element, or never terminate...
old rover
vocal gorge
it's rare to literally just forget a /2 in the most obvious part of the code
old rover
ik it's small but is that correct
vocal gorge
almost
old rover
oh boy
vocal gorge
it's correct pseudocode, but in Python you want //
since, well, / is float division in Python3
old rover
ok
that is a less grievous error than grokking
def binarySearch(list, item):
low = 0
high = len(list) -1
while low <= high:
mid = (low + high)//2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None
``` is it correct now?what's up with that len(list) - 1
what's the point
old rover
if the list was 5
then the high would be 4
I don't think low and high are good names for this
they're not actual values in the list
vocal gorge
uhh
you do realise that, like
lst[len(lst)-1] is the last element?
so these choices of low and high preserve an invariant of:
at every step, the target value (if it's present) is located among list[low], ...., list[high] (inclusive)
(or list[low:high+1] if you prefer slice notation)
jolly mortar
i mean you could call high and low the upper_bound and lower_bound if you like
I used begin and end at school 🥴
vocal gorge
considering the invariant here, first and last would fit nicely
since lst[last] is indeed the last candidate for being the target, at any point
old rover
Isn’t len(list) the length of the list and then - 1?
calm wind
Hi
old rover
@spring jasper is it - 1 bc we start counting from zero for indexes
spring jasper
Yes
old rover
oh ok
spring jasper
and i need HELP
calm wind
<#704250143020417084>
oof
agile heath
how do I find letters on a list of random letters by what coulum and row they are on
old rover
def binarySearch(list, item):
low = 0
high = len(list) -1
while low <= high:
mid = (low + high)//2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None
aList = [1,2,3,4]
print(binarySearch(aList, 4))
so all this does is return the index at where an element is in a sorted list
and if it's not there it'll return None
vocal gorge
yes, that's what search is
old rover
ok
old rover
should I spend my time regurgitating binary search
or should I move onto the other algorithms
come back when I do leetcode questions on them
the age-old question
grizzled schooner
wdym "regurgitating"
do you understand the algorithm?
if so, no need to spend much more time on it
grizzled schooner
what do you think is preventing you from being able to write it on your own?
old rover
I don't really know
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
is it mid - 1 bc it's sorted
least to greatest
sometimes I mix it up
grizzled schooner
yeah
if you think about it, guess > item so item != guess
so we can exclude mid from the range
old rover
yeah I think I basically got it
mid = (low + high)//2
what's the point of //2
so that if you have an even number and you subtract by 1 you don't get a .5?
you drop the .5?
grizzled schooner
yeah, indices have to be integers
old rover
this may be easier if I draw it out on paper
agile heath
thanks sry just saw this @old rover
also I have a variable which randomly selects a letter how would I add that into the binary search
abc = chr(random.randint(65,90))
old rover
The Feynman technique doesn’t work if you don’t have anyone to learn ds/algos w
grizzled schooner
aww 😔
vital rune
What is the time complexity of a function that looks like
for i in range(len(list))
for u in range(0,i+1)
would it be O(nlogn)?
chrome garden
yeah, indices have to be integers
indices have to be integers? hmmmmm what?
old rover
Yeah
onyx root
would it be O(nlogn)?
No, it is O(N**2)
old rover
Bc you’re iterating through the same list
with two for loops
it could be a for loop and an inner for loop and still not be O(N**2) it depends on what you’re iterating over with the for loops
vital rune
I have to write a function that looks for the greatest smaller predecessor for each int in a list with any data structure I want but idk how to do that within average time complexity of O(nlogn)
so [4,6,3,9,7,10] would return [None, 4, None, 6, 6, 9]
elements that precede the current element but is lesser than the current and highest only in the indices before it
does that make sense?
O(n)?
But you would iterate twice right?
for i in range(len(list))
for u in range(0,i+1)
It would look something like that?
that would be O(n**2) right?
onyx root
@vital rune were you told it's doable in nlogn?
agile sundial
you can insert something into a binary tree in log n, as well as find its predecessor in log n. if you do it n times, n log n
vital rune
I was given a TreeNode class with just the init and yeah I was told it was doable with average time complexity O(nlogn) and worst case O(n**2)
agile sundial
yep, worst case n^2, when it is strictly decreasing or increasing
actually no, only strictly increasing
wait..
ok yeah, it is either strictly increasing or strictly decreasing
vital rune
I'm not sure how I would implement that since I'm new to binary trees
how would the tree look for this example?
Would the first element be the origin/root?
agile sundial
yep
vital rune
haha its not too bad but im a bit confused on how the tree would help
4
/
/
3 6
/
7 10
Would the tree look like this?
for [4,6,3,9,7,10]
vital rune
what attributes would I need in a BST class?
if my TreeNode class has val, parent, left, and right
Or how would I access each node when I make the tree
Sorry I'm kinda lost haha
lean dome
You would preferably not have parent. Ideally a node knows only of its children
agile sundial
to get a predecessor you need to be able to grab the parent though
vital rune
but looking at this tree I would have to go from 10 to 9 to 6 to 4 to see which one is largest
cerulean river
Hey all, I am currently working on the problem below.
https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/
This is my solution:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
d = {}
d = dict.fromkeys(nums,0)
for i in nums:
d[i] += 1
# print(d)
for i, elem in enumerate(nums):
if 1 < d[elem]:
del nums[i]
d[elem] -= 1
print('d:', d)
print('nums:',nums)
return len(nums)
This is one of the test cases that are failing:
Input:
[1,1,1,1]
Output:
[1,1]
Expected:
[1]
Stdout:
d: {1: 3}
nums: [1, 1, 1]
d: {1: 2}
nums: [1, 1]
I am not sure why the loop doesn't delete one of the duplicate ones when nums: [1, 1] but does when nums: [1, 1, 1] or nums: [1, 1, 1, 1]
Also I have also thought of solving this with a set so that it can be done with one pass (hopefully, I will test this out when I fix this solution)
lean dome
I didn't look at the problem, that was just general tree advice. Avoiding reference cycles is better where possible.
vital rune
I also have to stay within space complexity O(n) for this problem. What would this mean in this case?
agile sundial
the amount of auxiliary memory you use scales linearly with the input size
vital rune
can anyone take a look at what I have so far? Idk if it makes sense lol
!paste
I might be overthinking it
grizzled schooner
indices have to be integers? hmmmmm what?
?
>>> l = [1, 2, 3]
>>> l[1.5]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: list indices must be integers, not float
halcyon plankBOT
heavy cloak
]
im just curious to why iuts outputting two things
when im only asking it to output one
grizzled schooner
that's returning a list, it's a listcomp
heavy cloak
listcomp?
lean dome
!e That list comprehension is equivalent to:
result = []
for i in 'Ie':
result.append('**'.replace('*', i))
print(result)
@lean dome :white_check_mark: Your eval job has completed with return code 0.
['II', 'ee']