Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
Mr SuperAwesome
Apr 6, 2011

im from the bad post police, and i'm afraid i have bad news


Steve Jorbs posted:

I would tell them no even if it wasnít illegal.

Adbot
ADBOT LOVES YOU

AWWNAW
Dec 30, 2008



raminasi posted:

ask for the request in writing, either you have a small chance to get them in Actual Trouble or you get to see some funny floundering

cinci zoo sniper
Mar 14, 2013



Mr SuperAwesome posted:

lol big O poo poo is something i am also terrible at because i studied physics not compsci, so i usually handwave this poo poo away with "uhh IO or network is probably slower, yolo" but really dict lookups are o(1)?

themoreyouknow.gif

i did celestial mechanics and radio astronomy later and i only know the o notation poo poo for the extent id expect to come up in an interview, so same actually. and yeah, python dictionary is what is called a hash map, so the access time complexity is o(1) average and o(n) amortised worst case - which makes it very useful for adhoc caching

cinci zoo sniper
Mar 14, 2013



Mr SuperAwesome posted:

how much do you reckon you can get away with in interviews by saying "yeah well i would aim for an XYZ approach (hashmaps, always hashmaps) but in my professional experience CPU/mem optimization has never been the bottleneck, only ABC" and elaborate on how you would solve various other bottlenecks

or is it just a crapshoot of company/interviewer/question and hope you get lucky (i presume the latter)

if that doesnít work with the specific interviewer itís either a faang interview or something you should walk out from, because python is not the language for algo fencing 9 to 5

PokeJoe
Aug 24, 2004

hail cgatan




to the big o not knowers, I used to be like you. i taught myself to program from books and recorded lectures and never really got it. i got sick of understanding how to solve problems but not how that silly notation worked.

just set aside some time and learn it. it's really not that hard. once it clicks you won't forget it because it's pretty basic to conceptualize

constant is obvious

n is a regular rear end for loop, grows as data grows

n² is a loop in a loop so it as data grows search time grows much more

log n, log, etc, just look at a graph. It's math

just Google "big o notation quizzes" I promise it won't take you more than a few hours to figure out, it's really not that complicated

KidDynamite
Feb 11, 2005



https://www.bigocheatsheet.com

that's also a good resource for big o stuff.

cinci zoo sniper
Mar 14, 2013



i think the problem is less so that the notation is difficult to understand - if you work in python, thereís no real impetus to know it. dictionaries are the only polished data structure in the core language, and everything else is going to be behind 10 abstraction layers, meaning that 90% of actionable algorithmic performance problems boil down to identifying that something you have is quadratic at best

Cybernetic Vermin
Apr 18, 2005



also hash tables is a kind of unfriendly case to start out with, since it involves assuming a good hash function exists (i.e. everything gets distributed randomishly), the amortization of resizing (so either a complicated distribution of the work or some ops sometimes being linear), a constant key size (i.e. the '1' here involves hashing the key you're indexing with, so if the key is large that should be counted), and arguably some potential bad constants (stuffing a cryptographic hash function into things gives you pretty certain randomness, but it'll be quite slow in practice).

hash tables are a bit abused even in theory, where people will slot a O(1) into their algorithm without commenting on the hash function, and in theory of course even a cryptographic hash can cause unbounded collisions in bad cases.

PIZZA.BAT
Nov 12, 2016

:cheers:



raminasi posted:

ask for the request in writing, either you have a small chance to get them in Actual Trouble or you get to see some funny floundering

PIZZA.BAT
Nov 12, 2016

:cheers:



of you need a good excuse say you use your inbox for reminders and your todo list. itís just so you donít forget ;)

bob dobbs is dead
Oct 8, 2017

I love peeps

Nap Ghost

the landau notation , which includes big o, was invented by mathematical analysist edmund landau to gently caress around w taylor series half a century before electronic computers were a gleam in turing and von neumanns mind

CarForumPoster
Jun 26, 2013
I have a high school diploma AND a hobby coin project

Now that you're sufficiently in awe, you motherfuckers shut up and let me tell you how human safety in your self driving car works in the REAL WORLD


hr at most companies is filled with enough stupidity and incompetence that they would actually ask for illegal poo poo in writing

even though preventing employees from suing is their job

don't send your pay stubs unless you already have an offer letter in writing from them.

hobbesmaster
Jan 28, 2008



Cybernetic Vermin posted:

also hash tables is a kind of unfriendly case to start out with, since it involves assuming a good hash function exists (i.e. everything gets distributed randomishly), the amortization of resizing (so either a complicated distribution of the work or some ops sometimes being linear), a constant key size (i.e. the '1' here involves hashing the key you're indexing with, so if the key is large that should be counted), and arguably some potential bad constants (stuffing a cryptographic hash function into things gives you pretty certain randomness, but it'll be quite slow in practice).

hash tables are a bit abused even in theory, where people will slot a O(1) into their algorithm without commenting on the hash function, and in theory of course even a cryptographic hash can cause unbounded collisions in bad cases.

ďamortizedĒ is probably the most abused word in computer science classes

itís like frictionless in first semester mechanics

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

i have never met anyone that cared that the time complexity of a disjoint set forest was ackshully O(n α(n)), it might as well be linear for all practical sizes. really what people are interested in when asking about big-o stuff is whether you actually understand how the algorithm you've written works beyond just "does it produce the right answer".

- is it doing something to each element that takes a constant amount of time? that's O(n)
- is it doing something to each element that takes a number of steps proportional to the depth of a tree? O(n log n)
- is it doing something to each element, that takes a number of steps proportional to the total number of elements? O(n^2)
- is it doing something for every possible combination of elements? O(2^n) (don't be here if you can help it)

silvergoose
Mar 18, 2006

IT IS SAID THE TEARS OF THE BWEENIX CAN HEAL ALL WOUNDS



is it theoretically able to run infinitely?

best joke my friends made in CS at school was shufflesort, the most important algorithm taught in CS 666. shuffle array. check to see if it's sorted. if it is, you're done! if it's not, repeat.

ultrafilter
Aug 23, 2007





In theory, shufflesort will terminate in finite time with probability one. In practice, you could be limited by sequences a PRNG can produce. Better use a hardware RNG.

zombienietzsche
Dec 9, 2003


silvergoose posted:

is it theoretically able to run infinitely?

best joke my friends made in CS at school was shufflesort, the most important algorithm taught in CS 666. shuffle array. check to see if it's sorted. if it is, you're done! if it's not, repeat.

you can optimize this to O(1) in quantumsort, which takes advantage of the "many worlds" interpretation of quantum mechanics. After shuffling, if the array is not sorted, destroy the universe (implementation left as an exercise for the reader). All remaining universes are ones in which the array was sorted successfully.

hobbesmaster
Jan 28, 2008



zombienietzsche posted:

you can optimize this to O(1) in quantumsort, which takes advantage of the "many worlds" interpretation of quantum mechanics. After shuffling, if the array is not sorted, destroy the universe (implementation left as an exercise for the reader). All remaining universes are ones in which the array was sorted successfully.

quantum bogosort and time loop logic were my favorite jokes in undergrad

(actual ďpaperĒ https://web.archive.org/web/20090129114503/http://www.frc.ri.cmu.edu/users/hpm/project.archive/general.articles/1991/TempComp.html )

Mr SuperAwesome
Apr 6, 2011

im from the bad post police, and i'm afraid i have bad news


i actually implemented sleepsort in production once to try and shard some horrible job that was taking ages (for other stupid reasons) based on UUID across a ~day interval

was quite happy with that one

(sadly didn't solve the problem in the end, because the rest of our stack sucked)

PIZZA.BAT
Nov 12, 2016

:cheers:



silvergoose posted:

is it theoretically able to run infinitely?

best joke my friends made in CS at school was shufflesort, the most important algorithm taught in CS 666. shuffle array. check to see if it's sorted. if it is, you're done! if it's not, repeat.

how to tell if your brain is busted enough to post in yospos:

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

you enjoy this video

ultrafilter
Aug 23, 2007





Real yosposters watch the extended version:
https://www.youtube.com/watch?v=xoR-1KwQh2k
Note: I am not a real yosposter.

PIZZA.BAT
Nov 12, 2016

:cheers:



i firmly believe this could be something you could show on sesame street and kids would be transfixed by it

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

Captain Foo
May 11, 2004

we vibin'
we slidin'
we breathin'
we dyin'


PIZZA.BAT posted:

i firmly believe this could be something you could show on sesame street and kids would be transfixed by it

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

havenít thought about this video, which kicks rear end, in a long time

tk
Dec 10, 2003



Nap Ghost

Cybernetic Vermin posted:

also hash tables is a kind of unfriendly case to start out with, since it involves assuming a good hash function exists (i.e. everything gets distributed randomishly), the amortization of resizing (so either a complicated distribution of the work or some ops sometimes being linear), a constant key size (i.e. the '1' here involves hashing the key you're indexing with, so if the key is large that should be counted), and arguably some potential bad constants (stuffing a cryptographic hash function into things gives you pretty certain randomness, but it'll be quite slow in practice).

hash tables are a bit abused even in theory, where people will slot a O(1) into their algorithm without commenting on the hash function, and in theory of course even a cryptographic hash can cause unbounded collisions in bad cases.

Early on in my career I learned that if you explain this to an interviewer who is just looking for O(1) as the answer that you wonít get the job.

Cybernetic Vermin
Apr 18, 2005



tk posted:

Early on in my career I learned that if you explain this to an interviewer who is just looking for O(1) as the answer that you won’t get the job.

otoh for the best-paying job i've gotten i got into a shouting match with the interviewer about some tree balancing detail. (i do not advice this approach)

tk
Dec 10, 2003



Nap Ghost

Iím pretty glad I didnít get that job because I didnít learn until much later that I donít want to work at a place that doesnít hire you for being right.

qhat
Jul 6, 2015




tk posted:

Early on in my career I learned that if you explain this to an interviewer who is just looking for O(1) as the answer that you wonít get the job.

what you should've learned is that you didn't want that job to begin with

edit:

tk posted:

Iím pretty glad I didnít get that job because I didnít learn until much later that I donít want to work at a place that doesnít hire you for being right.

lol yes this is right

Adbot
ADBOT LOVES YOU

JSON Bourne
Jun 1, 2004


PIZZA.BAT posted:

i firmly believe this could be something you could show on sesame street and kids would be transfixed by it

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

i watch it every time so i guess i am also transfixed by it

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply