3 ms·

> One answer I was expected to answer the complexity of my code to which the answer was something involving logarithms which I genuinely don't have a clue. Bei

by giobox 4y ago

> One answer I was expected to answer the complexity of my code to which the answer was something involving logarithms which I genuinely don't have a clue. Being asked the logarithmic time complexity of some code you just wrote is literally one of the most common interview questions in Software Engineering, no? I'm assuming at least this is what you are referring to. All the well known interview help books in the industry ("Cracking the Coding Interview" etc etc) and websites like Leetcode spend a lot of time teaching it for a reason! I've never had a software engineering interview where I wasn't asked to discuss something related to time complexity of a given bit of code, and given the regularity in which it will crop up its worth just spending the time to learn.

benbristow 4y ago
Yes, it was about the time complexity. I have a very primitive understanding of big-O notation from back in sixth form but I never did logarithms in maths (never did maths to a high enough level really). My fault for not dedicating a bunch of time to read loads of books to pass an interview and instead spending my time making a living at a full time software engineering job.
- eropple 4y ago
  The heuristic for this, FWIW, is to think about reducing the number of things you're messing with (such as a search set) by a factor (usually 2, not always) on every iteration. A binary search is a logarithmic algorithm because you chop off half of the (sorted) search set on every pass. That's all you really need to know about it to identify one (and thus realize you have a sublinear-time algorithm).
- giobox 4y ago
  You don't need to read a ton of books or know any math at all really - the basic answers they are typically looking for are patterns you can spot with no knowledge of logarithms what so ever. Spend a few days and you will just recognise, "oh hey I've a nested loop here, it's likely O(n2)!" That's really all it takes, and there are only 4-5 main classifications most interview code falls into, all of which can be spotted without knowing what a logarithm is. If I had interviewed you, I would not be impressed you hadn't understood this at such a basic level either, personally. The rest of us making a full time living at software engineering have to learn it to pass interviews at top companies too!
eropple 4y ago
I'm comfortable enough with time complexity, and I like to think I'll sniff out a logarithmic-class solution when I've written one, but I don't think I've ever had a problem with a candidate bucketing a problem into sublinear/linear/superlinear.

by giobox 4y ago

benbristow 4y ago

Yes, it was about the time complexity. I have a very primitive understanding of big-O notation from back in sixth form but I never did logarithms in maths (never did maths to a high enough level really). My fault for not dedicating a bunch of time to read loads of books to pass an interview and instead spending my time making a living at a full time software engineering job.

eropple 4y ago
The heuristic for this, FWIW, is to think about reducing the number of things you're messing with (such as a search set) by a factor (usually 2, not always) on every iteration. A binary search is a logarithmic algorithm because you chop off half of the (sorted) search set on every pass. That's all you really need to know about it to identify one (and thus realize you have a sublinear-time algorithm).
giobox 4y ago
You don't need to read a ton of books or know any math at all really - the basic answers they are typically looking for are patterns you can spot with no knowledge of logarithms what so ever. Spend a few days and you will just recognise, "oh hey I've a nested loop here, it's likely O(n2)!" That's really all it takes, and there are only 4-5 main classifications most interview code falls into, all of which can be spotted without knowing what a logarithm is. If I had interviewed you, I would not be impressed you hadn't understood this at such a basic level either, personally. The rest of us making a full time living at software engineering have to learn it to pass interviews at top companies too!

eropple 4y ago

I'm comfortable enough with time complexity, and I like to think I'll sniff out a logarithmic-class solution when I've written one, but I don't think I've ever had a problem with a candidate bucketing a problem into sublinear/linear/superlinear.