芒果DB 第一轮挂经

第一轮店面，被问到了一个Iterator问题，也是我自己练习不够，挂了

分享一下题目给大家，有帮助的希望能给我加米！求大米看面经！

整体我感觉面试体验还是挺好的，面试官人很nice，给了hint，然后感觉他们公司culture也不错，wlb也挺好的。

Implement a UnionIterator class that takes two strictly sorted iterators and produces a new iterator with the following properties:

• The new iterator contains the union of the elements from both input iterators. If an element appears in both inputs, it appears only once i
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  
  t().
  
  这个我一开始当linkedlist去做，后面才发现不太一样，分享一下解题思路：
  
  给两个 iterator 各 cache 一个 current value，每次 next() 比较两个 cached value，返回较小的那个，并只 advance 对应的 iterator；如果两个值相等，就只 return 一次，同时 advance 两个 iterator 来 dedup。这样只需额外存两个值，space complexity 是 O(1)

union iterator 这题确实容易想偏，一开始当 merge 两个 linkedlist 做太正常了。面试官给了 hint 还挺 nice 的，这种挂经分享出来就是攒人品，下次肯定过。