Tag Archives: c++

Interview Questions, Strings

Longest Substring Without Repeating Characters (Leetcode)

Another from the archives. In my old notes I tried a few different approaches. Ultimately this one feels a little “brute-force-y”, here is what I got:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int l = std::max(res, 1); l + i <= s.size(); l++) {
                std::bitset<256> seen;
                bool bad = false;
                for (int j = i; j < i + l; j++) {
                    if (seen.test(s[j])) {
                        bad = true;
                        break;
                    }
                    seen.set(s[j]);
                }
                if (!bad) {
                    res = std::max(res, l);
                } else {
                    // i i our starting point, a longer l won't help here.
                    break;
                }
            }
        }
        return res;
    }
};

Thoughts

  1. The “length” iteration (how i, l, j indexes interact) is pretty interesting. Comes up rarely, but in thinking about many collections of substrings.
  2. The final “break” (with the comment above it) is necessary.
  3. I wanted to port this to Python—my old archives are in C++. But it lacks a bitset class, and its range loops aren’t amenable to the length-based iteration (or at least, I don’t know how to adapt them).

I doubt my solution is the right one. What is the official Leetcode solution? Oh I like it! Does this make the cut as an interview question? I don’t know, I am skeptical. More string questions here.

Arrays, Interview Questions

Intersection of Two Arrays (Leetcode)

Another from the archives. This is actually something I like as an interview question, so I suppose maybe that means I should change my interview question. I suppose candidates need to know what a set is, but given the domains I work in I think that’s a fair requirement. This question is to take two arrays of integers, and return their set-intersection.

I think a very reasonable approach is to immediately sort the input. After that, as we build the result vector, we can think about the invariants that are maintained: the result vector is in sorted order, and so the “unique-ification” we need to do can follow naturally from that.

Nevermind also the invariants that guide the overall merge-sort-esque loop iterations. We can reason about how we make forward progress.

Code Solution

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(begin(nums1), end(nums1));
        sort(begin(nums2), end(nums2));
        vector<int> result;
        
        int i = 0;
        int j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                if (result.size() == 0) result.push_back(nums1[i]);
                else if (*(result.rbegin()) != nums1[i]) result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        
        return result;
    }
};

Extensions

I think some reasonable extensions are: what if the vector-of-ints is sort of a set datatype with certain invariants (e.g., that the contents are always sorted). This suggests the results should also be sorted, but we sort of get that “for free” with the natural approach. I like discussing possible trade-offs of performance depending on the input size.

This is, in my opinion, a nice exercise on loops and arrays. More can be found here.

Greedy Algorithm, Interview Questions

Array Partition (Leetcode)

Another from the archives! This one is interesting because, at least to me, I found it was more an algorithmic/math question, rather than a straight application or exploration of a data structure.

By that same token I’m not sure I’d use this as an interview question, nor as a homework question. It’s building the confidence that we have the “right” pairing is the tricky part, I think. When I’ve seen students confront an algorithm that ultimately has a greedy solution, they often intuit the greedy algorithm as an approach, but won’t have the rigor to be able to be confident it’s the right one (or they don’t even know it might not be the right one, and an, e.g., dynamic programming solution is called-for). I don’t know how I feel about students “accidentally” getting the right answer: when Leetcode finally lights up all green for them, I’d imagine they view that as a certificate that they fully understand the answer. Maybe not!

Anyways, I fortunately recorded my original thoughts in a comment, which I’ve extracted here:

Approach and Solution

The algorithmic question here is somewhat interesting! We don’t just want to pair the largest half with the smallest half. Is the intuition that we want to pair the “closest” values? The max value cannot be chosen, as it’d be paired with something smaller. But the second-max value can be chosen if we pair it with the max. Do we always want to do that?

That’s suggesting a greedy algorithm. Find the “largest-still-pickable” value. Let’s say there’s some other, better pairing. Then we have at least two pairs (a, b) (c, d) where a < b, c < d, but also b > c. In that case we have: a, c, b, d (or a, c, d, b, or c, a, b, d, or c, a, d, b) in terms of sorting by order.

Presumably what I want to say is that swapping b, c here would increase the result. Let’s see: previously we’d have a + c, but by swapping we get either b or d (both of which are bigger than c), and either a or c.

WLOG can we say that a < c? Probably! I think that’s enough to go on here.

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        if (nums.size() == 0) { return 0; }
        std::sort(begin(nums), end(nums));
        assert(nums.size() % 2 == 0);
        int result = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            result += nums[i];
        }
        return result;
    }
};

I think this is the first “greedy algorithm” solution I’ve posted here. So it trailblazes a new category, here.

Interview Questions, Linked List

Split Linked List In Parts (Leetcode)

This question feels a bit contrived, but a way to explore a lot of challenges with linked lists. I have an answer to this in my archive.

So, full disclosure: most of my archive is actually in C++, rather than the more approachable Python or (occasionally, for my students) Javascript. I think I do have a few earlier solutions in C++, but this is the first “big” one, I guess? Previously I’ve also been translating my archive, but as my external obligations are increasing I have to drop some features. So this is in C++. Also from the archive: a lot of my notes were intentionally embedded in comments.

class Solution {
public:
    // it seems we need to know the length, to begin with.
    // and then we do an interesting partition sort of algorithm.
    // the value of the LL nodes play no part in this?
    // Sure...
    int len(ListNode* r) {
        int l = 0;
        while (r) {
            l++;
            r = r->next;
        }
        return l;
    }
    // OK, and then we divide things into K.
    // Ah that things differ by less than 1 is sort of an interesting constraint.
    // So if k > l, that's sort of easy: we know we need length 1.
    // if k < l < 2k, then we know we'll have a few length-2, and the rest length 1.
    // So this suggests some kind of modulo. k > 0, so that's safe.
    // l / k is the length of the shorter lists.
    // l % k is how many lists need one more.
    // This feels like an obsfucated remainder check. But actually it's OK. I kind of like
    // this partition problem.
    
    ListNode* peel(ListNode** root, int l) {
        // forgot a deref!
        if (!(*root)) return nullptr; // assert l == 1?
        ListNode* p = *root;
        ListNode* t = *root;
        // Here I'm being a bit risky. Not sure if there's a weird case
        // where if we improperly peel we'll null-deref. I think if everything
        // goes right we'll only ever be "off by one", which is effectively
        // captured by our basecase there.
        //
        // In other words, this is not a very robust peel! Relies on qualities
        // of the list guaranteed by the caller.
        for (int i = 0; i < l-1; ++i) {
            t = t->next;
        }
        *root = t->next;
        t->next = nullptr;
        return p;
    }
    
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        const int l = len(root);
        int shortLength = l / k;
        int listsWithExtras = l % k;
        // next up: helper function "peel";
        vector<ListNode*> result;
        ListNode* r = root;
        for (int i = 0; i < k; ++i) {
            int n = shortLength;
            if (i < listsWithExtras) {
                n++;
            }
            result.push_back(peel(&r, n));
        }
        return result;
    }
};

Notes

A few notable things:

  • The len helper, it seems to be required? It’s unfortunate that we can’t do this online.
  • I’m having second thoughts about my implementation of “peel”. I think I can avoid the pointer-to-pointer, though for C that’s not a huge deal. Maybe inlining the function would make that clearer.
  • You can see my careful-ish reasoning about how to calculate each peel length, I think that’s an interesting comment.

As always, all linked list things are collected here.