面经详情

Lintcode原题
问了一个LintCode原题 add and search word,设计算法支持两个操作,一个是add一个字符串,一个是search某个字符串是否在目前的字典中。查找的串可能包含通配符‘.",匹配任意一个字符。用Trie Tree即可。 然后小哥问了一下如何在space和time之间trade off,这个问题我做题的时候就想过,因为这题有两种做法,一是建树时不把"."作为一个字符,而在搜索时碰到"."时搜索所有儿子节点。另外一种是建树时把"."加入到每个节点的儿子节点中,把所有包含"."的字符串也存在Trie Tree中。两种做法的区别在于,前者空间复杂度低,每次add时间复杂度是字符串长度,每次search时间复杂度是O(26^"."的个数);后者空间复杂度高,每次add时间复杂度是2的字符串长度次方,每次search时间复杂度是字符串长度。印度小哥表示挺满意的~

相关推荐

匿名用户
Java
确定通过确定通过
1、你在工作中遇到最大的挑战是什么 2、你觉得你从毕业到现在最大的收获是什么 3、你平时是怎样去做索引优化的,基于什么背景 4、为什么linux操作系统从从磁盘读取数据的单位大小是4k(只答到是安装操作系统时指定的) 5、B+树的结构,主键索引非叶子节点存储的是什么,叶子节点存储的是什么 6、你在项目中有线程间通讯的场景吗, 线程间的通信方式有哪几种(说了wait、notify、LockSupport的park、unpark、ReentrantLock的Condition, 答非所问) 7、在项目中你主要负责那一块儿,大致描述一下 8、你有什么特别熟悉的中间件吗(说了zookeeper、redis、RocketMQ),挑一个你最熟悉的说一下(说了redis zset跳跃表),有去了解redis底层源码吗(没有),你为什么要去了解这些,了解这些对你工作有什么帮助吗 9、你平常是怎么去学习的(博客、视频课程、书籍)...查看更多
包含1个问题,1个回答
Q:1、你在工作中遇到最大的挑战是什么 2、你觉得你从毕业到现在最大的收获是什么 3、你平时是怎样去做索引优化的,基于什么背景 4、为什么linux操作系统从从磁盘读取数据的单位大小是4k(只答到是安装操作系统时指定的) 5、B+树的结构,主键索引非叶子节点存储的是什么,叶子节点存储的是什么 6、你在项目中有线程间通讯的场景吗, 线程间的通信方式有哪几种(说了wait、notify、LockSupport的park、unpark、ReentrantLock的Condition, 答非所问) 7、在项目中你主要负责那一块儿,大致描述一下 8、你有什么特别熟悉的中间件吗(说了zookeeper、redis、RocketMQ),挑一个你最熟悉的说一下(说了redis zset跳跃表),有去了解redis底层源码吗(没有),你为什么要去了解这些,了解这些对你工作有什么帮助吗 9、你平常是怎么去学习的(博客、视频课程、书籍)
2 年前 发布

进入微信小程序

前往微信小程序,查看更多结果

立即前往
看准网谷歌中国(Google)谷歌中国(Google)面试经验谷歌中国(Google)面试经验:Lintcode原题