bagrounds.org

Search

SearchSearch

Sep 06, 202413 min read

Home > Reflections | ⏮️ ⏭️

2024-06-15

🧠 Education

🧰 Tools to Enhance Working Memory & Attention

🔮 Planning for my upcoming interview

Planning for Everything proposes the STAR FINDER framework.
Make planning more…

  1. 👥 Social
  2. 📈 Tangible
  3. 🐿️ Agile
  4. 🪞 Reflective

… through …

  1. 🖼️ Framing
  2. 💭 Imagining
  3. ✂️ Narrowing
  4. 👩‍⚖️ Deciding
  5. ⛹🏻 Executing
  6. 🪞 Reflecting

🖼️ Framing

  1. I have my first interview on Monday
  2. The role I’m apply for represents a step up on my career track
  3. I’ve been practicing for a couple of months
  4. The interview agenda
    1. A behavioral question
    2. 2 coding questions
    3. An opportunity for me to ask questions

💭 Imagining

1. Before my interview, I’ve prepared my mind, body, and environment for calm, focused, optimal performance.

  1. I slept well.
  2. I ate well
    1. breakfast and lunch
    2. Not too heavy
    3. Fiber → protein & fats → carbs
  3. If tired, I took a ~20 minute nappuccino+++
    1. Coffee → nap → cold exposure → bright light → exercise
  4. Aerobic exercise: ideally I’ve gone for a run.
  5. Hot, then cold shower.
  6. My office is clean, orderly, bright, and prepared.
    1. My headphones are charged and connected.
    2. I’m logged in to the zoom call and coderpad at least 5 minutes early.
    3. I can close my window or door as necessary to dampen distracting noises.
    4. I can choose noise canceling headphones if necessary.
    5. I have blank paper and pen ready for notes.
    6. I have coffee and water.
  7. The cats are quiet and distracted somewhere else in the house.
  8. I’m calm and in a good mood.

2. In the ideal interview

  1. I answer a behavioral question with a concise, specific, relevant story, demonstrating, technical expertise, leadership, and good judgement in a context with broad scope.

  2. I demonstrate effective problem solving, coding, communication, and verification skills on one or two coding problems.

    1. Planning (problem solving)
      2. I first demonstrate an understanding of the problem by paraphrasing, asking clarifying questions, and illustrating examples
      3. Next, I consider multiple approaches to solving the given problem
      1. I might start with an obvious, brute force approach
      2. Then I may search for insights, data structures, and algorithms that support a more efficient solution
      3. Is recursion a good fit? (And is my interviewer comfortable with a recursive solution?)
      4. Are there any obvious data structures or algorithms that come to mind?
      5. How can I reduce the search space?
      6. How can known properties of correct results inform my search?
      4. I identify the runtime and extra space complexity implied by each approach
      5. I consider trade offs
      6. And I seek agreement or hesitation from my interviewer
      7. If I can’t identify a satisfactory solution, I explain my situation and ask for guidance from my interviewer
      8. I carefully consider any feedback or hints they provide and incorporate them into my strategy
    2. Coding
      1. I should start with a top down approach
      2. Focus on the core of the solution
      3. Don’t implement helper functions in advance (or at all if my interviewer doesn’t ask me to)
      4. Move quickly, but carefully, taking time to use good variable names and patterns
      5. If stuck in the details, I can
      6. Simulate the algorithm working with example inputs
      7. Clearly state or write the point I’m focused on, and what exactly I’m stuck on
      8. Consider declaring a few moments of radio silence while I work out the details in my head
      9. When I’ve finished the top level function, I should ask my interviewer if they’re ready for me to test my solution, or if they’d like to see something more first (e.g. implementing a nontrivial helper function)
    3. Testing
      1. Choose an example input with high code coverage
      2. Walk through the code line by line, annotating critical variables with in-line comments succinctly describing state
      3. Be sure to mentally simulate each line of code and not just write what each value should be.
      4. Assume I’ll find bugs - I almost always do.
      5. Describe the bugs I find, making quick fixes when appropriate
      6. Keep an eye out for common kinds of bugs
      7. Logic errors
      8. Unhandled cases
      9. Off by 1 errors
      10. > vs >=
      11. Null pointer dereferencing
      12. Using wrong variable names
      13. Type errors (e.g. using an array instead of its length)
      14. Infinite loops
      15. Missing base cases in recursive functions
    4. Communication (throughout)
    5. Ask clarifying questions
    6. Occasionally check that the interviewer is following
    7. Demonstrate understanding with examples
    8. Narrate my thought process, but don’t be too verbose
    9. Use good variable names
    10. Describe and document obscure tricks, language features, and helper functions
    11. Pay careful attention to tips, hints, or questions my interviewer asks: they’re trying to help
    12. At the end, analyze my own code, commenting on what I like and don’t like about it. Would I approve this in a code review? What compromises or trade offs have we made?

  3. I ask good, strategic questions when invited.

  4. People love talking about themselves. Consider asking about my interviewer.

  5. Is there anything I can ask this interviewer that can help me in later interviews?

  6. Demonstrate my sincerity and enthusiasm for joining the company with thoughtful questions about culture, structure, or expectations.

✂️ Narrowing

  1. I don’t have much time left to prepare
  2. But I’ve covered a lot over the past weeks and months
  3. What gaps stand out in my mind?
  4. What’s the best use of my remaining time?

👩‍⚖️ Deciding

  1. I’ll aim to interleave
    1. Practicing coding problems
      1. end-to-end
      2. keeping an eye on timing
      3. and reviewing my work when it takes too long
      4. looking for different ways to solve the same problem faster
      5. and looking for patterns in successful and failure paths
    2. Implementing some basics and classic algorithms and data structures
    3. Writing more stories for behavioral questions
  2. With so little time before game day, I’m not likely to dramatically improve my performance at this point, so I’ll focus on fine tuning, moderation, and physical and psychological preparation

🏃 Executing

✍🏻 See below.

🪞 Reflecting

🔜 Coming soon.

🏋️ Practice

58. Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal substring consisting of non-space characters only.

🪞 Reflections

  1. even in easy problems, managing state is complicated and error prone (2nd implementation)
  2. annotating the index variable i during testing was a waste of time
  3. annotating true and false during testing could have been shortened to T | F
  4. I’m not super confident in regex special character notation (e.g. \s for white space… or is it \S … \w is for words or white space?)
  5. In the 2nd implementation, the test input was a bit unnecessarily complicated, e.g. didn’t need all the extra white space
  6. timing was still great for both of these implementations, ~9 & ~13 minutes respectively
  7. that said, this was a very easy problem
  8. initial planning was probably too detailed and took too long for this simple of a problem

My Solutions

/* return length of last word in string  
- a word consists of non-space characters  
  
example:  
"  howdy-there  world   " -> 5 (world)  
  
Solution is straight forward.  
1. trim the string for leading and trailing whitespace  
2. split on whitespace  
3. take the last element  
4. return its length  
  
Runtime complexity: O(N)  
  
Potential interviewer questions:  
- Do inputs use non alphabet characters? dashes, slashes, special characters, etc? Are they part of words?  
- Do I need to consider non utf-8 characters? Characters that get split across multiple bytes?  
- Is punctuation included in word length? e.g. world! is 6 characters?  
[4:54] done planning  
[6:06] done with initial implementation  
[8:24] done with 1 test (added + to regex)  
[8:45] zero bugs found after testing; success on first submission  
*/  
function lengthOfLastWord1(s: string): number { // " hello,  World!  "  
  const trimmed = s.trim() // "hello,  World!"  
  const words = trimmed.split(/\s+/) // ["hello,", "World!"]  
  // checking if split takes a regex... yep  
  const last = words[words.length - 1] // "world!"  
  return last.length // 6  
};  
  
/* Now I'll implement as if I'm not allowed to use helper functions.  
Plan:  
0. Initialize result to 0  
1. Iterate over each character in string, left to right  
2. at whitespace, reset result to 0  
3. otherwise, increment result on each non-whitespace character  
4. return result  
Runtime: O(N)  
extra space: O(1)  
  
change of plan during implementation:  
- can't reset to zero on all whitespace characters due to trailing whitespace  
- instead, only reset to zero if wordEnd is true and we're looking at a non-whitespace character  
- set wordEnd to true each time we see whitespace  
[12:32] finished (plan, implemenation, and) testing  
Bugs found during testing:  
1. set whitespaceSeenLast to false in 2nd conditional block  
[12:54] zero bugs caught after testing; success on first submission  
*/  
function lengthOfLastWord(s: string): number { // "  hi,  you  "  
  let result = 0  
  let whitespaceSeenLast = true  
  for (let i = 0; i < s.length; i++) { // 11; 10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0  
    // ' '; u; o; y; ' '; ' '; ,; i; h; ' '; ' '  
    if (/\s/.test(s[i])) {  
      whitespaceSeenLast = true // true; true; true; true; true; true  
    } else if (whitespaceSeenLast) {  
      result = 1 // 1; 1  
      whitespaceSeenLast = false // false; false  
    } else {  
      result++ // 3; 2; 3; 2  
    }  
  }  
  return result // 3  
};

2956. Find Common Elements Between Two Arrays

You are given two integer arrays nums1 and nums2 of sizes n and m, respectively. Calculate the following values:

  • answer1 : the number of indices i such that nums1[i] exists in nums2.
  • answer2 : the number of indices i such that nums2[i] exists in nums1.
    Return [answer1,answer2].

🪞 Reflections

  1. Planning went well, though maybe a bit long for this problem (5:32)
  2. Implementation was fast and correct on first try
  3. Testing was fine
  4. Overall time was satisfactory: 11 minutes (15 minute target)
  5. Even implementing the more complicated version with sorting, there was only the one bug due to JavaScript’s default sorting (though time was a bit long at 21 minutes)

My Solutions

/* return both:  
1. number of indices in nums1 whose element exist in nums2  
2. number of indices in nums2 whose element exists in nums1  
i.e. common elements including duplicates - excludes use of sets  
  
1. Brute force: for each n in nums1, check for existence in nums2 & vice versa (O(N * M) - or basically O(N^2) runtime)  
2. Make a set for nums1 and a set for nums2, iterate through each, checking existence via the set (which is a constant time lookup)  
Runtime: O(N + N + N + N) ~= O(N)  
Extra Space: O(N)  
  
3. If we don't want to use the extra space, we could sort each and iterate with 2 cursors for an O(N * log(N)) runtime  
  
Starting with approach 2, which should be the simplest to implement.  
[5:32] done planning  
[7:30] done with initial implementation  
[10:49] done with test  
No bugs found during testing (though I did accidentally annotate test state without a comment at first)  
[11:00] success on first submission  
*/  
function findIntersectionValues1(nums1: number[], nums2: number[]): number[] { // 1,2,2 3,1,1  
  const set1 = new Set(nums1) // {1,2}  
  const set2 = new Set(nums2) // {3,1}  
  const count1 = nums1  
    // 1 -> 1  
    // 2 -> 1  
    // 2 -> 1  
    .reduce((count, element) => count + (set2.has(element) ? 1 : 0), 0)  
  const count2 = nums2  
    // 3 -> 0  
    // 1 -> 1  
    // 1 -> 2  
    .reduce((count, element) => count + (set1.has(element) ? 1 : 0), 0)  
  return [count1, count2] // [1, 2]  
};  
  
/* try again with constant extra space  
1. can't use sets for quick lookup  
2. can sort each and use 2 cursors for O(N * log(N)) runtime  
3. can we do linear runtime and constant extra space?  
4. Yes. The numbers are between 1 -> 100, so we could encode existence in a bitstring (i.e. a single number can encode the entire set for each - constant space). Oh wait, that would require a 100bit number, which we would need 4 32-bit or 2 64-bit numbers to encode, and it would get a bit messy (no pun intended) to manage.  
5. Technically, I could argue that the sets are constant extra space because they won't be any larger than 100 elements due to input restrictions... that's just the previous implementation.  
6. For now, I'll just go with the sorting approach.  
[5:20] done planning  
[13:38] done with initial implementation  
[19:10] done with test  
[19:37] first submission: wrong answer  
Bugs found after submission:  
sorting is lexicographic by default, needed to add (a, b) => a - b to sort numerically  
[21:35] successful submission  
*/  
function findIntersectionValues2(nums1: number[], nums2: number[]): number[] { // 1,2,1 3,1  
  nums1.sort((a, b) => a - b) // 1,1,2  
  nums2.sort((a, b) => a - b) // 1,3  
  let count1 = 0  
  for (let i = 0, j = 0; i < nums1.length && j < nums2.length;) {  
    const n1 = nums1[i] // 2; 2; 1; 1  
    const n2 = nums2[j] // 3; 1; 1; 1  
    if (n1 < n2) {  
      // 1 2 3  
      // 2 3 4  
      i++ // 3  
    } else if (n1 > n2) {  
      // 2 3 4  
      // 1 2 3  
      j++ // 1  
    } else { // n1 == n2 equal  
      // 2 2 4  
      // 2 3  
      count1++ // 2; 1  
      i++ // 2; 1  
    }  
  } // count1 = 2  
  
  // under longer time constraints, I'd refactor to a helper function; copy/pasting for expedience  
  let count2 = 0  
  for (let i = 0, j = 0; i < nums1.length && j < nums2.length;) {  
    const n1 = nums1[i] // 2; 1; 1; 1  
    const n2 = nums2[j] // 3; 3; 3; 1  
    if (n1 < n2) {  
      i++ // 3; 2; 1  
    } else if (n1 > n2) {  
      j++  
    } else {  
      count2++ // 1  
      j++ // 1  
    }  
  } // count2 = 1  
    
  return [count1, count2] // [2, 1]  
};  
  
// refactor to use helper function  
function findIntersectionValues3(nums1: number[], nums2: number[]): number[] {  
  const commonElements = (nums1: number[], nums2: number[]): number => {  
    let count = 0  
    for (let i = 0, j = 0; i < nums1.length && j < nums2.length;) {  
      const n1 = nums1[i]  
      const n2 = nums2[j]  
      if (n1 < n2) {  
        i++  
      } else if (n1 > n2) {  
        j++  
      } else {  
        count++  
        i++  
      }  
    }  
    return count  
  }  
    
  nums1.sort((a, b) => a - b)  
  nums2.sort((a, b) => a - b)  
    
  return [commonElements(nums1, nums2), commonElements(nums2, nums1)]  
};  
  
// refactor original version to use arrays instead of sets for lookup  
// this demonstrates that we can do it in linear time with statically allocated constant space (though that constant is 202, which may be larger than many inputs)  
// but the implementation is algorithmically equivalent to the original implementation  
// a micro-optimization may be present in that the array is allocated once,  never has to be resized, and involves a very simple mapping function from index to value (whereas the hash set may require dynamic allocation as the set grows and may involve slight overhead due to hash function computation)  
function findIntersectionValues(nums1: number[], nums2: number[]): number[] {  
  const set1 = new Array(101)  
  nums1.forEach(n => set1[n] = true)  
  const set2 = new Array(101)  
  nums2.forEach(n => set2[n] = true)  
  const count1 = nums1  
    .reduce((count, element) => count + (set2[element] ? 1 : 0), 0)  
  const count2 = nums2  
    .reduce((count, element) => count + (set1[element] ? 1 : 0), 0)  
  return [count1, count2]  
};

Graph View

Backlinks