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.,
Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1; partition = 5
Output: 3 -> 1 -> 2 -> 5 -> 5 -> 8 -> 10
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: 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 l
and 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 l
and r
pointers and getting rid of l
altogether (really it was just renamed to d
).
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 -> 3
and p = 5
.d -> 1 -> 2 ...
r == node(1)
r
while loop puts r = node(5)
r.next
so we enter the loopc = node(8)
c >= p
doesn't make sense because c
is a node and p
is a value. So we would go up to change our code above to say c.val >= p
.c.val == 8
so the if condition is true and we set r = node(8)
.r.next == node(3)
so we go in the while loopc = node(3)
c.val < p
so we go to the else conditionr.next
is set to None
t
is set to node(1)
d
to c
so we have d -> 3
c
to t so we have d -> 3 -> 1 -> 2 -> 5 -> 8
r.next == None
d.next
or 3 -> 1 -> 2 -> 5 -> 8
, which satisfies the solution.partition(None, 5)
d
, that is the dummy head is pointing to Noner
is then set to None
r
is None
r.next
would dereference None
which is not allowed.while r and r.next
r == None
d.next
or 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
while r and r.next:
if r.next >= p:
r = r.next
else:
r = r.next.next
So again, the worst we can do is start at the beginning of the list and go to the end so this loop is O(N)
. So total time complexity is O(N)
.
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 O(1)
.