Pocket Gems的一系列面试面经

xanadulord 发表于 2015-6-28 09:27
请教lz第一轮第一题 这个数据结构add,delete,search的是什么数据类型呀？是不是自己实现一个HashMap？谢谢{ ...

他这些要存的都是object。。所以用hashmap和arraylist一起存。。。用hashmap找到这个object在list里的index然后直接取。。。～

豆子要奋斗 发表于 2015-6-28 22:52
他这些要存的都是object。。所以用hashmap和arraylist一起存。。。用hashmap找到这个object在list里的ind ...

哇，lz回得好快！

但是为什么要用arraylist呢？hashmap如果没有冲突的话，add,delete,search不都是O(1)吗？题目是不是还有其他要求呢？谢谢！

xanadulord 发表于 2015-6-29 08:10
哇，lz回得好快！

但是为什么要用arraylist呢？hashmap如果没有冲突的话，add,delete,search不都是O(1 ...

哈哈 因为我最近也在论坛里瞎逛。。。＝－＝
喔喔 对对 漏了一个。。。还要实现getRandom()。。谢谢提醒。。～

豆子要奋斗 发表于 2015-6-29 08:32
哈哈 因为我最近也在论坛里瞎逛。。。＝－＝
喔喔 对对 漏了一个。。。还要实现getRandom()。。谢谢提醒 ...

明白了，多谢lz！！

xanadulord 发表于 2015-6-29 08:47
明白了，多谢lz！！

哈哈 不客气～这小粉猪表情用的。。＝－＝
你要面他们家嘛？祝好运哦～

豆子要奋斗 发表于 2015-6-29 10:11
哈哈 不客气～这小粉猪表情用的。。＝－＝
你要面他们家嘛？祝好运哦～

嘿嘿，是的，下周去onsite，多谢鼓励~

再请教下lz，mutable string的那道题目的思路~~

第1,2问是不是这样做的？
这个String内部用一个char[], charAt()不用说直接返回，substring（）只要记录offset和length就可以得到substring

第3问
这时用char[]的话parent和sub会互相影响。在其他帖子里面有人提到用 ArrayList<HashMap<>>，对于这个数据结构不是很明白。
如果str0 = "hello",
底层结构就是 [<0,h>, <0,e>, <0,l>,<0,l>,<0,0>]吗？

xanadulord 发表于 2015-6-30 07:05
再请教下lz，mutable string的那道题目的思路~~

第1,2问是不是这样做的？

抱歉！才看见！
第一二问没问题～就是java里的实现方式
第三问 我没用arraylist那个， 直接把每一个string看成一个结点，不同的string可以构成一个树的结构～然后存每一次的变化～

豆子要奋斗 发表于 2015-7-3 10:33
抱歉！才看见！
第一二问没问题～就是java里的实现方式
第三问 我没用arraylist那个， 直接把每一个str ...

恩恩，用tree有道理。前天去onsite了，没有问到这题

楼主能简单说下mutable string 的tree 实现吗，马上onsite 这道题 很想搞明白。