During a technical interview, the way you work towards your solution is often more important than the binary result of solving the problem or not. There are a number of good ways to show and communicate your work as you work through an algorithm problem. The UMPIRE method is another way to state the best practices that underlie the most successful approaches in a catchy name.
UMPIRE stands for:
Let's practice using the UMPIRE technique on the following problem.
Partition: Write code to partition a linked list around a value x, such that all nodes less than x come before equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.
One of the best ways to understand a problem is to come up with test cases. E.g.,
Coming up with good test cases can be an art, but I typically like to cover one happy path or an average case. And any interesting edge cases. This can be tricky as it depends on the problem.
Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1; partition = 5 Output: 3 -> 1 -> 2 -> 5 -> 5 -> 8 -> 10
Input: 1; partition = 1 Output: 1
Remember that the interview is a dialog, so understanding the problem is best done as a dialog as well. Asking questions, like
are very useful components to the dialog and are helpful for this problem.
Linked List problems are usually some of the easiest to spot and so matching this to the Linked List category is a good choice. So we know we would like to employ Pointer Bookkeeping during the algorithm planning. So let's list out all the things that we might consider and our belief of match Likely, Neutral, Unlikely.
This is the harder part for Linked List problems as dealing with pointer management is where solving this problem can go awry. So we take advantage of our matching of Pointer Bookkeeping tool and perhaps a two-pointer strategy and dummy-head to move forward to visualize the solution.
In this pointer visualization, I started with the following assumption that I would have one pointer
l at the end of the left side and
r pointer at the last known right side position. Then
c or really just
r.next would test if the next node is greater than or less than the partition value
p. In the case labeled 1, value of
c is >=
p so in that case the
r pointer moves forward.
I then fast forward the bookkeeping visualization, to the next position where that condition doesn't hold. This is situation 2, in this case, we need to remove the
c node from its position and place it somewhere on the left which in the written code is after the
l node, but we recognize that we need to introduce a temporary pointer
t so that we can move the
c node into position without orphaning the rest of the list.
Since this seems to handle all possible cases, I fast forward the visualization to deal with the end case. This situation 3 is when
r reaches the end or
r.next. So most likely the whole algorithm will be in a while loop to forward
r until this condition fails.
Finally, I revisit the initial condition of setting up the
r pointer, in situation 4. Here, however, I realize that it would have been easier to utilize the dummy-head technique because there is a chance that the very first node could be >=
p, thus I would not be able to get the initial invariant I setup in the beginning with
l pointing to the last node on the left side. So situation with situation 4, I create a
d node or dummy-head that points to the actual head of the list and this is a great place to start
l. However, now that we have the dummy-head and combined with the knowledge that we don't care about the ordering of the nodes within the left or right partitions we realize we could alter the algorithm to not use an
l pointer and simply place the
c nodes after the dummy to simplify the algorithm.
If our plan stage was successful, we should be able to implement the code by simply glueing the plan together while filling out the details of our language specific implementation. I like to write my implementation out in layers, where the first layer is me writing basic setup code and then talking to the pieces of the plan.
def partition(list, p): d = ListNode('dummy') d.next = list # 4: Initialize r pointer to first value >= p # 3: Loop until we run out of unknown values # 1: Handle right side value # 2: Handle left side value ## Pop off the dummy return d.next
Then, I proceed to implement the separate parts of the plan:
def partition(list, p): d = ListNode('dummy') d.next = list # 4: Initialize r pointer to first value >= p r = d.next while r and r.val < p: r = r.next # 3: Loop until we run out of unkown values while r.next: c = r.next if c >= p: # 1: Handle right side value r = c else: # 2: Handle left side value r.next = c.next t = d.next d.next = c c.next = t ## Pop off the dummy return d.next
As we can see, the mix of understanding the ordering requirements of the algorithm and the dummy-head technique we were able to further simplify our problem by removing the need for the situation 4 or initialization of our
r pointers and getting rid of
l altogether (really it was just renamed to
The very important, but too often skimped on, review stage is next. Unfortunately, most interviewees just skim through the code to say yeah that looks right, but that IS NOT what review means. It means go through it as if you are debugging it, assuming there is a bug. If you do you woudn't just be saying yep, thats what I'd meant to write. Instead, you would be bringing the big debugging "guns". Watchlist of variables and stepping through the code line by line are the typical tools of choice to go for this stage.
list = 1 -> 2 -> 5 -> 8 -> 3and
p = 5.
d -> 1 -> 2 ...
r == node(1)
rwhile loop puts
r = node(5)
r.nextso we enter the loop
c = node(8)
c >= pdoesn't make sense because
cis a node and
pis a value. So we would go up to change our code above to say
c.val >= p.
c.val == 8so the if condition is true and we set
r = node(8).
r.next == node(3)so we go in the while loop
c = node(3)
c.val < pso we go to the else condition
r.nextis set to
tis set to
cso we have
d -> 3
cto t so we have
d -> 3 -> 1 -> 2 -> 5 -> 8
r.next == None
3 -> 1 -> 2 -> 5 -> 8, which satisfies the solution.
d, that is the dummy head is pointing to None
ris then set to
Nonewhich is not allowed.
while r and r.next
r == None
None, which satisfies the constraints of our algorithm.
After our review of our algorithm we have the following code:
def partition(list, p): d = ListNode('dummy') d.next = list # 4: Initialize r pointer to first value >= p r = d.next while r and r.val < p: r = r.next # 3: Loop until we run out of unkown values while r and r.next: c = r.next if c.val >= p: # 1: Handle right side value r = c else: # 2: Handle left side value r.next = c.next t = d.next d.next = c c.next = t ## Pop off the dummy return d.next
The last step of the UMPIRE strategy is to discuss the pros and cons of your algorithm with your interviewer. An algorithm much like a good interview is not amenable to correct/incorrect label, instead there are often things to discuss about what you like about your algorithm or code and what you would like to change depending on conditions, inputs, expectations, the business, etc.
A great place to start this conversation and is almost always required is to discuss the asymptotic performance of the algorithm. Let's evaluate our algorithm. To do this, let's start with any loop statements. We have two loop statements. The first, is iterating the
r pointer until it reaches the first node on the right side. In the best case, this wouldn't go further than the first position, in the worst case we would go to the end of the list without finding a right node. So this loop has
O(N) time complexity where
N is the length of the list.
Now we go to the second loop. Again, we are iterating
r and if we ignore the rest of the contents of the loop outside of how
r is manipulated we get
So again, the worst we can do is start at the beginning of the list and go to the end so this loop is
while r and r.next: if r.next >= p: r = r.next else: r = r.next.next
O(N). So total time complexity is
Next, we move on to space complexity. We see that we are only requiring a constant number of pointers in addition to the list, so our space complexity is