never heard that terminology before
#algos-and-data-structs
old rover
spring jasper
The nauve solution is looping through the array in a nested fashion so its quadratic time
vocal gorge
ah yeah, I love TwoSum
spring jasper
But it could be done in linear time hashmaps i think
vocal gorge
I even got caught on it myself, it's Easy after all
but no, it does require the O(n) solution to pass the time limits, at least in Python
spring jasper
Yea leetcode atleast lets you get away with it
vocal gorge
Don't think it does in Python.
spring jasper
Huh thats weird, i definitely did not do the hashmap solution when i first did the problem
shell heath
How would i remove the multiples of 5 from this loop?
total = 0
startRange = 1
endRange = 101
for num in range(startRange, endRange):
total = total + num
print("The sum of the integers from 50 to 100 excluding multiples of 5 is 3000")
print(total)
trim fiber
How would i remove the multiples of 5 from this loop?
```
total = 0
startRange ...
if num % 5 == 0:
pass # num is divisible by 5
Is it suppose to be like this?
for num in range(startRange, endRange):
if num % 5 == 0:
pass
total = total + num
Nope, my message is a tip how to check whether num is divisible by 5. You can use != instead of == to check whether num is not divisible by 5.
old rover
so arrays are inmutable in other languages
but lists are dynamic arrays
so the size can be adjusted
ok
so
this course I was looking at asked why len() is O(1) in Python?
why is that?
bc a list is an object and an object has attributes and len is one of them?
agile sundial
hmm, arrays tend to be mutable in other languages
you may be thinking of static length
old rover
yeah the video mentioned that
agile sundial
you can modify them, so they are not immutable
old rover
nice
agile sundial
bc a list is an object and an object has attributes and len is one of them?
you're on to something here, what makes an attribute access O(1)?
old rover
and behind the scenes python lists are actually arrays
agile sundial
dynamic arrays, yeah
old rover
I looked up the question
and I found a SO post that says
len is O(1) bc in the RAM lists are stored as tables
and to know when the table stops the computer needs to know two things
the length and the start point
so basically bc the computer stores the value then looks it up
so there's a lot of code behind appending to a list in python
also with prepending
and popping
agile sundial
eh, that's a bit lower level than what i expected you to answer
the expected answer was that python handles attribute access with hash tables, and accessing a value is O(1)
agile dirge
Hey - why does python allow modifying a global variable as long as the variable is a dictionary?
global_var = "mark"
global_dict = {
"key0": {
"subvalues": {
"subkey0": 100,
"subkey1": 200,
"subkey2": 300,
},
},
"key1": {
"subvalues": {
"subkey0": 100,
"subkey1": 200,
"subkey2": 300,
},
},
"key2": {
"subvalues": {
"subkey0": 100,
"subkey1": 200,
"subkey2": 300,
},
},
}
def print_global_var():
print(global_var)
# Below errors "UnboundLocalError: local variable 'global_var' referenced before assignment"
#global_var = "chris"
def update_global_dict(global_key):
print(global_dict)
for k in global_key:
global_key[k]["subkey0"] -= 1
print(global_dict)
print_global_var()
update_global_dict(global_dict["key0"])
{'key0': {'subvalues': {'subkey0': 100, 'subkey1': 200, 'subkey2': 300}}, 'key1': {'subvalues': {'subkey0': 100, 'subkey1': 200, 'subkey2': 300}}, 'key2': {'subvalues': {'subkey0': 100, 'subkey1': 200, 'subkey2': 300}}}
{'key0': {'subvalues': {'subkey0': 99, 'subkey1': 200, 'subkey2': 300}}, 'key1': {'subvalues': {'subkey0': 100, 'subkey1': 200, 'subkey2': 300}}, 'key2': {'subvalues': {'subkey0': 100, 'subkey1': 200, 'subkey2': 300}}}
it doesn't have to be a dictionary. you can modify any global variable in a function. the issue is with reassigning one
vocal gorge
Python doesn't allow reassigning global variables without a global reclaration.
agile dirge
Python doesn't allow *reassigning* global variables without a `global` reclarati...
Ahhh
agile sundial
!e
L = []
def func():
L.append(10)
func()
print(L)
halcyon plankBOT
@agile sundial :white_check_mark: Your eval job has completed with return code 0.
[10]
You can't do =, and with immutables you can't do += (because for them a+=b is a = a + b, roughly speaking)
But you can read them, and access any methods on them, including those that modify them.
agile dirge
that makes sense. I suspected it was something like that but I couldn't quite articulate it. Thanks very much!
charred gale
anyone here can assist me in something?
old rover
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
so do you even need this method?
udacity doesn't even have it
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 get_position(self, position):
counter = 1
current = self.head
if position < 1:
return None
while current and counter <= position:
if counter == position:
return current
current = current.next
counter += 1
return None
def insert(self, new_element, position):
counter = 1
current = self.head
if position > 1:
while current and counter < position:
if counter == position - 1:
new_element.next = current.next
current.next = new_element
current = current.next
counter += 1
elif position == 1:
new_element.next = self.head
self.head = new_element
def delete(self, value):
current = self.head
previous = None
while current.value != value and current.next:
previous = current
current = current.next
if current.value == value:
if previous:
previous.next = current.next
else:
self.head = current.next
also if you just added self.prev = None
all of this code would work for a doubly linked list right?
I should probably use a pastebin
agile sundial
well you don't need it, but it would get rid of a lot of annoying code
having __iter__ lets you do
for node in self, instead of
current = self.head
while current.next is not None:
...
how do you make boxes like these
old rover
do stacks and queues have just as hard implementations?
vocal gorge
how do you make boxes like these
!code
halcyon plankBOT
charred gale
oh thank you
agile sundial
do stacks and queues have just as hard implementations?
are you familiar with the basic idea of a stack or queue?
old rover
are you familiar with the basic idea of a stack or queue?
no not yet
all I remember is a queue is like a line
agile sundial
then i wouldn't worry about the difficulty until you've actually looked at it
it'll save you a lot of worrying
old rover
should I just stop panicking about linked lists
and move onto to stacks and queues?
it's literally not getting me anywhere
agile sundial
if you can create a fully functioning linked list without referring to resources, then i think you're fine
if not, study the parts you can't make
old rover
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
is this function just for the representation?
bc init means initializing an object
like the Udacity code doesn't do it at all
"With the above modification, creating linked lists to use in the examples below will be much faster."
I'm going to assume that means that you really don't need it
it's just so that you can call llist = LinkedList(["1","2","3"]) and have it "turn into" a linked list for visual purposes
vocal gorge
uhm
no, __init__ is for creating an object, it's the class constructor
it's absolutely necessary for you to be able to call LinkedList at all
old rover
but you don't actually need it in your code
like what Udacity did
they won't be able to call LinkedList tho
which is fine I know what a linked list looks like visually
old rover
do you have to create them? or do you just need to know how to write the functions to append nodes, get the index of a node, insert nodes, and delete nodes?
I guess my point is on the interview are they gonna ask me to write a function to create a linked list?
vocal gorge
I mean, presumably, though you can write it using your append function
agile sundial
no, `__init__` is for creating an object, it's the class constructor
ehhhh, not really. it's inherited from object if you don't have it
and it's not really the constructor, that's __new__
you won't have any of the fields you want though
vocal gorge
ehhhh, not really. it's inherited from object if you don't have it
nevertheless:
- That's where fields are set and work with arguments of the constructor is done, so without an
__init__your class would be quite barren - I think most people call
__init__the constructor anyway.__new__is barely ever used after all
old rover
I’m not trying to be lazy
I just don’t want to spend time on stuff that won’t really be asked
fiery cosmos
I found this on the internet, but it isn't working correctly (doesn't find any matching index, it should)
guildMembersXP = [{'Member': 345},{'Member': 547},{'Member': 4821}]
memberid = 547
memberIndex = next([i for i, item in enumerate(guildMembersXP) if item["Member"] == memberid], None)
doesn't it have to be an iterator? not a list?
agile sundial
well, learn what the code does before just copying it, for all you know, it could have stolen all your passwords or something
fiery cosmos
ok fair
old rover
I actually don’t know what that does when I read it
vocal gorge
I found this on the internet, but it isn't working correctly (doesn't find any m...
TypeError: 'list' object is not an iterator
Use a generator expression instead of a listcomp.
agile sundial
hey I was right !
vocal gorge
memberIndex = next((i for i, item in enumerate(guildMembersXP) if item["Member"] == memberid), None)
fiery cosmos
i basically want to do this:
guildMembersXP = [{'Member': 345},{'Member': 547},{'Member': 4821}]
memberid = 547
memberIndex = []
counter = -1
for item in guildMembersXP:
counter +=1
if item['Member'] == memberid:
memberIndex.append(counter)
if memberIndex == []:
memberIndex = None
i tried that, still nothing
vocal gorge
i tried that, still nothing
WDYM by nothing?
fiery cosmos
WDYM by nothing?
it didn't raise any errors (that i'm seeing), so I can only assume it returned None
because didnt find member was printed
if not memberIndex:
print('didnt find member')```This would also happen if the index is 0, though.
You probably want if memberIndex is None:
fiery cosmos
You probably want `if memberIndex is None:`
ok so turns out i'm an idiot, this worked.
thank you
vocal gorge
let me try that
if not memberIndex: is equivalent to if not bool(memberIndex):
and bool usually:
0) None is mapped to False
- For numbers, everything except zero is True
- For collections, only empty collections are False.
fiery cosmos
interesting ok
old rover
is there like a function name for adding nodes before the head of a linked list?
I just called it prependNode
old rover
oh
ok
def appendLeft(self, data):
while self.head is not None:
node = Node(data)
self.head.prev = node
self.head = node
does that still do the same thing as
def addBefore(self, data):
node = Node(data)
node.next = self.head
self.head = node
I wrote that first function without looking at resources
no actually I screwed up
old rover
what about now
vocal gorge
This loop will once again never terminate.
old rover
I need an else
vocal gorge
Because self.head is always set to node, which is Node(data), so not None.
vocal gorge
I need an else
No.
You don't need a loop 😛
Why did you think you need a loop here? Appending to either end is supposed to be an O(1) operation.
old rover
I thought I would have to check if there was a head
vocal gorge
Yeah. So use an if?
old rover
def appendLeft(self, data):
if self.head is not None:
node = Node(data)
self.head.prev = node
self.head = node
else:
self.head = node
else:
self.head = node
NameError: node not defined 😛
(are you using an IDE? It would have warned you about that, probably).
old rover
node not defined bc it does not exist out of the scope of that if?
vocal gorge
node not defined bc it does not exist out of the scope of that if?
yeah, you're only defining it in one branch.
also, you're forgetting .next (unless your list is single-linked backwards and only has prev, I guess)
vocal gorge
Here, again, an IDE would complain about having no idea what .prev you're talking about.
old rover
def appendLeft(self,data):
node = Node(data)
node.next = self.head
self.head = node
TBH it's argued whether it's a good idea for beginners to use IDEs, but I always felt like it's good to see errors right as you make them and not at runtime.
old rover
well I didn't call the function
that would require the repr function
and the init function
vocal gorge
...why'd anything happen, then?
without a linter of some kind (included in nearly all IDEs, even VSCode, but not in replit) you won't get any errors until runtime
old rover
so the only way I know that my functions are correct is if I have the repr function, init function, and the repr function in the Node class?
"""The LinkedList code from before is provided below.
Add three functions to the LinkedList.
"get_position" returns the element at a certain position.
The "insert" function will add an element to a particular
spot in the list.
"delete" will delete the first element with that
particular value.
Then, use "Test Run" and "Submit" to run the test cases
at the bottom."""
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 get_position(self, position):
"""Get an element from a particular position.
Assume the first position is "1".
Return "None" if position is not in the list."""
return None
def insert(self, new_element, position):
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between
the 2nd and 3rd elements."""
pass
def delete(self, value):
"""Delete the first node with a given value."""
pass
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
# Test get_position
# Should print 3
print ll.head.next.next.value
# Should also print 3
print ll.get_position(3).value
# Test insert
ll.insert(e4,3)
# Should print 4 now
print ll.get_position(3).value
# Test delete
ll.delete(1)
# Should print 2 now
print ll.get_position(1).value
# Should print 4 now
print ll.get_position(2).value
# Should print 3 now
print ll.get_position(3).value
here's the quiz on Udacity
old rover
no
vocal gorge
then all of your prints are SyntaxErrors.
old rover
actually
vocal gorge
missing parantheses
old rover
Udacity is in Python 2
it's a minor thing
Grokking is in Python 2.7
def appendLeft(self,data):
if self.head is not None:
node = Node(data)
node.next = self.head
self.head = node
else:
self.head = node
that still doesn't work
bc again it's out of scope
so how do I fix this
or is there a better way to write the condition
vocal gorge
so how do I fix this
I mean, you could just make it in both cases 😛
but a better idea would be to define node before the if, even.
mint jewel
It's a built-in
agile sundial
oh
old rover
you could make node a global variable???
vocal gorge
so yeah, really consider using at least VSCode. Right now, you seem to be coding blindly without any way of checking your code.
vocal gorge
you could make node a global variable???
uhh
you do realise that it's only not defined because you only define it in one of the if-branches, right?
old rover
yes
vocal gorge
so the solution is as simple as moving it before the if:
vocal gorge
you can also note that this can be simplified
self.head = node happens in both cases
so really, you can simplify it further to:
def appendLeft(self,data):
node = Element(data)
if self.head is not None:
node.next = self.head
self.head = node
strictly speaking, you don't even need that check
old rover
mariosis said I did
vocal gorge
if you remove it, then if head is None, you'll merely be setting node.next (which was None) to None again
hard bane
self.head = Element(data, self.head)
which, well, is useless, but hardly a problem
vocal gorge
```py
self.head = Element(data, self.head)
```
nice, a one-liner.
vocal gorge
!code
halcyon plankBOT
hard bane
Of course the one liner assumes your initializer takes the second parameter
vocal gorge
@old rover Here's a repr for LinkedList, so you can actually test your code.
def __repr__(self):
s = []
cur = self.head
while cur is not None:
s.append(str(cur.value))
cur = cur.next
return f"LinkedList[{', '.join(s)}]"
gives a nice output like LinkedList[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
old rover
if you remove it, then if `head` is `None`, you'll merely be setting `node.next`...
so I don't really need to even check that the head exists or not
vocal gorge
not for that method, no
old rover
but you should be checking if there is a head for the appendRight method?
vocal gorge
yeah
old rover
why
vocal gorge
because in appendleft the new node always becomes the head
old rover
ok
vocal gorge
in appendright it always becomes the tail (but you don't store it), and only becomes the head too if there's no head
old rover
def appendRight(self,data):
node = Node(data)
if self.head is not None:
self.tail.next = node
self.tail = node
else:
self.head = node
like that?
vocal gorge
Oh, you are storing the tail after all.
You also need to set the tail even if the head is None.
old rover
def appendRight(self,data):
node = Node(data)
if self.head is not None:
self.tail.next = node
self.tail = node
else:
self.head = node
self.tail = node
@vocal gorge is that what you mean by setting the tail even if the head is none?
trim fiber
```python
def appendRight(self,data):
node = Node(data)
if self.head is ...
You update self.tail twice when self.head is not None
old rover
You update `self.tail` twice when `self.head` is not `None`
that's wrong?
vocal gorge
it's useless work
old rover
you're not supposed to create the reference before you set the tail equal to the node?
vocal gorge
it's like doing
x = 2
x = 2
- precisely like that, in fact.
agile sundial
eh
it's more like
def appendRight(self,data):
node = Node(data)
if self.head is not None:
self.tail.next = node
self.tail = node
else:
self.head = node
self.tail = node
ok, -OPedantic
old rover
so I can just write self.tail = node?
agile sundial
if you're doing it at the end anyway, no need to put it in the if block also
old rover
oh ok
agile sundial
it's like this
if condition:
x = 10
x = 10
yeah that seems redundant
agile sundial
like, sure, you set x = 10 in the if block, but you were gonna do it anyway, so
old rover
ok
that makes sense
Add three functions to the LinkedList.
"get_position" returns the element at a certain position.
do they mean index?
agile sundial
yeah, position and index are interchangeable usually
although position is a bit weird 🤔
old rover
did index not exist in python 2?
old rover
oh
idk
what's interesting is that they say this
Assume the first position is "1".
Return "None" if position is not in the list."""
isn't the first index in a list 0?
agile sundial
they probably mean "get the item in the nth position/index"
"or None if the position/index is out of bounds"
and calling the first index 1 is a bit :/
old rover
I'm kind of surprised that this is Google sponsored
Google is really ok with a course saying the first position is 1 not 0?
old rover
a few but not Python
whatever
I think it's better to write a program that returns the index of a given node
agile sundial
why not both
basically, write a function that does what
list.index does, and what
list[n] does
old rover
what does .index do
vocal gorge
Help on method_descriptor:
index(self, value, start=0, stop=9223372036854775807, /)
Return first index of value.Raises ValueError if the value is not present.
agile sundial
!e print(2**63 - 1)
halcyon plankBOT
@agile sundial :white_check_mark: Your eval job has completed with return code 0.
9223372036854775807
old rover
fruits = ['apple', 'banana', 'cherry']
x = fruits.index("cherry")
like that
that would return 2
agile sundial
yep, exactly
old rover
also are you supposed to use snake case with function names?
not camel case?
# Returns data at given index in linked list
def getNth(self, index):
current = self.head # Initialise temp
count = 0 # Index of current node
# Loop while end of linked list is not reached
while (current):
if (count == index):
return current.data
count += 1
current = current.next
# if we get to this line, the caller was asking
# for a non-existent element so we assert fail
assert(false)
return 0
this is geeks 4 geeks
I don't think you can do it without a counter
undone mauve
is it possible to invert a binary tree without recursion
agile sundial
also are you supposed to use snake case with function names?
yes
old rover
oh
agile sundial
```python
# Returns data at given index in linked list
def getNth(self, inde...
i suggest you remove this code from wherever you have it locally, and remove it from your memory also
it is horrendous
spring jasper
Why do you need getNth when you can just implement getitem
mint jewel
is it possible to invert a binary tree without recursion
Yes, the most naive way is just using a stack or a queue
spring jasper
Also with an iter impl you can use enumerate on self
mint jewel
IIRC there is also a smarter algo
old rover
what is getitem
old rover
i suggest you remove this code from wherever you have it locally, and remove it ...
ok how else do I do it
send help pls
undone mauve
i have seen the looping code to do it and i gotta say
this is one of those cases there the recursive version is just so much more intuitive
mint jewel
Ye, recursion is awesome
agile sundial
yep, trees in general are very recursivey
agile sundial
ok how else do I do it
use what you've learned so far and create it
spring jasper
Its the dunder for [] syntax
when you do list[5] what youre really doing is list.__getitem__(5)
You can implement it in your linkedlist to be able to do indexing like that
Its O(n)
old rover
ok
austere sparrow
is it possible to invert a binary tree without recursion
It's always possible to transform recursion in a loop, but not always reasonable
🙂
agile sundial
huh, i read somewhere that ackermann can't
old rover
only recursion I’ve seen so far is w the Fibonacci sequence
spring jasper
You havent done factorial yet?
undone mauve
It's always possible to transform recursion in a loop, but not always reasonable
no
incorrect
tail recursion and loops are equivalent
but recursion and loops are not equivalent
agile sundial
hm?
undone mauve
?mh
agile sundial
he meant using a stack as an auxiliary data structure instead of a call stack
or maybe a queue
undone mauve
show me a recursive function you can't turn into a loop
ackermann
austere sparrow
it will be a loop, just not a constant-memory one
spring jasper
Can we get a rundown on this ackermann thing
austere sparrow
ackermann cannot be implemented as a loop
undone mauve
hmm
agile sundial
hmm
austere sparrow
There exist implementations of programming languages that don't use the hardware's call stack for nested calls. Instead, they use a stack or a queue.
They're called "stackless"
So it's impossible to make an algorithm that's recursion-only.
Basically, you can stack up the function's state and recover the states by popping them from a stack.
agile sundial
that's basically what recursion does anyway
austere sparrow
Well, yes. Just at a hardware level.
I mean, it's still an array in memory
CPUs just support efficient manipulations of it
undone mauve
quantum computing is so fun
it has all these interesting restraints that are caused by laws of physics
e.g. all operations on a (set of) qubit(s) must be reversible, because of the no-hiding theorem
additionally, all operations on a (set of) qubit(s) must be their own inverse, because of unitarity
old rover
My physics teacher made me hate physics
Don’t really need it to know coding unless I’m doing physics simulations
undone mauve
indeed
brave oak
undone mauve
oh it was proven that there are recursive functions that are not primitive recursive
i just wasn't aware that given certain allowances, they can be done with loops
austere sparrow
anyone know how im able to comapre the objects in the list as integers?
You're trying to take range of a list
heavy cloak
ye so i can call the index
What im trying to do is
to check if the first object is smaller than the last
u can see the [1, 2]
and Im going to input more numbers in here
so i cant do
x[-1]
its gonna be like a alot of elements
fix error i dont understand
austere sparrow
ye so i can call the index
You can't call range on a list -- only on an integer. You probably meant range(len(x))
heavy cloak
oh
i did
rip
sorrry i got this culminating to do as well so my brain ia a bit fuzzy
austere sparrow
You should also restrict the length, because at the last step it will take i+1
heavy cloak
i see
I was testing the lambda
and i switched the > operator
to check if the first element was greater thatn the last
but it returns 2
which is bascially what i asked it to
if it was true
but its not true
why did it happen
copper wedge
old rover
Huh?
whole lark
Hi! What is the best case in finding a key in an array B[0:m-1] in a hash table?
severe kiln
When some websites build complex calculators, with sin cos etc. Do they build it using a specific library, or would it be through some kind of recursion? A lot of examples who if operators, but I'm unsure.
How would I go about building a more complex calculator with variable user input without specifying every potential elif
e.g.
out = num1 + num2
elif operator == "-":
out = num1 - num2
elif operator == "*":
out = num1 * num2
elif operator == "/":
out = num1 / num2```Pretty sure its from the JS Math module
old rover
def get_position(self, position):
counter = 1
current = self.head
if position < 1:
return None
while current and counter <= position:
if counter == position:
return current
current = current.next
counter += 1
return None
how do I change this to get the index of a node?
write a function to get the index of a node and then use that function in another function to get the value of the node
I am confused by this function actually
actually you can change this by just changing the counter to 0
grizzled schooner
how do I change this to get the index of a node?
you would have to modify the while loop condition to reflect what you're searching for
old rover
I think I am close to figuring it out
agile sundial
didn't you define a __iter__?
unkempt trail
so i'm saving data with json for a server
which would be better to manage?
"users" : [
{
"nickname" : "Bob"
"friendcode": 1234567890
"public_rsa_key": <key goes here>
}
{
"nickname" : "Jim"
"friendcode": 0987654321
"public_rsa_key": <key goes here>
}
]
---OR---
"nicknames" : [
"Bob",
"Jim"
]
"friendcodes" : [
"1234567890",
"0987654321"
]
"public_rsa_keys" : [
<Bob's key>,
<Jim's key>
]
or does it not matter?
old rover
didn't you define a `__iter__`?
yeah
agile sundial
can't you use a for loop then?
old rover
use a for loop for what
are you saying I should use the iter method for finding the node given the index?
lean dome
are you saying I should use the iter method for finding the node given the index...
You can do it that way, for sure.
def get_nth_elem(self, n):
for idx, elem in enumerate(self):
if idx == n:
return elem
raise IndexError("no such item")
what's enumerate
lean dome
A function that turns an iterable over elements into an iterable over index/element pairs.
It's the same as ```py
def get_nth_elem(self, n):
idx = -1
for elem in self:
idx += 1
if idx == n:
return elem
raise IndexError("no such item")
!e ```py
print(list("abc"))
print(list(enumerate ("abc")))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | ['a', 'b', 'c']
002 | [(0, 'a'), (1, 'b'), (2, 'c')]
def idk():
aList = [1,2,3]
for val in enumerate(aList):
print(val)
idk()
so it prints the index
and then the element
cool
lean dome
Yeah. It gives them both back as a 2-tuple
old rover
so how is it useful?
in that first function you wrote
is n in that parameter supposed to be the index?
lean dome
Yep. Both functions do the same thing: return the data held by the nth node in the list, and raise an exception if the list has no nth node.
old rover
so n is the index
lean dome
Yep.
old rover
and elem is the data in the node
lean dome
Yep.
old rover
and then you're returning the data in the node
lean dome
n is the target index, idx is some node's actual index, elem is that node's data.
old rover
what's that IndexError for?
lean dome
To tell the user that you failed to find any such node.
Like if they ask for the value of the 10th node in a 5 node list.
lean dome
Walking to the nth node is just walking to all nodes and stopping part way through, too. You can start with your __iter__ code, and modify it to a) not yield every element, b) keep a counter and return when that counter reaches you target item, and c) report an error when the target isn't found
modern island
Not really an algo question but I'm looking for opinions/review...
What do you prefer 1️⃣ or 2️⃣
Or something different entirely?
modern island
Hmm, don't make it a list? as in for the second one?
Would i be better off putting this in a different channel too?
agile sundial
yeah sorry, i meant for the second one
yeah, a normal help channel would be better #❓｜how-to-get-help
fiery cosmos
How can I have a voice channel created in a specific category?
old rover
How can I have a voice channel created in a specific category?
wrong channel
fiery cosmos
oh sry everyone
bronze sail
is there algo for removing shorter lines ?
lean dome
are there indexes in dictionaries?
dictionaries are implemented using a data structure called a hash table. You'll get to it.
old rover
@lean dome so behind the scenes dictionaries are just hash tables with lipstick?
agile sundial
pretty much, yeah
although the lipstick could be considered part of the hash table
lean dome
A dict is "just" a hash table in the same way as a list is "just" a dynamic array.
There's Python specific stuff in there - like when resizing happens - but the underlying data structure it's based on is a common, well known one.
old rover
So now I need a class for a dictionary to implement it?
can’t you just implement it normally?
lean dome
I don't understand the question
lean dome
You need a class for any data structure you want to build
lean dome
dict is a class
old rover
Well I know dictionaries how hard could it be
lean dome
Well, harder than linked lists, heh
In fact, a hash table can use linked lists, as part of its implementation
sudden sinew
Could anybody point me towards an algorithm you could use to find the minimum number of values needed to have a value in all of a set of arrays, so if you had
a = [1, 2]
b = [1, 3]
c = [4, 5]
The answer would be two, and the values for that could be (1, 5) or (1, 4), as for both of those sets all the lists share at least one value with it. (The lists could be any length though)
Seems like this is what I was looking for https://cs.stackexchange.com/questions/3276/given-a-set-of-sets-find-the-smallest-sets-containing-at-least-one-element-fr
old rover
def get_nth_elem(self, n):
for idx, elem in enumerate(self):
if idx == n:
return elem
raise IndexError("no such item")
can anyone explain why this is constant time space complexity?
I still don’t get space complexity
the amount of space your code takes place in a data structure?
So what’s an example of O(N) space complexity?
just curious
mint jewel
removing duplicates from a list.
old rover
How come?
agile sundial
are you familiar with the algorithm to remove duplicates from a list?
old rover
No
vocal gorge
```python
def get_nth_elem(self, n):
for idx, elem in enumerate(self):
...
Wait, how come it's constant time complexity? It's O(len(self)).
(though space complexity is indeed constant)
old rover
I think I meant constant space complexity
Not constant time space complexity
it’s O(n) for searching for a node in a linked list
vocal gorge
yeah.
Here's a very simple modification of your algorithm above that makes it O(n) space too, for example:
def get_nth_elem(self, n):
vals = list(self)
try:
return vals[n]
except IndexError:
raise IndexError("no such item")
here we're transforming the linkedList into a normal list for no reason before picking the right element, and as a result use O(n) extra memory.
weak panther
can anyone help me solve this issue?
Every time I run out of urls to scan, it have a dead period where my scan needs to restart and I fall behind on the download time
all of the prints in the second block are 10 seconds behind because I'm having to refresh my download.
I have no idea how to approach this.
Even the stuff in the first block is behind by 9 seconds.
kindred coyote
that many comparisons slows down your code severely
also using a while 1 loop slows it down as well
tremendously
weak panther
idk what else to do
it's driving me mad
I'm trying to scan 83 apis and pull data from the current hour without getting any old data. The only way I can think of handling this is by using if realmid not in realm_dict or (datetime.utcnow() - realm_dict[realmid][1]).seconds >= 3600: and saving the old data into a pickle
old rover
Perhaps
an algorithm is just a function
You can make functions do absolutely anything
lucid token
ok
keen hearth
Can we make an algo for detect if a member have a discord selfbot.
Probably more suitable for #data-science-and-ml
cerulean shard
Im working on a project for a python class involving graphs (BFS). can anyone help me with it?
halcyon plankBOT
old rover
We can’t give code
spring jasper
Just ask the question so people can give you pointers
cerulean shard
got it, sorry about that
supple needle
It'd be nice if there was a daily (or so) codin' game challenge on this channel. We do that at work an they're fun. (https://www.codingame.com/start)
old rover
@supple needle this belongs in #community-meta
supple needle
Maybe, but I mean on this particular channel #algos-and-data-structs because the activities are aligned with the topic
spring jasper
Whats wrong with codingame itself
supple needle
Wait, do you already do codingames here?
cerulean shard
You didnt ask your question
let me try something really quick, ill let yall know if i get stuck
spring jasper
Wait, do you already do codingames here?
No, i meant you could do it yourself
supple needle
Sure, but what I have in mind is some kind of agreed upon periodicity and time of day, we share the link here and participate
spring jasper
I doubt there'd be enough demand but you can ask in meta
onyx root
Sure, but what I have in mind is some kind of agreed upon periodicity and time o...
that sounds like a new channel
fiery cosmos
Are there any resources for learning how to solve differential equations in Python?
supple needle
@fiery cosmos numerically?
twilit spear
does anyone know proof by induction for time complexity of algorithmns
Use Proof by Induction to prove: Merge sort worst case time complexity is O (n log n)
keen hearth
It'd be nice if there was a daily (or so) codin' game challenge on this channel....
Oh yeah, I enjoy that site's puzzles!
They have a discord server btw.
keen hearth
Sure, but what I have in mind is some kind of agreed upon periodicity and time o...
The hard part will be finding someone willing to do this regularly.
dapper sapphire
Am I on the right track with reversing the linked list in terms of comment/annotation:
def reverseList(self):
previous = None
current = self.head
while(current != None):
temp_next = current.next # 1. Store next node's address
current.next = previous # 2. Reversal. Change next node's address to point to previous node's address
previous = current # 3. Increment previous node by pointing it to current
current = temp_next # 4. Increment current by pointing it to temp_next(from step 1)
self.head = previous
print("self.head:", self.head.val)
@dapper sapphire does it work?
dapper sapphire
<@!673649624250056721> does it work?
Yes it works and reverses the list.
onyx root
sounds good!
dapper sapphire
But I wanted to know if my thought process is on the right track when I commented each line in the while loop.
twilit spear
thanks for "helping" btw
fiery cosmos
@supple needle Yes, numerically and with various solvers.
onyx root
@dapper sapphire i wouldn't use the verb "increment" with "node"
dapper sapphire
<@!673649624250056721> i wouldn't use the verb "increment" with "node"
Actually, you are right. I shouldnt say increment because we are dealing with memory address.
3. Previous node points to the current node, or previous node becomes current node.
4. current node points to the next node, or current node becomes next node.
dapper sapphire
very common leetcode question
It is from leetcode, not much originality here.
old rover
It is from leetcode, not much originality here.
oh I thought you were just doing it for learning sake
most of the code you do with linked list is just reassigning things
dapper sapphire
I am doing it for learning and leetcode both.
dapper sapphire
reassigning pointers?
old rover
yes
sometimes idk if it should be node.next = self.head
or self.head = node.next
like I get confused while I'm coding
dapper sapphire
How's you foundation?
dapper sapphire
What level linked list are you doing on leetcode?
old rover
I haven't done questions on linked lists in leetcode yet
I want to do all the data structures/algos before I just start endlessly grinding leetcode
agile sundial
they're a good way to practice dsa
dapper sapphire
they're a good way to practice dsa
What is?
old rover
I'll finish the udacity course first and then do leetcode
onyx root
I want to do all the data structures/algos before I just start endlessly grindin...
isn't your goal to use sklearn?
old rover
yes
but I should at least know DS/algos and the math in data science/ML before I just do sklearn
onyx root
i disagree
old rover
well I tried doing sklearn for a while and I didn't really know what I was doing
onyx root
did you find linked lists in sklearn?
old rover
I may need linked lists to pass interviews for internships
When I applied to IBM for a data science internship they asked a linked list question
onyx root
if you interview for a data science internship, and they ask about linked lists, it's a bad place.
old rover
so IBM is bad?
onyx root
did you interview there?
old rover
it was the first question they gave me before a phone screen
but I didn't actually make it to the phone screen
bc I didn't know what the hell a linked list was
dapper sapphire
So it was a online coding assessment?
Did they ask you what a linked list is or how do you implement one?
old rover
they asked me to reverse a linked list
dapper sapphire
hahahaha
old rover
no seriously
it was just a hackerrank question and it was like here's a linked list reverse it
I don't think someone who doesn't know linked lists just knows how to reverse them
dapper sapphire
Yeah I mean if someone doesnt know what a linked list is they cant reverse one.
dapper sapphire
I would have imagined ml and data science positions to be more about sql and python/pandas.
old rover
idk
I guess IBM felt particularly spicy that day
sklearn has multiple algorithms like linear regression
what do you do if they go like oh yeah can you explain the math behind linear regression?
bc they asked me that in my CUNA mutual group interview
agile sundial
how do you get so many interviews bruh
old rover
god knows
spring jasper
Honestly befuddled, i dont even get called back
old rover
the textron internship just fell into my lap too
they said I attended a conference for a women in tech career fair???
anyways this doesn't have to do w algos/DS so I'll stop
dapper sapphire
I imagine if someone goes to a university, they would be more likely to get an interview for an internship.
spring jasper
I've been to uni, im getting turned down from internship positions
dapper sapphire
You have been? But you are not currently attending one?
spring jasper
No, i graduated in september
dapper sapphire
Yeah, from the research that I have done, companies take a chance on students who are still going to school.
Once you graduate, companies are expecting the candidate to already have some experience, one or two internships and so on.
old rover
oof
old rover
def insert(self, new_element, position):
counter = 1
current = self.head
if position > 1:
while current and counter < position:
if counter == position - 1:
new_element.next = current.next
current.next = new_element
current = current.next
counter += 1
elif position == 1:
new_element.next = self.head
self.head = new_element
is there an easier way to write this
I'm confused anyways
position "1" would be after the head
agile sundial
haven't you written an __iter__ method
old rover
yes
agile sundial
why not use it
old rover
so I should call the iter method in the insert method?
agile sundial
no, __iter__ is called for you when you use a for loop
L = [1, 6, 3]
for x in L:
...
the for loop calls the __iter__ method of lists automatically, for you
old rover
by new_element do they mean new_node?
agile sundial
who's they
old rover
Udacity
agile sundial
it seems like it
pure terrace
Hello how can I break a for loop that is on top of another for loop:
for fieldName, errorMessages in form.errors.items(): # I want to break this loop after first iteraction
print("Iteraction")
for err in errorMessages:
flash(err, category='error')
break
...put a break there?
Or if it's after the first interaction always, don't use a loop at all?
pure terrace
Or if it's after the first interaction always, don't use a loop at all?
Yeah I only need the first item coming from form.errors.items()
vocal gorge
note that if it's empty, this will raise StopIteration
jolly mortar
apparently doesn't work
sad
>>> d = {1:2, 3:4}
>>> next(d.items())
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'dict_items' object is not an iterator
Yeah, you need next(iter(d.items()))
pure terrace
Hello how can I break a for loop that is on top of another for loop:
```python
f...
I added a break statement
spring jasper
```python
def insert(self, new_element, position):
counter = 1
c...
Why are you inserting at the head on position 1
Pyrhon is 0-indexed
old rover
Why are you inserting at the head on position 1
Udacity 😦
spring jasper
What, why are you consulting udacity resources now
I thought you stopped resource hopping
old rover
I thought I would do better with a course
spring jasper
Youre not paying for this, right?
old rover
no
it's completely free
honestly I don't know why Google sponsors a course saying that the first index is 1
spring jasper
Why are you following it then
old rover
hey it might just be really bad for linked lists
spring jasper
If its bad for linked lists its probably bad for everything else
Linked lists are the most basic data structure
old rover
def delete_node(self, node):
node.data = node.next.data #make the data of a given node equal to the data of the node after it
node.next = node.next.next #gets rid of the next node
that first line makes sense
actually the second line makes sense too
or does it
the first line makes the data of the next node equal to the data of the given node
vocal gorge
huh, that's a smart way of doing that, I actually didn't think to use that approach
(I actually delete the node, which needs me to get the previous node and link it instead to the next one after the deleted one, skipping the deleted node. This approach instead skips the next node and copies its data to the deleted note, overwriting the data that was there)
grizzled schooner
stacks will probably be easier for you than linked lists
old rover
yay
linked lists are really not that hard
it is mostly just reassignment
that is probably how append works behind the scenes
or under the hood
I think my old college is teaching algos/DS in C
they probably have it even harder than I do
spring jasper
C is not that hard, and it makes perfectly clear how references to other nodes work
Pointer stuff is what people usually struggle with
Been there done that
grizzled schooner
isn't C not object oriented or something
old rover
scenes when I say pointer instead of reference during my interview and the interviewer corrects me
😐
old rover
I thought I got corrected here that pointers don’t exist in python they’re references
vocal gorge
isn't C not object oriented or something
Depends, but considering C doesn't really have classes, only structs, I doubt it counts as such
plush sage
hello ppl, is here someone who would like to explain me some thing about algorithms, coding is my hobby and i dont have any cs degree, i understand some surface of it, but things like time and space complexity, mathematical insights and reasons i dont really understand 😅
links are also welcome <3
plush sage
well i use both :)
onyx root
@plush sage time complexity: https://nedbatchelder.com/text/bigo.html
plush sage
<@!805434832099737600> time complexity: https://nedbatchelder.com/text/bigo.html
this is EXACTLY what i was looking for, ive read intro and i like it... its cool that its yours, ill be sure to check whole blog! <3
old rover
@onyx root dude this is amazing
really well done
I really admire people who can explain things concisely
That’s like a really big flex
amber egret
pulsar imp
damn
amber egret
guess im the CEO now
vocal gorge
Oh wow, I wasn't aware of my involvement either!
amber egret
SHESSSHSHH
vocal gorge
(also, this is #algos-and-data-structs, not offtopic, as I just noticed.)
old rover
@amber egret #ot0-psvm’s-eternal-disapproval
onyx root
<@424559318617161740> dude this is amazing
thanks!
dapper sapphire
What are some concepts that are considered hard in data structures?
old rover
graph traversals are interesting
some of the things you do with data structures are considered hard to some
like inverting a binary tree
or reversing a linked list (which you already did)
dapper sapphire
Yeah for reversing a linked list, the naive approach is pretty simple and straight forward to understand.
But two pointer approach definitely would be harder for some people.
old rover
I'm gonna finish the Udacity course before I do leetcode
agile sundial
inverting a binary tree is trivial compared to the other convoluted things you can do with trees
spring jasper
Yea youtube ads make tree inversions out to be hard but its like 5 lines
keen hearth
I think the whole "inverting a binary tree" thing was meant as a silly example of something they didn't consider to be relevant to their job 😄
The tweet I'm referring to: https://twitter.com/mxcl/status/608682016205344768
Twitter
keen hearth
Yea youtube ads make tree inversions out to be hard but its like 5 lines
But I know the ads you're referring to 😄
keen hearth
I'm gonna finish the Udacity course before I do leetcode
Hey, you're working on that algorithms course I recommended?
old rover
Hey, you're working on that algorithms course I recommended?
yes indeed
keen hearth
yes indeed
Nice. The instructor is great right? 😄
old rover
Nice. The instructor is great right? 😄
yeah she's pretty good
def get_position(self, position):
"""Get an element from a particular position.
Assume the first position is "1".
Return "None" if position is not in the list."""
return None
def insert(self, new_element, position):
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between
the 2nd and 3rd elements."""
pass
```I don't really agree w this tho @keen hearth
the first node in a linked is the head and that is 0 not 1
just a minor thing tho
dapper sapphire
What Udacity course is this?
keen hearth
yeah she's pretty good
"she"? I think you're doing a different course. I was talking about the one taught my Michael Littman. Most of their courses are pretty good though.
keen hearth
I don't really agree w this tho <@!476543547210858506>
Let me take a look 🤔
old rover
"she"? I think you're doing a different course. I was talking about the one taug...
oh I just found his course
I'm doing this one rn
keen hearth
the first node in a linked is the head and that is 0 not 1
It can be 0 or 1, depending on convention. Most programming languages index from zero. I think mathematicians sometimes prefer indexing from one, for some reason.
Fortran and Matlab index from one, I think.
Python goes by the convention of indexing from zero and using half-open intervals.
keen hearth
https://classroom.udacity.com/courses/ud513
Oh that one looks like a good starting point.
keen hearth
~~but we in Python~~
Yeah 😄 It doesn't hurt to learn to be a bit flexible regarding these things. You might have to work on projects that use conventions that you disagree with in the future. Often the actual choice of convention isn't what matters, but that it is consistent within the project itself. If you are working on an existing python code-base that uses tabs for indentation, it would be wise to stick to that convention, for example.
keen hearth
yeah but there's no data structures there
To be honest, the line between an algorithm and a data-structure is a little blurry. For example, a heap is a data-structure, and heap-sort is an algorithm, but it's hard to learn about one without learning about the other.
keen hearth
I'll finish this course first
Yeah, please do. I'm not trying to distract you, sorry! 😄
red prawn
everyone here seems rather experienced, I have a question about python capabilities
if I had historical data on a price or level of a number
could I build an algo that could give me a rough estimate of the direction the price would go
keen hearth
everyone here seems rather experienced, I have a question about python capabilit...
Hey 🙂 I believe that's called "time-series" forecasting. (The question is probably a better fit for the #data-science-and-ml channel, btw). If you are referring to predicting the price of a stock specifically, this is a difficult question. There is some information in the price history that could tell you something about its future price, but this information can only really be used once, and it will be by other people who put a great deal of effort into doing it faster than you could at home. This is related to something called the "efficient-market hypothesis" https://en.wikipedia.org/wiki/Efficient-market_hypothesis
red prawn
interesting, I just had a great discussion in the data science channel on this. the stock thing would actually just be a baseline to learn about this, the main project is to roughly predict insulin levels needed and sugar levels for a diabetic in my family
agile sundial
It can be `0` or `1`, depending on convention. Most programming languages index ...
but dijkstra said 🥺 https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
keen hearth
interesting, I just had a great discussion in the data science channel on this. ...
That seems like something amenable to time-series forecasting 👍
eager hamlet
https://codeforces.com/contest/816/problem/E
so, this problem is tree dp
but say i solved the problem on all subtrees of a node, and say even better that i know which items to buy to maximize capacity
how would i merge the subtrees? any help would be appreciated. (ping 2 reply thx)
meager solstice
Hello guys, I'm using openCV and numpy to first read images and then splitting them into color channels(LAB), I need to stack L channel of each image (size 244x244) in such a way that the output is a numpy array with size for example(numer_of_images, 244, 244). I've tried dstack but got wrong size at the end. Any ideas?
flat sorrel
Hello guys, I'm using openCV and numpy to first read images and then splitting t...
!d numpy.stack
halcyon plankBOT
flat sorrel
The default of axis=0 should get you what you want
numpy.vstack should similarly work
limber junco
Hello, I am feeling it very difficult to come up with solutions for problems on competitive platforms like leetcode, anyone has suggestions on how can I improve?
onyx root
Hello, I am feeling it very difficult to come up with solutions for problems on ...
Maybe those types of exercises aren't the ones to be working on.
glossy breach
Solve easier problems or probably learn more algorithms
old rover
read some more books about data structures/algos to get a more holistic understanding of everything
Grokking is a good book if you already know the fundamentals of ds/algos
it skimps on implementation at times but it's assumed that you already know it
you know it really says a lot about the importance of linked lists when websites just skip over it
glossy breach
I haven't met much problems on linked lists on my competitive programming path
old rover
why'd I spend so much time on it smh
glossy breach
It's still a good thing to learn still
old rover
it's harder than stacks and queues
worldly pendant
why'd I spend so much time on it smh
You will use the principles learned in LLs when you begin tackling graphs and even when you are building hash tables. Your time was well spent.
old rover
You will use the principles learned in LLs when you begin tackling graphs and ev...
thanks dude
rustic valley
Hi, can you help me? I saw it in the algorithm design book .The operations given below are n-dimensional
on an array, not dependent on the size of the array
explain how you can do it at a time:
a. Series I. delete element (1 ≤ i ≤ n)
process.
b. I of an ordered sequence. delete the element.
lunar otter
Hi! does this pseudocode have O(n^3) run-time efficiency?
agile sundial
so it would seem
lunar otter
thanks
grizzled schooner
pretty sure unordered means not sorted
vocal gorge
it might also mean a set, but yeah, I'd assume ^
old rover
"In order to implement an unordered list, we will construct what is commonly known as a linked list. Recall that we need to be sure that we can maintain the relative positioning of the items. However, there is no requirement that we maintain that positioning in contiguous memory. For example, consider the collection of items shown in Figure 1. It appears that these values have been placed randomly. If we can maintain some explicit information in each item, namely the location of the next item (see Figure 2), then the relative position of each item can be expressed by simply following the link from one item to the next."
anyways back to Udacity I go
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
you know
I've never seen it done like that
vocal gorge
Are there any quick algorithms for calculating the Pareto frontier?
More precisely, suppose I have N n-dimensional vectors. I want to throw away all vectors that are strictly worse than another vector. That is, if there's a pair of vectors a,b such that all(a[i] <= b[i] for i in range(n)) (so there's no indexes for which a is better than b) and any(a[i] < b[i] for i in range(n)) (there's at least one index for which a is worse than b), then a needs to be thrown away.
This is obviously solvable in O(n^2), but I'm wondering if there's a faster solution.
agile sundial
i've never heard a linked list be called an "unordered list"
grizzled schooner
hm, maybe they mean that linked lists aren’t indexed
agile sundial
looks ok, but why are you looking at more linked list resources
old rover
torture
anyways
stacks here we go
so taking the first object off a stack is O(1) most likely
but taking the one all the way at bottom is O(N)?
grizzled schooner
you aren’t really meant to take the item at the bottom of a stack
old rover
what do they mean by a stack is "abstract"
abstraction in code means a simplification
I think
oh boy I can't escape linked lists
you can use linked lists to implement stacks
agile sundial
lul
old rover
maybe it's good that I spent an entire week and a half doing linked lists
agile sundial
you can also implement a stack with an array or list
vocal gorge
what do they mean by a stack is "abstract"
You can describe a stack as "a DS with the following operations (maybe even "which must have at most the following complexities")". You'll find, then, that there's several ways to actually implement a stack matching that description - for example, one can use an array instead of a linked list.
old rover
is there any benefit to using a linked list to implement a stack vs using an array
agile sundial
linked list doesn't have a max length
vocal gorge
So basically, Stack is an interface - a description of what a structure must do to qualify as a Stack.
agile sundial
trait lol
old rover
LIFO v FILO
FILO is what you first put in is on the bottom
and LIFO is what you last put is on the top
agile sundial
lifo and filo are equivalent @old rover
vocal gorge
is there any benefit to using a linked list to implement a stack vs using an arr...
arrays are more compact (linked lists need a pointer per item) and give you O(1) random access (not that you need it for a Stack), but you'll sometimes need to resize them (though that's amortized O(1), so same asymptotic complexity).
old rover
is it bad that I still don't get what amortized means
vocal gorge
though I suppose the first point isn't really true in most languages
old rover
in the context of big O
vocal gorge
is it bad that I still don't get what amortized means
you might not have encountered it before
vocal gorge
Basically, you can prove (pretty easily), that though resizing an array is O(n), after such a resizing a new resizing will never happen in the next n operations (the number depends on whether you double the size or triple it or whatever)
old rover
doesn't amortized mean like paying something off
agile sundial
the important part is paying it off over time
old rover
so what does that have to do with big O
vocal gorge
so on average, inserting an element is O(1), because the bigger the vector is, the more expensive resizings are, but the rarer they happen.
agile sundial
yes, any particular append may take O(N), but on average, appending is O(1)
old rover
oh
"Consider washing a lot of dishes.
You can wash them by hand (standard algorithm). Each dish takes some time to wash.
Or you can use a dishwasher (amortised algorithm). Putting each dish in is very fast, but once it fills up you need to wait an hour for it to finish.
Amortised analysis tells you the average time to wash one dish, accounting for the fact that sometimes it's fast and sometimes slow."
I like this explanation
vocal gorge
basically, one could say that a stack is
public interface StackInterface<E> {
public void push (E item);
public E pop();
public E peek();
}
lol
except one usually also includes requirements that all three must be (amortized, at least) O(1)
and how you achieve all this is nobody's concern. Hence, "abstract"
agile sundial
hooray for encapsulation
old rover
ofc their implementation is using a linked list
vocal gorge
If by "their" you mean Java's, no:
https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
but yeah, stacks via linked lists are a classic DSA teaching point
old rover
"""Add a couple methods to our LinkedList class,
and use that to implement a Stack.
You have 4 functions below to fill in:
insert_first, delete_first, push, and pop.
Think about this while you're implementing:
why is it easier to add an "insert_first"
function than just use "append"?"""
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
new_element = self.head
def delete_first(self):
"Delete the first (head) element in the LinkedList as return it"
pass
class Stack(object):
def __init__(self,top=None):
self.ll = LinkedList(top)
def push(self, new_element):
"Push (add) a new element onto the top of the stack"
pass
def pop(self):
"Pop (remove) the first element off the top of the stack and return it"
pass
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
# Start setting up a Stack
stack = Stack(e1)
# Test stack functionality
stack.push(e2)
stack.push(e3)
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value
I'm talking about this implementation
vocal gorge
yeah
agile sundial
what is that python 2?
old rover
yes it's python 2
"Delete the first (head) element in the LinkedList as return it"
what the hell does that even mean
as return it??
vocal gorge
and
vocal gorge
gotta love courses which have typos in addition to Py2
vocal gorge
return the linked list?
the element
vocal gorge
yes
old rover
smh
def delete_node(self, node):
node.data = node.next.data #make the data of a given node equal to the data of the node after it
node.next = node.next.next #gets rid of the next node
won't this delete the head if you gave it a linked list and the head node
vocal gorge
depends on what you mean by "delete the head"
vocal gorge
the data will be gone (as it should, that's why it's called delete_node lol), the node itself wouldn't
I'm more worried about the fact that, if your list has no sentinels, node.next.next can be None.next and so an AttributeError
where are null-aware operators when you need them 😔
vocal gorge
didn't you decide to stop surfing earlier and code it yourself?
old rover
that was after I got this method
but am I right?
def delete_first(self):
deleted = self.head #make your head the deleted node
if self.head:
self.head = self.head.next
deleted.next = None
return deleted
what does if self.head even do
if head?
if head what?
vocal gorge
if self.head: means if bool(self.head):
now, how objects are cast to bool depends on the __bool__ dunder
but if it's not present, it defaults to True always
old rover
so it just checks if it's there
vocal gorge
so it's a hard-to-read way of checking if self.head is not None:
old rover
and if it's there it's. true
ok
self.head = self.head.next
what's the point of that line
the reference points to self.head?
it's creating a reference that points to itself?
vocal gorge
No?
When you remove the list's head, the next node becomes the new head (kinda by definition)
vocal gorge
...making the next node the new head?
old rover
oh
I have been staring at code for too long
sorry dude
all it does is make the next node the head
delicate geode
Is it okay to discuss leetcode problems here? I'm new and I got a working solution, but I am having trouble with optimizing my solution.
old rover
yeah it's fine
vocal gorge
Sure, they are algorithms problems and they don't even violate rule5.
delicate geode
Okay, so the problem is this:```
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.```
So what I did was I kept track of both arrays and used indexes to do comparison logic to appropriately merge, and the code looks like this: https://pastebin.com/pVKYN8C2
I can explain variables as needed.
vocal gorge
https://leetcode.com/problems/merge-sorted-array/
This one, right?
delicate geode
Yes.
vocal gorge
hmm, I'm not sure whether it's possible to solve it in O(n) time and O(1) extra memory. Personally, I solved it in O(n) time and O(n) extra memory - merged the two lists into a third one, then rewrote the contents of nums1 with it
Your solution looks to be paying a complexity of O(n^2) time for being O(1) extra memory
(because you, at worst, shift the list to the right (an O(n) operation) for each element or so)
delicate geode
Yeah I was thinking of what I can do to avoid needing to shift arrays because the problems before used shifting.
vocal gorge
you can also almost certainly get by without an explicit shifting method by instead just using .insert to put an element into that position
that does precisely what you're doing - shifts the rest of the list to the right
but it's implemented in C, so will be much faster than doing so manually in Python.
delicate geode
I thought of a dirty trick where I would append all the elements from both arrays (excluding the leading 0s because they're for giving space) and just call sort on it 🙂 .
vocal gorge
that would be O(n log n)
using a third array, merging the two in sorted order is just walking two indexes over the list
like, look at the two current elements. Append the smaller of them to the third list, and increment the index you just used.
and also you'll have to handle the case when one of the lists ends.
that's the O(n) time and O(n) memory solution.
delicate geode
So O(n) is the best time possible here?
agile sundial
O(n + m), where n and m are the lengths of the arrays
vocal gorge
So O(n) is the best time possible here?
Naturally, you need to copy the contents of the second list into the first after all, so there's no way to get by with less than O(m) even in theory - and probably not less than O(n+m) either, considering the bad case where the entire second list is lower than the first one
delicate geode
Hmm in C++ if I make a third array, then I can just std::swap it for sweet O(1) for that step.
Is there a swap in Python?
fair prairie
What are important data structures and algorithms to get job
I mean which are important
Not for job only
vocal gorge
Is there a swap in Python?
nope, you can swap two names but you can't actually swap the objects two pointers are pointing to
that'd be kinda bad too, since it'd allow "mutating" immutable objects
after all, everything in Python is passed by reference
lean dome
The equivalent to swap in Python would be passing the function a reference to an object that holds a reference to a list, instead of passing it a reference to a list. Then, you would mutate that object to refer to a different list.
Or, you take a list and return a list, and the list you return may be a different list, and it's the caller's responsibility to assign it back to some attribute.
mild cape
What are important data structures and algorithms to get job
linked list, stack, queue, deque, etc
tree, binary tree, self balance tree, heap, etc
hashmap, (different collision resolutions methods)
are probably a good set of them
spring jasper
so lets say i have a tree and i wanna traverse it inorder
why cant i do
def inorder(self, node=self.root):
if node is not None:
self.inorder(node.left)
print(node.val)
self.inorder(node.right)
why cant i have an instance attribute as a default kwarg
actually this doesnt have to be about trees, just wondering why instance attributes dont work as defaults
vocal gorge
so lets say i have a tree and i wanna traverse it inorder
why cant i do
```py
d...
Because defaults are calculated once when the function is defined, not when the function is called.
So it can't depend on the other arguments.
the way of doing this is:
def inorder(self, node=None):
if node is None:
node = self.root
#...
ah but in this case the none check is for when it hits a leaf so i dont think i can actually do that
guess i'll stick to helper functions
dusk flare
https://github.com/joowani/binarytree
i want to visualize a binary tree , i have found this repo but, is there any way i can put node value inside a proper box instead of a combination of '\ - '
spring jasper
you can use jupyter like they do in their demo
delicate geode
Okay, so I've improved my solution :)```py
class Solution(object):
def merge(self, nums1, m, nums2, n):
n1_idx = 0
n2_idx = 0
nums3 = []
while True:
if n1_idx == m and n2_idx == n:
break;
if n1_idx < m and n2_idx < n:
n1_val = nums1[n1_idx]
n2_val = nums2[n2_idx]
if n1_val <= n2_val:
nums3.append(n1_val)
n1_idx += 1
else:
nums3.append(n2_val)
n2_idx += 1
else:
if n1_idx < m:
nums3.append(nums1[n1_idx])
n1_idx += 1
if n2_idx < n:
nums3.append(nums2[n2_idx])
n2_idx += 1
for i, val in enumerate(nums3):
nums1[i] = val```
However, I've only beaten 40% of people in terms of speed and memory usage 😦 .
vocal gorge
I saw it on a tik tok
I-
are there programming tictoks or something lmao
that exists???
all complexities exist
though not sure I can think of any sqrt(n) one
old rover
Yes I know what big O notation is
I have just never seen a O(sqrt N) time complexity
and yes there are coding tik toks
something something Grover algorithm
onyx root
@old rover a simple routine to decide if a number is prime is O(sqrt(N))
old rover
oh
onyx root
def is_prime(n):
for i in range(sqrt(n)):
if n % i == 0:
return False
return True