Another removal-question. Another from the archive. Again the trickiness case is usually if the very-first or very-last element should be removed. I find this is another nice exercise giving the opportunity to think carefully about different cases happening inside a loop.
class Solution(object):
def removeElements(self, head, val):
# base case: remove from head until not equal to val
while head is not None and head.val == val:
head = head.next
if head is None:
return None
t = head
while t.next is not None:
if t.next.val == val:
t.next = t.next.next
else:
t = t.next
return head
This one strikes me as an interesting exercise exploring that common hurdle of mixing up array-indexes and array-values. This is a nontrivial “array search” problem.
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
for i in range(1, len(arr)-1):
if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
return i
Apparently, however, we’re obliged to use binary search and find it in log(N) time. The idea there is you check your index “locally”, and move right or left depending on which way the mountain says is “up”.
This is another question and solution from the archive. I think this is a nice educational question, but not a great interview question. It’s an OK interview question. I tagged this “vocabulary” because Hamming distance, and the tools (that I think are) the right ones to solve this are less things you gain insight about over time, and instead things you learn. Some observations:
The final punchline involves the XOR operator (^), which can be understood in a few ways. One way is seeing it as a symmetric-difference operator (or something like that), where the two integers are bitsets. So the result is a third bitset, that contains all those elements that were in exactly 1 of the two original bitsets. This sounds like what we want!
The missing piece is being able to count the 1s in that resulting set. The vocab to use here is “popcount”, which is either a hardware instruction or — if you’d like — a simple enough loop.
class Solution {
public:
int popcount(int x) {
int count = 0;
while (x) {
if (x % 2) {
count++;
}
x >>= 1;
}
return count;
}
int hammingDistance(int x, int y) {
return popcount(x^y);
}
};
This is from the archives, when I’d take more notes. Let me take those insights and preserve them here.
Despite the name, this question is really about linked lists. I’ll assume you’ve read the question and understood it. Now, a few observations:
We get to iterate through the list in the “nice” way: we can start adding digits immediately.
Built into the question is the problem of “carries” — we’re adding things, but each node can only hold the values 0-9, and so if there’s overflow we have to carry that.
This is a linked-list-merge-style question (see featured post here), so we should be mindful of the “end” of each of our two linked lists and how we should handle them. A moment’s thought also suggests that the carry value can also play a role here!
No negative numbers! The natural approach doesn’t suggest we’d introduce an erroneous leading zero or anything either. So it doesn’t seem there’s anything too tricky here.
Some insights:
We can treat the carry value as a “virtual” node: this tightens up our iterations and puts everything into one loop.
The approach I took was to create a new, third list. Another option (in practice; I assume the autograder would accept this too) would be to make this transformation destructive of one or both lists.
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* lastDigit = nullptr;
ListNode* result = nullptr;
bool carry = false;
while (l1 || l2 || carry) {
auto l1val = l1 ? l1->val : 0;
auto l2val = l2 ? l2->val : 0;
auto nextVal = l1val + l2val;
if (carry) {
nextVal++;
carry = false;
}
if (nextVal > 9) {
nextVal -= 10;
carry = true;
// assert(nextVal < 10 && nextVal >= 0)
}
if (!result) {
result = new ListNode(nextVal);
lastDigit = result;
} else {
lastDigit->next = new ListNode(nextVal);
lastDigit = lastDigit->next;
}
if (l1) { l1 = l1->next; }
if (l2) { l2 = l2->next; }
}
return result;
}
};
This is a nice exercise on slices, and also careful reasoning about string length comparisons. A good warmup. Javascript doesn’t have slices, not in this nice syntax.
This is a useful classic question about simplifying to what you need in the answer.
def valid_parentheses(string):
leftCount = 0
for c in string:
if c == '(':
leftCount += 1
elif c == ')':
if leftCount == 0:
return False
leftCount -= 1
return leftCount == 0
Introductory notes on computer science and programming
