编程算法面试常考题答案汇总

Merge N Sorted Data Streams

Coding Interview Question: Merge N Sorted Data Streams

Assuming you have n sorted data streams in the form of an iterator, implement a new iterator that provides a total order stream by merging those input data streams.

The interface of the iterator will be as follow:

class Iterator(object):
def HasNext(self):
# Return true if there is the next element to be fetched from this iterator.

def Next(self):
# Consume and return the next element from this iterator.

Solution

  #  本代码来自 Techie科技求职，由 Techie Learning,Inc 原创
#  - Techielearning.com 是来自硅谷的科技职业发展平台。
#  - 本代码所属课程：<< Techie编程算法集训营 >>
#  - 12周56+课时精品内容，精讲软件工程师编程算法面试核心知识体系。
#  - 120道面试真题详解，27类常考题型剖析，1对1面试辅导与专业答疑。
#  - 官方网站：https://www.techielearning.com/
#  - 版权所有，禁止转发和分享
 
 
  class NewTotalOrderIterator(object):
    def __init__(self, iters):
      self._pq = []
      for iter in iters:
        if iter.HasNext():
          self._pq.append((iter.Next(), iter))
      heapq.heapify(self._pq)
 
    def HasNext(self):
      return len(self._pq) > 0
 
    def Next(self):
      if not self.HasNext():
        return None
      v, iter = heapq.heappop(self._pq)
      if iter.HasNext():
        heapq.heappush(self._pq, (iter.Next(), iter))
      return v
 
 
# Test code
  class ArrayIterator(object):
    def __init__(self, array):
      self._array = array
      self._idx = 0
 
    def HasNext(self):
      return self._idx < len(self._array)
 
    def Next(self):
      if not self.HasNext():
        return None
      elem = self._array[self._idx]
      self._idx += 1
      return elem

如果大家对题目代码有任何问题，欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信。期待与同学们继续交流！

现在免费试听！

编程算法集训营首节2小时精华内容，马上开始学习

内容包括：编程算法面试真题举例与评价体系，双指针 (Two Pointers) 题型详解，...

进入课程主页