[summary of interview questions] zj5

data structure : Trees and pictures

Graphs are divided into digraphs （ Added direction ）、 Undirected graph and weighted graph （ Add weight to the edge ）、 Ring 、 Acyclic graph .

Graph is represented by adjacency linked list and adjacency matrix

data structure ： Implementation of graph structure

Trees ：

Binary tree （ Full binary tree 、 Perfect binary tree ）、 Binary search tree 、 Balanced binary search tree （ The height difference between the left and right subtrees of all nodes does not exceed 1）、 Red and black trees 、B Trees （ Multiple search trees ）、B+ Trees

Common data structure —— Trees

How to find the shortest path ？

1、 Dijkstra algorithm ： Is the shortest path algorithm from one vertex to the rest , The solution is the shortest path problem in the weighted graph . Dijstra algorithm starts from the starting point , Adopt greedy algorithm strategy , Every time we traverse the critical node of the vertex that is closest to the starting point and has been visited , Know to extend to the end .

IoC How to implement container and dependency injection

What does it mean to resist reflection and serialization ？

** Why did you want to realize a simple spring Self research framework ？

**spring Have you seen the source code ？ Do you refer to the source code framework or do you do it yourself ？

** Scene question ：

There is a commodity class with an attribute of price , Another class is order , There is a method to calculate the total price according to the price and quantity , When prices change , The total price will also change , How to establish the connection between the two ？

If you set it as a scheduled task to poll and view , If this commodity category has 10 Ten thousand examples , Do you want to poll this 10 Properties in 10000 instances ？ The performance will be very poor .

If an attribute needs to be changed, it needs to pass set Methods to operate change . Then how do we know that this value has changed ？

Define a small framework , These classes defined by business personnel can be managed , Define some specifications , When business people use our stuff , The types they write are hosted by us , After trusteeship, I know what has changed , Who do I want to trigger .

How to establish the connection between the total price calculation method in the order category and the price attribute of the commodity category only by virtue of the bytecode ？ That is, how the program knows the connection between them ？

**JVM Virtual machine specification

JVM Virtual machine specification learning notes （ Thread safety implementation scheme 、 Lock the optimization ）

** How to simulate online flow pressure measurement ？ Import jmeter How to control the concurrency ？

First write a tool class to create 500 users to insert into the database , And put their id And generated token Write to a script file , Then import the script file into jmeter Inside . At the same time, design the number of thread groups .

final and finally difference

volatile keyword

java In the lock （ optimistic CAS、 Pessimism synchronized、lock）

**synchronized What is used to lock the method ？

synchronized It's the object that's locked , It can embellish common methods 、 Static methods 、 Code block .
When decorating a normal method, the current instance object is locked （ The method that the instance object calls , Who is the lock ）, Class objects are locked when decorating static methods .
synchronized What exactly is locked and how to use it

**ThreadLocal

The difference between threads and processes

** The process Deadlock in the operating system and how to release the deadlock

Four conditions of deadlock ：

Deadlock prevention is breaking one of the four conditions

Mutually exclusive conditions are generally not changed .

1、 Break requests and hold conditions ： Adopt a resource pre allocation strategy , That is, apply for all resources before the process runs , If satisfied, run , Or wait .

2、 Break the conditions of non deprivation ： When a process occupies an exclusive resource and then applies for an exclusive resource, it cannot satisfy it , Then withdraw from the original resources .

3、 Break the cycle of waiting ： Realize the strategy of orderly allocation of resources

Deadlock prevention ： Destroy one of the four conditions .

Deadlock avoidance ： The system is dynamically checking the resource request sent by a process , And decide whether to allocate resources according to the inspection results . If the system may deadlock after allocation , No distribution , Otherwise, it will be distributed .

Deadlock detection and release ： When a deadlock is detected , There are ways to eliminate deadlocks ： Undo process , Deprive of resources .

** How does the banker's algorithm do （ Which of the four conditions just now is broken ）

Banker algorithm belongs to deadlock prevention . It is the process by which the operating system decides whether to allocate resources . There is a safe state （ At some point , The system follows a certain sequence of processes , Allocate each process its required resources , It can make every process complete smoothly ）

There must be no deadlock in the safe state , An unsafe state does not necessarily lead to a deadlock , But a deadlock must be an unsafe state .

What breaks is the loop wait condition

Deadlock in database , How to remove

1、 Select the one with a small amount of transactions to rollback

2、 Use the resource allocation graph to predict , If there is a loop in the graph, a deadlock will occur .

Isolation level

Unreal reading and how to avoid it

Quick sort

**hash What is a data structure of a table

Hash table is a data mapping structure that searches for values according to key codes , The structure finds the place to store the value by mapping the key position . It's like a dictionary , For example, we are looking for “ surface ” Information about this word , We will start with Pinyin biao To find the corresponding location , After getting the location, you can go to the location to get the corresponding information .

Resolution of hash conflicts ：

1、 Open address method ：

When it comes to conflict , Just look for hash Table remaining free space , Find the free space and insert . It's like going to a store to buy something , But I found that the store had sold out , Then go to the next store next to it .

2、 Zipper method ：

The open address method is to find the next free address by following the original hash address in case of conflict , But what if the hash table is out of space ？

Principle of zipper method ： In case of conflict , It will create a new space in place , Then insert it into the space in the form of a linked list node .

** Semaphore ,PV What does the value in the operation mean

Semaphore Semaphore , Limit the number of threads that can access shared resources at the same time . Want to ReentrantLock It's all exclusive , Semaphores are shared , Just add the shared thread limit . For example, the parking space in the parking lot is limited , You can't keep driving into the parking lot .

When its value is greater than 0 when , Represents the current number of available resources . When its value is less than 0 when , Its absolute value identifies the number of processes waiting to use the resource . use PV Operate to change .P Minus one ,V Add one

When the semaphore S When it is greater than zero ,S Indicates the number of available resources . Do it once P An operation means a request to allocate a resource , therefore S Value of minus one . When the semaphore S When it's less than zero , Indicates that there are no available resources , The requester must wait for another process to release the resource , Then he can run . And execute a V Operation means releasing a resource , therefore S Add one to the value of .

When S<0, Indicates that some processes are waiting for the resource , So wake up a waiting process , Make it work .

[ Semaphore And PV Operation meaning ]

** Learn about the design patterns of

The singleton pattern 、 Facade mode 、 Simple factory model 、 Abstract factory pattern 、 Template method pattern 、 Decorator mode 、 Adapter pattern 、 The proxy pattern 、 Observer mode

【 Self research framework I 】 Facade mode 、 Simple factory model 、 Factory method model 、 Abstract factory pattern

Observer mode

** Decorator mode ,java This pattern is widely used in the package of

Decorator pattern means that without changing the existing object structure , Add some responsibilities to the object dynamically （ That is to add its extra functions ） The pattern of .

Take a fast food restaurant as an example . Fast food is an abstract component , It defines some basic characteristics of fast food , Such as price and description . Fried rice and fried noodles are the decorators , Need to inherit fast food . Ingredients are decorators , Not only need to inherit the fast food class, but also need to combine it . Egg ingredients and bacon ingredients are the specific decorative roles , You need to inherit the ingredient class . When we need to add another ingredient, such as sausage, we can directly add it and then inherit the ingredient class .

java Of IO package

Decorator mode

JDK Decorator mode in

[ From the understanding of Decorator Pattern JAVA Of IO package ](https://www.cnblogs.com/coprince/p/6525581.html)

** What designer patterns must be used in common frameworks

With spring Framework for example , The factory design pattern is used 、 The proxy pattern 、 The singleton pattern 、 Template method pattern 、 Decorator mode 、 Observer mode 、 Adapter pattern .

Factory design mode ：SPring Created using the factory pattern bean object （BeanFactory、ApplicationContext）

2、 The proxy pattern ：SpringAOP The method is enhanced by

3、 The singleton pattern ： management Bean For example .

4、 Template method pattern ：Spring in jdbcTemplate Such as to Template The end of the database operation class , They just use the template pattern .

5、 Decorator mode ： When the project connects to multiple databases in public , And different customers access different databases according to their needs in each access . This mode allows us to dynamically switch different data sources according to the needs of customers .

6、 Observer mode ：Spring Event driven

7、 Adapter mode ：SpringAOP The adapter mode is used for the notification of , as well as SpringMVC Adapter pattern matching is also used Controller

interviewer ：Spring What design patterns are used in the framework ？

** Template method pattern

It defines a process skeleton in an operation , And defer some concrete implementations to subclasses , According to the actual needs of subclasses .

The data structure of the index

Isolation level of database

What problem does repeatable reading solve

interviewer ：Spring What design patterns are used in the framework ？

** Template method pattern

It defines a process skeleton in an operation , And defer some concrete implementations to subclasses , According to the actual needs of subclasses .

The data structure of the index

Isolation level of database

What problem does repeatable reading solve

What is the problem of unreal reading 、 What is the problem with nonrepeatable reading