#algos-and-data-structs

1 messages · Page 140 of 1

bitter nacelle
#

@gritty marsh hello

gritty marsh
#

hello, just ask your question

bitter nacelle
# gritty marsh hello, just ask your question

time complexity for this algo

    try:
        value=0
        if(data):
            watsonPqueue.remove(data)
        else:
            value=watsonPqueue[0]
            watsonPqueue.pop(0)
        watsonPqueue.sort(reverse=True,key=getSumOfDigits)
        return value
    except IndexError as err:
        print("Oops!!:",err)
        exit()```


>> for deletion, will it be O(n log n)?
#

used priority queue deletion ()

sort is O(n log n) but for pop() it's O(1)
right?

gritty marsh
#

some sort of heap?

bitter nacelle
#

in this, one data item is removed and from te rest, values are added

gritty marsh
#

you can implement a priority queue in different ways - heap, list that maintains order, etc

bitter nacelle
#

Ohhhh its a list

dark aurora
#

Im just saving code here, no help needed

# 
import math
 
n, m = list(map(int, input().split()))
lof = [list(map(int, input().split())) for x in range(m)]
bg = math.inf
cn, we, pr, owe, hp, j = [[] for x in range(n+1)], [[] for x in range(n+1)], [0]*(n+1), [bg]*(n+1), [1], 1



for x in range(len(lof)):
    cn[lof[x][0]].append(lof[x][1])
    we[lof[x][0]].append(lof[x][2])

owe[1] = 0
owe[0] = 0
pr[0] = 1

def hpi(i):
    hp.append(i)
    inx = len(hp)-1
    while owe[hp[(inx-2)//2+inx%2]] > owe[hp[inx]]:
        owe[hp[(inx-2)//2+inx%2]],owe[hp[inx]],inx = owe[hp[inx]],owe[hp[(inx-2)//2+inx%2]],(inx-2)//2+inx%2
        if inx == 1 and owe[hp[0]] > owe[hp[1]] or inx == 0:
            if x != 0: owe[hp[0]],owe[hp[1]] = owe[hp[1]],owe[hp[0]]
            break



while hp != []:
    z = hp[0]
    if pr[z] == 0:
        for x,i in enumerate(cn[z]):
            owe[i] = min(owe[i], (owe[z] + we[z][x]))
            if pr[i] == 0:
                hpi(i)
    pr[z] = 1
    hpt()
    
        

print(" ".join(list(map(str, owe[1:]))))```
# 

lst = [0, 1, 2, 3, 4, 5, 6, 7 , 8, 9, 10, 11, 12, 13, 14, 15]
owe = [0, 7, 10, 14, 19, 33, 35, 26, 11, 26, 45, 34, 22, 11 ,27, 98]
hp = [2, 3, 4, 7]



def hpi(i):
    hp.append(i)
    inx = len(hp)-1
    while owe[hp[(inx-2)//2+inx%2]] > owe[hp[inx]]:
        owe[hp[(inx-2)//2+inx%2]],owe[hp[inx]],inx = owe[hp[inx]],owe[hp[(inx-2)//2+inx%2]],(inx-2)//2+inx%2
        if inx == 1 and owe[hp[0]] > owe[hp[1]] or inx == 0:
            if x != 0: owe[hp[0]],owe[hp[1]] = owe[hp[1]],owe[hp[0]]
            break
            
    
            
                    

       
    

hpi(8)
print([owe[i] for i in hp])```
fast merlin
#

I'm having a string "a (123) b1 (3912)" and trying to match everything besides the digits in parentheses thought of simple [^\d{3,} ] but that will include 1 from b1 😦 any regexp ninja that have an idea?

runic tinsel
#

regex can't do [^\d{3,} ]

#

not a thing

#

(?<= |^)\w+ would probably work

#

a word preceded by space

#

assuming you match words

fast merlin
#

🤯 @runic tinsel thanks a lot!

shut breach
golden sky
#

hey

#

can you go to help cookie to help me?

#

I believe my issue has to do with algos and data structs

fiery cosmos
#

python docs or on youtube u can refer "jimshaped coding"

gusty root
fiery cosmos
fiery cosmos
chilly cypress
#

Hello Everyone can any please help in my python assignment?

#

a. The preorder_serialize() method should use the preorder traversal and return the string “20, 8, 4, None, None, 12, 10, None, None, 14, None, None, 22, None, None”. (40 pts)
b. In BinaryTree, add a method save(string) to write the string into a text file and name it your Lastname_Firstname.csv. (10 pts)
c. In BinaryTree, add a method retrieve() to read the string from your text file and return the string. (10 pts)
d. In BinaryTree.java, add a method pre_order_deserialize(string) that accepts a serialized string, deserializes the given string to the original binary tree, and returns the tree. (40 pts)

#

Its a Homework assignment just in case if anyone had doubt

halcyon plankBOT
#
Rules

8. Do not help with ongoing exams. When helping with homework, help people learn how to do the assignment without doing it for them.

trim galleon
#

Is biconnected components and strongly Connected components are same thing??

harsh field
shut breach
trim galleon
#

Can you please suggest me a video or any link of details explanation of biconnected components??

#

Please

shut breach
#

i dont have any links at hand

#

o <-> o <-> o
this graph is strongly connected but not biconnected

keen osprey
#

Hello

wheat crypt
#

Anyone have a good book or YouTube or course to start learning algos and data structs using python?

shut breach
golden sky
#

I ended up doing a pivot table which seems to be the way to go

#

I still have some things to improve but I believe I am getting there, thank you

fiery cosmos
# 
>>> bin(5)
'0b101'
>>> bin(~5)
'-0b110'
>>> 5
5
>>> ~5
-6

why isnt bin(~5) b010?

#

sorry i dont understand can you give an example?

#

oh okay, i think i see it. it's because pythons showing the unsigned binary string of a negative number

gilded skiff
#

Hello,

Having issues pulling the peg_ratio using yahoo_fin

peg_ratio = float(si.get_stats_valuation('A')[1][4])```
woven basin
#

hi, is this accurate for data structures?

data_structures.png
glossy tinsel
#

What does primitive means?

woven basin
#

data that stores data of one type only

glossy tinsel
#

Alr ty

vocal gorge
#

hmm, would complex count as a primitive?

glossy tinsel
#

What is complex?

vocal gorge
#

python has complex numbers built-in.

#

!docs complex

halcyon plankBOT
#
complex 

class complex([real[, imag]])```
Return a complex number with the value *real* + *imag**1j or convert a string or number to a complex number. If the first parameter is a string, it will be interpreted as a complex number and the function must be called without a second parameter. The second parameter can never be a string. Each argument may be any numeric type (including complex). If *imag* is omitted, it defaults to zero and the constructor serves as a numeric conversion like [`int`](https://docs.python.org/3/library/functions.html#int "int") and [`float`](https://docs.python.org/3/library/functions.html#float "float"). If both arguments are omitted, returns `0j`.

For a general Python object `x`, `complex(x)` delegates to `x.__complex__()`. If `__complex__()` is not defined then it falls back to `__float__()`. If `__float__()` is not defined then it falls back to `__index__()`.
vocal gorge
#

and in CPython at least, these are not implemented as a class with two float fields (though internally, of course, it does boil down to two double values).

woven basin
ivory yacht
#

Python doesn't really have "primitive" values, everything's a full object.

#

Primitive types in other languages are things that are copied by value not reference, can be stored on the stack not heap, etc which doesn't apply. Also, strings and integers in particular are variable length, and so can end up very large in memory. Your split might be better phrased as something like "collection"/"non-collection", with strings moved over to the other side.

strong hornet
#

hello

#

are you there

lean dome
strong hornet
#

hello jolly

lean dome
#

Hi

strong hornet
#

how old are you

lean dome
#

That's not on topic for this channel.

strong hornet
#

I'm new around here

lean dome
#

If you're just looking to chat, check out our off topic channels

strong hornet
#

just greetings

strong hornet
lean dome
#

No worries - welcome!

#

But we do try to keep the topic based channels on-topic.

strong hornet
#

I understand, I'm a developer, and I work on a project in python, only before greetings

#

sorry

woven basin
lean dome
#

They may not even realize that it's wrong to call int a primitive in Python, because they're so used to languages where it is a primitive.

#

!e But in Python, ints have methods!

print(32768 . to_bytes(4, "little"))
halcyon plankBOT
#

@lean dome :white_check_mark: Your eval job has completed with return code 0.

b'\x00\x80\x00\x00'
dense forge
# ivory yacht Primitive types in other languages are things that are copied by value not refer...

Who said primitive data types in other languages are only copied by value, not reference? I don't know what languages you meant by "other languages". As far I know, you can copy value from one reference to another reference in C++ via pointers. But only lvalue assignment are allowed not rvalue. But the difference is, yes there no actual difference among the primitive data types in Python, everything is an object. And for C++, everything can be represented by pointers.

mighty ice
#

hey how can i write a algo to fix errors in a sentence

#

for example i have a sentence hello how are you
and input is helo hor are
and i want result as hello how are

hot thistle
mighty ice
#

hmm what you mean by I.A

hot thistle
#

artificial intelligence. I.A is the
abbreviation in spanish, sorry i'm confused ahaha

austere sparrow
#

What languages have primitive types though? Java, C# and C?

I'm not sure Rust or C++ truly have such a category. Rust has Copy types, and I remember there's something like that in C++ (with arcane syntax of course)

#

Hmm, does C even have the notion of a primitive type?

chrome kelp
austere sparrow
lean dome
austere sparrow
#

ah

lean dome
#

It also refers to "derived types", which are arrays, structures, unions, function types, and pointer types

austere sparrow
# austere sparrow ah

but that's just superficial classification, right? Both can be on the heap, the stack etc.

lean dome
#

When I think of primitives in C, I use the meaning of "not a derived type" I suppose

austere sparrow
#

I guess

#

maybe it's one of those terms which exists, but doesn't mean much

#

like 'weak typing'/'strong typing'

lean dome
#

Even the Wikipedia page on primitive data types acknowledges that some people use it to mean types built into the language, and others use it to mean types that are basic building blocks not derived from any other type

half lotus
#

By the latter definition c# then also lacks primitives, since those "value types" actually based on "structure types"

austere sparrow
half lotus
#

Maybe as far as really popular languages go.

austere sparrow
#

yeah

chrome kelp
chrome kelp
young tangle
woven basin
#

Hell, now I want a book about python concepts that I can use as a reference book. Any recommendations?

bitter wigeon
#

You can use something more smart that predicts probable misspell with ML but you need to train it and more code.. depends on how robust the spell check needs to be...look for libraries

#

The spell checker maybe tied to your OS of choice if you go the library route

dense urchin
#

This is so nice.

bitter wigeon
#

I have code like that scattered around but too lazy or shy to put on github ....maybe i should

chrome kelp
mighty ice
#

but this is not what i want

#

now i am trying to get things done with difflib.get_close_matcher()

bitter wigeon
#

Could work

#

Make a concordance first or a list of all unique words in the lisy

#

List then for each word test for close match then do global string replace with correction

#

You can also test each word individually like a word processor does but it will involve more repeat calls to string test

fiery cosmos
#

does the bisect library have a different name in algorithm textbooks? i'm trying to find an explanation of what it is and I can't find much on google

bitter wigeon
#

Could be related to binary search tree

#

Divide list into two = bisect

slow minnow
#

i need some help understanding B-trees

#

what are the three conditions and how to i identify them in a present tree

#

What is "M"

#

how do i calculate sealed m/2

austere sparrow
#

!pban 916504436271112193 Spamming an advert to buy accounts

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied purge ban to @vernal turret permanently.

agile sundial
cerulean elk
#

okay so I was experimenting around with python today and I learnt about dictionaries

#

How do I access the index of the key

#

like let me xplain

# 
print(x)
for i in range(x):
  if x[1]==42:
    print("Hey")
  else:
    print(x)```
#

I wanna make a code smth like this but IDK how to access the answer

harsh field
#

I'm gonna test if it works

#

looks like it works

fiery cosmos
#

Dictionaries don't really have indices. they are key-value stores. You can get a list of tuples of each pair using dict.items() if you really need to

cerulean elk
harsh field
#

in your example "what's 7x6" is a key

cerulean elk
harsh field
#

you can do list(dictionary)

#

or

#

print(list(dictionary))

#

to get the list of your keys for that dictionary

cerulean elk
#

okay one sec

# 
print(x)
for i in range(x):
  if x[1]==42:
    print("Hey")
  else:
    print(x)```
#

I wanna make a code like this

harsh field
#

i dont know if this is the best way

cerulean elk
#

how would u suggest to go at it

harsh field
# 
x={"what's 7x6":42,"what is 6x9":54}
print(x)
for i in range(len(x)):
  if (list(x.values()))[i]==42:
    print("Hey")
  else:
    print(x)
#

oh that doesnt work

#

🤔

#

ah i missed a ()

#

edited it

#

so the original print(x)

#

then the for loop
first result returns "hey", second prints x

cerulean elk
#

okay thank you so much

harsh field
#

no problem

austere sparrow
#

just have a list of pairs

cerulean elk
harsh field
agile sundial
gray sequoia
#

i don't understand how to solve this.

Screenshot_from_2021-12-25_15-19-15.png
austere sparrow
gray sequoia
#

no that's why i'm stuck

#

ok but that doesn't increament the color 2

austere sparrow
gray sequoia
#

color2 doesn't increament so the logic is wrong or something.

#

increase

austere sparrow
#

You can't increment something if that something is not defined

gray sequoia
#

i get this

Screenshot_from_2021-12-25_15-25-38.png
austere sparrow
#

@gray sequoia It should be just global color2

#

But you shouldn't use a global here.

#

You can just make it an attribute of your App object.

#

Do you know about attributes?

gray sequoia
#

no i don't

austere sparrow
gray sequoia
#

i read python manual few times already. instead of me reading the entire manual to get the answer i come here so i can talk to a human to tell me what's wrong.

austere sparrow
#

Basically, you can do self.color2 = 0 in your __init__, and then just access self.color2

# 
class App:
    def __init__(self):
        ...
        self.color2 = 0

    def draw(self):
        self.color2 += 1
        ...
        # use self.color2 somehow
#

!e
If you're not familiar with attributes, that's how objects store their state. This is how you can make a counter, for example:

class Counter:
    def __init__(self):
        self._count = 0

    def bump(self):
        self._count += 1

    def count(self):
        return self._count

counter = Counter()
counter.bump()
counter.bump()
counter.bump()
print(counter.count())
halcyon plankBOT
#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

3
austere sparrow
gray sequoia
#

i guess after a hundreds of hours of python tutorials i still don't get it.

#

i thought python was supposed to be the easiest language. ...

austere sparrow
#

well, programming in general isn't easy 🤷

#

is there something in particular you don't understand?

gray sequoia
#

well, in c and haxe all i gotta do is int color2=0 then use it in scope but in python i appears i gotta declare a class before i can use it?

austere sparrow
#

I don't really understand what you're trying to do

gray sequoia
austere sparrow
#

Ah, i see

#

pixel.run will call your run method before the color2 attribute is assigned

#

So you need to put self.color2 = 0 first

austere sparrow
gray sequoia
#

ok gotta it. thanks

#

this works.

#

what happened was it calls the game before executing the variable.

grave iron
#

Hi

flat bone
#

Hi I am new here, I just started learning python, Can I know where I can ask my basic doubts ?

vocal gorge
violet marsh
harsh field
# agile sundial wdym check for certain values

well, I'm thinking of things like chaotic systems.
For example, I was once looking into conways game of life.
I wanted to find a starting position with a small number of cells that could eventually produce a large number of cells in a small number of turns.

Several starting positions would converge on one position. So if I could store every position (that the program generates) as a key, and the maximum number of cells they produced in the next X number of turns, then i could save a lot of time in my calculations by checking if a position had been calculated before.

So that would be a situation where the dictionary is useful; i can't imagine how i would use a list to store position, maximum-cell-number pairs in a way that would let me look them up in O(1) time.

But after running enough starting positions, I would want to be able to get the values out of my dictionary, without knowing the keys.

Something like:

bestval = 0
bestpos = ""
for i in range(len(dictionary)):
  if (list(dictionary.values))[i] > bestval:
    bestval = (list(dictionary.values()))[i]
    bestpos = (list(dictionary))[i]
print(bestpos,bestval)

You'd get the benefit of having a dictionary for when the O(1) look up time is useful (and a list is impractical), but you'd be able to check for certain values when you want to find a specific result

vocal gorge
#

this specifically can be written as bestpos, bestval = max(dictionary.items(), key=lambda item:item[1])

harsh field
#

nice! I'm still very unexperienced with python 😅

agile sundial
#

what's the exact quote?

agile sundial
#

wdym "work in linear time"

#

it sounds like a list though, assuming that last part was assuming it was sorted

#

¯_(ツ)_/¯

bitter wigeon
#

linear time good mean not exponentially growing as more items are in the list

#

There is polynomial time too

#

Ihttps://en.m.wikipedia.org/wiki/Time_complexity

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus,...

harsh field
#

there are sets in python, which arent ordered, and dont keep track of duplicate entries

#

theyre similar to sets from set theory

#

you might find this useful:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/

MIT OpenCourseWare
Mathematics for Computer Science

This subject offers an interactive introduction to discrete mathematics oriented toward computer science and engineering. The subject coverage divides roughly into thirds: Fundamental concepts of mathematics: Definitions, proofs, sets, functions, relations. Discrete structures: graphs, state machines, modular arithmetic, counting. D...

#

lists function like what a mathematician would call an ordered set (i think) an n-tuple [edited]

shut breach
#

it's sort of analogous to a vector or tuple

vast sentinel
#

anyone knows how this is syntax error?

unknown.png
fervent saddle
#

You can search in log(n) time
They’re talking about C++ sets, maybe. They’re a type of tree structure. Python sets use hashing

#

And they can be iterated in sorted order in C++ since they use a tree structure

harsh field
vast sentinel
shut breach
agile sundial
dark aurora
#

Can someone help me with my Dijkstra implementation, I don't know why it doesn't work, and I have no idea of how to find out?

fervent saddle
#

Oh

#

Yeah then that’s weird, I wonder what they meant

dark aurora
#

code

# 
import math
 
n, m = list(map(int, input().split()))
lof = [list(map(int, input().split())) for x in range(m)]
bg = math.inf
cn, we, pr, owe, hp, j = [[] for x in range(n+1)], [[] for x in range(n+1)], [0]*(n+1), [bg]*(n+1), [1], 1
 
 
 
for x in range(len(lof)):
    cn[lof[x][0]].append(lof[x][1])
    we[lof[x][0]].append(lof[x][2])
 
 
 
owe[1] = 0
owe[0] = 0
pr[0] = 1
 
 
 
def hpi(i):
    hp.append(i)
    inx, g = (len(hp)-1), (((len(hp)-1)-2)//2)+((len(hp)-1)%2)
    while owe[hp[inx]] < owe[hp[g]]:
        hp[inx], hp[g] = hp[g], hp[inx]
        inx = ((inx-2)//2+(inx%2))
        if inx == 0: break
        g = ((inx-2)//2+(inx%2))
 
def hpt():
    hp[0],hp[-1] = hp[-1],hp[0]
    hp.pop(-1)
    inx = 0
    if len(hp) == 2:
        if owe[hp[0]] > owe[hp[1]]:
            hp[1],hp[0] = hp[0],hp[1]     
    elif len(hp) > 2:
        while owe[hp[inx]] > owe[hp[inx*2+1]] or owe[hp[inx]] > owe[hp[inx*2+2]]:
            if owe[hp[inx*2+1]] < owe[hp[inx*2+2]]:
                hp[inx],hp[inx*2+1] = hp[inx*2+1],hp[inx]
                inx = inx*2+1
            else:
                hp[inx*2+2],hp[inx] = hp[inx],hp[inx*2+2]
                inx = inx*2+2
            if (inx*2+2) > len(hp)-1:
                if (inx*2+1) > len(hp)-1:
                    break
                else:
                    if owe[hp[inx*2+1]] < owe[hp[inx]]:
                        hp[inx*2+1],hp[inx] = hp[inx],hp[inx*2+1]
                        break
                    else:
                        break
 
while hp != []:
    z = hp[0]
    if pr[z] == 0:
        pr[z] = 1
        for x,i in enumerate(cn[z]):
            hpi(i)
            owe[i] = min(owe[i], (owe[z] + we[z][x]))
        
    hpt()
                    
print(" ".join(list(map(str, owe[1:]))))
dark aurora
#

I don't know why this stuff happens

smoky roost
#

Hi i am new here! I wanna learn data-struct and algorithm from beginner to advanced level. Could you recommend me some reference,books or blogs? I think it should be easy to understand. I have read a book call "Data Structures and Algorithms in Python" but so many things

agile sundial
#

check the pins in this channel

smoky roost
smoky roost
#

I had a small question. Should I find a senior or coding expert person to teach me this? Or I should learn it by myself?

agile sundial
#

unless you pay a lot, you'll probably find not many people have the time for it

smoky roost
bitter wigeon
frigid forge
#

Anyone knows Hierarchical clustering (Divisive)?

#

How many steps maximum there can be for matrix n,n?

#

Ping me

fiery cosmos
sharp mica
#

Anyone who can help me in creating an order matching engine. I'm a complete beginner and don't know where to start 😩

shut path
#

'

lilac zephyr
#

what is a greedy ascent algorithm

fiery cosmos
#

is it correct to say a decorator is a closure?

>>> def my_decorator(f):
...     @wraps(f)
...     def wrapper(*args, **kwds):
...         print('Calling decorated function')
...         return f(*args, **kwds)
...     return wrapper

(from the docs) here wrapper is a closure because the variable f is bound to some function, and f is a non local variable in the wrapper function from the enclosing scope

lean dome
woeful basin
#

I'm creating a simple project in python using cv2. I've a doubt. In which channel should I ask a question from?

bitter wigeon
#

CV2 or openCV in common use in image recognition .. post to Data Science and AI

woeful basin
split garden
#

is there a simple way to calculate a list of coordinate pairs for all of the lines in a radial grid of hexagons given a radius? I'm calculating every point for each octogon right now (I can do the distortions myself after the grid is made)

bitter wigeon
#

Compare that with the standard square grid which is composed of two sets of parallel lines at 90 degree angle ...same concept

#

As for the line intecept points you can compute them individually or take a shortcut and take advantage of the fact that offsets are regular

split garden
#

I'll give that a shot tomorrow when my brain isn't zapped haha, thank you.

#

That make sense to me though, basically fin the first two points in one set of parallel lines and just keep adding an offset

bitter wigeon
#

Lol no worries i have done that myself but i dunno where the code is

#

Tomorrow is 3rd doze covid shot for me so i might be offline for a bit but i will check in

dreamy arrow
#

guys i want to ask u a question for design patterns
which language will make me understand it well?
python or java !
by the way i know both languages but i have made more projects incuding deep and machine learning using python but no problem for me using java ?

fluid sand
#

and also how to apply multithreading concept on it

pure torrent
# vast sentinel anyone?

well u r using next_states the same time you are defining it, i think u can do that if next_states has a previous value before

#

otherwise it would just result into an error

#

what was the error again?

amber otter
vast sentinel
pure torrent
#

you are using the variable next_states the same time you are defining it

#

you can't do that

vast sentinel
#

so you are saying i should create a new variable and store all of it inside and then put it in next states

#

to achieve the same thing

halcyon plankBOT
#

Hey @fluid sand!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

frail flare
#

Is there a better / "more pythonic" way to temporarily insert an item into the beginning of a for loop? Currently I have this:

channels: List[Channel]
special_channel: Channel
inserted = [special_channel]
inserted.extend(channels)
for channel in inserted:
    ...
#

I tried crafting something up as a one-liner in the for loop itself, but the closest I got was itertools.chain([special_channel], channels), which is kinda meh

austere sparrow
#

(the first one being lazy, while the second one actually creates a new list)

frail flare
#

huh, so the chain one was okay?

#

I see, alright

austere sparrow
#

what's wrong with it?

frail flare
#

I mean, nothing, just wasn't sure if there's a better option or not

#

Thank you gabsmile

austere sparrow
#

@split garden I would probably use the first one if the list wasn't huge

#

oops, wrong ping. I don't know how this happened

austere sparrow
frail flare
#

Ah, well, I'll just go with the chain one

split garden
#

Yay, I'm involved!

round glacier
#

What exactly does ``` @wraps(function)

#

what does @wraps do?

merry wave
#

Can anyone give me some good free resources to learn data structures and algorithms? I have no idea how to do it and want to learn.

I have heard that Leetcode is good but only if you already know data structures and algorithms.

agile sundial
#

check the pins in this channel

round glacier
agile sundial
#

?

round glacier
#

@agile sundiali am saying that i like your profile picture lol

idle pier
#

hello folks, I'm currently practicing on DP problems and am doing House Robber on Leetcode.
I was struggling so I looked up the solution

def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * len(nums)
        
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], nums[i]+dp[i-2])
        return dp[-1]```
Lets say our nums array was this `nums = [1,2,3,1]`
Where am lost, is on this `dp[i] = max(dp[i-1], nums[i]+dp[i-2])`
Can someone explain me what that line is doing?
glossy breach
#

do you understand what dp actually represents @idle pier ?

idle pier
glossy breach
#

No i mean

#

What is the meaning behind dp in this code

#

What does it stand for

idle pier
smoky roost
#

hi! I am a little confused in this case: If I have a class MyClass() and then I initialize a1 = MyClass(model_path = "x"), a2 = MyClass(model_path="y"). If I train the a1 model, does it affect a2 model? Thanks

glossy breach
#

Thats not what I meant but ok

#

So the approach here is

#

Assume dp[i] is the maximum amount of money you can rob considering only houses from 1 to i

#

Then you try to calculate the values of dp from smaller subproblems

raven kraken
# 
def countWords(self, words1: List[str], words2: List[str]) -> int:
        
        C1 = Counter(words1)
        C2 = Counter(words2)
        count = 0
        for k in C1:
            if k in C2 and C1[k] < 2 and C2[k] < 2:
                count += 1
                
        return count
#

Can anyone confirm the time and space complexity for this question? I think the space complexity should be O(len(words1) + len(words2)) where words1 and words2 are list of strings. And Time complexity could be O(N). If I am wrong please do correct me.

vocal gorge
vocal gorge
#

python dicts use a hash table internally

#

you could say that a dictionary is rather abstract - it has to be an associative array (a mapping from keys to values) requiring keys to be hashable. A hash table is a concrete data structure which has such properties, and in CPython dictionaries are implemented using hashtables

#

You could have a Python implementation where dicts would be implemented as, say, a BTree map, which will have different complexities - O(log n) in checks, say

#

(I don't know offhand if that would be valid - does the specification guarantee O(1) complexities for dicts?...)

#

Yeah, amortized constant time insertion, constant time lookups unless there's hash collisions

formal bison
#

@raven kraken I see n^2 worst case and n best case ? I haven't practiced this analysis

vocal gorge
#

how'd it be n^2 worst case?

#

also, what's n supposed to be?

raven saddle
#

Which is the best place to start with dsa and for practice problems

raven kraken
agile sundial
raven kraken
agile sundial
raven kraken
agile sundial
raven kraken
#

so T.C could be O(N^2)

agile sundial
#

worst case, yes

raven kraken
raven kraken
agile sundial
#

I think so

raven kraken
#

Then I guess I need to optimize it

agile sundial
#

why?

#

I'm pretty sure in cpython that worst case is impossible

raven kraken
#

Its just python3

agile sundial
#

it's the normal python pretty much everyone uses, so you probably are

dark aurora
#

How to change the value of a certain item in a heap using heapq in python?

#

I can't find the answer anywhere

vocal gorge
#

wdym the value of a certain item? heapq uses whatever comparison relations the items in the list have by themselves

dark aurora
vocal gorge
#

Well you can use tuples in heapq so for example (3, 1) the first is the value and the second is the item
Then you'd need to find the item in the list and get its value - not sure it's possible to do any faster than the straightforward solution of looping over the list (since the list is heap-ordered by the value, not the item)

dark aurora
#

I want to update the value while maintaining heap property

dark aurora
#

I just kept another list that kept track of indexes in the heap

dark aurora
# vocal gorge > Well you can use tuples in heapq so for example (3, 1) the first is the value ...

"The remaining challenges revolve around finding a pending task and making changes to its priority or removing it entirely. Finding a task can be done with a dictionary pointing to an entry in the queue.

Removing the entry or changing its priority is more difficult because it would break the heap structure invariants. So, a possible solution is to mark the entry as removed and add a new entry with the revised priority" this is what says on python website

#

but i don't understand what it means

round glacier
# 
    def get_tree_height_recursively(self, root: TreeNode) -> int:
        """ Returns the height of a tree, or subtree from a given root (uses recursion) """
        if not root:
            return 0
        left_height = self.get_tree_height(root.left)
        right_height = self.get_tree_height(root.right)

        return max(left_height, right_height) + 1```

Quick question. Wouldn't I get the same result if I just made the if statement return 1, and then remove the max + 1?
#

Also, is this basically the same thing in an iterative approach?:

   def get_tree_height_iteratively(self, root: TreeNode) -> int:
       """ Returns the height of a tree, or subtree from a given root (uses an iterative approach) """
       if not root:
           return 1

       my_queue = Queue()
       my_queue.enqueue(root)
       left_height = 0
       right_height = 0
       while not my_queue.is_empty():
           node = my_queue.dequeue()
           if node.left:
               left_height += 1
               my_queue.enqueue(node.left)
           if node.right:
               right_height += 1
               my_queue.enqueue(node.right)
       return max(left_height, right_height)```
shut breach
#

the expression in that return statement gets called multiple times

#

see how that +1 is the only thing actually incrementing the height?

#

without it, the number never goes up

violet sluice
#

ma ma mia

shut breach
#

that return statement is expressing the recursive relationship, which is that the height of a node is one more than the height of its children

round glacier
#

How can I implement a delete method for a BST

agile sundial
#

no

agile sundial
round glacier
agile sundial
#

right

dapper sapphire
#

I have done some string and array questions, so I feel ok with them, which topic should one tackle next?

  • Heap
  • Linked List
  • Trees
  • Graphs
  • Dynamic Programming

I have done linked list before. In the beginning of the year, so I will be able to pick that one up again fast.

#

I was just looking at Dynamic programming questions, climbing stairs and Fibonacci and it just went over my head.

worldly agate
#

tbh dynamic programming is a pretty nice thing to grasp

#

so i'd go with dp

maiden crown
#

Date = [[‘12-01-2020’,2,2],[‘03-21-2021’,36,0]]

I need to get the date with least year list and delete other list

#

I tried split and compared and took min it’s not working properly

gusty grove
#

i have a bunch of points and would like to now query them to find points near my point of interest P. My problem is that i may have millions of points and i cant afford a rebuilt that takes longer than say 10 seconds

fiery cosmos
#

Hello I have a pandas dataframe that contains COVID-19 incidence levels (Green - Low, Yellow - Medium, Red - High) per province/region and I want to determine the incidence level of the country based on the incidence level of each province.
To do that I'm using weighted average, but I wonder if you could lend me a hand figuring out a use case in which this approach wouldn't work totally fine. This is what I have so far:

num_green_provinces = 14
num_yellow_provinces = 10
num_red_provinces = 8

green_weigth = 1
yellow_weigth = 2
red_weigth = 3

weighted_average = ((14 * green_weigth) + (10 * yellow_weigth) + (8 * red_weigth)) / 3 + 2 + 1 
# result = 30

# ranges to determine incidence level for the country
country_incidence_level = "green"
if weighted_average >= 0 and weighted_average <= 20:
    country_incidence_level = "green"
elif weighted_average > 20 and weighted_average <= 40:
    country_incidence_level = "yellow"
elif weighted_average > 40:
    country_incidence_level = "red"

Incidence weight and ranges to determine whether a country should be considered as red, yellow or green are randomly selected so I would say that is key to determine appropiate ranges and weights to ensure a correct functioning. Am i right? Also if you have further solutions to this problem aside from this one please let me know.
Thank you in advance.

fiery cosmos
grim vortex
grim vortex
fiery cosmos
#

By making too big or too small ranges it could cause overfitting or underfitting respectively. Btw I'm not entirely sure if those are the terms to explain that issue.😅

atomic kettle
#

Hi, I am stuck at this json error pls help :

#

JSONDecodeError: Extra data

#

discord.ext.commands.errors.CommandInvokeError: Command raised an exception: JSONDecodeError: Extra data: line 1 column 5 (char 4)

#

help

#

anyone

austere sparrow
#

@atomic kettle We can't tell much without the code

atomic kettle
#

ok

# 
    r = requests.get(url)
    json_data = r.json()
    await ctx.send("IP: " + json_data["ip"] + "\nOnline: " + str(json_data["online"]) + "\nMax players: " + str(json_data["players"]["max"]) + "\nPlayers online: " + str(json_data["players"]["online"]) + "\nVersion: " + json_data["version"])```
grim vortex
# round glacier i understand the first two cases of deleting a node with no child, and deleting ...

Hello, then you should go back to learn recursion 😋

The basic idea of tree data structure is recursion. If you don't understand this, please don't move on until you grasp it.

Everytime you do a deletion in BST you can't just delete the node/the element in a tree, you need a replacement for the deleted one so your tree still have a pointer/reference to its children. There are two methods to find the replacement.

  1. inorderPredecessor, find the righest element from left subtree.
  2. inorderSucessor, find the leftest element from the right subtree.

I'm gonna explain the first one, first you traverse the node to the left subtree and then do a recursion to the right subtree from the current node of subtree until you hit node with the next of this node have null property, then this current node is going to be your new node to replace the deleted one.

austere sparrow
atomic kettle
#

ok thx

round glacier
cyan panther
#

I'm looking to very thoroughly learn DSA in Python, what is the best method? Which courses teach me the material but also provide a lot of practice questions?

jaunty maple
#

Pongrutttts

round glacier
cyan panther
#

Learn DSA in Python?

round glacier
#

No just learning it in general @cyan panther

#

I'm just curious

#

Do you have a goal in mind?

cyan panther
#

Im a first year so in a few months I will have to start interviewing for internships

#

So I want to be know DSA so I can start leetcoding with efficient solutions

shut breach
#

have you seen the pins in this channel?

cyan panther
#

No

round glacier
#

I see

cyan panther
#

Ok I just say it, yea I have seen those

#

I like the Rune Stone Academy books and the MIT lectures but I find the MIT problem sets usually too difficult

#

They are too math based and I havent taken discrete math yet

round glacier
#

i think the most useful thing would be to make use of your professors

#

i never went to school for CS so I wish I had those resources

#

i would try to learn something and then ask ur prof if u dont understand it

#

thats something I WISH I could afford 😄

# 
    def delete_recursive_helper(self, root: TreeNode, value: int) -> TreeNode:
        if not root:
            return root

        if value < root.data:
            root.left = self.delete_recursive_helper(root.left, value)
        elif value > root.data:
            root.right = self.delete_recursive_helper(root.right, value)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left

            # find inorder successor
            temp = root.right
            while temp.left:
                temp = temp.left

            root.data = temp.data
            root.right = self.delete_recursive_helper(root.right, root.data)

    def delete_recursive(self, value: int) -> None:
        self.delete_recursive_helper(self.root, value)```
#

what's wrong with my implementation of deleting from a BST?

#

its not working, been trying to debug it

#

not sure what im doing wrong sadly

vocal gorge
round glacier
#

It seems like it's literally deleting half the tree

#

lol

#

in the debugger

#

Oh looks like I just needed to add return root at the end of that last call

#

and i think my debugger was glitching out, it wasnt loading stuff

# 
    def delete_recursive_helper(self, root: TreeNode, value: int) -> TreeNode:
        """ Recursive helper method for deleting a value from a BST """
        if not root:
            return root

        if value < root.data:
            root.left = self.delete_recursive_helper(root.left, value)
        elif value > root.data:
            root.right = self.delete_recursive_helper(root.right, value)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left

            # find inorder successor, we have two children on this node
            temp = root.right
            while temp.left:
                temp = temp.left

            root.data = temp.data
            root.right = self.delete_recursive_helper(root.right, root.data)
            return root

    def delete_recursive(self, value: int) -> None:
        """ Deletes a value from the BST using a recursive approach """
        self.delete_recursive_helper(self.root, value)```
#

Does this look right? I made some pytest tests and all my tests pass 😄

#

I'm not sure that this part is neeeded:

if not root:
  return root```
vocal gorge
#

I think the return type is TreeNode | None because of, at the very least, this:

            if not root.left:
                return root.right # what if it's None?
            elif not root.right:
                return root.left
round glacier
#

So I would need to change it to Union[TreeNode, None]?

#

Is TreeNode | None the same as using a union?

vocal gorge
#

Yes, exactly the same, but it's a pretty new feature - 3.10, I think. Before, only Union.

round glacier
#

I see. I think at work we only use 3.9, so that's why I've never seen that before.

vocal gorge
#

by the way, Union[T, None] is better written as Optional[T]. It's only nowadays with | it's shorter to write T | None.

round glacier
#

Wait so

#

Optional is basically None, or the value T?

vocal gorge
#

Yup, Optional[T] is Union[T,None]

round glacier
#

ahh

#

That makes sense

#

I feel like the hardest part of BST's is just the deletion

#

That is soooo hard to understand and I still don't fully get it

#

insertion, easy. searching, easy. deletion, hard

#

Onto AVL trees now

#

probably gonna take me a week to understand these lol

# 
temp = root.right
            while temp.left:
                temp = temp.left```
#

i dont understand this concept

#

why do we find the inorder successor by going right and then left?

#

why not just go right?

#

@vocal gorgedo you understand this?

vocal gorge
#

if I understand it correctly, it has to be the lowest node higher than value - so we move right once, getting into the subtree that are all larger, and then we need the smallest of these, so we go as left as we can

round glacier
#

Lowest node that is higher than the one we want to delete?

vocal gorge
#

yeah, since it's inorder traversal, the successor is the node with the lowest value that's higher than the current one

round glacier
#

I've heard you could also use the inorder predecessor

mellow bobcat
#

Im new

#

whats wrong with this code

round glacier
#

This isn't really an algorithm @mellow bobcat

#

Post in anothe channel and @ me and i can probably help

mellow bobcat
#

question is where

#

:/

round glacier
#

Any of the help channels

clear ferry
#

@fiery cosmos hey, sorry I had to eat.
Your implementation works fine 70% of the time I'm not sure why the x doesn't decrease

#

Do you want me to clip what's going on? I have no idea how to explain it

agile shale
#

Hello everybody. I have completed basic syntax and OOP in python. Now I want to learn dynamic programming. Where would you suggest to a newbie to learn from?

dapper sapphire
#

Can we have dfs and bfs in strings, arrays, trees, and graphs, in all of them?

#

If we can bfs and dfs in strings and arrays, then those have to be 2D?

agile shale
#

I am programming in python since 9th grade now I am in College first year (4 years exp). I recently realized the next step is to learn Dymanic programming and Data Structures And Algo and I want to learn them.

lean dome
dapper sapphire
#

oh ok thanks jollygeek!! I guess I will ultimately get to it when I start doing graphs.

lean dome
# agile shale I am programming in python since 9th grade now I am in College first year (4 yea...

In a nutshell, dynamic programming is saving solutions to sub-problems, so that you can reuse those solutions if you later discover that you need to re-solve the same sub-problem. There's two approaches to dynamic programming, one called "top down" and one called "bottom up". Both are the same, the only difference is which order you solve the subproblems in. The "top down" dynamic programming approach is often called "memoization"

agile shale
#

Ohh okayyy

#

Where can I understand about it in more detail?

shut breach
#

have you learned about recursion yet?

agile shale
#

yes

grim vortex
grim vortex
# round glacier I've heard you could also use the inorder predecessor

Yes, you could. I modified your previous code so you go to left first and then go to right until you hit null node.

def delete_recursive_helper(self, root: TreeNode, value: int) -> TreeNode:
        """ Recursive helper method for deleting a value from a BST """
        if not root:
            return root

        if value < root.data:
            root.left = self.delete_recursive_helper(root.left, value)
        elif value > root.data:
            root.right = self.delete_recursive_helper(root.right, value)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left

            # find inorder successor, we have two children on this node
            #temp = root.right
            #while temp.left:
            #    temp = temp.left

            #root.data = temp.data
            #root.right = self.delete_recursive_helper(root.right, root.data)
            # find inorder predecessor
            temp = root.left
            while temp.right:
                  temp = temp.right
            root.data = temp.data
            root.left = self.delete_recursive_helper(root.left, temp.data)
            return root

    def delete_recursive(self, value: int) -> None:
        """ Deletes a value from the BST using a recursive approach """
        self.delete_recursive_helper(self.root, value)
coral portal
#

thats not correct

#

i would reccomend getting some help with that

wispy hare
#

Hello, how can the graph coloring problem be verified in polynomial time?

shut breach
#

can you specify which graph coloring problem?

fiery cosmos
#

@shut breach transparent, I can't see it. I am not sure why.

dapper sapphire
#

Hi, what's a good resource to learn about heapq?

agile sundial
#

learn about the module in python or how heaps work in general

dapper sapphire
agile sundial
#

yes, that

dapper sapphire
#

ok I will play around with it! Thank you (:

agile sundial
#

wait, what?

#

ok i guess

dapper sapphire
#

Yeah, what you said learn about the heapq module in python.

agile sundial
#

ah, i see the confusion

dapper sapphire
#

So I will try different things with it and get a better understanding of how it's working..

agile sundial
#

i was asking you what you wanted to learn

dapper sapphire
#

heapq

agile sundial
#

right, the module or the data structure in general

dapper sapphire
#

Oh I see where the confusion is.

#

So is the python heapq module is different from the general heapq data structure?

agile sundial
#

kinda? python's heapq is an implementation of a heap

dapper sapphire
#

So is python's heapq just like the general heap?

I dont think I know what a general heap is besides that it's structured like a tree, and it's perfectly balanced.

Root node value of a heap is the minimum value. And by default that's the behavior of python's heapq.

fiery cosmos
# 
dic = {}
def sussy(string):
    global dic
    v=False
    if string[0].lower()+string[1].lower()+string[len(string)//2].lower() == 'sus':
        v=True
    if v:
        dic[string] = v
#

e!

cobalt rapids
#

!e @fiery cosmos

dic = {}
def sussy(string):
    global dic
    v=False
    if string[0].lower()+string[1].lower()+string[len(string)//2].lower() == 'sus':
        v=True
    if v:
        dic[string] = v
halcyon plankBOT
#

@cobalt rapids :warning: Your eval job has completed with return code 0.

[No output]
fiery cosmos
#

i wanna learn trees but cant find a good tutorial someone suggested me a tutorial but its in jvs i need a tutorial in python

lament summit
#

im blu

raven tide
#

hello, i need help with a codeforces question

# 
import math

t=int(input())
for i in range(t):
    n,k=[int(j) for j in input().split()]
    array=sorted([int(j) for j in input().split()])
    summed=sum(array)
    small=array[0]
    ans=[]
    diff=summed-k
    array=[j-small for j in array]
    if k<summed:
        for j in range(n):
            sans=j
            minused=0
            if j!=0:
                minused=sum(array[-j:])
            while minused<diff:
                minused+=j+1
                sans+=1
            if minused<diff:
                sans+=math.ceil((diff-minused)/(j+1))
            ans.append(sans)
    else:
        ans.append(0)
    print(min(ans))
#

my code doesnt seem to pass the time limit, can anyone tell me which part of my code is taking too much time?

#

this is the question if anyone wants to see

austere sparrow
raven tide
#

what is line_profiler?

fiery cosmos
#

u can do it using recursion

#

if there are overlapping subs then use memoization

#

ig there wont be any

raven tide
fiery cosmos
#

ye

#

idk i am not too good at it

raven tide
#

im not sure how i can use recursion

fiery cosmos
#

lemme

#

show u

glossy nimbus
#

hello

fiery cosmos
#

idk

raven tide
#

yay i solved it

raven tide
fiery cosmos
dapper sapphire
#

heapq by default has min value at the root.

If we want the root to have max value, then would we have to implement that?

#

Or is there something that's already built-in?

dapper sapphire
#

Is there a benefit to doing heapify over heappush, in terms of time complexity or would it be the same?

heappush is O(log n) for one element. But O(n) or O(n + log n) if we have to push all elements of a list/array in a Tree like structure.

heapify I want to say is also O(n) or O(n + log n) because heapify at the core is pushing elements of a list in a Tree like structure.

dapper sapphire
austere sparrow
dapper sapphire
austere sparrow
#

yep

#

or well, turn the negative into positive and positive into negative

#

it's a bit of a hack though

dapper sapphire
#

haha yeah that's what I ended up doing and works like a charm!!

austere sparrow
#

doesn't it support a key function?

#

!d heapq.heappush

halcyon plankBOT
#
heapq.heappush 

heapq.heappush(heap, item)```
Push the value *item* onto the *heap*, maintaining the heap invariant.
austere sparrow
#

huh, it does not

dapper sapphire
#

What do you mean by key function?

round glacier
#

Which is harder to implement? AVL Trees, or Red-Black trees?

#

They seem to literally do the same exact thing. They auto balance the inner tree structure but its just a different implementation. Is there something else to it?

austere sparrow
#

I hope to avoid all the scary tree names in my lifetime 👀

#

I like birches and pines

round glacier
#

I've been working with AVL trees mostly, but I haven't looked at the RedBlack tree implementation yet. I'm just curious if one is harder to implement than the other. Also, I want to know if one is better than the other.

#

I have to learn this stuff for my job

#

Lol

#

I work at a major game company, and my boss basically said I need to get better at algorithms

#

So I'm doin it lol

#

Does anyone know?

dapper sapphire
#

Oh ok I see what you mean!

round glacier
#

I asked my boss a while ago why they do algorithm coding interviews. He told me it's to filter out lazy people who are unwilling to spend the time to learn these algorithms.

#

It makes a lot of sense honestly lol

#

If you're too lazy and unmotivated to learn them, why should we hire you?

austere sparrow
round glacier
#

Algorithmic thinking is useful in any code that you work on though

#

It's a mindset

austere sparrow
# round glacier It's a mindset

There are other paradigms of thinking: types, contracts, events, objects, queries/commands, etc.
What's special about "algorithmic thinking" and what is it exactly?

round glacier
#

If you don't know algorithms, you will always be getting brute force performance

austere sparrow
#

And if you don't know type theory, you are more likely to build a bad model for your data

#

So is 'algorithmic thinking' just knowing common algorithms?

round glacier
#

i dont know what type theory is

#

Nope

#

It's thinking with a mindset of performance in mind

austere sparrow
#

Performance isn't just about algorithms though, right? It's much more broad

#

I know about computational complexity. But if I need to improve the performance of something, there's little hope that my hand-rolled solution will outperform a ready-made library, such as multidict or sortedcollections

austere sparrow
# austere sparrow Performance isn't just about algorithms though, right? It's much more broad

I once spent quite a while implementing an ordered priority queue in Python. Took me a day or so.
It works and it has nice complexity properties, but for my purposes it was rather overkill: I only needed a few dozen, maybe a hundred elements.

So I don't think "you must know how to implement efficient algorithms" applies just on its own. If the programmer is expected to work on high-performance/high-load systems or invent brand new efficient algorithms, then it makes sense (in that case algorithmic complexity is just one brick in the wall: you can't make something faster just by making a nice algorithm). But I think most positions don't require that.

round glacier
#

mine does

#

lol

austere sparrow
#

well, in that case it is fine to expect that 🙂

#

Speaking of algorithms, is there some kind of standard recipe for an ordered priority queue?

#

ideally having the same interface as asyncio.PriorityQueue

round glacier
#

i dont know about python but i know c++ has one

#

its std::priority_queue

austere sparrow
#

is it ordered?

#

that is, if I insert three items with the same priority, will they come out in the same order?

round glacier
#

I think so. C++ usually has it labeled as unordered_map or just map for hash maps

#

So I assume its the same

#

there's also unordered_set and set

#

queue and dequeue

austere sparrow
#

I think I found a paper on implementing an ordered priority queue in C++ somewhere. But it's 15 pages long and I don't know C++ lol

round glacier
#

ive never implemented a priority queue

#

dont u just run the sorting method on it

#

i forget the name

#

theres a sorting method for it i think

austere sparrow
#

It gets really complicated if you need to change priorities of tasks... which is what I needed.

#

So this is what I did (pseudocode):

class Task(Generic[T]):
    uid: str
    invalidated: bool
    priority: int
    payload: T

    def __lt__(self, other):
        return self.priority < other.priority

class OrderedPriorityQueue(Generic[T]):
    tasks: PriorityQueue[tuple[Task, int]]
    counter: int
    uid_to_task: dict[str, tuple[Task, int]]

    def _insert(self, payload: T, priority: int, counter: int) -> str:
        uid = generate_uid()
        task = Task(uid, False, priority, payload)
        self.tasks.append((task, counter))
        self.uid_to_task[uid] = (task, counter)
        return uid

    def insert(self, payload: T, priority: int) -> str:
        self.counter += 1
        return self._insert(payload, priority, self.counter)

    def get_next(self) -> T:
        while True:
            _, task = self.tasks.pop()
            self.uid_to_task.pop(task.uid)
            if not task.invalidated:
                return task.payload

    def set_priority(self, uid: str, new_priority: int) -> str:
        counter, task = self.uid_to_task.pop(uid)
        task.invalidated = True
        return self._insert(task.payload, new_priority, counter)
#

basically,

  1. elements are compared first by priority, then by their sequence number
  2. when I want to change the priority of an item, I mark the old one as "dead" and add a new one with the new priority but the same sequence number
#

Hmm, I guess this would be easier if we had the queue equivalent of a ChainMap

round glacier
#

Isn't a priority queue just a max heap

austere sparrow
#

yep

#

I think 'priority queue' is a misnomer

#

because a queue implies an ordering

round glacier
#

You should look into HeapSort

austere sparrow
#

??

#

I know that a priority queue is just a fancy heap.

round glacier
#

Pretty sure u can just use heap sort

#

to make a priority queue

austere sparrow
#

What I need is a queue that supports both priority and insertion order

#

I think heapsort is unstable, which is the core of the issue

#

I want this, basically:

>>> queue = OrderedPriorityQueue()
>>> queue.push(42, priority=5)
>>> queue.push(100, priority=3)
>>> queue.push("foo", priority=3)
>>> queue.push("bar", priority=5)
>>> queue.push("baz", priority=5)
>>> queue.push(69, priority=3)
>>> queue.push(1, priority=0)
>>> list(queue.with_priorities())
[(1, 0), (100, 3), ("foo", 3), (69, 3), (42, 5), ("bar", 5), ("baz", 5)]
>>> list(queue)
[1, 100, "foo", 69, 42, "bar", "baz"]
#

I can't get this with a heap because it does not respect insertion order (i.e. "bar" and "baz" could be reordered)

round glacier
#

What are you trying to do this for?

austere sparrow
# round glacier What are you trying to do this for?

Well, the project is already done, but I'm wondering if there's a better way to do this.
I had a set of physical "things" which I needed to do background updates on in a round-robin way. However, sometimes I need to do active updates on some of the "things". When there are "things" that need active updates, they are updated first (also in a round-robin way). Only one "thing" can be updated at a time, and it takes some time

round glacier
#

What's the project

austere sparrow
#

i can't tell much

round glacier
#

oh

#

I can think of a few real-world applications for a priority queue

#

For example, compiling stuff in a specific order

#

If u have like 10 different C++ projects which rely upon each other's .exe's

#

You would put the highest priority as the first thing that needs to be built

#

then pop off from there

#

Not many code projects are that big though lol (personal projects i mean)

sour vine
round glacier
#

I understand graphs conceptually. And I can traverse them

#

But I don't know any of the algorithms like Dijsktra's for them

#

So that doesn't mean anything to me when you say that lol

#

Because I lack the knowledge 😄

dapper sapphire
# austere sparrow > -- Why are you testing the knitting skills of your backend development hires? ...

This ^^

Reality is companies haven't really figured out the best way to hire. Big companies FAANG use this DS&A approach, so small and med sized companies are also like, "Hey FAANG uses this method. If it works for them, then it works for us".

A friend has been working for a bank as a software engineer as a contractor for about a year. His boss likes his work and wanted to make him full-time directly through the bank. They still asked him to do the coding assessment hahaha. My friend failed it because he doesnt study DS&A, now he has to wait 6 months to take coding assessment lol.

#

Honestly, in a situation like that, they should just hire the person. The person has already proved their worth to the company.

brazen grail
#

Hi guys! Is there anyway to sort a list on the basis of a particular value in the list?

#

like i have a postinglists of words and i want to sort them by high frequency

dapper sapphire
#

Companies created this DS&A approach to filter people out and hire talented people, which everyone knows.

So hire really talented people through this filtering system. BUT also make it hard for people to leave the current company they are working at. Well, that's a complicated problem. How do you do that??? Simple, change the interview process in such a way that has nothing to do with the work that they will be doing. So the candidate has to spend months or years studying for it.

There's a video about Steve Jobs, how he was infuriated that a Google recruiter emailed an Apple Engineer. Apple Engineer interviewed at Google and took the offer. Google fired that recruiter.

So there was a non verbal agreement among FAANG companies that they wont steal away each other's talent. At least that was the case around that time. Not sure if that's how things still are.

austere sparrow
brazen grail
#

thanks

round glacier
#

im pretty sure that these algorithm questions

#

are easy once u learn the patterns

fiery cosmos
#

@austere sparrow why?

austere sparrow
fiery cosmos
#

Hey can someone possibly help me? I'm posting my question in #help-ramen

storm night
#

How can I keep track of the index of a value in a list if I recurse through the list? To clarify--as I recurse, the sublist is smaller than the original list, so I can't set a variable to keep track of where I am. I'm trying to find the index of a value when I apply binary search to go through a sorted list

shut breach
#

pass the index as an argument?

round glacier
#

It's really annoying how some of these algorithm courses on Udemy are literally just copy pasting stuff from geeksforgeeks.com

#

and geeksforgeeks doesn't cover all edge cases

#

so i get a poorly taught lesson

#

lol...

#

And they don't even follow PEP8 procedures

#

they use camel casing as if it's C++ or something

dapper sapphire
#

So the array/list that stores elements of heapq, do we conventionally name it heap?

import heapq

heap = [] # Do we conventionally name it heap?
heapq.heappush(heap, 5)
heapq.heappush(heap, 10)
austere sparrow
fiery cosmos
#

@round glacier do you think so?

#

@round glacier you think so?

#

@austere sparrow do you think so?

#

@dapper sapphire can you this without using the built-in heap function?

#

@fiery cosmos what is the question?

#

@brazen grail yes, there is a way.

round glacier
#

??

#

why u pinging everyone

round glacier
fiery cosmos
#

@round glacier I know Dijkstra's Algorithm well and several others.

round glacier
#

ok?

#

lol

#

idk why ur telling me that though

storm night
fiery cosmos
#

@round glacier that is the same question I ask myself about all the posts here.

#

I really enjoy writing Algorithms and their big O notation.

#

My favorite two languages are C++ and Q#.

shut breach
storm night
#

cause leetcode asked for it

shut breach
#

but like... what index?

storm night
#

the index of the number I'm trying to search for in a sorted list

# 
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Sorry for not being clear. This is the exact problem I'm trying to tackle

shut breach
#

that way the indices stay the same

storm night
#

I see. Since the provided function is def search(self, nums: List[int], target: int) -> int:

Would it be legal to pass in indexes then? Would I have to make a nested function?

agile sundial
#

you can always make another function

storm night
#

Got it. Thank you! I'm always worried whether I'm cheating myself by making objects outside the main function, etc

fiery cosmos
#

Not at my PC

brazen grail
#

Hi Guys! Hope you are doing great. I am working on a project in python and it's a mini text based search engine which searches through 100,000 articles. I have calculated the inverted index. i.e., against every word I have a list of documents in which it appears along with its frequency and positions in the documents. No I have to rank these documents. If someone is aware of the information retrieval system and can help me regarding this. Please let me know so I can elaborate my problem even further.

#

Basically, I have looked at many ranked retreival models. Vector Space Model, Boolean Model. Probabilistic Model. In vector space model it calculates the term document matrix and then calculates the cosine similarity with the query vector. I am searching on this topic since 2 days. And can't seem to get anywhere. Tonight is the project deadline. Any help regarding this would be really appreciated.

quartz crest
#

What is the time complexity of this algorithm

j = 1
k = 0
while i < n: 
    i *= 2
    k += 1
while j< k:  
    j *= 2
    print(j)```
jolly mortar
quartz crest
jolly mortar
#

the one with the worse complexity

quartz crest
#

I think log(n)

jolly mortar
#

i think so too

#

the second loop is log(log(n))

quartz crest
jolly mortar
#

k is log(n)

#

j is log(k), so log(log(n))

quartz crest
quartz crest
jolly mortar
#

yeah

quartz crest
jolly mortar
#

constants are dropped, so its just O(n)

quartz crest
#

ok

brazen grail
gilded kraken
#

So my socket server stops receiving messages after it gets sent like 6 messages. Is there any idea why this is happening?

austere sparrow
#

There can be lots of reasons.

dawn bridge
#

Whats algos

agile sundial
#

algorithms

lapis ridge
#

i found it 🙂 the a and d channel

eternal imp
#

not sure if this is the right place to ask, but does anyone know a reliable way to get crypto price feeds to perform pandas calculations such as RSI?

round glacier
azure gazelle
#

Is this a good place to ask numpy related questions?

grave crater
fiery cosmos
#

@quartz crest why do you need to know that? I can tell of a great book to learn about Big O notation.

storm night
#

Day 2 of leetcode

is there a more efficient way to learn this apart from grinding away at a block of questions with a related theme? (such as, focusing only on arrays for a few days, then moving onto sliding window problems, etc)

keen hearth
#

It might be more efficient to do readings and watch lecture videos, and then do Leetcode exercises as a supplement to this.

storm night
#

I think I’m all over the place, as one might expect from someone self taught. I did CS50, MITx 6.00.1 and 6.00.2, then gave up when things got tough in 6.00.6 (the algorithms course). I’m supplementing with reading Grokking Algorithms (30 min a day). I’m on track to finish this book by the middle of the month as long as I don’t get stuck for too long.

fiery cosmos
#

@keen hearth excellent and yours?

#

@storm night By more efficient way to learning. You mean can you learning without putting an effort? In short, yes but are you going to be great at it probably not.

#

@storm night Computer Science is not easy my friend.

#

To truly understand many of the concepts of Computer science it takes time and practice but most people do not have the patience and passion to learn things in detail. You see many people use the title of Computer Programmer but they really learned to copy and paste code.

#

I saw that you were doing Big O notation which is very important. Both time complexity and space complexity are super important when interviewing for a job.

storm night
storm night
fiery cosmos
#

@storm night what?

#

I am a professor of Algorithms and Quatum Computing. No problem and good luck.

fiery cosmos
#

And also, I don't understand how the first loop of the script has a time complexity of log(n), if n == 100 and the loop ran 6 times (without error).

Sorry if I seem young and unintelligent, I am relatively young and new to this.

raven kraken
fiery cosmos
raven kraken
#

So Far I wrote this -

if str1 != str2:
            return ""
#

😂

fiery cosmos
#

this is why im not a leetcode dev

fiery cosmos
raven kraken
fiery cosmos
#

'Lowest common string' haha I like this problem

#

im working on it now

raven kraken
#

I came up with this -

  1. First take the common strings
  2. Then check for pattern
  3. Print when the pattern breaks
fiery cosmos
#

i would prefer if str2 in str1 but ok

raven kraken
#

But how can we check for pattern in the string, Like do we have to use sliding window?

fiery cosmos
#

its notabout pattern

#

You start by identifying string simularities in chars

#

then work your way up

#

I want to do this without iterating

#

because of the old saying,

dont iterate. too much time complexity

-creator of stackoverflow

#

ok this isnt a difficlt problem

#

almost there

#

a couple of minutes pls

#

also im not using OOP

raven kraken
fiery cosmos
#

🙂

raven kraken
#

I came up with this -

def gcdOfStrings(self, str1: str, str2: str) -> str:
        
        if str1 != str2:
            return ""
        
        
        ans = ""
        i = 0
        while i < len(str1):
            if str1[i] in ans:
                break
            ans += str1[i]
            
            i += 1
            
            
                
        return ans
#

Its not passing even a single case, what could be wrong in this?

#

It is returning an empty string

#

Ohh got it

fiery cosmos
#

did u pass?

raven kraken
#

In this question the logic is correct I am only getting error at the first if condition

#

str1 != str2

fiery cosmos
#

ye

raven kraken
#

Its is failing when str1 = "LEET" , str2 = "CODE"

fiery cosmos
#

wait 1 sec

fiery cosmos
#

i dont think that script is fully functional

#

it is a O(n)

raven kraken
raven kraken
# fiery cosmos it is a O(n)

I think it should be O(N ^ N), since we are iterating once using while loop and then looping again in ans with if str1[i] in ans:

fiery cosmos
#

true

#

I'm a bit of a slow scripter mainly preparing for google kickstart.

#

I have this so far

#

This is supposed to increase run time

# 
def repStr(string):
    a=list(map(string.count,[x for x in string]))
    if len(set(a)) == 1:
        return a[0]
    else:
        return 'ILLEGAL'
def divisorOfStrings(str1,str2):
    bruh = [repStr(str1),repstr(str2)]
    
    ```
#

supposed to check the amount of repetitive loops

#

and after that, the main for loop can just use the returned data to calculate the answer, as not to use an O(n squared) solution

raven kraken
#

I looked up for solution and found this -

def gcdOfStrings(self, str1: str, str2: str) -> str:
        
        str1Length, str2Length = len(str1), len(str2)
        
        if str2Length > str1Length: 
            return self.gcdOfStrings(str2, str1)
        
        if str1[:str2Length] == str2: 
        
            if str1Length == str2Length: 
                return str2
            
            return self.gcdOfStrings(str2, str1[str2Length:]) 

        return ""
fiery cosmos
#

oh crap

#

thats a good solutiom

#

but too many if statements

raven kraken
fiery cosmos
#

I dont usually use leet

#

I wanted to know

#

How many test cases are there for every problem in leetcode

pearl orchid
#

Hi

fiery cosmos
#

Who are you

pearl orchid
#

Just wanted to join any DS-ALGO community

raven kraken
fiery cosmos
#

grinding medium and hard

quartz crest
quartz crest
quartz crest
fiery cosmos
#

the first loop

#

dude

#

im doing an assessment in leetcode

#

2 problems

#

the first one i passed

#

the second one is scuffed

#

look

#

explain

glossy breach
#

your algorithm is wrong

#

so like

#

if name is "abcd" and typed is "dcba" for example

#

dcba cant possibly be the long pressed version of abcd

fiery cosmos
#

Thank you

#

I realised at the time that my main error (resulting in the output to play up) was my returned value was 'true' or 'false' instead of the Bools True and False. Silly me.

#

But I had only 3 fucking minutes by the time I realised that

#

so ggwp now I only got like 70-80 out of the 94 test cases

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:1641201530:f> (9 minutes and 59 seconds) (reason: duplicates rule: sent 4 duplicated messages in 10s).

candid osprey
#

!unmute 883321240788557874

halcyon plankBOT
#

:incoming_envelope: :ok_hand: pardoned infraction mute for @fiery cosmos.

fiery cosmos
#

sorry

candid osprey
#

!paste

halcyon plankBOT
#

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

candid osprey
#

All g, try that

fiery cosmos
#

thanks

#

🙂

#

Guy guys

#

Can anyone give me any detail on how to improve my Chess Coordinates basic project?

#

I made this for a clash of CodinGame

#

But it was heavily criticised and disliked. I want some guidance on how to improve my code (Is written on a my 3.9.7 IDE)

cedar summit
#

The many indentation layers make it hard to read. Using guard clauses might help. E.g., instead of

if a[0].isupper() and a[0] in pieces:
    ... #rest of nested code
else:
    print('Illegal')

you could rewrite this as

if not (a[0].isupper() and a[0] in pieces):
    print('Illegal')
    return
... #rest of code
hexed ravine
#

hey can someone help me out with this question?

unknown.png
fiery cosmos
#

Interesting question.

#

Well, there has to be 2 jars between each divider

#

Otherwise the first requirement of having an equal number of even and odd jars in each group won't hold

#

(Having a single jar of even or odd, means there are 0 of the other)

#

So I guess what you need to do is divide the jars into evens and odds and order them by number of candies

#

So you have E_1 E_2 E_3 ... E_n | O_1 O_2 O_3 .... O_n

#

Now I think the most dividers you can place is by doing E_1 + O_1, E_2 + O_2, etc

#

And the number of dividers is M >= abs(E_1 - O_1) + abs( E_2 - O_2) + ...

#

Honestly, I'm curious to know what the answer is. Cause I think this is too naive

prime heath
prime heath
#

no scratch that. it can also be abs(e1-e2) or abs(o1-o2)

fiery cosmos
#

I feel like this may be a dp problem.

novel ermine
#

Does anyone know about a library or algorithm for re-arranging items in a list in an optimal order according to a cost function?
I wrote an interesting algorithm for that and before I make it public I want to see how it compares with other methods

fiery cosmos
fiery cosmos
#

You can pass method in key.

#

Which would be a cost function yeah.

#

.sort(key=mymethod)
mymethod(ele) -> returns cost

novel ermine
#

not exactly, a use case for my algo would be arranging manufacturing steps in an optimal order, to do that the cost (or score) of the entire list order must be evaluated at the same time

fiery cosmos
#

I can't see the difference yet. It's sorting.

novel ermine
#

the key argument in .sort() only is a function that converts each member of the list to a simplified form (for example an int) so they can be sorted correctly

fiery cosmos
#

Also to clear confusion an example would help.

#

Also shakshuka is a kind of soup right?

#

Or egg dish i think

novel ermine
#

no because my cost function takes the entire list as an argument. but key function only runs on each member of the list once before sorting

#

key=str.lower is an example

fiery cosmos
#

Great. An example of what your method does would help.

novel ermine
#

and yes it is (: my favorite meal

fiery cosmos
novel ermine
#

here is an example for a cost function im using in testing:

#

def cost_func(lst1):
e = 0
for i in range(len(lst1) - 1):
e += abs(i + 1 - lst1[i])
return e

#

it evaluates a list of integers and gives it a lower score if they are perfectly sorted and higher if they aren't

austere sparrow
#

there isn't a general way to minimize a general function

novel ermine
#

well, as far as i can see i wrote one, as long as you can describe your problem by ordering members of a list and have a cost function to evaluate that order i can solve it

fiery cosmos
#

So yeah you don't even need sorting. My bad.

novel ermine
#

it solves problems like the traveling sales man

austere sparrow
#

maybe you can share the algorithm? 🙂

novel ermine
#

I am planning to release it in Medium article soon, it is called Simulated annealing optimization

#

This optimization module simulates the natural process
of annealing. In short, the solver tries different
solutions, if a solution is an improvement the solution is accepted. If a solution is not an improvement, it has a
semi-random chance to be accepted anyways. This chance is smaller the further we are into the solving process.

shut breach
#

what does your transformation function look like?

novel ermine
#

i am using a few, such as swapping random members or slices, shuffling slices, reversing slices and so on. in general, the bigger the change, the less likely it is to occur

shut breach
#

the bigger the change, or the higher the cost delta of the change?

merry scroll
#

Please help me:
Sorry I used Google Translate

865551884861702165.png
#

And please ping me when you help

novel ermine
shut breach
novel ermine
#

no, they can be whatever. i just used the range(n) for testing. my algo doesnt touch the elements themselves, only their position in the array

shut breach
#

lst[i] is the element itself

#

so your elements need to have defined subtraction with integers

novel ermine
# shut breach `lst[i]` is the element itself

yes that is the cost function, not my algorithm. when you use my algo you provide the cost or evaluation function that takes the current order of the list and evaluates it

my algo can for example compete with this: https://towardsdatascience.com/solving-travelling-salesperson-problems-with-python-5de7e883d847

Medium
Solving Travelling Salesperson Problems with Python

How to use randomized optimization algorithms to solve travelling salesperson problems with Python’s mlrose package

shut breach
#

to answer your original question, no I don't know of any existing libraries that do simulated annealing list sorting

novel ermine
shut breach
#

unlikely, we already have very good algorithms for solving list sorting

novel ermine
#

ok thanks

merry scroll
shut breach
merry scroll
#

How?

#

Sorry I'm so bad at algorithms

#

@shut breach

shut breach
#

try it out, how would you solve W(5) yourself?

merry scroll
#

I can't, I tried, but it didn't work

#

please @shut breach, explain the algo

agile sundial
#

the idea is to use previously calculated answers

#

if you know how many ways there are to balance with m=1 and m=2, you can add those together to balance m=3

merry scroll
#

That is it?

#

So with n = 4 and m = 2 we will have 7 ways to weigh the object:

([],[2]),([1],[3]),([2],[4]),([2],[1,3]),([3],[1,4]),([4],[1,2,3]),([1,3],[2,4])
````([right side],[left side]); right side + m == left side`
wild harness
#

any can helpme whit this error? pls

unknown.png
merry scroll
merry scroll
#

@shut breach @agile sundial ?

marsh abyss
#

.

#

.

merry scroll
#

Hey guys?

#

Help

fiery cosmos
#

@wild harness did you figure it out?

#

@merry scroll help with what?

merry scroll
#

Look up there

fiery cosmos
#

Who are you saying that to?

#

@merry scroll you do not reply to a thread.

lapis ridge
#

anyone want to vc and go over some leet code? i stlll have yet to solve one. idk what my problem is because i know coding. just these problems don't make sense to me. maybe i'm dislexia

young ice
#

Hi
What are best resources to learn data structures and algo in python from scratch?

#

Im going through campus placements

fiery cosmos
#

@lapis ridge this is because most people learn to code by copying and pasting other code, and have no background in computer science principles.

young ice
#

Im really stressed about my career. pls give some suggestions. TIA

fiery cosmos
#

@young ice I can recommend you some great books that dive deep into these topics.

young ice
fiery cosmos
#

@young ice are you in the USA?

young ice
#

no.. Im from India

fiery cosmos
#

@young ice I ask because in the USA most books you can get for free via libraries.

young ice
#

Im ready to buy the book

fiery cosmos
#

@young ice have you worked with pandas?

young ice
#

yes

#

I interned at Genpact as jr data scientist in time series forecasting

#

but ive no experience in DSA

wild harness
lapis ridge
fiery cosmos
#

@lapis ridge good for you

bitter wigeon
shut breach
#

@fiery cosmos please treat other community members with respect

fiery cosmos
#

@bitter wigeon I am not trying to be an ass but most people that ask for help come to me with a blank assignment no code, no effort and not even trying to read to learn.

bitter wigeon
#

In the past we had to sometimes hunt the code in books or magazines like Dr. Dobbs and read the article , understand the concepts then manually type the code we need from the code listings

#

Then debug said code

fiery cosmos
bitter wigeon
#

True and nobody is .. what matters more are intentions and it seems well placed. The people we help should learn first to help themselves

round glacier
#

There's a specific data structure which CS GO uses for path finding. I forgot the name of it though and can't find it anymore. Does anyone know the name of a datstructure which does this?

#

It's not just a regular graph i believe

bitter wigeon
#

It is a shortest path algo ...probably A * it uses graphs

vocal gorge
round glacier
#

That might be it

#

but i think theres another one

bitter wigeon
#

You can try several path finding algos to see what works best in your problsm space

#

Algorithms used in pathfinding

Dijkstra's algorithm

A* search algorithm, a special case of the Dijkstra's algorithm

D* a family of incremental heuristic search algorithms for problems in which constraints vary over time or are not completely known when the agent first plans its path

Any-angle path planning algorithms, a family of algorithms for planning paths that are not restricted to move along the edges in the search graph, designed to be able to take on any angle and thus find shorter and straighter paths

vocal gorge
bitter wigeon
#

pip install binarytree

woeful linden
#

for path searching algos like dijkstras and A* is it better to implement it iteratively? id imagine recursive implementations will encouter lots of overflow errors

vocal gorge
#

yeah, you'd probably run out of stack space. Though I can't think offhand how to implement them recursively in the first place, I've always done them iteratively. Like, there's a natural while !open_set.is_empty(){ loop involved.

fiery cosmos
#

@bitter wigeon this is a great resource but not perfect.

#

@bitter wigeon it is a simple guide for beginners with no experience and no previous knowledge of binary tree and nodes.

vocal gorge
#

You'd normally do something like

@dataclass
class Node:
    val: int # or whatever type you're storing
    left: Optional[Node] # that means Node | None
    right: Optional[Node]
#

I've seen many a binary tree implementation like that in this channel, actually

austere sparrow
#

that doesn't support an empty binary tree, though

#

you do need a wrapper for empty trees

vocal gorge
#

ah yeah, fair enough. It's less of a problem than for LinkedLists, but you can indeed do a

@dataclass
class Tree:
    root: Optional[Node]
austere sparrow
#

or you could have Tree = Optional[tuple[Element, "Tree", "Tree"]]

#

and then just have free functions operating on trees

#

although... I'm not sure how useful an immutable binary tree is 🙂

vocal gorge
#

this isn't haskell :P

#

I personally find it weird if Optional is included in the very definition of a type

#

like, it'd be weirded out if I did Optional[Tree] and pyright said "hey, Tree is already possibly None"

storm granite
#

Do you need algos and data structures for django

fiery cosmos
austere sparrow
#

that's pseudocode 🙂

vocal gorge
#

hmm, is there a way to do, like

#

in Rust:

type Tree<T> = Option<(T, Tree<T>, Tree<T>)>; // let's not think about sizes

declares a type generic by a parameter. In Python you can do that with classes, inheriting from Generic, but can you do it like this?

austere sparrow
#

where T is a TypeVar

vocal gorge
#

yeah, but that's not... hmm

austere sparrow
#

that's how you make generic type aliases 🙂

vocal gorge
#

but Tree isn't subscriptable then

#

you can't specify a Tree[int]

austere sparrow
vocal gorge
#

I can indeed

#

is this some typevar magic? It propagates subscriptability?

austere sparrow
#

typing is a big magic hack tbh

vocal gorge
#

well apparently Tree[int] is a typing.Union[typing.Tuple[int, ForwardRef('Tree'), ForwardRef('Tree')], NoneType]

#

ForwardRef 😰

#

and Tree is typing.Union[typing.Tuple[~T, ForwardRef('Tree'), ForwardRef('Tree')], NoneType]

#

actually, hmm

# 
>>> Tree.__parameters__
(~T,)
#

so indeed it propagates parameters upwards somehow

fiery cosmos
#

@vocal gorge how about a N-ary Tree.

raven kraken
#

Find max 10 numbers in a list having 10M entries.

#

I had one doubt with this question, I am thinking of solving it with a maxheap in python. Time complexity should be O(logn) but what about the space complexity

#

If I will heapify a list with 10M entries would it be efficient?

jolly mortar
#

yeah, heapify is an O(n) operation

raven kraken
jolly mortar
#

yes, O(n) space too

raven kraken
jolly mortar
#

actually, O(1) extra space

raven kraken
jolly mortar
#

you can heapify the input list in-place, you don't need another list
so there's no extra space needed

raven kraken
jolly mortar
#

yeah i believe only extra space is considered for SC

raven kraken
#

Can you think of any more efficient solution better than using heap?

jolly mortar
raven kraken
jolly mortar