必修-场景题

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_api
            uri: http://backend-service
            predicates:
            - Path=/some/api/method
            filters:
            - name: RequestRateLimiter
              args:
                redis-rate-limiter.replenishRate: 1
                redis-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:";

    @Autowired
    private 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 {

    @Autowired
    private 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 {

    @Autowired
    private 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();

        // 创建CircuitBreaker
        CircuitBreakerRegistry 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: true
           slidingWindowSize: 100
           permittedNumberOfCallsInHalfOpenState: 10
           minimumNumberOfCalls: 10
           waitDurationInOpenState: 10s
           failureRateThreshold: 50
           eventConsumerBufferSize: 10
       instances:
         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;
   
       @Autowired
       public BackendController(BackendService backendService) {
           this.backendService = backendService;
       }

       @GetMapping("/doSomething")
       public ResponseEntity<String> doSomething() {
           String result = backendService.doSomething();
           return new ResponseEntity<>(result, HttpStatus.OK);
       }
   }

服务实现

   @Service
   public 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: 3
           waitDuration: 500ms
           retryExceptions:
             - java.io.IOException
             - java.util.concurrent.TimeoutException


 
retry: 这部分配置是关于重试机制的。

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 异常时，也会触发重试。

修改服务实现：

   @Service
   public 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等进行系统监控，设置报警阈值，及时发现并处理问题，这部分回头补吧

原文地址：https://blog.csdn.net/weixin_44550490/article/details/140694110

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！