Category Archives: Introductory

Interview Questions, Introductory, Strings

Roman Numerals to Decimal (Leetcode)

This is apparently a popular question. It seems OK, it’s very easy. I think I already knew the rule of subtraction. I suppose questions that prompt the learner to consider “doing the work” of writing out a map is nice.

Maybe there’s something to it with the loop being backwards. What if I did it forwards? Seems like it’d end up in the same place: the condition in the if statement would be a bit different, that’s all.

MAP = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        val = 0
        prevC = None
        for c in reversed(s):
            if prevC is not None and MAP[c] < MAP[prevC]:
                val -= MAP[c]
            else:
                val += MAP[c]
            prevC = c
        return val
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.
Interview Questions, Introductory

Two Sum (Leetcode)

This is the classic, literally Leetcode question 1. It’s an OK question. It admits a “naive” solution of try-every-pair, and also enables some deeper thought. I don’t have a good read on whether that deeper thought should be considered expected in an interview setting.

Naive Solution

The naive solution is try-every-pair. This is an accessible example of a concept I like, where we have the explicit object (in our case, an array), but we’re really exploring an implicit object (in our case, a sequence of pairs of elements, those elements drawn from an array). We can be careful about precisely which pairs we’re exploring.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i]+nums[j] == target:
                    return [i, j]

Not-Better Solution

The interesting thing is how to derive the better solution. Let’s formulate it in terms of the condition we “care” about, nums[i]+nums[j] == target. With arithmetic, we can say that’s the same condition as: nums[i] == target – nums[j], (we subtracted nums[j] from each side).

So we can derive a new sequence, diffNums, where we assign diffNums[j] = target – nums[j]. Now what would our loop look like?

class Solution(object):
    def twoSum(self, nums, target):
        diffNums = [target-nums[i] for i in range(len(nums))]
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i] == diffNums[j]:
                    return [i, j]

This is not faster by any measure: asymptotically it’s still O(n^2), and now we have an extra intermediate array diffNums to instantiate. Sure enough, it’s too slow for Leetcode, haha.

However, a careful look at our condition now is enticing: we’re “just” seeing if the collection nums has any element in common with the collection diffNums. That’s set-membership! So let’s recast things:

Faster Solution

We ultimately need to return the indices. So let’s have diffNums be a mapping from target-nums[i] : i.

class Solution(object):
    def twoSum(self, nums, target):
        diffNums = {target-nums[i] : i for i in range(len(nums))}
        for i in range(len(nums)):
            v = nums[i]
            if v in diffNums and i != diffNums[v]:
                return [i, diffNums[v]]

A lot has changed! Crucially, we have the if v in diffNums condition: that captures the whole inner for-loop! Even better, because diffNums is a map, we can expect that lookup to be roughly constant time, instead of linear. This brings our algorithm down to roughly-linear time. (Note that diffNums[v] is basically j in this loop.)

Conclusion

This problem grew on me, in terms of introducing some intermediate programming thoughts. I think if we have to use this an interview question, assuming the candidate is stuck on getting the faster solution, I’d prompt them to that not-better solution and see where they take it. More introductory questions here.

Interview Questions, Introductory

Jump Game (Leetcode Dynamic Programming Study Plan)

Well this one was embarrassing, I flubbed a lot of the base cases. I spent the most amount of time, however, trying really hard to see what I was missing: frankly, I don’t see why this is considered a harder question (“Medium”), and I don’t really see why this would be considered dynamic programming or be part of the study plan.

So yes, there is sort of a recurrence we’d want, as demonstrated in the solution…

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # We can (implicitly) make a DAG and now we're just finding
        # some kind of reachability/length
        # This seems a bit too easy... isn't reachability here really simple?
        # We can do normal reachability, but isn't this sort of an integer?
        # We keep the max of our current run, and what we currently see.
        v = nums[0]
        for w in nums[1:]:
            if v <= 0:
                return False
            v -= 1
            v = max(v, w)
        return True

You can see my comments revealing my confusion. There’s no real “there”, there, in my opinion. I’m gathering this and all its friends from the study plan in this tag.

Interview Questions, Introductory

Robot Return to Origin (Leetcode 33)

I guess I have a lot of archives. This question is mainly about reasoning-by-cases, which is a way of handling a question that isn’t explicitly called out so well by the usual exercise batteries, in my experience (it’s neither a data structure nor an algorithm, not really).

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0
        for m in moves:
            if m == 'U': y += 1
            if m == 'D': y -= 1
            if m == 'R': x += 1
            if m == 'L': x -= 1
        return x == 0 and y == 0

Discussion

  1. The question is of course contrived, but I think it’s a good exercise in initial practice in “understanding a question” and translating that to a programming-amenable approach.
  2. The question does invite overthinking it, I would guess. Hopefully not everyone, but I can see a student panicking and starting to make an array-of-arrays. Knowing that sometimes you don’t have to do the hardest thing you can think of is very valuable in interviews and in practice!

I don’t know really know a general category to put this in. I’ll call it an introductory interview question, and collect any more here.