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 with 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.
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
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.
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
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.
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
The angle is 48° so we need to diminish the window still to be within given angle limits.
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
Now increase right border to expand window;
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
Max tree count is 3 and angle is 28°, keep increasing right border;
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
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;
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
Diminish window from the left border as the angle is 56° higher than 45°
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
Angle is 52° and still higher than 45°, keep diminish window by increasing left border;
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
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.
| 12 | 26 | 50 | 73 | 77 | 94 | 128 | 170 |
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.
English 
Arabic
2 Responses