The way I did it, the heap always had k items, so it should be N log k. I vaguely recall a linear time solution I saw on LC. The basic idea is that if you have two numbers X and Y separated by less than k, nothing in the middle is relevant. So you can use a deque, iterate over the list, and at each step, pop everything in the deque that’s smaller than the current number off, then push the current number on. Then the left side of the deque should be the maximum from the current window, and you pop it off when it leaves the window. Possibly some details off there, but I think that was the general idea.
That’s clear and good, thanks.
I don’t think your heap can always have K items. To do so you have to remove something which is not the max element, which isn’t how heaps work.
Your python heap is exposed as a python list so you can remove, but that cost is linear, so total cost is N * K^2.
What am I missing?
The dequeue is good.
You can transpose the element to be removed with the last element of the list, then delete the last element. Now you have a rogue element in the middle of the list, but you can simply sift it up or down to fix the heap.
Update: I took the job. I’m officially a technology brother now!
Also, wtf is going on with comp? The offer was 50% more than I thought was the max realistic amount I’d be able to get. It’s bonkers.
6 Likes
Congratulations!
You’re still a newb until you’re bitter that your comp is too low.
5 Likes
Market’s wild right now. Congrats btw!
1 Like
I was looking for some examples of clean coding in Python and found results along these lines:
Some of the guidelines seemed a little extreme to me and counter to how the APIs of several widely used packages are designed. For example, one article recommends that functions should not have more than 3 arguments, and another recommends that functions shouldn’t have flags (e.g., a parameter that determines whether the output will be in miles or kilometers).
Is this type of stuff considered to be guiding principals that can be outweighed by other concerns in certain cases, or are clean coding practitioners sticklers about this sort of thing?
Generally once the function gets to 2-3 parameters-ish is when I decide to just pass an object that can grow to as many parameters as needed w/o upsetting the method signature. Otherwise you can wind up with annoying method calls like someFunction(“bob”, null, null, 1, null, 47).
But it’s not like this stuff set in concrete or anything. For something like too many method parameters, it’s almost better to just learn on your own why that can get annoying imo.
I’ve never heard the thing about flags. How do they recommend handling the miles/km case - two separate functions? That might be cleaner I guess depending on the context. That or convert the result after getting it from the function.
The miles vs. km wasn’t their example. They used converting to uppercase and lowercase instead, and they did recommend setting up different functions, which I think makes sense there.
I’m actually working on some code that calculates distances and will be used by others. I have simple mi_to_km and km_to_mi convenience functions as part of the package, so users could simply write something like km_to_mi(distance(x)) if they want the answer in miles. But I think writing distance(x, miles=False) is a little simpler from the user perspective, especially since the typical use case is miles in which case that argument doesn’t need to be supplied.
1 Like
Yeah I don’t think there’s any problem with distance(x, miles=False). I forget in python can you have missing parameters like Javascript? I like using them in cases like this.
So for the more common (correct American) case you’d have distance(x) and the (lame Euro) edge case would be distance(x, km=True).
Also I wasn’t thinking about named parameters when I gave the advice above. For most cases named parameters are as good as passing an object imo.
But ask yourself if the user might ever want meters or anything other than those two options. If so, don’t make it a boolean. It’s hard to clean up later when there’s a bunch of code out there and you realize your boolean is actually a multi-choice. That might be what they’re talking about with not using flags. I’ve gotten burned on that many many times.
- contain code with the same level of abstraction
- use descriptive names
These are useful. The others are meh. The book " Clean Code: A Handbook of Agile Software Craftsmanship" is strictly inferior to the guide of the previous generation “Code Complete”. “Uncle Bob” does not impress.
I do think the miles option is bad in your example. It’s not the end of the world, but consider:
- Do all of your functions (now and for the rest of time) have the same option? If not, it’s confusing. If so, you’re duplicating the same conversion code for no real reason.
- You need to put some thought into how to handle weird inputs. What should you do for
distance(x, miles=7.5)? Ordistance(x, True)? I would call both errors, but properly handling them is nontrivial and perhaps surprising to the user. - You might realize later (or perhaps right now!) that it’s better to provide this feature through some kind of context, as
with output_units(Units.MILES): distance(x). If v1 of the API uses a flag, you’re stuck with supporting that feature forever in addition to or instead of the new approach. - Each flag doubles the number of behaviors your function can have that you should be testing. It’s better for each function you provide to do exactly one, well tested thing and let the combinatoric explosion of behaviors occur on the user’s side (because each user is only assembling your tools in one way, so they can analyze and test their particular assemblage thoroughly and without a lot of burden).
Thanks for all the feedback. I may rework it so that the the units option isn’t a Boolean, which should make it easier to extend functionality if needed and simplify error handling.
You might find some inspiration from the way the decimal module in the standard library uses a context object. Unfortunately decimal is a C extension, so there’s no Python implementation to look at.
EDIT: Oooh, but the stdlib has this module to handle all the bookkeeping and thread safety stuff!
any advice for a “fun” java project
the next year of my life is gonna be completely java/spark and I have not programmed java (or OOP really for that matter) in 8 years at least, it’s becoming quite obvious and I need to practice.
i cant emphasize enough that it needs to be fun. I hate this language with every fucking fiber of my being.
2 Likes
i can’t imagine ever writing java again. i probably will but i can’t even imagine it right now. last time was 5+ years ago.
although just today i added a try/catch around a substring call. that brought back memories
I know the prospect of having to write Java is taking a toll on your mental health, but let’s not descend into frank delusion. There is no Santa Claus and there are no “fun” Java projects.
At least you’ll have me to commiserate with, and if you really haven’t written Java in 8 years then you are probably not familiar with JDK 8, which introduced the Streams API, plus various other enhancements since. The language is still horrible, but it’s not quite as soul-destroying as it used to be.
If you are going to have to write new stuff and not just update then you will have to catch up on some stuff. I use Streams API in virtually every function I ever write, java.time has made Date and everything associated with it obsolete, etc.
A brief list of stuff you need to know about:
- Streams API
- java.time
- record types
- switch expression + yield statement
- CompletableFuture, Java’s Promise implementation
- multiline strings, fucking finally
1 Like
Why can’t git just say resolve using the branch names - IE - “develop” or “stage” - rather than confusing as hell “mine” and “theirs” that mean different things with rebase vs. merge?
I always have to look it up, and then read it several times before I feel comfortable.
1-1 with boss today.
Me: Well I should be done with my only project (that I’ve been deliberately dragging out), and the new project isn’t starting for a while, so if you have anything.
Boss: Hmmm, well there’s this one PHP-wordpress-oauth thing that no one has time for right now (and sounds painful). No rush though.
“No rush though” is the worst thing to say to me. Just tell me you want it. I need to know my work is important and appreciated. Otherwise I struggle with motivation.
I hate it when things are slow.