algos-and-data-structs

[lean dome]

doesn't work that way - it's only N^3 if there is some statement in it that runs some multiple of N^3 times.

that if statement runs at most N times, so it can't cause the complexity to go up to N^3

[lunar jacinth]

ah i see..

so ill leave that constant

but then now we call alpha

that has to be N^3 now

[lean dome]

how many times is alpha called?

[lunar jacinth]

m amount of times

so depends on beta function

[lean dome]

is it?

[lunar jacinth]

it depends on the if actually doesnt

[lean dome]

alpha is called at most twice per iteration of the while loop, and the while loop body runs at most N-1 times, so alpha is called at most 2N-2 times. That's still order N

[lunar jacinth]

so the loop right now is N^3?

cuz u do N * N * N?

[lean dome]

where can you do N * N * N?

let's say N is 5 - what statement runs 125 times?

[lunar jacinth]

sso back tracking a little up to ```py
m = Beta(arr, curr_size) N

up to this line it would be O(2n) or O(n^2)?

its a while loop with a function call that has a loop inside

would that make it quadratic?

[lean dome]

the most times any line inside the Beta function runs on any given call is N, so if beta is called N times, then the most times any line inside the Beta function runs across all calls is N * N

[lunar jacinth]

so ```py
Alpha(arr, m)

now we have ```py
N * N * N

[lean dome]

why times?

you have N * N for lines in the beta function, and you have N * N for lines in the alpha function - that's 2 * N * N, not N * N * N

[lunar jacinth]

Alpha(arr, m)
``` Soo this right here is N * N of time?

[lean dome]

again, think of how many times the instructions inside the Alpha function run. On any given call to the Alpha function, there's no line in it that runs more than N times. So across N calls to the Alpha function, there's no line in it that runs more than N * N times.

[lunar jacinth]

    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

so this would be the correct way to write line by line to show that it runs no more than N *N times?

[lean dome]

it seems like a reasonable notation, I guess.

[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
```So the cumulative time of these 3 functions would be O(n)+ O(n) + O(2N^2)?

[lean dome]

yeah - though O(2N^2) is usually just written O(N^2)

[lunar jacinth]

oh right because constants get cancelled right?

So the 2 just goes away

[lean dome]

yeah, the constants are generally ignored.

[lunar jacinth]

is there a possibility i can just combine py O(n)+ O(n) + O(N^2) all into one?

[lean dome]

the runtime complexity of Alpha is O(N)
the runtime complexity of Beta is O(N)
the runtime complexity of Gamma is O(N^2)

[lunar jacinth]

oh okay

right

Sso the cumulative would just be O(n) + O(n) + O(n^2)

[lean dome]

what do you mean by "cumulative"?

[lunar jacinth]

I'm trying to find the cumulative Big O analysis of Gamma, Beta, and Alpha

[lean dome]

"cumulative Big O analysis" isn't something I've heard of. What do you mean by it?

for big O analysis, we talk about the complexity of a single function, in terms of how its performance changes as the size of its input changes.

[lunar jacinth]

i think i just had to add them together haha

not really sure myself

[lean dome]

that's not really a sensible operation to perform.

[gusty elk]

Can we speak about ML here ?

[jolly mortar]

#data-science-and-ml might be better suited

[dapper sapphire]

wow creating substrings from a string is harder than I thought it would be. Good lord!!!

So writing it I can sort of see how it would be. We just keep on sliding it over to create the next substring.

so next would be: c, cd, cde, cdef

Is this called sliding window?

[shut breach]

not sure what you're talking about

[dapper sapphire]

I'm trying to create all possible sub-strings from a string

[shut breach]

are the substrings contiguous

[dapper sapphire]

Yes, they are contiguous.

I guess it is sliding window. or is the range always fixed in sliding window?

[shut breach]

then a substring is uniquely defined by its start and end

if you can find all the start and end pairs, you have all the substrings

[dapper sapphire]

https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples

It just didnt occur to me that we can slide the index over to create a new sub string. Actually, I think I can create the substrings.

[dapper sapphire]

hahaha I guess this would work

!e

def _subString(s: str) -> list:
    output_array = []
    for i in range(len(s)):
        for j in range(len(s)):
            sub_string = s[i: j+1]
            if sub_string:
                output_array.append(sub_string)
    return output_array

string = "abcd"
sorted_sub_string = sorted(_subString(string))
print(sorted_sub_string)

[halcyon plank]

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

['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']

[azure gulch]

hi guys i need some help about a algorithm. i need to do a kind of path finder so i am searching for a algorithm its visit all vertices just one and turn back start node

[severe kernel]

Hey everyone! I have quick question about sorting lists in python

If my 2d list looks like this:

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

And I need to sort it w.r.t. l[0]while making sure elements in the second row l[1] moves with it so the relative position of elements in both sublists stays the same. The resulting list looks like this:

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

Basically l[1] keeps the original index of elements in l[0]

Does anyone know what function does this? Thanks a lot!

[jolly mortar]

transpose it with zip(*l), do a normal sort (using sorted), then transpose it back

[gentle spruce]

hey i want to start learning data structures and algorithms

can anyone tell me where do I start from

and also which website do i refer to

[lapis ibex]

oh that's cool use dijkstra's algo and return back in shortest path which can be done by storing a parent array

[lapis ibex]

geeks for geeks ,abdul bari yt mycodeschool yt and tech dose yt

[vocal gorge]

its visit all vertices just one and turn back start node
That actually sounds like a Hamiltonian cycle, finding which is IIRC NP-complete.

[dapper sapphire]

There are also some resources in pinned area in the channel.

[old rover]

i still don't get what amortized time is

it's the time spent during the worst case scenario?

[vocal gorge]

on average, the complexity is this. It's possible for worse complexity to happen, but not consistently.

[old rover]

ohhhh

ok yeah that makes much more sense

so it's like an average?

[vocal gorge]

Like how when you append to a list, maybe this time it'll be n operations due to resizing - but then it's guaranteed that the next n insertions (assuming the list doubles in size each time) will be O(1)

[lean dome]

Amortized means "spread across many", basically.

[old rover]

i see

[vocal gorge]

so you know for sure that you can't consistently get O(n) no matter what you try - on average it'll be O(1) because each spike when the list resizes is guaranteed to be followed by many constant-times where it doesn't.

[old rover]

doesn't amortized loans in real life mean

you pay it back a bit by bit?

[lean dome]

Spread across many months of repayment, yeah.

[old rover]

oh i see

ok cool

the pomodoro technique is elite

[lean dome]

The dictionary does better, it says amortize is "to pay off a debt gradually". In the case of a dynamic array, the periodic O(n) resizes are "paid off" by the guaranteed O(1) inserts that follow them.

[old rover]

hm that makes more sense

so is every time complexity amortized?

[lean dome]

No. The trick for a dynamic array that makes for amortized constant time complexity is that each time you resize, you grow by some constant factor of the current size. That's what makes for O(1) on average: the bigger the array is, the more expensive resizes are, but the less often they happen

[old rover]

oh

[lean dome]

If instead of a factor of the current size you always grew the array by a constant amount - add space for 10 new items each time it filled up, let's say - then it would be O(N) on average/amortized

[old rover]

my mind is tired

i think that's enough for today

can't burn myself out

but hey

made a solid dent

[fiery cosmos]

Here's a way I like to convince myself appending to a dynamic array is O(1) amortized, if you aren't too burnt out

Imagine you have a dynamic array that doubles in size whenever its last element is filled. It starts at length 1 with nothing in it (_ is unfilled, d is filled data). So it will grow like this: [_] ~1 time unit to create [d, _] ~2 time units to grow to size 2 [d, d, _, _] ~4 time units to grow to size 4 [d, d, d, _] 1 time unit to set value [d, d, d, d, _, _, _, _] ~8 time units to grow to size 8 [d, d, d, d, d, _, _, _] 1 time unit to set value [d, d, d, d, d, d, _, _] 1 time unit to set value [d, d, d, d, d, d, d, _] 1 time unit to set value [d, d, d, d, d, d, d, d, _, _, _, _, _, _, _, _] ~16 time units to grow to size 16

it takes constant 1 time to set a value, but linear time to double the array size

and if you write all those times out you get 1 2 4 1 8 1 1 1 16 1 1 1 1 1 1 1 32 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 64 1 1 1 ...

But I like to think you can use a butter knife to spread out all those numbers. Split each big number among the 1's to its right. 4 1 becomes 2 3, 8 1 1 1 becomes 2 3 3 3

So you end up with a list where everything is bounded by a constant, 3: 1 2 2 3 2 3 3 3 2 3 3 3 3 3 3 3 2 3 3 ...

So overall every append takes, on average, constant O(1) time

[old rover]

Hmmmm

alright

[fiery cosmos]

And maybe my 4 should have been 5 for the time to set a value and grow and 8 maybe should be 9, etc. But it still works out to all 3's bounded by 3

[austere sparrow]

@old rover perhaps a more concise explanation:

1. To create a list of size N, you need to spend N units of time. (it scales linearly with size, because you'll need to fill it with N / 2 items, doesn't really matter)
2. Suppose that you start with an empty list, and you want to append 2^N items to it. You double the capacity if you run out of capacity. This is how many time steps it's going to take:
   1 + 2 + 4 + 8 + 16 + 32 + ... + 2^N.
   Now let's extract 2^N out of the sum: S = 1 + 2 + 4 + 8 + 16 + 32 + ... + 2^N S = 2^N(1/2^N + 1/2^(N-1) + 1/2^(N-2) + 1/2^(N-3) + 1/2^(N-4) + ... + 1/4 + 1/2 + 1) then let's reverse the sequence: S = 2^N(1 + 1/2 + 1/4 + 1/8 + ... + 1/2^N) Don't know if you've seen this sequence, but its sum is going to be less than 2 (try taking a rectangle then painting half of it, then half of the remaining, then half of the remaining -- you'll never paint the full rectangle). So the total number of steps is going to approach 2 * 2^N. So to insert X items, you need O(X) of time.

Real implementations don't necessarily use 2, e.g. in CPython the new capacity is calculated as new_size + new_size >> 3 + (newsize < 9 ? 3 : 6) (according to https://stackoverflow.com/questions/52195579/what-is-the-resizing-factor-of-lists-in-python).

So the factor is k=1.125, but for any k > 1, (1 + 1/k + 1/k^2 + 1/k^3 + ...) is going to be finite

[old rover]

It’s starting to make more sense

[old rover]

I’ll look at it tomorrow

[fiery cosmos]

Lol hi

[red scarab]

had to ping

ill talk to you tommorow

im bussy rn

[shut breach]

@red scarab This channel is for discussion of algorithms and data structures, please don't misuse it

[tame fractal]

other than int, are there any other datatypes(classes in python ig) that have __rshift__/__lshift dunders?

[stable pecan]

i can't think of any, except, you know, bool, which subclasses int

[fiery cosmos]

It kinda would be cool if you could use them on lists/tuples [1, 2, 3] >> 1 👉 [3, 1, 2]

[stable pecan]

maybe deques and queues only, where rotation is O(1)

[stable pecan]

https://github.com/salt-die/sacks/blob/main/sacks/sequences/necklace.py#L4-L6

[halcyon plank]

sacks/sequences/necklace.py lines 4 to 6

class Necklace(Sequence):
    """
    An immutable sequence that "wraps-around". [https://en.wikipedia.org/wiki/Necklace_(combinatorics)]```

[pallid girder]

this name is great

[heady jewel]

It's got an established name already; ring buffer

[runic tinsel]

but it like, has equality

are ring buffers understood to be equal if you can rotate them to be equal?

I wouldn't expect that

[halcyon plank]

:ok_hand: applied mute to @fiery cosmos until 2021-07-17 18:33 (9 minutes and 59 seconds) (reason: mentions rule: sent 60 mentions in 10s).

[rotund lodge]

oh no nevermind , it was a raider. Let's not contribute to the spam by asking who pinged

[low scaffold]

uhh what

[haughty urchin]

ping?

[tame fractal]

who ping

[silk pendant]

ooga booga

[lavish jay]

ping

[fiery cosmos]

!ban 852897957392154655 Spam pinger

[halcyon plank]

:ok_hand: applied ban to @astral eagle permanently.

[low scaffold]

pong

[haughty urchin]

Good mod

[tame fractal]

[fiery cosmos]

Apologies for the ping y'all, let's keep this channel on-topic though

[lavish jay]

good

[lavish jay]

10/10 mod

[fiery cosmos]

Hey!
I want my program to check the extension of each and every file and if it doesn't match any of the elements in an array, then print a single statement for that particular array!
Can someone help me?

[latent prawn]

10/10 would use as mod again

[lunar jacinth]

class SORT(arr)
        k = arr.size
        res = []
        while k > 0
            mIndex = max(arr[0] to arr[k])
            maxIndex = mIndex - arr[0] + 1
            res.push(maxIndex)
            reverse(arr[0] to maxIndex)
            res.push(k)
            reverse(arr[0] to array[k])
            k-=1
        return res
def recursiveSort(arr, k):
         k = arr.size
         res = []
         if k <= 0:
             return []
         else:
              mIndex = max(arr[0] to arr[k])
              maxIndex = mIndex - arr[0] + 1
              res.push(maxIndex)
              reverse(arr[0] to maxIndex)
              res.push(k)
              reverse(arr[0] to array[k])
              return recursiveSort(arr, k-1)

So I'm supposed to turn the first function into recursion function
But I believe as of right now, it only resets ARR on each recursive pass. Could someone help me fix this?

[dapper sapphire]

!e

string = ""
array = []
if string:
  print("ok")
else:
  print("string is empty")

if array:
  print("ok")
else:
  print("Array is empty")

[halcyon plank]

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

001 | string is empty
002 | Array is empty

[dapper sapphire]

So we can do if string: or if array: to check if a string or an array is empty?

[deft locust]

yep, empty sequences are usually falsy in python

[dapper sapphire]

ok

!e

array = []
string = ""

if not array:
  print("Array is empty")

if not string:
  print("String is empty")

We can also use not to determine if array or string is empty

[halcyon plank]

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

001 | Array is empty
002 | String is empty

[blissful drum]

hello, I want to make a skew t log p diagram using metpy with this code, but it displays a value error

https://paste.pythondiscord.com/okuwuraxur.rust

if I remove the line for shading the cin and cape, the code runs through tho

[old rover]

this might be better suited for #data-science-and-ml

i'm a bit confused guys

why is the fibonacci algorithm O(2^N) for time complexity?

CTCI kinda generalizes it

and says something along the lines (paraphrasing here)

when a recursive function makes a lot of calls like this

they're like branches

branches are the recursive call branches

which is why it's O(2^N)

and also i think i can finally read CLRS since I changed the way I learn things

improvement 🙂

i don't need to know a lot of this stuff for project management

but I'd like to see what coders deal with

it's cool to me

[blissful drum]

@old rover aight thanks, I will move it there

[old rover]

no problem 🙂 glad to help

can someone show me a recursive algorithm

that doesn't have a time complexity of O(2^N)?

[knotty magnet]

factorial

[knotty magnet]

in each recursive call, it makes 2 more recursive calls

[old rover]

ohhh

ok yeah then that makes sense

[knotty magnet]

if you imagine it sorta like a binary tree, each function call moves you down one level

[austere sparrow]

Which one?

This one? ```py
def fib(n: int) -> int:
if n <= 1:
return 1
else:
return fib(n - 1) + fib(n - 2)

It's not O(2^N), it's O(fib(N)) 🙂

[austere sparrow]

It doesn't mean that it's O(2^N).
Here's an O(N) algorithm that does 2 recursive calls:

def foo(n: int):
    print(n)
    if n <= 0:
        return
    n //= 2
    foo(n)
    foo(n)

[knotty magnet]

fair enough 😔

[austere sparrow]

Why? Because if you expand any computation with fib, you get this:

fib(4)
fib(3) + fib(2)
(fib(2) + fib(1)) + (fib(1) + fib(0))
((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))
((1 + 1) + 1) + (1 + 1)
```, which is a sum of `1`s. So you have as many calls as there are `1`s. And there are `fib(N)` `1`s.

[fiery cosmos]

class Solution:
    def deleteNode(self, root: TreeNode, key: int, parentNode = None) -> TreeNode:
        currentNode = root # start with root
        while currentNode is not None:
            if key < currentNode.val: # go left since it's smaller that the root
                parentNode = currentNode
                currentNode = currentNode.left
            elif key > currentNode.val:
                parentNode = currentNode
                currentNode = currentNode.right
            else: # elif key == currentNode.key:
                if currentNode.left is not None and currentNode.right is not None:
                    currentNode.val = self.findMin(currentNode.right)
                    self.deleteNode(currentNode, currentNode.val)
                    break
        
                # poss. 2: the key node is the top root node and it doesn't have two children (only one or none)
                elif parentNode is None:
                    # manually reassign them based on the possibilities, stop using currentNode
                    if currentNode.left is not None: # there is only the leftNode, no rightNode
                        #*#
                        currentNode.value = currentNode.left 
                        currentNode.left = parentNode.left.left
                        currentNode.right = parentNode.left.right 
                    elif currentNode.right is not None: # there is only the rightNode, no leftNode
                    else: # empty Tree/sub-tree
                        pass
                elif parentNode.left == currentNode: #currentNode.left is not None:
                    parentNode.left = currentNode.left if currentNode.left is not None else currentNode.right
                elif parentNode.right == currentNode: #currentNode.right is not None:
                    parentNode.right = currentNode.right if currentNode.right is not None else currentNode.left
                break #*#
        return root

trying to write a function for remove a BST node

this is for LeetCode so it has to be inside the class Solution

also ran out of space for my function that is also inside the class Solution:

    # finds the min val of a root (tree or subtree), i.e., the leftmost node
    def findMin(self, root):
        currentNode = root
        while currentNode.left is not None: 
            currentNode = currentNode.left
        return currentNode.val

I believe the error is caused in ```py
self.deleteNode(currentNode, currentNode.val)

I wrote the same solution over in AlgoExpert, which puts my solution in the same class as the BTS, and it works

the only line that's really different from AlgoExpert is:

currentNode.right.remove(currentNode.value, currentNode)

but I cant do that here because LeetCode uses a method written outside the BTS Class, inside its own class

so I'm wondering how I could convert that line to my LeetCode code

the error I get is maximum recursion depth exceeded. it might not be the problem with that one line, but I have a strong feeling it is

[old rover]

i made a typo

but yeah

it's O(2^N)

i think i understand why now

[austere sparrow]

I just explained why it's not

[old rover]

it's not O(2^N)?

wait let me read it aggain

oh

O(fib(N)?

hmmmmm

ohhh

i see now

when you use a recursive algorithm like the fibonacci algorithm it's gonna call itself over and over and over again

then it's starting to make more sense

it's O(fib(N) bc something like f(4)

becomes

f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1)

and then f(2)s and the f(3)s and the f(4)

it's like

death by a thousand cuts

if that analogy makes any sense

gotta love CTCI

this one would be O(A+B)

but

you drop the constants w big O

so it's just O(N)

and also

it's O(A + B) bc the for loops come one after another

it's not

this happens for every time this happens

"If your algorithm is in the form "do this, then, when you're all done, do that"then you add the runtimes.

If your algorithm is in the form "do this for each time you do that"then you multiply the runtimes."

gotta love Gayle

i know what this is

that initial for loop

i think it's from 0 to the length of the array

and then the second for loop

from 0 which is the value of a variable assigned to j to the length of the array

so that's two conditions

[austere sparrow]

This is the times I get:

N      time, us
10 ->          10
20 ->        1230    (123 times longer)
30 ->      151000    (~123 times longer)
40 ->    18600000    (~123 times longer)

Which is consistent with fib(40) / fib(30), fib(30) / fib(20), fib(20) / fib(10) being about 123
(which is the case because the ratio fib(n+1)/fib(n) approaches phi = 1.618..., and phi**10 ~= 123)

[old rover]

each condition happens along with the other condition

[austere sparrow]

@old rover Maybe you should start a blog explaining big O problems 🙂

[old rover]

oh i see

[old rover]

haha yeah it just took a bit of careful analysis

[austere sparrow]

I'm sure it will help people who are just one step behind you to understand them

(no sarcasm)

[old rover]

nah none taken

very flattering compliment

appreciated 🙂

i'm heavily endorsing the pomodoro technique

[austere sparrow]

By the way, time complexities become more complicated when you consider bigints.

[old rover]

what's a big int... big number?

[austere sparrow]

integer without an upper bound (like in Python)

For example, the complexity of adding two integers N and M is log(max(N, M)) (or max(log(N), log(M)), which is the same)

[old rover]

so you have to take into account the size of the input

to determine the time complexity?

[austere sparrow]

well, thankfully, most of the time the integers are bounded to some reasonable size

[old rover]

right

[austere sparrow]

but if you want to the really real complexity, you might want to account for bigints

it also gets more complicated with multiplication, because different languages/implementation use different algorithms

[old rover]

i see

yeah it seems like big O on an interview level

[austere sparrow]

and in typical applications, you usually don't deal with very large numbers

[old rover]

is pattern recognition

it took multiple 25 minute periods of trying to digest this stuff

for it to sink in

[austere sparrow]

fun interview question: create as many functions who are their own O notation (like the recursive Fibonacci algorithm)

[old rover]

what do you mean by "who are their own O notation"?

oh

[austere sparrow]

(treating two equal notations, like O(n) and O(5n + log(n)), as one submission)

[old rover]

hmmmm

i still haven't tried turning recursive stuff into iterative stuff

but i don't think it will be too hard

i figured out recursion by carefully dissecting the Fibonacci algorithm

i know this is O(N^2)

that second for loop depends on a variable that is created in the first for loop

one can't exist without the other

how poetic

what is it trying to do?

concatenate strings?

that would be my best guess

[knotty magnet]

print all unique pairings

[old rover]

oh i see

very cool

Gayle is a beast

I like how she thinks

it reminds me of me

alright this one

those two for loops have nothing to really do with each other

the outer one establishes this variable called i when it is lower than the length of array A

the inner one is this variable j which when it is lower than array B... the next condition is executed

oh my pomodoro is over

yayyyy

that if condition only happens if at a certain index

a number in the array is less than another number

then you print out each pairing

where that's true

it's O(A +B)

but it's more like

O(N)

bc you gotta drop constants

the only way these people are gonna learn big O

is they approach the problem with calmness

and some confidence

and not spend hours on it

ok here we go again

the most outer for loop

for i which is zero less than the length of the array

[knotty magnet]

it's not O(N)

[old rover]

O(A+ B)?

it's O(A+B)... right?

misconception on my part

[knotty magnet]

no, you loop over arrayB, arrayA.length times

[old rover]

right...

so that's why it's O(ab)?

[knotty magnet]

that's why it's not O(A+B)

[old rover]

hmmmmm

oh i think i see it

i'm getting burnt out now

you multiply the runtimes bc it happens for each time you do something else

i got it

this seems to be O(N)

there are N nodes in a tree

"The most straightforward way is to think about what this means. This code touches each node in the tree once and does a constant time amount of work with each"touch" (excluding the recursive calls).
Therefore, the runtime will be linear in terms of the number of nodes. If there areN nodes, then the runtime isO(N)."

[knotty magnet]

did you skip the last one?

[old rover]

example 8 didn't include a code snippet

but I did read it

[knotty magnet]

i meant the one you sent, example 5

[old rover]

yeah I get this now

O(AB)

the for loops occur each time one of them happens

what the fuck is O(✅ N)?

oh

it's a square root sign

🥴

[knotty magnet]

i mean, it's square root

[old rover]

yeah i'm tired

this stuff drains me quickly

holy shit

gayle goes hardddddd

what

O(A/B)???

[lunar jacinth]

isnt this O(N^3)?

[vocal gorge]

There isn't an N here at all.

it's O(a*b), where a and b are the array lengths

the third loop performs a constant number of iterations, so it's O(1)

[lunar jacinth]

So that entire thing is O(1)?

[vocal gorge]

the innerrmost loop is O(1), yes

[lunar jacinth]

what about the entire function?

[vocal gorge]

100000 iterations is still O(1), it doesn't depend on anything after all

[vocal gorge]

^

[lunar jacinth]

Oh I thought nested looped were quadratic

for(int i =0; i < arrayA.length;i++){
    for(int j= 1; j < arrayA.length;j++{
            ....  
``` would make it quadratic? O(A^2)?

[vocal gorge]

sure

[lunar jacinth]

haha okay, i think i get it now. ty

[lunar jacinth]

i actually had another question about recursion if you have some time?

[vocal gorge]

Ask away

[lunar jacinth]

class SORT(arr)
        k = arr.size
        res = []
        while k > 0
            mIndex = max(arr[0] to arr[k])
            maxIndex = mIndex - arr[0] + 1
            res.push(maxIndex)
            reverse(arr[0] to maxIndex)
            res.push(k)
            reverse(arr[0] to array[k])
            k-=1
        return res

def recursiveSort(arr, k):
         k = arr.size
         res = []
         if k <= 0:
             return []
         else:
              mIndex = max(arr[0] to arr[k])
              maxIndex = mIndex - arr[0] + 1
              res.push(maxIndex)
              reverse(arr[0] to maxIndex)
              res.push(k)
              reverse(arr[0] to array[k])
              return recursiveSort(arr, k-1)

So recently I got this exercise wrong and was wondering how would I fix this?

as of right now, I believe this resets ARR on each recursive pass.

I believe SORT is pseudocode

[vocal gorge]

what sorting algorithm is this?

it seems to do something really weird - maxIndex doesn't seem to even be an element of the array, yet it pushes it into the final array anyway

[lunar jacinth]

I'm not quite sure myself because the problem just said change the iterative function to a recursive one

could it be quicksort?

[vocal gorge]

anyway, you're on the right track - it should just be a function that accepts a k argument

that said, your base case is wrong

it should probably, hmm

you could just have res be the third argument, and have every recursive call modify it

[lunar jacinth]

If k is none:
K = arr.size
Res = []
```?

Or maybe just convert the while loop into a class function somehow?

[quasi aspen]

Let's say I offer 4 options to the user, and the user chooses the 3rd one of these options.
Options:
1-) Stop
2-) Previous
3-) Next
4-) Close

And consider a list object:
list= ["A", "B" , "C"]
Suppose the user is currently interacting with the "C" element. And if the user wants to move from C to the next element, he will choose the 3rd option. I want the user to return to the beginning of the list, that is, the 'A' element after selecting the 3rd option, how do I do that with Python?

[vocal gorge]

You could remember the index the user is on and make it wrap around - as in, take it modulo the length of the list every time you change it

[lunar jacinth]

how would i possibly modify it?

def recursiveSort(arr, k,res):
         k = arr.size
         res = []
         if k <= 0:
             return []
         else:
              mIndex = max(arr[0] to arr[k])
              maxIndex = mIndex - arr[0] + 1
              res.push(maxIndex)
              reverse(arr[0] to maxIndex)
              res.push(k)
              reverse(arr[0] to array[k])
              return recursiveSort(arr, k-1,res)
``` just like that? haha

[vocal gorge]

along the lines of

def recursiveSort(arr, k, res = None):
    # this will be the case only on the first call:
    if res is None:
        res = []
    # base case:
    if k==0:
        return res
    # do one iteration, modifying res
    # do the recursive call:
    return recursiveSort(arr, k-1, res)

[lunar jacinth]

def recursiveSort(arr, k, res = None):
         if res is None:
              res = []
         if k == 0:
              return res
         else:
              mIndex = max(arr[0] to arr[k])
              maxIndex = mIndex - arr[0] + 1
              res.push(maxIndex)
              reverse(arr[0] to maxIndex)
              res.push(k)
              reverse(arr[0] to array[k])
              return recursiveSort(arr, k-1,res)

So something like this would have worked?

[vocal gorge]

sure. Of course, to isn't valid syntax in Python, you probably want to take a slice instead

[lunar jacinth]

Yeah I think that was just pseudocode

At the time, it said u can do this in C++, java, python ,or even pseudocode

i chose python

do you mean like py reverse(arr[0:maxIndex]) or something like that?

[vocal gorge]

yeah, pretty much, though there's no built-in reverse function either

[lunar jacinth]

yeah i think that was not the point to like make it work yknow

i think at the time, the process was what mattered

i mean i still got most of the points, but good to know how to fix this for my upcoming midterm

[lunar jacinth]

tyvm!

[wispy hare]

tool to visualize Graham scan algorithm for finding convex hull of a set of 2D points: https://convexo.netlify.app/
please tell me if it's working well

[fervent saddle]

Is the worst-case space complexity of a trie O(n * k), where n is the range of characters the strings can have, and k is the combined number of characters in all the strings?
And is the best-case space complexity of a trie O(n * k), where n is the range of characters the strings can have, and k is the length of the longest string?
I’m trying to figure out if I have the right idea of how a trie works.

[brave owl]

yo, is this O(n^2) or O(n)

def firstRecurring(list):
    values = {}
    for i in list:
        if i not in values.keys():
            values[i] = i
        else:
            return i
    return None

my gut says O(n) but im not 100% sure in the if statement is O(1) or O(n)

and does it matter what you put as the value for the key?

[knotty magnet]

since you're just checking which key you see again, you don't need a specific value

this means you should probably be using a set

checking if a key exists in a dict or set is O(1)

[brave owl]

okay

does a set have the same time complexity as a dict?

[knotty magnet]

data structures don't have time complexities

its operations do

[brave owl]

ah yeah thats what i meant to say

[knotty magnet]

checking if something is in a set is pretty much the same operation as checking if a key is in a dictionary

[brave owl]

okay good to know

im just now learning about how you can add stuff to a dictionary to check values which leads to only have to use 1 for loop instead of a nested for loop

[knotty magnet]

a set is better if you don't need values

[brave owl]

okay

[vocal gorge]

empty string literal is a literal and so (slightly) faster, if that's what you mean

[stable pecan]

!e

from typing import NamedTuple

class TupleHolder(NamedTuple):
    point: tuple
    size: tuple

print(TupleHolder((1, 2), (3, 4)))

[halcyon plank]

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

TupleHolder(point=(1, 2), size=(3, 4))

[stable pecan]

same thing

you want the same named tuple inside itself?

i don't understand the question, there are type hints above

!e

from typing import NamedTuple

class Point(NamedTuple):
    x: int
    y: int


class Size(NamedTuple):
    width: int
    height: int


class Rect(NamedTuple):
    location: Point
    dimension: Size

print(Rect(Point(1, 2), Size(3, 4)))

[halcyon plank]

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

Rect(location=Point(x=1, y=2), dimension=Size(width=3, height=4))

[wheat plover]

For this code jam I created a class Vec which is a subclass of np.ndarray. The problem is that this class is mutable and we faced countless bugs because of this. I thought of making this class immutable with __slots__ or some but then you can't assign anything to the array and numpy's internal operations get buggy. What could have been a way to make this class immutable like. i.e. we don't have to be careful while assigning varibales. eg: a = copy.copy(b)

[vocal gorge]

Is it the mutability of the class that's the problem or of the array?

For the former, you can override __setattribute__ to prohibit changes. For the latter, you can set, IIRC, arr.flags.writeable = False

[wheat plover]

__setattribute__ would probably mess something up in numpy addition and multiplication. I am going to try writable = False

[vocal gorge]

If you still have trouble after than, it might be worth it to simply replace inheritance with composition and instead have the class not inherit from anything, but store the array in an attribute, and manually define all the operations.

That'll also allow you to introduce nice things that numpy arrays don't have, like access by .x/.y/.z, and even swizzling - like, .zx to get the z and x components as a 2-element array.

[wheat plover]

I initially did that... but with all the numeric magic methods the class became sooo long and wanted to be cool

[wheat plover]

I think writebackifcopy flag is the thing I was always looking for

[vocal gorge]

The WRITEBACKIFCOPY and (deprecated) UPDATEIFCOPY flags can never be set to True.
uhh

[wheat plover]

WRITEBACKIFCOPY still writes back for some reason even after setting it to False. Well I can atleast do write=False and that solves most of the problem. I found we didn't do a.x = 3 in a lot of places

[old rover]

holy shit CTCI is godly

Gayle is helpful

she hurts my head a bit, but she's very good

[old rover]

so bottlenecks are like unnecessary things in your code that can can be done better?

i don't get what she's saying here

[jolly mortar]

not unnecessary

its just the slowest part of the algorithm

[old rover]

hm ok

[slim vault]

think of an actual bottle neck, if you turn a bottle upside down the liquid will only be coming out as fast as the neck allows

[old rover]

i get what's going on here

[old rover]

this is the page that comes after what I just sent

looks like she's putting c,d into a dictionary with the key being "result"

gayle loves hash tables

[jolly mortar]

are you familiar with the 2 sum problem?

you're given a list of numbers, and you have to find all pairs which sum to a certain number

the naive solution is to check every pair of numbers in the list, which runs in N^2 time

the better solution is to loop over the numbers, and check if S - i is also in the list

the " check if S - i is also in the list" would normally take O(n) time again, which makes it overall N^2, which isn't helpful

[old rover]

i get it now

i re read it slowly

despacitooooooo

[jolly mortar]

the trick is to make it a set first, so you get O(1) membership tests

[jolly mortar]

this is essentially the same concept

[old rover]

i think i got it

[old rover]

up to hash tables now

i think that's it for today

gayle goes way too hard

lmao

but it's good

I'm making progress

[fiery cosmos]

can some one help me

i need to print 001 to 100

[dapper sapphire]

Do you know how to write a for or while loop?

[lyric aspen]

Does the popright() method of a collections.deque serve the same purpose as a stack?

I guess popleft() is FIFO which is an attribute of a queue?

[knotty magnet]

yes

[lyric aspen]

whats the point of using that versus just a list

[knotty magnet]

because you can popleft quickly

[lyric aspen]

quicker than a lists .pop() ?

[knotty magnet]

if you do pop(0) on a list, all the elements to the right have to shift left

this doesn't happen in a deque

[lyric aspen]

oh interesting, so the relative index of the queue is maintained?

[knotty magnet]

no

[lyric aspen]

because if I do a popleft on a queue and then another popleft, obviously the first 2 elements should have been popped

[knotty magnet]

yes

[lyric aspen]

can you make a blanket statement that bfs would always use a queue or can you use a stack?

[knotty magnet]

yeah, probably a queue

[knotty magnet]

it's because of how lists and deques are implemented

lists are a dynamic array, so to remove the first element you have to shift all the elements on the right to fill in the gap

deques are a doubly linked list, so removing the first element just removes the first element. none of the other elements have to be touched

[lyric aspen]

got it, thanks @knotty magnet

[tranquil vapor]

can you learn algo?

[knotty magnet]

you can

[old rover]

you can

[tranquil vapor]

how?

is it what you learn in basic python?

[shut breach]

no, data structures and algorithms aren't specific to any one language, and the topic isn't typically covered in basic python courses

you can check the pins in this channel for some DSA learning resources

@tranquil vapor

[tranquil vapor]

ahhh

aight thanks for the info

[fervent saddle]

Can’t you use hash tables with a trie instead of arrays in order to save space at the cost of speed? Why don’t people do that? Is it because it would defeat the point of using a trie instead of just using a hash table?

Would it probably end up being even slower because you’re hashing for each character instead of once for the whole string?
Also what are the reasons that all the nodes at the same depth can’t share the same array? Is it only because it would cause problems when you deleted a string from the trie because you wouldn’t know which characters were shared by multiple words? Or are there other reasons?

[rain viper]

Hey

how can i convert a column in my df from printing my values as "[value]" to "value"

[dapper sapphire]

Someone in that channel might be able to help you #data-science-and-ml since your question is more related to data science

[oblique panther]

What would be the runtime complexity of T(n) = 1 + 2 + 3 + 4 + 5 + ... + n?

[fervent saddle]

1 + 2 + 3 are the number of steps?

[oblique panther]

yes

[slim cape]

O(n)?

[oblique panther]

it's not O(n) for sure

[fervent saddle]

It’s O(n^2)
It’s like a triangle visually, half a square

[oblique panther]

Ah, so it's basically T(n) = (n ** 2) / 2?

[fervent saddle]

Yeah

[oblique panther]

thanks 😄

[fervent saddle]

nvm I think I get why:
"abcda"
"bcdea"
Those would both lead to the same spot

[fervent saddle]

Are there any ways and/or any situations that let trie nodes share the same arrays the way I’m thinking of? Or is it impossible?

[dapper sapphire]

Wondering what the time time complexity is of turning an int to a binary or int to a str and vice versa? Is it O(1)?

[knotty magnet]

log n for laatter

wdym "int to a binary" though

[fiery cosmos]

print(bin(0b1 << 2))

[dapper sapphire]

!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

[dapper sapphire]

Sorry, which one is log n? int to str?

[knotty magnet]

yeah

i don't know how bin works, so idk

[dapper sapphire]

Where n is the number of elements and not the length of the number?

[knotty magnet]

wdym elements, it's a number

[dapper sapphire]

So converting 123456789 to str would be O(1).

[knotty magnet]

it's log n

[dapper sapphire]

Ok

[fiery cosmos]

    def fib(self, n: int) -> int:
        # top-down dp/memo solution: O(n) time, O(n) space
        if n <= 1:
            return n
        self.dp = [0] * (n+1)
        return self.memo(n)
    def memo(self, n: int) -> []:
        if len(self.dp) >= n:
            return self.dp[n]
        self.dp[n] = self.memo(n - 1) + self.memo(n - 2)
        return self.memo(n)

trying to write fibonacci using top-down memoization/dp

the explained way I'm copying uses a dictionary

but I'm trying to do it with a list

is it possible?

[fiery cosmos]

i need some help

hello?

[shut breach]

#❓｜how-to-get-help

[fiery cosmos]

i created a help

channel

burrito

but no one is responding

[dapper sapphire]

I have seen people mention DP here before. Does that stand for Dynamic Programming?

[jolly mortar]

yes

[flat radish]

Best factorial function I've ever seen
def sol(n):
return 1 if n<2 and n*(sol(n-1))

[lean dome]

O(N) in all 4 cases. You can't convert an int to binary without looking at all N bits of the int. You can't convert a string to an int without looking at all N characters in the string. Etc. Granted N is different units in those two cases, but in both cases they scale linearly with something.

!e you can also see this experimentally:

from timeit import timeit
for i in range(3, 18, 3):
    number = 10**i
    time = timeit(f"bin({number})")
    print(f"{time} {number}") 

[halcyon plank]

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

001 | 0.17147679580375552 1000
002 | 0.17612868081778288 1000000
003 | 0.21081173093989491 1000000000
004 | 0.23536432161927223 1000000000000
005 | 0.25643296213820577 1000000000000000

[lean dome]

The bigger the number you call bin() on, the longer it takes. If something takes longer on bigger inputs, it cannot be O(1)

[fiery cosmos]

Worth emphasizing N is the number of bits there, proportional to the log of the actual number. So you might wanna say O(log(X)) where X is the number, i.e. pretty efficient, and constant O(1) if X has a bounded number of bits like 32.

[zenith wasp]

Is anyone able to give an eli5 on how IIR filters are able to function as e.g. lowpass filter despite only knowing about 3 inputs at a time?

[fervent saddle]

!e ```py
def fib(n, cache_list=[0, 1]):
if len(cache_list) <= n:
cache_list.extend([None] * (n - len(cache_list) + 1))
elif cache_list[n] is not None:
return cache_list[n]
result = fib(n - 1) + fib(n - 2)
cache_list[n] = result
return result

for n in range(1000):
print(n, fib(n))```

[halcyon plank]

@fervent saddle :white_check_mark: Your eval job has completed with return code 0.

001 | 0 0
002 | 1 1
003 | 2 1
004 | 3 2
005 | 4 3
006 | 5 5
007 | 6 8
008 | 7 13
009 | 8 21
010 | 9 34
011 | 10 55
... (truncated - too many lines)

Full output: too long to upload

[fervent saddle]

You mean like that?

[fiery cosmos]

Yea cool

[lyric aspen]

In this binary search implementation:

# Returns index of x in arr if present, else -1
def binary_search(arr, low, high, x):
 
    # Check base case
    if high >= low:
 
        mid = (high + low) // 2
 
        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
 
        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
 
        # Else the element can only be present in right subarray
        else:
            return binary_search(arr, mid + 1, high, x)
 
    else:
        # Element is not present in the array
        return -1
 
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
# Function call
result = binary_search(arr, 0, len(arr)-1, x)

Why is it that to get the upper bound, we do len(arr)-1 Wouldn't the total len be the upper bound?

[shut breach]

the maximum index in an array is one less than the length

if you passed in len(arr) and an x that was greater than everything in the array, eventually the algo would try to reference arr[len(arr)], which is an index error

[lyric aspen]

ahh right, because of 0 indexing

[fiery sinew]

Can someone suggest me where should i study DS from?? (for competitive programming)?

[dapper sapphire]

oh ok so that's how we can measure the execution time. Thanks!!

[shut breach]

check the pins

[fiery sinew]

Using c++ actually i am still not that comfortable in python

[copper heron]

when implementing quick sort and merge sort, will the algorithm perform better in c++ than in py?

[runic tinsel]

yes

[copper heron]

by how much?(rough est.)

[runic tinsel]

10x

[copper heron]

thnx

[runic tinsel]

10−40x roughly

although technically there's pypy which is itself 10 times faster than python, but it's like, python

[copper heron]

are the syntax same as py?

[runic tinsel]

yes

[copper heron]

interesting so why isn't python implementing things from pypy?

[runic tinsel]

i don't know

[lunar jacinth]

Could someone help with a hashtable understanding in #help-pineapple please

[knotty magnet]

pypy is python, just a different implementation

[dapper sapphire]

There is work being done to make python faster

[gritty tree]

Hey I was given this Question:

You are given a number, at a time either you can increase a number by 1 or decrease by 1 it is considered as one move find the minimum number of moves required to convert a given into a lucky number. A number is called lucky if all the digits in it are even

My approach is flawed and I keep getting errors.

can anyone help me out

[knotty magnet]

what's your approach?

[gritty tree]

this is what I tried to do

[lean junco]

thats my question plz read

[vagrant hawk]

how do i code 3D on python???

[fiery cosmos]

would performing an add at an arbitrary point in a linked list be constant or linear?

[knotty magnet]

linear

[fiery cosmos]

ok thanks

also, if you invoke the remove operation on an iterator object attached at an arbitrary location of a linked list, would that be constant or linear

[fervent saddle]

Wdym an add?

Like inserting something?

Or you mean something else?

Inserting in and removing from linked lists is always constant

Assuming you already have a reference to the spot you want to insert/remove

[fiery cosmos]

ok

I meant like, there's an iterator that points to an element

what is the big o to remove that elmeent

[fervent saddle]

If you have a reference to the node you want to insert at or remove then it’s O(1)

[fiery cosmos]

ok perfect

just curious, what would be the big o of removing every other element of a linked list

[fervent saddle]

He was probably thinking of the complexity of if you had a linked list of numbers, and you wanted to add some amount at a random spot
Or maybe he was thinking of if you didn’t already have a reference to the right spot, which I’ve heard is often the case in real world situations which is one of the reasons why linked lists aren’t used very often

[fervent saddle]

Which would be O(n)

[fiery cosmos]

this is the code that I wrote to remove every other element

would this be o(n)?

[fervent saddle]

It’s O(n) because it involves the whole list and increases at a linear rate

[knotty magnet]

the latter.

[fervent saddle]

Yeah. There’s some article that mentions exactly that situation

It might have been this one: https://dzone.com/articles/c-benchmark-–-stdvector-vs

[heady lichen]

Does anyone know anything about linked lists? And whether you can use them in Python?

[vocal gorge]

They are a data structure that can be implemented in Python, yeah.

(and internally, a linked list of arrays is used for collections.deque)

[umbral hound]

Hello, I'm new to machine learning and I'm creating a crawler and it should classify if a given URL is an article link or section link. My use cases are to determine if a web page is an article link is based on the structure of Document Object Model(DOM), because an article link would always have a title and content, and for the section link it is the opposite of the structure of article link's DOM structure.

I'm not yet sure if I should use random forest algorithm to classify a web page or other algorithm to perform a DOM analysis to classify if its an article link or section link. Any thoughts?

[heady lichen]

Thanks, i'm trying to build an inverted index. Do you know anything about it?

[smoky widget]

i say oooooo

i am drowning in the night

when i am like this ur the one i trust

[lunar jacinth]

Could someone help me in #help-pancakes It's on hashing

[tawdry compass]

anyone able to help with basic pandas stuff in #help-apple

[last fulcrum]

A python module used to implement stacks and queues

[jolly mortar]

similar to how a list allows fast pops and appends at the end of the list, a deque allows fast pops and appends at both ends

[last fulcrum]

Exactly why I love python. No need to write a stack myself using a linked list.

[knotty magnet]

why would you ever need to do that in any language

[last fulcrum]

Cause it's not implemented natively in most languages. And you have do to it yourself. Ex: C and C++

[knotty magnet]

does cpp not have a vector

[last fulcrum]

Yea I think so

It has

[knotty magnet]

and you can use that as a stack

[tight sentinel]

have you tried STL?

It has stack, queues, arrays, maps all in it, you don't have to implement them

[last fulcrum]

What's that?

[tight sentinel]

https://www.geeksforgeeks.org/the-c-standard-template-library-stl/

[last fulcrum]

Thanks

[narrow horizon]

Do anybody got solution for this?

[gritty tree]

Nope. Figured it out myself.

[narrow horizon]

How??

What's the solution?

[narrow horizon]

def evaluate(array):
    times = 0
    decimal_place = len(array)-1
    for n in array:
        if n%2 != 0:
            times = times + 10**decimal_place
        decimal_place -= 1
    return times

if __name__ == '__main__':
    num = input("Enter no: ")
    array = [int(x) for x in str(num)]
    times = evaluate(array)
    print(times)

I find this solution best for your problem

[old rover]

holy shit data structures are mind numbingly easy once you understand OOP

i think I watched Gayle's video on linked lists like maybe 15 or 20 times

whatever it takes really

pomodoro technique is helping a lot too

i am seemingly better at turning java into python

[waxen swift]

Hello guys. i have a question in webscraping using python

can you help me??

[dapper sapphire]

#web-development might be the right channel for that

[waxen swift]

Hello guys. I badly need help, I need to do a webscraping. To give you details, They gave me a zip folder to extract a file, inside that extracted file was 3 folders with python codes, they told me to use beautifulsoup and pip. so after extracting it, I dont know the next thing to do. here is the screenshot. the notepad was the extracted file with codes then the other side is a jupyter notebook which I prefer to use. Unfortunately, it is not working

[old rover]

class Node:
  class Queue:
    def __init__(self, data, node, head, tail):
      self.data = data
      self.node = node
      self.head = head
      self.tail = tail

    def is_empty(self):
      if self.head is None:
        return

    def peek(self):
      return self.head.data

    def add(self, data):
      node = Node(data)
      if(self.tail is not None):
        #can you use a while loop here?
        self.tail.next = node
      if self.head is None:
        self.head = node
    
    def remove(self):
      data = self.head.data
      head = self.head.next
      if head is None:
        self.tail = None
      return data
 

i wrote this stuff based on what gayle did in her video on stacks and queues

i don't get that remove method

actually maybe I do

the head is now the node that came after the original head

and it's returning the data of the original head?

also can't you use a while loop where I wrote if self.tail is not None?

I had to flip the order of the classes

I put Node as the outside class and Queue as the inside class

also gayle uses a constructor.... do I have to use a constructor?

i'm sorry if i'm overwhelming or spamming

[last fulcrum]

Ask all your questions here. We're not bothered.

[last fulcrum]

The woman who wrote cracking the coding interview?

[old rover]

yep

she's a good resource

it's in java but that's alright

[dapper sapphire]

I think java is really hard.

So if someone tried coming up with all the algorithms that are out there on their own without looking up the original implementation.
I dont wanna say it would be impossible, but it would just take a long time and a lot of mental power?

And even people who wrote algorithms, they had to first read other people's algorithm to build up a mental model

[old rover]

i think i've stared at java enough to get it into my head now

and plus implementations of DSs aren't really in Python

i think CLRS is also in Java

[cosmic geode]

Hey guys, I'm trying to wrap my head around octrees. I was trying to throw a simple prototype of a tree building algorithm together, but I became a bit unsure about my understanding...
Do you actually "generate" octrees from another data structure? or is the octree both the graph and the primitives?

So far I've just used a BVH. I would just take a chunk of voxel data in my world grid, find the outer bounds, and recursively subdivide it until I had leafs of primitives (a single voxel). My initial approach for octrees was to just do the same, except with more subdivisions, but that's not how they work, is it?
I just don't think that starting with a root node, and continously expanding the graph through insertions seem like a very efficient approach either

An ELI5 or just a suggestion for a good learning resource would be great

[outer roost]

Does anyone have any idea what data format this is

[dapper sapphire]

Looks like a dictionary or json

[cosmic geode]

I don't think that's what he meant

[outer roost]

Looks like json, it’s not though

[outer roost]

I’m just trying to find out what it’s serialized in so i can parse it more easily

[old rover]

it's if a dictionary tried to be lasagna

[knotty magnet]

it's pseudocode

[old rover]

oh

ok then

[frank summit]

Question on median vs quantile(0.5) and mean. When I run these on a series all 3 are different. I would expect median and quantile to be the same

[cosmic geode]

well, first off quantile is not a single value. it's any division in a range of values. you are thinking of the 2nd quartile, or the 50th percentile

mean is the average value, while median is just the middlepoint of the range

[dapper sapphire]

Are you getting this response from Bloomberg API by any chance?

[frank summit]

Isn't 50th percentile and middlepoint of the range the same thing?

[last fulcrum]

Or you implementing a queue or a linked list?

[last fulcrum]

Median and 2nd quartile are the same

[lunar jacinth]

class Node(object):

    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None


class BinarySearchTree(Node):
    def __init__(self,data):
        super().__init__(data)
        self.list = []

Would this be the correct way to initialize my BinarySearchTree?

[knotty magnet]

it doesn't really make sense that your binary search tree would be a subclass of Node

[lunar jacinth]

i cant do .data though then can i?

[knotty magnet]

well, no

[lunar jacinth]

z = BinarySearchTree()
z.insert(3)

I'm trying to see if it gets inserted

[lunar jacinth]

would this be the correct way of doing so?

[knotty magnet]

of doing what

[lunar jacinth]

inserting into my binary search tree

[lunar jacinth]

im trying to test my insert method out

    def insert(self, root, key):
        if root is None:
            return Node(key)
        else:
            if root == key:
                return root
            elif root.data < key:
                root.right = self.insert(root.right, key)
            else:
                root.left = self.insert(root.left, key)
        return root

[lunar jacinth]

so wouldnt i need Node inherited here?

[knotty magnet]

no, that doesn't make sense

[lunar jacinth]

so my insert function is wrong?

[outer roost]

Yeah, figured it out though

it’s an element

Just have to use get element to get value

Have you used it before?

[dapper sapphire]

I havent used it before. I came across a SO post, and the response structure looked similar to yours:
https://stackoverflow.com/questions/56166313/parse-bloomberg-api-response-to-json-in-python3

[old rover]

Queue

[outer roost]

in this case i’m not using python but yeah

same thing

[last fulcrum]

Use a deque to implement a queue

Like this

from collections import deque
from typing import Union


class Queue:

    def __init__(self) -> None:
        """
        Initializes the queue object.
        """
        self.queue = deque()

    def is_empty(self) -> bool:
        """
        Returns True if the queue is Empty else False.
        """
        return len(self.queue) == 0

    def enqueue(self, element) -> None:
        """
        Adds an element to the front of the queue.
        """
        self.queue.appendleft(element)

    def dequeue(self) -> Union[str, int, None]:
        """
        Removes an element from the queue and returns it.
        """
        if not self.is_empty():
            return self.queue.pop()
        return None

    def top(self) -> Union[str, int, None]:
        """
        Returns the first element in the queue but does not remove it.
        """
        if not self.is_empty():
            return self.queue[-1]
        return None

    def size(self) -> int:
        """
        Returns the size of the queue.
        """
        return len(self.queue)

[knotty magnet]

but why, just use deque as a queue

[old rover]

what was wrong with what I did

[wooden pecan]

class Node:
    def __init__(self,data):
        self.data=None
        self.nextNode=None

class linkedList:
    def __init__(self):
        self.head=None
        self.numNodes=0
        
    #Coming to the LL functions:
    def insert_at_start(self,data):
        self.numNodes=self.numNodes+1
        new_node=Node(data)
        
        if not self.head:
            self.head=new_node
        else:
            new_node.nextNode=self.head
            self.head=new_node
    
    def insert_at_end(self,data):
        self.numNodes=self.numNodes+1
        new_node=Node(data)
         #First we need to init the nodes to the last one; Linear search
         
        present_node=self.head
         
        while present_node.nextNode is not None:
            present_node=present_node.nextNode
        
        present_node.nextNode=new_node
    
    
    def size_of_ll(self):
        return self.numNodes
    
    
    def traverse(self):
        present_node=self.head
        
        while present_node is not None:
            print(present_node.data)
            present_node=present_node.nextNode
            
ll = linkedList()
ll.insert_at_start("Adam")
ll.insert_at_start(169)
ll.insert_at_end(53)
ll.insert_at_end(99)
ll.insert_at_start("EVE")
print(ll.size_of_ll())
ll.traverse()

Can someone help me with this? I am getting
None
None
None
None
None

As in the elemtns i Push into the list are not showing

[austere sparrow]

You never use data in Node's __init__

[last fulcrum]

Arrays are slow.

A list, when the elements are large is far slower than a linked list

Especially an optimized linked list.

[knotty magnet]

a deque is not an array

idk what your point with that is

you're using a deque in an implementation of a queue when you could just be using the deque as the queue

[last fulcrum]

I wanted to. Everyone has how they learn

[knotty magnet]

ok

[last fulcrum]

And for array I meant stack

Sorry

[livid rapids]

Hello There,
i have a question about generators since i couldnt find anything helpful on stackoverflow ill ask it here right away.

i'm trying to chain multiple generators where the output of generator_1 is the input of generator_2 and so on for n generators. Could someone explain to me how to actually solve that? im ending up with the 'generator' object is not subscriptable. The error is not the problem but more the understanding of how to solve such an pipeline-filter problem in the right way

[trim fiber]

!e

data = [0, 1, 2, 3, 4]
gen = (x ** 2 for x in data)  # generator
gen = map(str, gen)  # another generator by using map
output = ",".join(gen)
print(output)

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

0,1,4,9,16

[trim fiber]

How you chain generators?

!e

data = [0, 1, 2, 3, 4]
gen = (x ** 2 for x in data)
gen = (x + 1 for x in gen)
gen = map(str, gen)
output = ",".join(gen)
print(output)

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

1,2,5,10,17

[trim fiber]

Another simple example

[livid rapids]

thanks 🙂 thats helpful!

[livid rapids]

appreciated your help, but im still kinda stuck..
i'm trying to iterate over a list of functions instead of calling a generator after another.
is there a simple way to make this work?

# instead of:
gen = ({k: v} for k, v in dict_.items()) # initial data split
gen = (add_a(e) for e in gen) # generator 1
gen = (add_b(e) for e in gen) # generator 2
# do something like
gen = ({k: v} for k, v in dict_.items()) # initial data split
for function_ in functions: # functions: [add_a, add_b]
    gen = (function_(e) for e in gen)

def add_a(x):
    return {k: v + 'A' for k, v in x.items()}

def add_b(x):
    return {k: v + 'b' for k, v in x.items()}

dict_ = {'a': 'a', 'b': 'b', 'c': 'c', 'd': 'd', 'e': 'e'}
functions = [add_a, add_b]

gen = ({k: v} for k, v in dict_.items()) # initial data split
gen = (add_a(e) for e in gen) # generator 1
gen = (add_b(e) for e in gen) # generator 2
result = dict()
for entry in gen:
    for k, v in entry.items():
        result[k] = v
print(result)

Thanks!

[vocal gorge]

So you want to apply the composition of several functions to every element in an iterator? While this could be done with reduce, that'd be much uglier than a solution utilizing a loop, i.e.:

for func in functions:
    gen = map(func, gen)

[livid rapids]

Yes in the end im trying to process a Dataset by a combination of steps. sometimes the data has to be processed by generator1, generator2, generator3 but on other runs it would be enough to simply pass it through generator3. This is why i would like to make it as simple as possilbe.

Thanks for your help, somehow it seems so easy, but i havent thought of it

[fiery cosmos]

How can I get the first common multiple of two numbers x and y, which is also greater than z?

[plush owl]

Unfortunately, I've to parse a debug string and construct a binary tree.
The string looks like this.

   If (u_l_a <= 1.0)
    If (t_rev <= 2.5)
     Predict: 0.0
    Else (t_rev > 2.5)
     Predict: 1.0
   Else (u_l_a > 1.0)
    If (h120 in {1.0})
     Predict: 0.0
    Else (h120 in {0.0})
     If (u_mb <= 9)
      Predict: 1.0
     Else (u_mb > 9)
      Predict: 0.0
"""

How do I go about it?

x = [i.strip() for i in x]

class Node:
    def __init__(self,  data):
        self.data = data
        self.left = None
        self.right = None```

[trim fiber]

Next time please ping me 👍

[plush owl]

after this I'm iterating over each line, but how do I insert into the correct node

[trim fiber]

Hmm, nice question

[fiery cosmos]

def ClosestMultiple(n, x):
    if (x > n):
        return x
    else:
        n = n + x / 2
        n = n - (n % x)
        return n

print(ClosestMultiple(5000, 3900))```

Here's what I currently have, so for example ClosestMultiple(5000, 3900) returns 3900 when Ideally I'd want 7800 (first multiple > 5000)

[trim fiber]

Oh, it's not Python

[fiery cosmos]

Whoops

there

[trim fiber]

Better ❤️

Do you have some example datasets for x, y, z?

I am thinking about something like lcm(x, y) * lcm(gcd(x, z), gcd(y, z))

[plush owl]

if x > 0:
    return ((n // x) + 1) * x
else: 
    return n + 1

[fiery cosmos]

n is the ideal server batch size (5000), x is the client specified batch size (can vary between 1000-10000), and I'd like to calculate the first multiple which is above 5,000 but below 10,000 (which it always should be anyways)

[fiery cosmos]

This works perfectly, thanks!

[kindred imp]

hi, hoping to get some help with a merkle tree traversal

I have a data structure that looks like this

https://www.dropbox.com/s/wwrwxybhfaad8xr/Screenshot 2021-07-22 13.46.19.png?dl=0

I was wondering how I might go about looking up a value wthin the tree and then from that location moving back up the tree to prove inclusion

def proof_of_inclusion(block):
    if not block:
        return
    print(block.hash_value) 
    proof_of_inclusion(block.child_left)
    proof_of_inclusion(block.child_right)```

so this will print out all of the hash values

is there a way of knowing how deep into the tree i am and whether its a left or right leaf

class MyMerkleTree():
    def __init__(self, hash_value):
        self.hash_value = hash_value
        self.level = 0
        self.child_left = None
        self.child_right = None```

so i record the level of the tree when I build it

so i can call that, but I don't store whether it's right or left when i build it

[native terrace]

can anyone help me what to do here ?

[cyan pulsar]

You can pick which version of python you want to use on vs code

You can pick the one you want to use

[knotty magnet]

that looks like pycharm, but yeah

[cyan pulsar]

Still same idea

[nocturne ginkgo]

I'm having trouble processing the exponent equation for a situation. If any math experts can help me with this, I'd appreciate it.

for each flower, you get 18 guaranteed seeds that grow into a flower. so if you plant a flower, it makes 18 more and itself dies.

Then those 18 make 18 each and die.

Then those 324 make 18 each and die.

Whats the exponential equation here...

[jolly mortar]

17^n?
x_n+1 = 18*x_n - x_n = 17x_n

[nocturne ginkgo]

I came to a similar conclusion, but just going off the number of cycles

I'm not sure why this was so hard for me to workout

been dealing with exponents for 20 years...

here and there at least

index representing cycle, left number representing number of flowers, right number representing number of new flowers

[jolly mortar]

how can it be 18^n if some of them are dying \🤔

[cyan pulsar]

Thats what the -x_n is for

[nocturne ginkgo]

so on cycle 3 for example

we have 324 flowers

they have 18 seeds each

18^3 = 5832

I'm honestly not sure my information is valid

that's how much trouble I'm having with this

should be 324*18

which is also 5832

I have no idea why it works

[jolly mortar]

if you have x_n flowers at some stage, in the next stage you'd have 18x_n flowers if none of them died
but x_n of them are dying, so you end up with 18*x_n - x_n = 17x_n in the next stage

so you'd have 17^n flowers after n cycles

[nocturne ginkgo]

the numbers on the left represent flowers not including the flowers that seeded and died

1 flower makes 18 more

18 flowers makes 324 more

324 makes 5832 more

respectively:

18 does not include the original 1

324 does not include the original 18

5832 does not include the original 324

so if I want to represent the number of flower after 9 cycles, I can do 18^9, which is:

198359290368

or 11019960576 * 18, which is the same result

I think it works because the way the question and formula are presented already excludes the seeded and dead flowers?

idk

ah, I see, it only works if you start with 1 flower

That's why they line up

[last fulcrum]

I have an implementation of quickselect that finds the smallest kth element in an array

How can I modify it to give me the kth largest element

def partition(array: List[int], lowerbound: int, upperbound: int) -> int:
    """
    Partitions the array so that lower items are to the left of the pivot and bigger items are to the right.
    """
    pivot = array[upperbound]
    index_1 = lowerbound - 1

    for index_2 in range(lowerbound, upperbound):  # we loop from lowerbound and stop just before the pivot.
        if array[index_2] < pivot:  # if the value at index 2 is less than the pivot.
            index_1 += 1
            array[index_1], array[index_2] = array[index_2], array[index_1]  # swap index one and two
    array[index_1 + 1], array[upperbound] = array[upperbound], array[index_1 + 1]
    return index_1 + 1  # return the pivot(basically it's index)


def quick_select(array: List[int], lowerbound: int, upperbound: int, item_index: int) -> int:
    """
    Performs the quick select algorithm.
    """
    if lowerbound >= upperbound:
        return array[lowerbound]

    pivot_index = partition(array, lowerbound, upperbound)
    if pivot_index == item_index:
        return array[item_index]

    if pivot_index > item_index:
        return quick_select(array, lowerbound, pivot_index - 1, item_index)
    else:
        return quick_select(array, pivot_index + 1, upperbound, item_index)

[austere sparrow]

@last fulcrum The easiest way is probably to accept a key function, like sort or max does

Then you can do quick_select(the_list, key=lambda x: -x)

[last fulcrum]

I've never implemented a key myself. How would I go about it?

[austere sparrow]

Try implementing your own max that accepts a key

Have you ever written a function that accepts a function as an argument?

[last fulcrum]

Yes I have. To tell you the truth it was long ago so I've forgotten

[austere sparrow]

well, it's no different than any other function

!e

def apply_twice(f, x):
    return f(f(x))

def add_one(x):
    return x + 1

print(apply_twice(add_one, 5))

[halcyon plank]

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

7

[last fulcrum]

Ok thanks for that. I'll implement the max function later on

[dapper sapphire]

!zip

[halcyon plank]

The zip function allows you to iterate through multiple iterables simultaneously. It joins the iterables together, almost like a zipper, so that each new element is a tuple with one element from each iterable.

letters = 'abc'
numbers = [1, 2, 3]
# zip(letters, numbers) --> [('a', 1), ('b', 2), ('c', 3)]
for letter, number in zip(letters, numbers):
    print(letter, number)

The zip() iterator is exhausted after the length of the shortest iterable is exceeded. If you would like to retain the other values, consider using itertools.zip_longest.

For more information on zip, please refer to the official documentation.

[dapper sapphire]

Is there a simple way to generate sub_arrays? I feel the below gets a bit confusing

!e

arr = [1,4,2,5,3]
for i in range(len(arr)):
    for j in range(len(arr) - i):
        sub_array = arr[i: i+j+1]
        print(sub_array)

[halcyon plank]

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

001 | [1]
002 | [1, 4]
003 | [1, 4, 2]
004 | [1, 4, 2, 5]
005 | [1, 4, 2, 5, 3]
006 | [4]
007 | [4, 2]
008 | [4, 2, 5]
009 | [4, 2, 5, 3]
010 | [2]
011 | [2, 5]
... (truncated - too many lines)

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

[dapper sapphire]

[1]
[1, 4]
[1, 4, 2]
[1, 4, 2, 5]
[1, 4, 2, 5, 3]
[4]
[4, 2]
[4, 2, 5]
[4, 2, 5, 3]
[2]
[2, 5]
[2, 5, 3]
[5]
[5, 3]
[3]

I feel the slicing portion gets a bits confusing

[dapper sapphire]

This is sad. I did something similar a week ago, but with strings and that generated empty string so I had an if statement to check if the sub_string is empty

[fiery cosmos]

!e You might tweak the ranges to make the names clear py def subs3(arr): arrs = [] for start in range(len(arr)): for end in range(start+1, len(arr)+1): arrs.append(arr[start:end]) return arrs print(subs3([1, 4, 2, 5, 3]))

[halcyon plank]

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

[[1], [1, 4], [1, 4, 2], [1, 4, 2, 5], [1, 4, 2, 5, 3], [4], [4, 2], [4, 2, 5], [4, 2, 5, 3], [2], [2, 5], [2, 5, 3], [5], [5, 3], [3]]

[fiery cosmos]

And I think this with combinations_with_replacement is equivalent

!e py from itertools import combinations_with_replacement as cr def subs2(arr): arrs = [] for i, j in cr(range(len(arr)), 2): arrs.append(arr[i:j+1]) return arrs print(subs2([1, 4, 2, 5, 3]))

[halcyon plank]

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

[[1], [1, 4], [1, 4, 2], [1, 4, 2, 5], [1, 4, 2, 5, 3], [4], [4, 2], [4, 2, 5], [4, 2, 5, 3], [2], [2, 5], [2, 5, 3], [5], [5, 3], [3]]

[fiery cosmos]

Also you'd want to include the empty array to be truly all subarrays

[dapper sapphire]

I like how you used start and end, definitely makes it a bit easier to read

[fiery cosmos]

Can anyone glance over this complexity classes poster thing I made and verify that it's all correct - or at least understandable?

[austere sparrow]

I don't think N ^ O(1) and such makes sense. Did you mean O(N ^ k), where k is a constant?

also, if it's a poster, you can use actual superscript notation for powers

[fiery cosmos]

I wanted to but the design app couldn't do a double superscript for the 2^N^O(1)

[fiery cosmos]

And yeah, this is the proper way to write it but I'm running out of space, and the original guy did put it that way

[austere sparrow]

I think it's abuse of notation

just write O(N^k) and O(2^(N^k))

I guess it's a shorthand for O(n ^ f(n)) where f(n) = O(1)

[fiery cosmos]

I agree it looks better, though the font I'm using has a tiny caret 🥕

[austere sparrow]

exponential time should be exponential

i.e. O(2^(N ^ k))

[fiery cosmos]

oh yeah

Thanks improved

Now how long until the Clay Institute ups their $1 million Millennium prize to match inflation should be more like $1,577,793.26 by my calculations

[shut breach]

yeah but the longer it takes us the less we deserve

[brisk terrace]

What algo would be efficient for a string sort

[burnt nest]

Sort it like a list

[keen hearth]

If you mean sorting a collection of strings, you may want to look into radix-sort and tries.

[viscid pumice]

I have a list of pre-determined events (say A,B,C,D,E). Throughout the day, I'll have a collection of event a1, a2, b1, c1, b2, c1, c2, c3, d1 in any order
I want to store this chain of events in such a way that I can:

1. Fetch only the 'X' events [A or B or C or D or E] from the chain.
2. Fetch the entire chain of events
   What data structure would give me the most optimal solution in this regard? What is the best way to go about handling this?

[keen hearth]

Hey, I'm not sure I understand. So you have a sequence of 'events', and each event falls into a category. You want to be able to easily extract the sequence of just the events from one category?

[viscid pumice]

yes, that's correct

[keen hearth]

Maybe you could use a linked list, where each node points not just to the next event in the main sequence, but also to the next event in its own category.

[viscid pumice]

Valid point. But, this could make insertion slower. I'll definitely consider this.

[keen hearth]

Slower relative to?

[viscid pumice]

I don't have any reference in mind; I was just assuming that because I'd need to traverse in backward direction through the last node in order to insert the next event of similar category. Note* The last node will be my active node at all times

[keen hearth]

Ah right. You could perhaps also maintain a hash-table of nodes, to access the node associated with an event in O(1) time.

[viscid pumice]

Wouldn't that cause a clash though? Because similar events can be present in many nodes at once. For eg: a1 -> a2 -> b1 -> a3 -> b2 -> a4
In this case, a1 and a2 would have the same hash because we're running under the assumption that each event is a node of its own.
Edit: I just realized as I was typing this out that I could set a1 to be the parent node and traverse in not O(1) but O(m) [m : max length of event]

[stable pecan]

what you might want to do is keep separate sorted lists for each event type --- to get all events sorted you can use heapq.merge

merging sorted lists is fast

you can also merge two or more types if you don't want all the events but only say A and B events

because merging is fast

[solid gull]

Hi, about operators: the order is:
(), **, +x, -x, *, /, //, %, +, -

I don't get this one:
5 / (2 - 3) * 2 #result = -10

I get another result, -2.5, i do:
2-3 = -1
-1 * 2 = -2
5 / -2 = -2.5

can anybody explain?

[stable pecan]

the *, /, //, operators have the same precedence --- so the leftmost one is done first

[viscid pumice]

Hmm... this does sound interesting and bears no overhead to my implementation. Thanks @stable pecan . I'll take a look into this as well

[solid gull]

thank you @stable pecan , I couldn't read that in the order of operators

[vapid dirge]

im looking for algorithm that takes params int x and int n and creates a list with length of n with random ints that sum up to x

[timid sequoia]

How to create ASCII Mountain map in pure Python with input as number Series

[shut breach]

with what distribution?

[knotty magnet]

[x] + (n-1)*[0] 🎉

[kind night]

Carry

[keen hearth]

Perhaps you're looking for a Dirichlet distribution?

[austere pike]

hi

[keen hearth]

!eval ```py
import numpy as np

def foo(x, n):
return x * np.random.dirichlet([1] * n)

print(foo(5, 10))

[halcyon plank]

@keen hearth :white_check_mark: Your eval job has completed with return code 0.

001 | [0.35319467 0.03863742 0.08606454 0.08990213 0.71744555 0.43287303
002 |  0.90408936 0.13358966 0.10614465 2.138059  ]

[stark basalt]

help why does this not work valid = re.findall('(^+1\d{10})',pnumber)

it finds a match even when its more than 10 numbers following the 1

(if this isnt the right channel tell me)

[hidden fiber]

has anyone tried algoexpert?

[fiery cosmos]

I've tried their free questions and seem mostly the same as LeetCode or lots of other sites that have way more for free

[onyx root]

everyone should boycott coding interviews that quiz you about data structures and algorithms.

or go to the interviews, and when they ask you to reverse a red-black linked list or whatever, say, "I'll be able to google that later, didn't you want to ask me anything more substantive?"

and then instead of studying for interviews, you can spend your time writing interesting projects that teach you useful things instead.

[austere sparrow]

sounds like a good idea

but I have a suspicion that I'll never get a job if I employ that tactic 👀

[onyx root]

idk, you might stand out from the crowd. Do you have code you have written that you can talk about?

[austere sparrow]

I guess

[elder sand]

This is probably the wrong place, but I wasn't really getting anywhere in #python-discussion.
Does someone mind explaining the significance of this error?

TypeError: Object of type LazyList is not JSON serializable

I got it trying to return a JSON Response of a structure in Starlette

[ivory yacht]

Well, your structure contains a "LazyList" object, which the json module doesn't recognise - it only does basic types like lists, dicts, strings, numbers etc. Not familiar with Starlette so I don't know exactly what that is, but you can either edit the structure to make it a regular list, or subclass JSONEncoder and override default to convert it to something else.

[runic tinsel]

Talking about an algorithm lets them know that you'll be able to 1) understand that you need this algorithm 2) modify it so it actually fits. I've never been on a single interview so I may be missing something.

having google, even if it's literally in your brain and you can query at the speed of thought doesn't help

[onyx root]

but the algorithms that people study: almost no one needs to implement those algorithms

and "invert this tree" or whatever doesn't get you to talk about why you might need the algorithm, it just tests your knowledge of the algorithm.

[runic tinsel]

so you want to talk about a different algorithm that you made for some task?

why though

they don;t know it, how can they tell if you're right

[onyx root]

i think it's more useful to talk about things you have built, and the decisions you made along the way.

[runic tinsel]

basically when you'll need an algorithm you'll need someone to tell you what to google

they prefer to not have that person employed, and rely on the programmer to tell himself

[onyx root]

a discussion about which data structure to use when would be good. implementing data structures is just trivia.

[runic tinsel]

it suggests that you can maybe implement another data structure if you know how to implement a specfic one

[onyx root]

i'm not sure how else to say this: you don't have to implement these data structures.

[runic tinsel]

talking about which data structure to use doesn't suggest that to me

alright, I'll wait until i get invited to an interview

2034 maybe

[onyx root]

i'm not sure why you are focused on the idea of implementing data structures

[runic tinsel]

can you guess?

[onyx root]

no, that's why i said i wasn't sure 🙂

[runic tinsel]

don't ever say "I'm not sure" when you can;t even start to guess

it suggests you have theories

[onyx root]

I don't know why you are focused on the idea of implementing data structures

[runic tinsel]

it's much harder to fake

[onyx root]

it's also not something employers need

[runic tinsel]

you said it's trivia, I don't get that

[knotty magnet]

it's trivia because there's no real world application to implementing an arbitrary data structure

[onyx root]

It's something you won't have to do, and you can study for to cram into your head. Then you get into a real job, and the things you actually have to do are different, and require thinking and communicating.

[runic tinsel]

you suggest talking about things that actually happen when working

like what does it show

[onyx root]

it shows that you'd be good at working.

[runic tinsel]

it's more relevant to what you'll be doing, it's almost not filtering candidates though

[onyx root]

i have no idea what you are talking about. You seem to be saying that it's irrelevant to talk about work-related skills?

i must be misunderstanding

[runic tinsel]

i mean talking is not showing a skill

i don;t think you;re misunderstanding at all

[onyx root]

talking about what you have built shows both that you can build things, and that you can talk about it.

[knotty magnet]

being able to talk about something implies understanding

[runic tinsel]

okay, I've no idea how to counter

[austere sparrow]

I don't think talking and implementing a data structure is a dichotomy. Why not ask the interviewee to implement something that's closer to what they're going to be doing on the job? For example, present a piece of code (like https://github.com/yegor256/quiz) and ask how they would refactor it.

[onyx root]

that would be better, yes.

if you can study for an interview, then it's a bad interview.

[runic tinsel]

that was my point too i think

building things counts as studying if the interview is about how you built things

no, that couldn't be my point

i just made that up

unless you're actually arguing for interviews that are harder for you personally, we kinda have the same position, "the thing that's harder for me shouldn't be tested for, because it's too easy"

[onyx root]

i haven't talked about harder or easier. I talked about useful

[runic tinsel]

uh, then I misunderstood

why "you can study for an interview, then it's a bad interview"

if easiness is not relevant

[onyx root]

because it's shallow knowledge you gain for the interview, and it's not knowledge that is useful on the job.

[runic tinsel]

but you can study for useful deep knowledge too

ok, a misunderstanding

[onyx root]

good, then it's useful.

except the things I want to find out in an interview you can't study for.

[elder sand]

What’s the original point of discussion?

[onyx root]

i want to know how the person thinks.

[elder sand]

Sounds interesting

[onyx root]

i want to know if they can express their ideas, in code, and in words.

i want to know if they are self-reflective about their work.

[onyx root]

i claimed that questions about implementing data structures are bad questions for an interview.

[elder sand]

Sounds not black and white too.
Like you learn a lot of vocabulary in programming and anything else, and some of interviewing is showing you can articulate

Really? Those are my favorite interview questions

[runic tinsel]

the counterpoint I'm parroting is that you can't test for that, but now I doubt it

[elder sand]

Otherwise it tends to boil down to language trivia like “what happens if you extend a class in this really pathological example”

[elder sand]

Are you more in favor of testing algorithm knowledge instead then? That can get even more esoteric past like “demonstrate DFS”

[onyx root]

no, algorithm knowledge is useless

[runic tinsel]

they want to chat about past experience

[elder sand]

Useless?! That’s a really bold claim

[runic tinsel]

sort of prove the cv

[elder sand]

Proving CV is useful

[onyx root]

if you mean knowledge about how to implement algorithms like balanced trees or hash tables, then yes, it's useless.

[elder sand]

Immediate question is why you think that haha. I think it’s great knowing how to make an efficient algorithm

Maybe there’s some disconnect with definitions or something

[onyx root]

generally knowing how to code efficiently is good. Quizzing candidates about details like balancing trees is just trivia.

[runic tinsel]

The interview is short and shallow by its nature. It doesn't matter what it consists of.

[elder sand]

Like I don’t think turning it into a programming competition is useful

[onyx root]

it doesn't matter?

[elder sand]

I think implementation of a balanced tree is overly deep for an interview, but whiteboarding something sounds good

Like there are tangible real world benefits to knowing algorithms and data structures, especially wrt efficiency

[onyx root]

This got started because someone said they were studying up on algorithms and data structures

[onyx root]

maybe i don't know what you mean by "knowing algorithms"

[elder sand]

Yeah, I can elaborate

For instance, I might ask a junior something like “when would you use a list vs dict vs set etc”. Basic data structures

[onyx root]

that is good knowledge

[elder sand]

For someone a little more knowledgeable, I think asking about trees, graphs, and some of the basic algorithms with those are fair game

They come up a lot in practice

[onyx root]

what do you mean, asking about algorithms? What would you ask them?

[elder sand]

How would you determine a graph is a tree

And give the formal definitions of those

Tree is a graph, but each node having only one parent

[brave oak]

I'm p sure that's not sufficient...?

[elder sand]

That’s not as important for the interviewee to know, although prior intuition is a plus

[brave oak]

it has to be acyclic

does "parent" imply that?

[elder sand]

Yeah you’re right, meant to haha

[brave oak]

actually, for that matter

it has to be connected too

right?

[knotty magnet]

yeah

[elder sand]

Yeah