documenting p-knuth

project begin date: Jan 04, 2022
project end date: Indefinite
completion rate: 50%
success rate: 40%
remarks: difficult; work in progress

• Nuggets:

  • inorder traversal, preorder traversal, postorder traversal are all depth first-ish, very unlike level order traversal which is more breadth first-ish
  • postorder traversal is strictly bottom-up. inorder traversal is slightly bottom-up. preorder traversal is strictly top-down.

• why learn algorithm design?

• what makes algorithm design troublesome but fun (Private)?

• How do you remember the wandering of thought processes that went into implementing the code for an algorithm? Even after months of implementing the code? Especially when you don't have all the time to practice?

  • For example, See Leetcode 5, Longest Palindromic Substring & Leetcode 647, Palindromic Substrings.

• Write down your thought process when thinking about a solution for problems. (You actually shouldn't do this)

• See using Anki to think about algorithm design problems.

  • are you not cramming code? (Private)---Oh no, actually not.

• Some algorithms become more Interesting because it is clear how they are very practically useful.

  • (See Sean Parent and std::rotate in C++ GoingNative 2013).

• Algorithms that easily become a part of you (because they are simple? or their problem statement is straightforward? or the solution is memorable?)

  • Linked List: "Design an algorithm that, given a pointer to the head of a linked list, returns a pointer to the element at the middle of the list", Leetcode Link
  • Bit-shifting, Adhoc: "Design an algorithm that, given a non-empty array of integers where every integer appears twice except for one integer, returns the value of that one integer", Leetcode Link
  • Breadth-first search
  • Depth-first search

• Restate problem statement for algorithms in your own words (i.e., compress them)

  • For example, despite the long plot for the problem in Leetcode 198 - House Robber, the task is basically to design an algorithm that makes a selection of numbers in an array such that the sum of the selected numbers is maximum but adjacent numbers cannot be selected.
  • A compressed statement then is; select maximum sum of non-adjacent numbers from given array.

• It is usually the case that it is the thought process towards a solution (EDIT: or rather, it is the conditions, dependencies, reasons, intent, hows, whys (why this condition in the for loop), &.c within the code for the algorithm/solution) for a problem that one would want to remember. This is most times difficult to do for non-simple problems or for a beginner.

• It is also important to understand that algorithms designed with the technical interview process in mind are not in their final form. They could be modified into shorter and easier-to-think-about code by employing the programming language's standard library. Employing this standard algorithms library is a skill.

  • For example... "Design an algorithm that, given the head of an unsorted linked list of integers, returns the head to the linked list sorted using insertion sort"

  • To solve this, if the input is not a linked list but an array, one could go on and implement the insertion sort procedure. But it is usually better to employ standard lbrary algorithm. The algorithm below is an implementation of the insertion sort procedure on an array, making use of the std::rotate, std::upper_bound, and std::next algorithms in c++.

    for(auto i = start; i != end; i++){
      std::rotate(std::upper_bound(start, i, *i), i, std::next(i));
    }
    

• coding problems are puzzles you solve by thinking/tinkering first, without code. after you've got the solution, you translate the idea you've got into code. the most useful/transferrable learning comes in this stage.

  • curiously, there's no way to accurately decouple the puzzle-solving process from the translation process because you inevitably think in code. you think in the affordances & constraints of your programming language; "is there a way to do this easily, with a few characters of code in python? etc" the two are conceptually separate and yet bound.
  • Leetcode problem 2551 (Put Marbles in Bags) illustrates this

• it is best to "remember" the outline of the (coded) solution to each problem—which is easier to do when you actually understand the solution—so that it is easier to think about a solution for related problems which (by definition) should build upon (or be similar to) the coded solution for the initial problem.

  • The coded solution for the Maximum Depth of Binary Tree problem is similar to that of Minimum Depth of Binary Tree such that if the former is solved before the latter and the solution remembered, it is easy to implement the solution for the latter since relatively little thinking/figuring-out will be required.
  • Also for Number of Islands and Max Area of Island.

• we don't care about puzzles or finding the patterns of algorithm design thinking in our household lives because we don't particularly care about optimization; the data is not fully available at our grasp at any given moment &c. But for companies whose profit or life & death status is dependent on how well they cut their losses, optimization is important.

• I think it is best to play around the solution of an algorithm problem as a beginner (if you don't want to move fast), this way you get a feel of the breadth or landscape of the (mathematical) patterns in the problem.

• (leet)coders tutoring on youtube are not teachers, beginners will get the wrong impression that that [top-down coding] with ease is how problems are solved. (on the difficulty of communication)

  • this is a good example of a youtuber thinking through a problem?
  • including some from exponent
  • A much better example!: Errichto solves the Valid Parenthesis String problem
  • "leetcode tutorials," instead, could be "journals" of the exploration towards a solution, rather than an exposé of the solution..
    • the problem is? we don't have all the time.
    • I seem to have a sub-good illustration of this through the Sliding Window Maximum problem.

• how do you convince yourself with quick proofs that the algorithm you're blindly putting together will compile and give the correct results?

  • this is very important and is one the reasons some problems feel difficult.. they feel tricky because you cannot prove to yourself that so and so step that you envision will be "correct" and you don't eventually foray into that path or you probably couldn't even see it. (Integer Break)
  • (written after attempting the Merge Intervals problem)
    • I was too unsure the step I was taking led to a solution

• backtracking (Private) is retraced recursion (thinking non-intuitively about recursion)

• What is the pattern in the way decision trees are used to think about solution to problems (Private)?

• What is the pattern in the code for algorithms that solve backtracking problems (Private)?

• What is the pattern in the repeated work of problems that can be solved using dynamic programming?

• It is curious that I have not come across or solved a lot of Simulation problems (like Robot Bounded In Circle or ). OR RATHER, I have not primed myself to think about identifying them in interviews. So, I was a bit unsure what step to take when I encountered two simulation problems (which I didn't initially classify) in a GS interview. August 15th

  • But it turns out I have solved about 9 of these through Leetcode (Spiral Matrix II, Game of Life, Fizz Buzz, Baseball Game, Asteroid Collision, Backspace String Compare, Validate Stack Sequences, Shift 2D Grid, Build Array from Permutation)

• A good problem: Sliding Window Maximum

• You try to learn these things in such a way that whatever is learnt, however meager, is transferrable in obtaining the solution to other problems.

---

Backlinks

• Projects
• using Anki to think about algorithm design problems