bagrounds.org

Search

SearchSearch

Sep 06, 20248 min read

Home > Reflections | ⏮️ ⏭️

2024-06-20

🏃 Running

🥵 Hot. Torturous. Today’s run was the hardest I’ve endured in some time, though it was my standard route.
🌡️ I guess temperature makes a big difference. Today’s high is 79 degrees Fahrenheit.
🤷 That probably means I’m spoiled with cool weather. Oh well.

🏋🏻 Coding Practice

7. Reverse Integer

I previously did some isolated planning for this problem.
Let’s see how well that planning helps with implementation today.

🪞 Reflections

  1. Reading my previous planning notes & writing out a concrete plan took < 6 minutes
  2. My plan worked
  3. If I subtract the previous 11:44 from total time, this took 28:06
    1. It’s a medium problem, so that’s probably acceptable, as I don’t think I’ll get 2 mediums in a single interview
  4. I’m happy that my plan worked out as expected
  5. I don’t care too much about the 1 error that was caught at execution time. I don’t think an interviewer will care about the parens needed for a negative next to an exponent.
    1. Then again, I guess it is mathematically ambiguous without parens, because (-x)^y does not necessarily equal -(x^y)
  6. I used, perhaps more caution than was warranted by creating similar constants for, e.g. the number of digits in the extreme value
    1. This caution was due to not knowing the exact value of the numbers and not wanting to hastily make a potentially invalid assumption
    2. But it did make the code a bit more complex
    3. I’d like to come back and clean the problem up to remove unnecessary complexity

⌨️ My Solution

/*  
1. Reversing the digits is easy: toString -> toArray -> Reverse -> join -> parseInt  
2. The trick, however, is in the constraint that we can't store a number that's out of range.  
3. So we'll have to be able to identify when a number would be out of the 32 bit signed range before converting the string of digits back to a number.  
4. Alternatively, they might want us to detect overflow (i.e. we attempt to store a number bigger than can fit in 32 bits and the result is simply the wrong 32 bit number).  
5. If we simply had to detect overflow, we could just convert the reversed number back to a string after parsing the integer and check if it's the same string as before parsing.  
6. If we have to proactively decide if the (reversed) number will be too large before converting it to an integer, we can try several approaches  
    1. How many digits is the biggest (or smallest if negative) number we can fit in 32 bits? If our string is fewer digits, we're fine.  
    2. If our string has the max number of digits we can fit in 32 bits, we can check digit-by digit, from largest to smallest: if our reversed number's ith digit is smaller or equal to the max (min) able to fit in that place, we're fine. As soon as we find a digit that is strictly smaller, the remaining digits don't matter.  
  
There are log10 digits in a base-10 integer, and the amount of work we're doing is proportional to the number of digits, so:  
Runtime complexity: O(log(N)) in the passed in integer.  
Storing the digits will take O(log(N)) space.  
If the first approach is acceptable (I think we'd have to simulate this overflow effect in JavaScript), this implementation seems pretty easy.  
Implementing the second approach is quite doable, but could get a bit messy in tracking all of the details.  
  
**Planning Time: 11:44**  
  
Concretely:  
1. store min & max values as strings  
2. convert x to a string  
3. if length(x) < length(min|max) return the reversed number, else  
4. if length(x) > length(min|max) return 0  
5. if length(x) = length(min|max), check digit-by-digit, starting with greatest value  
[17:00] Done planning  
[28:24] Done with initial implementation  
[35:46] Done with first test  
[38:55] Done with 2nd test  
Errors found after manual testing:  
1. cannot put a negative to the left side of an exponentiation  
[39:50] Successful submission  
*/  
function reverse(x: number): number { // 7463847412; 2147483647  
  const MIN = -(2**31) // -2147483648 (I calculated this in a REPL, not by hand)  
  const MIN_STRING = MIN.toString().replace('-', '')  
  const MIN_DIGITS = MIN_STRING.length // 10  
  const MAX = 2**31 - 1 // 2147483647  
  const MAX_STRING = MAX.toString()  
  const MAX_DIGITS = MAX_STRING.length // 10  
  
  const isNegative = x < 0 // F; F  
  
  const extreme = isNegative ? MIN : MAX // 2147483647; 2147483647  
  const extremeString = isNegative ? MIN_STRING : MAX_STRING  
  const extremeDigits = isNegative ? MIN_DIGITS : MAX_DIGITS // 10  
  
  const digits = x.toString().replace('-', '') // '7463847412'; '2147483647'  
  const numDigits = digits.length // 10  
  const reversedDigits = digits.split('').reverse().join('') // '2147483647'; '7463847412'  
  
  const reverse = (): number =>  
    parseInt((isNegative ? '-' : '') + reversedDigits) // 2147483647; 7463847412  
  
  if (numDigits < extremeDigits) {  
    return reverse()  
  } else if (numDigits > extremeDigits) {  
    return 0  
  } else {  
    for (let i = 0; i < numDigits; i++) {  
      // 7 > 2 = true  
      if (parseInt(reversedDigits[i]) > parseInt(extremeString[i])) return 0 // return 0  
      if (parseInt(reversedDigits[i]) < parseInt(extremeString[i])) return reverse()  
      // 7 = 7; ...; 2 = 2  
      // if equal, check the next digit  
    }  
    // if all digits are equal, our reversed string is exactly the max value we can fit, so  
    // we can return the reversed number  
    return reverse() // 2147483647  
  }  
};

543. Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.

🪞 Reflections

  1. This is labeled an easy problem, but it seemed… not super easy
  2. The bug was a weird one, related to the execution model used by LeetCode
    1. On one hand, that’s what I get for doing unsafe things
    2. On the other hand, in an interview this probably would have been fine
    3. On the third hand, I guess I should start practicing currying state into a parameter to systematically avoid global state in recursive functions
  3. The time to implement up to the weird state bug was acceptable - 16:25
  4. Another tree problem that’s not super easy. I should definitely keep practicing on trees.

⌨️ My Solution

/* return length of longest path between any 2 nodes in a tree  
1. Hm.. this doesn't actually seem like an easy problem...  
2. Let's see... Maybe I can use the depth of a tree to calculate the longest path  
3. Maybe recursively calculating the depth of a tree, we can look for the node with the greatest sum of depths of children... I _think_ that would give us the longest path...  
4. Let's try it  
5. to make it easy, we can track a rolling max diameter in a global variable  
  
[11:44] Done with initial implementation  
... this feels sus...  
[16:10] Done with a test  
[16:25] wrong answer [1, 2] -> 3  
oof - that's why we don't use global mutable state. It was returning the max from the previous invocation.  
To fix the bug, I reset maxDiameter on firstCall  
[24:11] Successful submission  
Yuck.. I don't really like this implementation. But it works now.  
*/  
/**  
 * Definition for a binary tree node.  
 * class TreeNode {  
 *     val: number  
 *     left: TreeNode | null  
 *     right: TreeNode | null  
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {  
 *         this.val = (val===undefined ? 0 : val)  
 *         this.left = (left===undefined ? null : left)  
 *         this.right = (right===undefined ? null : right)  
 *     }  
 * }  
 */  
  
let maxDiameter = 0  
  
function diameterOfBinaryTree(root: TreeNode | null, firstCall = true): number { // 3; 5; 4; [2, 4, 5]; [1,2,3,4,5]  
  if (firstCall) maxDiameter = 0  
  if (!root) return 0  
  if (!root.left && !root.right) return 0 // 3 -> 0; 5 -> 0; 4 -> 0  
  const leftDepth = root.left ? diameterOfBinaryTree(root.left, false) + 1 : 0 // 1 -> 2; 2 -> 1  
  const rightDepth = root.right ? diameterOfBinaryTree(root.right, false) + 1 : 0 // 1 -> 1; 2 -> 1  
  const diameter = leftDepth + rightDepth // 3; 2  
  maxDiameter = Math.max(diameter, maxDiameter) // 3; 2  
  console.log({root: root.val, maxDiameter, diameter, leftDepth, rightDepth, firstCall})  
  return firstCall ? maxDiameter : Math.max(leftDepth, rightDepth) // 3; 1  
};

Design Interview Framework

Free Recall

  1. Problem Exploration & Functional Requirements
    1. Identify & Prioritize Customers
    2. Use cases
    3. Business Goals & Metrics
  2. Non Functional Requirements
    1. Latencies
    2. CAP - Strong consistency vs high availability
    3. Maintainability - Development, Deployments, & Logging
  3. API Design & Data Model
    1. APIs
      1. CRUD vs events
      2. REST
      3. Public vs Private
    2. Data Model
      1. RDBMS
      2. Object or document storage
      3. Sharding
      4. Subsystem isolation
  4. Capacity Estimations
    1. Network bandwidth
    2. CPU
    3. Memory
    4. Storage
  5. Diagram & Deep Dive
    … To be reviewed

Rationalizing a Framework from Scratch

  1. Systems Thinking: Synthesis → Analysis
    1. Before we can understand the purpose of a system, we must understand the larger system it is a part of. From an understanding of the purpose of the larger whole, we can derive a purpose of the part.
    2. Then, we can use analysis to decompose our system into parts.
    3. Practical implications
      1. Who will build the system?
        1. Single owner: Individual → large, hierarchical corporation
        2. Collaboration: open or closed?
      2. Who will maintain the system?
      3. Who will use the system?
      4. What is the purpose of the system?
        1. Revenue or profit generation?
        2. User acquisition?
        3. Solving a problem?
        4. Innovating?
        5. Philanthropy?
      5. Funding
        1. Budgets
        2. Staff
        3. Resources
          … To be continued

Graph View

Backlinks