Sliding Window Technique

The sliding window technique is used to eliminate travel waste (nested loop) within an array whenever you need to operate on subarrays of length K.

This technique allows you to convert a time complexity of O(N * K) to a single linear pass of O(N).

With a brute force solution, you’d use two loops, where the outer loop increments the subarray starting point, and the inner loop sequentially adds K elements to build the subarray. All of the inner loop’s work is lost/reset when the outer loop increments to the next starting element.

This results in unnecessary repetition: re-iterating over all of the prior subarray’s elements between the first and last; these are common between adjacent subarrays.

Instead of building a new subarray from each starting element, you can create the next subarray by performing two modifications to the current one:

  1. remove prior subarray’s first element from current subarray.
  2. add the next array element to current subarray.

This operation is a bit like an inchworm, inching along the parent array.

The basic sliding window

Goal: Given an array, get a list of averages for each subarray of length K.

  1. Take an array arr and a subarray length k.
  2. Init a container for your results, to store the averages of each subarray.
  3. Init an intermediary accumulator value sum, to store the sum of elements in the current subarray.
  4. Init a counter windowStart, representing the index of the start of the sliding window.
  5. For each element at index windowEnd in the array,
  6. } Add the element to the accumulator.
  7. } If we have a complete subarray (windowEnd is greater than k-1),
  8. } } Calculate and append result for this subarray.
  9. } } Remove the element at windowStart from sum.
  10. } } Increment windowStart to next index.
  11. Return results.

8 Wastes of Six Sigma, Applied to Software Engineering

Six Sigma is basically the study of efficiency in manufacturing.

They’ve codified a list of efficiency antipatterns called the 8 wastes.

These antipatterns are transferrable to the domain of software engineering and are useful to know in your own work.

The 8 wastes are:

  • Transportation/travel/motion waste: iterating over an entire collection rather than using a sliding window/two pointers, for example.
  • Defects: introducing bugs. Unexpected and unintended behavior.
  • Overproduction: building something you don’t actually need yet, and may not actually ever need. Also, using a data structure that takes more memory when a smaller one would suffice.
  • Waiting: using blocking code when it’s not necessary and asynchronous code is more appropriate.
  • Non-utilized talent: not reusing existing features/libraries.
  • Inventory: a backup of work/information that is sitting idle rather than being processed. Bottlenecks. Backpressure. Tech debt accumulation.
  • Extra processing: building to more restrictive constraints than actually called for. Not starting with MVP and extending on subsequent iterations.

I’ve combined travel/transportation and motion here; within software engineering these are the same, unless you want to consider the waste of commuting to an office instead of working remotely.

Achieving Deep Focus in an Open Office

Writing software is an activity that requires uninterrupted periods of deep focus.

You’re thinking procedurally through the logical implications of minute differences in abstract structures.

Each interruption, or a ‘context switch,’ represents significant wasted attentional overhead, as it can take 20-30 minutes to get back into your flow state.

I explained it once to a product manager friend of mine this way:

Imagine you’re a terrier, and you’ve been asked by a human to go into a gopher hole, and traverse an expansive network of gopher tunnels to eventually locate the gopher and bring it back to the surface.

Every time the human calls you back up to the surface to ask a question or adjust the parameters of their request, you then have to go back down into the tunnels, and reorient yourself. Where are you, again? Which tunnels have you already traversed? Which one were you in the middle of traversing? etc.

Silence is the Absolute Best Environment for Concentration

If you need to achieve a deep focus, the research shows that you really want a perfectly silent environment:

Cognitive processes improved with silence.

If you are going to listen to music, it’s preferable to listen to repetitive, non-stimulating music without language or vocals:

Hearing ‘meaningful’ sounds (like language) interferes with concentration.

Stimulative music hampers concentration.

Choosing whether to listen to music or not is within your control, but if you’re working in an open office environment, the conversations of your coworkers are omnipresent and not within your control.

So what can you do to mitigate this focus-threatening environmental factor?

A Software Engineer’s Best Friend

Enter these guys, right here:

3M X2A PELTOR X2 Earmuffs, 24 dB, Yellow/Black

3M X2A PELTOR X2 Earmuffs, 24 dB, Yellow/Black

Total focus for $13.

I have two pairs: one for home, and one for the office. I take them to the library with me. I even combine them with earplugs to even greater effect. They’ve been extremely useful for maintaining a deep focus in any environment.

If you’re working in an open office, I highly recommend giving them a shot.

If you do choose to listen to music, you can even tuck your earbuds inside to get a nice noise-canceling effect.

categories:

posted: