Again yue four recruitment season every year, had the opportunity to obtain the chances of Microsoft’s written and program the ape should all know, the old company like Dui data structure and algorithm of beauty, Microsoft certainly is not exceptional also, personal feel to take an examination of the data structure for each applicant is fair, I this is Sue Microsoft institute, written examination of the is not difficult, is the most common data structure algorithm of naked, Let me write it down here and give you the solution.

1 Quicksort

Fast row should be the most web celebrity items, from school to clubs, from the back-end to the front-end to mobile terminal, will be asked, but no more than half, estimate expert to tear out the estimation can clear thinking on no more than half of the half, actually use two word, is double pointer + recursive partition, in each round of recursive find after each reference number sequence, Put anything less than the base number to its left, anything more than the base number to its right, and then recurse the array to its left and the array to its right. For example, array [2,3,1,5,6,4]:

    functionQuickSort (arr, begin, end) {// Exit recursionif(begin >= end)
               return; var l = begin; Var r = end; // Right pointer var temp = arr[begin]; // Exit the scan loop when the left and right Pointers meetwhile(l < r) {// The right pointer scans from right to left and stops when it hits the first number less than the base numberwhile(l < r && arr[r] >= temp) r --; // The left pointer scans from left to right and stops when it hits the first number larger than the reference numberwhile(l < r && arr[l] <= temp) l ++; / / stop exchange about an open position number [arr [l], arr [r]] = [arr [r], arr [l]]. } // Change the number where the base number and pointer meet [arr[begin], arr[l]] = [arr[l], arr[begin]]; QuickSort (arr, begin, L - 1); quickSort(arr, l + 1, end); } var arr = [2,3,4,1,5,6] quickSort(arr, 0, 5); console.log(arr)Copy the code

Think: why is the right pointer to scan first instead of the left pointer to scan first, everyone think about it haha, simulation will know.

Divergent thinking

I mentioned the left array, the right array, and the base number, where all values in the left array are less than the base number, and all values in the right array are greater than the base number, and quicksorting is a recursive process. If I make an analogy here, if I regard the base number as the root of the tree, the left array as the left child of the root, the right array as the right child of the root, I believe that children who have learned data structures know, it is not a BST. Ha ha indeed, in fact, you will find that the in-order traversal of BST is an ordered array, so the above quicksort process is a process of creating a binary search tree.

A Binary Search Tree is either an empty Tree or a Binary Tree with the following properties: if its left subtree is not empty, all nodes in the left subtree are less than the value of its root node; If its right subtree is not empty, then the value of all nodes in the right subtree is greater than the value of its root; Its left and right subtrees are also binary sorting trees.

So if I asked you how to create a BST, I’d be able to do it without the code:

     function vNode(value) {
           this.val = value;
           this.left = this.right = null;
       }
     function createBST(arr) {
           var len = arr.length;
           if(len < 1)
               return;
           var l = 0;
           var r = len - 1;
           var temp = arr[0];
           while(l < r) {
               while(l < r && arr[r] >= temp)
                   r --;
               while(l < r && arr[l] <= temp)
                   l ++;
               [arr[l], arr[r]] = [arr[r], arr[l]];
           }
           [arr[0], arr[l]] = [arr[l], arr[0]];
           var root = new vNode(arr[l]);
           root.left = createBST(arr.slice(0, l));
           root.right = createBST(arr.slice(l + 1));
           return root;
       }
Copy the code

Non-recursive binary tree in order traversal

I believe many people can write a binary tree recursive traversal: recursion through the left subtree, output the root node, recursion through the right subtree, three lines of code, done.

var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    while(root||stack.length ! = = 0) {while(root)
          {
              stack.push(root);
             root=root.left;
         }
         if(stack.length)
         {
             letp=stack[stack.length - 1]; res.push(p.val); stack.pop(); root = p.right; }}return res;
};
Copy the code

Old American company, the algorithm must pass ah. So, the road ahead is long; I see no ending