Background BECAUSE I want to face byte backend internship post, in the panic driven to search a large number of online experience. Part1-4 (net; Database; Operating system; Python). Part5-9 (Bulk knowledge; The project; Algorithm problem; Intelligence; Math). My own face was put on the ox. You can take a look at it.

  • The main content of this text is algorithm/intelligence/math problem.
  • That intelligence question I feel to find quite complete, optimal solution general solution of what also arranged ~ (^_ ^)

5 Bulk knowledge

Bulk knowledge is… Neither the computer network, nor the operating system, nor the database ٩(danjun ‘– ´ danjun) p

5.1 a hash table

  • HashMap (Java) Method for resolving Hash conflicts. Principle of HashMap and expansion
    • The underlying implementation of a HashMap is a Hash array and a one-way linked list, where each element in the array is a linked list.
    • Method for resolving Hash conflicts: Zip method. When the list length exceeds 8, the list is converted to a red-black tree.
    • Capacity expansion: the actual padding is greater than the loadFactor loadFactor (the default value is 0.75). During capacity expansion, call resize() to double the size of the table (default initial length is 16).
  • How do hash tables handle high concurrency? How do linked lists form rings?
    • ReHash may form linked list loop comics in the case of concurrency: HashMap under high concurrency – small Grey article – Zhihu
    • Use thread-safe ConcurrentHashMap
  • What is the underlying implementation of ConcurrentHashMap
  • What other methods are there for hash collisions besides linked lists?
    • Hash algorithm in detail
    1. Open addressing
      • Linear detection hashes (+1,+2,+3… +n)
      • Second detection and then hashing (+1,-1,+2,-2,+4,-4… +2^n, -2^n)
      • Pseudo random probe hashes (+3,-6,+8,-7,-10,+2,+4.. A permutation random sequence containing values from 1 to m-1))
      • Double hash probe ((hash1(key) + I * hash2(key)) % TABLE_SIZE, I = step size, +1 if hit again)
    2. Hash again (if one is repeated, then use another algorithm to calculate)
    3. Chain address method (Java HashMap does this)
    4. Establish a public overflow area
  • What are the disadvantages of open addressing?
    1. The number of records cannot exceed the length of the bucket array. If the number of records exceeds the size of the bucket array, the time cost of an operation increases dramatically
    2. Using probe sequences requires computation and can be time costly
    3. When the record size or total size is large, the space occupied by empty slots can cause significant memory waste
    4. When deleting records, it is more troublesome. Delete flags need to be set. Resulting in extra space and manipulation.
    • Advantages: Easy serialization
  • What are the advantages of the zipper method
    1. Handles better for cases where the total number of records changes frequently (avoiding the overhead of dynamic adjustment)
    2. Since records are stored in dynamically allocated nodes, there is no waste of memory, which is suitable for the case where the size of the record itself is large, and the overhead of Pointers can be ignored
    3. When deleting records, it is convenient to use the pointer operation directly
    • Disadvantages: Jump access to a hash table incurs additional time overhead compared to compact data types such as arrays; Not easy to serialize.

    Summary of zipper vs. Open Addressing comparison: The problem of space; The problem of deletion; Access speed issues; The serialization problem

5.2 Object-oriented

  • Override and Overload
    • Overload: Indicates that there can be multiple methods in the same class with the same name but with different argument lists (that is, different number or type of arguments). It’s about the compiler, it’s not about OOP.
    • Override: Indicates that a method in a subclass can have exactly the same name and arguments as a method in a parent class, and that a method in a subclass (even if it is a parent class pointer) will be called when called through a subclass object. You can achieve polymorphism.
  • Restful api
    • REST stands for Representational State Transfer and is an API design style. Interviewer: How dare I hire you when you don’t even know RESTful? – Bryant’s article – Zhihu
    1. Uniform Interface: An Interface should include a URL (a resource) and self-describing information (how to handle that resource). Readable. So that the client only needs to focus on implementing the interface.
    2. Stateless: Each request of the client has sufficient information (URL,header,body) for the server to identify. Good for debugging, bad for wasting transmission bandwidth.
    3. Client-server: Data is stored on the Server and only needs to be used by the Client. Both ends are completely separated. So that the client side of the code portability is stronger, the Server side of the expansion is stronger.
    4. Cacheable: Properly managed caching partially or completely removes the interaction between client and server, further improving performance and scalability
    5. Layered System: Clients are usually unable to know whether they are directly or indirectly connected to the end server. Consider security policies when layering.
  • If you want to add a function to software, do you want to use composition or inheritance
    • If some functions on requirements are freely combinable, then composition should be used, forcing inheritance will cause Combinatorial explosion.
    • The inheritance level is too deep and complex, which will affect the maintainability of the code.
    • Inheritance has three main functions: representing IS-A relationships, supporting polymorphic characteristics, and code reuse.
    • Theoretically, inheritance can be replaced by composition, interface and delegation. Avoid or minimize the use of inheritance relationships in projects, especially complex ones.
    • Inheritance passes calls up for reuse and composition passes in for delegation.
public class Ostrich implements Tweetable.EggLayable {/ / the ostrich
  private TweetAbility tweetAbility = new TweetAbility(a);/ /
  private EggLayAbility eggLayAbility = new EggLayAbility(a);/ /
  / /... Omit other properties and methods...
  @Override
  public void tweet(a) {
    tweetAbility.tweet(a);/ / to entrust
  }
  @Override
  public void layEgg(a) {
    eggLayAbility.layEgg(a);/ / to entrust}} By Mu Chen link: HTTPS://zhuanlan.zhihu.com/p/93899632The copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the code
  • How does multiple inheritance solve the diamond model
  • Three main features of object-oriented languages
    • Encapsulation: Hides the properties and implementation details of an object and exposes only the interface. The goal is to enhance security and simplify programming
    • Inheritance: A subclass inherits the characteristics (variables) and behavior (functions) of its parent class. It allows code reuse (but also high coupling), and the biggest implication is to implement polymorphism.
    • Polymorphic: A subclass object can be considered a superclass object. Depending on which class the program is actually using at runtime (performing functions overwritten by subclasses themselves).

5.3 Redis

Why Redis? Why is Redis so fast? – Fat dog’s article – Zhihu

  • Redis data structure
    • String An integer, floating point, or String
    • The Set collection
    • Zset ordered Set (skip list implementation)
    • Hash Hash
    • List the List
  • Why is Redis fast and why single threaded
    • Firstly, multiplexing blocking IO mechanism is adopted.
    • Then, the data structure is simple, operation saves time;
    • Finally, running in memory is naturally fast
    • Single-threaded: The bottleneck in Redis is not CPU speed, but network bandwidth and the size of the machine’s memory. Single thread switching is cheap and easy to implement.

5.4 Design Mode

  • What design patterns have been used? I say singleton, factory, observer, agent. (He wanted me to say policy mode, decorator mode, and adapter mode, but I didn’t know any of those three.)
  • Decorator mode
    • Adding additional behavior to an object dynamically is more flexible than subclassing (because you decorate objects, not classes)
    1. Abstract Component: Defines the interface of the object to be decorated
    2. ConcreteComponent: Defines objects to be decorated by decorators
    3. Decorators: Maintain references to Component
    4. Concrete Decorators: Add new responsibilities to the component
    • Example code: Design pattern decorator pattern – Lin Dongzhou’s article – Zhihu

  • Design patterns? Talk about strategic patterns
    1. Context: Holds a reference to a concrete policy class, which is provided to the client for invocation. Mask direct access to policies/algorithms by high-level modules. It can also provide some common functionality or store some state.
    2. Abstract Policy class (Strategy): Policy abstraction, generally defining interfaces.
    3. ConcreteStrategy classes: concrete abstract policy implementations that implement interfaces.
    • Advantages: It is convenient to switch policies and add policies.
    • Disadvantages: Each policy is a class (there are more and more of them), and policy classes need to be exposed (the upper modules must know which policies are available before deciding which to use)
  • Adapter mode
    • The adapter pattern enables two classes whose interfaces do not match to work together to transform.
    • Adapter pattern for classes: Converts the API of the adapted class into the API of the target class. Extends the original adapted class to implement the interface to the Implement target.
    • Adaptor pattern for objects: An API that converts the API of the adapted class into the target class. But this is done through composition rather than inheritance. An object that contains the adapted class, an interface that implements the Implement goal.

5.5 the Git

  • Git rebase git merge

5.6 Behaviour Question

  • I see XXX in your resume. Let’s talk about it
  • Tell me about the latest technologies you’re following
  • Describe a problem that was solved and how it was solved
  • Describe an unresolved problem and explore ways to solve it
  • To a strange job, how to carry out work
  • What non-technical books and technical books have you read recently
  • Can give oneself compare big pressure

6 projects

Obviously the project is different, so I picked a few that are close to my project.

  • What about login status in the project
    • Django comes with the auth module
  • What are the advantages of token compared to cookie+session
    • Wp – rocket. Me/blog/differ…
  • Mvc, MTV
  • Sessionid may duplicate with a large number of connections?
    • May be. But the probability is small.
  • Django orm
  • How do I search for articles in the database
# Django ORM: Searches for articles whose title or content contains a specified string, case and case insensitive
articles = articles.filter(
    Q(title__icontains=search) |
    Q(body__icontains=search))
# Q wraps the condition because filter is separated by a comma. Use the Q, and | operators can realize the OR
Copy the code
  • Tag-article list is too slow (Not sure)
    • Index the article. Labels are repetitive and cannot be indexed
    • The gal cache. The average user sees the article according to the label is to see the top several articles
  • Large file upload

7 algorithm

7.1 Classic Topics

Longest ascending subsequence

This is a bad question

Arr [I]: the size of the tail number of a continuous ascending subsequence of length I +1
class Solution:
    def lengthOfLIS(self, nums: List[int]) - >int:
        arr = []    
        for n in nums:
            # Special case: When there is no data at first
            if not arr: 
                arr.append(n)
                continue
            # Find a number smaller than the current value from back to front and extend it
            i = len(arr)-1  
            while arr[i] >= n and i>=0: i -= 1
            
            if arr[i] < n:  Stop because a small value is found
                if i+1 < len(arr):  # If there is someone behind, try updating this length. The smaller the tail number, the better
                    arr[i+1] = min(arr[i+1], n)
                else:   # If there is no one behind, open a new length
                    arr.append(n)
            else:   # If no one is smaller than you, stop at 0
                arr[0] = n

        return len(arr)
Copy the code
# use binary lookup to optimize to O(NlogN)
class Solution:
    def lengthOfLIS(self, nums: List[int]) - >int:
        arr = []    # arr[I]: the tail digit size of a continuous ascending subsequence of length I +1
        for n in nums:
            # if there is no number greater than n in arr
            if not arr or arr[-1]<n: 
                arr.append(n)
                continue
            # find a number just a little bit larger than n, binary search
            left,right=0.len(arr)-1
            while left <= right:
                mid = (left+right)//2
                midval = arr[mid]
                if midval > n:
                    right = mid-1
                elif midval < n:
                    left = mid+1
                else:
                    left = right = mid
                    break
            # Left refers to something larger than or equal to n
            arr[left] = min(arr[left], n)
            
        return len(arr)
Copy the code

Finger 48. The longest substring without repeating characters

class Solution:
    def lengthOfLongestSubstring(self, s: str) - >int:
        if not s: return 0
        left, right = 0.1	
        # Open left close right. Right is in charge of exploring the unknown.
        contain = set()
        contain.add(s[left])
        ans = 1
        
        while right < len(s):
            if s[right] not in contain:
                contain.add(s[right])
                ans = max(ans, len(contain))
                right += 1
            else:	
            # If duplicate is found, discard the left character until no duplicate is found
            In extreme cases, left=right, equivalent to emptying the original set
                contain.discard(s[left])
                left += 1
        return ans
Copy the code

After the rain

  • As soon as each wall appears, cement all the gaps that can be filled between it and the wall to the left. (This is pretended to be cement, more vivid than water. Poured cement turns into a wall.)
  • So the left side, which has been treated, must have been a stepwise increase and decrease, with no depression. For a new wall, its left side is from the lower wall to the higher wall
  • Pour cement in layers. The initial bottleneck was the low wall on the left, and as the layers of cement were poured, the bottom of the pool got higher and higher. The final bottleneck is itself as the low wall on the right.
class Solution:
    def trap(self, height: List[int]) - >int:
        stack = []
        ans = 0
        for i, h in enumerate(height):
            if h == 0:
                continue
            bar = 0  # For each new wall, bar is new
            while stack:
                i_, h_ = stack[-1]
                if h_ <= h:     # If the top of the stack <= the current wall, keep hitting the left wall with the current wall and gradually raise the bar
                    ans += (i-i_-1) * (h_ - bar)
                    bar = h_
                    stack.pop()
                else:           # If top of stack > current wall, current wall becomes the dwarf on the right, add water according to current bar.
                    The current bar is the maximum value of the wall between the current wall and the current top of the stack, which was calculated in the first step of the continuous collision
                    ans += (i-i_-1) * (h - bar)
                    break
            stack.append((i,h))
        return ans
Copy the code

LRU implementation

The sum of three number

Wu_yan_zu – Force buckle problem solution

A string. Find the second most common character

  • This should only be hash table counting, right?

Egg drop

When writing this question, I often get frustrated. Pay attention to:

  • You have to use the symbols that you’re given, or you have to use your own symbols all the way through. In a word to unify!! When thinking about this problem, I used F (N, D) to think, but the order of the problem was (K,N). As a result, I could not see the reverse order, which wasted a lot of unnecessary time.
  • When debugging complex recursive code, a large block is printed all at once, the dividing line is not easy to draw, and please believe that it is impossible to follow even if the thought is separated… Another approach is to separate the code according to its logical function and test the control variables. For example, “replace binary with exhaustive” will change from wrong to correct, indicating that binary code is buggy and other code is not buggy. But only if there is a “dumber but reliable” alternative to the logic module. Such as exhaustive method.
  • I went to the extreme point at the beginning of this problem, and luckily I didn’t think there were that many horizontal lines unless they were near the answer, and in fact there were a lot of places where the derivative was zero, far from the true minimum… This makes it very difficult to handle midval=midrval. The correct solution is to search for upper=downer. Visible at the beginning to consider the consequences of the unthinkable.
  • For recursive functions that enter multiple times, consider the possible range of input parameters. The egg is decreasing by at most one at a time, so you can be sure that it’s already been processed at K=1, you can’t have K=0. If N=0 occurs, it must be because mid=1 or mid=N. The former is theoretically possible, so better to deal with it.

An incrementing, then decrementing array finds the number of unique elements

I’m going to do a set that takes order n time and then I’m going to write a double pointer and I’m going to finish it without running

Implementing circular queues (LeetCode 622)

  • Use a k+1 array for storage
  • Note that the subscript of the MOD array should also press k+1.

Binary tree to bidirectional linked list

Climbing stairs => Multiples of 7 are not allowed

  • It’s like Fibonacci numbers. It doesn’t count if you’re not allowed to reach multiples of seven.

The longest path sum of two points in the tree (Leetcode 124)

class Solution:
    def maxPathSum(self, root: TreeNode) - >int:
        ans = root.val
        
        def work(node) :
            nonlocal ans
            # ans: node+ Max (0, longest left)+ Max (0, longest right)
            The # work function returns the longest chain length starting with node, possibly a negative number
            
            if not node: return 0
            leftmax = work(node.left)
            rightmax = work(node.right)
            #print("at node", root.val, "leftmax,rightmax=",leftmax, rightmax)
            ans = max(ans, node.val + max(0,leftmax) + max(0,rightmax))
            return max(leftmax, rightmax, 0) + node.val
        
        work(root)
        return ans
Copy the code

Find the next number larger than the current number (1243, 1324)

  • Pay attention to rigor. When you climb a mountain, you have to climb. This is how repeating numbers are handled correctly
  • Nums [NextDigit +1:].sort() doesn’t work in Python
class Solution:	# LeetCode 31
    def nextPermutation(self, nums: List[int]) - >None:
        """ Do not return anything, modify nums in-place instead. This function can also handle duplicate values. Note the greater than or equal sign (""").
        
        cur = len(nums)-1  # Look for the first drop (<) from the back
        while cur >= 1 and nums[cur-1] >= nums[cur]: cur -=1
        if cur==0:
            nums.reverse()
            return
        nextdigit = cur-1  # The place to increment the carry

        cur = len(nums)-1  Select the smallest number greater than target from the back
        while nums[cur] <= nums[nextdigit]: cur -=1

        nums[cur], nums[nextdigit] = nums[nextdigit], nums[cur]
        nums[nextdigit+1:] = sorted(nums[nextdigit+1:)Copy the code

Take x to the y, and come up with something better than just a for loop

  • Binary fast power

Strives for the modal

  • Moore vote

Find the smallest positive integer that does not appear in an unsorted integer array

Hash with list subscripts.

Given a string, find the length of the smallest string that does not contain repeating characters

Sliding Windows.

Two dimensional array, increment by row, increment by column, ask if you can find some number

  1. Easy way from the bottom left corner to the top right. But the interviewer will ask you to write a normal 2. Ha ha.
  2. The matrix is divided into four pieces. But not by the center of the line. See solution 3 for details

An IP address is converted to an int (IP address is 32 bits, int is 32 bits).

A binary tree finds the common parent of both nodes

How to optimize fast sorting when there are many repetitions

Three way fast platoon. This thing has to be written by hand!

How can a group of numbers be arranged to produce the largest number

Same thing with strings. Custom rule sorting.

Whether the character matrix has a given string

  • DFS, calculating time complexity. Refer to the path in the Offer 12 matrix

Non-negative integer string rearrangement minimizes the result

Set the array to the smallest number
from functools import cmp_to_key    # Python great!!
def compare(x1, x2) :   # if x1 is larger, it returns a positive number; if x1 is smaller, it returns a negative number; if x1 is equal, it returns 0.
    return int(x1+x2) - int(x2+x1)

class Solution:
    def minNumber(self, nums: List[int]) - >str:
        nums = [str(i) for i in nums]
        nums.sort(key=cmp_to_key(compare))
        return ' '.join(nums)
Copy the code

Given a string, find the shortest substring containing the specified character

The time complexity of the algorithm is given to prove the validity of the algorithm.

  • Should be the same as the longest non-repeating substring, maintain left and right Pointers and a collection

LeetCode 54 helical matrix, how to ensure that the output does not repeat.

There are two ways to solve this problem: the circular printing method, and around the “peel edge” method. Below is the code printed in circles. I’m going to make sure that I don’t print the second one if I have left and right overlap, or top and Down overlap.

class Solution:		# Split circle printing method
    def spiralOrder(self, matrix: List[List[int]]) - >List[int] :
        if not matrix: return []
        
        m,n = len(matrix),len(matrix[0])
        left,right = 0, n-1
        top,down = 0, m-1
        
        ans = []   
        def printCircle(top, left, down, right) :
            nonlocal ans
            for i in range(left,right+1):
                ans.append(matrix[top][i])
            for j in range(top+1, down):
                ans.append(matrix[j][right])
                
            iftop ! = down:# This part could be swallowed!
                for i in range(right, left-1, -1):
                    ans.append(matrix[down][i])
            ifleft ! = right:# This part could be swallowed!
                for j in range(down-1, top, -1):
                    ans.append(matrix[j][left])
        
        while left<=right and top <= down:
            printCircle(top,left,down,right)
            top, left, down, right = top+1, left+1, down-1, right-1
            
        return ans
Copy the code

Zigzag level traversal of Leetcode103 binary tree

Leetcode25 K sets of flipped linked lists

Find the first missing positive integer

  • If n positive integers are entered, the first missing positive integer must be in the interval [1,n+1]
  • Scan the list and record the occurrence of [1,n+1]
  • Scan the array for the first missing number in [1,n+1]

Implementation of RAND (1, 7)

  • Rand5 is called twice, generating between 1 and 25 combinations
  • For 1 to 21, use %7+1 to print the result
  • Otherwise, refuse sampling and start all over again

7.2 Large amount of data

1 billion unordered integers find the median.

Because it is a billion integers, it cannot be processed in memory. That is to say, use a proper external sorting algorithm. Here you can use bucket sort, take n evenly spaced buckets, iterate over the integers, store them in the buckets of the corresponding interval, and count the number of digits in the buckets. If the number in the bucket is still too large, sort the bucket. Otherwise, sort the bucket in memory.

Memory can only hold 1000 pieces of data. How do YOU sort 5000 pieces of data?

  • 5K pieces are divided into 5 groups with 1K pieces in each group
  • Each group is read into the memory separately and sorted into the hard disk
  • Read the first 200 entries from each of the five groups. Select 1 from each of the five groups and write the entries to the hard disk. When the 200 entries in a group are sorted, read the 200 entries in the group until the sorting is complete.

100,000 IP addresses. Find the 10 most frequent IP addresses

  • First hash into small files
  • Find the 10 most frequent IP addresses in each small file
  • Compute the top 10 IP addresses with the highest frequency globally

100 billion unsigned integers. Find the largest 100

What’s the solution for running out of memory? What if I have enough memory? Partition’s solution is unstable. Is there any way to stabilize it?

  • I ran out of memory to sort the heap (create a small top heap of k=100 size, then iterate over the data, replace the root of the heap with the value greater than the root of the heap). He said time, I said N log k.
  • There is enough memory for counting sorts (there are only so many unsigned integers, 100 billion of them must be duplicated. The advantage of counting sort is O(n), but the disadvantage is that it takes too much memory. Since the memory is enough, use it freely ~)
  • Bucket sort can be thought of as a weakened version of count sort, which is the sort of buckets whose size is 1.

7.3 Semaphore and lock

The semaphore realizes the philosopher’s meal

  • Method 1: Five forks are numbered 0-4, and each philosopher must take the smaller one first.
  • Method two: allow up to four philosophers to hold a fork, so that at least one philosopher can eat it.
  • Method three: let the philosopher numbered odd take the left side first, and the philosopher numbered even take the right side first.

Three ideas – break cycle wait – ngcafai – force link problem solution

Use condition variables to implement read/write locks

Producer consumer

Hand tear producer and consumer model, 10 producers, 10 consumers, 30 queue capacity (the following picture is the producer consumers without the while loop, different from the original)

Implementing blocking queues

Take the highest priority first. I used the priority queue directly and was later asked to implement the maximum heap.

import threading
class BoundedBlockingQueue(object) :	# LeetCode1188
    
    def __init__(self, capacity: int) :
        self.capacity = capacity
        self.q = []
        self.con = threading.Condition()


    def enqueue(self, element: int) - >None:
        with self.con:  # automatically acquire and release
            while len(self.q) == self.capacity:   # full
                self.con.wait()
            self.q.append(element)
            self.con.notify()

    def dequeue(self) - >int:
        with self.con: 
            while len(self.q) == 0:  # empty
                self.con.wait()
            ans = self.q.pop(0)
            self.con.notify()
            return ans
        

    def size(self) - >int:
        return len(self.q)
Copy the code

8 brainteasers

Here is my painstaking saving of intelligence questions, later interview a intelligence question did not ask, good anger (= _=)

The mice drank the poison

1000 bottles of water, one bottle is poison, you have infinite mice, drink poison after an hour poison hair, how to know within an hour which bottle of water poison? How many mice is the minimum? 1000 bottles of liquid medicine, 1 bottle of poison, how many mice can find out? – Wen Di’s article – Zhihu

This problem is looking at an understanding of base 2.

  • Rat 1: drink the one digit bottle numbered 1, Rat 2: drink the ten digit bottle numbered 1…
  • If mouse 1 is dead, mouse 2 is not dead, and mouse 3 is dead, then bottle 101=5 is toxic. So bottle 101=5 is toxic.
  • N mice have a range of 2^N, 1000 bottles are located between 2^9 and 2^10, that is, 10 mice can measure 1000 bottles of water.

What if it takes 30 minutes? (2 rounds can be tested)

  • If you drink 1 in the first round, fill in 1 when you die. If you drink 2 in the second round, fill in 2 when you die. If you don’t die in both rounds, fill in 0.

Incense timing

Two sticks of incense burn for an hour, 45 minutes

  1. A ends ignite, B ends ignite
  2. After A burns out, B still has half A stick of incense, which normally takes 30 minutes to burn
  3. Ignite B at both ends and burn it out in 15 minutes

Pirates divide gold

Five pirates took a hundred gold coins. All five pirates are greedy but wise at the same time. They drew lots in order. First signed by to draw a number of pirates say a set of points of king’s plan, if 5 people in more than 50% (including 50%) of people agree with, then according to this plan execution, or the people in the proposed scheme will be throw to feed the fish in the sea, then signed by to draw 2 pirates continue to say a plan, and so on to the fifth. If you were the pirate who drew number one, what plan would you make to get the most gold without losing your life?

To solve this problem, use the backward method:

  • If only number 5 is left: Number 5 keeps all the gold for himself
  • If only number 4 and 5: Number 5 must vote against and let number 4 feed the sharks, in order to keep all the gold. This situation is a dead end for Number four.
  • If there’s only 3, 4, and 5 left: No. 3 has one vote of his own and only needs to get one more vote to pass. If plan 3 doesn’t pass, it’s gonna be a two-person situation. Dead end for number four, good for number five. Number four doesn’t need money to support number three. Allocation scheme: “100,0,0”
  • If 2, 3, 4, 5 are left: No. 2 has one vote of his own and needs to get two votes to pass. If plan two doesn’t pass, it’s going to be three people. Good for number 3, 0 gold for number 4, 0 gold for number 5. So no. 2 can get to no. 4 and no. 5 by “98,0,1,1.”
  • If 1, 2, 3, 4, 5 are left: 1 has one vote of his own and needs to get two votes to pass. If plan 1 doesn’t pass, it’s going to be 4 people. Good for number 2, 0 gold for number 3, 1 gold for number 4, 1 gold for number 5. So no. 1 can woo no. 3, and no. 4 or no. 5 by (97,0,1,0,2) or (97,0,1,0,2).
  • If 0, 1, 2, 3, 4, 5 (added by oneself) are left: 0 has one vote and needs to win three votes to pass. If plan 0 doesn’t pass, it’s going to be 5 people. Good for number 1, 0 gold for number 2, 1 gold for number 3, 2 or 0 gold for number 4, 2 or 0 gold for number 5. So no. 1 can woo no. 2,3,4 by (95,1,2,2,0) or 2,3,5 by (95,1,2,0,2).

The tiger to eat the sheep

A hundred tigers can survive on grass, but they prefer to eat sheep. Only one tiger can eat the sheep at a time, but the tiger that eats the sheep will also become a sheep. Assuming all tigers are smart, think about saving their lives first and then eat the sheep. Will the sheep be eaten?

  • When a tiger: eat sheep decisively
  • With 2 tigers: do not eat, or you will become the sheep in the 1 tiger situation
  • Three tigers when: eat. If you eat sheep, you get two tigers, and if you eat two tigers, you don’t eat sheep.

And so on, an even number of tigers will not eat sheep, and an odd number will eat sheep

Screws and nuts

The horse racing

25 horses and 5 tracks. Only one horse per track is allowed in each race, and there is no tie. What is the minimum number of races required to pick the 3 fastest horses? 64 horses, 8 tracks, minimum number of top four finishes. The interviewer suggested 11 times in some cases, 10 times in others. Tencent algorithm interview – horse racing questions – a poem of the article – Zhihu

12 balls, one of different quality, weighing up to three times, how to weigh

God level general solution: N table tennis has a different quality and other, with the balance at least a few times must be able to weigh out? – zhihu

Divided into 3 groups, {1,2,3,4}, {5,6,7,8}, {9,10,11,12}

  • Weigh the first two groups first. If the weight is the same, we know that 8 must be a normal ball. Then [the second time] say {9,10}, {8,11}.
    1. If the weight is the same, it indicates that 9,10,11 are genuine and 12 is defective. [For the third time] Weigh 12 and 1 to see if they are lighter or heavier.
    2. {9, 10} heavy, then 9 or 10 heavy, or 11 light. [third time] Compare 9 and 10: if they are the same, 11 is lighter, otherwise the heavier one is inferior.
    3. {9, 10} light, then 9 or 10 light, or 11 heavy. [third time] Compare 9 and 10: if they are the same, weight 11, otherwise the light one is defective.
  • If {1, 2, 3, 4} is heavy in the first two groups, then there is some heavy in 1-4 or some light in 5-8. We know that 9-12 is a normal ball. [second time] compare {1,2, 5}(2 groups 1, 1 group 2) and {3,6,9}(groups 1,2, and 3)
    1. {1, 2, 5} Heavy: may be 1 or 2, or 6 light. [third time] Then compare 1, 2, if not the same weight, heavy is inferior. If it’s the same weight, six is defective.
    2. Same weight: means 1,2,5,3,6,9 are normal balls. 4 heavy, or 7 light or 8 light, [third time] compare 7 8.
    3. {1,2,5} light: state 5 light or 3 heavy, compare 3 (or 5) with a normal (such as 9) c.
  • If {5,6,7,8} is heavy in the first two groups, do the same with {1,2,3,4}.

A shall have 5 balls, B shall have 7 balls, and A and B shall take at least one ball at A time, and only one ball from the same box. Whoever takes the last ball loses. Does the first mover have a winning strategy?

  • There is. This is the manual DP. When a and b<=1, the analysis is simple. Skip. If a=b and A >=2, the first player loses, and the rest of the time the first player wins.

9 math problem

Three problems

There are three boxes, one of which has a prize. After the participant selects one, the host opens the other box without a prize and asks the participant whether to change the box. What is the winning probability of changing or not?

Given a function g that outputs 1 with probability P and 0 with probability 1-p, design a function f that outputs 0 and 1 with equal probability

Reject sampling method: call g twice, if the result is 0/1, output 0, the result is 1/0 output 1, the result is 1/1 or 0/0 then recalculate again.

The probability of three random points in a circle being exactly in a semicircle

What is the probability that any three or four points in the circle are in the same semicircle? Inspirations: What are the probabilities of forming an acute triangle, a right triangle and an obtuse triangle by randomly picking three points on a circle? (Answer: 1/4, 0, 3/4) Obtuse triangles are actually on the same semicircle.

[crazy hint][Crazy hint][Crazy hint]