编程算法面试常考题答案汇总
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教师团队微信。期待与同学们继续交流！
