フロントエンドの面接でよく聞かれるアルゴリズムに関する質問

ただし、フロントエンドでアルゴリズムに触れる機会はほとんどありません。ほとんどがインタラクティブな操作ですが、大手企業のインタビューから判断すると、アルゴリズムは依然として評価の一側面となっています。実際、データ構造とアルゴリズムを学ぶことは、エンジニアが問題を理解し分析するのに役立ちます。将来、より複雑な問題に直面した場合、これらの基本的な知識を蓄積することで、解決策をより最適化できるようになります。フロントエンドの面接でよく聞かれる質問をいくつか紹介します。

Q1 単語が回文であるかどうかを判断するにはどうすればいいですか?

回文とは、同じ単語や文が次のテキストで入れ替わったり逆になったりして、ループ効果を生み出す文です。これを回文またはループと呼びます。たとえば、mamam redivider などです。

多くの人がこのような質問を受けたとき、 for を使用して文字列のアルファベット順を逆にしてから一致させることを簡単に思いつくでしょう。実は、検討すべき重要な点は、リバースの実装です。実際、既製の関数を使用して文字列を配列に変換できます。このアイデアは非常に重要です。文字列操作をより自由に実行できるようになります。

関数checkPalindrom(str) { 
 
 str == str.split( '' ).reverse(). join ( '' )を返します。 
 
 }

Q2 整数配列から重複した値を削除する

たとえば、次のように入力します: [1,13,24,11,11,14,1,2]

出力: [1,13,24,11,14,2]

繰り返される要素 11 と 1 を削除する必要があります。

この質問は、フロントエンドの面接の多くの質問に出てきます。主に、オブジェクトの使用とスクリーニングのためのキーの使用を調べます。

 /**
 *ユニークな配列
**/
ユニーク=関数(arr) {
  ハッシュテーブルを {} とします。
  データ = [] とします。
 (i=0,l=arr.length;i<l;i++)の場合{
    if(!hashTable[arr[i]]) {
      ハッシュテーブル[arr[i]] = true ;
      データ.push(arr[i]);
    }
  }
データを返す
  
 } 
  
 module.exports =ユニーク;

Q3 文字列内の最も一般的な文字を数える

連続した英語の文字列が与えられたとき、最も多く出現する文字を見つけます。

入力: afjghdfraaaasdenas

出力:

繰り返し回数を数えるには、先ほど登場した繰り返し回数を計算するアルゴリズムが必要になります。

関数findMaxDuplicateChar(str) {
  str.length == 1の場合{
 strを返します。
  }
  charObj = {} とします。
 (i=0;i<str.length;i++)の場合{
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    }それ以外{
      charObj[str.charAt(i)] += 1;
    }
  }
  maxChar = ''とします。
      最大値 = 1;
 (var k in charObj)の場合{
    if(charObj[k] >= maxValue) {
      最大文字数 = k;
      最大値 = charObj[k];
    }
  }
 maxCharを返します。 
  
 } 
  
モジュール.exports = findMaxDuplicateChar;

Q4 ソートアルゴリズム

アルゴリズムに関する質問を受けた場合、そのほとんどは比較的オープンな質問であるはずです。アルゴリズムの実装を制限するものではありませんが、いくつかのアルゴリズムを習得する必要があります。したがって、比較的基本的で理解しやすく、記憶しやすいアルゴリズムであるバブルソートは、必ず記憶する必要があります。バブルソートアルゴリズムは、サイズを順番に比較し、小さい方と大きい方の位置を交換します。

関数bubbleSort(arr) {
 ( i = 0,l=arr.length;i<l-1;i++とします) {
 (j = i+1;j<l;j++)の場合
          もしarr[i]>arr[j]であれば
                tem = arr[i]とします。
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
    }
 arrを返します。
 }
モジュール.exports = bubbleSort;

バブルソート以外にも、挿入ソート、クイックソート、シェルソートなど、実は他にもたくさんのソートが存在します。各ソートアルゴリズムには独自の特性があります。すべてを習得する必要はありませんが、いくつかのアルゴリズムに精通している必要があります。たとえば、クイックソートは非常に効率的で、その基本原理は図のとおりです (wiki より)。

このアルゴリズムは、特定の要素の値を参照し、それより小さい値を左の配列に、それより大きい要素を右の配列に格納し、左の配列と右の配列に対して最後の操作を再帰的に実行し、マージされた配列、つまりソートされた配列を返します。

関数quickSort(arr) { 
  
    長さ<=1の場合{
 arrを返します。
    } 
  
    leftArr = [] とします。
    rightArr = [] とします。
    q = arr[0]とします。
 (i = 1,l=arr.length; i<l; i++)の場合{
        もしarr[i]>qの場合{
            右Arr.push(arr[i]);
        }それ以外{
            左Arr.push(arr[i]);
        }
    } 
  
 [].concat(quickSort(leftArr),[q],quickSort(rightArr))を返します。
 } 
  
モジュール.exports = クイックソート;

皆さんに学習リンクを紹介し、アニメーションを通じてアルゴリズムの実装を実演したいと思います。

HTML5 Canvas デモ: ソートアルゴリズム (http://math.hws.edu/eck/jsdemo/sortlab.html)

Q5 一時変数を使わずに2つの整数を交換する

入力 a = 2、b = 4 出力 a = 4、b = 2

このタイプの質問は非常に巧妙で、通常の方法から離れて考え、a と b を代入して使用する必要があります。

主に + – を使用して計算を実行します。たとえば、a = a + ( b – a) は実際には *** の a = b と同等です。

関数swap(a, b) {
  b = b - a;
  a = a + b;
  b = a - b;
 [a,b]を返します。
 } 
  
モジュールをエクスポートしてスワップします。

Q6 キャンバスを使用して有限フィボナッチ数列曲線を描くにはどうすればよいでしょうか?

シーケンスの長さは 9 に制限されます。

フィボナッチ数列は黄金比数列とも呼ばれ、0、1、1、2、3、5、8、13、21、34、... のような数列を指します。数学では、フィボナッチ数列は主に再帰呼び出しを調べます。定義は一般的に知られている

fibo[i] = fibo[i-1]+fibo[i-2];

フィボナッチ配列を生成する方法

関数getFibonacci(n) {
  var fibarr = [];
  var i = 0;
  i<n の間 {
    i<=1の場合{
      fibarr.push(i);
    }それ以外{
      fibarr.push(fibarr[i-1] + fibarr[i-2])
    }
    私は++;
  } 
  
 fibarrを返します。
 }

残りの作業は、キャンバスアーク法を使用して曲線を描くことです。

デモ (http://codepen.io/Jack_Pu/pen/LRaxZB)

Q7 たとえば、次の正の配列の *** 差を求めます。

入力[10,5,11,7,8,9]

出力6

これは、基本配列の最大値の検索をテストする質問です。明らかに、最大差は配列内の最大値と最小値の差でなければならないことはわかっています。

関数getMaxProfit(arr) { 
  
    var minPrice = arr[0];
    var 最大利益 = 0; 
  
 (var i = 0; i < arr.length; i++)の場合{
        var 現在の価格 = arr[i]; 
  
        minPrice = Math.min (minPrice, 現在の価格); 
  
        var potentialProfit = 現在の価格 - 最小価格; 
  
        最大利益 = Math.max (最大利益、潜在的利益);
    } 
  
 maxProfitを返します。
 }

Q8 指定された長さの文字列をランダムに生成する

指定された長さの文字列をランダムに生成するアルゴリズムを実装します。

例えば、長さが8の場合、出力は4ldkfg9jとなる。

関数ランダム文字列(n) {
  str = 'abcdefghijklmnopqrstuvwxyz9876543210'とします。
  tmp = ''とします。
      i = 0,
      l = 文字列の長さ;
 (i = 0; i < n; i++)の場合{
    tmp += str.charAt(Math.floor(Math.random() * l));
  }
 tmpを返します。
 } 
  
モジュール.exports = ランダム文字列;

Q9 getElementsByClassNameに似た関数を実装する

特定のクラスを含む特定の DOM ノードの下にあるすべての DOM ノードを検索する関数を自分で実装しますか? ネイティブシステムによって提供される getElementsByClassName querySelectorAll などのネイティブ DOM 検索関数を使用することはできません。

関数queryClassName(ノード、名前) {
  var starts = '(^|[ \n\r\t\f])' 、
       終了 = '([ \n\r\t\f]|$)' ;
  var 配列 = [],
        regex = 新しい RegExp(開始 +名前+ 終了)、
        要素 = node.getElementsByTagName( "*" )、
        長さ = 要素.長さ、
        i = 0,
        要素; 
  
    (i < 長さ) の間 {
        要素 = elements[i];
        if (regex.test(要素.className)) {
            配列.push(要素);
        } 
  
        私 += 1;
    } 
  
配列を返します。
 }

Q10 JSを使用して二分探索木を実装する

一般的に言えば、タスク全体を完了する可能性は比較的低いですが、タスクの理解といくつかの基本機能の実装に重点が置かれます。バイナリ検索ツリーは、バイナリ検索ツリーまたは順序付きバイナリツリーとも呼ばれ、次のプロパティを持つ空のツリーまたはバイナリツリーです。

いずれかのノードの左サブツリーが空でない場合、左サブツリー上のすべてのノードの値はルートノードの値よりも小さくなります。
いずれかのノードの右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はルートノードの値よりも大きくなります。
任意のノードの左と右のサブツリーもバイナリ検索ツリーです。
等しいキー値を持つノードはありません。他のデータ構造と比較したバイナリ検索ツリーの利点は、検索と挿入の時間計算量が低いことです。それはO(log n)です。二分探索木は、セット、マルチセット、連想配列などのより抽象的なデータ構造を構築するために使用される基本的なデータ構造です。

記述する際には、二分探索木の特性を十分に理解し、各ノードのデータ構造を最初に設定する必要があります。

クラスノード{
  コンストラクター(データ、左、右) {
    this.data = データ;
    this.left =左;
    this.right =右;
  }
 }

ツリーは、ルートノードから各子ノードへと段階的に拡張されるノードで構成されているため、ルートノードと、ノードの追加、検索、削除のメソッドを持つのが基本的な構造です。

クラス BinarySearchTree { 
  
  コンストラクタ() {
    this.root = null ;
  } 
  
挿入（データ）{
    n = new Node(data, null , null );とします。
    もし (!this.root) {
 this.root = nを返します。
    }
    currentNode を this.root とします。
    親をnullにします。
    一方（1）{
      親 = 現在のノード;
      データ < currentNode.data の場合 {
        現在のノード =現在のノード.left;
        (currentNode === null )の場合{
          親.left = n ;
          壊す;
        }
      }それ以外{
        現在のノード =現在のノード.right;
        (currentNode === null )の場合{
          親の右端= n;
          壊す;
        }
      }
    }
  } 
  
  削除(データ) {
    this.root = this.removeNode(this.root、データ)
  } 
  
  ノードを削除します(ノード、データ) {
    if (ノード == null ) {
戻る ヌル;
    } 
  
    if (データ == node.data) {
      //子ノードなし
      （ノード.left == null && ノード.right == null ）の場合{
戻る ヌル;
      }
      （ノード.left == null ）の場合{
 node.rightを返します。
      }
      （ノード.right == null ）の場合{
 node.leftを返します。
      } 
  
      getSmallest =関数(ノード) {
        if( node.left === null && node.right == null ) {
ノードを返します。
        }
        if( node.left != null ) {
 node.leftを返します。
        }
        if( node.right !== null ) {
 getSmallest ( node.right )を返します。
        } 
  
      }
      temNode = getSmallest( node.right ) とします。
      ノードデータ = temNode.data;
      temNode からデータを削除します。
ノードを返します。 
  
    }そうでない場合 (データ < node.data) {
      ノードを左から左にドラッグします。
ノードを返します。
    }それ以外{
      ノードを右から削除します。
ノードを返します。
    }
  } 
  
  find(データ) {
    var現在の値= this.root;
    while (現在値!= null ) {
      if (データ ==現在の.data) {
        壊す;
      }
      if (データ <現在の.data) {
 current = current . left ;
      }それ以外{
現在=現在.右 
      }
    }
戻る 現在の.data;
  } 
  
 } 
  
モジュールをエクスポートします。