Monthly Archives: June 2023

Linked List

Delete Node in a Linked List (Leetcode)

Another question from the archives. I was loathe to share this because it was an easy (or medium?) question at the time that I really hammered on but could not solve. The description makes it plain there’s not too many options on what to do, but having exhausted everything I could think of, I looked at the answer. It was not something I considered a good practical approach. Let’s discuss.

The Meta-Problem

You have a singly-linked list, and you have a pointer to a node, and you want to delete that node. The challenge is that, naively “blowing away” that object would invalidate the list: presumably there is some prefix that ends with the node you were given, and the node you were given may continue with some suffix.

So ideally you’d have a pointer to the node prior to the one you want to delete. Then you just do node.next = nodex.next.next, up to null-checks and the like. We lack that ability.

Vindication

Having returned to this question many years from now (and to be clear, my notes have the solution I ultimately got from the site), I feel vindicated. As of reading in June 2023, the following paragraph is included:

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean: […]

That clarification was 100% missing in the version I read! I can’t objectively claim I would have gotten it with that clue, but saying delete and not meaning free-the-memory is a pretty weird construction.

So I would bet this question got a lot of feedback. Anyways, the solution is straightforward, it’s more an excuse to have a cute loop over linked lists.

class Solution:
    def deleteNode(self, node):
        prev = None
        while node.next is not None:
            node.val = node.next.val
            prev = node
            node = node.next
        prev.next = None
Introductory, Linked List

Middle of Linked List (Leetcode)

Another warm-up question from the archives.

The editorial solution, fast-and-slow-pointer, is very cute. I’m not sure how it’s preferable over separating the length (“fast”) calculation from the actual-find-calculation (“slow”). We’re doing the same traversals, but presumably with better locality?

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        l = 0
        n = head
        while n is not None:
            n = n.next
            l += 1

        n = head
        for i in range(l//2):
            n = n.next
        
        return n
Interview Questions, Introductory, Musings

Find the Duplicate Number (Leetcode)

This is a reasonable warm-up question I think, but the performance-related requirement (constant space) is silly. Reading the editorial, well, I have thoughts to share. This is from the archives.

Using this as a warm-up question

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = set([])
        for n in nums:
            if n in seen: return n
            seen.add(n)

This presents an approachable-enough setting to discuss performance, and I think things like “find the duplicates” are related to real-world questions. Moreover, there are ready sequels: OK, if they use this “hash table approach”, what about one that can take more time, but less space?

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        prev = None
        for n in sorted(nums):
            if prev is None:
                prev = n
            elif prev == n:
                return n
            prev = n

Considering The Leetcode Discussion

The leetcode “editorial” (at least as of June 2023) presents 7 different approaches for the problem. Here are some of my reactions to the editorial. This is my experimental foray into providing a criticism to, what I think is the typical leetcode perspective on questions. I’m not meaning to pick on this particular question.

  • “[The problem] is a classic problem” — I’m not sure in what domain this question is a classic. Deduplication in general is very useful, but the particular of this question don’t strike me as something classic. Maybe it’s a common interview question for a certain company? I wish leetcode questions placed their evaluations in more context. It gives the air of secret knowledge (“oh, this is a classic question, and I didn’t know that!”) when I think they’re just… making things up.
  • Approach 3, in which they borrow a bit from each element in the array (and use the range-trick) they say is O(1) space. In practical terms, sure, but what if the array is, say, unsigned shorts and the size of 2^16? You have no bits to borrow; that’s just an example where this is sort of “punning” between theoretical concerns (asymptotic analysis of resource usage) versus practical concerns. Both are fine, but mixing them leads to confusion.
  • The other approaches are fun things to learn, but all (including approach 3) really rely on the particular structure of the input. It’s just unsatisfying.