Interview Question: Insert switch to maximize time lightbulb spends on
Let's call the array of switches $a$ and let's add two elements to the array at the beginning we add 0 and at the end we add 100.
We now want to insert an element between two consecutive elements to maximise the length the bulb is turned on.
Let's make the following observations:


Note1 If a[i+1] = a[i] + 1, two consecutive elements have consecutive values. In this case we can't add anything between them.



Note2 The optimal value we add between $a[i]$ and $a[i + 1]$  for some $i$ is either equal to $a[i] + 1$ or to $a[i+1] - 1$.
Proof. Assuming the claim is not true, there is an optimal value strictly between $a[i]+1$ and $a[i+1]-1$. However, if the bulb is turned off in this interval we can push it back to $a[i]+1$ increasing the length of the turned on pulp in this interval without effecting the others. On the other hand if the bulb is turned on, we push it right to $a[i+1]-1$ increasing the length of turned on pulp in this interval.


So now we can loop over the array, and for each $i$, if $a[i] \neq a[i+1]-1$, we try to add the value $a[i]+1$ and the value $a[i+1]-1$, these are 2*(n-1) tries in total where n is the number of elements in the array (including 0 and n), which is linear in the number of the switches. We only have to show that we can do each step in constant time.
So let's say we already have the array, and we want to check the total value after adding a switch at position $k$. Let's pre-process the array and calculate and building the following 2 arrays in linear time:
 1. The length of light-on since the begin.
 2. The length of light-off from now till the end.
We can do that in two loops over the array using prefix-/suffix-sums.
Now when adding a switch between $a[i]$ and $a[i+1]$ with time stamp $k \in (a[i], a[i+1])$, the total value of on-light will be total value of on light from the begin to $i$ + the total off-light from $a[i+1]$ till the end + the total on-light in the interval between $a[i]$ and a[i+1] after adding $k$ (Which is either $k - a[i]$ or $a[i+1] - k$ depending on the original status of the interval).
Summary, In total we preprocess the array in $O(n)$, we do linear number of checks $O(n)$ and each in constant time in total we have $O(n) + O(n) * O(1) = O(n)$