TripAdvisor on campus + homework

给个timeline

9.14 On Campus

9.15 Homework

9.20 拒

On Campus

ABC大叔，一大早9点第一个面，感觉大叔还没睡醒或者本来就话不多吧，问问题都经常自己卡壳了。

介绍一个最近的项目，最challenging的part，然后tech方面以后想focus啥，然后几个问题

• 解释hashtable原理，感觉这是一个多月面试以来说的最多的了，balabala说了好多，从怎么hash，到处理collision的各种方法，对时间复杂度的影响，如何根据load factor高效exte

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

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

  现这样还是O(MN)，M = text1.length, N = text2.length。现在想想发现如果内存都放得下，应该把第二个文本的词组全提取出来放在一个set里，然后扫第一个就好了，就只用O(M+N)了，不知道是不是这里挂了。
  
  
  本着去波士顿玩的心情做的，结果想也没多想就做了交了，结果旅游泡汤了。
  
  
  
  

求问一下楼主hashtable的时间复杂度 我当时学这块的时候就有点迷 求讲解一下！谢谢～

jinlan940713 发表于 2017-9-20 23:09
求问一下楼主hashtable的时间复杂度 我当时学这块的时候就有点迷 求讲解一下！谢谢～

没有collision就是o(1)呗，如果多个key被hash到了同一个slot就不是O（1）了

面壁者 发表于 2017-9-20 23:21
没有collision就是o(1)呗，如果多个key被hash到了同一个slot就不是O（1）了

嗯嗯 原来要这样答 谢啦

求问Homework用kmp咋写的啊 我是pre-processing之后直接比的。。。

nickdgu 发表于 2017-10-1 00:00
求问Homework用kmp咋写的啊 我是pre-processing之后直接比的。。。

我觉得直接比就可以了， 我用kmp复杂度上也没有优化

好XD。。。