Two algorithm questions for Microsoft intern interview -- 20220119

Microsoft intern interview 2 Dao algorithm topic

Topic 1

The title is a bit similar to leetcode The series of topics of rotating array in https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/xuan-zhuan-shu-zu-cong-yi-dao-nan-ge-ge-dcv7a/, Two points of investigation . The interviewer transformed the question into V Type or inverted V Array find the subscript of the minimum value , The specific topics are as follows .

• subject ： In an array , Elements are ordered , At most one inflection point , Let's find the subscript of the smallest value in the array .
• Understand the topic ： The title is the interviewer's dictation , Some specific details can be added by yourself , My understanding is mainly divided into 4 Medium condition , Arrays are monotonically increasing 、 Monotonic decline 、 Concave V Array , Convex inverted V Array . During the communication between roommate and interview supervisor , The time complexity of making it find O(nlogn)——>O(n)——>O(logn), That is to say, we should finally use the dichotomy method to make it . My understanding is to judge the above first 4 Which of the two situations , And then deal with it , Monotone increasing 、 Monotonic decline 、 Convex inverted V Array this 3 In one case, you can get the answer directly , The key is concave V Array search . My approach is to use two points to approach the lowest point , If mid Return directly at the lowest point , If mid Downhill on the left , Then order left=mid+1 Continue to find . If mid Downhill on the right , Then order right=mid-1 Continue to find , until right be equal to left Return results .
• Code （Java）

public class Main {
    
    public static void main(String[] args) {
    
        int[] arr={
    4,2,3};
        int len=arr.length-1;
        if(len<3) System.out.println(arr[0]<arr[1]?0:1);
        // Judge the relationship between concavity and linearity 
        if(arr[1]>arr[0]&&arr[len]>arr[len-1]){
      // Monotone increasing 
            System.out.println(0);
        }else if(arr[1]<arr[0]&&arr[len]<arr[len-1]){
      // Monotonic decline 
            System.out.println(len);
        }else if(arr[1]>arr[0]&&arr[len]<arr[len-1]){
      // Convex 
            System.out.println(arr[0]<arr[len]?0:len);
        }else if(arr[1]<arr[0]&&arr[len]>arr[len-1]){
      // Concave 
            int left=0,right=len;
            while (left<right){
    
                int mid=left+(right-left)/2;
                if(arr[mid]<arr[mid-1]&&arr[mid]<arr[mid+1]){
    
                    System.out.println(mid);
                    return;
                }else if(arr[mid]<arr[mid-1]&&arr[mid]>arr[mid+1]){
    
                    left=mid+1;
                }else if(arr[mid]>arr[mid-1]&&arr[mid]<arr[mid+1]){
    
                    right=mid-1;
                }
            }
            System.out.println(left);
        }
    }
}

Topic two

• The maximum path in a binary tree and （leetcode The original question in https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/, difficulty hard）
  route It is defined as a path starting from any node in the tree , Along the parent node - Child node connection , A sequence that reaches any node . The same node in a path sequence At most once . This path At least one node , And it doesn't have to go through the root node .
  Path and Is the sum of the values of the nodes in the path .
  Give you the root node of a binary tree root , Back to its The maximum path and .
  
• Train of thought solution ：
  It mainly uses the bottom-up recursive method , Calculate the maximum contribution value of each node in the binary tree from bottom to top , And update the global maximum . To be specific , It is to find a path starting from the node in the subtree with the node as the root node , Make the sum of node values on the path maximum .
  For specific ideas, please refer to the problem solution ：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/
• Code （Java）：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    int maxSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
    
        // The recursive method , This recursive function returns 
        maxValue(root);
        return maxSum;
    }
    public int maxValue(TreeNode node){
    
        if(node==null){
    
            return 0;
        }
        // Recursively calculate the maximum contribution value of left and right child nodes , Only when the maximum contribution value is greater than  0  when , The corresponding child node will be selected 
        int leftValue=Math.max(maxValue(node.left),0);
        int rightValue=Math.max(maxValue(node.right),0);
        // The maximum path sum of a node depends on the value of the node 、 The maximum contribution value of the left and right child nodes of the node 
        int lmr=node.val+leftValue+rightValue;
        int ret=node.val+Math.max(leftValue,rightValue);
        maxSum=Math.max(maxSum,Math.max(lmr,ret));
        return ret;
    }
}