[HN Gopher] Role of Algorithms
___________________________________________________________________
Role of Algorithms
Author : GlobalFrying
Score : 160 points
Date : 2023-10-07 08:31 UTC (1 days ago)
(HTM) web link (matklad.github.io)
(TXT) w3m dump (matklad.github.io)
| quirino wrote:
| I immersed myself in Competitive Programming this year and I'm
| very glad I did. I like it a lot for a couple of reasons:
|
| It is a very nice challenge/sport. The skill ceiling is high but
| there are many high quality resources online. The rating systems
| on competitive websites makes seeing your improvement very
| rewarding.
|
| It serves as an endless source of problem solving "ingenuity".
| Many problems have extremely elegant solutions. I find it
| especially satisfying to find subtle ideas/intuitions from one
| problem being applicable to another one.
| jhck wrote:
| I share that sentiment. I've been practicing Competitive
| Programming off-and-on for some years now. I still struggle a
| lot with it. But sometimes I manage to come up with a nice
| solution, and that makes it all worth it to me.
|
| When I make no progress at all, I take comfort in an anecdote I
| once read about the statistician Jimmie Savage [1]:
|
| "Jimmie had what he called 'a long-standing neurosis about
| Polya-Szego' (the most famous and long-lived problem book in
| analysis). Even when he was working on his first (and major)
| book in Paris, he was spending evenings on that neurosis.
| 'Polya-Szego humiliates me', he wrote. 'I never really know
| what's going on, but I can now work quite a few of the problems
| and seem to learn thereby some things of general interest.'"
| [2]
|
| [1] https://en.wikipedia.org/wiki/Leonard_Jimmie_Savage
|
| [2] Quote from Paul Halmos's _Automathography_
| aiunboxed wrote:
| Yes as a former competitive programmer I think there are a lot of
| benefits to learning algorithms
|
| - It makes you habitual to pushing bug free code as there is a
| penalty you give in every wrong submission.
|
| - You have to make sure that you get the submission done is
| shortest possible time, you learn to execute with speed.
|
| - You have great debugging skills
|
| - Edit (Edge cases as well)
| ahoka wrote:
| I don't doubt it is a very good skill to have, but have you
| found it making any bad habits? Like always having an external
| oracle you can rely on to tell your solution is correct or
| getting used to problems having a "right" solution?
| raincole wrote:
| This orcale exists for real world programming jobs. It's
| called <s>beta users</s> QA.
| aiunboxed wrote:
| Bad habits, not the one you mentioned but sometimes I feel
| that same time invested in software development might have
| yielded better results.
|
| In software development you also have test cases where your
| code should pass so you have in CP
| [deleted]
| GuB-42 wrote:
| I have done a bit of competitive programming, occasionally, but
| I have never been in a competition where there is a penalty for
| wrong submission.
|
| You obviously have to fix your bugs to validate the answer, and
| you obviously lose time when you didn't make it right the first
| time and have to debug your code, but when it comes to ranking,
| the only thing that mattered is the time it takes to get a
| right answer.
|
| But I agree that competitive programming can be a great
| exercise. Not just for the algorithm, but also for everything
| around the algorithm. For instance, you don't have time to
| waste parsing a list of integers. You have to get these parts
| right the first time almost without thinking, so that you can
| focus on the hard parts, like the algorithm. For example, if
| you are not confident that you parsed the input data correctly,
| you will lose time trying to figure out if you algorithm was
| wrong or if you fed it the wrong data.
| aiunboxed wrote:
| Top coder, codeforces, they have penalties for wrong
| submissions right ?
| baobabKoodaa wrote:
| Correct. In fact I'm having trouble thinking up a single
| counter example of an algorithm competition that doesn't
| give penalty for failed submissions.
| mynameismon wrote:
| The Informatics Olympiads?
| tylerhou wrote:
| USACO
| JohnKemeny wrote:
| While there often is no penalty for a wrong submission, the
| score you get for a _correct_ submission very often depends
| on the number of attempts you needed. E.g. ICPC, topcoder,
| ...
| jprete wrote:
| Isn't that the same as a penalty? Unless there's a big
| category of submissions that are neither right nor
| wrong....
| champagnepapi wrote:
| Any resources to get started with competitive programming? For
| someone who has years of SWE experience, but 0 with competitive
| programming.
| mrits wrote:
| The same as interviewing resources.
|
| this series is a good start:
|
| https://www.youtube.com/watch?v=DKCbsiDBN6c
| JohnKemeny wrote:
| Do Advent of Code! It's great fun. Invite your friends and
| colleagues to participate too, and make your own scoreboard.
| ratmice wrote:
| > Debugging complex code is hard, first simplify, then debug
|
| I've always made it a point to do a first pass just reading code
| and forming a hypothesis about the problem (which is often wildly
| wrong) before making any changes or even running it in a
| debugger.
|
| If nothing else you usually find other oddities, and get more
| familiar with the code as written. It isn't fast but it tends
| towards being beneficial for more than just solving the specific
| bug at hand.
| logdahl wrote:
| I have been wanting to get into competitive programming. I am
| quite an experienced programmer. Is leetcode still applicable, or
| are there other sites that are more suited?
| matklad wrote:
| https://cses.fi/problemset/ is _by far_ the best resource I
| know.
| jhck wrote:
| Worth mentioning that there's a companion book to this
| website: https://cses.fi/book/book.pdf
|
| The problems are indeed of very high quality. But it can be a
| difficult place to start. For example, even the very first
| problem has an overflow gotcha built into it. Also, Kadane's
| Algorithm appears as an early problem even though several
| mathematicians and computer scientists failed to discover it:
| https://en.wikipedia.org/wiki/Maximum_subarray_problem#Histo.
| ..
| baobabKoodaa wrote:
| The CSES book and problemset are amazing resources for
| learning.
| natrys wrote:
| Interesting that they have Assembly, but not C.
|
| In practice it seems most people just use C++ (87.5%). Add
| Python3 (7.5%) and Java (5%) and 99% of submissions are
| accounted for.
| sinkwool wrote:
| Great resource, but it's hard to practice there as a beginner
| because there are no solutions (unless you solve the problem
| yourself). So you might have to get comfortable with being
| stuck. Which is fine when you're experienced, but will
| demotivate you if you're just starting.
| jhck wrote:
| I think it's a fine place to start for the following reasons:
|
| * It has a large selection of problems with many good starter
| problems.
|
| * Once you've solved a problem, you can see how others have
| solved it (wish more sites had this feature).
|
| * You don't have to write I/O code, so you can just focus on
| the problem.
| sinkwool wrote:
| Leetcode is fine: lots of supported languages, large community,
| lots of solutions and editorials.
|
| Here are some more resources:
|
| - USACO: https://train.usaco.org/ and
| https://usaco.guide/general/
|
| - Codeforces: https://codeforces.com/ the de facto standard
| community for competitive programmers, regular contests with
| editorials, huge archive of problems
| (https://codeforces.com/problemset) with pretty accurate
| difficulty ratings so you can focus on problems of suitable
| difficulty if you want to progress quickly. They also have an
| incipient EDU section: https://codeforces.com/edu/courses that
| covers basic algorithms with practice problems.
| raunakchhatwal wrote:
| I definitely agree that it improves writing fewer bugs. When I
| first began using leetcode, I was proud that I was able to begin
| at leetcode medium and even solve the hard ones because the tip
| was to grind the easy ones before progressing to medium and hard
| problems. However, reading up on how DSA interviews are
| conducted, I realized that I probably would be penalized for not
| getting my solution right the first few times, whereas my style
| of solving leetcode problems at first was to get it right only
| after like the sixth+ try. Also, leetcode problems are also a
| good way to learn new languages, I'm currently using it to learn
| Rust, and learning Haskell probably would've been smoother if
| leetcode supported it.
| theusus wrote:
| IMO, Algorithms are overstated. It is just like going to the gym.
| Will make you healthy, but won't make you an athlete.
|
| What I found to be more useful is working abstractions, learning
| more about language theory, and etc.
|
| Algorithm is a branch of Computer Science and should be treated
| as such. It doesn't surpass or transcend it.
| layer8 wrote:
| Thinking in terms of proofs -- what the article mentions as
| properties and invariants -- is what's critical for writing
| correct code. This doesn't necessarily depend on DSA knowledge,
| but it sure helps in developing the understanding. Likewise,
| writing code that scales performantly relies on an
| understanding of asymptotic and amortized runtime, which DSA
| provides the practical examples of.
| angarg12 wrote:
| > Somewhat related, I noticed a surprising correlation between
| programming skills in the small, and programming skills in the
| large. You can solve a problem in five lines of code, or, if you
| try hard, in ten lines of code. If you consistently come up with
| concise solutions in the small, chances are large scale design
| will be simple as well.
|
| Well, my anecdotal evidence doesn't support this.
|
| I've done 500+ interviews for big tech, and often it is easy to
| spot people who have grinded leetcode. They excel at DSA, but
| fail at system design, or even low level design.
|
| The thing is that overall I kind of agree with this article.
| Leetcode is great as a fun coding exercise. I also think they
| help the craft like katas help martial artist to practice.
|
| The problem is when me getting the job depends on solving a
| coding puzzle. Sometimes I can solve a leetcode hard with ease
| and sometimes I get completely blocked in a medium one. Getting a
| job becomes more of a random toss than assessment of my skills.
| And yes, my company, and by extension me, are very guilty of
| this.
| tialaramex wrote:
| > The problem is when me getting the job depends on solving a
| coding puzzle.
|
| I have worked somewhere that we used online coding as part of
| our hiring process and it was valuable, but I agree that it's
| terrible as a gate. We used it because recruiters seemed to
| keep sending us people who can't write software, and it's just
| soul-destroying to sit down and interview people who are
| completely unable to do the job and had just sort of hoped we
| wouldn't check.
|
| My favourite interview though was somebody whose coding was
| excellent, and I spent the interview trying to figure out
| whether she's acting the way she is because she's terrified, or
| because she's incompetent. Turns out she was terrified, she's
| Russian and our interview was her first time using English, a
| language she'd learned in the classroom, in real life -- and
| she'd only been in the country for about one day.
|
| The reason I cared is, humans can't stay terrified for a
| prolonged period. No matter what's happening, even if it
| initially causes blind panic after not long they adjust to it.
| So if she was terrified that'll wear off after we hire her,
| which we did.
| matklad wrote:
| I think our observations are consistent: I would say that
| candidates ability to solve leetcode-style problem during an
| interview reveals very little of their ability to code in the
| small or in the large. "Algorithms during code interview" is a
| completely separate genre to what's discussed in the article.
|
| To give a positive example here: when someone sends a 1k lines
| PR implementing a new big feature, how well a body of a single
| function is implemented is often a good predictor of whether
| the whole PR makes sense.
| angarg12 wrote:
| I'm not sure our observations are consistent. What I'm saying
| is that I've seen many times people who crush the DSA
| problem, but struggle to define clean APIs, write clear,
| maintainable and extensible code, or just design systems. In
| fact in some cases leetcode makes this worse, with it's
| emphasis on very terse code (e.g. single letter variables,
| all code in a single method, hard to understand coding
| constructs...).
|
| About your second point, not to be a dick, but if someone on
| my team sent a 1k loc single PR for a big feature, I would
| sit down with them to have a conversation about why that is
| bad (I have indeed done this before).
| snakey wrote:
| > Getting a job becomes more of a random toss than assessment
| of my skills.
|
| I've coined a term for this throughout my long job search, it's
| called the "leetcode lottery" (patent pending).
|
| You can do a couple of hundred leetcode problems, but you're
| still at the mercy of the Gods when your technical interview
| comes around. The worst part of this whole charade is that I
| come out of most interviews having learned nothing valuable and
| I can say the same for the interviewer. They haven't learned
| about my strengths and weaknesses, etc.
|
| I don't have a better solution for how you can get an idea of
| my knowledge and skills over 2-3 hours of technical interviews
| though. And until someone does come up with a better idea,
| we're stuck playing this game.
| tayo42 wrote:
| You just skip the technical interview completely and start
| relying on some kind of certification for this
| pjmorris wrote:
| I think certification is essentially the same thing as
| having someone else interview the candidate, so it won't be
| better and is easier to game than interviews. Working
| together with someone on the kinds of problems you actually
| face is the most realistic way to assess a person's
| abilities on the work to be done because it's less of a
| proxy than anything else.
| andromeduck wrote:
| I've seen Stanford CS masters hard flunk leetcode-easy.
| mrits wrote:
| If I give you a choice of 5 mediums and you fail at all of them
| you probably are worth skipping for now.
| nonameiguess wrote:
| I believe you're seeing people trying to game the interview
| system who think grinding Leetcode is _all_ they need to do to
| become qualified as programmers. That isn 't what Matklad is
| saying as far as I can. To keep up the analogy to physical
| training, you're not going to master or even get good at any
| particular sport, other than competitive lifting, just by
| lifting, but it provides a basis that makes all of your more
| specific practice easier and more efficient.
| vsareto wrote:
| >They excel at DSA, but fail at system design, or even low
| level design.
|
| Leetcode was the gate for a while, then system design was added
| on to it.
|
| >Leetcode is great as a fun coding exercise. I also think they
| help the craft like katas help martial artist to practice.
|
| I know this is completely subjective, but it bothers me to
| solve toy problems that people have likely already solved (and
| now ChatGPT might be able to point you in a general direction
| given a plainly written problem description).
|
| And practicing it for a muscle reflex effect seems silly
| because you're unlikely to run into these again.
|
| However on the flip side, even business problems which are
| composed of things that people have solved before still seem
| novel, so I'm more engaged on those kinds.
| bryancoxwell wrote:
| > Do you know why we use i, j, k for loop indices? Because D ijk
| stra!
|
| Wait, really? I love that.
| lioeters wrote:
| My theory is that origially the variable name "i" meant
| "index", and then when someone needed one or two more temporary
| variables, they added "j" and "k".
|
| Oh, here's a more likely explanation:
|
| > i and j have typically been used as subscripts in quite a bit
| of math for quite some time (e.g., even in papers that predate
| higher-level languages, you frequently see things like "Xi,j",
| especially in things like a summation).
|
| > When they designed Fortran, they (apparently) decided to
| allow the same, so all variables starting with "I" through "N"
| default to integer, and all others to real (floating point).
|
| https://softwareengineering.stackexchange.com/questions/8690...
| tialaramex wrote:
| There's a recent stream where @tsoding decides to learn
| Fortran, and soon enough the instructions tell him to turn
| off Fortran's implicit types with "IMPLICIT NONE". And so of
| course as a contrary person and with experience of many
| modern languages with lovely type inference he doesn't want
| to and... yeah, there's a reason for IMPLICIT NONE. That's
| not inference @tsoding, it's complete madness.
| umanwizard wrote:
| Doubtful since i is also used as an index variable in
| mathematics.
| [deleted]
___________________________________________________________________
(page generated 2023-10-08 23:01 UTC)