Contact us: Youdao Technical Team assistant: ydtech01 / email: [email protected]

Welcome to the graduating students

Come to the 2022 Varsity Games

And now it’s coming right in your face

Netease Youdao team!

(Portal: HR.netease)

Their canteen is delicious

They never sneak in

Today, they also brought

10 written programming questions

It is said that all the students do right

They all got the offer smoothly!

Class, please start your bugs

Oh don’t

Show!!!!

First, warm up exercise

1.1 Finding duplicate numbers

Given an array nums containing n+1 integers, all of which are between 1 and n (both 1 and N), we know that there is at least one duplicate integer. Assuming that NUMS has only one duplicate integer, find the duplicate number.

  • Difficulty: one star
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 256MB for C/C++ and 512MB for other languages
  • 64bit IO Format: %lld天安门事件

Sample:

  • Input:,3,4,2,2 [1]
  • Returns: 2
import java.util.*;


public class Solution {
    /** * The class name, method name, and parameter name in the code have been specified, do not modify, directly return the value specified by the method ** return repeated numbers **@param Nums int A one-dimensional array of integers *@return Int * / integer
    public int duplicate (int[] nums) {
        // write code here
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if(nums[i] <= mid) { cnt++; }}if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1; ans = mid; }}returnans; }}Copy the code

1.2 Triangular area

Input the coordinates of the three points and output the area of the triangle formed by the three points. (The results are rounded to three decimal points.)

  • Difficulty: one star
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 256MB for C/C++ and 512MB for other languages
  • Special Judge, 64bit IO Format: %lld
  • Knowledge: Calculate geometry

Sample:

  • Input: 12, -70, 95, 91, -72, 35
  • Output: 11119.500
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
    double x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    double xa = (x1 - x2);
    double ya = (y1 - y2);
    double xb = (x3 - x2);
    double yb = (y3 - y2);
    
    float area = fabs((xa * yb - ya * xb) / 2.0);
    printf("%.3f", area);
    
    return 0;
}
Copy the code

2. Stretch

2.1 Decomposition of natural numbers

A natural number can be decomposed into several natural numbers multiplied together. Now, given a given natural number n, ask for the minimum value of the sum of the natural numbers for each decomposition.

  • Difficulty: two stars
  • Time limit: 5 seconds for C/C++, 10 seconds for other languages
  • Space limit: 32MB for C/C++, 64M for other languages
  • 64bit IO Format: %lld

Sample:

  • Input: 6
  • Returns: 5
  • Note: 6 is decomposed into 2 * 3, so the smallest sum is 2+3=5
# # the class name, method name and parameter name in the code have been specified, do not modify, directly return the value specified by the method # # get the minimum value of the sum of decomposed natural numbers # # param n int integer natural number n # #returnInt # integerclass Solution:
    def getMinSum(self , n) :if n <= 1:
            return n
        temp = int(n / 2)
        whiletemp ! =0:
            if n % temp == 0:
                if temp == 1 and n / temp == n:
                    print(n)
                    return n
                else:
                    return self.getMinSum(n / temp) + self.getMinSum(temp)
            else:
                temp -= 1
Copy the code

2.2 Restoring the Number of Exceptions

There’s a one-dimensional array of integers called a fuzzyArray, and it stores n numbers from 1 to N, but it’s out of order; It’s going to be negative 1 in one place. Use the optimal space and time complexity to find the location and original value of this exception number.

  • Difficulty: two stars
  • Time limit: 5 seconds for C/C++, 10 seconds for other languages
  • Space limit: 256 MB for C/C++, 512 MB for other languages
  • 64bit IO Format: %lld
  • Knowledge: test development, array

Sample:

  • Input: [2, -1, 3]
  • Returns: [1, 1]
  • [2, -1, 3] [2, -1, 3] [1, 1] [1, 1] [2, -1, 3] [1, 1] [2, -1, 3] [1, 1]
# # function: find the position of the exception and the original value # # param fuzzyArray intreturnInt a one-dimensional array of integers #class Solution:
    def fuzzyNumber(self , fuzzyArray) :flag = 1
        pos = 0
        sumnumber = 0
        index = 0
        for item in fuzzyArray:
            if item == -1:
                if flag == 0:
                    return [-1, -1]
                flag = 0
                pos = index
            else:
                sumnumber += item
            index += 1
        orisum = (index + 1) * index / 2
        orinumber = orisum - sumnumber
        return [pos, orinumber]
Copy the code

2.3 Average waiting time of orders

There is a milk tea shop, which can only process one order at a time. There is an order list (ORDERS) (two-dimensional array) of customers, and each order contains two elements: the first element indicates the arrival time of the order. Orders in the Orders are arranged in non-decreasing order of arrival time; The second element shows how long it took to make the order; When a customer’s order arrives, the milk tea shop will start making the milk tea for that order as soon as it is free. Every customer will wait for the milk tea shop to complete his order. Milk tea shops will process orders in strict order. Please return the average waiting time of all customers in the order list. If the error is within 10-5 of the standard answer, it is considered correct.

  • Difficulty: two stars
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 256MB for C/C++ and 512MB for other languages
  • Special Judge, 64bit IO Format: %lld
  • Knowledge: Simulation

Sample:

  • Input: [[1, 2], [1, 3], [4]]
  • Returns: 4.00000
  • Description:

When the first order arrives at time 1, the milk tea shop immediately starts to process the order and completes it at time 3. The waiting time for the first customer is 3-1=2.

The second order arrives at time 1, the milk tea shop is processing the first order, the first order is completed at time 3 and begins to process order 2, the second order is completed at time 6, the second customer needs to wait for time 6-1=5;

The third order arrives at time 4, the milk tea shop is processing the second order, the second order is completed at time 6 and begins to process order 3, the third order is completed at time 9, the second customer needs to wait for time is 9-4=5; So the average is 2 plus 5 plus 5 over 3 is 4

import java.util.*;


public class Solution {
    /** * The class name, method name and parameter name in the code have been specified, do not modify, directly return the value specified by the method ** *@param Orders int A two-dimensional array of integers *@return Double floating point */
    public double averageWaitingTime (int[][] orders) {
        int currentTime=0;
         long timeSum=0;// Pay attention to crossing the line
         for(int[] a:orders){            
            if(a[0]>currentTime){
                timeSum+=a[1];
                currentTime=a[0]+a[1];
            }else{
                timeSum+=a[1]+currentTime-a[0];
                currentTime=a[1]+currentTime; }}return(double)timeSum/orders.length; }}Copy the code

Three, the whole body exercise

3.1 Numbers and Letters

Given a character array containing only numbers and uppercase letters, find the longest substring such that it contains the same number of numbers and letters. The substring must be a contiguous part of the original array. Return the length of the substring, or 0 if there is no such substring.

  • Difficulty: Samsung
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 256 MB for C/C++, 512 MB for other languages
  • 64bit IO Format: %lld
  • Knowledge: String processing

Sample:

  • Input: [A, A, A]
  • Return: 0
import java.util.*;


public class Solution {
    /** * The class name, method name and parameter name in the code have been specified, do not modify, directly return the value specified by the method ** *@param STR char one-dimensional array of characters *@return Int * / integer
    public int findLongestSubarray (char[] str) {
         Map<Integer,Integer> map = new HashMap<>();
         map.put(0, -1);
         int prefixSum = 0;
         int longest = 0;
         for (int i = 0; i < str.length; i++) { char c = str[i]; prefixSum += Character.isDigit(c)? -1:1;
            if(! map.containsKey(prefixSum)){ map.put(prefixSum,i); }else{
                // i-map.get(prefixSum) == i-left+1
                if(i-map.get(prefixSum)>longest){ longest = i-map.get(prefixSum); }}}returnlongest; }}Copy the code

3.2 Splicing of sticks

Mr. Wang, the carpenter, had sticks of different lengths. He wanted to know if they could be put together to form a square. Please write a program to solve xiao Wang’s doubts.

Description:

  1. A single stick can be used as one side of a square, or multiple sticks can be joined together to form one side of a square.
  2. All sticks must be used, and each stick can only be used once.
  • Difficulty: Samsung
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 32MB for C/C++, 64MB for other languages
  • 64bit IO Format: %lld
  • Knowledge: DFS, pruning

Sample:

  • Input: [4,1,1,1]
  • Returns: (false)
  • Explanation: These four sticks cannot be assembled into a square
#include <algorithm>
#include <numeric>


class Solution {
public:
    /** * The class name, method name and parameter name in the code have been specified, do not modify, directly return the value specified by the method ** to determine whether the input different length of sticks can be joined into a square **@param Sticks int Int Vector Specifies the length of a stick (*)@return Bool Boolean */
    bool canLinkToSquare(vector<int>& sticks) {
        if (sticks.size() < 4) {
            return false;
        }
        
        int len = std::accumulate(sticks.begin(), sticks.end(), 0);
        if (len == 0 || len % 4! =0) {
            return false;
        }
        
        int max = *std::max_element(sticks.begin(), sticks.end());
        if (max > len / 4) {
            return false;
        }
        
        std::sort(sticks.begin(), sticks.end());
        std::vector<bool> marks(sticks.size(), false);
        
        return dfs(sticks, marks, len / 4.0.0.0);
    }
    
    /** ** Use DFS to determine whether the input sticks of different lengths can be assembled into a square *@param Sticks int Int Vector Specifies the length of a stick (*)@param Marks bool Whether vector sticks are used *@param Len int Length of the side of the integral stick *@param Count int Number of edges of an integer *@param L int The length of the current edge *@param Pos size_t Position of the stick currently used by the integer *@return Bool Boolean */
    bool dfs(const vector<int> &sticks, vector<bool> &marks, const int len,
         	 int count, int l, size_t pos) {
  		if (count == 3) return true;
  		for (int i = pos; i < sticks.size(); i++) {
    		if (marks[i]) continue;

    		if (l + sticks[i] == len) {
      			marks[i] = true;
      			if (dfs(sticks, marks, len, count + 1.0.0))
        			return true;
      			marks[i] = false;
      			return false;
    		} else if (l + sticks[i] < len) {
      			marks[i] = true;
      			if (dfs(sticks, marks, len, count, l + sticks[i], i + 1))
        			return true;
      			marks[i] = false;
      			if (l == 0)
                    return false;
      			while (i + 1 < sticks.size() && sticks[i] == sticks[i + 1]) i++; }}return false; }};Copy the code

3.3 Remove the shortest subarray to make the remaining array orderly

Enter an array of integers. Remove one of the subarrays so that the remaining elements in the array are non-incrementing. A subarray can be a contiguous subsequence of the original array, or it can be empty. Please return the length of the shortest subarray.

  • Difficulty: Samsung
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 256MB for C/C++ and 512MB for other languages
  • 64bit IO Format: %lld
  • Knowledge: Array

Sample:

  • Input:,4,3,7,8,2,1 [5]
  • Return value: 2
  • Note: the shortest subarray to delete is [7,8] with length 2. The remaining elements are [5,4,3,2,1] and are non-incrementing.
import java.util.*;


public class Solution {
    /** * The class name, method name and parameter name in the code have been specified, do not modify, directly return the value specified by the method ** *@param Array int A one-dimensional array of integers@return Int * / integer
    public int findLengthOfShortestSubarray (int[] arr) {
          int n = arr.length;
        int left = 0;
        while (left + 1 < n && arr[left] >= arr[left+1]) {
            left++;
        }
        / / [0... left] orderly
        if (left == n - 1) {
            return 0;
        }
        / / / right... n - 1) in order
        int right = n - 1;
        while (right > 0 && arr[right - 1] >= arr[right]) {
            right--;
        }
        
        // delete side [left+1, n-1], or [0... right-1]
        int result = Math.min(n - left - 1, right);

        // The left and right sides are reserved
        int i = 0, j = right;
        
        while (i <= left && j <= n - 1) {
            if (arr[i] >= arr[j]) {
                // [0... I] and [j...n-1] order, delete [I +1...j-1]
                result = Math.min(result, j - i - 1);
                i++;
            } else {
                // 小的+1j++; }}returnresult; }}Copy the code

Four, jumping movement

4.1 Task Assignment

In the off-line machine translation system, sometimes multiple sentence translation requests are received at one time. The translation time of these sentences can be estimated as jobs according to the length. Jobs [I] indicates the translation time of the i-th requested sentence. The system starts k threads to process these translation tasks simultaneously. In order to reduce the response time, we need to allocate these translation requests to different threads for processing. Each request can only be allocated to one thread, and the processing time of one thread is the sum of the translation time of all request sentences allocated to it. The system processing time is the time it takes all threads to translate the assigned task. Your goal is to optimize the allocation so that the system can process all requests as quickly as possible. Calculate the minimum processing time for the entire system.

  • Difficulty: five stars
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 32MB for C/C++, 64MB for other languages
  • 64bit IO Format: %lld
  • Knowledge: greed, linear dynamic programming

Sample:

  • Input: (3, 2, 3), 3
  • Returns: 3
  • Description: Three requests are assigned to three tasks, and the system processing time is 3
class Solution {
public:
    /** * The class name, method name and parameter name in the code have been specified, do not modify, directly return the value specified by the method can ** schedule tasks in jobs, assign k workers to process, return the shortest processing time of the system *@param Jobs int Integer vector Translation length array *@param K int Number of integer translation threads *@return Int * / integer
    int minimumProcessTime(vector<int>& jobs, int k) {
        // write code here
        int n = jobs.size();
        if (n <= k) {
            return *max_element(jobs.begin(), jobs.end());
        }
        vector<int> tot(1 << n, 0);
        for (int i = 1; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) == 0) continue;
                int left = (i - (1 << j));
                tot[i] = tot[left] + jobs[j];
                break;
            }
        }
        
        vector<vector<int>> dp(k, vector<int>(1 << n, -1));
        for (int i = 0; i < (1 << n); i++) {
            dp[0][i] = tot[i];
        }
        
        for (int j = 1; j < k; j++) {
            for (int i = 0; i < (1 << n); i++) {
                int minv = 1e9;
                for (int s = i; s; s = (s - 1) & i) { // Enumerate all subsets of I
                    int left = i - s;
                    int val = max(dp[j-1][left], tot[s]); minv = min(minv, val); } dp[j][i] = minv; }}return dp[k-1] [(1<<n)-1]; }};Copy the code

4.2 Practice makes perfect

The saleman has two oil cans, each with a liter and B liters in capacity. The customer wants to buy C liters of oil. Since neither can has a scale, the saleman can only do the following three operations:

  1. Fill one of the oil cans with oil
  2. Pour all the oil out of one of the oil cans
  3. Pour oil from one can into another. If the oil capacity of the source oil can is larger than the remaining capacity of the target oil can, the source oil can retains the remaining capacity after this operation and the target oil can is filled with oil; otherwise, the source oil can capacity is empty after this operation and the target oil can capacity is the previous capacity + the source oil can capacity.

The man wanted to know if he could do this several times so that the volume of oil in one of the cans was equal to the customer’s purchase volume of C liters. Write a program to solve the problem of oil seller, output the minimum number of operations if the target capacity can be obtained after several operations, otherwise output -1.

  • Difficulty: five stars
  • Time limit: 1 second for C/C++, 2 seconds for other languages
  • Space limit: 32MB for C/C++, 64MB for other languages
  • 64bit IO Format: %lld
  • Knowledge: BFS

Sample:

  • Input: [5,3,6]
  • Returns: [1]
  • Note: [Cannot be operated several times so that the capacity of oil in one can is equal to 6]
class Solution {
public:
    // Two oil cans
    class State {
    public:
      	State(int _a, int _b) : a(_a), b(_b), step(0), op(-1) {};
    public:
      	int a; // A can of oil
     	int b; // A can of oil
    	int step; // How many steps have you taken to reach this state
      	int op; // The number of operations taken to reach this state
    };
    
    void update(std::queue
       
         &q, std::vector
        <:vector>
         > &visited, State &next, int step, int op
        ) {
      	assert(next.a >= 0 && next.b >= 0);
      	if(! visited[next.a][next.b]) { next.step = step; next.op = op; q.push(next); visited[next.a][next.b] =true; }}/** * The class name, method name, parameter name in the code has been specified, do not modify, directly return the value specified by the method ** can after several operations to get the target capacity, if possible, please output the minimum number of operations, if not, please output -1. *@param A int A pot capacity *@param B int Int b Pot capacity *@param C int Specifies the target capacity of an integer@return Int * / integer
    int findShortestStep(int a, int b, int c) {
    	if (c > a && c > b)
        	return -1;

    	if (c == a || c == b)
        	return 1;

    	if (a == b)
        	return -1;
    	else if (b > a)
        	std::swap(a, b);

    	if (c > b && c < a && a % b == 0 && c % b == 0) {
        	int ua = a / b;
        	int uc = c / b;
        	return std::min(ua - uc, uc) * 2;
    	}

    	if (c == a - b) {
        	return 2;
    	}

    	State init(0.0);
        std::vector<std::vector<bool>> visited(a + 1.std::vector<bool>(b + 1.false));
    	visited[0] [0] = true;

   		std::queue<State> q;
    	q.push(init);
    	while(! q.empty()) { State s = q.front();if (s.a == c || s.b == c) {
            	return s.step;
        	}

        	// fill a
        	State next(0.0);
        	if (s.a < a) {
            	next.a = a;
            	next.b = s.b;
            	update(q, visited, next, s.step + 1.0);
        	}

        	// fill b
        	if (s.b < b) {
            	next.a = s.a;
            	next.b = b;
            	update(q, visited, next, s.step + 1.1);
        	}

        	// drop a
        	if (s.a) {
            	next.a = 0;
            	next.b = s.b;
            	update(q, visited, next, s.step + 1.2);
        	}

        	// drop b
        	if (s.b) {
            	next.a = s.a;
            	next.b = 0;
            	update(q, visited, next, s.step + 1.3);
        	}

        	// pour a to b
        	if (s.a && s.b < b) {
            	if (s.a <= b - s.b) {
                	next.a = 0;
                	next.b = s.b + s.a;
            	} else {
                	next.a = s.a - (b - s.b);
               		next.b = b;
            	}
            	update(q, visited, next, s.step + 1.4);
        	}

        	// pour b to a
        	if (s.b && a > s.a) {
            	if (s.b <= a - s.a) {
                	next.a = s.a + s.b;
                	next.b = 0;
            	} else {
                	next.b = s.b - (a - s.a);
                	next.a = a;
            	}
            	update(q, visited, next, s.step + 1.5);
        	}

        	q.pop();
    	}

    	return -1; }};Copy the code

How do you feel?

Is your hair ok?

It doesn’t matter if you’re a code guru

Or try to grow up brave Niuniu

Youdao technology team is looking forward to your joining!

Welcome to deliver netease Youdao! (Delivery channel: HR.netease)

* Easter Egg: On August 16th (Monday) 19:00, netease Youdao 2022 Technical air Promotion will meet you face to face to answer questions and reveal youdao’s secret work!