必修-场景题
场景题
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);
}
};
}
后端
- 进网管网关层
使用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 相关的依赖和配置
- 服务层
应用服务:采用微服务架构,将抢优惠券逻辑放在专门的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.";
}
}
}
-
数据库层
关系型数据库:MySQL,用于存储持久化的优惠券数据。
NoSQL数据库:使用Redis的持久化功能或者MongoDB用于用户临时抢券信息存储。
MySQL:用于存储需要持久化的、结构化的优惠券数据(长期保存)。
Redis:用于存储高并发、需要快速读写的用户临时抢券信息(短期保存,高性能)。 -
并发控制策略
a. 乐观锁
在数据库层面使用乐观锁机制避免超发优惠券。例如,在优惠券数量减少的过程中,进行版本号比较,确保操作的原子性,前提是一个库一张表
b. 分布式锁
使用Redis分布式锁(或者ZooKeeper等)确保优惠券扣减的原子性,可避免并发超发,但要考虑延时问题
c. 请求去重
使用独立的请求ID对每个用户的请求进行去重,防止重复请求,常用的就是id加上ip加上机器放bitmap
d. 延迟队列
对于高并发的场景,可以采用Kafka/RabbitMQ等消息队列,将请求进行排队处理,避免瞬时高并发冲击数据库,关于如何利用消息队列延时队列处理有对应的文章我集成框架 - RabbitMQ -
流程设计
用户请求:用户发送抢优惠券请求。
网关层限流:网关层进行初步限流和鉴权。
缓存层验证:查询Redis缓存中的优惠券是否仍有剩余。
如果有,进入下一步。
如果没有,直接返回抢光提示。
分布式锁:在Redis中获取分布式锁,确保同一时间只有一个请求进行优惠券扣减操作。
数据库操作:
开启事务。
查询当前优惠券库存。
扣减库存,更新数据。
提交事务。
释放锁:释放Redis分布式锁。
更新缓存:同步更新Redis中的优惠券库存信息。
响应用户:返回成功领取的响应。
我能想到就这么多,剩下的自己补充
- 错误处理与降级策略
超时处理:设置合理的请求超时时间,超时后提示用户重试,关于系统请求重试机制我写一下吧,以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";
}
}
- 监控与报警:使用Prometheus、Grafana等进行系统监控,设置报警阈值,及时发现并处理问题,这部分回头补吧
原文地址:https://blog.csdn.net/weixin_44550490/article/details/140694110
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!