Technical Interview Questions: Sliding Window Technique

Technical Interview Questions - Sliding Window Technique

The first round of technical interviews is generally algorithm-based questions. You may be asked to solve a most common problem through a technical assessment tool such as Hackerrank or Codility, or maybe within a screening interview while other developers are watching you. As a developer who participated in many interviews during the past years, I hear what you’re saying and sharing the same feelings! It can be tough to show our best qualities in a limited time with certain circumstances. 

That’s why I decided to write a tutorial series about the most common Interview questions to improve our problem-solving skills. I will go with the Sliding Window algorithm with detailed steps in the first round.

What is Sliding Window Technique/ Algorithm?

The Sliding window is a problem-solving technique that runs over a given data in Array or String form.  It is so-called because it will slide on data to satisfy certain conditions by expanding or diminishing subsets. 

This technique helps you convert nested loops to a single loop, reducing time complexity from O(n²) to O(n).

Question forms you may face;

  • Longest Repeating Character Replacement
  • Find the largest sum of k consecutive elements
  • Longest Substring Without Repeating Characters
  • Fruit Into Baskets
  • Subarray Product Less Than K
  • Permutation in String
  • Find duplicates in any form

Sliding Window Technique In Action

Question: You are given a fixed camera at 45° in a forest with a list of predefined trees. Find the best angle to view/picture the maximum of trees.

Given data

// List of tree locations
trees = {12, 73, 77, 94, 128, 50, 26, 170};  
//camera angle
k= 45

We are supposed to find the maximum trees for the given angle.

To find the consecutive max trees for 45°, we need to sort all trees. 

Sorted tree array;

sortedTrees = {12, 26, 50, 73, 77, 94, 128, 170};

We need to track the right border and left border of the window.

leftBorder=0; 
rightBorder=0;
maxTreeCountForGivenAngle=0;

In every iteration check the below cases; 

  • if the angle between the right border and the left border is smaller than the given angle then increase the right border index.
  • if the angle between the right border and the left border is greater than the given angle then increase the left border index.
122650737794128170

The window has a red border and a sea-green background. The current sum of the trees is 2 and the angle is 26-12+1 = 15° so we can expand the right side of the window by increasing the right border.

122650737794128170

This window evaluates the max tree count to 3 since the angle is 50-12+1 = 39° and still less than 45°. Continue to expand the window.

Expanding the right side only will exceed the angle so increasing the left border also to make sure we diminish the window at the same time in case it is needed; This basically will slide the window by 1.

122650737794128170

The angle is 48° so we need to diminish the window still to be within given angle limits.  

122650737794128170

Now increase right border to expand window;

122650737794128170

Max tree count is 3 and angle is 28°, keep increasing right border;

122650737794128170

The angle is 45° and the max tree count is 4, the highest so far. Make sure you save this and compare it to the other iterations. 

Slide the window by 1 in the next iteration;

122650737794128170

Diminish window from the left border as the angle is 56° higher than 45°

122650737794128170

Angle is 52° and still higher than 45°, keep diminish window by increasing left border;

122650737794128170

Finally, the current angle is 35° less than 45° again, keep expand the window’s right side. As the expansion will make the angle higher than 45°;

Slide window by increasing both the right and left border indexes in the same iteration.

122650737794128170

We managed to find the maximum tree count for the 45° without using nested loops with a linear complexity.

You can check various sliding window problems and solutions from different perspectives from leetcode.com

If you are a Java developer; I highly recommend the recent post I shared Common Mistakes Every Beginner Java Programmer Makes which highlights some common mistakes during interviews.

2 thoughts on "Technical Interview Questions: Sliding Window Technique"

Leave a Reply

Your email address will not be published.

#

“Exceptionly was such a fast and efficient process. Complete game changer for hiring remote.”

Liam Martin
Co-Founder at TimeDoctor

#

“Great service, outstanding speed, stunning quality.”

Andy Tryba
CEO at Gigster

Is Exceptionly an outsourcing business?

No. We encourage our clients to do direct hires. We provide payroll consultancy and services in a 100% transparent way if our clients are new to remote hiring.

Is Exceptionly a database of candidates?

Not really, data is only a small part of our business. While we own over 2 million publicly available software engineer data evaluated, our power lies in hands-on testing and engineer-to-engineer technical interviews.

Is Exceptionly expensive?

Exceptionly is more cost-efficient than any other serious competitor who owns a decent technical testing funnel. If you compare Exceptionly with HR agencies who only do resume screening before endorsement, yes, it is expensive.

Who is the founder of Exceptionly?

Sinan Ata is the founder of Exceptionly, who previously built two global technical talent acquisition enginess and tested over 2.5 million software engineers in his career.

Still have questions? Contact us.

Ready to meet top-notch engineers?

Let's get your talent pipelines up and running!

HIRE WITH EXCEPTIONLY

No hidden fees.