必修-场景题

1. 树遍历

遍历树是数据结构中的一个重要部分
二叉树（每个节点最多有两个子节点）
三叉树（每个节点最多有三个子节点）

通常，我们会有以下几种遍历方式：

前序遍历：访问顺序是根节点 -> 左子树 -> 右子树。
中序遍历 ：访问顺序是左子树 -> 根节点 -> 右子树。
后序遍历：访问顺序是左子树 -> 右子树 -> 根节点。
层序遍历：按层次依次访问节点。

二叉树

首先，我们定义一个二叉树节点类：

class BinaryTreeNode {int value;BinaryTreeNode left;BinaryTreeNode right;BinaryTreeNode(int value) {this.value = value;left = null;right = null;}
}

接下来，我们实现各种遍历方法：

import java.util.LinkedList;
import java.util.Queue;public class BinaryTreeTraversal {// 前序遍历public void preOrder(BinaryTreeNode node) {if (node != null) {System.out.print(node.value + " ");preOrder(node.left);preOrder(node.right);}}// 中序遍历public void inOrder(BinaryTreeNode node) {if (node != null) {inOrder(node.left);System.out.print(node.value + " ");inOrder(node.right);}}// 后序遍历public void postOrder(BinaryTreeNode node) {if (node != null) {postOrder(node.left);postOrder(node.right);System.out.print(node.value + " ");}}// 层序遍历public void levelOrder(BinaryTreeNode root) {if (root == null) return;Queue<BinaryTreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {BinaryTreeNode node = queue.poll();System.out.print(node.value + " ");if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}}public static void main(String[] args) {BinaryTreeNode root = new BinaryTreeNode(1);root.left = new BinaryTreeNode(2);root.right = new BinaryTreeNode(3);root.left.left = new BinaryTreeNode(4);root.left.right = new BinaryTreeNode(5);BinaryTreeTraversal traversal = new BinaryTreeTraversal();System.out.println("Pre-order:");traversal.preOrder(root);System.out.println("\nIn-order:");traversal.inOrder(root);System.out.println("\nPost-order:");traversal.postOrder(root);System.out.println("\nLevel-order:");traversal.levelOrder(root);}
}

三叉树

首先，我们定义一个三叉树节点类：

class TernaryTreeNode {int value;TernaryTreeNode left;TernaryTreeNode middle;TernaryTreeNode right;TernaryTreeNode(int value) {this.value = value;left = null;middle = null;right = null;}
}

接下来，我们实现各种遍历方法：

import java.util.LinkedList;
import java.util.Queue;public class TernaryTreeTraversal {// 前序遍历public void preOrder(TernaryTreeNode node) {if (node != null) {System.out.print(node.value + " ");preOrder(node.left);preOrder(node.middle);preOrder(node.right);}}// 后序遍历public void postOrder(TernaryTreeNode node) {if (node != null) {postOrder(node.left);postOrder(node.middle);postOrder(node.right);System.out.print(node.value + " ");}}// 层序遍历public void levelOrder(TernaryTreeNode root) {if (root == null) return;Queue<TernaryTreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TernaryTreeNode node = queue.poll();System.out.print(node.value + " ");if (node.left != null) queue.offer(node.left);if (node.middle != null) queue.offer(node.middle);if (node.right != null) queue.offer(node.right);}}public static void main(String[] args) {TernaryTreeNode root = new TernaryTreeNode(1);root.left = new TernaryTreeNode(2);root.middle = new TernaryTreeNode(3);root.right = new TernaryTreeNode(4);root.left.left = new TernaryTreeNode(5);root.left.middle = new TernaryTreeNode(6);root.left.right = new TernaryTreeNode(7);TernaryTreeTraversal traversal = new TernaryTreeTraversal();System.out.println("Pre-order:");traversal.preOrder(root);System.out.println("\nPost-order:");traversal.postOrder(root);System.out.println("\nLevel-order:");traversal.levelOrder(root);}
}

2. 并发问题

我以设计一个抢优惠券并发场景的解决方案，来举例，那么需要确保系统的高并发处理能力、安全性和可靠性。下面是我想到的解决方案：

架构设计

前端

用户请求：使用Vue.js、React等前端框架进行用户交互设计，确保用户体验。
请求限流：前端可以进行简单的限流，比如每个用户每秒钟只能发起一个请求,用限流器进行限流防抖操作

function throttle(func, wait) {let lastTime = 0;return function(...args) {const now = Date.now();if (now - lastTime >= wait) {lastTime = now;func.apply(this, args);}};
}

后端

1. 进网管网关层
   使用Nginx、Spring Cloud Gateway等，进行负载均衡、限流和日志记录

Nginx

确保Nginx编译时带有 ngx_http_limit_req_module 模块，这是Nginx默认包含的模块。
配置限流:http {limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;server {listen 80;server_name example.com;location /some/api/method {limit_req zone=one burst=5 nodelay;proxy_pass http://backend;}}
}

在这个配置中，limit_req_zone 定义了一个共享内存区域 one，用于保存限流信息。rate=1r/s 表示允许每秒一次请求。burst=5 允许突发流量可以达到5个请求。nodelay 禁用延迟队列。

Spring Cloud Gateway和限流的依赖：

    <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifactId></dependency><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis-reactive</artifactId></dependency>

配置路由并启用限流:

在 application.yml 中配置限流。

    spring:cloud:gateway:routes:- id: some_apiuri: http://backend-servicepredicates:- Path=/some/api/methodfilters:- name: RequestRateLimiterargs:redis-rate-limiter.replenishRate: 1redis-rate-limiter.burstCapacity: 5

确保你有 Redis 依赖和配置: Spring Cloud Gateway 使用 Redis 进行限流，这意味着你需要配置 Redis 相关的依赖和配置

2. 服务层
   应用服务：采用微服务架构，将抢优惠券逻辑放在专门的Coupon Service中。
   使用 Redis/Memcached：用于缓存优惠券信息，以及用户抢券请求，防止数据库压力过大

处理优惠券的缓存逻辑：

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.ValueOperations;
import org.springframework.stereotype.Service;import java.util.concurrent.TimeUnit;
*** Author: 徐寿春* Date:    2024/7/25 17:40* <p>* 名称  处理优惠券的缓存逻辑*/
@Service
public class CouponService {private static final String COUPON_KEY_PREFIX = "coupon:";private static final String USER_REQUEST_KEY_PREFIX = "user_request:";@Autowiredprivate RedisTemplate<String, Object> redisTemplate;// 缓存优惠券信息public void cacheCouponInfo(String couponId, String couponInfo, long timeout, TimeUnit unit) {ValueOperations<String, Object> ops = redisTemplate.opsForValue();ops.set(COUPON_KEY_PREFIX + couponId, couponInfo, timeout, unit);}// 获取缓存的优惠券信息public String getCouponInfo(String couponId) {ValueOperations<String, Object> ops = redisTemplate.opsForValue();return (String) ops.get(COUPON_KEY_PREFIX + couponId);}// 记录用户抢券请求public boolean recordUserRequest(String userId, String couponId, long timeout, TimeUnit unit) {ValueOperations<String, Object> ops = redisTemplate.opsForValue();String key = USER_REQUEST_KEY_PREFIX + userId + ":" + couponId;if (redisTemplate.hasKey(key)) {return false; // 用户已经抢过该券} else {ops.set(key, "requested", timeout, unit);return true;}}
}

处理优惠卷HTTP请求：

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
*** Author: 徐寿春* Date:    2024/7/25 17:40* <p>* 名称  处理优惠券逻辑*/
@RestController
@RequestMapping("/coupons")
public class CouponController {@Autowiredprivate CouponService couponService;@GetMapping("/{couponId}")public String getCouponInfo(@PathVariable String couponId) {String couponInfo = couponService.getCouponInfo(couponId);if (couponInfo == null) {// 从数据库中获取优惠券信息，并缓存起来couponInfo = "Coupon info from DB"; // 这里应该从数据库获取couponService.cacheCouponInfo(couponId, couponInfo, 1, TimeUnit.HOURS);}return couponInfo;}@PostMapping("/{couponId}/request")public String requestCoupon(@PathVariable String couponId, @RequestParam String userId) {boolean success = couponService.recordUserRequest(userId, couponId, 1, TimeUnit.DAYS);if (success) {return "Coupon requested successfully";} else {return "Coupon already requested";}}
}

二, Token Bucket：采用令牌桶算法进行流量控制，限制每秒钟的请求数。

实现令牌桶算法

import org.springframework.stereotype.Component;import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
*** Author: 徐寿春* Date:    2024/7/25 17:40* <p>* 名称  延时线程池生成token*/
@Component
public class TokenBucket {private final int MAX_TOKENS = 10; // 最大令牌数private int tokens;private final ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);public TokenBucket() {this.tokens = MAX_TOKENS;startTokenGenerator();}// 定期生成令牌private void startTokenGenerator() {scheduler.scheduleAtFixedRate(() -> {synchronized (this) {if (tokens < MAX_TOKENS) {tokens++;}System.out.println("Tokens available: " + tokens);}}, 0, 1, TimeUnit.SECONDS); // 每秒钟生成一个令牌}// 请求令牌public synchronized boolean requestToken() {if (tokens > 0) {tokens--;return true;}return false;}
}

请求限流一秒

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;*** Author: 徐寿春* Date:    2024/7/25 17:40* <p>* 名称  限流请求token算法令牌接口*/
@RestController
public class RateLimitController {@Autowiredprivate TokenBucket tokenBucket;@GetMapping("/limited-endpoint")public String limitedEndpoint() {if (tokenBucket.requestToken()) {return "Request processed successfully.";} else {return "Too many requests. Please try again later.";}}
}

3. 数据库层
   关系型数据库：MySQL，用于存储持久化的优惠券数据。
   NoSQL数据库：使用Redis的持久化功能或者MongoDB用于用户临时抢券信息存储。
   MySQL：用于存储需要持久化的、结构化的优惠券数据（长期保存）。
   Redis：用于存储高并发、需要快速读写的用户临时抢券信息（短期保存，高性能）。

4. 并发控制策略
   a. 乐观锁
   在数据库层面使用乐观锁机制避免超发优惠券。例如，在优惠券数量减少的过程中，进行版本号比较，确保操作的原子性，前提是一个库一张表
   b. 分布式锁
   使用Redis分布式锁（或者ZooKeeper等）确保优惠券扣减的原子性，可避免并发超发，但要考虑延时问题
   c. 请求去重
   使用独立的请求ID对每个用户的请求进行去重，防止重复请求，常用的就是id加上ip加上机器放bitmap
   d. 延迟队列
   对于高并发的场景，可以采用Kafka/RabbitMQ等消息队列，将请求进行排队处理，避免瞬时高并发冲击数据库，关于如何利用消息队列延时队列处理有对应的文章我集成框架 - RabbitMQ

5. 流程设计
   用户请求：用户发送抢优惠券请求。
   网关层限流：网关层进行初步限流和鉴权。
   缓存层验证：查询Redis缓存中的优惠券是否仍有剩余。
   如果有，进入下一步。
   如果没有，直接返回抢光提示。
   分布式锁：在Redis中获取分布式锁，确保同一时间只有一个请求进行优惠券扣减操作。
   数据库操作：
   开启事务。
   查询当前优惠券库存。
   扣减库存，更新数据。
   提交事务。
   释放锁：释放Redis分布式锁。
   更新缓存：同步更新Redis中的优惠券库存信息。
   响应用户：返回成功领取的响应。

我能想到就这么多，剩下的自己补充

5. 错误处理与降级策略
   超时处理：设置合理的请求超时时间，超时后提示用户重试，关于系统请求重试机制我写一下吧，以http为例

*** Author: 徐寿春* Date:    2024/7/25 17:58* <p>* 名称  重试demo*/
public class RetryHttpRequest {// 定义重试次数和间隔时间private static final int MAX_RETRIES = 3;private static final int RETRY_INTERVAL_MS = 1000; // 1秒钟public static void main(String[] args) {String urlString = "http://example.com";for (int attempt = 1; attempt <= MAX_RETRIES; attempt++) {try {String response = sendHttpRequest(urlString);System.out.println("请求成功: " + response);// 成功时跳出循环break;} catch (SocketTimeoutException e) {System.out.println("请求超时，尝试重试 " + attempt);if (attempt == MAX_RETRIES) {System.out.println("达到最大重试次数，停止重试");} else {try {Thread.sleep(RETRY_INTERVAL_MS);} catch (InterruptedException ie) {Thread.currentThread().interrupt();System.out.println("线程被中断");}}} catch (IOException e) {System.out.println("请求失败: " + e.getMessage());// 其他IOException错误直接停止重试break;}}}public static String sendHttpRequest(String urlString) throws IOException {URL url = new URL(urlString);HttpURLConnection connection = (HttpURLConnection) url.openConnection();connection.setRequestMethod("GET");connection.setConnectTimeout(5000); // 设置连接超时时间connection.setReadTimeout(5000); // 设置读取超时时间int responseCode = connection.getResponseCode();if (responseCode == HttpURLConnection.HTTP_OK) { // 200表示成功BufferedReader in = new BufferedReader(new InputStreamReader(connection.getInputStream()));String inputLine;StringBuilder response = new StringBuilder();while ((inputLine = in.readLine()) != null) {response.append(inputLine);}in.close();return response.toString();} else {throw new IOException("HTTP 请求失败，响应码: " + responseCode);}}
}

降级策略：当系统压力大或出现问题时，可降级处理，例如直接返回优惠券已抢光，或者进入排队模式，Hystrix太重了我平时用Resilience4j

用Resilience4j实现降级策略

<dependency><groupId>io.github.resilience4j</groupId><artifactId>resilience4j-circuitbreaker</artifactId><version>1.7.1</version>
</dependency>

import io.github.resilience4j.circuitbreaker.CircuitBreaker;
import io.github.resilience4j.circuitbreaker.CircuitBreakerConfig;
import io.github.resilience4j.circuitbreaker.CircuitBreakerRegistry;import java.time.Duration;
import java.util.function.Supplier;*** Author: 徐寿春* Date:    2024/7/25 18:28* <p>* 名称  Resilience4j demo 降级*/
public class Resilience4jExample {public static void main(String[] args) {// 创建配置CircuitBreakerConfig circuitBreakerConfig = CircuitBreakerConfig.custom().failureRateThreshold(50).waitDurationInOpenState(Duration.ofMillis(1000)).slidingWindowSize(2).build();// 创建CircuitBreakerCircuitBreakerRegistry circuitBreakerRegistry = CircuitBreakerRegistry.of(circuitBreakerConfig);CircuitBreaker circuitBreaker = circuitBreakerRegistry.circuitBreaker("couponService");// 定义业务逻辑Supplier<String> getCouponSupplier = CircuitBreaker.decorateSupplier(circuitBreaker, () -> {if (System.currentTimeMillis() % 2 == 0) {throw new RuntimeException("System is busy");}return "Coupon acquired!";});// 定义降级逻辑Supplier<String> fallbackSupplier = () -> "Coupons are sold out, please try again later.";// 执行并处理降级String result = CircuitBreaker.decorateSupplier(circuitBreaker, getCouponSupplier).recover(fallbackSupplier).get();System.out.println(result);}
}

Resilience4j 这块我写一下吧，回头做个和Hystrix的比较

   <dependency><groupId>io.github.resilience4j</groupId><artifactId>resilience4j-spring-boot2</artifactId><version>1.7.0</version></dependency>

在 application.yml 或 application.properties 中配置 Resilience4j：

   resilience4j:circuitbreaker:configs:default:registerHealthIndicator: trueslidingWindowSize: 100permittedNumberOfCallsInHalfOpenState: 10minimumNumberOfCalls: 10waitDurationInOpenState: 10sfailureRateThreshold: 50eventConsumerBufferSize: 10instances:backendA:baseConfig: default----
registerHealthIndicator:
解释: 当设置为 true 时，Resilience4j 会注册一个健康指示器（Health Indicator），使其可用于监控框架，例如 Spring Boot Actuator。slidingWindowSize:
解释: 滑动窗口的大小。表示断路器的滑动窗口会包含多少次调用。100表明滑动窗口包含100次调用。permittedNumberOfCallsInHalfOpenState:
解释: 半开启状态时允许的最大调用次数。当断路器从开启状态转换为半开启状态时，允许通过的最大调用次数。10表示允许10次调用。minimumNumberOfCalls:
解释: 在评价断路器状态之前，必须记录的最少调用次数。如果设为 10，那么在至少有10次调用后，才会根据配置的其他条件再来决定断路器的状态。waitDurationInOpenState:
解释: 断路器在开启状态保持的时间长度。10s 表示在断路器转换为开放状态后，10秒钟后将进入半开启状态。failureRateThreshold:
解释: 失败率的阈值。定义了错误调用率的最大百分比。如果设为 50，那么只有当失败调用比例超过50%时，断路器才会打开。eventConsumerBufferSize:
解释: 事件消费者的缓冲区大小，表示事件处理队列的最大容量。设为 10的话，表示最多可以处理10个事件。如果满了，新事件将覆盖最老的事件。

控制层

   @RestController@RequestMapping("/api")public class BackendController {private final BackendService backendService;@Autowiredpublic BackendController(BackendService backendService) {this.backendService = backendService;}@GetMapping("/doSomething")public ResponseEntity<String> doSomething() {String result = backendService.doSomething();return new ResponseEntity<>(result, HttpStatus.OK);}}

服务实现

   @Servicepublic class BackendServiceImpl implements BackendService {@Override@CircuitBreaker(name = "backendA", fallbackMethod = "fallback")public String doSomething() {// 这里模拟一个可能会失败的调用if (new Random().nextBoolean()) {throw new RuntimeException("Service failed");}return "Service is successful";}// 断路器打开时的回退方法public String fallback(Throwable t) {return "Service is down, please try again later";}}

 resilience4j:retry:instances:backendA:maxAttempts: 3waitDuration: 500msretryExceptions:- java.io.IOException- java.util.concurrent.TimeoutExceptionretry: 这部分配置是关于重试机制的。backendA: 这是特定于某个服务或组件（在这里是 backendA）的配置。这里列出的所有配置都只适用于 backendA。maxAttempts: 3: 这是最大重试次数。当对 backendA 进行操作失败时，最多会重试两次（加上第一次尝试，总共三次）。也就是说，最多会允许三次失败尝试。waitDuration: 500ms: 重试之间的等待时间是 500 毫秒。如果一次尝试 backendA 失败，那么在最小 500 毫秒后，库会再次尝试。retryExceptions: 这是一个需要触发重试的异常列表。如果遇到列出的异常，重试机制就会生效。- java.io.IOException: 遇到 java.io.IOException 异常时，会触发重试。- java.util.concurrent.TimeoutException: 遇到 java.util.concurrent.TimeoutException 异常时，也会触发重试。

修改服务实现：

   @Servicepublic class BackendServiceImpl implements BackendService {@Override@Retry(name = "backendA", fallbackMethod = "fallback")public String doSomething() {// 这里模拟一个可能会失败的调用if (new Random().nextBoolean()) {throw new RuntimeException("Service failed");}return "Service is successful";}public String fallback(Throwable t) {return "Service is down, please try again later";}}

6. 监控与报警：使用Prometheus、Grafana等进行系统监控，设置报警阈值，及时发现并处理问题，这部分回头补吧