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

To be a better programmer, write little proofs in your head

the-nerve-blog.ghost.io

Post reply on HN
Print view View original

151–160 of 181 posts

Re: To be a better programmer, write little proofs in your head

#151

Post by andyjohnson0 »

mdnahas wrote: post #144
hiAndrewQuinn wrote: post #2

Oh, I have a relevant and surprisingly simple example: Binary search. Binary search and its variants leftmost and rightmost binary search are surprisingly hard to code correctly if you don't think about the problem in terms of loop invariants. I outlined the loop invariant approach in [1] with some example Python code that was about as clear and close to plain English at I could get. Jon Bentley, the writer of Progra…

I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. Most failures went into an infinite loop on simple cases! The ones who could write it usually did so quickly. I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to…

> I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes.

I'd be interested to know why you feel that this is a useful interview question.

Implementing a well-known and widely implemented algorithm under stressful interview conditions wouldn't seem to me to demonstrate much about a candidate. In that situation I'd much rather be given a printout of some code and asked to talk around the implementation - how the code maps to the abstract algorithm, implementation trade-offs, readability, etc.

Re: To be a better programmer, write little proofs in your head

#152

Post by naniwaduni »

hiAndrewQuinn wrote: post #138
godelski wrote: post #137

Earlier quoted context omitted.

This makes for an interesting test. I checked Claude Sonnet, just for the he'll of it Prompt: Please write a bug free binary search in python Answer: def binary_search(arr, target): """ Performs binary search on a sorted array. Args: arr: A sorted list of comparable elements target: The element to search for Returns: The index of target if found, -1 otherwise """ left = 0 right = len(arr) - 1 while left # Example usa…

Very good! Looks good to me. One small callout: mid = left + (right - left) // 2 This implementation detail is to my knowledge unnecessary in Python because Python's built-in int type has arbitrary-precision integers. It's intended to avoid buffer overflows in languages like C. Imagine, say, that left is 1 and right is 2^63 - 1. In Python left + right will just give you 2^63, no big deal. In C, left + right will over…

Even in languages like C, it's mostly voodoo in practice unless you're using undersized indices anyway—you surely don't have anywhere near SIZE_MAX/2 elements.

The underlying problem is sloppy use of int for indices. The roundabout calculation will still overflow at twice the size.

Re: To be a better programmer, write little proofs in your head

#153

Post by Etheryte »

mdnahas wrote: post #144
hiAndrewQuinn wrote: post #2

Oh, I have a relevant and surprisingly simple example: Binary search. Binary search and its variants leftmost and rightmost binary search are surprisingly hard to code correctly if you don't think about the problem in terms of loop invariants. I outlined the loop invariant approach in [1] with some example Python code that was about as clear and close to plain English at I could get. Jon Bentley, the writer of Progra…

I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. Most failures went into an infinite loop on simple cases! The ones who could write it usually did so quickly. I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to…

Based on your description, it sounds like a bad interview question. When otherwise capable candidates can't answer your trivia, maybe it isn't a useful signal? More than anything, it just sounds like you're selecting for people who practiced leetcode vs those who didn't.

Re: To be a better programmer, write little proofs in your head

#154

Post by mettamage »

andyjohnson0 wrote: post #151
mdnahas wrote: post #144

Earlier quoted context omitted.

I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. Most failures went into an infinite loop on simple cases! The ones who could write it usually did so quickly. I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to…

> I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. I'd be interested to know why you feel that this is a useful interview question. Implementing a well-known and widely implemented algorithm under stressful interview conditions wouldn't seem to me to demonstrate much about…

It showcases they have done some leetcode. Or it showcases they can write code when someone is looking over your shoulder. There are company cultures where these skills are needed.

Companies that don't fall into a culture like this are indeed deluded.

I would do the following:

1. Write a tax calculator that reads in data from a CSV, or a similar question to showcase programming ability.

2. Do a small paid project. If it was good enough, hire them. If it wasn't, then give feedback and do another one in a week, tell them to learn as much about the topic as possible.

3. Do a small paid project a week later. If their learning agility is high, then hire them still.

Re: To be a better programmer, write little proofs in your head

#155

Post by zozbot234 »

Etheryte wrote: post #153
mdnahas wrote: post #144

Earlier quoted context omitted.

I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. Most failures went into an infinite loop on simple cases! The ones who could write it usually did so quickly. I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to…

Based on your description, it sounds like a bad interview question. When otherwise capable candidates can't answer your trivia, maybe it isn't a useful signal? More than anything, it just sounds like you're selecting for people who practiced leetcode vs those who didn't.

It's not whether you can solve it right away, it's how you approach the problem solving process to reach a viable solution. If "try to prove that this code is actually correct" is part of that process, that's the kind of "trivia" that can really be widely applicable even in a working environment, in a way that random leetcode algos often aren't.

I vote for making "how would you think about proving this correct?" a question in all algo-focused interviews.

Re: To be a better programmer, write little proofs in your head

#156

Post by namibj »

naniwaduni wrote: post #152
hiAndrewQuinn wrote: post #138

Earlier quoted context omitted.

Very good! Looks good to me. One small callout: mid = left + (right - left) // 2 This implementation detail is to my knowledge unnecessary in Python because Python's built-in int type has arbitrary-precision integers. It's intended to avoid buffer overflows in languages like C. Imagine, say, that left is 1 and right is 2^63 - 1. In Python left + right will just give you 2^63, no big deal. In C, left + right will over…

Even in languages like C, it's mostly voodoo in practice unless you're using undersized indices anyway—you surely don't have anywhere near SIZE_MAX/2 elements. The underlying problem is sloppy use of int for indices. The roundabout calculation will still overflow at twice the size.

For scalar code that's fair, but keep in mind that with `gather`, you can vectorize it, and there you do worry about integer width as more width means fewer lanes. Though tbf you probably should use B+ Tree structures chunked to your bulk/cache fetch "line/page" size, and vectorized higher-than-radix-2 search within each node.

Re: To be a better programmer, write little proofs in your head

#159

Post by bmn__ »

auggierose wrote: post #150
bmn__ wrote: post #140

Earlier quoted context omitted.

People downvoted you because instead of polluting the discussion, you could have looked this up yourself. The answer is yes, both words are related to idios, "own", "self", "private".

Please don't comment about the voting on comments. It never does any good, and it makes boring reading. https://news.ycombinator.com/newsguidelines.html

lame

Re: To be a better programmer, write little proofs in your head

#160

Post by hiAndrewQuinn »

mdnahas wrote: post #144
hiAndrewQuinn wrote: post #2

Oh, I have a relevant and surprisingly simple example: Binary search. Binary search and its variants leftmost and rightmost binary search are surprisingly hard to code correctly if you don't think about the problem in terms of loop invariants. I outlined the loop invariant approach in [1] with some example Python code that was about as clear and close to plain English at I could get. Jon Bentley, the writer of Progra…

I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. Most failures went into an infinite loop on simple cases! The ones who could write it usually did so quickly. I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to…

Indeed, this is actually one reason why I like Python's closed-left, open-right syntax. It lets us sidestep the inclusive bound issue entirely, because, as noted in the post, for all 0 ≤ l ≤ r ≤ len(L) where L is a Python list,

    L
    == L[0:len(L)]
    == L[0:l] + L[l:len(L)]
    == L[0:l] + L[l:r] + L[r:len(L)]
I actually didn't like this syntax until I had to work this out. Now everyone else's approach seems silly to me.
Post reply on HN