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

41–50 of 100 posts

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

#41

Post by dpzmick »

MichaelBurge wrote: post #7

def print_first_item(items): print items[0] This function runs in O(1) time (or "constant time") relative to its input. If this were C where the only types are fixed-size, that might be true. But in Python it seems like items[0] could display as 10 gigabytes of JSON. And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally. Also, since Python has arbitrarily large integer…

in C, it items[0] could segfault, the fault could be caught by a signal handler which does some unbounded amount of work, then populates the appropriate memory location and returns...

More realistically, the page of memory that items[0] is sitting on could be swapped to disk, requiring the OS to do some big operation.

trying to write a piece of code with the big-O you are looking for generally has a huge number of caveats. I'm undecided on whether this is a feature (abstraction) or a flaw (easily misleading)

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

#42

Post by Sirenos »

ma2rten wrote: post #40
abalone wrote: post #13

I've noticed there are SO many of these "coding interview prep" courses lately. Like, obviously it's a hot job market, but there's just so many and of a certain vibe that it seems like some are selling a dream. There's a common narrative too, that it's all about algorithm question prep and it's a "game" you can win. One youtuber who recently landed a ~$275K TC gig said it's not about being "intelligent" it's about pr…

I work at Google. I think it's half true. I would not have passed the Google interview if I had not prepared. After 3 years, I have completely forgotten most of the prep. I couldn't even implement a binary search right now. That said, I do have an innate ability for problem solving. I know another person, who has prepared significantly more than me (multiple months full-time) but still wasn't able to get an on-site i…

I get the sentiment but come on. I seriously doubt you cannot even implement a binary search right now.

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

#43

Post by JudgeWapner »

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.

More generally, why do we have such a fetish for acronyms in general? Is it some kind of insider feeling to know a "code" for a thing?

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

#44

Post by JudgeWapner »

hello_moto wrote: post #38
abalone wrote: post #21

Earlier quoted context omitted.

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…

> 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 agree with you on this. They do have taken this to the extreme because the questions are getting harder and harder. This is hard tbh because if you're an employer whom used to be able to filter candidates…

>what will you do?

You'll do the same thing most other professional industries do. List the requirements for the job: x to y years experience with technologies a,b and c. Grab a handful of the most polished resumes, interview them for personality, and hire the one you liked best.

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

#45

Post by hello_moto »

JudgeWapner wrote: post #44
hello_moto wrote: post #38

Earlier quoted context omitted.

> 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 agree with you on this. They do have taken this to the extreme because the questions are getting harder and harder. This is hard tbh because if you're an employer whom used to be able to filter candidates…

>what will you do? You'll do the same thing most other professional industries do. List the requirements for the job: x to y years experience with technologies a,b and c. Grab a handful of the most polished resumes, interview them for personality, and hire the one you liked best.

Previous method works well,why change it?

Silicon Valley thrive in tricky algo questions. That's how they hired engineers since long time ago.

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

#46

Post by weq »

abalone wrote: post #13

I've noticed there are SO many of these "coding interview prep" courses lately. Like, obviously it's a hot job market, but there's just so many and of a certain vibe that it seems like some are selling a dream. There's a common narrative too, that it's all about algorithm question prep and it's a "game" you can win. One youtuber who recently landed a ~$275K TC gig said it's not about being "intelligent" it's about pr…

I have found pair-programming with a dev on a current problem you have in your codebase to be the best litmus test.

If u want to give "quiz" interviews, u will get employee's good doing them. Like those CS grads in my class who copied eachothers take-home assignments yet still passed because they were good at memoizing.

Furthermore, this is the first training session for your future employee - you are inducting them into your companies culture. If "answering meaningless questions for the sake of it, is what you want to portray to them. So be it." They have been warned!

Selecting for a certain subset of people, is a business decision. Be aware of what interview practices mean in the context of how that company operates. If the job add has a sticker list of tech-hype, a promise of re-dev'ing a monolith into k8 microservices, with a leetcode interview, you already know alot about that company!

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

#47

Post by Const-me »

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.

If you need precision good enough for practical applications, it’s very hard to do. All modern CPUs are pipelined, time they spent on every instruction depends on neighbor instructions + data dependencies between them. All modern CPUs have multi-level caches, static analyzers must also simulate what data is in which levels of caches; for many practical problems RAM access dominates computations and L1 cache is ~2 orders of magnitude faster than main RAM. All modern CPUs have very sophisticated power management, they scale frequency based on temperature, they selectively turn on/off their blocks, this too affects time. All modern CPUs have multiple cores, L3 cache is often shared across them, all caches suffer heavy penalty when a line is shared across cores. And so on.

People don’t do it not only because it’s hard, also because running the function and measuring time + memory is much easier, also much more precise.

Even if you don’t care about time and memory complexity and only care about these useless O(N), it’s still very hard because complexity depends on input data. E.g. bubble sort is O(N^2) but it can also be O(N) if the data is mostly sorted already and only a single element needs to be moved.

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

#48

Post by trabant00 »

mancerayder wrote: post #24
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…

As a DevOps guy who's been screened out of companies that care about such things, I'm a mix of horrified and skeptical. I'm horrified because I'm seeing some gross incompetence in the realm of organization in thinking, clean infrastructure and security awareness. And some of this punishes the old(er). I'm skeptical because I think many of these interviewers are themselves lousy systems people, are building environmen…

Having the same experience and background as you I took a different perspective: I use that system of interview to filter the companies _I_ don't want to work for.

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

#49

Post by xenihn »

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.

Do Uber and Microsoft pay as much as Facebook/Apple/Google/Netflix/Amazon? The acronym exists for a reason. I think Amazon only makes the list because of how well their stock performs, but it still deserves to be on there because of that.

The only large company I can think of that matches or even exceeds the offers those companies give out is (surprisingly) Snap. If we go smaller, Airbnb and Pinterest are up there too, but they don't have nearly as many employees or open positions.

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

#50

Post by mgradowski »

MichaelBurge wrote: post #7

def print_first_item(items): print items[0] This function runs in O(1) time (or "constant time") relative to its input. If this were C where the only types are fixed-size, that might be true. But in Python it seems like items[0] could display as 10 gigabytes of JSON. And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally. Also, since Python has arbitrarily large integer…

Similarly, if you were to write a O(n) Python program displaying the Fibbonacci sequence, it would not run in O(n) time but it would still take O(n) operations. It only makes sense to treat time complexity literally, if operations take fixed amount of time (int addition in Python doesn't).
Post reply on HN