|
i stumbled a lil' in an interview once when i got asked the big-o complexity of an algorithm and i said "constant" and he said "so the big-o is..." and i repeated "constant" because i just pronounce O(1) "constant" (and O(n) "linear" and O(n^2) "quadratic" etc.) and i didn't realize that he literally wanted me to say "one" to show i knew what he was talking about wrt "knowing big-o" i don't think anyone's claiming that you need to be able to write both bound proofs for a big-theta analysis on demand, you just gotta be comfortable with the common vocabulary for describing complexity
|
#
?
May 29, 2017 22:17
|
|
|
|
| # ? May 13, 2024 00:19 |
|
|
doing time+space complexity in an interview is an incredibly bad filter and waste of time unless you are hiring fresh grads with zero experience being able to reason about time+space complexity extremely good and useful thing to know
|
|
#
?
May 29, 2017 22:19
|
|
|
raminasi posted:big-theta analysis on demand This is the kind of "gotcha" question I assumed was being discussed, but in any case I don't pick good employers and I'm not sure anyone else but me would have any clue what O(n^2) meant where I'm at now given that the other CS degree holder left. I need to leave.
|
|
#
?
May 29, 2017 22:25
|
|
|
VOTE YES ON 69 posted:doing time+space complexity in an interview is an incredibly bad filter and waste of time unless you are hiring fresh grads with zero experience counterpoint: I literally had people that tried to do Fibonacci in a tree recursive fashion without seeing the problem on an interview
|
|
#
?
May 29, 2017 22:26
|
|
|
raminasi posted:
this. im not super math oriented and i don't think theta and omega end up being that useful outside of the sort of academic cs research poo poo where you come up with more and more low complexity algorithms for things that will never be implemented outside the paper they are described in. but being able to say "bubble sort is o(n^2) but is easy to do in place but merge sort is o(n log n) and can be done in place with slightly more complex code" is useful for deciding tradeoffs between algorithms, even if that particular example is vacuous.
|
|
#
?
May 29, 2017 22:27
|
|
|
The Management posted:counterpoint: I literally had people that tried to do Fibonacci in a tree recursive fashion without seeing the problem on an interview i need to know more to decide if that was bad. if it was just "print the numbers in order" then am iterative calc-and-forget approach is better if it was "and make it efficient to call multiple times" then iterating and storing each step in an array is better but at least there if you're using recursion you're not creating as much unnecessary overhead as when you don't need to hold onto the data for later. or am i overthinking it already? i tend to do that.
|
|
#
?
May 29, 2017 22:31
|
|
|
cis autodrag posted:i need to know more to decide if that was bad. if it was just "print the numbers in order" then am iterative calc-and-forget approach is better fibonacci was the classic example of "the simple recursive algorithm is extremely inefficient O(2^n), much more than the iterative algorithm" when i took those courses. if you aren't memoizing in some way, it's just terrible, and it's not a bad test to someone to mention that, at least with some hinting. carry on then fucked around with this message at 22:36 on May 29, 2017 |
|
#
?
May 29, 2017 22:32
|
|
|
cis autodrag posted:like, explain to me why bubble sort is slower than merge sort in one sentence. big O notation can do it extremely succinctly in a way every programmer will recognize. your sentence is likely to be wandering and confusing. don't forget that i was a technical writer before i ever wrote a line of code. having a useful, compact, expressive, and universally understood notation for a difficult concept is extremely ftw. more than a sentence but bubble sort puts the biggest unsorted element into its correct place on each run, and each run has to look at up to the entire array. merge sort also has to look at the entire array several times, but it only has to do it for however many times you can break the the whole array in half. that number grows much slower than the size of the array, so merge sort can be much faster.
|
|
#
?
May 29, 2017 22:34
|
|
|
carry on then posted:fibonacci was the classic example of "the simple recursive algorithm is extremely inefficient O(2^n), much more than the iterative algorithm" when i took those courses. if you aren't memoizing in some way, it's just terrible. O(n2^n) addition on unbounded numbers isn't constant time friend
|
|
#
?
May 29, 2017 22:37
|
|
|
carry on then posted:fibonacci was the classic example of "the simple recursive algorithm is extremely inefficient O(2^n), much more than the iterative algorithm" when i took those courses. if you aren't memoizing in some way, it's just terrible, and it's not a bad test to someone to mention that, at least with some hinting. i mean you can define the recurrence in a way that passes the last two calculated values through and that's efficient enough if you only need to call it once and just need to print the sequence. but ya iterating will get you that for free and without adding a bunch of stack frames for no reason. like i said i tend to over think things 
|
|
#
?
May 29, 2017 22:39
|
|
|
FamDav posted:O(n2^n) carry on then fucked around with this message at 22:44 on May 29, 2017 |
|
#
?
May 29, 2017 22:39
|
|
|
usually big O is defined against a single thing, be that length of the input, bits in the operands (such as with karatsuba multiplication), number of records, or some other thing. trying to conflate two things into the same analysis is silly.
|
|
#
?
May 29, 2017 22:41
|
|
|
cis autodrag posted:usually big O is defined against a single thing, be that length of the input, bits in the operands (such as with karatsuba multiplication), number of records, or some other thing. trying to conflate two things into the same analysis is silly. yeah, and the time complexity of addition for fibonacci numbers grows linearly for N when we're talking about calculating the Nth fibonacci number (N+2th is more than double the Nth fibonacci number)
|
|
#
?
May 29, 2017 22:47
|
|
|
trap sprung itt
|
|
#
?
May 29, 2017 22:49
|
|
|
FamDav posted:yeah, and the time complexity of addition for fibonacci numbers grows linearly for N when we're talking about calculating the Nth fibonacci number (N+2th is more than double the Nth fibonacci number) sure, but in the analysis you were responding to addition is being treated as a constant factor because that's generally how big o works. otherwise you're trying to measure two things at once which isn't useful especially since you can't change the algorithm to make large numbers smaller. you can't do anything about the addition so you treat it as insignificant.
|
|
#
?
May 29, 2017 22:50
|
|
|
VOTE YES ON 69 posted:trap sprung itt ya ur right ill stop now.
|
|
#
?
May 29, 2017 22:50
|
|
|
Better brush up on your ML before that next hardware store interview I guessquote:while we increased fulfillment levels from our stores, our overall fulfillment costs remain nearly constant as a percent of digital sales….by using machine learning to improve the algorithms that determine how to optimally fill orders with our network of stores and EFCs” – Kohl’s Corp CEO Kevin Mansell
|
|
#
?
May 29, 2017 22:52
|
|
|
Pryor on Fire posted:Better brush up on your ML before that next hardware store interview I guess my wife works in sales and she was telling me how stores like Lowe's and home Depot have been trying to use algorithms to do their inventory and the result is they they're massively overstocked on some poo poo and constantly out of others because trying to figure out how many of x object you can fit into y stores is basically a flavor of the backpack problem.
|
|
#
?
May 29, 2017 22:56
|
|
|
VOTE YES ON 69 posted:trap sprung itt many bad programmers were trapped
|
|
#
?
May 29, 2017 22:58
|
|
|
cis autodrag posted:sure, but in the analysis you were responding to addition is being treated as a constant factor because that's generally how big o works. otherwise you're trying to measure two things at once which isn't useful especially since you can't change the algorithm to make large numbers smaller. you can't do anything about the addition so you treat it as insignificant. big-o doesn't imply that addition is constant time, thats just the model of computation you happen to be using when calculating it. when its relevant you should consider the cost of the operations, because for example there is an O(n) solution and a O(log n), but the latter requires multiplication
|
|
#
?
May 29, 2017 22:58
|
|
|
FamDav posted:big-o doesn't imply that addition is constant time, thats just the model of computation you happen to be using when calculating it. when its relevant you should consider the cost of the operations, because for example there is an O(n) solution and a O(log n), but the latter requires multiplication i can't find a single piece of literature which provides O(n2^n) as the answer for "what is the bigO of recursive fibonacci". source?
|
|
#
?
May 29, 2017 23:03
|
|
|
carry on then posted:i can't find a single piece of literature which provides O(n2^n) as the answer for "what is the bigO of recursive fibonacci". source? he's depending on the fact that adding very large numbers larger than the processor's native addition requires an additional algorithm with its own complexity.
|
|
#
?
May 29, 2017 23:05
|
|
|
cis autodrag posted:he's depending on the fact that adding very large numbers larger than the processor's native addition requires an additional algorithm with its own complexity. ya i'm looking for a source that lays out why its imperative we consider that for this, because as far as i can tell, the bigO of recrusive fibonacci is said to be O(2^n) in the general case. i'm really just curious.
|
|
#
?
May 29, 2017 23:07
|
|
|
also everything that touches memory has an extra O(sqrt(n)) on it but basically nobody acknowledges this and i only just recently saw a compelling proof of it
|
|
#
?
May 29, 2017 23:10
|
|
|
lol if you think computer science has anything to do with computer hardware
|
|
#
?
May 29, 2017 23:17
|
|
|
hobbesmaster posted:lol if you think computer science has anything to do with computer hardware it totally doesnt. in my algos class i read a paper where they published the first o(n) median-finding algorithm but when you read it its o(n) because they don't mention the constant factor of like 828748383.45 on the front. cs algorithm research at this point is more about researchwank algorithms that vacuously improve asymptotic analysis while being completely impractical for something other than pseudocode on paper.
|
|
#
?
May 29, 2017 23:23
|
|
|
back to bitching about this recruiter, when i talked to him on thursday he's like "ill email you the health benefits information tomorrow and put your offer in the mail". never got an email. im not getting that fuckin offer letter for like a month i bet. this dude has made the whole process way more nerve wracking than necessary and if anyone asks me about him im going to spill so much tea.
|
|
#
?
May 29, 2017 23:37
|
|
|
cis autodrag posted:back to bitching about this recruiter, when i talked to him on thursday he's like "ill email you the health benefits information tomorrow and put your offer in the mail". never got an email. im not getting that fuckin offer letter for like a month i bet. this dude has made the whole process way more nerve wracking than necessary and if anyone asks me about him im going to spill so much tea. It's combination of them being a little bit slow probably due to their workload, and you being very stressed about it. Chill, figgies will come
|
|
#
?
May 29, 2017 23:44
|
|
|
hobbesmaster posted:lol if you think computer science has anything to do with computer hardware that's way data-oriented design is good also anyone who suggests that a linked-list is the correct answer to a problem is wrong 99% of the time
|
|
#
?
May 30, 2017 00:03
|
|
|
Y'all mother fuckers misusing n is driving me up a wall. If you're going to put multiple things into one complexity at least have the good sense to use different variables
|
|
#
?
May 30, 2017 00:07
|
|
|
The_Franz posted:that's way data-oriented design is good you mean infinity cache misses for easy insertions isn't a good tradeoff?
|
|
#
?
May 30, 2017 00:12
|
|
|
apseudonym posted:Y'all mother fuckers misusing n is driving me up a wall. standard CS complexity analysis usually assumes all operations take the same amount of time but if you have two inputs then yes you should be using m as well. like, n*m operations to hit everything in a matrix or whatever
|
|
#
?
May 30, 2017 00:25
|
|
|
cis autodrag posted:back to bitching about this recruiter, when i talked to him on thursday he's like "ill email you the health benefits information tomorrow and put your offer in the mail". never got an email. im not getting that fuckin offer letter for like a month i bet. this dude has made the whole process way more nerve wracking than necessary and if anyone asks me about him im going to spill so much tea. i had to hound my recruiter for like a month between verbal offer and e-sign on the dotted line complications included: having to redo my resume and reapply for the position because my paper resume didn't match the online submission exactly having to apply to another position because their job offer software would not let them make me an offer at the agreed upon figgies for the req ID i first applied for
|
|
#
?
May 30, 2017 00:27
|
|
|
cis autodrag posted:you mean infinity cache misses for easy insertions isn't a good tradeoff? there are no cache misses in theoreticalville also the hookers and booze are free
|
|
#
?
May 30, 2017 00:30
|
|
|
apseudonym posted:Y'all mother fuckers misusing n is driving me up a wall. addition on arbitrarily sized binary values is O(b) where b is the number of bits in the number. b is O(n) for the nth fibonacci number, so adding the n-1th and n-2th fibonacci numbers together is going to be O(n) nth fibonacci is kind of interesting because the complexity of arithmetic operations has to scale with n cis autodrag posted:back to bitching about this recruiter, when i talked to him on thursday he's like "ill email you the health benefits information tomorrow and put your offer in the mail". never got an email. im not getting that fuckin offer letter for like a month i bet. this dude has made the whole process way more nerve wracking than necessary and if anyone asks me about him im going to spill so much tea. its memorial day weekend chill out
|
|
#
?
May 30, 2017 00:31
|
|
|
The_Franz posted:also the hookers and booze are free the perfectly spherical part is kinda awkward though
|
|
#
?
May 30, 2017 00:32
|
|
|
dragon enthusiast posted:i had to hound my recruiter for like a month between verbal offer and e-sign on the dotted line i did this with Epic but instead of sending me the offer they told me to get lost
|
|
#
?
May 30, 2017 00:32
|
|
|
Shaman Linavi posted:i did this with Epic but instead of sending me the offer they told me to get lost bullet dodged ?
|
|
#
?
May 30, 2017 00:34
|
|
|
FamDav posted:
id be more chill if he hadn't gone mia after emailing to ask if i could phone call that day 3 times in the last couple weeks.
|
|
#
?
May 30, 2017 00:35
|
|
|
|
| # ? May 13, 2024 00:19 |
|
|
jre posted:bullet dodged ? confirmed. unless it was the games company i guess?
|
|
#
?
May 30, 2017 00:36
|
|