behdad

I expect any candidate to be hired to be able to produce code for the brute-force cases, and do the runtime analysis on them.

It's a whole other debate that most software engineers, even at BigCo end up writing CSS code to move pixels only and lose their DSA knowledge over time...

Yes, the string equality itself is o(n).

n is the length of the string. As for why it matters whether it's linear or quadratic, we are assessing the candidates ability to analyze a problem and possibly improve an algorithm. It might not matter in the problem at hand.

That's the same as the trie solution.

You are technically right. Though if we assume that the size of the dictionary is at least o(n), then the size of such DFA will be exponential in n, and indexing it will be o(n), resulting in a o(n^2) solution again, I think.

How?

You still need to query every byte of the input string...

Any better than that you can do would be O(min(n, k)) where k is the length of the longest word in the dictionary. But without loss of generality that would be O(n).

You are correct in that. A few points though:

- While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases,

- I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one,

- When interviewing entry-level software-engineers, there's not much else you can ask them except for what they learned in class, which is these kinds of questions.

Thanks for the comment. By saying "I get good signal" I mean that it's not a binary yes/no, but gives a range to score the candidate. You are right about actual correlation to job performance. I know the HR at Google performed correlation analysis between interview scores and job performance and made internal observations, which as you note is biased because only includes hired candidates.

That might have worked before ChatGPT. :)

With the dynamic-programming you don't need the reverse trie indeed.

Between 2010 and 2019 I interviewed dozens of Software Engineer candidates at Google. Almost always I asked the same interview question. Moreover, this question happened to be on the banned list at Google, because it was publicly available on Glassdoor and other interview websites, but I continued to use it because I got good signal from the candidates.

I (Behdad Esfahbod) discuss Microsoft+Adobe unfair-competition practices in the ISO Open Font Format process.

3hr video. I understand is long, but please watch if you care about my cause.

Hey. Behdad here. I live in the States but one of our core developers is in Iran. This whole incident was a huge miscommunication on github. Fortunately they have addressed some of it. In short: Open Source and public repos are not affected at all. HarfBuzz has been on github. We will consider moving to fdo or GNOME gitlab if github becomes a problem. Cheers

Hey. HarfBuzz maintainer here. I live in the States but one of our core developers is in Iran. This whole incident was a huge miscommunication on github. Fortunately they have addressed some of it. In short: Open Source and public repos are not affected at all. Cheers

Ouch! Thanks for the report. We'll look into fixing that ASAP.

Please continue conversation here:

  https://bugzilla.gnome.org/show_bug.cgi?id=321490

Hi,

Thanks for the nice words. I wrote BiCon over ten years ago and never touched it again. It definitely wasn't before SIGWINCH was introduced as I was barely four years old then :).

I checked the code, looks like code for SIGWINCH was there, but not working. I believe this got broken during the pty rewrite we did back then. At any rate. I just fixed that, and fixed initial window size. Enjoy, and in the future, feel free to shoot me an email if something I maintain bothers you!

  https://github.com/behdad/bicon/commits/master

Cheers, behdad

Yes, that's what I want to do. My main goal redesigning the buffer was to 1) fix memory fragmentation, 2) make unlimited scrollback possible. I offered to find some time on a weekend to add a caching layer, a compression layer, and an encryption layer. But the author of that report was more interested in getting publicity I guess, so ignored my offer and made it look like I said I won't fix this. Well, NOW it's harder to justify taking time off my personal life to work on this...

No, actually it's not. That's a different issue.