Reviewed: 9 October 2026. The exercise, trace and suggested explanations below are original illustrative preparation material. They are not a company question bank, a timed interview result or evidence of hiring success. Follow the actual invitation's language, tool and assistance rules.
Agree on the problem before writing code
A useful coding answer connects the requested behaviour to the implementation and tests. A plausible algorithm can still answer the wrong problem if it drops duplicates, changes an input or silently accepts invalid data. Start by asking what the function receives, what it must return and which assumptions you may rely on.
Microsoft's technical interviewing guidance recommends clarifying a problem, planning a solution, coding and testing. That is employer-scoped preparation guidance. It does not establish the rules, duration or assessment criteria for an Indian employer's particular interview. Use the practice below to make your reasoning inspectable, then adapt to the actual brief.
For a real interview, clarify whether you should validate input or assume it is valid; whether you may use a library; and whether a runnable implementation is required. Say when you are making an assumption rather than presenting it as something the interviewer agreed.
Original exercise: merge two sorted integer lists
The supplied practice brief asks for a function that receives two Python lists of integers in nondecreasing order and returns a new list containing every input element in nondecreasing order. Repeated values must remain repeated. Negative values are allowed. Empty lists are allowed. Neither input may be modified. For equal values, take the next element from the left list first.
The exercise adds an explicit validation requirement: accept only the exact built-in list container and exact built-in int elements, excluding subclasses of either. Reject a Boolean element or a list that is not already nondecreasing. These are exercise requirements, not universal requirements for every merge problem. In Python, a Boolean is accepted by some integer checks, so use an exact type check here.
With left [-2, 1, 1, 7] and right [-2, 1, 3], the required result is [-2, -2, 1, 1, 1, 3, 7]. There are seven input elements and seven output elements. Converting the inputs to a set would lose multiplicity and violate this contract.
An opening explanation could be: “I will first check both lists against the supplied contract. Then I will compare the two next unconsumed values, append the smaller one and advance only its pointer. On equality I will advance the left pointer. When one list is exhausted, I will append the other list's remaining values into the new output.”
Trace the pointers before implementing
Use i for the left position and j for the right position. Both start at zero. The output starts empty.
| Step | Choice and resulting state |
|---|---|
| 1 | Compare left −2 with right −2; choose left on equality. Output [-2]; i = 1, j = 0. |
| 2 | Compare left 1 with right −2; choose right. Output [-2, -2]; i = 1, j = 1. |
| 3 | Compare left 1 with right 1; choose left. Output [-2, -2, 1]; i = 2, j = 1. |
| 4 | Compare the next left 1 with right 1; choose left. Output [-2, -2, 1, 1]; i = 3, j = 1. |
| 5 | Compare left 7 with right 1; choose right. Output [-2, -2, 1, 1, 1]; i = 3, j = 2. |
| 6 | Compare left 7 with right 3; choose right. Output [-2, -2, 1, 1, 1, 3]; i = 3, j = 3. |
| 7 | Right is exhausted. Append the remaining left 7. Output [-2, -2, 1, 1, 1, 3, 7]. |
Every step consumes an element; no step consumes both equal elements at once. With plain integer values, equality does not reveal which list supplied a value in the final output. The stated left-first rule is visible in the control flow and trace. It would need a different test representation if the elements carried identities.
Complete Python implementation
def _check(xs):
if type(xs) != list:
raise TypeError
p = None
for x in xs:
if type(x) != int:
raise TypeError
seen = p != None
if seen and x < p:
raise ValueError
p = x
def merge_sorted(a, b):
_check(a)
_check(b)
r = []
i = 0
j = 0
n = len(a)
m = len(b)
while i < n and j < m:
if a[i] <= b[j]:
r.append(a[i])
i += 1
else:
r.append(b[j])
j += 1
while i < n:
r.append(a[i])
i += 1
while j < m:
r.append(b[j])
j += 1
return r
In the code, a and b denote the left and right inputs; r is the new result. The function reads from each input and appends to that separate result. Even when one input is empty, it constructs a new output rather than returning the other input itself. The validation pass reads both inputs before the merge begins, so an invalid tail is checked even if an early comparison would not reach it immediately.
Explain why this produces the requested order
At each comparison, the next value in a sorted input is its smallest remaining value. Choosing the smaller of the two next values therefore chooses a smallest remaining value across both lists. Everything already appended is no larger than that choice. Advancing only the selected pointer also preserves every unconsumed occurrence.
Once one input is exhausted, the other input's tail is already ordered and follows the values already chosen. Appending that tail completes the output. This reasoning depends on the nondecreasing input condition; it would not establish correctness for an arbitrary unsorted list.
If the input lengths are n and m, validation and merging each take linear passes. Under a bounded-size integer comparison assumption, total time is O(n + m). The result stores n + m elements, so output space is O(n + m), with O(1) additional pointer state. Python integers can be arbitrarily large; treating comparison cost as constant is an explicit simplifying assumption for this analysis, not a claim about every possible bit length.
Test the contract, not just the main example
The expected results below can be checked independently of the implementation's explanation.
| Case | Inputs and expected result |
|---|---|
| Both empty | [] and [] produce a new []. |
| One empty | [] and [-3, 2] produce [-3, 2], without returning the right input object. |
| All equal | [1, 1] and [1] produce [1, 1, 1]. |
| Negatives | [-5, -1] and [-4, 0] produce [-5, -4, -1, 0]. |
| Unsorted input | [2, 1] and [] raise ValueError. |
| Boolean element | [True] and [] raise TypeError. |
| Wrong container | (1, 2) and [] raise TypeError. |
For the complete seven-element fixture, save copies of both inputs before calling the function, compare them afterwards, and check that the output is a different object. Nonmutation is part of the requested behaviour, not something established merely because the printed result looks correct.
An unsorted integer tail such as [1, 3, 2] must also be rejected. Include a non-integer late in a list to check that validation covers all elements. If a test fails, report the actual failing case and correct the implementation or explanation; do not turn an unexecuted test plan into a claim that tests passed.
Handle a changed requirement explicitly
Suppose the interviewer changes the brief to “return each distinct integer once.” The seven-element result above is now wrong: the new expected result would be [-2, 1, 3, 7]. A correct response is to acknowledge the changed multiplicity requirement and explain a revised approach before editing the function. You could suppress a selected value when it equals the last appended value. Review empty output handling and duplicate runs in both inputs.
If arbitrary unsorted lists become allowed, the sorted-input reasoning no longer applies directly. Discuss whether sorting copies is permitted and how it changes the cost. Do not silently sort the original lists when the nonmutation requirement still applies. These follow-ups test how you update a contract and justification, rather than whether you memorised one answer.
Practise an explanation you can support
Rehearse the contract, one trace, correctness reasoning and boundary tests aloud. Distinguish code you executed from cases you merely planned. If using this exercise in a project discussion, do not imply it was a production feature or a company interview you attended.
For a service-level discussion involving concurrent requests and retries, use the separate system design interview guide. For structuring a truthful behavioural example around your own contribution, see the STAR method guide. Those topics complement coding practice but do not replace algorithm correctness.
Frequently asked questions
Must I validate inputs in every coding interview?
Clarify the actual brief. This exercise explicitly requires validation. If an interviewer guarantees valid sorted integer inputs, explain that assumption and focus the implementation accordingly.
Can I use sorting instead of two pointers?
It can produce an ordered result when used appropriately, but explain whether it preserves multiplicity and inputs, and compare its cost with using the supplied sorted order. Tool permissions and the requested learning objective still matter.
Does solving this exercise prove interview readiness?
It shows preparation on a bounded problem. Readiness for a particular role also depends on the actual topics, communication and constraints in its assessment. No selection probability or hiring outcome follows from this example.