7.13 Weilai approved the written examination in advance

13 Daodan topic selection 3 Multiple choice questions with indefinite items 3 Algorithm questions The length of the written test 90min

Single topic selection

1. Child threads under the same parent process , Can't share （）

Stack

2. When executed rm -f* when , Which file will not be deleted （）

Can't , Pick any one

3. In the worst case , The least time complexity of the following sorting methods is ( )

A． Bubble sort B． Quick sort C． Insertion sort  D． Heap sort

4.B Class private address range

【172.16.0.0-172.31.255.255】

5. For having n A binary tree of nodes , Its height is

Not sure

If it is a complete binary tree, it is 【log2 n】+1

6. stay SQL Use in UPDATE When modifying the data in the table , The clause that should be used is （）

SET

7. perform fork() Three times , How many sub processes are generated （）

8 individual , Reference resources

Three fork Function can create a total of how many processes ？_spark_g The blog of -CSDN Blog _fork Number of processes created

8. The pointer to the top of a stack is  hs （hs Is the address of the first element of the stack ） Insert a... Into the chain stack of  s  Node time , Should execute （）

9.  For linear tables （7,34,55,25,64,46,20,10） When hashing , If selected H（K）=K %9 As a hash function , Then the hash address is 1 The elements of （ ） individual

4 individual , Namely ：55,64,46,10.
H（K）= K%9, Divide by 9 The remainder of . Conflict due to address overlap , So hash storage , There are usually ways to resolve conflicts , Such as linear exploration method and so on

10. Conditions for Deadlock

1、 mutual exclusion ： A resource can only be used by one process at a time ;

2、 Request and hold conditions ： When a process is blocked by a request for resources , Keep the acquired resources ;

3、 Conditions of non deprivation : Resources obtained by the process , Before the end of use , Can't be forcibly deprived ;

4、 Loop wait condition : A circular waiting resource relationship is formed between several processes ;

In addition, there are some logical thinking problems

Indefinite multiple choice questions

1. Which of the following algorithms are stable sorting algorithms

Stable sorting algorithms are as follows 4 Kind of ：1、 Bubble sort ;2、 Insertion sort ;3、 Merge sort ;4、 Radix sorting .

2. In the multi table connection of the database , Table join algorithm contains

HASH JOIN      SORT MERGE JOIN Merge sort      NESTED LOOP Nested loop

3.list_b = copy.copy(a）,list_b[4][1]=5,list_b[1]='c'....

b = a Is a shallow copy ,b = list(a) and b = copy.cpoy(a) It's a deep copy .

Shallow copy ,a and b It points to an address . When b After change ,a It will change too. .

Deep copy ,a and b Points to two addresses , When b After change ,a Unaffected .

list2 = Lists.newArrayList(list1) It's a deep copy ,list3 = list1 Is a shallow copy .

Deep copy ,list2 After change ,list1 The value of .

Shallow copy ,list3 After change ,list1 The value of .

Deep copy ,pd.DataFrame.copy(user_info, deep=True), The original value changes , The copied new value will not change .

Shallow copy ,pd.DataFrame.copy(user_info, deep=False), The original value changes , The copied new value also changes .

Shallow copy ： user_info_copy2 = user_info

Algorithm problem

1. Count the number of times a number appears in the array

Sort the array , Turn into The finger of the sword Offer 53 - I. Look up numbers in the sort array I

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target-1);
    }

    public int helper(int[] nums, int target){
        int i=0, j=nums.length-1;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m]<=target) i=m+1;
            else j=m-1;
        }
        return j;
    }
}

2. Equal sum subset of array ACM Pattern

Given an array of integers nums And a positive integer k, Find out if it is possible to divide this array into k A non empty subset , The sum is equal to .

Input description ：

In the first line, enter an array

Enter a number on the second line

Output description ：

true perhaps false, It means that we can find non empty subsets that meet the conditions

May refer to

The finger of the sword Offer II 101. To divide into equal and subsets

knapsack problem

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        if(sum % 2 == 1){
            return false;
        }else {
            int target = sum / 2;
            int[][] dp = new int[nums.length + 1][target + 1];
            for (int i = 1; i <= nums.length; i++) {
                for (int j = 1; j <= target; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= nums[i - 1]) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
                    }
                }
            }
            return dp[nums.length][target] == target;
        }

    }
}

3. String expansion

Same as 1087. Curly bracket expansion

class Solution {
    List<String> res;

    public String[] expand(String S) {
        if (S.indexOf("{") < 0) {
            String[] res = {S};
            return res;
        }
        res = new ArrayList<>();
        backTrace(S, new StringBuilder(), 0);
        Collections.sort(res);
        return res.toArray(new String[res.size()]);
    }

    private void backTrace(String s, StringBuilder sb, int index) {

        if (index == s.length()) {
            res.add(sb.toString());
            return;
        }
        // encounter ’{‘ character 
        if (s.charAt(index) == '{') {
            int count = 0;
            // First calculate {} Length of content in count
            for (int j = index + 1; s.charAt(j) != '}'; j++) {
                count++;
            }
            // The next position to jump is index+count+2
            for (int j = index + 1; s.charAt(j) != '}'; j++) {
                char ch = s.charAt(j);
                if (ch != ','){
                    sb.append(ch);
                    backTrace(s, sb, index + count + 2);
                    sb.deleteCharAt(sb.length() - 1);
                }

            }
        } else {// Encountered other characters 
            sb.append(s.charAt(index));
            backTrace(s, sb, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}