eBay技术电面

感觉要挂...经
天竺SDE3来面的

45分钟

给一个数组， 包含一些空字符串， 非空字符串是排序好的， 要求你求target wo

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

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

后也没bug free写出来，结束后发现了那个小bug，已经来不及了


求米！ 我感觉我这辈子都上不了岸了。沮丧。。。

cuzy 发表于 2020-10-19 13:32
是的 不过遇到空的时候怎么处理 要注意死循环的情况 他叫我当场跑代码了，感觉他自己理解得也不透彻 给不 ...

我觉得首先初始化的时候左右指针如果是空就得统一往左或者右移动找到一个首位第一个非空的str，像是“空 非空 空 非空 空”的话， 就是区间【1，3】，然后之后每次二分中指针遇到空的时候可以统一把中指针往左移动直到遇到非空。如果移动过后碰到左指针就break表示循环结束（表示左右指针中间全是空，没必要继续二分了）。这样就可以保证每次二分的结果都必然不是空。最后左右指针一定会落在一个像是“非空 空 空 空 非空” 这样一个区间，对比左右指针和target应该就能得到结果了。

感觉就是普通二分法？不过把数字比较换成string.compareTo（） 。 然empty string的时候把指针往一个方向移动（左或者右）直到遇到非空就停下。

用hashmap 做？

yangcheng901211 发表于 2020-10-15 07:27
用hashmap 做？

时间复杂度要小于O(n) 用不了hashmap吧。 我用的二分

CC150上有这道题

cuzy 发表于 2020-10-14 16:41:58
时间复杂度要小于O(n) 用不了hashmap吧。 我用的二分

请问这一题用二分法的worst case time complexity是不是也是O(n)? 如果大部分的string都是empty的话。谢谢！

CharlotteZcccc 发表于 2020-10-15 10:16
CC150上有这道题

好吧 第一次听说CC150

a_small_potato 发表于 2020-10-15 11:00
请问这一题用二分法的worst case time complexity是不是也是O(n)? 如果大部分的string都是empty的话。谢谢 ...

是的！ logn 到 n

hjy 发表于 2020-10-19 06:09
感觉就是普通二分法？不过把数字比较换成string.compareTo（） 。 然empty string的时候把指针往一个方向移 ...

是的 不过遇到空的时候怎么处理 要注意死循环的情况 他叫我当场跑代码了，感觉他自己理解得也不透彻 给不了好的引导 大概思路对了之后只看你最后有没有bug free写出来