题目

时间:2024-07-11持续时间:80分钟，算法写了快50min 总体体验:面试官很好，循循善诱，没有思路的也有提示

问题: 1.自我介绍，实习内容

2.询问简历中的RBAC模型是什么意思，讲一下

3.系统用户量多少(提到了会查出很多ip)ip这么多如何存储，mysql吗，看你提到了es。解释使用es存储

5.对于mysql你大概了解多少。打过数据库比赛，对mysql比较了解在数据库比赛中你负责那一部分?。简单介绍了实现了什么，buffer，索引等

7.mysql做一次查询经历了什么。互相理解出了问题，后来讲了讲buffer和火山模型

8.写入语句的执行(面试官想问的是能不能直接写磁盘，性能如何体现答所有交互都跟buffer交互，buffer被替换下去的时候会刷盘，保证持久，如果突然中断有redo log保证持久

提到了redo log，redo log的作用是什么。讲了讲redo的工作原理，如何保证持久10.数据库的隔离级别有哪些? 11.每一种隔离级别都有哪些问题?

12.详细解释下读已提交

13.场景题:需要设计一个权限任务，某个人只能拥有这个权限7天，如何设计。

开始答的id +权限放redis，但其实有逻辑漏洞14.又问如果希望查找这个权限都谁拥有那就不能只存redis了，需要持久化，简单说了。一下依靠后台线程去删除，可以用延时队列15.延时队列如何实现。

提到只用过rabbitmq，rabbitmq中使用死信队列实现，讲了下如何实现

16.你们这里索引一般怎么用? 需要快速查找，还不违反最左前缀的就可以考虑加一个

17.最左前缀是什么。大概讲了下b+树的结构，举例子说明了一下18.a-b-c建立索引，a精确，b是"%%'，可以走索引吗。

19.了解过go吗，讲讲进程线程的区别，对协程有什么了解；进程线程区别；协程轻量级线程，不设计用户态内核态切换，跟java线程对比，由go的线程调度器调度； 20.算法题目（Java）:

• 最长回文子序列。
• 岛屿数量。

题目来自原主分享：https://www.nowcoder.com/feed/main/detail/e56ca5688e3d4f64b7c91ba5f5f0cb71

参考回答

自我介绍和实习内容

「面试官」：欢迎来到今天的面试。首先，请你做一个简短的自我介绍，并谈谈你的实习内容。 『求职者』：谢谢面试官。我是[您的名字]，是[您的学校]计算机科学专业的学生。我最近在[公司名称]实习，担任后端开发实习生。 在实习期间，我主要负责了以下工作：

1. 参与了公司权限管理系统的开发，使用了RBAC模型来实现灵活的权限控制。
2. 优化了系统的数据存储和查询性能，包括使用ElasticSearch来处理大量的IP地址数据。
3. 参与了数据库性能优化，包括索引设计和查询优化。
4. 开发了一些RESTful API，用于前后端数据交互。

这段实习经历让我对企业级应用开发有了更深入的理解，特别是在数据库和系统架构方面获得了宝贵的实践经验。

RBAC模型解释

「面试官」：听起来你的实习经历很丰富。你提到了RBAC模型，能详细解释一下这是什么吗？ 『求职者』：当然。RBAC全称是基于角色的访问控制（Role-Based Access Control）。这是一种广泟使用的权限管理模型，主要包含以下几个核心概念：

1. 用户（User）：系统的实际使用者。
2. 角色（Role）：一组权限的集合。
3. 权限（Permission）：执行特定操作的能力。
4. 对象（Object）：被访问或操作的实体。

RBAC的核心思想是：不直接给用户分配权限，而是通过角色作为中间层。具体工作流程是：

1. 首先定义各种角色，并为每个角色分配相应的权限。
2. 然后将用户与角色关联，用户就继承了该角色的所有权限。

这种方式的优点是：

• 简化了权限管理：当有大量用户时，直接管理每个用户的权限会非常复杂。而通过角色，我们可以更容易地管理和分配权限。
• 提高了灵活性：可以快速调整用户的权限，只需要更改用户的角色即可。
• 降低了错误率：集中管理角色的权限，减少了直接操作单个用户权限可能带来的错误。

在我们的项目中，我们使用RBAC模型成功地实现了一个灵活且易于管理的权限系统。

IP存储和ElasticSearch使用

「面试官」：理解了。你刚才提到系统中有大量的IP地址需要存储，为什么选择使用ElasticSearch而不是MySQL来存储这些数据？ 『求职者』：选择使用ElasticSearch而不是MySQL来存储大量IP地址数据，主要基于以下几个考虑：

1. 查询性能：
   • ElasticSearch是一个全文搜索引擎，对于大量数据的快速搜索和过滤有优势。
   • 特别是对于IP地址的范围查询或模糊匹配，ElasticSearch可以提供更好的性能。
2. 扩展性：
   • ElasticSearch天生就是为分布式设计的，可以轻松扩展到多个节点。
   • 当数据量继续增长时，我们可以通过添加节点来提高存储容量和查询性能。
3. 灵活的数据模型：
   • ElasticSearch是文档型数据库，对于半结构化或非结构化数据的存储更灵活。
   • 我们可以轻松地为IP地址添加额外的元数据，而不需要修改表结构。
4. 实时性：
   • ElasticSearch提供近实时的索引和搜索能力，这对于需要快速反应的场景（如安全监控）很有用。
5. 分析能力：
   • ElasticSearch提供强大的聚合和分析功能，可以轻松地进行复杂的统计分析。
6. 与日志系统的集成：
   • 如果系统还涉及日志分析，ElasticSearch作为ELK（Elasticsearch, Logstash, Kibana）栈的一部分，可以更好地集成。

当然，这个选择也有一些权衡。比如ElasticSearch在事务处理和数据一致性方面不如关系型数据库。但对于IP地址这种主要用于查询和分析的数据，ElasticSearch的优势更为明显。 在实际应用中，我们可能会采用混合架构，使用MySQL存储核心业务数据，而使用ElasticSearch存储和检索IP地址等需要高性能搜索的数据。

MySQL查询过程

「面试官」：你提到参加过数据库比赛，能详细讲解一下MySQL执行一次查询的过程吗？ 『求职者』：当然，我很乐意解释MySQL执行查询的过程。这个过程涉及多个组件和步骤，我们可以从查询到达服务器开始讲起：

1. 连接器：
   • 负责建立、管理和关闭与客户端的连接。
   • 进行身份认证。
2. 查询缓存：
   • 检查查询是否在缓存中。如果命中，直接返回结果。
   • 注意：MySQL 8.0后已移除此功能，因为其效率较低。
3. 解析器：
   • 对SQL语句进行词法分析和语法分析。
   • 构建语法树。
4. 预处理器：
   • 进一步检查解析树，进行语义分析。
   • 检查表和列是否存在，解析名字和别名，检查权限。
5. 查询优化器：
   • 决定使用哪个索引。
   • 决定各个表的连接顺序。
   • 将子查询转化成连接。
   • 生成执行计划。
6. 执行器：
   • 根据执行计划，调用存储引擎的API来执行查询。
   • 对于SELECT语句，将结果返回给客户端。
7. 存储引擎：
   • 负责数据的存储和提取。
   • 常用的有InnoDB、MyISAM等。

在这个过程中，**缓冲池（Buffer Pool）**扮演着重要角色：

• 它缓存了表数据、索引数据、插入缓冲、锁信息等。
• 大多数的读操作都会先从缓冲池中查找，如果找不到才会去磁盘读取。

而火山模型是查询执行的一种模型：

• 查询被分解成一系列的操作符。
• 每个操作符实现一个next()方法，用于获取下一个元组。
• 数据以流的形式从底层操作符向上传递，直到返回最终结果。

这种模型的优点是灵活性高，易于实现复杂的查询操作，但可能会有一些性能开销。

写入操作和持久性保证

「面试官」：很好。那么对于写入操作，MySQL是如何保证性能和数据持久性的呢？ 『求职者』：对于写入操作，MySQL（特别是InnoDB存储引擎）采用了一系列机制来平衡性能和数据持久性：

1. 缓冲池（Buffer Pool）：
   • 所有的写操作首先是对缓冲池中的数据进行修改，而不是直接写入磁盘。
   • 这大大提高了写入性能，因为内存操作远快于磁盘I/O。
2. Change Buffer：
   • 对于非唯一二级索引的插入或更新操作，不是每次都直接更新索引页。
   • 而是将这些操作缓存在change buffer中，等到下次读取该页时再进行合并。
   • 这减少了随机I/O，提高了写入性能。
3. 日志文件：
   • redo log（重做日志）：记录了对数据页的修改。
   • undo log（回滚日志）：用于事务回滚和MVCC。
4. 两阶段提交：
   • 在事务提交时，先将redo log写入磁盘（prepare阶段）。
   • 然后修改binlog。
   • 最后完成redo log的写入（commit阶段）。
5. 刷盘策略：
   • 脏页不会立即刷新到磁盘，而是通过后台线程或某些条件触发时刷新。
   • 可以通过参数如innodb_flush_log_at_trx_commit来控制刷盘行为。

特别说明redo log的作用：

1. 保证持久性：即使系统崩溃，也可以通过redo log恢复未刷盘的修改。
2. 提高性能：将随机写转化为顺序写，redo log是追加写入的。
3. 实现崩溃恢复：系统重启时，可以根据redo log重放未完成的事务。

redo log的工作原理：

1. 当事务修改数据时，首先将修改写入redo log buffer。
2. 根据设置，redo log buffer会以不同频率刷新到redo log文件。
3. 在事务提交时，确保redo log已经写入磁盘。
4. 如果系统崩溃，重启时会检查redo log，重放未完成的事务。

通过这些机制，MySQL既保证了数据的持久性，又实现了高效的写入性能。即使在突然断电的情况下，已提交的事务也不会丢失数据。

数据库隔离级别

「面试官」：非常详细的解释。那么你能说说数据库的隔离级别有哪些，以及每种隔离级别可能出现的问题吗？ 『求职者』：当然，数据库的隔离级别主要有四种，从低到高依次是：

1. 读未提交（Read Uncommitted）
2. 读已提交（Read Committed）
3. 可重复读（Repeatable Read）
4. 串行化（Serializable）

每种隔离级别可能出现的问题：

1. 读未提交（Read Uncommitted）：
   • 脏读（Dirty Read）：可以读取未提交的数据。
   • 不可重复读（Non-repeatable Read）：在同一事务内，多次读取同一数据可能得到不同结果。
   • 幻读（Phantom Read）：在同一事务内，多次查询返回的结果集不同。
2. 读已提交（Read Committed）：
   • 不可重复读（Non-repeatable Read）：在同一事务内，多次读取同一数据可能得到不同结果。
   • 幻读（Phantom Read）：在同一事务内，多次查询返回的结果集不同。
3. 可重复读（Repeatable Read）：
   • 幻读（Phantom Read）：在某些实现中可能出现，但在InnoDB中通过多版本并发控制（MVCC）解决了这个问题。
4. 串行化（Serializable）：
   • 理论上没有并发问题，但性能最低。

这里详细解释一下**读已提交（Read Committed）**级别：

• 在这个级别下，一个事务只能看见已经提交的事务所做的修改。
• 它解决了脏读的问题，但仍然可能出现不可重复读和幻读。

举个例子：

1. 事务A开始，读取一行数据。
2. 事务B开始，修改该行数据并提交。
3. 事务A再次读取同一行数据，会看到事务B的修改。

这就是不可重复读的现象。对于幻读，如果事务B插入了新的行，事务A可能在后续的查询中看到这些新行，这就是幻读。 Read Committed通过版本读来实现：

• 每个查询都会生成一个新的快照。
• 事务只能看到在它开始之前已经提交的数据，以及它自己所做的修改。

这个级别是很多数据库系统的默认级别（如Oracle），因为它在一致性和性能之间取得了很好的平衡。

权限任务设计

「面试官」：很好的解释。现在我们来看一个实际的场景题：假设需要设计一个权限系统，要求某个用户只能拥有某个特定权限7天，你会如何设计这个系统？ 『求职者』：这是一个很有趣的设计问题。我们需要考虑权限的时效性、查询效率和系统的可扩展性。我会这样设计：

1. 数据存储：
   • 使用关系型数据库（如MySQL）存储用户权限的基本信息。
   • 表结构可能如下：

CREATE TABLE user_permissions (
    id INT PRIMARY KEY AUTO_INCREMENT,
    user_id INT,
    permission_id INT,
    start_time TIMESTAMP,
    end_time TIMESTAMP,
    INDEX idx_user_permission (user_id, permission_id)
);

2. 缓存层：
   • 使用Redis缓存活跃的权限信息。
   • 键值对形式：user:{userId}:permission:{permissionId} -> expiration timestamp
3. 权限分配流程：
   • 当分配权限时，在MySQL中插入一条记录。
   • 同时在Redis中设置一个带有7天过期时间的键值对。
4. 权限检查流程：
   • 首先检查Redis是否存在相应的键。
   • 如果存在，表示用户有权限。
   • 如果不存在，查询MySQL数据库。
   • 如果在MySQL中找到有效的权限记录，更新Redis缓存。
5. 定期清理：
   • 使用一个后台任务定期清理过期的MySQL记录。
   • 可以使用类似Quartz的调度框架来执行这个任务。
6. 查找特定权限的所有用户：
   • 这个操作主要通过MySQL来完成。
   • 可以使用类似以下的SQL：

SELECT user_id FROM user_permissions 
WHERE permission_id = ? AND end_time > CURRENT_TIMESTAMP;

7. 优化考虑：
   • 对于频繁访问的权限，可以在应用层增加本地缓存。
   • 使用读写分离来提高数据库性能。
8. 容错处理：
   • 如果Redis不可用，系统可以降级为只读取MySQL。
   • 实现重试机制，确保Redis和MySQL的数据最终一致。

这个设计结合了数据库的持久性和Redis的高性能，可以有效地处理大量的权限检查请求，同时保证了数据的一致性和可靠性。 「面试官」：你提到了使用后台任务清理过期记录，能详细说说如何实现这个延时队列吗？ 『求职者』：当然，实现延时队列有多种方式，我之前主要使用过RabbitMQ来实现。在RabbitMQ中，我们可以通过**死信队列（Dead Letter Queue）**来实现延时队列。具体步骤如下：

1. 创建死信交换机（Dead Letter Exchange）：
   • 这是一个普通的交换机，用于接收过期的消息。
2. 创建主队列：
   • 设置消息的 TTL（Time To Live）。
   • 配置死信交换机和路由键。
3. 创建死信队列：
   • 绑定到死信交换机上。
4. 消息流程：
   • 发送消息到主队列，设置过期时间为7天。
   • 7天后，消息过期，被发送到死信交换机。
   • 死信交换机将消息路由到死信队列。
   • 消费者从死信队列中获取消息，进行清理操作。

具体的代码实现可能如下（使用Java和Spring AMQP）：

@Configuration
public class RabbitConfig {

    @Bean
    public Queue mainQueue() {
        Map<String, Object> args = new HashMap<>();
        args.put("x-dead-letter-exchange", "deadLetterExchange");
        args.put("x-dead-letter-routing-key", "deadLetter");
        args.put("x-message-ttl", 7 * 24 * 60 * 60 * 1000); // 7天
        return new Queue("mainQueue", true, false, false, args);
    }

    @Bean
    public Queue deadLetterQueue() {
        return new Queue("deadLetterQueue");
    }

    @Bean
    public DirectExchange deadLetterExchange() {
        return new DirectExchange("deadLetterExchange");
    }

    @Bean
    public Binding deadLetterBinding() {
        return BindingBuilder.bind(deadLetterQueue())
                .to(deadLetterExchange()).with("deadLetter");
    }
}

消费者代码：

@Component
public class DeadLetterConsumer {

    @RabbitListener(queues = "deadLetterQueue")
    public void receiveDeadLetter(Message message) {
        // 处理过期的权限，例如从数据库中删除
        String userId = message.getMessageProperties().getHeader("userId");
        String permissionId = message.getMessageProperties().getHeader("permissionId");
        // 执行清理操作
    }
}

这种方式的优点是：

• 可以精确控制延迟时间。
• 可靠性高，即使在系统崩溃后重启，任务也不会丢失。
• 可以轻松处理大量的延迟任务。

缺点是可能需要占用较多的内存，特别是当延迟时间较长时。在实际应用中，可能需要结合具体的业务需求和系统负载来选择最适合的实现方式。 「面试官」：非常好。现在让我们谈谈索引。在你的项目中，你们是如何使用索引的？什么是最左前缀原则？ 『求职者』：在我们的项目中，索引的使用主要遵循以下原则：

1. 频繁查询的列：对经常出现在WHERE子句中的列创建索引。
2. 外键列：在外键列上创建索引，以加速连接操作。
3. 排序和分组列：对经常用于ORDER BY和GROUP BY的列创建索引。
4. 唯一性约束：对需要保证唯一性的列创建唯一索引。
5. 覆盖索引：尽可能创建包含所有查询所需字段的索引，以实现索引覆盖。
6. 前缀索引：对于长字符串列，考虑使用前缀索引。
7. 复合索引：对多个列同时创建索引，注意考虑列的顺序。

关于最左前缀原则，这是复合索引的一个重要特性：

• 最左前缀原则指的是，在使用复合索引时，MySQL会从左到右依次使用索引中的字段。
• 例如，如果创建了一个(a, b, c)的复合索引：
  • 查询条件包含 a，或者 a 和 b，或者 a、b 和 c，都可以使用该索引。
  • 但如果查询条件只有 b，或者 b 和 c，则无法使用该索引。
• 这个原则的原因是B+树的数据结构特性决定的。B+树按照从左到右的顺序建立搜索树。

举个例子：

CREATE INDEX idx_abc ON table_name (a, b, c);

-- 可以使用索引
SELECT * FROM table_name WHERE a = 1;
SELECT * FROM table_name WHERE a = 1 AND b = 2;
SELECT * FROM table_name WHERE a = 1 AND b = 2 AND c = 3;

-- 无法使用索引
SELECT * FROM table_name WHERE b = 2;
SELECT * FROM table_name WHERE c = 3;

理解最左前缀原则对于优化查询和设计合适的索引非常重要。它可以帮助我们在创建复合索引时，合理安排列的顺序，以最大化索引的效用。 「面试官」：很好。那么如果有一个复合索引(a, b, c)，查询条件是 a 精确匹配，b 是模糊匹配（like '%xx%'），c 是精确匹配，这个查询能否使用到索引？ 『求职者』：这是一个很好的问题，涉及到索引的使用细节。让我们逐步分析：

1. 对于复合索引(a, b, c)：
   • a 列是精确匹配，可以使用索引。
   • b 列是模糊匹配，而且是 '%xx%' 这种形式。
   • c 列是精确匹配。
2. 索引的使用情况：
   • 索引可以用于 a 列的查询条件。
   • 索引无法用于 b 列的查询条件，因为 '%xx%' 这种模糊查询无法利用索引。
   • 由于最左前缀原则，c 列的索引也无法使用。
3. 具体解释：
   • MySQL 可以使用索引快速定位到 a 列匹配的记录。
   • 但是对于 b 列的 '%xx%' 查询，数据库必须扫描所有 a 匹配的记录，进行逐行的模糊匹配。
   • 即使 c 列是精确匹配，由于 b 列的模糊匹配打断了索引的连续性，c 列的索引也无法使用。
4. 查询优化器的行为：
   • 查询优化器可能会选择使用索引到 a 列，然后对结果集进行全表扫描来处理 b 和 c 的条件。
   • 或者，如果 a 的选择性不够高（即 a 匹配的记录数量很大），优化器可能会选择完全不使用索引，直接全表扫描。
5. 改进建议：
   • 如果可能，尽量避免在中间列使用 '%xx%' 这样的模糊查询。
   • 考虑将索引拆分，例如 (a, c) 和 (a, b) 两个独立的索引。
   • 如果 b 列的模糊查询非常重要，可以考虑使用全文索引或搜索引擎（如 Elasticsearch）来处理这类查询。

总结：在这种情况下，索引只能部分使用（只用于 a 列），而无法充分利用 (a, b, c) 的完整索引结构。这提醒我们在设计索引和编写查询时，要特别注意模糊查询对索引使用的影响。 「面试官」：非常好的解答。现在让我们转向一些更广泛的话题。你了解Go语言吗？能谈谈进程、线程和协程的区别吗？ 『求职者』：虽然我的主要开发语言是Java，但我对Go语言也有一定了解。让我来谈谈进程、线程和协程的区别：

1. 进程（Process）：
   • 进程是操作系统分配资源的基本单位。
   • 每个进程都有自己的内存空间、文件描述符等资源。
   • 进程间通信（IPC）相对复杂和昂贵。
   • 进程切换开销大，涉及到上下文切换和缓存刷新。
2. 线程（Thread）：
   • 线程是操作系统调度的基本单位。
   • 同一进程中的线程共享进程的内存空间和资源。
   • 线程间通信相对简单，可以直接访问共享内存。
   • 线程切换比进程切换开销小，但仍涉及上下文切换。
3. 协程（Goroutine in Go）：
   • 协程是用户态的轻量级线程，由语言或库层面实现。
   • 多个协程可以在一个操作系统线程上运行。
   • 协程切换非常轻量，不涉及操作系统的上下文切换。
   • 协程间通信通常通过 channel（在 Go 中）等机制实现。

主要区别：

1. 资源占用：
   • 进程 > 线程 > 协程
2. 切换成本：
   • 进程切换 > 线程切换 > 协程切换
3. 并发性：
   • 协程支持更高的并发数量，可以轻松创建上万个协程。
4. 调度方式：
   • 进程和线程由操作系统调度。
   • 协程由语言运行时或用户程序调度。
5. 通信方式：
   • 进程间通信复杂（如管道、消息队列）。
   • 线程间可以通过共享内存通信。
   • 协程通常使用特定的通信原语（如 Go 的 channel）。

Go语言的协程（Goroutine）特点：

1. 轻量级：创建和销毁的开销很小。
2. 非抢占式调度：协程主动让出控制权。
3. 通过 channel 进行通信：遵循 "不要通过共享内存来通信，而要通过通信来共享内存" 的原则。

相比Java线程，Go的协程有以下优势：

• 创建成本更低。
• 可以支持更多的并发单元。
• 调度更加灵活，不依赖操作系统线程调度。

然而，Java也在不断发展，如Project Loom就旨在为Java引入轻量级线程（类似于协程的概念），以提高Java的并发性能。 「面试官」：非常好的比较。现在我们来做两道算法题。第一题是求最长回文子序列，第二题是计算岛屿数量。你能用Java来实现这两个算法吗？ 『求职者』：当然，我很乐意实现这两个算法。让我们一个一个来看。

1. 最长回文子序列

这个问题可以使用动态规划来解决。我们定义 dp[i][j] 为字符串从索引 i 到 j 的最长回文子序列的长度。

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        // 所有单个字符都是长度为1的回文序列
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        
        // 填充dp数组
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && len == 2) {
                    dp[i][j] = 2;
                } else if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[0][n-1];
    }
}

这个算法的时间复杂度是 O(n2)，空间复杂度也是 O(n2)，其中 n 是字符串的长度。

2. 岛屿数量

这个问题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。这里我们使用DFS的方法。

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int count = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] != '1') {
            return;
        }
        
        // 标记已访问
        grid[i][j] = '0';
        
        // 访问四个方向
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
}

这个算法的时间复杂度是 O(m_n)，其中 m 和 n 分别是网格的行数和列数。空间复杂度在最坏情况下（整个网格都是陆地）是 O(m_n)，因为递归的深度可能达到 m*n。 这两个算法都展示了不同的问题解决策略：

1. 最长回文子序列使用了动态规划，它通过构建一个表来存储子问题的解，从而避免重复计算。
2. 岛屿数量问题使用了深度优先搜索，它通过递归地探索相连的陆地，并在过程中标记已访问的区域，从而高效地计算岛屿数量。

这些策略在很多其他问题中也能找到应用，理解它们的工作原理对于解决各种算法问题都很有帮助。 「面试官」：非常好的解答。你能解释一下为什么在岛屿数量问题中，我们可以直接修改输入的grid数组，而不需要额外的visited数组来标记已访问的位置吗？ 『求职者』：这是一个很好的问题，涉及到算法实现的一些细节和权衡。在岛屿数量问题中，我们确实可以直接修改输入的grid数组，而不需要额外的visited数组。这种做法有几个原因：

1. 空间效率：
   • 直接修改输入数组避免了创建额外的visited数组，节省了空间。
   • 对于大规模的grid，这种方法可以显著减少内存使用。
2. 时间效率：
   • 直接修改数组比维护一个单独的visited数组更快。
   • 我们不需要额外的检查visited数组的操作。
3. 简化代码：
   • 代码变得更简洁，不需要处理额外的数据结构。
4. 问题特性：
   • 在这个问题中，一旦我们访问了一个陆地格子，我们就不需要再次访问它。
   • 将'1'改为'0'既标记了已访问，又防止了重复计算。
5. 输入数据的使用方式：
   • 在很多情况下，尤其是在面试场景，我们假设输入数据是一次性使用的，不需要保留原始状态。

然而，这种方法也有一些潜在的缺点：

1. 修改输入数据：
   • 在某些场景下，修改输入数据可能不被允许或不合适。
   • 如果后续还需要使用原始数据，这种方法就不适用。
2. 可读性：
   • 对于不熟悉这种技巧的人来说，直接修改输入可能会造成困惑。
3. 副作用：
   • 如果函数的调用者期望输入保持不变，这种方法可能会导致意外的副作用。

在实际的工程实践中，我们通常会根据具体情况来决定是否修改输入数据：

• 如果是一次性使用的数据，直接修改通常是可以的。
• 如果需要保留原始数据，或者函数设计原则要求不修改输入，那么使用额外的visited数组会更合适。

在面试中，我们可以先询问面试官是否可以修改输入数据。如果允许，那么直接修改是一个很好的优化。如果不允许，我们就需要使用额外的空间来标记已访问的位置。 总的来说，这个例子很好地说明了在算法设计中，我们常常需要在空间效率、时间效率和代码清晰度之间做出权衡。 「面试官」：非常好的解释。看来你不仅理解了算法的实现，还能深入思考其中的权衡。那么，我们的面试就到此结束了。你有什么问题要问我的吗？ 『求职者』：谢谢您的肯定。我确实有几个问题想请教：

1. 贵公司在技术栈选择上有什么特别的考虑吗？特别是在处理高并发和大数据量方面。
2. 对于新入职的员工，公司有什么培训或成长计划吗？
3. 在当前的团队中，您认为最大的技术挑战是什么？
4. 公司如何看待工作与生活的平衡？有远程工作的政策吗？
5. 在接下来的6-12个月里，团队或公司有什么重要的项目或目标吗？

这些问题可以帮助我更好地了解公司的技术方向、文化和发展前景。非常感谢您的时间和宝贵的反馈。 「面试官」：这些都是很好的问题。[面试官会根据公司实际情况回答这些问题]。感谢你今天的表现，我们会尽快给你反馈。祝你好运！ 『求职者』：非常感谢您的回答和这次宝贵的面试机会。我对贵公司的技术实力和文化氛围留下了深刻的印象。我会耐心等待您的反馈，也希望有机会能加入您的团队，为公司的发展贡献自己的力量。再次感谢您的时间，祝您工作顺利！