二叉搜索树转双向链表与广告库索引服务设计

"字节跳动2018校招后端方向的面试题，包含两道问答题，一道关于二叉搜索树转双向链表的算法问题，另一道是广告库索引服务的设计问题。" 第一部分：二叉搜索树转双向链表 在给定的代码中，用于将二叉搜索树转换为有序双向链表的函数存在一些问题。首先，我们需要理解二叉搜索树的特性，其左子节点小于根节点，右子节点大于根节点。转换的目标是使所有节点按值顺序连接。 1. 代码中缺少对二叉树遍历的终止条件，导致无限循环。在第19行，应添加`root=root->left;`的判断条件，当`root->left`为空时结束左子树的遍历，改为`if(root->left)`。 2. 在第22行，`root=s.top();`和第24行`listHead=root;`之后，应当先处理当前节点的左右指针，再进行其他操作。否则，`root->right`可能未被正确设置，影响后续节点的连接。 3. 第27行，`listLastNode->right=root;`之后，应该设置`root->left=listLastNode;`以形成双向链表。这是转换过程中非常关键的一步，确保链表节点间的双向链接。 4. 考虑到双向链表的最后一个元素的`right`指针应为空，因此在第31行后，应设置`listLastNode->right=NULL;`。 修正后的代码示例： ```cpp TreeNode* Convert(TreeNode* root) { if (root == NULL) return root; TreeNode* listHead = NULL; TreeNode* listLastNode = NULL; stack<TreeNode*> s; while (root || !s.empty()) { while (root) { root = root->left; s.push(root); } root = s.top(); s.pop(); if (listHead == NULL) { listHead = root; } else { listLastNode->right = root; root->left = listLastNode; } listLastNode = root; root = root->right; if (root) { // 避免丢失右子节点 s.push(root); root = NULL; } } listLastNode->right = NULL; // 设置最后一个节点的right指针为空 return listHead; } ``` 第二部分：广告库索引服务设计 设计一个广告库索引模块，以满足多线程请求、数据热更新、大量广告策略和创意以及高并发要求，我们可以采用以下方案： 1. **数据结构设计**：使用哈希表或B+树作为索引结构，因为它们具有快速查找和插入的能力。哈希表适用于等值查询，B+树则适用于范围查询。每个广告策略对应一个键，键由定向属性（地域、运营商等）组合而成。 2. **多线程支持**：采用线程安全的数据结构，如`std::unordered_map`（C++）或`ConcurrentHashMap`（Java），并利用锁或其他并发控制机制（如读写锁）确保并发访问的安全性。 3. **数据热更新**：使用内存缓存（如Redis）与数据库相结合的方式，当数据库中的数据更新时，通过消息队列（如Kafka）通知缓存系统更新对应的索引。 4. **分片与负载均衡**：将广告库索引分散到多个服务器上，每个服务器负责一部分广告策略。可以使用一致性哈希实现分片，确保广告策略的迁移最小化。同时，结合负载均衡器（如Nginx、HAProxy）分发请求。 5. **预计算与缓存**：针对高并发请求，预先计算热门广告策略的匹配结果并缓存，减少实时计算的压力。 6. **异步处理**：对于复杂的广告策略匹配，可采用异步处理模型，使用队列（如RabbitMQ）处理非实时需求，避免阻塞主线程。 7. **监控与扩展性**：设置全面的性能监控，如使用Prometheus + Grafana，及时发现并解决问题。根据负载情况动态扩展服务节点，使用Docker和Kubernetes进行容器化部署，实现弹性伸缩。 通过以上设计，广告库索引服务能够高效地处理多线程请求、支持数据热更新、处理大量广告策略和创意，并具备高并发处理能力。