algos-and-data-structs

[brave oak]

why?

the bboxes should be 1000x3

why is there a 6 in there

okay

think of it this way

[brisk aurora]

because it's a bbox point per plane

[brave oak]

any point

(P, B, C) should give you the value for plane P, bbox B, and coordinate C

[brisk aurora]

it's mimicking this code:

def is_bbox_contained_or_intersects(self, bbox_min: Vector3, bbox_max: Vector3) -> bool:
    for plane in self._planes:
        bbox_x = bbox_max[0] if plane[0] > 0 else bbox_min[0]
        bbox_y = bbox_max[1] if plane[1] > 0 else bbox_min[1]
        bbox_z = bbox_max[2] if plane[2] > 0 else bbox_min[2]

        dot = plane[0] * bbox_x + plane[1] * bbox_y + plane[2] * bbox_z

        if dot < -plane[3]:
            return False

    return True

[brave oak]

isn't the number of bboxes

independent of the number of plaanes

[brisk aurora]

yes, it is.

there are two points per bbox - min and max.
Per plane, I want to decide what x,y,z component to take from bbox_min or bbox_max, according to if the plane component is positive

i.e.:

        bbox_x = bbox_max[0] if plane[0] > 0 else bbox_min[0]
        bbox_y = bbox_max[1] if plane[1] > 0 else bbox_min[1]
        bbox_z = bbox_max[2] if plane[2] > 0 else bbox_min[2]

so per plane I want a bbox_x, bbox_y, bbox_z.
I have 6 planes. 1000 bbox_min and 1000 bbox_max (i.e. 1000 bboxes total).
so 6x1000x3

no? 🙂

[brave oak]

6x1000x3 is the result of np.where

then you take that and dot against the subset of planes

which will be 6x1x3

[brisk aurora]

how do I do that dot?

that's my problem now

from numpy.dot help:
If a is an N-D array and b is an M-D array (where M>=2), it is a sum product over the last axis of a and the second-to-last axis of b:

[brave oak]

actually

I think you don't?

just multiply elementwise

then sum

[brisk aurora]

hmmm

I see. Isn't that less optimized/performant or something?

[brave oak]

why would it be

hm

it COULD be

[brisk aurora]

lol why?

so with multiply and sum , something like this:
np.sum(np.multiply(planes_normal[:,None], bbox), axis=-1)

[brave oak]

because

there might be BLAS/LAPACK rountines

routines

that optimise the interediatei multiplciation

I can't spell

sorry

[brisk aurora]

multiply 6x1x3 (the planes_normal, added 1 for broadcasting), by 6x1000x3. Get 6x1000x3. Then sum the last axis.

[brave oak]

also yo ucan just do

and .sum()

instead of using the free functions

[brisk aurora]

sum with axis=-1, right?

Can you think of a way to do this with np.dot, np.tensordot or np.inner directly instead of multiply + sum? To "get" these BLAS optimizations

what I can't figure out is how to connect the two 6 in planes_normal and bbox. I want to say: For each index in the 6x3 planes_normal, i.e. planes_normal[0], do the dot product with bbox[0][n]

@brave oak OK I think I have an answer:
https://stackoverflow.com/a/64285103
can't use dot or tensordot. Should use matmul or einsum (oh god)

[brave oak]

yeah einsum is king

but I don't know how to do it

if you see salt rock lamp around

[brisk aurora]

I'll try

[brave oak]

they're pro @ einsum

basically

anyone with salt in their name

is pro @ einsum

[brisk aurora]

lol

what I'm trying to figure out as well is if it's possible (or even logical in numpy) to not calculate the dot product for further planes + bbox if a dot product of a previous plane and bbox is smaller than the plane distance.

like, I can do early exits in a lot of the bboxes if you get what I mean. And in the numpy solution, I calculate everything

[brave oak]

do you know

if this will not be fast enough?

[brisk aurora]

not yet, hence I'm not focusing on that question 🙂

[brave oak]

I'm not sure

[brisk aurora]

but it is interesting how to generally do that in numpy

[brave oak]

if this is possible

because it's path dependence

like

the whole foundation of vectorisation

is that each calculation is independent

the corollary is that

it would have had to be performed in any case

[brisk aurora]

yeah

@brave oak

NUM_ELEMENTS = 1_000_000
planes = np.random.normal(size=(6, 4))
bbox_min = np.random.normal(size=(NUM_ELEMENTS, 3))
bbox_max = np.random.normal(size=_NUM_ELEMENTS, 3))

planes_normal = planes[:, :3]
planes_greater_than_zero = planes_normal > 0

start = time.perf_counter_ns()
bbox = np.where(planes_greater_than_zero[:, None, :3], bbox_max, bbox_min)
end = time.perf_counter_ns()

This takes 170millis (the bbox = ... line).
Which is much faster than my python only version, but just wondering - it's 170ns (nanoseconds) per element.
Isn't that still a lot for literally checking this:

bbox_x = bbox_max[0] if plane[0] > 0 else bbox_min[0]
bbox_y = bbox_max[1] if plane[1] > 0 else bbox_min[1]
bbox_z = bbox_max[2] if plane[2] > 0 else bbox_min[2]

like, a cycle on a 4GHz cpu like I'm running is 0.25ns. so that's 680 cycles to do that?

[brave oak]

uh

I am not experienced enough in computer engineering

to say anything about that

but

a lot of it could be function call overhead?

[feral hound]

its because each instruction is in machine code

and its not like your pc is just running your code its doing a lot of other stuff at the same time

[idle pier]

hello folks, almightypush here with another question lol

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node,left,right):
            if not node:
                return True
            
            if not (node.val < right and node.val > left):
                return False
            
            return (valid(node.left,left,node.val) and valid(node.right, node.val, right))
            
        return valid(root,float("-inf"),float("inf"))```
I understand most of the code, am just having trouble grasping the second to last return statement

[feral hound]

are you sure this is correct?

@idle pier

[idle pier]

yup

[feral hound]

ok then maybe I'm misunderstanding something

but to check if a binary tree is valid each nodes left has to be smaller than itself and its right has to be bigger correct?

ok nvm I get it now I was just missing the fact that all nodes on the left have to be smaller and all nodes on the right have to be bigger

this makes sense

[knotty magnet]

that's a weird way to do it, but i guess it eliminates the is None checking, so i guess it isn't weird?

[feral hound]

btw I would call left and right lower bound and upper bound

makes more sense that way

and if you change your if statement to

if node.val > right or node.val < left:

it will be easier to understand

so this

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, lower_bound, upper_bound):
            if not node:
                return True
            
            if node.val >= upper_bound or node.val <= lower_bound:
                return False
            
            return (valid(node.left, lower_bound, node.val) and valid(node.right, node.val, upper_bound))
            
        return valid(root, float("-inf"), float("inf"))

@idle pier does it make more sense like this?

and what part of the second to last return dont you understand?

[idle pier]

so I know its recursive but thats about it lol

[feral hound]

forgot to change it to upper and lower bound in the if lol

well think about each branch one at a time

ahh also one thing I forgot

need to check if its equal as well now

man its hard to explain recursion without illustrations

do you understand recursion in general?

[idle pier]

I understand thats the recursion part and I know how recursion works in general

[feral hound]

is it more difficult because its branching?

[idle pier]

so for that particular return statement, is it just recursing? If that makes sense lol

[feral hound]

I guess?

basically it calls the function again and waits until that has return then that cascades down back into it and it uses that boolean value

so it verified that the current node was correct so it checks if both the right and left nodes are correct

in terms of how it works one side will be fully evaluated first before moving on to the next im not 100% sure if its left or right first in python but it doesnt really matter to us so lets assume it goes with right side first

[idle pier]

hmmmmmm ok ok, now am getting a better understanding

[feral hound]

the idea is
check current node is correct then check if left node is correct then check if left nodes left node is correct and so on until there is no more connection

at the end when you reach the terminal node the result will start travelling back up

and the right side will be evaluated working its way back up

animations would make this a lot easier tbh lol

[idle pier]

thanks, I have a better understanding now

[feral hound]

wait I got some illustrations this should clear everything up

and there we go

[idle pier]

ohhhhhh ok ok, so it goes through every branch

[feral hound]

if any of those evaluated to false it would travel back up and return invalid instead

im pretty sure in pyhton if you put and in your if statement it will wont bother checking the second statement if the first one was already false

so as soon as its invalid it instantly travels back up instead of checking the other nodes

[idle pier]

and my solution is O(N) correct? Since it goes through every N

[feral hound]

I think so yes

it only checks each node once

do you want me to show you an example of it being invalid?

[idle pier]

No thanks, luckily I know what it is. I was just having trouble understanding that specific return statement

[feral hound]

all makes sense now?

I essentially only showed you what the return was doing in these illustrations

[idle pier]

💯

[feral hound]

ngl though im annoyed that I skipped a bit at the beginning

[idle pier]

I have another question, how should one go about during a virtual interview? I know one should never jump straight into coding(I found out the hard way lol)

[feral hound]

no idea but I think you might have more luck asking here #career-advice

[fiery cosmos]

Very good explanation

How do I convert a string into a unique id for the binary tree?

[knotty magnet]

why does hashing not work?

[fiery cosmos]

I mean in time to hash and collisions is a problem for a binary tree.

[knotty magnet]

why do you need a unique int in the first place?

[fiery cosmos]

to store it as a key in my binary tree, it only works with int.

[knotty magnet]

collisions are quite rare, i don't think that'd be an issue

have you tested it and found that to not be true?

[fiery cosmos]

I didn't check if it's true, but I want to avoid it.

[knotty magnet]

there's no problem to avoid

collisions are rare

[fiery cosmos]

'rare'

[knotty magnet]

have you done any testing that would indicate otherwise

[fiery cosmos]

Strings can be compared with < > == just like ints so order should not really be a problem and equal values don't necessarily break things if left tree means <=

but if you have duplicate values maybe a binary tree is not the best ds to use?

[knotty magnet]

you can deaal with dupes in a binary tree in a few waays though

[fiery cosmos]

You convinced me even though I didn't want to.

[knotty magnet]

huh? just do some testing to verify

[austere sparrow]

if you want to store strings in a binary tree, you can't avoid using all the information in each string.

So just use normal lexicographical comparisons

You can't compress arbitrary amount of information into a fixed amount of space, so if you do make some kind of integer out of a string, it will occupy as much space as a string

[idle pier]

hello folks, almightyPush with another question here
am currently doing twoSum on leetcode, this is my solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left,right = 0, len(nums)-1
        
        while left < right:
            curr = nums[left] + nums[right]
            if curr < target:
                left += 1
            elif curr > target:
                right -= 1
            else:
                return [left,right]
            
        return [-1,-1]```
when I submit it gives an error but I know it works, I think am returning the wrong thing on leetcode

[long orbit]

Anyone know of a module for financial modeling? I want to run some simulations but feel like I'm going to have to reinvent the wheel to do it.

[feral hound]

I would say ask in #data-science-and-ml

[feral hound]

what does it tell you?

should say output vs expected

[knotty magnet]

what's the error?

[feral hound]

ahh i know what your issue is

you assumed that the list was sorted

its not

[vocal gorge]

I know it works
I don't think it does. What if, say, you have [5,5,0,0,0] and target is 10? Your code can never find the 0,1 solution because it only decrements right when the current is below the goal.

[stiff hound]

Te

[narrow cape]

Does anyone know what kind of list 'edge' is?

What values it holds etc

Because I can't wrap my around over it

Here's the full algorithm

[feral hound]

I'll be honest not 100% sure but the only thing I think it can be is u is current node v is destination node

[eager frost]

A tuple of (start, end)-values

So the "connection"(=edge) between vertices. Also each edge has a weight associated to it (w).

or did I miss the question

[feral hound]

looking back on it now im 100% sure now

[feral hound]

this seems to be pseudo code so no tuples but what your saying is correct

[eager frost]

Specifically, u is the start-vertex and v is the end-vertex

ye

just realized

alphabet is hard

[feral hound]

^^ it do be like that

[fiery cosmos]

I did not understand what you are talking about

is there any downside to using > or < in strings?

[knotty magnet]

not really

[feral hound]

string comparison is slower than integer comparison however the time that the hash function would need to create a hash from your string would probably be longer than all the string comparisons you will need to do combined

[knotty magnet]

the hash has to look at each character anyway, which the comparison was already gonna do

[feral hound]

and are you thinking that you need a hash because dictionaries/hash tables use them?

[fiery cosmos]

don't necessarily need a hash

[feral hound]

btw even if there are collisions there are a lot ways that you can choose to deal with them

[fervent saddle]

random import randrange
from collections import defaultdict

result = [0] * 100

ranges_dict = defaultdict(int)

test_ranges = [
    ((start := randrange(101)), randrange(start, 101))
    for _ in range(10)
]

for r in test_ranges:
    ranges_dict[r] += 1

for r, increase in ranges_dict.items():
    for ind in range(r[0], r[1]):
        result[ind] += increase

print() # some of the text was blocked on repl.it
print(test_ranges, result, sep="\n- - -\n")```

Is there a better way to do this?

Basically, you have a list where each value starts at 0, and you have a bunch of random ranges, and for each range, you increase the list’s value by 1 through the whole range

I saw someone trying to do this by going through each range one by one. So that was O(len_of_list * how_many_ranges)

But this still isn’t very good, it’s O(len_of_list**2 + how_many_ranges)

Is there a better way?

[knotty magnet]

hmm, if you store the starts and ends of the ranges in a list, sort by value

then when you find a start, increment a counter, when you find an end, decrement the counter

write the value of the counter into the list on each iteration

@fervent saddle

[fervent saddle]

I’m storing the ranges in a dict now

[knotty magnet]

i think that solution would be O(n log n + m), where n is num_ranges and m is len(list)

[fervent saddle]

How does each range know where it ends?

[knotty magnet]

that doesn't matter, since it only matters that a range ended

[fervent saddle]

I think I’m kind of seeing what you’re talking about

You use a counter to see how deep you are in ranges

[fervent saddle]

That’s phrased pretty bad, I hope that makes sense lol

[knotty magnet]

yeah, i get what you mean

if you sorta think of it like

               i'm here
                  |
 -----
             --------
          ----------
                     -------
           -------------
``` i'd be 3 deep in ranges

[fervent saddle]

Yeah

Ok, I’ll try it that way when I get the chance. Thanks

You wouldn’t need to sort of the starts and ends are within a reasonable limit, right?

Actually

Yeah, the most extra space is proportional to the size of the list, I think

What I’m thinking is something like, you get the range (5, 10). Then you add 1 to index 5, and -1 to index 10, or something along those lines

[knotty magnet]

you have to sort because then the counter is out of sync

oh so instead of sorting, just cache when to subtract and add 🤔

[fervent saddle]

Yeah

[knotty magnet]

that could work yeah

[fervent saddle]

I’m gonna try it when I get the chance

[tropic glacier]

I'm confused, what's the actual problem one is trying to solve?

[keen hearth]

I think they're given a collection of ranges, and for each index in a list they have to determine how many of the ranges that index lies within.

[knotty magnet]

#algos-and-data-structs message

[tropic glacier]

I see. And how are the ranges provided? Just unordered?

[fervent saddle]

Here’s the person’s original question:
#help-chestnut message

[knotty magnet]

cc @candid elk

[tropic glacier]

yeah, I don't feel like that code snippet really explains the problem very well

But let's say I'm given a number k and a bunch of ranges, and I want to know how many ranges k is inside, is that the basic idea?

[fervent saddle]

I think so, yeah

[tropic glacier]

k in range(start, stop)

is of course constant time, since it's just

start <= k < stop

So, if I have n ranges and m numbers I want to check against them, then I can do this in O(m n)

[feral hound]

this is the problem correct?

[fervent saddle]

Yeah

[tropic glacier]

I mean m positions

[fervent saddle]

Right, yeah

[feral hound]

and you dont know the minimum and maximum range right?

[fervent saddle]

I just reread it

No

I don’t

[keen hearth]

Except you're missing a dot on the first row.

[fervent saddle]

I guess one could be (5, 10), and another could be (5000000000, 10000000000)

[feral hound]

oops your right

[knotty magnet]

well if it's that big you need a smarter way to store and compute the result

[fervent saddle]

Yeah

So

It depends what his ranges are like

[feral hound]

well its more like I mean the minimum and maximum arent inputs?

so you have to figure that out yourself

[tropic glacier]

But ok, you can also sort all the starts, and separately sort all the stops, and then iterate through your m positions, and instead of doing n comparisons each iteration, you're doing only 1 comparison, and incrementing every time you pass a start, and decrementing every time you pass a stop. So that will be O(n log n + m) as someone mentioned.

[tropic glacier]

Here's a way to do it:

ranges = [(2, 5), (3, 7), (1, 6), (5, 8)]
starts = sorted((start, 1) for start, _ in ranges)
stops = sorted((stop, -1) for _, stop in ranges)
boundaries = starts + stops

positions = list()
count, boundary = 0, 0
for position in range(10):
    if boundary < len(boundaries):
        threshold, delta = boundaries[boundary]
        if position >= threshold:
            count += delta
            boundary += 1
    positions.append(count)

print(positions)

Might have errors. But you get the idea 🙂

[gaunt tangle]

Why does this code gives MLE in this question https://leetcode.com/problems/combination-sum/

def combinationSum(self, c: List[int], t: int) -> List[List[int]]:
        def rec(c,t,a,s):
            for ind,i in enumerate(c):
                if s+i<t:
                    tmp=[j for j in a]
                    tmp.append(i)
                    rec(c[ind:],t,tmp,s+i)
                    rec(c[ind:],t,a,s)
                elif s+i==t:
                    tmp=[j for j in a]
                    tmp.append(i)
                    res.append(tmp)
                    return
                    
            return
        
        res=[]
        a=[]
        s=0
        rec(c,t,a,s)
        print(res)
        return res

test case:

[2,7,6,3,5,1]
9

[idle pier]

ahhh yes I see now

[idle pier]

I know using a hash table is easier to solve but I like this solution because I actually understand whats going on
But for now I can't seem to find the issue

[feral hound]

your solution only works for sorted lists

you see in ConfusedReptiles example the list wasnt sorted so your method failed

the only thing you have to change is to make your solution work is to sort the list first

[vocal gorge]

yeah, though that way is O(n log n) compared to O(n) of the hash table way

it is a working method, though

[feral hound]

it takes less memory though

theres always a trade off I guess

from searching online there were 3 methods people used for this

nested loop n^2 time 1 space
hash tables n time n? space
this method nlogn time 1 space

[vocal gorge]

IIRC Python's timsort is actually not O(1) space

not even when doing it inplace

[feral hound]

what sort does python default to?

[vocal gorge]

https://github.com/python/cpython/blob/main/Objects/listsort.txt#L17-L23

[halcyon plank]

Objects/listsort.txt lines 17 to 23

+ timsort can require a temp array containing as many as N//2 pointers,
  which means as many as 2*N extra bytes on 32-bit boxes.  It can be
  expected to require a temp array this large when sorting random data; on
  data with significant structure, it may get away without using any extra
  heap memory.  This appears to be the strongest argument against it, but
  compared to the size of an object, 2 temp bytes worst-case (also expected-
  case for random data) doesn't scare me much.```

[vocal gorge]

Timsort - it's a very advanced mergesort modification, basically

[feral hound]

hmm might have to look into it

honestly I need to look into sorting algorithms in general...

[idle pier]

hmmm ok I see now

for sorting the list, I just simply use nums.sort() correct

[vocal gorge]

yeah

[feral hound]

btw about this I didnt care before but recently I've started noticing that pythons methods are inconsistent with whether they mutate the object or return a value

am I just missing some kind of pattern in the naming or is it really just inconsistent

[fiery cosmos]

How can I know the number of requests that must be made every 1 a certain amount?

[feral hound]

?

[fiery cosmos]

the amount and period are floating, I need to know how many times I can make requests per period

[vocal gorge]

There isn't a naming pattern, but there is a pattern in that inplace methods always return None, and methods that return the result are expected to not mutate the object

[idle pier]

something like this @vocal gorge ?

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        left,right = 0,len(nums)-1
        
        while left < right:
            curr = nums[left] + nums[right]
            if curr < target:
                left += 1
            elif curr > target:
                right -= 1
            else:
                return [left,right]
            
        return [-1,-1]```

[fiery cosmos]

I Try period / amount but the number is not expected.

[feral hound]

I feel like methods should always be inplace unless they check for some kind of property in the object

!e

cars = ['Ford', 'BMW', 'Volvo']
print(cars.sort())
print(cars)

my_str = 'Volvo'
print(my_str.lower())
print(my_str)

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | None
002 | ['BMW', 'Ford', 'Volvo']
003 | volvo
004 | Volvo

[feral hound]

for example this right here it just doesnt make sense for one to be inplace and the other to return the result

[vocal gorge]

You can know the latter can't be inplace because strings are immutable.

[feral hound]

hmm how come they're immutable btw?

I feel like given the type of language python is it would make sense to use lists to make strings instead of arrays

[vocal gorge]

well, using actual lists internally for strings would be horrifying (20 bytes per character instead of 1-4 :P), but as for why they aren't allowed to be mutable (growing the internal array as a vector) - it was just considered a better choice to have strings immutable by default
https://stackoverflow.com/questions/8680080/why-are-python-strings-immutable-best-practices-for-using-them

[feral hound]

this should work try it

[idle pier]

doesn't work

I just get the wrong first indices but the second one is correct

[feral hound]

couldnt inplace methods just remake the string then?

!e

my_str = 'Volvo'
print(my_str.lower())
my_str += "masd"
print(my_str)

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | volvo
002 | Volvomasd

[feral hound]

since you ca do things like this I dont see why an inplace method couldnt be made for strings

[feral hound]

no idea tbh it should have worked

[fiery cosmos]

How can I get the number of requests that can be made per period?

[idle pier]

I guess its just a leetcode issue then lol

But for a interview that should be a valid response, I think lol

[feral hound]

I would think so

just compared it to a solution on SO to make sure and its pretty much identical

[feral hound]

I feel like more context is needed for this

[fiery cosmos]

I think it's understandable, Number of requests allowed per period.

for the ratelimit

[feral hound]

well I'm not sure but I would think #networks would be a better place for this question

[vocal gorge]

The idea is that if you have a string, you can be sure it won't change, even if someone with another reference to it really wants to change it.

[fiery cosmos]

I tried doing this period / amount allowed, then the condition to block is self.usage> self.amount. But for some reason I'm wrong about something.

[feral hound]

ok I looked through the link again and I see what you mean now so this

my_str += "masd"

actually changes the reference id of my_str leaving the original reference pointing to the same value so it doesn't change the string in other places of the code
or is it just passed by value straight away and a new reference is created every time its passed somewhere?

[vocal gorge]

Yeah, this copies both my_str and "masd" to a newly allocated string, then binds the name my_str to it instead.

in theory, that's what always happens

in practice, because this is extremely expensive, CPython since 2.7 has an optimization

in short, when doing += on strings, CPython checks the refcount of my_str. If it's 1 (so noone else can see the string after the operation, it'll just get dropped), then instead of doing this, it actually tries to grow the internal array of my_str inplace.

this isn't always possible, and it's still not really a true mutable string because it doesn't use a proper vector (with overallocation, etc), but it ends up being quite a massive optimization when it works.

[feral hound]

well I learned some new things its interesting how things really work when you look into it

[knotty magnet]

strings need to be hashable too, that's the biggest thing, probably

[feral hound]

I dont think hash matters at all

since it doesnt actually store a refrence to the string

but only implements a function that computes a certain hash based on the strings value

but using it as a key in a dict would be an issue though

[knotty magnet]

hashable means the hash doesn't change over the lifetime of the object

[feral hound]

ahh fair I misunderstood

[knotty magnet]

although that could be sidestepped if you used some other not-changing value like the id, for instance

although that'd be annoying to satisfy if hash(a) == hash(b) then a == b

[feral hound]

seems id is how user defined class objects are hashed

[austere sparrow]

In CPython, strings compute their hash on creation.

[feral hound]

@vocal gorge thx for all the info btw

[knotty magnet]

wait wuut, i thought it was just cached when it's calculated once

source?

[fiery cosmos]

How can I calculate the complexity of the search in a tree? After understanding that I should pass n as the depth of the tree to log2, I still don't get a satisfactory result.

[knotty magnet]

you shouldn't be plugging any numbers in when you try to find complexity though?

[feral hound]

for complexity you always have a best case average case and worst case

[fiery cosmos]

#algos-and-data-structs message

[feral hound]

and its not about the numbers but how they scale as your data grows

[knotty magnet]

that's not really how you'd find the complexity

[feral hound]

lets use a simple example of linear search

if you use linear search to look for an element in an array with length N

in the best case scenario its the first element and you got O(1) in the worst case its the last element and its O(N) in the average case its gona be O(N)

since N/2 we remove the constants though since those dont change

and to explain why we remove the constants look at this if your array was 100 elements

you would need 50 iterations on average to find the element

if your list is 200 elements you now need 100 iterations

400 elements 200 iterations

and so on

if you plot iterations / elements you will see a straight line

its a linear relationship hench the complexity of O(N)

we dont actually care how long each operation takes just how it will scale with the data

in the case of linear search we know its a 1 to 1 relationship based on this if data doubles time doubles

does that explain it or would you like an example using binary search as well for comparison? @fiery cosmos

[brave owl]

im doing a problem where i have to check if there are no repeating values in a dict, how would i do this?

this is what im trying and its not working

if set(occur.values()) != occur.values():
            return False

[fiery cosmos]

yes, I don't like linear search but it is understandable.

[knotty magnet]

i don't think a set can be equal to a dict_values, try checking the length?

[brave owl]

yeah that worked thanks

i also tried converting the set to a list and it didnt like that either

[feral hound]

btw if your algorithm is really complicated and you cant figure out the complexity you could measure the time at different amounts of data and plot it

and from the curve you get you can determine the complexity

[brave owl]

is it bad that im usually in the bottom 1/3 of runtime on leetcode?

[fiery cosmos]

In fact it is very easy to understand the code, so any idea gives me.

[austere sparrow]

If d is the depth, the number of comparisons to perform to find an element (on average) will be d

(assuming it's a balanced binary tree)

d ≈ log2(n) where n is the number of elements

[fiery cosmos]

Weak balance

[austere sparrow]

Oh right, they do cache the hash. I was wrong
https://github.com/python/cpython/blob/main/Objects/unicodeobject.c#L11786-L11803

[candid elk]

Hi guys! How can I optimize this code?

n, q = map(int, input().split())
mass_n = list(map(int, input().split()))
mass_n.sort()
mass_q = []
for i in range(q):
    x, y = map(int, input().split())
    mass_q.append(range(x-1, y))
inter_mass_n = dict()

for i in range(n):
    for j in mass_q:
        if i in j:
            inter_mass_n[i] = inter_mass_n.get(i,0) + 1

value = list(inter_mass_n.values())
value.sort()
summ = 0

for i in range(len(value)):
    summ += mass_n.pop(-1) * value.pop(-1)

print(summ)```
This code takes n and q as input, then gets an array of length n, which consists of numbers in unsorted form. And also receives q lines with ranges in which to calculate the sum.

Next, I create a dictionary into which I count the occurrence of numbers in the ranges. This is in order to get the maximum amount in this array on the given ranges (that is, you need to rearrange the numbers in the array so that the amount is the largest)

Then I select the maximum number in the array and the maximum number of values that are stored in the dictionary. And so I consider the maximum possible amount

[austere sparrow]

That I don't know about, but it's probably not log(depth), because depth is already log(number_of_elements).

[feral hound]

your code is doing this right?

[fiery cosmos]

is getting close to being avl.

[candid elk]

Yes. This is roughly used to count the occurrences of numbers in ranges.

Sorry if I talk nonsense😄 I speak a little bad English

[feral hound]

if you really wanetd to know what the average case is you would also need to know the frequency that a particular node is called at

have a look at Huffman codes if what I mean doesnt make sense

[fiery cosmos]

The node doesn't have much special

[feral hound]

so every node has the same possibility of being picked?

[fiery cosmos]

no

[feral hound]

?

[fiery cosmos]

@austere sparrow 9.210340371976183604374455171637237071990966796875 in 10,000 elements.

[austere sparrow]

what's that?

[fiery cosmos]

log(n)

[austere sparrow]

I don't understand you

what is 9.21...?

[candid elk]

Huffman code is definitely not suitable for solving this problem🤔 He calculates the sum of all elements quickly, and I just need the maximum sum in some ranges. + it is always implemented with the sys library, which cannot be used for this task. In the condition it was said, it can be dispensed with only by standard python tools without using libraries🤔

@feral hound

[feral hound]

that wasnt for you problem

[fiery cosmos]

I tell myself that it will pass the number of elements to log and that is the result, now the height is 13 so it is not very approximate but with log2 it is.

[feral hound]

your tree can have a minimum height and a maximum height

log2 assumes it is completely balanced

[candid elk]

Ooooo, apparently confused😅

[feral hound]

haha it happens

[fiery cosmos]

it is weak balanced.

[feral hound]

yes so you having a height larger than the log2 which is the ideal height makes sense

[austere sparrow]

I meant that the order of the height is O(log(N))

If you have an WAVL tree, wikipedia says that its height is at most log(n, phi), and the number of comparisons is therefore O(log(n)) where n is the number of elements

[fiery cosmos]

That gives a different answer

[austere sparrow]

answer to what?

what are you trying to find?

[feral hound]

@fiery cosmos

[fiery cosmos]

The time of complexity

[feral hound]

time complexity comes in 3 forms worst average and best case scenarios

even in a binary tree if its implemented very badly it can have a O(N) complexity

for example imagine you have a list of numbers from range 0 to 100

if you want to make a binary tree using this list and choose 0 as the root node

now none of your nodes will have any left children and the complexity is O(N)

if you choose the middle element say 50 as the root node you will have a well balanced tree where the left side is the same height as the right side

and your complexity will be O(logN)

@fiery cosmos does this help or its not related to what your asking?

[rose stone]

Are there any pre requisite for the Stanford's data structures and algo course ? Other than basic programming.

[knotty magnet]

i was thinking that didn't make sense because there would be some strings that aren't eventually hashed, and it'd be the same to just cache when it's hashed once anyway

[candid elk]

n, q = map(int, input().split())
mass_n = list(map(int, input().split()))
mass_n.sort()
inter_mass_n = dict()
for i in range(q):
    x, y = map(int, input().split())
    for j in range(x-1,y):
        inter_mass_n[j] = inter_mass_n.get(j,0) + 1

value = list(inter_mass_n.values())
value.sort()
summ = 0

for i in range(len(value)):
    summ += mass_n.pop(-1) * value.pop(-1)

print(summ)```

@feral hound, I optimized the code like this. It turns out that I shortened the code by 1 cycle.

This is how he looked before:
```py
n, q = map(int, input().split())
mass_n = list(map(int, input().split()))
mass_n.sort()
mass_q = []
for i in range(q):
    x, y = map(int, input().split())
    mass_q.append(range(x-1, y))
inter_mass_n = dict()

for i in range(n):
    for j in mass_q:
        if i in j:
            inter_mass_n[i] = inter_mass_n.get(i,0) + 1

value = list(inter_mass_n.values())
value.sort()
summ = 0

for i in range(len(value)):
    summ += mass_n.pop(-1) * value.pop(-1)

print(summ)```

But that's not enough... The code still fails the tests...

[feral hound]

@candid elk could you send the actual problem?

as in a link to where your trying out your solutions

[candid elk]

The problem is that for n = 2 * 10 ^ (5) the program runs for more than 2.5 seconds and I don't know how to optimise this code even more...

[candid elk]

Here's a detailed description of what my code does

[feral hound]

no I mean from where did you get this problem?

@candid elk

[candid elk]

This is preparation for sports programming. I take small courses on it. That's it from there the task

[feral hound]

can you post the actual text from the task?

or scrn shot it

[candid elk]

I can, but the whole task is in Russian😅

[feral hound]

ahhh

could you do a rough translation?

[candid elk]

There is a lot to translate. And google translate will make it crooked for large text

[feral hound]

hmm fair

the reason im asking is because maybe there is some kind of subtlety in the problem that allows for a much faster solution

can you post the inputs and outputs required?

a few examples should be fine

[feral hound]

do this from the original problem

[candid elk]

I understood you. I will try to translate the task

Task:
The input is 2 numbers 1 <= n, q <= 2 * 10 ^ (5). n is the number of numbers in the array, q is the number of ranges on which the sum is calculated. Next comes the array itself of length n and q ranges via Enter. The task is to arrange the numbers in the array n so that the sum of the numbers on all ranges is the largest. And output the largest amount

Example 1:
INPUT:
5 3 1 9 4 3 1 1 4 2 2 3 5

OUTPUT:

34```

Example 2:
    INPUT:

1 1
5
1 1```

OUTPUT:

5```

Example 3:
    INPUT:

2 2
8 4
1 1
2 2

    OUTPUT:

12```

Let us consider the first example: the most profitable would be to put 9 on position 4, and 4 on position 3, and 3 on position 2, we will put units on the first and last positions. We get: 1 3 4 9 1
(1,4) → 17
(2,2) → 3
(3,5) → 14

@feral hound

[feral hound]

ok so based on this although I still dont 100% understand the problem I can already see a faster solution than what you did

[candid elk]

Yes? I thought that there was nothing faster to come up with😆 Therefore, I tried to optimise my code

[feral hound]

ahh i get the problem now

[candid elk]

What?

[feral hound]

length of array: 5   number of ranges: 3
the arary: 1 9 4 3 1
range1: 1 4
range2: 2 2
range3: 3 5

sort the array such that the sum of the sum of the ranges on the array is the max

correct?

[candid elk]

Yes, but you only need to output the maximum amount that is possible from these numbers

[feral hound]

yes

ok I see why you chose to solve it like that

I have to go in a bit so I will try to figure out a solution when I come back (around 2hrs) but hopefully with this info someone else might be able to help you aswell

[candid elk]

Well. I will wait for you if no one helps me

[covert furnace]

https://www.theraleighregister.com/httpswwwbookmakereu.html

[feral hound]

I think

!rule 8

[halcyon plank]

Rules

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

[feral hound]

is what you want but we can still help him just not give the answer straight up

[vernal flint]

what is wrong ffs

[glossy breach]

you're missing a bracket

[shut breach]

please don't be condescending

[woeful trail]

you have a period

at the end of that client statement

line 18

@vernal flint

[vernal flint]

ya got it guys, thanks.

[woeful trail]

welcome

https://i.imgur.com/8VlJa0h.jpeg how do i get list comprehension to take a previous list ahhhhh

i need line defined in this list comprehension but i have no idea how

[glossy breach]

No like seriously i didnt mean it that way

Sorry for that

[shut breach]

that's good, just be mindful of how your tone might be taken by others

[rapid dome]

enumerate(line)?
at least if you refer to line 5
oh, I see it now

sth like email_line = [[line.split() for (index, line) in enumerate(line_list) if line[index].isdigit() should do the job.
Unless I'm missing sth, but in general having comprehensions for complex task is harder to understand and use than having for loops

[fervent saddle]

I didn’t interpret it that way either

[feral hound]

dont know if it was fixed after edit or if that was the original but that sounds fine to me rn

[fervent saddle]

Maybe, yeah

Idk

[dapper sapphire]

Is // same at the core compared with typecasting a floating value with an int?

[knotty magnet]

a smart way to store data

a dict is a data structure

json is a file format

[feral hound]

essentially anything that you store data in is some kind of data structure dicts, arrays, lists, tuples sets, binary trees, stacks, queues, graphs

[fervent saddle]

Yeah

Storing and retrieving it

And processing it I guess

Like with graphs, they can be used to solve certain problems

[feral hound]

well essentially all data structures can be used to solve some kind of problem its just about figuring out which one works best for what you need to do and figuring out what algorithm you should use / develop

and its not like each of these data structures has to be made 1 particular way they are often modified to better suit their application

[feral hound]

I'm trying to figure out a solution for this rn but honestly I can't think of anything other than what you already did just written a bit differently

although I do feel like there has to be a much more efficient way to solve this problem

If I think of anything I'll let you know

[brave owl]

why do i see Counter so much in user submitted solutions on lc

what exactly does it do

[feral hound]

you mean the variable name counter?

[brave owl]

the class

[feral hound]

idk about a class called counter but a lot of people like to use the name counter to keep track of their loop iterations

[shut breach]

a Counter is like a dict with objects as keys and their count as values

[feral hound]

hmm thats the first time I hear about this

[shut breach]

you can create a Counter from an iterable and it will automatically count the elements for you

[brave owl]

yeah i looked into it now and understand it somewhat

if i pass a string/array into Counter im assuming that O(n)?

[shut breach]

yep

[brave owl]

i was doing a few problems yesterday about unique items in an array and number of occurences and it was popping up a lot in solutions

[candid elk]

Unfortunately, I do not yet understand if there is any other solution at all... Only if we create a range tree, but this may work even worse than now

[glossy breach]

Isn't this problem just prefix sum + some greedy

You sort all the numbers in decreasing order

Let's say

p[i] is the multiplier of i-th element

Then you sort p in decreasing order

Greedily put the largest number with the largest p[i]

Second largest number with the second largest p[i]

@candid elk

Did I get the statement wrong

[feral hound]

this is what his solution is doing given the problem however its too slow

[feral hound]

also have a look at this

this is the actual problem

[glossy breach]

Uhm

This can be done in O(n)

[feral hound]

could you share your solution?

[glossy breach]

I mean

O(n log n) if the sorting part is counted

The only remaining part is to calculate the p array right

[feral hound]

O(nlogn + n*m)

[glossy breach]

calculating the p array can be done in O(n)

[feral hound]

m is the number of ranges

[glossy breach]

Ya

So let's say I have another array called q (of length n)

And p is the prefix sum of q

If I increase q[i] by 1 then how does p change?

[feral hound]

just to be clear what do you mean by prefix sum?

[glossy breach]

Oh

p[i] = q[1] + q[2] + ... + q[i]

[feral hound]

ok I understand

[glossy breach]

?

All elements of p from index i to n gets increased by 1 right

[feral hound]

actually wait nvm im confused again lol

[glossy breach]

Hmm

[feral hound]

is q a range?

[glossy breach]

Nope

It's just an ordinary array

[feral hound]

so in the problem hes given an array lets call it L it has unordered numbers inside it

[glossy breach]

Yup

[feral hound]

N is the length of L

and he is given M ranges that can be anything in between 0 to N

[glossy breach]

Yes

[feral hound]

could you use this notation to explain again?

[glossy breach]

Alright

So the answer will be each element of the array multiplied with some number right

[feral hound]

yup

and the numbers would be the overlap in the ranges

[glossy breach]

All the remaining part is to calculate all the multipliers

So I call the array of multipliers p

For example

[feral hound]

ok

[glossy breach]

With ranges 1-4, 2-3 and N = 5

p should be

0 1 2 2 1

[feral hound]

ahh btw in the notation given in his example arrays are indexed at 1 not 0

[glossy breach]

Then

1 2 2 1 0

[feral hound]

yup

[glossy breach]

So for each range

hmm

Let's say

from l to r

I have to increase all elements of p from l->r by 1 right

[feral hound]

yup

[glossy breach]

So this is how I would do it

I construct an array q

And let p be the prefix sum of q, i.e p[i] = q[1] + q[2] + ... + q[i]

p[i] is the sum of first i elements of q

Do you get it?

[feral hound]

what does array q contain?

[glossy breach]

I'll talk about this soon

Firstly it should be filled with 0s

[feral hound]

what is its length?

[glossy breach]

N

Equal to p

[feral hound]

ok

[glossy breach]

Let's say

If I increase q[i] by 1

All elements of p from i to N will be increased by 1 right

Since it is the prefix sum

Hmm

If q is

[feral hound]

yup

[glossy breach]

0 0 1 0 0 for example

Then p is 0 0 1 1 1

[feral hound]

I understand where your going with this

[glossy breach]

So I increase q[l] by 1, and decrease q[r + 1] by 1

[feral hound]

by doing this we dont have to loop over the range for each range

[glossy breach]

Yes

Then calculate the prefix sum of q

[feral hound]

so it goes from n*m to N

this is definitely more efficient

[glossy breach]

School starting in 5 mins

I have to go now, bye

[feral hound]

bye thx for the info at least we have a better solution now

[feral hound]

also this might be wrong will prob have to write my own solution to make sure

another thing to add because I almost thought calculating the prefix sum would be a n*n / 2 operation

you should do a cumulative sum this will make it an o(n) operation

and to reiterate at the start of a range you add 1 and at the end of the range you -1

[timid garnet]

n = len(matrix[0]) for row in range(n): for col in range(row,n):

What exactly is this iterating through?

[shut breach]

!e

for i in range(4):
    for j in range(i, 4):
        print(j, end=' ')
    print()

[halcyon plank]

@shut breach :white_check_mark: Your eval job has completed with return code 0.

001 | 0 1 2 3 
002 | 1 2 3 
003 | 2 3 
004 | 3 

[timid garnet]

I know what its outputting, but I wanna know what the code is actually doing.

[knotty magnet]

you can figure it out from the output

[timid garnet]

I come for help and get told figure it out. Nice. I still dont know, sorry.

[knotty magnet]

it's looping 4 times, then 3 times, then 2 times, then 1 time

[gritty marsh]

i loops from 0 to 4.
then, j loops from i to 4.

you can see why this happens: when i increases after each iteration, j loops through a smaller range each time.
on the first iteration of i, i = 0. j loops from 0 to 4
on the second iteration of i, i = 1. j loops from 1 to 4.
on the third iteration of i, i = 2. j loops from 2 to 4.
and so on...

[candid elk]

@feral hound, @glossy breach, Wow, the idea is certainly interesting. I just need to understand now how to implement it.😅

[glossy breach]

That should be fairly simple

[glossy breach]

Well I assumed that was trivial

[candid elk]

Maybe simple, but I just woke up😅

[glossy breach]

Ya, if you have any problem just ping me

[candid elk]

Also, I don't know much English. Therefore, there may be slight problems understanding the idea😑

[candid elk]

Ok) Thanks for the help🙃

[tawdry jacinth]

#include<iostream>
using namespace std;


void swap(int &x ,int &y){
    int temp = x;
    x = y;
    y = temp;
}

int trigger(int a[] , int start , int end ){

    cout<<"trigger"<<endl;
    int pivot = a[start];
    int i = start , j = end-1;
    while(i<j){ 
        while(a[i]<pivot) i++;
        while(a[j]>pivot) j--;
        if(i<j) swap(a[i], a[j]);
    }
    swap(a[j],a[start]);
    return j;
}


void quicksort(int a[] , int start , int end){
    cout<<"Quicksort"<<endl;

    while (start<end){
    int mid = trigger(a,start,end);
    quicksort(a,start,mid);
    quicksort(a,mid+1,end);
    }
}

int main()
{
    int n;
    cin>>n;
    int *arr = new int[n+1];

    for(int i = 0; i < n; i++) cin>>arr[i];
    arr[n] = INT_MAX;
    // for(int i = 0; i < n; i++) cout<<arr[i]<<" ";

    quicksort(arr,0,n);

    for(int i = 0; i < n; i++) cout<<arr[i]<<" ";
    return 0;
}

the recusion doesnt stop in my code . can someone help me find whats the problem ? thanks in advance

[glossy breach]

Why do you have that while loop inside void quicksort

Also this is python server btw

[onyx umbra]

start and end value in quicksort() is not changing

[candid elk]

Can you please explain again what it is for? I'm just dumb and lost my train of thought😆 😅

[onyx umbra]

not sure what was your original question, but I think it is adding all elements before "i" in "q" and storing in "p"

including the one at q[i]

[tawdry jacinth]

ohk i though since it was dsa channel we can ask anything sorry

[feral hound]

yeah it was my brain just wasnt working yesterday lol it was pretty late for me

[feral hound]

if you make a list zeros of length N and call it q

then for every range (a, b) add 1 at q[a] and -1 at q(b) (if its non inclusive like in python, if its inclusive do it at q[b+1])

then you can make a multipliers list also of length N lets call it k

k[i] = q[0] + q[1] + q[2] ... q[i]

comparing to your old code k will be what you called inter_mass_n

however make sure that when your making list k that you use a cumulative sum as that is an O(n) operation its a trivial step but if you calculate the sum for each index instead of using a cumulative sum you will end up with a O(n^2) operation which is obviously much much worse

the time complexity for this solution should O(nlogn + n + m)

[candid elk]

Wow, how tricky everything is😅

Thanks a lot, I'll try to figure it out)

[glossy breach]

Pardon me, I've been on DnD for hours

[candid elk]

Dungeons & Dragons? Lucky you) I always dreamed of playing😄

[glossy breach]

No that's Do not Disturb

Lmao

[feral hound]

lol

[candid elk]

But... Such games are not very popular in Russia...

[candid elk]

😂 👌

OK. The joke is counted😄

[feral hound]

@glossy breach I didnt miss anything right?

[glossy breach]

I guess so

[feral hound]

only optimisation after this I can think of is somehow doing it without sorting but not sure if thats possible

[candid elk]

Well, then I'll go deal with it😄

[glossy breach]

If limit is small enough then counting sort will be O(n) but for n <= 2e5 O(n log n) should be fast enough

[candid elk]

@feral hound, @glossy breach Thanks again for your help)

[glossy breach]

np

[feral hound]

all Pichu but happy I could be part of it learned something as well 🙂

[candid elk]

@glossy breach, Can you please tell me if I'm going right?

n, q = map(int, input().split())
mass_n = list(map(int, input().split()))
mass_n.sort()
mass_q = [0 for _ in range(n)]
inter_mass_q = [0 for _ in range(n)]
for i in range(q):
    x, y = map(int, input().split())
    mass_q[x-1] = 1
    mass_q[y-1] = -1
for i in range(n):
    inter_mass_q[i] = sum(mass_q[:i]) ```

[glossy breach]

No

You are setting it to 1 instead of increasing it by 1

[feral hound]

+=

[glossy breach]

Also as Murtada says you should use cumulative sum to calculate inter_mass_q

Using sum() would be n times slower

[feral hound]

if you dont use cumulative sum this method is actually slower lol

[candid elk]

Oh, missed

[candid elk]

How to do this in python? I only know the way with numpy, but it is forbidden...

[feral hound]

just do it manually

have a variable cum_sum and += q[i] as you loop through

[candid elk]

I think I understand you😑 thx

So?

n, q = map(int, input().split())
mass_n = list(map(int, input().split()))
mass_n.sort()
mass_q = [0 for _ in range(n)]
inter_mass_q = [0 for _ in range(n)]
for i in range(q):
    x, y = map(int, input().split())
    mass_q[x-1] += 1
    mass_q[y-1] += -1
cum_sum = 0
for i in range(n):
    cum_sum += mass_q[i]
    inter_mass_q[i] = cum_sum```

@feral hound

[feral hound]

mass_q[x-1] += 1
mass_q[y-1] += -1

did you do -1 here because they give ranges indexing at 1 instead of 0?

[candid elk]

Yes

[feral hound]

do just y not -1 then

looks good other than that

mass_q[x-1] += 1
mass_q[y] += -1

like this

[candid elk]

But... If n = 5 and in one of the ranges y = 5, then an error... That is, I need to make mass_q of length n + 1?

[feral hound]

if its bigger then dont do -1

just add a check for that

[candid elk]

inter_mass_q = [1, 2, 2, 2, 0] although there should be inter_mass_q = [1, 2, 2, 2, 1]

🤔

[feral hound]

show me what check you added

    if rangei[1] < n:
        k[rangei[1]] -= 1

this is the check you need to add

[candid elk]

mass_q[y if y < n else y-1] -= 1```

[feral hound]

no no

do what I sent you instead

think a bit more about why you need to do what I told you if you understand how the algorithm works you will know

[candid elk]

Now I understand

thanks a lot!!! I love you😄 💚

@feral hound @glossy breach

[glossy breach]

Nice!

[feral hound]

gj 🙂

[meager slate]

hello, there if i have the values of the xor of 2 numbers and or of 2 numbers, can retreive the 2 numbers back

i suck at bit manipulation 🥲

[glossy breach]

That's not enough information afaik

[trim fiber]

Hmm...

a  b  (a | b)  (a ⊕ b)
0  0        0         0
1  0        1         1
0  1        1         1
1  1        1         0

As you can see it's not unique (for pairs 0-1, 1-0 you have same output 1-1)

[meager slate]

ah i see...

[glossy breach]

however you can find the sum of two numbers

[stable pecan]

their sum mod two maybe

[glossy breach]

I mean the exact sum

xor + and = or

and + or = sum

=> sum = or * 2 - xor

I think

[median vortex]

If I want to use n-bit grey code, I understand that it is a list of values from 0 to n bit where only one bit can shift at a time, so 2 bit would be 00,01,11,10 and so on. Any ideas on how this would look like with backtracking & node count? The little I found online only said to either ignore or invert bits, which seems odd to me..

[tropic glacier]

What do you mean by backtracking and node count?

[median vortex]

Backtracking as in a node tree where you have multiple choices to go, say you start from node A and can go to node B and C, you go to node C but figure its wrong so you backtrack to node A and go to B instead

I have an assignment to program nbit grey code with backtracking and a count of nodes visited and promising nodes, but I don't understand how backtracking is supposed to work with this, I can't visualise a node tree in my head that would work for this

[feral hound]

well you can backtrack with recursion

https://www.youtube.com/watch?v=G_UYXzGuqvM

have a look at this video

[tropic glacier]

Hmm, not really sure what you need, then, as there are perfectly straightforward, non-recursive ways to generate Gray codes

"Backtracking" is something I would associate with puzzle-solving, as in "backtracking search"

[feral hound]

@tropic glacier honestly to me backtracking seems like the easier solution here idk what methods your talking about (im not too familar with nbit grey codes)

I can also see a way to solve this using graph searching algorithms like bfs

[median vortex]

So if I understand the video correct, backtracking recursively is solving a problem step by step, removing the steps that is wrong?

[feral hound]

yeah so you go down a path however if you realise that you dont have anymore options down that path just go back until you have options again

[tropic glacier]

There are some funny tricks with bit-shifting and bitwise xor that automatically generate a Gray code sequence. I forget the details, but I did find them on the internet somewhere 🙂

[feral hound]

and when you finally find a solution just break out and return the path

[median vortex]

@feral hound @tropic glacier thank you both! I think I have a better grasp about this task now! if I try a few things, would either of you mind if I shoot you a quick DM to see if I'm still on the right track?

[tropic glacier]

No, don't DM, just post questions in the channel so anybody can help

[feral hound]

^^ will help if I can/see it

feel free to @ me here as well

[median vortex]

Will do that!

[maiden timber]

If I have a dictionary of arrays/lists, and I iterate over the dictionary and I subsequently iterate over the array, thats O(n^2), right?

[fervent saddle]

It’s O(n) with the number of things in all the arrays combined

If the arrays are the same size then it’s O(n^2) with the size of any one array, if that’s what you mean

Or, I guess you could also say it’s O(n^2) where n is the average size of the arrays

Wait

[maiden timber]

So, I have hashmap/dictionary, and each key value is an array

[fervent saddle]

Well, and there would have to be n arrays too

[feral hound]

if number of items in the dictionary is N and the average length of each array is M then its O(N*M)

[fervent saddle]

Yeah

[maiden timber]

If I'm iterating over the map and then iterating over array, it would be O(N*M) ?

[feral hound]

yes

[maiden timber]

Because we are not iterating over the same data, which would be input N and input N -> n^2

[feral hound]

to be clear you are iterating over every single array in the dict correct?

[maiden timber]

Yes

[feral hound]

if your arrays are different lengths just take the average length

[maiden timber]

But, it would be O^2 is I was iterating over the same input data in the map(so, iterating over the map twice for some reason)?

**Newbie to asymptotic notation

[feral hound]

yeah I guess

[fervent saddle]

Twice would still be O(n)

[maiden timber]

By twice, I mean inner loop*

[fervent saddle]

Oh

[maiden timber]

I'm confused on what you mean by take the average length

nested loop*

Also, in regard to space complexity, if I'm storing data in a map in my algorithm, would be space complexity still be O(1), or would it be the storage in the map/array => O(n*m)?

[feral hound]

!e

my_list = [0, 1, 2, 3, 4]

for _ in my_list:
    for i in my_list:
        print(i, end="")
    print()

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | 01234
002 | 01234
003 | 01234
004 | 01234
005 | 01234

[feral hound]

thats N^2

[feral hound]

the average length of the arrays will be M

if M is constant then your time complexity is actually just N

you discard constants in big O notation

[maiden timber]

What defines if M is constant or not? (each array is of varying size)

If each array was of size 5?

Got it

[feral hound]

yes but if the average length of the arrays doesnt change you can treat it as a constant

[maiden timber]

Ah

[feral hound]

obv it will change a bit as you add different arrays but if the average is staying roughly the same its a constant

[maiden timber]

That makes total sense -- thanks

By varying, would that be if there is a ceiling and the variance is between the floor and ceiling?

[feral hound]

well then M would be bounded

and remember big O doesnt always tell you the whole story

!e

for i in range(5):
    print("one")

for i in range(5):
    print("one")
    print("two")
    print("three")

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | one
002 | one
003 | one
004 | one
005 | one
006 | one
007 | two
008 | three
009 | one
010 | two
011 | three
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/owoxegofam.txt?noredirect

[feral hound]

loop 1 and loop 2 both have O(N) complexity N being the number of loop iterations here 5

but loop 2 is doing three operations and is slower because of that

[maiden timber]

sure but theyre all constant operations

[feral hound]

yup

because we will always be doing the same number of operations in each loop

if I loop 10 times it will take 2 times as long 20 times 4 times as long 40 times 8 times as long

you see how this is a linear relationship

thats really all that big O is concerned with

[maiden timber]

Got it

[feral hound]

so a N^2 algorithm might be faster than an N algorithm with small N

[maiden timber]

Just to restate in my own words, Big O is more concerned with the relationship to input size, rather than operations on the a single instance of the input(constant expressions)?

[feral hound]

but after some point it will keep getting worse

[feral hound]

yup

there is some other notation that factors in everything but I dont remember its name

[fervent saddle]

The data in the map is the base data, and space complexity is about additional data requirements as that data grows

[maiden timber]

So, say I have an list/array input, and then i build a map of each individual unique key in that array, is space complexity now O(n), or O(1)?

[maiden timber]

This is ridiculously helpful, thank you so much

[oblique urchin]

Can anyone explain this?

[feral hound]

with hash maps space complexity is highly dependent on implementation

they take up a lot of space

https://stackoverflow.com/questions/43433699/hashmap-space-complexity

[maiden timber]

Just during generic coding interviews, how do you define space complexity then?

[fervent saddle]

I think it’s O(n) in python

[feral hound]

its the relation ship of data and storage instead of data and time

[maiden timber]

I was under the assumption space complexity was more dependent on call-stack / recursive algorithms then local variable storage

[fervent saddle]

It’s about all memory requirement in general

[maiden timber]

Got it

[fervent saddle]

Or data requirement, I guess

It might not necessarily be in RAM

So I shouldn’t say “memory”

[maiden timber]

So, if I have two hash maps that both contain the entire input size, would that be a space complexity of O(N^2) then?

[feral hound]

#❓｜how-to-get-help this channel is for algorithms and data structures go to a help channel

[feral hound]

no just N

2 * N is still just N

[maiden timber]

What would cause space complexity to be n^2* is a more appropriate question

[feral hound]

if you had a hasmap for every single item in the hashmap thats N^2

[maiden timber]

A hashmap of hashmaps?

So, if I had a hashmap of arrays, is the space complexity O(N*M) then, as with the time complexity?

[feral hound]

should be

are you familiar with list comprehensions?

[maiden timber]

Is that a set?

[feral hound]

nah its not

[dawn geyser]

Does anyone know a memoized solution for finding the different ways to sum upto a number n using an array of digits. Meaning find the diff number of ways I can 3 using [1,2] for eg.

[feral hound]

dw if your not its not related to this was gona give an example using list comps but if you dont know it will only be more confusing

[maiden timber]

Oh, like lambda type syntax

[feral hound]

I guess

!e

print([i for i in range(10)])

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[feral hound]

thats a list comprehension

its a shorthand way to create a list

you also have dict, set and generator comprehensions

[maiden timber]

Got it, yeah

But, with space complexity, is it ever constant?

My assumption is only if you dont allocate additional memory outside of primitives?

[feral hound]

yeah

honestly it was mb saying data and storage its more like N and storage

N can be any variable that changes

[maiden timber]

N and storage?

So, if I allocate a new array and store a bunch of stuff in there from the input, sort it, then space complexity would be O(N) and time complexity would be O(n log(n))

[feral hound]

let me give you an example with finding primes

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

def is_prime(num):
    if num > 1:
        for i in range(2,num):
            if (num%i) == 0:
                break
        else:
            return True
    return False

these are 2 different algorithms to calculate primes

in this case N is the number we are checking is prime or not

so we want to know the space and time complexity of checking N for these algorithms

for the first algorithm space complexity is N + M where N is the number we are checking and M is the number of primes in the range 2 to N

for the second algorithm the space complexity is 1

@maiden timber does that help?

[maiden timber]

Time and space compleixty for the first are both O(N*M)?

The 2nd one definitely makes sense

[glossy breach]

Space complexity is O(N)

[feral hound]

for sieve its N*M

N is the whole array M is all the primes

[glossy breach]

Time complexity is a bit more complicated

[maiden timber]

But if its a single array(reading sudo-code), would it be O(N)?

[glossy breach]

You mean N+M?

[feral hound]

ooops yeah

[maiden timber]

Because you're just changing bits in that array?

[feral hound]

N+M

hmm honestly this is a bad example looking back at it cause these 2 algorithms are doing 2 slightly different things so the first one seems worse

even though its a better algorithm

wait let me write something up real quick

[maiden timber]

Ha -- okay, given this example:

def foo(arr):
    div_two_list = []
    for item in arr:
        if item % 2 == 0:
            div_two_list.append(item)

    div_two_list.sort()
    return div_two_list

print(foo([5,29,2,459,2,53,54,23,6,49]))```

The space complexity here would be O(N), and the time complexity would be O(nlog(n))

If we do memory allocations for composite type, or allocate frames on the stack, then we we start to increase space complexity in some polynomial form

[feral hound]

yeah also I got a better example now

def all_primes(num):
    primes = []
    if num > 1:
        for i in range(2,num):
            for j in range(2, i):
                if (i%j) == 0:
                    break
            else:
                primes.append(i)
    return primes

there we go this algorithm calculates all the primes up to num

compare this algorithm with the sieve now

[maiden timber]

So, this would be N*M?

[feral hound]

nope

space complexity is just M

time complexity is N^2

[maiden timber]

Sorry, was referring to time complexity ha

[feral hound]

sieve time complexity is N*M

[maiden timber]

Ah, because we are not looking at different data --> it would be n^2

[feral hound]

and we know that for this case M will be much smaller than N especially as N grows

so sieve is much much faster

M is the number of primes up to N

so in terms of space complexity this is much better than the sieve but in terms of time complexity the sieve is much better

[maiden timber]

Got it

Whats a case where we have N+M?

[feral hound]

if you have 2 loops one looping over N and one looping over M thats N + M time complexity

just as an example

[maiden timber]

Non-nested loops?

If its nested then it would be N*M

[feral hound]

yeah

def nplusm(list1, list2):
    for item in list1:
        do something
  
    for item in list2:
        do something

[maiden timber]

If I have two different varying size hashmaps, would that be 2N, or NM?

Got it

[feral hound]

N + M

[maiden timber]

@feral hound This is extremely helpful, will probably ask it a couple more times to solidify, but really appreciate it!

[feral hound]

np

it can take a while to get the hang of space and time complexity but the more you do it the better you get

[maiden timber]

Any practice ideas?

[feral hound]

and if you just cant figure it out for some reason because an algorithm is very complicated you can run it a few times with different N and see how it changes in terms of space and time and plot the relation ship

from the plot you can tell what the complexity is

[feral hound]

just do more algorithmic problems

have a look at codewars, hacker rank or leet code

[maiden timber]

How can you tell how the relationship is changing?

My concern is that I'll assume its N*M, when its really N^2

[feral hound]

you mean if your plotting it?

[maiden timber]

Yeah

[feral hound]

I would say just play around with the data

you can keep M constant keep N constant change both at the same time etc

and usually you will have an idea of what the complexity should be just not sure

so use the info you have to make the best guess you can if your not sure

also do keep in mind there is still a best case average and worst case so you got to weigh those out as well

[maiden timber]

Ok

[frank vault]

import sys
from typing import List


def get_profit(prices: List[int]) -> int:
    '''
    42 ms ± 3.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
    '''
    max_price = max(prices)
    max_index = prices.index(max_price)

    min_price = min(prices)
    min_index = prices.index(min_price)
    return max_price - min_price if min_index < max_index else 0


def get_profit_for(prices: List[int]) -> int:
    '''
    340 ms ± 43.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    '''
    min_price = sys.maxsize
    profit = 0
    for price in prices:
        if price > min_price:
            profit = max(profit, price - min_price)
        else:
            min_price = min(min_price, price)
    return profit

why is the second function taking longer?

[knotty magnet]

it does more work in python

[frank vault]

because of the several min and max calls?

[knotty magnet]

yes, and the loop

[feral hound]

you also have conditionals in each loop its just doing a lot more

builtins tend to also be faster at doing something than you implementing yourself

[knotty magnet]

they're always faster, they're written in C

[feral hound]

they should have the same time complexity though so if you change up prices you should see a linear relationship in the time

by change it up I mean the length of the list btw aka longer list shorter list

[fiery cosmos]

is there a word for a graph with zero branches

[shut breach]

do you mean zero nodes, or zero edges, or each node has at most 2 edges?

[fiery cosmos]

each node has at most 2 edges

[shut breach]

as a data structure you could call that a linked list

as a mathematical object... a unary tree?

[fiery cosmos]

ya that sounds right

thanks

[winged summit]

Hello, I am new here, may I ask a question on a problem Ive been stuck on for quite some time?

[fiery cosmos]

Sure

[winged summit]

I am having trouble trying to develop a function that returns a higher-order function in order to do some math.

So far, everything I have tried skips right over the answer an produces only a function so I am pretty stuck

Ill post a screen shot of what I mean

Here is the problem and one of my more recent attempts at a solution

I can also take a screen shot of the environment diagrams on PyTutor if that seems useful

Thank you for any guidance you can offer

[fiery cosmos]

Yeah what is cycle supposed to do and what might f1/2/3 be?

[winged summit]

If I am being entirely honest, I am not even sure what the cycle is supposed to do either. So far as I can tell from the Doc Tests, in at least the first example, I think it composes each function into one another and then when you call the function you plug in the x value.

Part of me is glad I'm not the only one confused, the other part is scared lol

So if you're asking what my answer does, essentially, I attempted to use Lambda calls in order to compose the functions from f3 -> f1 so that I had a final function that could be called later with a substituted value for x

suffice it to say, it does not work and I am not entirely sure what function I have managed to create because when I try to print it I just get a hexadecimal location of the function

okay, so the number called on the cycle function "my_cycle(x)" would represent how many times it cycles through the functions 1 by 1?

okay, I think I understand now. I think I am going to need to use the nested function notation you did above but I am thinking of putting it under a while loop?

like "while (number) is not 0, run through these functions in such and such order decreasing (number) by 1 each time"

I'll try it

this feels a lot better than when I came here

I would but I am worried I will get flagged for cheating if my solution is too good lol they expect it to be gross and sloppy, I think

Ill just try it out for a bit with the new info, you guys are great tysm!!!!

[grave topaz]

how to learnn DS and algo this is the only part of programming where i have trouble with how did you leaen DS and algo?

please do ping me

[rose pond]

is anybody available for me to ask questions with

[abstract shadow]

wgat

[naive tundra]

i have a doubt in data structures and algorithms, in c language, may i ask here

plz help

[trim fiber]

Generally this server is dedicated to Python language but you can ask about data structures and algorithms at all

[grave topaz]

can someone please provide an answer thank you

[trim fiber]

Have you seen pinned messages?

[grave topaz]

yes

?

[trim fiber]

Basically you can learn algorithms by implementing them on your own

Like - implement binary tree or red-black tree

[grave topaz]

oh ok i did not see the pinned messages(i clicked the hashtag smh) thanks it it will help a lot

[frank vault]

I see, I thought that the for was gonna be faster because in my head both max and min calls on the list did a full loop

so 2 loops vs 1

[jolly lantern]

    while len(nums)!= 0:
        temp1=nums.copy() #this is for preventing test cases values to be modified dynamically
        index = len(temp1) - 2
        while index >= 0 and temp1[index + 1] <= temp1[index]:
            index -= 1
        if index >= 0:
            j = len(temp1) - 1
            while temp1[j] <= temp1[index]:
                j -= 1
            swap(temp1, index, j)
        return reverse(temp1, index + 1)
    else:
        return []
def swap(temp1, index, j):
    temp1[index], temp1[j] = temp1[j], temp1[index]
def reverse(temp1, from_index):
    res = []
    for index in range(0, from_index):
        res.append(temp1[index])
    for index in range(len(temp1) - 1, from_index - 1, -1):
        res.append(temp1[index])
    return res```

Hi. Can somebody please tell me the time and space complexity of this code?

[fiery cosmos]

Is there any way to decrypt google Cookies file?

[feral hound]

add py to the end of the top 3 back ticks to color the code

[naive tundra]

if a tree is having a single element, it is considered as the root, can it be considered as the leaf node also, since the left and right subtrees are NULL s

[pseudo hornet]

Can you guys tell me how to find which letter is lexicographically smaller
Please code in c++
Thanks 🥰

[tropic glacier]

<

[shut breach]

sure

[naive tundra]

can anyone find the error in my code written in c langauge please

i basically have to delete all the leaf nodes and print the post order traversal of the remaining tree.

#include <stdio.h>
#include <stdlib.h>
struct Node{
  int data;
  struct Node* left;
  struct Node* right;
};

struct Node* create_new_node(int data){
  struct Node* new_node = (struct Node*) malloc (sizeof(struct Node));
  new_node->data = data;
  new_node->left = NULL;
  new_node->right = NULL;
  return (new_node);
}

struct Node* insert_bst(struct Node* root, int key){
  if(root ==NULL){
    root = create_new_node(key);
    return root;
  }
  else if( key <= root->data){
    root->left = insert_bst(root->left, key);
  }
  else{
    root->right = insert_bst(root->right, key);
  }
  return root;
}
struct Node* delete_leaf_nodes(struct Node* root){
  if (root->left==NULL && root->right==NULL ){
    free(root);
  }
  else{
    root->left = delete_leaf_nodes(root->left);
    root->right = delete_leaf_nodes(root->right);
  }
  return (root);
}
void post_order(struct Node* root){
    if (root!=NULL){
        post_order(root->left);
        post_order(root->right);
        printf("%d",root->data);
    }
}
int main(){
  
  int n;
  scanf("%d",&n);
  
  struct Node* root = NULL;
  
  int a[n];
  for (int i=0; i<n; i++){
    scanf("%d", &a[i]);
    root = insert_bst(root, a[i]);
  }
  root = delete_leaf_nodes(root);
  post_order(root);
  return 0;
}

plz help guys

[austere sparrow]

@naive tundra This is a Python server. If you want help with debugging C or C++ code, you should see a different server, for example https://discord.gg/W4qm4ErU

[dense forge]

does anyone know about javascript server?

[fiery cosmos]

@fiery cosmos

[fiery cosmos]

this is bad

Hello pal.

bad C

Good evening

+Hey

[fiery cosmos]

I had a quick question about terms,
what is "1" and "2" called?

{
  "items": {
    "1": {
      "name": 1927997,
      "id": 1631226801,
      "status": 1923970,
    }
    "2": {
      "name": 1927997,
      "id": 1631226801,
      "status": 1923970,
    } 
  }
}```

i know, name, id, status are all elements right?

does each one count as a new dictionary?

[fervent saddle]

No the dictionary is the whole object

1, name, id, and status are keys

[fiery cosmos]

aah okay

im trying to generate a new

'key' for each line in a file

idk if you know any good resources for something like that

[fervent saddle]

Like for line numbers?

[fiery cosmos]

yeah

[fervent saddle]

You can use a list for that part

[fiery cosmos]

so each line number would...
1, 2, 3 and than the below elements would be filled in by some other code

this is my shoddy output right now

[fervent saddle]

If you’re trying to map things to a sequence of consecutive values, you can use a list

[fiery cosmos]

I will see what lists look like

are they that different?

[fervent saddle]

Yeah, they don’t have key-value pairs, you just index them

x = [5, 10, 15, 20, 25]
I mean one of these

[fiery cosmos]

aah yeah

i do want key value pairs

i just wanna generate a new 'set' per line

like a new

    "1": {
      "name": 1927997,
      "id": 1631226801,
      "status": 1923970,
    }```
per line

name, id and status are all changing per line ofc

[dim bane]

The "1" there would be a key, and the value for that key is another dictionary, which has keys "name" "id" "status". A set is something different

[tight echo]

print(‘uo’)

[quasi lichen]

Hi do we need calculus

[keen hearth]

For the algorithms you would learn on an introductory course, no.

It's almost entirely discrete maths.