Leet Codecheck If N Double Exists And Donald Knuth On Guessing
The aim of this page📝is to learn from 1346. Check If N and Its Double Exist.
Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).
Example 1:
Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.In the process I am stressing the great passage from Donald Knuth’s Oral History and structuring the post into a “Guess → Learn → Improve” Loop.
1. GUESS
- not looking, not googling, just guessing, visualizing, walking with it for a while and coming up with…
- …two-pointers and temporary hash table implemented as a dictionary
2. LEARN
3. IMPROVE
- single-pass with the use of python set as a temporary hash table
- the hash table does not contain doubles and halves, but items themselves
- the check is performed within the loop
4. DONALD KNUTH ON “GUESS → LEARN → IMPROVE” LOOP
Also, your word “heuristics” triggers another thing in my mind, and that is George Polya. Polya wrote this great book called, “Heuristics and Plausible Reasoning.” Of course, I know heuristics is a great word for you because you had the ”Heuristics Programming Project” and all these things. Heuristic, meaning discovery. Polya also inspired me. I had the great fortune to get to know him because he’s a Stanford professor. He came to my house many times and I spent a lot of time with him. One of the things that cuts across also many years is he had an approach to teaching that he called, “Let Us Teach Guessing.” When he was teaching his classes, he’s not saying, “Memorize this, guys.” He’s saying, “Here’s a problem. How do you solve it?”, with the idea that the students are going to make mistakes and then they’re going to learn how to recover from mistakes, as well as making guesses. These are important heuristics for my life, both in the teaching aspect and in the research aspect. Let me talk about the teaching aspect first. Polya gave a demonstration lecture that was filmed at Stanford, and I saw it when I was still at Caltech. I saw this. He presents the students with a problem, with something like, “You have a piece of cheese and you cut it with four strokes. How many pieces are you going to get?” Something like this. Then he has the students try to analyze this. He started out by looking at simpler problems, where it’s on a plane instead of in three dimensions, and you only take two cuts; things like this. At the end of the hour he has all the students understanding not only the solution to this problem, but also having taken apart and discovering the solution themselves. That’s what goes into their brain, because then they can solve other problems later on. I adopted this as a model for my own classes, already at Caltech. Whenever I taught a class that had a decent textbook, I would devote the class time to problem solving as a group, instead of reading to them or lecturing to them about what’s in the book. I would assume that they could read the book on their own. They come to class, we do things that aren’t in the book. We take a problem that’s similar to ones in the book and we try to work on it, almost like a language class. I go down the row and, “It’s your turn, your turn, your turn.” People soon learned that if they make a mistake, we all do, and we recover. I’d give a rule that nobody’s allowed to speak more than twice in the hour, so that everybody participates. My teaching assistants would take notes, so that the students could concentrate on what was going on instead of having to worry about having their notes right so they couldn’t listen fully. The teaching assistant’s notes would then be typed up later on by Phyllis and distributed to everyone. So we could record these sessions in the class as to things that aren’t in the book, and how to recover from errors. I kept that style of teaching all the way through until I retired. That was a great source of pleasure. I could use it except in the cases where there was no textbook available. In my own research, this idea of guessing is also very important. When I read a technical paper, I don’t turn the page until I try to guess what’s on the next page. Or, [say] the guy writing the paper is going to state a problem. Before I look any further, I’ll say, “Now how would I solve this problem?” I fail almost always. But I’m ready now to read the solution to the problem, so then I turn the page and I see. But by this time I’m ready for what’s happening. When I work on “The Art of Computer Programming,” over a period of 40 years I’ve gathered together dozens of papers on the same subject. I haven’t read any of them yet except to know that they belong to this subject. Then I read those papers, the first two papers extremely slowly with this “Don’t turn the page until you’ve tried to solve the problem yourself and do it yourself.” With this method, I can then cover dozens of papers. The last ones, I’m ready for. I just know what to look at that’s a little different than I’ve already learned how to absorb. That’s been a key heuristic in my own research, based on guessing.
