腾讯-WXG企业微信-前端一面

🖊️ 手撕五道题

括号匹配问题
- 给定一个包含括号的字符串，判断是否每个括号都匹配。
- 常用栈结构来解决，遍历字符串时，遇到左括号入栈，遇到右括号出栈，最后栈为空则匹配成功。
数组去重检查，要求 O(n) 时间 + O(1) 空间
- 给定一个数组，检查是否有重复元素，要求时间复杂度 O(n)，空间复杂度 O(1)。
- 不允许使用 Set/Map，可能需要利用排序后对比或者其他空间优化技巧，如位运算。
二叉树路径和判断
- 判断是否存在一条从根节点到叶节点的路径，使得路径上所有节点的值之和为给定目标值。
- 采用深度优先搜索（DFS）来遍历二叉树，并计算路径和。
最长子序列问题
- 求解给定序列的最长递增子序列（LIS）。
- 可以使用动态规划（DP）或二分查找与动态规划结合的算法。
LRU 缓存设计（只实现 set 和 get）
- 设计一个LRU（最近最少使用）缓存系统，实现 set 和 get 方法，要求操作时间复杂度为 O(1)。
- 可使用哈希表（Map）和双向链表结合的方式实现。

浏览器缓存主要分为强缓存和协商缓存：
- 强缓存：在缓存有效期内直接使用缓存数据，浏览器不会向服务器发起请求。常用的 HTTP 头部有 Cache-Control、Expires。
- 协商缓存：缓存失效后，浏览器会向服务器发起请求，服务器根据文件的最后修改时间或文件的ETag来判断缓存是否有效，常用的 HTTP 头部有 Last-Modified 和 ETag。