Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Go

Flatten Nested List Iterator

Explore how to implement a flatten nested list iterator using stacks in Go. Learn to build the Nested Iterator class with Next and Has Next functions, enabling efficient traversal of complex nested integer lists. Understand problem constraints and practice coding the solution hands-on to master this common interview challenge.

We'll cover the following...

Statement

You’re given a nested list of integers. Each element is either an integer or a list whose elements may also be integers or other integer lists. Your task is to implement an iterator to flatten the nested list.

You will have to implement the Nested Iterator class. This class has the following functions:

  • Constructor: This initializes the iterator with the nested list.
  • Next (): This returns the next integer in the nested list.
  • Has Next (): This returns TRUE if there are still some integers in the nested list. Otherwise, it returns FALSE.

Constraints

  • The nested list length is between 11 and 200200.
  • The nested list consists of integers between [1,104][1, 10^4].

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Flatten Nested List Iterator

1.

What is the output if the following set of parameters are passed to the Constructor(), Next, and Has next() functions?

Constructor([3, [6, 7], 8])
Next()
Has Next()
Next()
Next()
A.

NULL

3

TRUE

6

7

B.

NULL

3

TRUE

[6, 7]

8

C.

NULL

3

TRUE

[6, 7, 8]

9

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: You need to figure out the solution of the Has Next () function only.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3

Try it yourself

Implement your solution in nested_iterator.go in the following coding playground. You’ll need the provided supporting code to implement your solution.

Go
usercode > nested_iterator.go
package main
type NestedIterator struct {
	// Write your code here
}
// Constructor inializes the stack using the
// given nestedList list
func Constructor(nestedList []*NestedIntegers) *NestedIterator {
  	// Replace this placeholder return statement with your code
	return new(NestedIterator)
}
// HasNext() will return True if there are still some integers
// in the stack (that has nestedList elements) and, otherwise,
// will return False.
func (this *NestedIterator) HasNext() bool {
  	// Replace this placeholder return statement with your code
	return false
}
// Next append the values of the nested list into the stack
func (this *NestedIterator) Next() int {
  	// Replace this placeholder return statement with your code
	return -1
}
Flatten Nested List Iterator