Interview Question: The Principle of Implementing the Array Flat Method

During an interview some time ago, the interviewer asked: how to implement the flat method? At that time, the implementation was not perfect, and later on, I found that there were not a few interviewers who asked to write the flat method for arrays by hand. These include Xiaomi, Meituan, Drip, Shopee, etc.

Handwriting the flat method is a very basic interview question, usually in the written test or the first round of interviews, mainly to investigate the basic handwriting code ability. Today, we will relearn the array flat method from understanding flat features to implementing flat and then catching the interviewer’s series of questions.

Javascript array flat method

A code summary Array.prototype.flat() feature

const animals = ["🐷", ["🐶", "🐂"], ["🐎", ["🐑", ["🐲"]], "🐛"]];
// default "flatten" once if no parameters are passed
animals.flat();
// ["🐷", "🐶", "🐂", "🐎", ["🐑", ["🐲"]], "🐛"]
// pass in an integer parameter, the number of "flattenings"
animals.flat(2);
// ["🐷", "🐶", "🐂", "🐎", "🐑", ["🐲"], "🐛"]
// The Infinity keyword is converted to a one-dimensional array when used as an argument, no matter how many levels of nesting
animals.flat(Infinity);
// ["🐷", "🐶", "🐂", "🐎", "🐑", "🐲", "🐛"]
// passing in an integer <= 0 will return the original array, not "flattened"
animals.flat(0);
animals.flat(-10);
// ["🐷", ["🐶", "🐂"], ["🐎", ["🐑", ["🐲"]], "🐛"]];
// If the original array has empty space, the flat() method will skip the empty space.
["🐷", "🐶", "🐂", "🐎",,].flat();
// ["🐷", "🐶", "🐂", "🐎"]

Summary of Array.prototype.flat() features

• Array.prototype.flat() is used to "flatten" a nested array into a one-dimensional array. This method returns a new array, with no effect on the original data.
• When no arguments are passed, the default is to “flatten” one level, and an integer can be passed to indicate the number of levels you want to “flatten”.
• Passing an integer <=0 will return the original array without "flattening" it.
• When the Infinity keyword is used as an argument, it will be converted to a one-dimensional array, regardless of the number of nested layers
• If the original array has empty space, Array.prototype.flat() will skip the empty space.

The interviewer gets to the heart of the matter

First question: Implementing a simple array flattening flat function

First, we’ll spend a little time exploring how to implement a simple array flattening flat function, detailing the various implementation options, and then try to catch the interviewer's barrage of questions.

implementation idea

The idea is very simple: implement a flat function with an array flat function, all we have to do is find the elements in the array that are of type array and expand them. This is the key idea behind implementing the flat method.

With the idea in mind, we need to address the difficulties that need to be overcome to implement it.

• The first one to solve is traversing every element of the array;
• The second problem is to determine if the element is an array;
• The third thing to solve is to expand the elements of the array by one layer;

Solutions for Iterating through Arrays

There are many ways to iterate through an array and obtain its elements, including and not limited to the following.

• for loop
• for.... .of
• for... .in
• forEach()
• entries()
• keys()
• values()
• reduce()
• map()

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }];
// There are too many ways to iterate through an array, so this article will only enumerate the common ones
// for loop
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}
// for...of
for (let value of arr) {
  console.log(value);
}
// for...in
for (let i in arr) {
  console.log(arr[i]);
}
// forEach loop
arr.forEach(value => {
  console.log(value);
});
// entries（）
for (let [index, value] of arr.entries()) {
  console.log(value);
}
// keys()
for (let index of arr.keys()) {
  console.log(arr[index]);
}
// values()
for (let value of arr.values()) {
  console.log(value);
}
// reduce()
arr.reduce((pre, cur) => {
  console.log(cur);
}, []);
// map()
arr.map(value => console.log(value));

Any method that can iterate through an array to fetch every element in the array is a viable solution.

A solution to determining if an element is an array

• instanceof
• constructor
• Object.prototype.toString
• isArray

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }];
arr instanceof Array
// true
arr.constructor === Array
// true
Object.prototype.toString.call(arr) === '[object Array]'
// true
Array.isArray(arr)
// true

Description.

• The instanceof operator assumes that there is only one global environment. If the page contains multiple frames with multiple global environments, and if you pass an array from one frame to another, the incoming array will have its own separate constructor from the array created natively in the second frame. (So it will be inaccurate in this case)
• The typeof operator takes the type of the array and returns object.
• Since constructor can be overridden, it is not guaranteed to be an array.

const str = 'abc'; 
str.constructor = Array; 
str.constructor === Array  // true

Scheme to expand the elements of an array by one level

• Expansion operator + concat

The concat() method is used to merge two or more arrays, and adding the expansion operator to the concatenation will expand the array by one layer. See the following code for details.

• concat + apply

mainly uses apply to bind the scope with the second argument being an array or array-like object, where the array elements are passed as separate arguments to the func function. That is, during the call to the apply function, the incoming arrays are passed one by one into the function to be executed, which is equivalent to a layer of expansion of the array.

• toString + split

The toString + split method is not recommended, because manipulating strings is a dangerous thing to do. If all the elements in the array are numbers, toString + split works, and it's a one-step process.

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }];
// Expansion operator + concat
[].concat(...arr)
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "Bouncing iron eggs" }];
// concat + apply
[].concat.apply([], arr);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "Bouncing iron eggs" }];
// toString  + split
const arr2 =[1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]]]
arr2.toString().split(',').map(v=>parseInt(v))
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3]

After summarizing the three major difficulties to be solved, then we can very easily implement a version of the flat function.

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }];
// concat + recursive
function flat(arr) {
  let arrResult = [];
  arr.forEach(item => {
    if (Array.isArray(item)) {
      arrResult = arrResult.concat(arguments.callee(item));   
      // recursive
      // or use the extended operator
      // arrResult.push(...arguments.callee(item));
    } else {
      arrResult.push(item);
    }
  });
  return arrResult;
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "Bouncing iron eggs" }];

By this point, congratulations on successfully getting the interviewer’s basic approval of your ability to tear code by hand 🎉. But the interviewer will often go beyond that and will continue to look at the interviewer’s various abilities.

Question 2: Implement the flat function with reduce

I’ve seen a lot of interviewers who like to name names and ask interviewers to implement the flat function directly with reduce. Want to know why? We'll see why later in the article when we consider the case of empty arrays. In fact, the idea is the same.

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }]
// First use reduce to expand a layer
arr.reduce((pre, cur) => pre.concat(cur), []);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "Bouncing iron eggs" }];
// Expanding a layer with reduce + recursion
const flat = arr => {
  return arr.reduce((pre, cur) => {
    return pre.concat(Array.isArray(cur) ? flat(cur) : cur);
  }, []);
};
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "Bouncing iron eggs" }];

Question 3: Use the stack idea to implement the flat function

// Stack Ideas
function flat(arr) {
  const result = []; 
  const stack = [].concat(arr);  
  // Copy the array elements to the stack, direct assignment will change the original array
  // If the stack is not empty, the loop traverses
  while (stack.length !== 0) {
    const val = stack.pop(); 
    if (Array.isArray(val)) {
      stack.push(...val); 
      // If the array is on the stack again, and a layer is expanded
    } else {
      result.unshift(val); 
      // If it's not an array, take it out and put it in the result array
    }
  }
  return result;
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }]
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "Bouncing iron eggs" }];

Fourth question: control the number of “leveling” layers by passing in integer parameters

// reduce + recursive
function flat(arr, num = 1) {
  return num > 0
    ? arr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? flat(cur, num - 1) : cur),
        []
      )
    : arr.slice();
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }]
flat(arr, Infinity);
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "Bouncing iron eggs" }];

Question 5: Use Generator to implement the flat function

function* flat(arr, num) {
  if (num === undefined) num = 1;
  for (const item of arr) {
    if (Array.isArray(item) && num > 0) {   // num > 0
      yield* flat(item, num - 1);
    } else {
      yield item;
    }
  }
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }]
// When the Generator function is called, it does not execute and returns not the result of the function run, but a pointer object to the internal state.
// That is, the Iterator Object. So we have to use the extension operator once to get the result
[...flat(arr, Infinity)]    
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "Bouncing iron eggs" }];

Question 6: Implementing rewriting the flat function on a prototype chain

Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = this.concat();    
      // Get an array of calls to the fakeFlat function
  while (num > 0) {           
    if (arr.some(x => Array.isArray(x))) {
      arr = [].concat.apply([], arr);	
      // If there are still array elements in the array and num > 0, continue to expand the array by one level 
    } else {
      break; 
      // Stops the loop if there are no array elements in the array and regardless of whether num is still greater than 0.
    }
    num--;
  }
  return arr;
};
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "Bouncing iron eggs" }]
arr.fakeFlat(Infinity)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "Bouncing iron eggs" }];

Question 7: Consider the case of an empty array

We know from the flat feature we summarized at the beginning that the flat function executes by skipping nulls, and most ES5 array methods that handle nulls choose to skip them, including: forEach(), filter(), reduce(), every() and some().

So we can use the above methods to implement the flat skip-empty feature

// reduce + recursive
Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = [].concat(this);
  return num > 0
    ? arr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? cur.fakeFlat(--num) : cur),
        []
      )
    : arr.slice();
};
const arr = [1, [3, 4], , ,];
arr.fakeFlat()
// [1, 3, 4]
// foEach + recursive
Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = [];
  this.forEach(item => {
    if (Array.isArray(item)) {
      arr = arr.concat(item.fakeFlat(--num));
    } else {
      arr.push(item);
    }
  });
  return arr;
};
const arr = [1, [3, 4], , ,];
arr.fakeFlat()
// [1, 3, 4]

Extended Reading: Since the rules for handling empty spaces are very inconsistent, it is recommended to avoid them.

ES5 is very inconsistent when it comes to the handling of empty spaces and ignores them in most cases.

• forEach(), filter(), reduce(), every() and some() all skip the empty space.
• map() will skip the empty space, but will keep the value.
• join() and toString() treat the null bit as undefined, while undefined and null are treated as empty strings.

ES6 explicitly converts null bits to undefined.

• entries(), keys(), values(), find() and findIndex() will treat empty bits as undefined.
• The for... . of loops will iterate over the empty space.
• fill() treats the empty space as a normal array position.
• copyWithin() will copy the empty bit along with it.
• The extension operator (... ) will also convert the empty space to undefined.
• The Array.from method takes the empty bits of the array and converts them to undefined.

Summary

The interviewer is looking at a topic of writing code, but it’s not just about writing code, there are various knowledge points and code boundary cases. Although in most cases, the interviewer will not be so perverted as to flat implementation to chase the interviewer continuously and tear several versions, but the interviewer will ask to write a more perfect version of the code based on the version you wrote is a common thing. Only if we sink our teeth into the basics will we respond comfortably no matter how much the interviewer asks. The implementation of flat is definitely not the only version listed in the article, knocking out your own code is the best progress, write your own version in the comment section!

Follow me if you find it useful ❤

More content at plainenglish.io