Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big O Notation – Using not-boring math to measure code’s efficiency

interviewcake.com

Post reply on HN
Print view View original

81–90 of 100 posts

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#81

Post by namelosw »

abalone wrote: post #21
save_ferris wrote: post #15

Earlier quoted context omitted.

A major force driving this is the employers who choose to conduct interviews in this way. I'm a developer with about 6 years experience in full stack web app development (Rails & Django mostly), and I recently got my ass absolutely kicked during a couple of live coding challenges that were very heavy on theory (also worth mentioning that I'm a self-taught dev without a CS degree). I started talking to some former cow…

To be clear I think it’s good to test CS fundamentals even if you don’t use them every day. It’s a good screen for aptitude. I’m just concerned that taken to the extreme it mistakes excessive pattern recognition prep for true comprehension and aptitude. Especially if it’s “whoever puts the optimal solution on the board fastest wins.” I do think it would do you some good to read up on core CS and algorithms though. I…

But CS is not only about algorithms and data structures. Even schools are missing the point mostly. Things like general PLT and formal methods, namely how to deal with abstractions in a large project, and how to know if your program is correct, are mostly ignored because they're not favored by the market.

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#82

Post by Jaxan »

concert-gilled wrote: post #77
falcor84 wrote: post #74

> As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect. I was annoyed to see that comment about division, as of course dividing n by 2 has exactly the same effect regardless of the size of n. This is not the reason we ignore multiplicative constants in complexity analysis. It reminded me of the joke that Earth's circumference is pretty much the same as its diameter, since the the si…

> This is not the reason we ignore multiplicative constants in complexity analysis. What is the reason?

One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem . (At least theoretically, for runtimes bigger than linear.)

Another answer could be Moore's law: machines do get faster over time. (And also memory gets cheaper.) And so we wish to define efficiency (time or space) in a way which does not depend on the current technological state.

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#83

Post by gsich »

spraak wrote: post #31
dntrkv wrote: post #18

Earlier quoted context omitted.

It depends on the company, but most of the FAANG company (and others that try to imitate them) interviews come down to how quickly you can get the optimal solution on the board. It has very little to do with how well you can code day to day. Most interviews have 4 sessions broken up in the following manner: 1 hour: coding 1 hour: coding 1 hour: lunch 1 hour: system design 1 hour: cross-functional In my experience tho…

I wish the usage of FAANG would die. Firstly it exlcudes obvious others like Uber, Microsoft, etc. Secondly, and purely aesthetically, it sounds silly. I hereby propose we call such companies the Big N, and I'm definitely open to other ideas.

Why Netflix?

Gmafia

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#84

Post by kgilpin »

It's true that most engineers are not going to implement a binary search algorithm or an optimizing compiler during the course of their employment in a typical year.

However, CS fundamentals are the language of software engineering. It's important for engineers to be able to communicate efficiently about things like runtime analysis, indexes, concurrency models, type systems, etc.

Your mechanic knows how a carburetor works, (s)he knows how brakes work. Mechanics have a common set of fundamentals that they all know and share, and can use to communicate with each other about their work. The purpose of this knowledge is not to be able to fabricate new car parts, although given time and the right equipment, it could probably be done.

The purpose of CS fundamentals is not to so much to implement complex algorithms, as to understand how to use tools and libraries that are based on them.

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#85

Post by dooglius »

Jaxan wrote: post #82
concert-gilled wrote: post #77

Earlier quoted context omitted.

> This is not the reason we ignore multiplicative constants in complexity analysis. What is the reason?

One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem . (At least theoretically, for runtimes bigger than linear.) Another answer could be Moore's law: machines do get faster over time. (And also memory gets cheaper.) And so we wish to define efficiency (time or space) in a way which does not depend on the current technological state.

That theorem just indicates that Turing Machines with an unbounded/arbitrary number of symbols is a poor model; the approach there will not work on any actual machine. If you take out a factor of 2 in an algorithm, that's going to asymptotically double the state regardless of what actual machine you're on, so I don't buy machine-independence as a reasonable excuse. The actual reason constants are ignored is because it makes the math a lot simpler when you ignore them.

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#86

Post by rand_r »

concert-gilled wrote: post #77
falcor84 wrote: post #74

> As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect. I was annoyed to see that comment about division, as of course dividing n by 2 has exactly the same effect regardless of the size of n. This is not the reason we ignore multiplicative constants in complexity analysis. It reminded me of the joke that Earth's circumference is pretty much the same as its diameter, since the the si…

> This is not the reason we ignore multiplicative constants in complexity analysis. What is the reason?

One part is that Big-O is an upper bound that kicks in for sufficiently large n.

For example, a O(log(n)) function will be faster than a O(k * n) function, for any fixed k, when n>j (for some fixed j i.e. when n is large enough). When comparing major classes of functions (n, log(n), 2^n, etc,), constant multiples don't matter, mathematically.

The other reason is that when comparing two functions with a similar amount of constant steps, let's say 5n vs 2n, it's impossible to say which is faster in the real world, so it's simpler and just as useful to collapse the set of O(k * f(n)) functions into O(f(n)).

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#87

Post by sireat »

Am I the only one who signed up for interviewcake on a whim (similar to those January fitness club resolutions)?

Then I sort of had an epiphany. When will I need this? (or rather "I am too old for this...") I must be the perfect customer for interview cake: paid but do not use it.

I make my own work and those kind of problems just do not come up.

I mean CLRS was fun a long time ago, but it seems to degenerate into skeet shooting pretty quickly:

“Shooting skeet eight hours a month was excellent training for them. It trained them to shoot skeet.”

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#88

Post by blattimwind »

bauerd wrote: post #61
iandanforth wrote: post #58

Question: At what point in a career do you expect someone to have gone from "I know Big O" to "I know how this data structure is laid out in memory on this OS?" My experience says really good engineers know the latter, but I'd like to hear if this holds for others.

How data structures are laid out in memory has nothing to do with the operating system

OS typically dictates ABI, ABI dictates memory layout of structures, among other things.

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#89

Post by adrianN »

smudgymcscmudge wrote: post #2

I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.

Yes it's difficult, but people try anyway. The term to Google for is WCET analysis:

https://en.wikipedia.org/wiki/Worst-case_execution_time#Auto...

Re: Big O Notation – Using not-boring math to measure code’s efficiency

#90

Post by ggambetta »

throwaway2016a wrote: post #76
ggambetta wrote: post #75

Earlier quoted context omitted.

> most of those interviews just test your knowledge of how quickly you can figure out the right data structure and algo for the question at hand Not sure that's true. Just a few days ago someone was commenting here how they were a frontend developer with a few years of experience, yet they didn't know what a for loop was. These interviews aren't about how quickly you can figure out the right data structure, they're a…

A simple fizz buzz will solve for that. No need to put in algorithm questions.

FizzBuzz establishes a minimum baseline, but you need more than the ability to write FizzBuzz to be able to work at a FAANG.
Post reply on HN