Home Web Front-end JS Tutorial Interview Kit: Arrays - Sliding window.

Interview Kit: Arrays - Sliding window.

Sep 05, 2024 pm 05:35 PM

It's All About Patterns!

Once you learn the patterns, everything starts to feel a bit easier! If you're like me, you probably don't like tech interviews, and I don't blame you—they can be tough.

Array problems are some of the most common ones you’ll encounter in interviews. These problems often involve working with natural arrays:

const arr = [1, 2, 3, 4, 5];
Copy after login

And string problems, which are essentially arrays of characters:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']


Copy after login

One of the most common patterns for solving array problems is the sliding window.

Sliding Window Pattern

The sliding window pattern involves two pointers that move in the same direction—like a window sliding across the array.

When to Use It

Use the sliding window pattern when you need to find a sub-array or sub-string that satisfies a certain condition, such as being the minimum, maximum, longest, or shortest.

Rule 1: If you need to find a sub-array or sub-string and the data structure is an array or string, consider using the sliding window pattern.

Simple Example

Here’s a basic example to introduce the concept of pointers in a sliding window:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);
Copy after login

Note that the left (L) and right (R) pointers don’t have to move at the same time, but they must move in the same direction.

Interview Kit: Arrays - Sliding window.

The right pointer will never be lower than the left pointer.

Let’s explore this concept with a real interview problem.

Real-World Problem: Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest sub-string without repeating characters.

Keywords: sub-string, longest (maximum)

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}
Copy after login

Don’t worry if this looks complicated—we’ll go through it bit by bit.

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5
Copy after login

The core of this problem is finding the longest sub-string without repeating characters.

Initial Window: Size 0

At the start, both the left (L) and right (R) pointers are at the same place:

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER
Copy after login
h e l l o w o r l d 
^
^
L
R
Copy after login

And we have an empty hash (object):

let hash = {};
Copy after login

What’s great about objects? They store unique keys, which is exactly what we need to solve this problem. We’ll use hash to track all the characters we’ve visited and check if we’ve seen the current character before (to detect duplicates).

By looking at the string, we can visually tell that world is the longest substring without repeating characters:

h e l l o w o r l d 
          ^        ^   
          L        R
Copy after login

This has a length of 5. So, how do we get there?

Let’s break it down step by step:

Initial State

hash = {}

h e l l o w o r l d 
^
^
L
R
Copy after login

Iteration 1:

On each iteration, we add the character under the R pointer to the hash map and increment:

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);
Copy after login
Copy after login

Currently, there are no repeating characters in our window (h and e):

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R
Copy after login

Iteration 2:

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R
Copy after login

Now, we have a new window: hel.

Iteration 3:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R
Copy after login

Here’s where it gets interesting: we already have l in our hash, and R is pointing to another l in the string. This is where our if statement comes in:

if (hash[str[right]] !== undefined)
Copy after login

If our hash contains the letter R is pointing to, we’ve found a duplicate! The previous window (hel) is our longest so far.

So, what do we do next? We shrink the window from the left by moving the L pointer up since we’ve already processed the left substring. But how far do we move L?

left = hash[str[right]] + 1;
Copy after login

We move L to just after the duplicate:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R
Copy after login

We still add our duplicate to the hash, so L will now have an index of 3.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);
Copy after login
Copy after login

New State: Iteration 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R
Copy after login

Iterations 4 to 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R
Copy after login

When R points to another duplicate (o), we move L to just after the first o:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R
Copy after login

We continue until we encounter another duplicate l:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R
Copy after login

But notice it's outside the current window! starting from w,

Rule 3: Ignore Processed sub-x

Anything outside the current window is irrelevant—we’ve already processed it. The key code to manage this is:

if (hash[str[right]] !== undefined && hash[str[right]] >= left)
Copy after login

This condition ensures we only care about characters within the current window, filtering out any noise.

hash[str[right]] >= left
Copy after login

We focus on anything bigger or equal to the left pointer

Final Iteration:

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R
Copy after login

I know this was detailed, but breaking problems down into smaller patterns or rules is the easiest way to master them.

In Summary:

  • Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
  • Rule 2: If you need to find unique or non-repeating elements, think hash maps.
  • Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

  • Break down the problem and make it verbose using a small subset.
  • When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Copy after login

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

The above is the detailed content of Interview Kit: Arrays - Sliding window.. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial
1664
14
PHP Tutorial
1267
29
C# Tutorial
1239
24
Demystifying JavaScript: What It Does and Why It Matters Demystifying JavaScript: What It Does and Why It Matters Apr 09, 2025 am 12:07 AM

JavaScript is the cornerstone of modern web development, and its main functions include event-driven programming, dynamic content generation and asynchronous programming. 1) Event-driven programming allows web pages to change dynamically according to user operations. 2) Dynamic content generation allows page content to be adjusted according to conditions. 3) Asynchronous programming ensures that the user interface is not blocked. JavaScript is widely used in web interaction, single-page application and server-side development, greatly improving the flexibility of user experience and cross-platform development.

The Evolution of JavaScript: Current Trends and Future Prospects The Evolution of JavaScript: Current Trends and Future Prospects Apr 10, 2025 am 09:33 AM

The latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.

JavaScript Engines: Comparing Implementations JavaScript Engines: Comparing Implementations Apr 13, 2025 am 12:05 AM

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

Python vs. JavaScript: The Learning Curve and Ease of Use Python vs. JavaScript: The Learning Curve and Ease of Use Apr 16, 2025 am 12:12 AM

Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.

JavaScript: Exploring the Versatility of a Web Language JavaScript: Exploring the Versatility of a Web Language Apr 11, 2025 am 12:01 AM

JavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.

How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration) How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration) Apr 11, 2025 am 08:22 AM

This article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base

Building a Multi-Tenant SaaS Application with Next.js (Backend Integration) Building a Multi-Tenant SaaS Application with Next.js (Backend Integration) Apr 11, 2025 am 08:23 AM

I built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing

From C/C   to JavaScript: How It All Works From C/C to JavaScript: How It All Works Apr 14, 2025 am 12:05 AM

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.

See all articles