Microsoft Data Scientist Interview Questions & Answers

I would count factors of 5 instead of building the factorial. Every trailing zero needs a factor pair 2 × 5, and there are enough factors of 2 to pair with the factors of 5 in n!. I start with factor = 5 and repeatedly add n // factor to a running count. Then I multiply factor by 5 and continue until factor is greater than n. For n = 30, I get 6 + 1 = 7. This takes O(log_5 n) time and O(1) auxiliary space.

The input is one nonnegative integer n. We need to return how many zero digits appear continuously at the end of n!. We must not build n! because factorial values become extremely large. A trailing zero comes from a factor pair 2 × 5. In a factorial, there are enough factors of 2 to pair with every factor of 5, so the number of factors of 5 determines the answer. We count multiples of 5, then extra factors contributed by multiples of 25, 125, and higher powers of 5.

1. Can I assume n is always a nonnegative integer, as stated?
2. Should inputs outside the stated contract be ignored, as the problem allows?

The input is a nonnegative integer n. The output is one integer. It is the number of consecutive decimal zero digits at the end of n!. We do not need to handle values outside the stated input contract. We must not calculate n! itself. The function also does not mutate caller-owned data.

A decimal trailing zero comes from a factor of 10. A factor of 10 is 2 × 5. In n!, there are enough factors of 2 to pair with every factor of 5. Therefore, the number of trailing zeroes is determined by the total number of factors of 5.

We count n // 5 for the first factors of 5. We also count n // 25 because multiples of 25 contain an additional factor of 5. The same idea continues with 125, 625, and higher powers of 5.

Set count = 0 and factor = 5. The variable count stores the number of factors of 5 found from the powers already processed. The variable factor stores the current power of 5. At the beginning, no power has been processed, so count = 0 is correct.

Start with count = 0 and factor = 5.

For factor = 5, calculate 30 // 5 = 6. These six contributions come from 5, 10, 15, 20, 25, and 30. Add 6, so count changes from 0 to 6. Then multiply factor by 5, so factor becomes 25.

For factor = 25, calculate 30 // 25 = 1. The number 25 contributes one extra factor of 5. Add 1, so count changes from 6 to 7. Then factor becomes 125.

Now 125 > 30, so the loop stops. The factor 125 is not processed. We return 7.

The key invariant is that count equals the total number of factors of 5 contributed by every power of 5 processed so far. The first division counts one factor from every multiple of 5. The next division counts an additional factor from every multiple of 25. Higher powers work the same way. Because there are enough factors of 2 to pair with these factors of 5, this total is exactly the number of trailing zeroes.

The code starts count at 0 and factor at 5. While factor <= n, integer floor division n // factor tells us how many numbers contribute that power of 5. We add that value to count. Then factor *= 5 moves to the next power of 5. When factor becomes greater than n, there are no more contributing powers, so the function returns count.

The factor grows as 5, 25, 125, and so on. Therefore, the number of loop iterations is O(log_5 n). The function stores only two integer variables besides the input, so auxiliary space is O(1). For n = 0 or any n < 5, the loop never runs and the answer is 0. Powers of 5 need special attention because values such as 25 contribute more than one factor of 5 overall.

The key idea is to count how many factors of 5 appear in n!. A trailing decimal zero needs one factor of 2 and one factor of 5. There are enough factors of 2 to pair with every factor of 5 in the factorial, so the factors of 5 determine the answer. We add n // 5, n // 25, n // 125, and so on while the current power of 5 is at most n. The invariant is that count always equals the number of factors of 5 contributed by all powers processed so far. This avoids constructing the huge factorial value.

The time complexity is O(log_5 n). The factor starts at 5 and is multiplied by 5 after each loop, so the number of iterations grows logarithmically with n. For example, the factors progress as 5, 25, 125, and so on. The auxiliary space complexity is O(1). Auxiliary space means extra memory used by the algorithm. We only keep the running count and the current power of 5, so the extra memory does not grow with n.

1. Computing n! first and then counting its final zero digits. This does unnecessary work and ignores the required O(log_5 n) method. 2. Counting only n // 5 and forgetting extra factors from 25, 125, and higher powers of 5. 3. Treating factor = 125 as an executed iteration for n = 30. The loop has already stopped because 125 > 30. 4. Using normal division instead of integer floor division. 5. Claiming O(n) time even though the factor is multiplied by 5 after each iteration.

Explain why 25 must be counted twice overall before writing the loop. Once the interviewer sees that multiples of higher powers of 5 contribute extra factors, the repeated division by 5, 25, 125, and so on becomes easy to justify.

I would first find the rotation point with a modified binary search that handles duplicates. The rotation point is the descent index, or 0 when there is no descent. This splits the array into two sorted runs. I then use leftmost binary search on the earlier run first, followed by the second run only if needed. That guarantees the smallest rotated-input index for the target. Expected time is O(log n), worst-case time is O(n) with duplicates, and auxiliary space is O(1).

The array was originally sorted in nondecreasing order and may have been rotated. Duplicate values are allowed. We need to return two indices. The first is the rotation count: 0 when there is no descent, otherwise the smallest index r where nums[r] < nums[(r - 1) % n]. The second is the smallest index in the current rotated array whose value equals target, or -1 if the target is absent. The main idea is to find the rotation point first. That divides the array into two sorted runs, and each run can then be searched with binary search.

1. Should an empty array return (0, -1)? Yes. That is the required behavior.
2. If target appears multiple times, should I return its smallest index in the rotated input? Yes.
3. Can duplicates appear around the rotation boundary? Yes. The pivot search must handle that ambiguity.

nums contains 0 to 100,000 integers and is a rotation of a nondecreasing array. I must return (rotation_count, leftmost_target_index). For an empty input, I return (0, -1). For a nonempty array, the rotation count is 0 if no descent exists. Otherwise, it is the smallest index r where nums[r] < nums[(r - 1) % n]. The second result is the smallest rotated-input index containing target, or -1 if target is absent. I do not mutate nums and use only constant auxiliary space.

I keep an inclusive interval [lo, hi]. At each step, I compute mid = (lo + hi) // 2. If nums[mid] < nums[hi], the descent can be at mid or to its left, so I set hi = mid. If nums[mid] > nums[hi], the descent must be to the right of mid, so I set lo = mid + 1.

Duplicates need special handling. If nums[mid] == nums[hi], the comparison alone cannot tell which side contains the descent. Before shrinking the interval, I test whether nums[hi - 1] > nums[hi]. If so, hi itself is the descent, so I set lo = hi and stop the pivot search. Otherwise, hi is not the descent, so I safely shrink the interval with hi -= 1. Every update reduces the search interval or finishes the pivot search.

For nums = [4,5,5,6,6,1,2,3,3] and target = 3, start with lo = 0 and hi = 8.

Step 1: mid = 4. nums[4] = 6 and nums[8] = 3. Because 6 > 3, set lo = 5. The new state is lo = 5, hi = 8.

Step 2: mid = 6. nums[6] = 2 and nums[8] = 3. Because 2 < 3, set hi = 6. The new state is lo = 5, hi = 6.

Step 3: mid = 5. nums[5] = 1 and nums[6] = 2. Because 1 < 2, set hi = 5. The new state is lo = 5, hi = 5.

Now lo == hi, so the pivot search stops and r = 5. This is the descent because nums[5] = 1 < nums[4] = 6.

The pivot divides the array into the sorted runs [0, 5) and [5, 9). I use a lower-bound binary search to find the first target within a run.

I search [0, 5) first because every index there is smaller than every index in the second run. Target 3 is not present, so this search returns -1. I then search [5, 9). The first 3 in this run is at index 7, so the final result is (5, 7). This also verifies that nums[7] = 3 and no earlier rotated-input index contains 3.

During the pivot search, the true descent remains inside [lo, hi]. When nums[mid] is smaller or larger than nums[hi], sorted-order properties tell us which side cannot contain the descent. When the two values are equal, I first check whether hi itself is the descent. If it is not, removing that duplicate boundary position does not remove the true descent. After r is found, [0, r) and [r, n) are nondecreasing. Lower-bound search returns the first target in each run. Searching the lower-index run first guarantees the smallest rotated-input index overall.

The function first handles n ==

1. It then uses lo, hi, and mid to find r with the duplicate-aware pivot search. The nested leftmost(a, b) function performs lower-bound search on the half-open sorted interval [a, b). If nums[mid] < target, it moves lo to mid +
2. Otherwise, it keeps mid as a possible first target position by setting hi = mid. When the loop finishes, it verifies that the candidate really equals target. The main function searches [0, r) first and searches [r, n) only if the first run misses.

The expected running time is O(log n). The two target searches are binary searches, and the pivot search normally removes about half of the remaining interval. With many duplicates, however, nums[mid] may repeatedly equal nums[hi], forcing hi -= 1. Therefore the required worst-case running time is O(n). Auxiliary space is O(1).

Important edge cases are an empty array, a single-element array, an already sorted array, all-equal values, duplicates near the rotation boundary, an absent target, and multiple copies of target. For the question's already-sorted example nums = [1,2,3,4,5] with target = 3, there is no descent, so r = 0, and the leftmost target index is 2. The result is (0, 2).

The key insight is that the rotation point divides the array into two nondecreasing runs. The pivot-search invariant is that the true descent index, or index 0 when no descent exists, remains inside the inclusive interval [lo, hi]. Comparing nums[mid] with nums[hi] normally removes one side. Equal values are ambiguous, so the algorithm first checks whether hi itself is the descent; otherwise it removes only that duplicate boundary position with hi -= 1. After finding r, lower-bound search finds the first target in each sorted run. Searching [0, r) before [r, n) guarantees the smallest index in the rotated input.

Let n be the number of elements. The expected running time is O(log n). The pivot search usually reduces the search range quickly, and each target search is a standard binary search. With many duplicates, nums[mid] can equal nums[hi] repeatedly, so the pivot search may shrink hi by only one position at a time. That makes the worst-case running time O(n). The algorithm uses O(1) auxiliary space because it keeps only a fixed number of index variables and does not copy or modify nums.

One common mistake is treating any occurrence of the minimum value as the rotation count. The required rotation count is the descent index, or 0 if no descent exists. Another mistake is using ordinary rotated-array binary search without handling nums[mid] == nums[hi]. A candidate may also shrink hi before checking whether hi itself is the descent. During target search, ordinary binary search may return a later duplicate instead of the leftmost one. Finally, searching [r, n) before [0, r) can return a valid target index that is not the smallest rotated-input index.

State two invariants before coding: the real pivot remains inside [lo, hi], and leftmost(a, b) is a lower-bound search on one sorted run. Then explain why [0, r) is searched before [r, n). Those points make the duplicate handling and the leftmost-index requirement easy to justify.