4 ms·
Haha, this is pretty funny. I immediately thought of Cantor's diagonal argument when I saw the question, but it makes me wonder — how long would it have taken m
by Xcelerate 2y ago
Haha, this is pretty funny. I immediately thought of Cantor's diagonal argument when I saw the question, but it makes me wonder — how long would it have taken me to solve the problem if I hadn't previously read about Cantor's argument in the context of Turing machines?
Here's a variant: "Given a list of k LeetCode problems sourced from a bag of n unique tricks, generate a new LeetCode problem that utilizes a trick not found in the bag."
I'm being facetious of course, but actually now I have an idea that we could create a bipartite graph mapping tricks to LeetCode problems. From there, given a willingness to memorize n tricks, we can compute the optimal bag of tricks to commit to memory in order to maximize the number of LeetCode problems quickly solvable during an interview, weighted by the probability of each problem's appearance.
- jrochkind1 2y agoCantor's diagonilization is something I think one would learn in most CS curricula, at least I did. Obviously Cantor was a genius, I would not expect most people, including myself, to come up with his argument themselves from scratch!
- nitwit005 2y agoI learned about that proof from a YouTube math video, rather than my Computer Science degree or minor in Mathematics. People expect genius in interviews all the time. They just don't realize that's what they're doing. They think what they're asking about is an obvious concept, forgetting that (insert renowned genius here) came up with the idea.
- YZF 2y agoI'd have thought group theory would be a required math course. This would also come up in Comp.Sci. complexity contexts and even in Calculus or mathematical logic contexts (I'm sure in many others I'm missing). Way back when this was a required first year course in the Comp.Sci./Math program I took.
- deleted 2y ago[deleted]
- nitwit005 2y agoI suspect you are forgetting the possibility they just didn't cover that particular proof.
- deleted 2y ago[deleted]
- jrochkind1 2y agoI also would have thought that it would be covered in a CS curriculum, as I said. it'snot just some random proof, but an important foundational one. (I don't think I "forgot a possibilty", I just thought it usually would). You are saying you took classes that covered logic, number theory, group theory, algorithmic complexity, discrete math, and calculus, and you are certain none of them covered this? Too bad, that is unfortunate! I'm glad you found it on your own! it's really neat!
- YZF 2y agoYeah. It's pretty foundational. e.g. https://en.wikipedia.org/wiki/Aleph_number https://en.wikipedia.org/wiki/Aleph_number I guess it's possible to teach it without going through the proof.
- gopher_space 2y agoHow many times have you been asked to rediscover the Fibonacci sequence and then make it useful to some stupid business?
- eru 2y agoYes. Cantors diagonalisation wasn't just a neat proof for an interesting theorem, but it made Cantor one of the few people to invent an entirely new class of proof technique. I'd give it a similar status to techniques like 'indirect proof' and 'induction'.
- fragmede 2y agoHilariously, you can plug that into ChatGPT and get a (new?) leetcode problem out. https://chatgpt.com/share/baf1c785-11dc-46d1-aed7-860cbc741f46 https://chatgpt.com/share/baf1c785-11dc-46d1-aed7-860cbc741f...
- zzigge 2y agoThat seems almost like the way people curate their Magic the Gathering decks.