Maybe you and I have never met, but we may not have met. I am a head fish

preface

Fathead fish recently in sorting out some previous personal experience of the interview questions, found two very interesting topics, from ant Financial a certain online written test. How do I prevent repeated requests? Do you find similar scenarios in normal services? It seems that ant or the topic and the actual business combined. Sum of two numbers, add by subtraction.

How do I prevent repeated requests?

Problem: Business requirements often require only one request to prevent repeated requests from being triggered by repeated user clicks.

Pass the request method (which returns a promise after execution) and return a new method. When triggered consecutively, it is executed only once.

/ / sample
let count = 1;
let promiseFunction = () = >
  new Promise(rs= >
    window.setTimeout(() = >{ rs(count++); }));let firstFn = firstPromise(promiseFunction);
firstFn().then(console.log); / / 1
firstFn().then(console.log); / / 1
firstFn().then(console.log); / / 1
Copy the code

title

The firstFn callback will reuse the result of this request. An instance of the request can be stored first, and both success and failure can be sensed internally, so that it can be emptied again for the next request.


function firstPromise(promiseFunction) {
  let p = null;
  return function (. args) {
    // An instance of the request already exists, meaning that the request is in progress
    return p
      ? p
      // Otherwise send the request with p null in finally, and the next request can be re-initiated
      : (p = promiseFunction.apply(this, args).finally(() = > (p = null)));
  };
}

Copy the code

Test the

let count = 1;
let promiseFunction = () = >
  new Promise((rs) = >
    setTimeout(() = > {
      rs(count++);
    }, 1000));let firstFn = firstPromise(promiseFunction);
firstFn().then(console.log); / / 1
firstFn().then(console.log); / / 1
firstFn().then(console.log); / / 1

setTimeout(() = > {
  firstFn().then(console.log); / / 2
  firstFn().then(console.log); / / 2
  firstFn().then(console.log); / / 2
}, 3000);

Copy the code

As you can see, although we called firstFn6 times, the actual request only happened twice (because count only changed from 1 to 2). Congratulations, you passed the first ant pen test.

The sum of two Numbers

Sum of two numbers. A leetCode question, I didn’t think about it at that time, directly double cycle, the result can be imagined, the question is solved, but obviously not what the interviewer wanted…

Take a look at the title:

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

The sample1: Input: nums = [2.7.11.15], target = 9Output:0.1Because nums[0] + nums[1] = =9To return to the [0.1]. The sample2: Input: nums = [3.2.4], target = 6Output:1.2] example3: Input: nums = [3.3], target = 6Output:0.1] :2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109There will only be one order of valid answers: you can come up with a time complexity less than O(n^)2)?Copy the code

“Honest and honest” intuition

See this topic my heart secretly pleased, unexpectedly face so simple topic, 😋 hey hey. The double cycle comes out.

const twoSum = (nums, target) = > {
  const len = nums.length
  for (let i = 0; i < len; i++) {
    // The same element cannot be repeated in the answer so j = I + 1
    for (let j = i + 1; j < len ; j++) {
      // Find the answer, return
      if (nums[ i] + nums[ j ] === target) {
        return [ i, j ]
      }
    }
  }
}

Copy the code

Unexpectedly, I passed all the cases…

What are the drawbacks of naive intuitions?

Advanced: Can you think of an algorithm whose time complexity is less than O(n^2)? At the end of the question, it reminds us if there is an algorithm with a time complexity less than O(n^2), which means there is a better solution.

The interviewer will not be impressed by the two-layer loop (O(n^2)), so once you’ve actually written a two-layer, or even an n-layer loop, stop and think about space for time.

“Map” space for time

In this case, it can be done with a loop, as long as the addition to subtraction, the traversal of the value in an object sumCache store, traversal to see if there is a difference between the current value sumCache, there is a direct return that ends.

Try drawing a picture:

Input:,7,11,15 [2]

Step 1: Read 2, sumCache is empty, store 2 as key and index 0 as value in sumCache

Step 2: read 7, find 9-7 = 2,2 exists in sumCache, then return 0 and 1 index directly

The map method is much simpler than the for loop

const twoSum = (nums, target) = > {
  const len = nums.length
  const sumCache = {}

  for (let i = 0; i < len; i++) {
    const value = nums[ i ]
    // Calculate the difference
    const diff = target - value
    // If the difference already exists, return the corresponding index directly
    if (typeofsumCache[ diff ] ! = ='undefined') {
      return [ sumCache[ diff ], i ]
    } else {
      // Otherwise, save it
      sumCache[ value ] = i
    }
  }
}

Copy the code

The space for time method instantly reduces the time by more than half, sacrificing a little space, but this is definitely the answer the interviewer wants to see

At the end

I hope I can share practical, basic and advanced knowledge points with you all the time.

I look forward to your attention in nuggets: front end bighead fish, you can also find me in the public number: front end bighead fish.