Flatten Nested List Iterator: Duyệt Đệ Quy Danh Sách Lồng Nhau

Đề bài: Triển khai iterator làm phẳng nested list của integer. Mỗi element là int hoặc list. Ví dụ: [[1,1],2,[1,1]] → iterator trả về 1,1,2,1,1.

Ý tưởng: Pre-flatten khi khởi tạo

Dùng DFS đệ quy để flatten toàn bộ nested list thành list phẳng self.flat lúc init. Iterator chỉ cần giữ index.

Code Python

class NestedIterator:
    def __init__(self, nestedList: list):
        self.flat = []
        self.index = 0
        self._flatten(nestedList)
    
    def _flatten(self, nested):
        for item in nested:
            if isinstance(item, int):
                self.flat.append(item)
            else:
                self._flatten(item)
    
    def next(self) -> int:
        val = self.flat[self.index]
        self.index += 1
        return val
    
    def hasNext(self) -> bool:
        return self.index < len(self.flat)

# Test
it = NestedIterator([[1,1],2,[1,1]])
while it.hasNext():
    print(it.next(), end=' ')  # 1 1 2 1 1
print()

# Test nested deeper
it2 = NestedIterator([1, [4, [6]]])
while it2.hasNext():
    print(it2.next(), end=' ')  # 1 4 6

Phân tích

• Init: O(N) time/space (N = tổng số integer).
• next, hasNext: O(1).
• Đơn giản, dễ hiểu, phù hợp khi nested list không quá lớn.

Biến thể: Lazy Flatten (Iterator thực sự, không pre-flatten)

Dùng stack lưu (list, index). hasNext tìm next integer on-demand. Tiết kiệm memory nếu chỉ duyệt một phần.

class NestedIteratorLazy:
    def __init__(self, nestedList):
        self.stack = [(nestedList, 0)]
    
    def next(self):
        self.hasNext()  # Ensure top is integer
        nested, i = self.stack[-1]
        val = nested[i]
        self.stack[-1] = (nested, i + 1)
        return val
    
    def hasNext(self):
        while self.stack:
            nested, i = self.stack[-1]
            if i == len(nested):
                self.stack.pop()
                continue
            elem = nested[i]
            if isinstance(elem, int):
                return True
            # Is list: dive in
            self.stack[-1] = (nested, i + 1)
            self.stack.append((elem, 0))
        return False

Kết luận

Pre-flatten đơn giản cho interview. Lazy flatten phức tạp hơn nhưng memory-efficient cho large/deep nested structures.