狗家上周上门面

感觉题目不难，挺可惜的1. 离口巴斯斯，不让用额外的space，经提示后写出了从右到左扫的方法。时间不多，加问了一个如何判断坐标系上四个点能不能组成一个正方形，讲下思路就好
2. 给一个排好序的数组和一个数，返回该数在数组中的范围，我用的是离口三思的方法

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

，然后做了一道coding，给一个排序数组和一组起始点终点，返回数组中有多少数在这个范围呢，左闭右开区间，follow up是返回数组中绝对值在该区间的数的个数

LionelWang 发表于 2019-6-12 15:06
系统设计日志系统怎么解？

按某章系统设计的套路来做的，是一个write heavy的系统

fir925 发表于 2019-6-12 08:57
对，思路是这样

1.     int countNumRecursive(vector<int>& nums, int s, int e, int target){
   
2.         if (nums[s] == target && nums[e] == target) return (e - s + 1);
   
3.         if (nums[s] > target || nums[e] < target) return 0;
   
4.         int mid = s + (e - s) / 2;
   
5.         return countNumRecursive(nums, s, mid, target) + countNumRecursive(nums, mid + 1, e, target);
   
6.         
   
7.     }
   
8.     int countNum(vector<int>& nums, int target) {
   
9.         return countNumRecursive(nums, 0, nums.size() - 1, target);
   
10.     }

复制代码

fir925 发表于 2019-6-12 08:57
对，思路是这样

1.     int countNumRecursive(vector<int>& nums, int s, int e, int target){
   
2.         if (nums[s] == target && nums[e] == target) return (e - s + 1);
   
3.         if (nums[s] > target || nums[e] < target) return 0;
   
4.         int mid = s + (e - s) / 2;
   
5.         return countNumRecursive(nums, s, mid, target) + countNumRecursive(nums, mid + 1, e, target);
   
6.         
   
7.     }
   
8.     int countNum(vector<int>& nums, int target) {
   
9.         return countNumRecursive(nums, 0, nums.size() - 1, target);
   
10.     }

复制代码

第二问返回的是该数在数组中的出现的次数

recursion难道是前一半 加 后一半出现的次数？

pandami 发表于 2019-6-12 08:53
recursion难道是前一半 加 后一半出现的次数？

对，思路是这样

第三题union find？index应该是唯一的 而且要删除的树和其它部分只通过给出的节点相连？

pandami 发表于 2019-6-12 08:58
第三题union find？index应该是唯一的 而且要删除的树和其它部分只通过给出的节点相连？

可以用union find，同时生成新的森林数组的同时也需要更新剩余的树节点的index

fir925 发表于 2019/06/12 09:02:07


可以用union find，同时生成新的森林数组的同时也需要更新剩余的树节点的index

是说node里的index和数组index要一致吗
那就是生成新的数组之后再更新一波？

bq居然还加coding 是因为楼主bq说的太快了吗 哈哈

pandami 发表于 2019/06/12 09:26:03


是说node里的index和数组index要一致吗
那就是生成新的数组之后再更新一波？

bq居然还加coding 是因为楼主bq说的太快了吗 哈哈

对的，哈哈哈 我也不知道啊，一个国人小哥面的bq，可能还不习惯狗家这种新方式吧

第三题可以构造hashmap adjacency list，然后dfs删，最后再返回array

系统设计日志系统怎么解？