algos-and-data-structs

[fiery cosmos]

hey, I'm trying to learn data structures and algos on my own and am having trouble with some big o problems, can one of you guys help me

[last fulcrum]

Thanks for the info guys

[knotty magnet]

not if you don't be more specific and provide a specific problem

[fiery cosmos]

yes, I can send the problem, I just wanted to ask if it's appropriate to ask that in here

[knotty magnet]

it is

[fiery cosmos]

what is the big o complexity of this

[knotty magnet]

what do you think

[fiery cosmos]

Well I thought it was linear

[knotty magnet]

why?

[spring jasper]

Unrelated but dont use builtin func names as variables

[fervent saddle]

It’s linear, but I notice that the inner loop doesn’t run, and actually nothing at all happens, unless i is under 25. If n is supposed to always be under 25, the whole thing is constant.

Otherwise you’re right, it’s linear with the size of n

[fiery cosmos]

yeah I think it's as n goes to infinity

[vocal gorge]

constant? the opposite, for low n it scales like n^2.
or wait

[fiery cosmos]

not just before 25

[vocal gorge]

for low n the runtime is (25-0) + (25-1) + ... + (25-n), which is (50-n)*n/2 or so

so it's increasing, but, uhh, in a complicated way (parabola angled down). Can be bounded by a linear function for low n, too.

so basically it's all linear-ish.

[fervent saddle]

If n has a maximum value, the whole algorithm becomes constant, right? Isn’t that how it works?

That’s where that one joke comes from, that linear searching through an array is O(1) because all computers have a limited amount of RAM

[vocal gorge]

ooh, that's what you meant - yeah, sure

[runic tinsel]

it's linear cuz python certainly will take linear time to go through that loop

[fiery cosmos]

I mean, it wouldn't be constant

since it would still have to run through the first loop

it just wouldn't execute the second loop

[runic tinsel]

but like philosophically it's constant because your imaginary computer won't bother

[fervent saddle]

Yeah it’s linear

If n can be any number then it’s linear because of what you said

[fiery cosmos]

ok

and this one would just be n^2 right

[runic tinsel]

of course

what's after line 3 is constant then linear, which simplifies to linear, and it's in a loop

[fervent saddle]

So you’re only worrying about n in these, and k is assumed to be some constant that can be ignored?

[runic tinsel]

a known constant

we can see it's 0

[fervent saddle]

Ok, because otherwise it would be like O(n * (n - k)), right?

[runic tinsel]

yeah i suppose

[fiery cosmos]

for this one, I said it was log_k(n)

[spring jasper]

!rule 6 this isnt a place to advertise

[halcyon plank]

Rules

6. Do not post unapproved advertising.

[runic tinsel]

i'm certain it is

that it is log_k(n)

[fiery cosmos]

this one is the one I'm most uncertain of

I don't even know when to start

[fervent saddle]

I think it’s O(n**4)

The inner loop is O(n**3), the outer loop is O(n)

So it’s O(n * n**3) which is O(n**4)

[turbid laurel]

Hey guys, I need to get some information on Python data structures

I have a dataset that's a table with strings and floats

which I believe translates into a 2d dict, or a dict of dicts

but I'm struggling to understand the key

if I have a dict that uses strings for its keys

can I iterate through it using a for loop?

[knotty magnet]

sure

[minor onyx]

hey guys, can someone help me in help-ramen?

[fiery cosmos]

what's the dp solution to this?

I think I have one in my head but I'm not sure how to account for the blocks you can't travel to

ah I guess the grid representations would be something like chars "+" where you could go, and "-" where you cant go and if it's a "-" then you don't count it

def countPaths(grid, row, col):
  dp[row - 1][col] = 1
  dp[row][col - 1] = 1
  for r in range(row):
    for c in range(col):
      if dp[r - 1][c] == "+" and dp[r][c - 1] == "+":
        dp[r][c] = dp[r - 1][col] + dp[r][c - 1]
      elif dp[r - 1][c] == "+":
        dp[r][c] = dp[r - 1][col]
      elif dp[r][c - 1]:
        dp[r][c] = dp[r][c - 1]
      else:
        continue

that's my guess of what the code should be, can someone please check ?
I can't actually run it since this is just from a YouTube video and I'm just trying to learn DP fundementals

[dapper sapphire]

So when we convert a number to binary, what is the Ob in the beginning?:

!e

number = 42
binary = bin(number)
print(binary)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

0b101010

[dreamy phoenix]

0b indicates that it's a binary number

[dapper sapphire]

Oh hahahahaha

[dreamy phoenix]

another example is 0x which means hex

[dapper sapphire]

Yeah, I was like wait is it supposed to be hex.

Thanks!!!

[dreamy phoenix]

nw

[dapper sapphire]

Is Ob to denote something is binary just limited to python, or does it also apply to other languages?

[dreamy phoenix]

other languages use this notation too

for example

[dapper sapphire]

Got it!

[worldly osprey]

any suggestions for me who is beginning with data structures and algorithms? like where to begin with etc

[wheat plover]

can you "waste" first few values of an iterator without using a for loop? Say I have an iterator but I don't need first 5 values. The iterator has been already initiated so I can not initialize the iterator myself.

[half lotus]

An iterator is really basic - all you can do is call next() on it. So with that in mind, I don't see any mechanism to skip items besides calling next() a bunch of times.

Or using a loop, which implicitly does that

[wheat plover]

Okay, thanks

[half lotus]

Maybe there's something in the pins that can help you get started.

[worldly osprey]

oh ok didnt realise thanks

[loud lance]

Hi guys, I need help with homework:(( I just dont understand what its asking:

Binary relationships as matrices

A matrix can be used to represent a relationship between two sets A and B. This representation is as follows: If A = {X₀,X₁,X₂,...,Xₙ_₁} and B = {Y₀,Y₁,Y₂,.... ,Yₘ_₁} a relation R of A in B is represented by a ones and zeros matrix of size nxm, where Aᵢⱼ = 1 if element xᵢ is related to element yⱼ, otherwise Aᵢⱼ = 0.

Using this representation make a program that allows the user to read two relations between two sets and choose from a menu one of the following operations on those relations:

Union: calculate and print the union relation.
Intersection: Calculate and print the intersection relation.
Symmetry: Determines whether the first relation is symmetric or not.
Reflexivity: Determines if the first relation is reflexive or not.
Transitivity: Determines whether the first relation read is transitive or not.
Order: Determines whether the first relation read is an order relation or not.
Equivalence: Determines whether the first relation read is an equivalence relation.
Function: Determines whether the relation is a function or not.
Injectivity: Determines if the relation is an injective function.
Overjectivity: Determines if the relation is an overjective function.
Exit: Allows the user to exit the program

After the operation has been performed, the menu must be displayed again until the user wants to exit.

I really don't know what to do and I would be very grateful if someone could share with me some material or guide me in this matter, thank you very much in advanced

[worldly osprey]

well im not stuck, i havent started yet, i was asking tips for like where to begin etc, didnt realise that there was content in the pins

[fiery cosmos]

wait, thats your 2nd acc?

oh freak i replied on wrong msg, nvm.

[fiery cosmos]

i can give you small helps if you want, so where exactly are you stuck?

[fiery cosmos]

i personally started with searching algos on list, then watching various data structures like trees, BST, sorting algos, heaps and graphs.

[worldly osprey]

ah ok hahah

yea im planning on following the mit open course ware algorithms course

[fiery cosmos]

as we kinda start implementing each of these, we eventually get to used our languages too well, like if im implementing BST in lets say python, i can use classes to make a BST node, I can use recursion for traversals, and logic building will also be nice as removing node is a nice deal in BST.

[halcyon plank]

Hey @digital plank!

It looks like you tried to attach file type(s) that we do not allow (.ipynb). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a.

Feel free to ask in #community-meta if you think this is a mistake.

[digital plank]

I am following this tutorial

https://www.kaggle.com/somaktukai/credit-card-default-model-comparison/notebook#Classification-of-Taiwan-Credit-Card-Payment-Default-Prediction

And when I run it, I changed what classifiers to use and my code only does knn any tips on fixing this?

[keen hearth]

You'll probably get better responses in #data-science-and-ml

[worldly osprey]

can anyone help me implement a basic binary search algorithm which finds the peak in a 1D array? i have written a code till this but i cant figure out where im going wrong

from random import randrange
from typing import List

# Takes in an 1D array and returns its peak if it exists, using the binary search algorithm
def binary_search(array: List[int]) ->  int:
    print(array)

    if len(array) == 1:
        return array[0]

    left_num = array[(len(array)//2) - 1]
    right_num = array[(len(array)//2) + 1]
    middle_num = array[len(array)//2]

    print(left_num, middle_num, right_num)

    if left_num >= middle_num and left_num >= right_num:
        print('ran left', array[len(array)//2 - 1])
        binary_search(array[0 : len(array)//2])

    elif right_num >= middle_num and right_num >= left_num:
        print('ran right', array[len(array)//2 + 1])
        binary_search(array[len(array)//2 : -1])

    else:
        return middle_num

rando_list = [randrange(0, 10) for _ in range(10)]
print(binary_search(rando_list))

[cerulean flare]

I'll try to help

[rain valve]

I am a bit unsure about what the most pythonic/recommended data structure would be to handle large amounts of json data following a defined Schema.

Basically i need to create instances on request based on standardized objects in a large json DB.
Normally i would use the dataclass module to store the information but since the objects have multiple layers (up to 6) i would need to rely on some kind of a nesting extension and this gets kinda messy and is a pain to initialise.

The other way i thought about was using types.SimpleNamespace to load the json with a objecthook to create namespaces for each layer. (https://docs.python.org/3/library/types.html#types.SimpleNamespace)

Maybe there are other options i completely overlooked?

[worldly osprey]

thanks, tbh im not sure where i went wrong with the algorithm or its implementation

[vocal gorge]

i would need to rely on some kind of a nesting extension and this gets kinda messy and is a pain to initialise.
I mostly used that route, using dataclass-factory or pydantic for the nested records.

[worldly osprey]

ok so i think im thinking about the finding peak if it exists problem wrong, according to the MIT introduction to algorithms course, the pseudo code will be

• If a[n/2] < a[n/2 − 1] then only look at left half 1 . . . n/2 − − − 1 to look for peak
• Else if a[n/2] < a[n/2 + 1] then only look at right half n/2 + 1 . . . n to look for peak
• Else n/2 position is a peak:

but, then that only checks the side two numbers, what if the array is [9, 0, 2, 5, 8, 3, 1] where n/2 = 5 , the algorithm then will look at the right stack, while the greatest number in in the left stack

so what is the algorithm really doing?

[vocal gorge]

The definition of the peak it finds is a number that's higher-or-equal to its neighbours (one neighbour if it's an edge element), so 8 is a correct answer - there's simply two peaks in this array

it's not possible to find the global maximum of an array quickly

[worldly osprey]

oh so the peak can be thought of like the peak of a mountain in a mountain range where multiple peaks exist?

[vocal gorge]

yeah, sure

you can't find the highest one of them any quicker than O(n)

[worldly osprey]

oh, because it has to iterate through the list atleast once?

[vocal gorge]

Yeah, pretty much - in a general list, there's no way to "detect" a big element by looking at other ones, so you need to scan the entire list and pick the highest (so, pretty much, the max function).

but for finding an arbitrary peak (local maximum), it turns out there's an O(log n) way - this algorithm.

[worldly osprey]

ohhhh got it, thanks a lot!

[spring jasper]

is there a "canonical" way of checking if two strings are anagrams

[steady mortar]

I found this https://web.stanford.edu/class/cs9/sample_probs/Anagrams.pdf

[knotty magnet]

what does canonical mean in this caes

[somber dirge]

hi

can anyone recommend my a DSA course please

[spring jasper]

pythonic, i guess

my solution looks too much like cpp and i dont like it lmao

[knotty magnet]

show code?

[spring jasper]

def anagram(first, second):
    first = [letter for letter in first.lower() if letter.isalpha()]
    second = [letter for letter in second.lower() if letter.isalpha()]

    if len(first) != len(second):
        return False

    d = {letter: 0 for letter in first}
    for letter in first:
        d[letter] += 1
    for letter in second:
        d[letter] -= 1
    for val in d.values():
        if val != 0:
            return False
    return True

i guess i could use Counter instead

[knotty magnet]

yeah

[jolly mortar]

a fun solution i'd seen was mapping each letter to a distinct prime number, and comparing the products of the two strings

[keen hearth]

Funnily enough, the canonical way to do this is to convert each of them to a canonical form. For anagrams, you could sort the letters.

def canonical(string):
    return ''.join(sorted(string))

def is_anagram(string1, string2):
    return canonical(string1) == canonical(string2)

[spring jasper]

Thats what i was debating tbh, the sorted lists approach looks much better and reads much better than a dict implementation

[vocal gorge]

eww, n log n

[spring jasper]

But that O(nlogn)

This was for an interview task, i wasnt sure if i should go for the faster approach or the most readable

[keen hearth]

Well, where the n is the length of the strings. But if you have a large number of short strings, this approach may be preferable.

For example, if you need to build a dictionary of anagrams: ```py
anagrams = defaultdict(set)
for word in wordset:
anagrams[canonical(word)].add(word)

Then you can get all the anagrams of a given word in O(1) (kind-of 👀 )

[vocal gorge]

one could use an array of counts as the key

...no, that's bigger than the string in most cases.

[fiery cosmos]

I think the O(N) way with the Counter is fine and just as elegant

!e ```py
from collections import Counter

def clean(word): # .isalpha includes more than a-z which may or may not be desired
return [c.lower() for c in word if c.isalpha()]

def anagrams(w1, w2):
return Counter(clean(w1)) == Counter(clean(w2))

print(anagrams("Astronomer", "Moon Starer"))
print(anagrams("aaa", "aa"))
print(anagrams("a fool", "aloof"))```

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | False
003 | True

[fiery cosmos]

!e And you can make your own counter function easy enough ```py
def my_counter(word):
counts = {}
for c in word:
if c not in counts:
counts[c] = 0
counts[c] += 1
return counts

print(my_counter("ABCDD") == my_counter("DABDC"))

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

True

[dapper sapphire]

Does it matter if you are doing dynamic problems using recursion or with for/while loop?

[vocal gorge]

well, the former may result in hitting the recursion limit (and that's if you're doing memoization - if you aren't, it's usually just a horrible idea and won't result in an acceptable complexity) on big problems (>10000 elements)

[dapper sapphire]

ok I see. Thanks.

And memoization is when we store results so we dont have to do computation again for the same numbers?

[grizzled schooner]

yeah

[rain valve]

Thanks alot btw. I found a cool module: dacite which does everything I need without to many extra features.

[covert prairie]

Not sure if this is the proper channel to ask... I'm using Postgres with CUBE_MAX_DIM set to 128, but it turns out my array is a 2622 dimensional vector. Is this safe? Will I see performance issues? In terms of comparison distances between arrays(using Euclidean distance)? The DB will contain 100+ Million of these records.

[minor cedar]

hey guys who uses LeetCode and he is a beginner ?? maybe we can be partners and try to help each others im GMT+1 timezone

[honest night]

#algos-and-data-structs

[coarse folio]

any reason why its only returning the first value?

the actual list looks like this [b'...', b'...', b'...']

[fiery cosmos]

Is there a way to generate a random sorted list but do it in O(N)?

i.e. a function equivalent to this but more efficient py from random import randint def randomsortedlist(length=5, minimum=1, maximum=10): lst = [randint(minimum, maximum) for _ in range(length)] lst.sort() return lst

[knotty magnet]

a random sorted list?

like, random numbers, but sorted order?

[fiery cosmos]

yeah

[wide lake]

for i in range(0,10,2):
priint(i)
guys what is the time complexity for this
is it O(logn)?

[fiery cosmos]

No. O(N) (assuming the 10 could be any number N). Because you print every other number from 0 to N

or about N/2 numbers, which boils down to linear O(N)

[wide lake]

thanks

can u recommend any videos ,books or articles to study time complexity

[fiery cosmos]

I like the MIT Open Courseware CS classes - they have several specifically about algorithms https://ocw.mit.edu/courses/find-by-topic/#cat=engineering&subcat=computerscience&spec=algorithmsanddatastructures (all on YT as well)

But might be a bit advanced to start off with

[wide lake]

👍

[vital crescent]

How might i invert a KD tree to find the point that maximises the distance to the nearest neighbour

[vocal gorge]

sure, just each time generate a number equal to or higher than the last one.

from random import randint
def randomsortedlist(length=5, minimum=1, maximum=10):
    lst = []
    cur_min = minimum
    for _i in range(length):
        el = randint(cur_min, maximum)
        cur_min = el
        lst.append(el)
    return lst

though this results in a significantly different distribution of values than the solution you had, probably

[fiery cosmos]

Right. I though of that but the distribution is way different, yeah

[vocal gorge]

hmm

oh, yeah, yikes, that's a completely different distrib

[vocal gorge]

@fiery cosmos I think this is the distribution of the list's elements by index:

from math import comb,factorial
def cdf(length:int, index:int, minimum:int, maximum:int):
    """Returns the CDF - a function P(x) = P(theta<=x)"""
    return lambda x: (x-minimum+1)/(maximum-minimum+1)
def pdf(length:int, index:int, minimum:int, maximum:int):
    return lambda x: 1/(maximum-minimum+1)
def order_prob(length:int, i:int, minimum:int, maximum:int):
    """Returns the PDF for the ith(0<=i<length) smallest element of the list"""
    _cdf = cdf(length,i,minimum,maximum)
    _pdf = pdf(length,i,minimum,maximum)
    def fun(x):
        val = _cdf(x)
        return val**i * (1-val)**(length-i-1) * _pdf(x) * coeff(length,i)
    return fun

def coeff(n,i):
    return factorial(n)//(factorial(i)*factorial(n-i-1))

The order_prob here (obtained by the order statistic formulas). The means, calculated via:

def find_mean(fun,minimum,maximum):
    lst = [fun(x)*x for x in range(minimum,maximum+1)]
    return np.sum(lst)

seems to perfectly match the ones from your first function

perhaps knowing the distribution of the elements, one can sample them quickly

not totally obvious to me how, though

[fiery cosmos]

Statistics

[vocal gorge]

indeed

[whole plover]

as matter of fact, this --> does something?

[vocal gorge]

like, def f(n:int) -> float:? the -> here is the return type typehint.

[whole plover]

out my scope of understanding

[vocal gorge]

essentially, it's just documentation on what the types of all arugments and the return type of the function are.

they are also used by IDEs for autocompletion.

[whole plover]

that's why arguments should be lowercase?

[knotty magnet]

that's not really related

[ruby bough]

@mellow wyvern

[minor onyx]

hey guys. One little doubt. If I implement B-tree in different forms, can I get different results for a B-tree? Or the B-tree is always the same and doesn't matter how I implement?

Sorry for doesn't call in help chat. I mean this question this quite quickly for this.

[trim galleon]

Write a MIPS code to store the word in a REVERSE manner in the array myRevName. For reversing purposes, you need to use the STACK. The necessary C code is provided below.

• base register of array myName is stored in Ss0 register

• base register of array myRevName is stored in Ss1 register

• variable strLength is stored in Ss2

• For loop counters i and J. you have to use Sto and St1 register respectively

The C code:

for (i=0; i<strLength; i++)

PUSH myName[] into Stack

}

for (j=0; j<strLength: j++)

POP from Stack and store the popped element into myRevName[j]

}

Anyone can solve this?¿???????????

[vernal garnet]

can someone suggest me some good resources to learn Data Structures and Algo's in Python!

[old rover]

check what's pinned

i liked the one pinned w my username

and it's always good to brush up on OOP

just a quick refresh

bc it's literally in all data structures

in fact i would really stress it

[chrome void]

**n=int(input())
k=int(input())
ls=[]
for i in range(1,n+1):
ls.append(i)
ls1=list(cmb(ls,k))

cou=0
for i in ls1:
temp= True
for j in range(1,len(i)):
if i[j]%i[j-1]!=0:
temp = temp and False
if temp==True:
cou=cou+1

print(cou)**

Any better solution to this?

[muted canyon]

i think this can be broke down into formula

1+k*(number of primes between [1,n])+

[runic tinsel]

so many steps

[chrome void]

am learning😅

[muted canyon]

1+k*(n-1)+(number of factors for every i from [2,n] excluding 1 and i)

idk if this works, need to implement

[chrome void]

am trying

btw how do you come up with these

how do i?

[muted canyon]

just try for some inputs and write down outputs, check for the pattern

before jumping into code, solve in paper

[chrome void]

Thats helpful thank you !! ✌️

[muted canyon]

is there any link to submit this?

[chrome void]

No I got a pdf as sample questions

if you want i can send it here

[muted canyon]

yes pls

[halcyon plank]

Hey @chrome void!

It looks like you tried to attach file type(s) that we do not allow (.pdf). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a.

Feel free to ask in #community-meta if you think this is a mistake.

[runic tinsel]

I meant my idea

[muted canyon]

dm,

[main flower]

Well, what I can think of is some dynamic programming like: dp[i][j] means number of arrays of length j which end with number i

[runic tinsel]

i also think it has to be dp

[main flower]

Yeah

[runic tinsel]

hm

[muted canyon]

well, i need to start dp, idk more about that

[chrome void]

I am learning dp too, I thought the solution would be dp too

[runic tinsel]

what's the max N anyway?

[chrome void]

Thats the total info there is

[runic tinsel]

oh

[muted canyon]

not mentioned

[chrome void]

But ig they are telling us to print modulo 10k

so it should be large

[runic tinsel]

i like Witcher's idea

so at the start it looks like

         last number
length   1 1 1 1 1 1 1 1 1 1
         

if the array ends in 4 it's the largest prefix of any array that ends in a number divisible by 4

so like

         last number
length   1 1 1 1 1 1 1 1 1 1
               1       1
```the fourth 1 gets added to those 2 cells

like a sieve

[chrome void]

I am sorry i am trying to understand, but its difficult for me

[runic tinsel]

i'm just thinking aloud

[chrome void]

If you code it, send if possible

[runic tinsel]

!e

N = 38
K = 91

arr = [1]*N

for _ in range(K-1):
   for c in range(N)[::-1]:
       for c2 in range(c+c+1,N,c+1):
           arr[c2] += arr[c]



print(sum(arr))

[halcyon plank]

@runic tinsel :white_check_mark: Your eval job has completed with return code 0.

92962871

[runic tinsel]

that's that

no idea if it's correct lol

if correct, it may be slower than required

wish i could test it but i can't google this problem

https://www.geeksforgeeks.org/count-sequences-of-length-k-having-each-term-divisible-by-its-preceding-term/

yeah that one also gives 92962871

you start with a 2d array with K rows N cols, with first row initialized to 1, because we know that length 1 arrays are 1 per ending

the rest are 0
then you iterate through first row and add the number to all cells one row lower that are divisible by this ending
you can only make an array that ends in Y by taking a shorter array that ends in X where Y is divisible by X and adding Y

then you do it for the next row

until the last one, and add up last row

since you go row by row it can be done inside one array, you gradually convert it into next row

nice one witcher

[upbeat charm]

A university is receiving applications from students to register for language courses offered in six different languages. Each language has limited seats and time of submission of request is to be used for making a decision. The following are the fields provided in the application: a. Register Number, Name, Time and date of submission, Preference of language (Option1, Option2, Option3} Devise a solution that would automate the process of allocating the languages based on the order of preference given by students. Use appropriate data structures to process the data. Include provision for swapping of the language that has been allocated for a student on mutual consent.

Can anyone help me with logic of this q

[prime heath]

I have a list of list of numbers, for example [[1, 3, 10], [2, 6, 9], [5, 6, 7, 20]]. I want to pick one number from each inner list, such that the set of numbers I get is the closest bunch of numbers on the number line. Or in other words, the difference b/w the largest and smallest numbers in my set is the minimum. How can I achieve this efficiently?

In my example, the answer could be [10, 9, 7] or [3, 6, 6] or [3, 6, 5] or [3, 2, 5]

[fervent saddle]

So the list is like [n1, n2, n3], and you’re trying to find all the combinations which have the lowest sum of this:
abs(n1 - n2) + abs(n2 - n3) + abs(n1 - n3) ?

[prime heath]

its a list of list: [list1, list2, list3]

[fervent saddle]

I mean the answer list

[prime heath]

oh, no it should just have lowest value for max(ans) - min(ans)

you could say the numbers are contained within the shortest range

[fervent saddle]

Then what’s the point of the intermediate number?

[runic tinsel]

you want 1 number for each set

3 numbers because there are 3 lists, not because each has 3

[prime heath]

yeah, so there can be any number of inner lists, and inner lists can have any number of elements

[runic tinsel]

no idea whatsoever

[prime heath]

The brute force would be to just find all combinations. I was thinking if there is any better way

[vocal gorge]

It seems to me like you can maybe take a number from the first list, then take the two closest numbers to it in the two other lists via binary search. That'd be O(n log n)

though, hmm, that might not give the optimal result?

maybe if you repeat it with the other lists, each time considering the current element from the current list as the "middle" one?

[prime heath]

hmmm

[scenic hawk]

is the prerequisite to learning data structs and algos just knowing the python library inside and out?

[knotty magnet]

what python library

[fervent saddle]

You don’t need to know any particular language to start learning algos and data structs

[scenic hawk]

i might be reffering to it wrong

but just all the python syntax

like all the things i can do in python

[scenic hawk]

o rlly?

[hard bison]

Hi all, does anybody know if there's a place where I can find hundreds of test cases for classic graph algorithms (Dijkstra, Bellman-Ford, Kosaraju, etc) so I can test my algos against the right solutions? I took a MOOC a couple of years ago where you had to pass 1k tests per algo (with lots of edge cases) to have your solution "validated", but those test cases were private. I've been looking online but so far no luck.

[sinful hawk]

Had a general efficiency question

is it faster to find the max of a dict or an array?

[vocal gorge]

same asymptotic complexity, O(n)

iteration over dicts isn't anything special

[fervent saddle]

In python, with the way dicts are implemented, it might be pretty much the same speed. If you’ve been deleting from the dict then it might be slightly slower

But otherwise there won’t be a lot of empty spaces to go over since it iterates over the consecutively filled array

Instead of some hash table with a bunch of empty slots

But yeah they’re both O(n) like he said, if that’s what you’re asking

[sinful hawk]

ok thanks

yeah that makes sense

[dapper sapphire]

O(n log n ) takes longer than O(n)?

Yeah, O(n log n) takes longer than O(n).

Do both sort() in-place and sorted use Timsort?

!e

array1 = [11, 22, 33, 11, 11, 22, 22, 33]
array2 = [11, 22, 33, 11, 11, 22, 22, 33]

array1.sort()
array2 = sorted(array2)

print(array1)
print(array2)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | [11, 11, 11, 22, 22, 22, 33, 33]
002 | [11, 11, 11, 22, 22, 22, 33, 33]

[knotty magnet]

yes

[knotty magnet]

if by longer you mean is greater than, yes. however in terms of actual runtime, it depends

[fiery cosmos]

The order of a set won't change when you create an iterator of it right

i.e. the if a == b: will always trigger on the very first loop iteration here, right? py for a in someset: for b in someset: if a == b: ...

[fervent saddle]

Yeah

It should
You’re not allowed to add or remove from sets during iteration specifically to avoid resizing causing the order of things to change

[chrome void]

Can anyone explain this.? This is for combinations method from itertools

[dapper sapphire]

I meant longer in terms of time

[jolly mortar]

big O doesn't tell you much about runtime

even a O(n) program can run longer than a O(2^n) for some small input size

[dapper sapphire]

Let's say if we are doing some computation on 10 million elements and we have two algorithms.

One that's O(n), and another that's O (n log n), then to compute these 10 million elements, algorithm that is O(n) would take less time compared to the algorithm that uses O(n log n), right?

[fiery cosmos]

Probably. It is certain that there is some number (maybe above 10 million) for which that is true.

[fervent saddle]

If by “10 million” you mean “some hypothetical huge number” then yeah

[dapper sapphire]

Yeah I meant some hypothetically large number, sorry.

[wide lake]

for i in range(0, len(data), 3):
print(data[i])
is the time complexity is O(n) or O(logn)? and can explain why is that?

[jolly mortar]

which one do you think it is

[wide lake]

O(n)

[jolly mortar]

that is correct

the number of iterations grows linearly

there are n/3 iterations, if I doubled n i would get double the number of iterations

[wide lake]

But I saw this on the website :https://towardsdatascience.com/understanding-time-complexity-with-python-examples-2bda6e8158a7
An algorithm is said to have a logarithmic time complexity when it reduces the size of the input data in each step (it don’t need to look at all values of the input data), for example:
for index in range(0, len(data), 3):
print(data[index])

[fiery cosmos]

Well even linear time reduces the size of the input data by about 1 every iteration. log usually comes up when the size of the input is reduced by half every iteration.

[dapper sapphire]

It's still linear. Suppose you had a problem and you had to traverse through a list three times:

for elements in items:
  ...
  ...
for elements in items:
  ...
  ...
for elements in items:
  ...
  ...  

Time complexity for this would still be O(n).

It will not be O(3n).

[wide lake]

so if the list iteration is completly reduced by half it is O(logn),but if it iterate only by 2 or 3 elements but not the reducing the iterations over half it is O(n)

[fiery cosmos]

Technically it's correct to say that n = O(3n) and vice versa 3n = O(n). They are both O(n), and by convention and common sense you don't write the 3

[dapper sapphire]

Actually, yeah you are right O(3n) is still correct, but this would boil down to O(n).

[fiery cosmos]

Definitely yes to the latter part. If you skip ever other item the total items you see is still 0.5 the total, i.e. it's still proportional to the total length by a constant.

[dapper sapphire]

I dont know if this is a good exmaple, but think of it:
Imagine you have some algorithm which traverses every other element and assume numbers and time given below in seconds are hypothetical:

If you have 100 elements, then it would take 50 seconds in total.
If you have 300 elements, then it would take 150 seconds in total.
50 elements, would take 25 seconds in total.

You traversed through half the elements, so you could say O(n/2), but in computer science we would call it O(n). As you can see the time increase and decrease is linear.

[wide lake]

yeah i understood guys thks

[jolly mortar]

if you had something like

i = 1
while i < len(data):
  print(data[i])
  i = i * 3

where you multiply i by 3 each time instead of adding, it'd be O(log n)

[fiery cosmos]

There are some cases where "reducing by half" could give something more like N/1 + N/2 + N/4 + N/8 + N/16 + ... = 2N = O(N) which is linear but I'm not entirely clear on the subtleties here myself

[wide lake]

👍

[jolly mortar]

that's for infinite iterations though

when the denominator 2^n exceeds N, N/2^n becomes less than 1

and you can't iterate over less than 1 items

[fiery cosmos]

Right but that pattern still comes up in some algorithms.

I think the recurrence relation T(n) = O(n) + T(n/2) works out to that n + n/2 + n/4 + n/8 + ... = O(n)

Whereas T(n) = O(1) + T(n/2) works out to O(1) * log(n) = O(logn)

Just making it clear in my own mind

[fiery cosmos]

Can you please tell me the time complexity of this sort? size can range from 1 to 10^7

listOfTuples.sort(key=lambda x:x[0])```

[fiery cosmos]

What do you think?

The key=lambda x:x[0] bit means it's being sorted by the first tuple number, i.e. the 3 2 1, in case you don't know. So it's effectively sorting numbers normally

[sudden garden]

hey, I'm having a lot of difficulty with subarray/substring questions, I can't even do easy on leetcode for these problems. Is there a resource that goes through general techniques and approach for such questions?

[keen hearth]

You mean dynamic programming problems where you have to find the optimum substring or subarray?

[sudden garden]

so are these type of questions always going to involve dp?

I have never felt so stuck on leetcode questions before

[keen hearth]

Generally, yes. And I find them difficult too, don't worry

For subsequence problems, each element of the main sequence is either included in or excluded from the subsequence. This means that with a brute-force approach, there are 2^n possible subsequences to try, where n is the length of the main sequence.

The dynamic programming approach to this is to focus on just one element at a time, and whether you include or exclude this element from the subsequence. As you work through the elements, you maintain a table of partially completed subsequences (usually just their lengths) and just enough information about each subsequence to determine which elements can extend that subsequence.

For example, in the 'longest increasing subsequence' problem, you only need to know the value of the last element of a subsequence to know whether you can extend that subsequence with another value.

[sudden garden]

my problem is definitely coming up with a proper substructure for such questions

I'm currently trying to solve this https://leetcode.com/problems/maximum-subarray/

[vocal gorge]

in O(n) or via divide-and-conquer?

[sudden garden]

O(n)

[vocal gorge]

the O(n) solution involves a trick of constructing ||an array of cumulative sums, which then allows finding the sum over any contigious subarray in constant time, by just looking at the difference of two elements of that cumsum array||

not sure if that is considered dynamic programming; I got taught that trick before I knew what DP was, so not sure

[sudden garden]

my idea was if need to find sum of subarray[0,n-2], it would just be totalSum - array[n-1]

[vocal gorge]

yeah, that's a particular case of finding the sum of a subarray via the cumsum array

generally, if cumsum[0] = 0, cumsum[n] = totalSum, cumsum[i] is the sum of subarray[:i], then the sum of subarray[i:j] is cumsum[j]-cumsum[i].

and the sumsum array itself can be calculated in O(n)

[sudden garden]

wouldn't I have to calculate each subarray since I need the max?

I don't see how that can be done in linear time

[keen hearth]

It's helpful to think of a contiguous subarray as the difference of two prefixes. You only need to ||keep track of the minimum prefix-sum so far||.

[vocal gorge]

by using the cumsum trick, the task is reduced to finding two indexes i,j such that j >= i+1 and cumsum[j] - cumsum[i] is maximized, which can be done in O(n) too

hmm, I wonder if this is the nicest way to solve this, though it does work

[vocal gorge]

heh, that task actually has its own entry: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

[sudden garden]

thank you for help, I clearly need a lot of practice

[dapper sapphire]

What is (x2 - x1)^2 called in Euclidian distance formula?

I dont know if it's called something, but can we call that portion, delta_x_square?

or just delta_x?

[vocal gorge]

I guess you could call it a squared cathetus too

but delta_x_sq is totally fine by me

[dapper sapphire]

Actually I like delta_x_sq, it's short, but the person reading it would also get the idea sq is square. Thanks!!

[hidden fiber]

is time complexity O(n) with space comp. O(n) better than time comp. O(n log n) with space comp. O(1)?

[vocal gorge]

...why would lowering both complexities be worse?

[hidden fiber]

typo... its O(n log n)

[dapper sapphire]

In terms of computation, is square easier and faster than square root?

[knotty magnet]

yes

[main flower]

Yeah

[main flower]

It depends on the problem

Like

In dynamic programming you cache expensive function calls to decrease time complexity, but it requires you to store all of that so it obviously increases memory complexity

So

It depends on what you need

[runic tinsel]

you have limited time and limited space, neither is great, you kinda prefer O(1) space because it won't run out of memory, crash and waste all the time, but if it actually won't run out of memory then it's a waste of time to use the slow program

🤷‍♂️

[fiery cosmos]

so it'll be the same O(nlogn) for Timsort

[wispy hawk]

Getting TLE for this, I am guessing the problem is using the queue module, I solved the problem using list in python,but want to solve using queue module:https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/1326581/level-order-traversal-time-limit-exceed-queue-module-python3/1003810

[runic tinsel]

try with deque from collections

it worked for me, I don;t know what's the issue with yours

Like, there may be no issue, you could be using a library that's 60 times slower or something

[old rover]

hmmm

i think i should try some CTCI

i think it's a good idea

there are some tough problems in there that require careful thought and analysis

and plus I need a refresher on the basics

[fiery cosmos]

Does anyone which algorithms Google Search uses?

[knotty magnet]

it's probably proprietary

[fiery cosmos]

do you know the names at least?

[knotty magnet]

of what

[fiery cosmos]

of the algos google search uses?

[knotty magnet]

no

[fiery cosmos]

PageRank

Originally

[fiery cosmos]

thnx!

but is it still being used now?

[knotty magnet]

probably not

[fiery cosmos]

hmm... that's interesting

[knotty magnet]

ah, from quick wikipediaing, it says they do

[fiery cosmos]

oh

[fiery cosmos]

thanks for the info btw!

[autumn mason]

hello everyone
wanted to ask how does one approach the pathfinding problems in python?

[main flower]

Yes, they still use PageRank, but most of the work is now done by ML algorithms and stuff like that

So now it depends on what you mean by "use it"

[shut breach]

I'm looking for a data structure with the following properties:

pop(idx)    # removes item - O(1)
get(idx)    # returns item - O(1)
push(item)  # returns idx for item, don't care what it is just that it's unique - O(1) ideally, not sure if possible
``` I know the max number of items ahead of time, but specific entries might get added or removed over the course of the algo

I'm thinking about some kind of sparse array, but I wanted to see if there was a ready-made solution that I'm missing

oh maybe an array paired with a queue of available keys...

[fiery cosmos]

Seems like a thin wrapper around a dict would work and be O(1) for all 3 handle the keys aka indexes internally and increment the index on every push

!e ```py
class ScoffDict:
def init(self):
self.d = {}
self.index = 0

def push(self, item):
    self.d[self.index] = item
    self.index += 1
    return self.index - 1

def get(self, index):
    return self.d.get(index)

def pop(self, index):
    del self.d[index]

d = ScoffDict()
i = d.push("abc")
j = d.push(999)

print(d.get(i))
d.pop(i)
print(d.get(i))
print(d.get(j))

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | abc
002 | None
003 | 999

[fiery cosmos]

Though if you pop loads the performance might start to degrade @fervent saddle would know more

[shut breach]

hmm that's true, I was thinking in the context of arrays where repeated activity would grow the array infinitely

but a dict wouldn't do that

[plain cove]

               'C1' : [10,20,30]               
             }

Say if I have this dictionary and I want to add {'C2' : [20,30,40]}, then what should I do?

[shut breach]

dictionary['C2'] = [20,30,40]

unless you mean at the time you define it, in which case

dictionary = { 
               'C1' : [10,20,30],
               'C2' : [20,30,40],       
             }

[plain cove]

what if i have another variable that stores {'C2' : [20,30,40]}

[shut breach]

dictionary.update({'C2' : [20,30,40]})

actually now you can do dictionary |= {'C2' : [20,30,40]}

you have a wealth of options

[plain cove]

oh thanks, let me try. The data I'm working with is a little bit different but I think your solution might work.

[old rover]

woah you can use .update?

i never knew that was a thing

that is cooll

[dapper sapphire]

!e

dictionary = {"abc": 0}
dictionary.update({"abc": 1})
print(dictionary)
dictionary.update({"abc": +1})
print(dictionary)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | {'abc': 1}
002 | {'abc': 1}

[dapper sapphire]

!e
dictionary = {"abc": 0}
dictionary.update({"abc": 1})
print(dictionary)
dictionary.update({"abc": dictionary ["abc"] + 1})
print(dictionary)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | {'abc': 1}
002 | {'abc': 2}

[fathom flume]

How would I make the type annotation for a List of Dictionaries where I already know the keys?
Right now I just have the info about the keys in the comment.
I have to examples below of what I am trying to go for.
Example:

class SomeClassName:
    myDictList = []  # List of Dictionaries with the following keys: 'key1', 'key2'
    # myDictList = List[Dict]
    # myDictList = List[{'key1': str, 'key2': int}]

[celest herald]

is there help available here?

''' py

cmlargs = {} # initialize as empty dictionary
cmlargs['JAN'] = 1 # add 'm' key and its val
cmlargs['FEB'] = 2

print cmlargs

filename = open('temperatures_1.dat','r')

data = genfromtxt(filename, dtype = None, skip_header =18, skip_footer =1)

data =np.loadtxt(filename, dtype = str, skiprows = 18)

print data

filename = 'temperatures_1.dat'
data = np.genfromtxt(filename, dtype = None, skip_header =18, skip_footer =1, usecols=(1,12))

print data

here I am interested to use a dictionary to map from file
to select relevant columns to further plot them in matplotlib
YEAR JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC ANNUAL
1856 0.02 -0.35 -0.76 -0.32 -0.18 0.16 -0.12 -0.35 -0.30 -0.52 -0.89 -0.23 -0.32
1857 -0.29 -0.41 -0.51 -0.46 -0.52 -0.22 -0.04 0.03 -0.42 -0.53 -0.72 0.07 -0.34
1858 -0.44 -1.30 -0.83 -0.11 -0.15 0.04 -0.06 -0.24 0.05 0.19 -0.84 -0.32 -0.34
this is how the data looks in file
by matching the coomand line arguments with columns' indices I shall be able select the wanted columns
the first row is suggested to be used in the command line arguments

[vocal gorge]

List[Dict[Literal["key1","key2"]]]

Literal is how you write "exactly this". Literal[a,b] is an alias for Union[Literal[a],Literal[b]].

That said, if the structure of the dict is predefined, you might want to simply have it be a class of your own and not a dict.

like,

@dataclass
class SomeData:
    key1: str
    key2: int

and then your list is List[SomeData].

[meager sun]

def BinarySearchHelper(arr,x,l,r):
    if r >= l:
        mid = l + r // 2
        
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return BinarySearchHelper(arr,x,l,mid-1)
        else:
            return BinarySearchHelper(arr,x,mid+1,r)
    else:
        return -1
    
    
arr =[10,20,30,40,50,60,70,80,90,100]
x = 70
    
result = BinarySearchHelper(arr,x,0,len(arr)-1)
if result != -1:
    print("Element present at index % d "% result)
else:
    print("Element is not present in array.")

[prisma mortar]

this show me error.

[prisma mortar]

def binarySearch(arr, f, l, x):
if f > l:
return -1
mid = (f + l) // 2
if arr[mid] == x:
return mid
elif x > arr[mid]:
return binarySearch(arr, mid + 1, l, x)
else:
return binarySearch(arr, f, mid - 1, x)

[dapper sapphire]

I remember easy Leetcode were hard for me to solve in the beginning, but then after sometime, I could figure out the solution in reasonable time.

But medium level Leetocde questions actually make me think a lot harder. Especially the part where you have to decipher what the actual problem is.

[fathom flume]

Thank you, I will try that out

[chrome timber]

is it okay if i discuss numpy here?

Points = np.take(pointIn, Indices, 1)
what this does is grab an array for example [5,2,6,3,100,2] if the indices are [1,3,4] then the return of this function would be [2,3,100] so it's basically filtering an array by indices

how would i go about doing this on a dictionary?

that is in this format

points['x'][0:numOfPoints], points['y'][0:numOfPoints] etc...

i know i can make a new dict and a million other inefficient approaches

looking for something somewhat elegant

[vocal gorge]

This can also be written as just Points = pointIn[Indices], I believe, btw

[chrome timber]

yes it can

[vocal gorge]

Not totally sure what you want to do. Can you provide an example?

[chrome timber]

Okay so i want

let's say i have a dictionary with a billion keys that all have the same number of values. Now i want a subset of those values by using indices to refer to the ones I want

[vocal gorge]

Indices as in the keys?

or by position in the dictionary?

[chrome timber]

indices meaning

point['x'][3] point['y'][3] etc.... = Filtered_point['x'][0] Filtered_point['y'][0]

if 3 was in that list of indices

and it keeps going on until it goes through all the indices

the trivial solution would be to make a loop and copy the dictionary

but i'm certain that there exists something in python itself for this

I just can't phrase it well in google

[vocal gorge]

ooh, so point is a dictionary of lists, and you want a dict of key: point[key][3] for all keys in point?

[chrome timber]

Yup

[vocal gorge]

that can be done via a dict comprehension, which is just a succintly written loop:

filtered = {key: value[3] for key,value in point.items()}

(.items() returns an iterable of all (key,value) tuples in a dict).

[chrome timber]

and how do i add a list of indices?

meaning

filtered = {key: value[indices] for key,value in point.items()}```

value unfortunately isn't a numpy array though

[vocal gorge]

are the values numpy arrays or-

[chrome timber]

Nope 😦

don't think python has that functionality?

i've been programming way too much rust lately

[vocal gorge]

then you'd have to write your own helper function like:

def get_indices(lst, indices):
    return [lst[i] for i in indices]

heh,same

[chrome timber]

ah okay

[scenic hawk]

could someone explain how O(n^2) is correlated with the summation formula? i don't quite get that

[chrome timber]

Imagine u're doing that programmatically

[scenic hawk]

it makes sense mathematically, just not logically

[chrome timber]

so you have a for loop

[scenic hawk]

right

[chrome timber]

what is the question even about?

cause if that was a function O(n^2) is correct

cause it's technically an upper case

even though it's not the tightest

[scenic hawk]

just understanding it better, bc i understood it as a double for loop and i don't see how that pattern is created

with 1 + 2...

[chrome timber]

it's a single for loop

it's O(n) realistically

[vocal gorge]

presumably the loop was something like

for i in range(n):
    for j in range(i,n):

[scenic hawk]

ahhh, i see

[vocal gorge]

which does:

1. n iterations for i=0
2. n-1 iterations for i=1...
3. 1 iteration for i=n-1.
   So total of n+n-1+...+1 = n*(n+1)/2 iterations of the inner loop, which is O(n^2).

[scenic hawk]

gotcha, ty i understand it so much better now

[chrome timber]

but isn't that just ∑n?

[vocal gorge]

Wdym?

[scenic hawk]

yea

[chrome timber]

cause u can refer to a single for loop as O(n^2)

even tho it's not realistic

maybe the question is referring to that?

[vocal gorge]

not sure what you are trying to say

[chrome timber]

back in first year university we had a series of questions like those

that get us to answer what the time complexity of a function would be if we had to implement in programatically

and half the answers were cheeky answers were we had to understand that O(n) is just an upper bound

[vocal gorge]

the exact number of iterations of the inner loop (let's say some constant stuff happens there) is n*(n+1)/2, which is O(n^2) by definition. You can also do an upper estimate by considering that the inner loop does at most n iterations for each outer iterations, so it's around O(n^2) that way too.

But n*(n+1)/2, here, is an exact answer, and it's O(n^2).

[vocal gorge]

hmm, not totally sure what you mean

like, if the loop breaks in some conditions?

[chrome timber]

nope

let's say a random function has a true upper bound of O(n)

you can technically say that it's O(n^2) even though it would never reach that time complexity

[vocal gorge]

hmm, that's true, the definition does allow that

[chrome timber]

and that summation should be O(n) right? or am i missing something?

it's just

x = 0
for i in range(1, n):
  x += i

[vocal gorge]

This snippet of code is O(n), yes

[violet dirge]

yo anyone has a code to read gmail through python?

[fiery cosmos]

solving for the easy squared array problem

class Solution:
   def sortedSquares(self, nums: List[int]) -> List[int]:
        # brute force: O(nlogn) time, O(1) space (modifying the original array)
        for i in range(len(nums)):
            nums[i] *= nums[i]
        return sorted(nums) 
    
    import bisect # lets insert in a sorted way (binary way)
    def sortedSquares(self, nums):
        ans = []
        for num in nums:
            bisect.insort(ans, num*num)
        return ans

why does the first function run much faster when I test it?

I thought my bisect function would run in O(logn) time

[fervent saddle]

Inserting into an array is O(n) whether you find the right position to insert at in O(logn) time or not

The bisect function inserts into the array

So it’s actually O(n**2)

[fiery cosmos]

shouldnt it be n log n then?

where is the n * n coming from

[fervent saddle]

Because you’re inserting n times

[fiery cosmos]

insort is O(n)

I see

because it still does insert which is O(n), I got it

so it's nlogn * n

no, just n*n

insort is O(logn + n) = O(n) and you do it O(n) times

[fiery cosmos]

doing O(logn) n times would mean O(nlogn)

oh yea I was wrong

O(logn + n) = O(n) because it's upperbounded by n

[fiery cosmos]

    # two/three pointers solution
    # O(n) time, O(n) space
    
    def sortedSquares(self, nums):
        ans = [0 for _ in nums]
        left = 0
        right = len(nums) - 1
        
        for i in reversed(range(len(nums))):
            if abs(nums[left]) > abs(nums[right]):
                ans[i] = nums[left] ** 2
                left += 1
            else:
                ans[i] = nums[right] ** 2
                right -= 1
        return ans

I dont get it, I wrote a O(n) time solution (at least that's how fast I think it is)

but on LC, it runs slower, on avg, than my sorted() solution which is O(nlogn)

LeetCode times are pretty sporadic in my experience I've seen a solution go from faster than 99% to 20% to 80% without changing a thing

Though it also might have to do with sorted being a highly optimized built-in that (I assume) is implemented in C, so depending on the tests it could look better

In fact where is the source code for sorted I can't find it

[ivory yacht]

Sorted is indeed implemented in C, it's an optimised merge sort.
The code is here, sorted() just does list(x).sort():
https://github.com/python/cpython/blob/main/Objects/listobject.c#L1051
There's documentation on the algorithm here, the main optimisation is to detect already-sorted parts of the list, and take advantage of that.
https://github.com/python/cpython/blob/main/Objects/listsort.txt

[fiery cosmos]

ooh thanks

I count ~1400 lines dedicated to list sorting that's like 41% of that 3.4k line file

[jolly wolf]

hi!, im stuck trying to bound a sum to find a time complexity uwu can i ask it here?

[old rover]

you know I really like the amount of thought this code even takes

it's simple

but it does well

like thinking about how the code does

what each line does

bc you're gonna have to think about what each line does

i ruminate and emphasize issues to NF so he feels more sympathetic

[jolly wolf]

well, basically the problem is,

let x an integer, let A an array of arrays, when every array ai in A has length ni, and |A| = k
let D an algorithm that figure out if x is in the intersection of all arrays in A.

Get the time complexity of D in the worst case, assuming D use a binary search to find x.

Well, the worst case happens when x is actually in the intersection, because forces D to looking for x in all arrays in A.
Knowing that the time complexity of a binary search is O(log n) (being n the length of the array), then the
time complexity of D is

$\sum_{i=1}^{k} log(n_i)$

my problem here is to bound that sum 😦

[fiery cosmos]

doesnt Python use Timsort for sorts?

[ivory yacht]

Yep, that's the name of the algorithm, it's an enhancement of merge sorts.

[vital wadi]

Hello I want to scrape data in red fields. I've watched several video's about BeautifulSoup or python scraping but every video assumes the site has unique class names to search & capture data. For this website I'm testing on, every td has same class. Does anyone have tips, or a link to a post/tutorial or anything that will help me scrape the specific data I want? Thanks in advance

[ember topaz]

So I've been comparing a lot of ways to find the latest named file in a directory out of jpgs... and with a test directory of almost 40k files feels like it should be enough, real world example will be around 5-10k.

people been telling me Scandir is the way to go, other said I should use glob. etc. but in the end...

in my tests, os.listdir() with Lambda and sorted() is fastest to get a sorted list...

[vocal gorge]

If you need only the latest file, you don't need to sort the list - just take the max by modification date of the iterable of files obtained by iterdir or scandir.

taking the max should be notably faster than sorting the like in its entirety

[ember topaz]

latest file is based on the date stuck in the filename, so rather than getting that date, I'm getting the date it was placed/saved there., so that's why the sorting by filename

so this turned out to be the fastest, and it became slower if I didn't put sorted() on a separate line^

[vocal gorge]

I'd try

return max(x for x in os.listdir(path) if x.endswith(".jpg"))

[ember topaz]

I'll add it in the tests and try.

[vocal gorge]

glob I can easily see being slower just because it's a pretty powerful library, and overkill for just checking .endswith(".jpg")

[ember topaz]

yeah that max solution is very much similar, every other run they beat each other in the test I just ran

glob was one of the slowest, if not the slowest I tested

[ember topaz]

with glob you can also do glob.glob1(path,"*.jpg") which using a asterisk prob, isn't very efficient

without the asterisk you get index out of range,

[vocal gorge]

I wonder how using

return max(x for x in pathlib.Path(path).iterdir() if x.suffix==".jpg")

compares

probably a bit worse, pathlib does have a little overhead

[ember topaz]

yeah, yeesh

[vocal gorge]

lol, that's worse than I hoped

I guess splitting 40k paths into components is heavy

[ember topaz]

yeah also that Pathlib line, gave me whole path instad of filename as well.

used x.name instad ad I just got the filename instead of path, it was faster than before, but still slow compared to the earlier listdir max

the old code I am refactoring is using glob, so this def gonna be a improvement overall^

the old code, vs the "newer" code my co-worker said scandir was faster...

but now with the lambda/max solutions it's down to 0.05-0.06 on avg, so that's great

[deft locust]

it could be O(1) using the sum of natural numbers?

i think most optimizing compilers will optimize it like that anyways

[vocal gorge]

heh, optimizing compilers

[deft locust]

numba, cython, any C/Rust compiler with -Ofast or O3 or whatever will just use AP under the hood

[vocal gorge]

let's see

[vocal gorge]

It does not appear so:
https://godbolt.org/z/x1PhGbr1v

the ASM looks like it still has a loop to me

[deft locust]

huh... it did that last time i tried with numba

brb

[vocal gorge]

ha, it does work in Rust tho

pub fn sum_n(n:u32) -> u32{
    (0..n).sum()
}

gets optimized to be a multiplication:

example::sum_n:
        test    edi, edi
        je      .LBB0_1
        lea     eax, [rdi - 1]
        lea     ecx, [rdi - 2]
        imul    rcx, rax
        shr     rcx
        lea     eax, [rdi + rcx]
        add     eax, -1
        ret

[deft locust]

yep

gcc

probably O(1) in numba too

[vocal gorge]

yeah, clang optimizes it correctly

[hidden fiber]

how is AlgoExpert for algorithms?

[lethal bridge]

Wait isn't gcc supposed to be better for performance runtimes... although my source is 2years old

[fiery cosmos]

someone know how to export images (tkinter background) with pyinstaller to my exe? The users obviously dont have the images in the directory so yea how can i share a exe with images?

only works on my device (the pictures on my window)

[lunar jacinth]

Could someone help me figure out the time complexity of the while loop inside the beta function?

[shut breach]

what does the function do?

[lunar jacinth]

i'm not quite sure tbh :l

[vocal gorge]

it's probably a practice question and the functions aren't meant to mean anything

[lunar jacinth]

yeah its a practice question for my midterm coming up

[shut breach]

that's... really awful practice

[lunar jacinth]

its listed as "practice question" haha

I got O(h-l) for alpha, but not sure about beta

[shut breach]

well the fundamental question is how many times does the loop run

so I'd recommend running through it by hand and maybe note down what the stack looks like as it goes

and use that to figure out when the loop will hit its stop condition

[lunar jacinth]

Could we even figure that out if we dont have numbers for l and h?

would the while loop just be constant time?

[leaden magnet]

hello can someone help me with a advice

my vs code terminal is don't working properly

[shut breach]

you want to figure it out in terms of l and h

[shut breach]

this is not the place for that question, try #editors-ides

[lunar jacinth]

Wouldnt it just be O(h-l)?

[shut breach]

haven't looked at it closely until now

I hate these questions, asking to find the complexity of obfuscated code is just a waste of everyone's time

do you know what Alpha does?

[lunar jacinth]

Yeah it is O(h-l)

[lunar jacinth]

I have C0 + C1 + (h-l)(C1+C2+C3+C4) + C5 + C6 = O(h-l)

[shut breach]

no I mean what Alpha returns matters since it's used to control the flow in the while loop

it determines whether top is incremented, which in turn determines how many times the loop is run

[lunar jacinth]

okay i see

could it be O((h-l) ^2)?

[knotty magnet]

it prevents the student from just having memorized things like, "oh, sorting is n logn, binsearch is log n" etc, so it makes sense, sorta

[shut breach]

idk I don't there's a shortage of algorithms out there

and if there was, memorization would basically be sufficient anyway

[knotty magnet]

for common ones, it's not that hard to do, though

[lethal bridge]

how do you invert a binary tree

[lunar jacinth]

recursion i believe would work well

aftter making two classes, one for node, one for invertTree

you could do something like ```py
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root

[lethal bridge]

It was a joke

But thanks for the reply

[lunar jacinth]

u see idk jokes yet

im still on the very basic level of data structures

[lethal bridge]

This will probably work

[rugged swan]

I need answers

This question

Please

[knotty magnet]

presumably, you were intended to provide them yourself

given that no one actually does these types of questions for fun, that's probably a test

[austere sparrow]

You should try to solve it yourself, and ask specific questions if something isn't clear.

wikipedia https://en.wikipedia.org/wiki/Big_O_notation explains quite well the difference between big O, big Omega and big Theta.

[rugged swan]

I don't know

[rugged swan]

I don't know answers

[austere sparrow]

Do you understand what O, Ω, and Θ mean?

What level of education are you in, btw? High school/college/... ?

[rugged swan]

College

Please help me

To answer

[austere sparrow]

.

[rugged swan]

No

[austere sparrow]

Are you familiar with Big O-notation in programming, in general?

[rugged swan]

The doctor told us to answer this question without explaining to us

[austere sparrow]

If you've never seen Big O, I recommend reading this article https://nedbatchelder.com/text/slowsgrows.html.
Then you can read about the formal definition of O-notation, either in the textbooks you were provided or on wikipedia https://en.wikipedia.org/wiki/Big_O_notation, I think it's a decent page.
The formal theory bit is based on limits, so if you aren't familiar with limits, I recommend the lessons on Khan's academy https://www.khanacademy.org/math/calculus-1.

[fiery cosmos]

I like the succinct definition at https://xlinux.nist.gov/dads/HTML/bigOnotation.html

Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

[lunar jacinth]

Wait so is the while loop O((h-l)^2)?

[south umbra]

how to get started with dsa in py

[knotty magnet]

check the pins in this channel

[south umbra]

should we do dsa in py

[knotty magnet]

imo, no. but some people will disagree

[lunar jacinth]

@fiery cosmos would you know anything about this?

[south umbra]

[fiery cosmos]

I have a hunch Beta sorts the list, though I'm not sure exactly how. Alpha returns the number of other items from l to h that are less than or equal to the last, and rearranges a bit.

So Alpha is O(N) (N = h - l) and it seems plausible the Beta stack stuff loops until the list is sorted - maybe O(N) times total. So I'd guess O(N^2) overall.

But I really can't say for certain

The stack in beta appears to keep l, h pairs which are ranges over arr and it keeps calling Alpha on them. It almost feels like a non-recursive quasi-mergesort. So it might be O(NlogN)

[lunar jacinth]

yeah i believe it is O(h-l)^2

[lunar jacinth]

but what would the while top >=0 line be? O(h-l)?

if i were to do a line by line analysis

[fiery cosmos]

Well it depends on the stack and how alpha and the logic in the while loop behaves

You can't reduce it to just looking at the while condition

[lunar jacinth]

Lets say the while loop line runs, would it be O(h-l) then?

and then O(h-l) again when it calls alpha?

[fiery cosmos]

I don't think the while loop is linear. nlogn or n^2 maybe

[lunar jacinth]

yeah i believe its n^2

i have O(h-l)^2 for it rn

when it goes into the while loop, would the h = stack[top] be of constant time?

[fiery cosmos]

(You can say the actual comparison top >= 0 is constant time of course, but I don't think that's the question )

[lunar jacinth]

oh no that is the question xD

i have to do line by line analysis

[fiery cosmos]

Isn't the question how many times you have to do that comparison? i.e. what is the overall running time of Beta?

[lunar jacinth]

like literally the line ```py
while top >= 0

yeah it is but i have to do line by line analysis first

sorry if i was confusing

[fiery cosmos]

I see so yeah in that sense the comparison is O(1)

[lunar jacinth]

and then ```py
h = stack[top]
top = top - 1
l = stack[top]

im confused on where the while loop becomes O(l-n)^2

[fiery cosmos]

yeah, everything inside except the call to Alpha is constant since it's simple array accessing and increments and ifs

[lunar jacinth]

yeah so the line ```py
p = Alpha(arr,l,h)

[fiery cosmos]

yeah, because alpha loops from l to h

[lunar jacinth]

So how exactly is this O(h-l)^2?

if theres only one O(h-l) in the loop

im sure you're correct haha, just trying to understand it a bit

[fiery cosmos]

The Beta while loop only stops once the stack is empty. And what gets added to the stack depends on how Alpha behaves (which I'm not entirely clear on).

Alpha runs in O(N) but it might end up that over time N things are added to the stack, making it O(N^2) total

I think it's misleading to label the while loop with O(1) because really the actual loop does way more. (It's ok to say the while comparison is O(1))

like, how would your teacher label this code line by line

for x in somelist:
  print(x)```

<@&831776746206265384>

[keen hearth]

!mute 437994756468113408

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @void rampart until 2021-07-12 23:03 (59 minutes and 58 seconds).

[shut breach]

!pban 437994756468113408 spam

[halcyon plank]

:incoming_envelope: :ok_hand: applied purge ban to @void rampart permanently.

[fiery cosmos]

thanks mods

[lunar jacinth]

Algorithm Beta(arr, l, h)
    size = h - l + 1               C0
    stack = [0] * (size)           C1 
    top = -1                       C2
    top = top + 1                  C3
    stack[top] = l                 C4
    top = top + 1                  C5
    stack[top] = h                 C6
    while top >= 0                 C7
        h = stack[top]             C8
        top = top - 1              C9
        l = stack[top]             C10
        top = top - 1              C11
        p = Alpha( arr, l, h )     O(h-l)
        if p-1 > l                 C12
            top = top + 1          C13
            stack[top] = l         C14
            top = top + 1          C15
            stack[top] = p - 1     C16
        if p + 1 < h               C17
            top = top + 1          C18
            stack[top] = p + 1     C19
            top = top + 1          C20
            stack[top] = h         C21

Would that be correct? C stands for constant

like everything is constant except the p = Alpha line?

[fiery cosmos]

I guess But then the C7 being constant doesn't let you infer anything about the overall run time

i = 0        # O(1)
while i < N: # O(1)
 i += 1      # O(1)``` in the same way this snippet is definitely not O(1) overall

[lunar jacinth]

maybe that should be O(h-l) too? xD

[fiery cosmos]

Depends on what your class/teacher wants I guess

Finding the actual complexity of Beta is super tricky so maybe that isn't the actual goal

[lunar jacinth]

i might put O(h-l) here instead of c7

[fiery cosmos]

The N for the while in that image confuses me again it depends on the loop body. If the body was pass it would be infinite time. If it was low += 1 then sure it's N. As it is a binary search is logN. N makes no sense as is.

[lunar jacinth]

i think ima just leave it as N cuz i think thats what he wants according to his notes xD

but yeah this function makes no sense haha

I have another question actually, would this line ```py
stack = [0] * (size)

[fiery cosmos]

it has to allocate size number of variables so O(size)

try x = [0] * 1000 in a Repl adding more and more 0's to the 1000 and you'll see it takes longer and longer

[scenic hawk]

is there something where i could paste my code and it tells me the time complexity?

[fiery cosmos]

I meant post your code here and we may be able to help you analyze it

[scenic hawk]

ik there like softwares where they analyze your code and give you like a grade rating, so they must use some kind of like big O notation kind of thing to rely on right?

oh

i actually don't have a code, but just a general question that i've thought up of @fiery cosmos

[fervent saddle]

They might just time it

[scenic hawk]

ah, thats true

[fiery cosmos]

Though in practice timing likely wouldn't be accurate enough find those super crazy complexities that come up in research e.g.

(from https://en.wikipedia.org/wiki/Shellsort o.O)

[dapper sapphire]

Is there a way to slice and set elements of a slice to 0?
So if we have:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

if we can do something like
matrix[1:] = 0

So we can turn [4, 5, 6] into [0, 0, 0]?

I can only think of creating a helper function that would do that

[jolly mortar]

matrix[1:] = [0, 0, 0] would work

if the length is unknown, you would have to find len(matrix[1:]) and multiply [0] by that

[fervent saddle]

import numpy as np

arr = np.array([1,2,3,4,5], "int8")
print(arr)
arr *= 2
print(arr)```
When you do this thing that’s being done on the 2nd to last line, is it O(1) or O(n)?

And if it’s O(1) then how? Does it remember the operations that have been done on the array and apply them when you access the value or something like that?
*nvm, it doesn’t seem like it’s O(1) based on timeit results

[dapper sapphire]

Yeah, that would work actually for a row.
can we something similar for column?
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

change 1, 4, 7 to 0?

actually nvm

[jolly mortar]

its possible with numpy arrays i think, not with normal lists afaik

you could zip(*x) to transpose, change it and transpose it back i guess

[dapper sapphire]

oh ok

I created helper function to change both rows and columns. But [0] * len is pretty neat. Thanks!!

[knotty magnet]

it tries to do this, https://en.wikipedia.org/wiki/Automatic_vectorization, iirc

[vocal gorge]

Ultimately, vectorized operations on numpy arrays are O(size of the array). They are just usually really, really fast compared to what you see in Python because they are written in C and, yeah, probably in such a way as to maximize the chances for autovectorization.

[knotty magnet]

it has a much smaller constant than looping over a list

[lethal bridge]

In short compiler black magic

[vocal gorge]

maybe I should try comparing the performance of numpy installed from pip vs. compiled from source

hypothetically, the latter, if compiled for my specific CPU, etc, should be a bit faster

being able to use AVX, say

[lethal bridge]

trying to compile numpy is a mistake

I personally never succeeded

Essentially trying to compile numpy will likely force one to go down the BLAS rabbit hole

One of which I never successfully navigated (I never got MKL to work, ever), but perhaps you will solve them without issues

[vocal gorge]

yeah, that's a bit of a yikes, I wouldn't want to complile BLAS from source

[deft locust]

march = native

[subtle musk]

You might be interested in trying Anaconda. If I recall correctly, it will install MKL without a glitch, and you will get very fast results.

[loud trail]

i did some microbenchmarks (matrix multiplication, matrix inverse, svd) and found that MKL was a lot faster than OpenBLAS in some cases (on intel hardware of course)

i wonder if there is some MKL equivalent for ARM

[lunar jacinth]

Could someone explain how to implement a radix sort using a doubly linked list?

[brave owl]

hey i have a merge sorted array problem and i cant figure out why it isnt working

def merge(arr1, arr2):
    m = len(arr1)
    n = len(arr2)
    fin = []
    while m>0 or n>0:
        ind1 = len(arr1) - m
        ind2 = len(arr2) - n
        if arr1[ind1] < arr2[ind2]:
            fin.append(arr1[ind1])
            m -= 1
        else:
            fin.append(arr2[ind2])
            n -= 1
    return fin


print(merge([0,3,4,31], [4,6,7,30]))

it seems to sort the 2 lists into 1 but then the while loop runs again and causes an error

actually it leaves off the largest value from the 2 lists

[knotty magnet]

0 is the first index

[tepid bear]

If I am not wrong you have to do a bit more. First of all you have to do the while loop while m and n are larger 0
Once the loop ends one list will be empty you have to check so with an if statement and then just add the rest of the list to the final list

[brave owl]

Ok that makes sense

[shut inlet]

hi this is a problem:

- Insert
- Remove
- Replace

but i dont really get the solution:

 
    # If first string is empty, the only option is to
    # insert all characters of second string into first
    if m == 0:
        return n
 
    # If second string is empty, the only option is to
    # remove all characters of first string
    if n == 0:
        return m
 
    # If last characters of two strings are same, nothing
    # much to do. Ignore last characters and get count for
    # remaining strings.
    if str1[m-1] == str2[n-1]:
        return editDistance(str1, str2, m-1, n-1)
 
    # If last characters are not same, consider all three
    # operations on last character of first string, recursively
    # compute minimum cost for all three operations and take
    # minimum of three values.
    return 1 + min(editDistance(str1, str2, m, n-1),    # Insert
                   editDistance(str1, str2, m-1, n),    # Remove
                   editDistance(str1, str2, m-1, n-1)    # Replace
                   )
 
 
# Driver code
str1 = "sunday"
str2 = "saturday"
print editDistance(str1, str2, len(str1), len(str2))```

[tepid bear]

Are removing a char and adding one desperate operations?

[shut inlet]

oh these are the operations we can do:

Insert
Remove
Replace

[tepid bear]

Ah ok

So I think my approach would be to loop through one string and count the number of similar characters. And this basically solves it. Now you can substract that number from str1 and then add str2 - similar characters

In this case s u d a ( a only once) y are similar in both so the num would be 5. Then you do Len(str1) - NUM so that would be 1 ( you have to remove the n) then you do Len(str2) - NUM which would be 3 and then you add those numbers so 1 + 3 and that's your solution

@shut inlet

[shut inlet]

i got you, i didn't get this part s u d a ( a only once) y

[tepid bear]

So you have to count the number of similar character between str1 and str2

therefore you can loop through str1 and if the char is in str2 you can add 1 some variable that is counting the similar character

In the case of Sunday and Saturday.

S is in both.
u is in both.
n is not in both
d is in both
a is in both
y is in both

So the number of same would be 5

@shut inlet

[shut inlet]

ahh okay

that makes sense

thank you so much for your solution 🙂

helped a lot @tepid bear

[tepid bear]

No problem Hope it works :D

[rain viper]

Dudes: I am wanting to loop my whole script to run every 60 seconds through my api to write to csv every 60 secs i am so close to making it work, i am using this:

schedule.every(60).seconds.do(tweets_to_data_frame)
    while 1:
        schedule.run_pending()
        time.sleep(1)

and my df is written using this:

 def tweets_to_data_frame(self, df, tweets, user):
    user_from_api = api.get_user(user)
    for tweet in tweets:
        
        df = df.append({'Tweet' : tweet.text,
                   'Handle'     : tweet.user.screen_name, 
                   'TimeStamp'  : tweet.created_at, 
                   'Likes'      : tweet.favorite_count,
                   #Reply count works with premium api
                   #'Replies'    : tweet.reply_count,
                   'Retweets'   : tweet.retweet_count,
                   'TimeSince'  : int((datetime.datetime.now()-tweet.created_at).total_seconds()),
                   #Sentiment needs recalibrating for time periods over a 24hrs for a week reduce time scaling factor or even remove it.
                   'Sentiment'  : (1/(100000*(int((datetime.datetime.now()-tweet.created_at).total_seconds())/3600)*user_from_api.followers_count)) * (( tweet.retweet_count* 5) + (tweet.favorite_count * 0.5))},
                  #ImpulsedSentiment - time derivative version of this, taken over two instances will deliver impact rating and help detect high impact tweets before the 'alpha' is lost
                  #^ Can introduce a time variable or take two separate instances of csv and manually compute with delta sentiment / delta time.
                  # Alternatively  can introduce time taken to hit certain metric eg, 100 likes/RT's or sentiment score 
                   ignore_index=True)
    ```

[gleaming geyser]

hi i need help with this exercise
create a hash table which is pre assigned with a size and filling-ratio in between 0.0 - 1.0
Hashtable<K, V> ht = new Hashtable<K, V>(int size, float fillRatio);

[shut inlet]

@tepid bear their answer output is 3, and i coded out your solution and got 4 as you said. do you know where the difference is coming from?

[tepid bear]

Hmm

Yea my solution does produce 4 so you did that right

sunday
saturday

I have no idea how you can do it in 3

[shut inlet]

okay no issues. yeah, i have no idea how their dp solution works either haha

[tepid bear]

You want to make str1 == str2 right?

Can you send their solution?

[shut inlet]

yeah sure

def editDistance(str1, str2, m, n):
 
    # If first string is empty, the only option is to
    # insert all characters of second string into first
    if m == 0:
        return n
 
    # If second string is empty, the only option is to
    # remove all characters of first string
    if n == 0:
        return m
 
    # If last characters of two strings are same, nothing
    # much to do. Ignore last characters and get count for
    # remaining strings.
    if str1[m-1] == str2[n-1]:
        return editDistance(str1, str2, m-1, n-1)
 
    # If last characters are not same, consider all three
    # operations on last character of first string, recursively
    # compute minimum cost for all three operations and take
    # minimum of three values.
    return 1 + min(editDistance(str1, str2, m, n-1),    # Insert
                   editDistance(str1, str2, m-1, n),    # Remove
                   editDistance(str1, str2, m-1, n-1)    # Replace
                   )
 
 
# Driver code
str1 = "sunday"
str2 = "saturday"
print(editDistance(str1, str2, len(str1), len(str2)))```

[lunar jacinth]

Could someone explain to me how i could implement radix sort using doubly linked lists?

[gleaming geyser]

hi i need help with this exercise
create a hash table which is pre assigned with a size and filling-ratio in between 0.0 - 1.0
Hashtable<K, V> ht = new Hashtable<K, V>(int size, float fillRatio);

my deadline is after 1 hour

im stuck

[tepid bear]

I still have no idea how it's possible to do it in 3 moves :D

[shut inlet]

haha no issues at all. thanks for your help anyway 🙂

[tepid bear]

Np but I still wanna figure it out😝

On what site are you doing the task?

[shut inlet]

alright bet 🙂

and it's https://www.geeksforgeeks.org/edit-distance-dp-5/

[tepid bear]

Ahhh

You can use replace too

I dunno why but I didn't see that hahah

That makes sense now lol

Yea that makes it way more complicated

[shut inlet]

i gotcha. yeah totally. i need to learn dp to understand this better haha

[tepid bear]

You know freeCodeCamp?

They have a huge video about dp

[shut inlet]

okay i'll check it out after work. lol i was doing these algos at work for my next interview which is in 9 days

[tepid bear]

Uii nice good luck 🤞

[shut inlet]

ty ty 🙂

[lunar jacinth]

Can someone help me implement a radix sort using my doublylinkedlist?

[tepid bear]

Nop sorry but I am sure there are some yet videos die you already check that?

[dapper sapphire]

constant extra space is O(1)?

[tepid bear]

well now that i took a closer look at it my solution doesnt make any sense. yea you need dp for that problem

[dapper sapphire]

If we store elements in a hashmap or dictionary that wont be constant extra space? Unless we just stored 1 number

[shut inlet]

okay i gotcha. do you have the link for dp video by any chance? i only found articles so far

[tepid bear]

https://www.youtube.com/watch?v=oBt53YbR9Kk&t=6128s

[shut inlet]

thanks!

[lunar jacinth]

    def countingSort(self,n,exp):
        my_list = [SList() for i in range(0,10)]
        output = [0 for i in range(0,len(my_list))]
        sorted_list = [0 for i in range(0,n)]

        for i in range(0,n):
            sorted_list[(my_list[i]/exp %10)] += 1
        
        for i in range(1,n):
            sorted_list[i] += sorted_list[i-1]
        
        for i in range(n-1, 0):
            output[sorted_list[(my_list[i]/exp) % 10] -1] = my_list[i]
            sorted_list[(my_list[i]/exp) % 10] -= 1

        for i in range(0,n):
            my_list[i] = output[i]
``` Does anyone know if i'm on the right path to implementing a radix sort using doublylinkedlists?

[lunar jacinth]

I have to somehow convert the CountSort algorithm to use an Array of DoublyLinkedLists

[reef remnant]

bro i bet 99% of the questions in this channel are from homework

(and sorry i can't help you)

but im looking rn and half of them are just copy pasted lol

[lunar jacinth]

im confused lol. i'm trying to use data structures to implement a counting sort algo

[reef remnant]

well i will tell you a couple things

range(0, n) can just be range(n)

also

change range(n-1, 0) to range(n-1, 0, -1)
i don't think the step argument is implicit like that

and you should say -1

i think

also a cleaner way to say output = [0 for i in range(0,len(my_list))] is just output = [0 for i in my_list]

[lunar jacinth]

I'm still a bit confused on this, does anyone have experience implementing radix sort on linked lists?

[bold lake]

https://www.geeksforgeeks.org/radix-sort/ here it s given @lunar jacinth

[fiery cosmos]

is simply using sorted() mean you're using O(nlogn) space?

(even if you're just overwriting the input array, not storing it in a new array)

[ivory yacht]

Sorting is O(n log n) in time complexity, not space. list.sort() does allocate some temporary memory to store parts of the array that it's sorting, but not significant amounts of it.

[fiery cosmos]

the algos cheatsheet says Timsort uses O(n) space

[ivory yacht]

That matches a quick look at the code.

It's here by the way, if you're comfortable with C:
https://github.com/python/cpython/blob/main/Objects/listobject.c#L1051

[halcyon plank]

Objects/listobject.c line 1051

/* Lots of code for an adaptive, stable, natural mergesort.  There are many```

[ivory yacht]

If you use keys of course it'll also have to allocate memory to store those results.

[knotty magnet]

mergesort has to use an auxiliary array. there are in place versions, but i think there are some other issues with them which is why they aren't used

[fiery cosmos]

weird the video I'm watching says the algorithm is O(1) space because it's sorted in place

he uses input_arr.sort()

in the function

I guess he is wrong because it's actually O(n) for Timsort

[knotty magnet]

https://github.com/python/cpython/blob/main/Objects/listsort.txt you can read about it here

[stable mason]

if i use a gradient for node values for A* how can I make a heuristic for that? I'm converting from euclidean.

[lunar jacinth]

Could someone help me with a sorting algo in #help-pear ?

[dapper sapphire]

How do people learn new algorithmic techniques?
What I mean is you let's say you have a problem and your brute force, but that problem can also be solved using hashmap or dictionary. So how did you learn this hashmap technique?

Do you read other people's code and solutions to pick up these and other techniques?

[keen hearth]

I think it's pattern matching essentially. Most algorithmic problems fall into a a few categories. You can learn these by:

1. studying them formally by taking an algorithms course or reading a text-book; and
2. practicing!

[keen hearth]

But it helps to learn general principles. For example trading-off memory for speed; that's what you're doing when you use a hash-map for caching.

[dapper sapphire]

I agree, I felt that too that solving problems really comes down to recognizing patterns. I do practice, but I havent really gone through a data structures & algorithms course or book properly, so I think that might give me exposure to additional patterns that I am not aware of.

[shut inlet]

do you have to learn all the data structures well to solve algorithmic problems?

i only know the very basics, which is why i probably struggle

[dapper sapphire]

It depends, some questions might rely on the data structures that you already know and dont require too much thinking, you will be able to do these easily. Example, is string a palindrome

Some questions rely on data structures that you already know, but require a bit more thinking. Example how many palindromes are there in a string.

If you dont know a data structure I can see two possibilities, you simple cant do a question that solely rely on it. Or you might not be able to optimize some of your solutions.

As LX mentioned above about hash-map and caching. If you dont know these then some of your solutions might not be as efficient/optimized, but you can still brute force these.

[vocal gorge]

I participated in one programming competition* in my school years in which more than half the problems ended up being solved by binary search. The problem was to figure out how to do so, but fundamentally this one basic algorithm pulled a lot of weight. So no, often you don't need to know fancy stuff, just apply basic knowledge to new problems.
*(No, I did not do well on it).

[shut inlet]

ah, okay that makes sense. i guess i know the basics but not like stuff that i don't use in everyday life such as hashmaps and BST and what not

arrays, strings, lists i've got down

[knotty magnet]

hashmaps are one of the most important and useful data structures. it would be useful to learn about them

[fiery cosmos]

aka dicts in python

[main flower]

Having a bit of knowledge on some basic data structures and algorithms is important, but at the same time you will never find a problem in any official contest saying e.g. "Implement segment tree" but you will rather have to come up with a clever way to speeding up your program

So, learn data structures and algorithms, but don't forget that most of the work has to be "adhoc" and there is no better way to learn it than practice

So If you want to learn a new technique then read more about it and google some problems (e.g. on codeforces) to apply it

[lunar jacinth]

    def countingSort(self):
        newArr = []
        big_list = []
        for i in range(0,10):
            newNode = Node()
            newNode.data = i
            newArr.append(newNode)
        
        random_list = []
        for i in range(0,100):
            x = random.randint(1,10000)
            random_list.append(x)

        _max  = int(max(random_list))
        _min = int(min(random_list))
        _range = _max - _min + 1
        print(_max, _min, _range)

        count_arr = [0 for i in range(_range)]
``` Could someone help me on radix sort?

i'm trying to sort the numbers according to their radix by appending each number into the right slot in the linked list array of 10

[fervent saddle]

If dicts and sets only resized to a smaller size when you called a certain method or something like that, would there no longer be any problem with deleting from them while iterating, or would there still be an issue with doing that?

[fair prairie]

Where shall I learn dsa in python

Can*

[knotty magnet]

check the pins

[bleak pagoda]

Hi guys, I don't really know where to ask, but how many numbers are between 100_000 and 999_999?

Including both numbers

I just wanna know what the total possible integers would be if I ran randint(100_000, 999_999) forever

[vocal gorge]

inclusive? between a and b inclusive there's b-a+1 numbers.

(That's why Python's range convention where b is exclusive is nice - in range(a,b) there's exactly b-a numbers).

[bleak pagoda]

That's perfect man, thank you 🙂

[jolly mortar]

randint is the only exception to the lower-bound-inclusive-upper-bound-exclusive thing

that i know of

[knotty magnet]

(that's why everyone likes inclusive start exclusive ends more)

[old rover]

i am revising my OOP knowledge (more like understanding it for the first time)

and i got a question

Is a class attribute just a variable inside of a class?

i think so right?

if you want to use an instance method
You have to create an object from it
And then use that method in the class in dot notation?

How do parent and child classes work? What’s the point? Is it inheritance? Does it gain the methods in the parent class along with the attributes??

i like the way I analyze now

Pomodoro technique is working wonders

[shut breach]

I'm gonna answer your questions in #software-architecture since this doesn't really have anything to do with DSA

[random shoal]

dude subtract them

[bleak pagoda]

wrong 😛

[bleak pagoda]

@random shoal look here

[random shoal]

yes thats correct

[shut breach]

that isn't related to DSA

[lean dome]

Iterating over a dict or set gives predicable behavior so long as the hash table does not grow or shrink while you're iterating over it. So, yes, deleting things while iterating would be safe if you could delay the shrinking.

[hidden raft]

I'm trying to generate a random path between two points on a grid but I'd like it to have a few larger twists and turns so it's longer than a near perfect path. I've tried using a randomly weighted a* but that still generated fairly optimal paths. Adding random obstacles worked relatively well but it was a naive approach that commonly resulted in no paths being available and the obstacles with the path needed to be regenerated because of that.
Is there something which would be more suited to this kind of a problem?

[austere sparrow]

Maybe you could take a look at Slitherlink puzzle generators, like this one https://github.com/ghewgill/puzzles/blob/master/loopgen.c (from sgtpuzzles)?
Frankly speaking, I have no idea how they work, but they manage to create a pretty intricate closed loop on a grid.

or maybe just place "fake"/"virtual" obstacles (and ensure that they don't block the passage) so that they deform a path? nvm, I didn't read properly

[vocal gorge]

No idea if that's a good way, but you could generate a straight path, make an utility function that incentivises a longer length and maybe a specific number of turns, and then use something like simulated annealing to go from the straight path to one optimizing that function

[austere sparrow]

you're making some sort of game AI? or maybe I'm misunderstanding the purpose

[stable pecan]

i have a maze generator that prefers longer paths --- somewhere

you could just outline the maze afterwards

maybe i should read the original question --- yeah, you could just modify it to only generate the first path i guess

i dug up the code, it's not pretty, but maybe it can be hacked on

def gen_maze_longer_paths():
    G = nx.grid_graph(DIM)
    tree = nx.Graph()
    old_node = choice(list(G))
    tree.add_node(old_node)
    all_neighbors = Setch(*G.neighbors(old_node))
    while tree.order() < G.order():
        neighbors = [node for node in G.neighbors(old_node) if node not in tree]
        if neighbors:
            new_node = choice(neighbors)
            neighbors.remove(new_node)
        else:  #Dead-end
            new_node = all_neighbors.choose()
            nodes_in_tree, neighbors = [], []
            for node in G.neighbors(new_node):
                (nodes_in_tree if node in tree else neighbors).append(node)
            old_node = choice(nodes_in_tree)
        all_neighbors.remove(new_node)
        tree.add_edge(old_node, new_node)
        all_neighbors += neighbors
        old_node = new_node
    return tree

[hidden raft]

I only need it to generate the path for the user - so for example something like this https://i.imgur.com/G3shAIC.png is all it needs to achieve. The random placement worked (although I didn't check for it blocking the path, just regenerated) but on small grids it still usually went for an almost straight path

[stable pecan]

can you do some random depth first walk to the end point

like, if you hit an edge or the path, back up and keep going

[hidden raft]

I'm not knowledgeable with the theory around this, how would that look?
The cells are currently stored in a 2d list (moved from a flat list for clearer access)

[shut breach]

the grid is just a graph where neighboring cells are connected nodes
with (randomized) DFS you choose a random neighbor of each node, keep track of visited nodes, and backtrack when you run out of unvisited neighbors

the result will be some kind of random, but I don't think you can make any strong guarantees about what it will look like that way

[shut breach]

I kind of like this approach of mutating a straight path with some sort of objective function, just the length of the path would probably work

[hidden raft]

Where would the algorithm stop backtracking? When a cell with unvisited neighbours is encountered?

[tepid bear]

I think his approach is to not visit all neighbors

And always choose one neighbor randomly until you get to the end

[stable pecan]

you stop back tracking when you get to the target end point

[sinful pier]

i shall use this technique thank you for the idea.

[shut breach]

i think the other's misunderstood the question, but yes you'd stop backtracking as soon as you can go forward again

alternatively, you could try maintaining a set of nodes on the "frontier" of your visited nodes, and choose randomly from that set each time

not sure what the differences in the outcomes would be, I don't think I've ever tried to do randomized graph search before

[stable pecan]

!e

import random

GRID_DIM = 5, 5
START = 2, 0
END = 2, 4

def random_valid_neighbor(point, dimensions, seen):
    y, x = point
    height, width = dimensions

    neighbor_deltas = [
        (0, 1),
        (0, -1),
        (1, 0),
        (-1, 0),
    ]
    random.shuffle(neighbor_deltas)

    for dy, dx in neighbor_deltas:
        if 0 <= y + dy < height and 0 <= x + dx < width:
            neighbor = y + dy, x + dx
            if neighbor not in seen:
                seen.add(neighbor)
                return neighbor

def random_depth_first_search(start, end, dimensions):
    path = [ start ]
    seen = { start }

    while path[-1] != end:
        if neighbor := random_valid_neighbor(path[-1], dimensions, seen):
            path.append(neighbor)
        else:
            path.pop()

    return path

def print_path(path, dimensions):
    height, width = dimensions
    grid = [[" " for x in range(width * 2 - 1)] for _ in range(height * 2 - 1)]

    last_y, last_x = path[0]
    for y, x in path:
        grid[last_y + y][last_x + x] = "*"
        grid[2 * y][2 * x] = "*"
        last_y, last_x = y, x

    print("\n".join("".join(row) for row in grid))

path = random_depth_first_search(START, END, GRID_DIM)
print_path(path, GRID_DIM)

[halcyon plank]

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

001 | *******    
002 | *     *    
003 | ***   ***  
004 |   *     *  
005 | * ***   *  
006 | *   *      
007 | *   ***    
008 | *     *    
009 | *******    
010 |            
011 |            

[stable pecan]

i mixed up my dimensions in the last function

but jokes on me, they're the same anyway

fixed

[hidden raft]

The thing I made which seems to be the same thing as above works well https://paste.fuelrats.com/jiyetuxoxo.py, but maybe a bit too well for larger grids where the path becomes overly complex - https://i.imgur.com/xYL4M9V.png

[old rover]

Good move 🙂

[stable pecan]

yeah, i found the same, for larger grids the paths are very windy

[hidden raft]

the cell holes highlighting the path could be clearer but even with it shown it's hard to navigate, do you think adding a optimized neighbour pick instead of random could help here?

[stable pecan]

this is possible to weight the neighbors by how close they are to the exit

this would only require a small change in random_valid_neighbor or whatever similar function you might have

[hidden raft]

            if random.random() < .5:
                current_cell = min(valid_neighbours, key=lambda cell: abs(end.x_pos - cell.x_pos) + abs(end.y_pos - cell.y_pos))
            else:
                current_cell = random.choice(valid_neighbours)

I tried this - the paths generated are straight but if the random neighbour makes a few consecutive turns the section around it gets mangled. But I'd like to avoid straight runs like here for example (and the middle section is a mess even with the (naive) optimized neighbour search https://i.imgur.com/TY1Eby1.png)
I wonder if prioritizing straight runs up to some length could make it more consistent

So it'd make a random choice, then with some possibility it'd continue in the current direction instead of an another completely random choice

[stable pecan]

i would use random.choices to pick from the weighted cells -- instead of always picking the min

just use k=1

current_cell = random.choices(valid_neighbors, [1 / (.001 + abs(end.x_pos - cell.x_pos) + abs(end.y_pos - cell.y_pos)) for cell in valid_neighbors], k=1)[0]

might need to inverse the weights

[hidden raft]

a weighted random seems to be about as twist and turny as the original completely random approach

[stable pecan]

might depend on how one weights it

admittedly i made a pretty bad weighting above

[hidden raft]

Yeah maybe skewing it to the nearest could help, but I think with a naive distance algo like that it'll commonly end up wrong (the nearest cell may not be the one with the shortst path)

I'll try out the straight runs in a bit and see how that goes

[shut breach]

I would try having it prioritize choosing a neighbor where it can move two spaces in the same direction

or the neighbor where it can move the furthest forward up to a cap

something like that

[hidden raft]

Haven't been able to really get anything I'd be satisfied with on larger grids, will try if limiting tight U turns helps tomorrow

[lunar jacinth]

    Alpha(arr, i) 
        start = 0                     C0
        while start < i               N
           temp = arr[start]          C1
           arr[start] = arr[i]        C2
          arr[i] = temp               C3
            start += 1                C4
           i -= 1                     C5

    Beta(arr, n)
        m = 0                         c6 
        for i = 0 to n                N
            if arr[i] > arr[m]        c7
                m = i                 c8
        return m                      c9

    Gamma(arr, n) 
        curr_size = n                 c10
        while curr_size > 1            N
            m = Beta(arr, curr_size)   N
            if m != curr_size-1       c11
                Alpha(arr, m)          N
                Alpha(arr, curr_size-1) N
            curr_size -= 1              C12
```Could someone help with finding out the time complexity of this?

[lean dome]

What do you think the answers are?

[lunar jacinth]

I'm still kind of on the first function and was wondering if that was correct

O(n) for Alpha

[lean dome]

yep, that's correct.

[lunar jacinth]

oh okay im kind of confused on how to determine like which line is constant

and which line is linear

and then I believe following the same way, Beta is also O(N)?

if im doing this correctly?

[lean dome]

yes, that's also correct.

"which line is linear" and "which line is constant" is the wrong way to look at it. The right question is how many times each statement gets executed when the function runs.

[lunar jacinth]

would m = i be considered constant time though?

or just like nothing?

[lean dome]

everything is "something" - nothing is totally free, the smallest time complexity that anything can be is constant time

[lunar jacinth]

ah okay true, that makes sense

okay but gamma is where im completely lost...

[lean dome]

what time complexity tells you isn't how slow or fast something is, it's how much slower or faster it gets as the size of its input increases

[lunar jacinth]

for gamma it seems that curr size. = n and then it gets put into the while loop

[lean dome]

okay but gamma is where im completely lost...
Start with this: how many times does the while loop body run?

[lunar jacinth]

it depends on n right?

[lean dome]

right - which tells you that it's not constant time. but everything above constant time depends on N

if N is 50, how many times does the while loop body run?

[lunar jacinth]

49 times

the while loop makes it O(n) right

[lean dome]

minimum

[lunar jacinth]

and then call tthe Beta function makes it O(n) so now we have n^2?

[lean dome]

yes, that's correct

[lunar jacinth]

if m != curr_size-1
``` this doesnt make it linear or anything i believe

just constant

wait actually it has size

wait actually, no its constant

but that if statement gets executed multiple times tho.. lol

would that make it no constant?

[lunar jacinth]

I believe that ```py
if m != curr_size-1