Learn and practice the Stacks, and Matrices patterns to solve coding interview problems.

Speedrun the Apple Coding Interview: Top Problems in C++

Interviewers want to be sure that the candidate is comfortable manipulating linked lists, arrays, and data structures based on them, such as stacks and matrices. This module will provide the practice you need to review the concepts and techniques needed to solve common problems involving these data structures.

Basic Data Structures

# 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 $1$ and $200$.
* The nested list consists of integers between $[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:


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

```text
Constructor([3, [6, 7], 8])
Next()
Has Next()
Next()
Next()
```

What is the output if the following set of parameters are passed to the Constructor(), Next, and Has next() functions?
<pre><code class="language-text">Constructor([3, [6, 7], 8])
Next()
Has Next()
Next()
Next()
</code></pre>

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

```text
Constructor([1, 1, [2], [3], [6, 7], [4]])
Has Next()
Next()
Next()
Next()
Has Next()
Has Next()
Next()
```

What is the output if the following set of parameters are passed to the Constructor(), Next, and Has next() functions?
<pre><code class="language-text">Constructor([1, 1, [2], [3], [6, 7], [4]])
Has Next()
Next()
Next()
Next()
Has Next()
Has Next()
Next()
</code></pre>

NULL

TRUE

2

[1]

TRUE

3

FALSE

FALSE

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

```text
Constructor([[2, [1], 3]])
Has Next()
Next()
Next()
Has Next()
Next()
Has Next()
Has Next()
```

What is the output if the following set of parameters are passed to the Constructor(), Next, and Has next() functions?
<pre><code class="language-text">Constructor([[2, [1], 3]])
Has Next()
Next()
Next()
Has Next()
Next()
Has Next()
Has Next()
</code></pre>

Flatten Nested List Iterator

Flatten Nested List Iterator

# 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.

# Try it yourself

Implement your solution in `NestedIterator.cpp` in the following coding playground. You'll need the provided supporting code to implement your solution.

// The following class is used for creating nested lists.
// You should not implement this class or speculate about its implementation.

class NestedIntegers
{
 std::vector<NestedIntegers> nList;
 int integer;

public:
 // Constructor initializes an empty nested list.

 NestedIntegers()
 {
 integer = -1;
 }

 // Constructor initializes a single integer.
 NestedIntegers(int value)
 {
 integer = value;
 }

 // @return true if this NestedIntegers holds a single integer, rather than a nested list.
 bool isInteger()
 {
 if (integer != -1)
 return true;
 return false;
 }

 // @return the single integer that this NestedIntegers holds, if it holds a single integer
 // Return null if this NestedIntegers holds a nested list
 int getInteger()
 {
 return (integer);
 }

 // Set this NestedIntegers to hold a single integer.
 void setInteger(int value)
 {
 nList.clear();
 integer = value;
 }

 // Set this NestedIntegers to hold a nested list and adds a nested integer to it.
 // void add(NestedIntegers *ni)
 // {
 // if (this->integer != -1)
 // {
 // this->nList.push_back(new NestedIntegers((this->integer)));
 // this->integer = -1;
 // }
 // this->list.push_back(ni);
 // }

 //new statements
 void add(int value) {
 nList.push_back(NestedIntegers(value));
 }

 void add(NestedIntegers ni) {
 nList.push_back(ni);
 }


 // @return the nested list that this NestedIntegers holds, if it holds a nested list
 // Return null if this NestedIntegers holds a single integer
 std::vector<NestedIntegers> getList()
 {
 return nList;
 }
};

#include "NestedIntegers.cpp"

class NestedIterator
{
 public:
 NestedIterator(vector<NestedIntegers> nestedList)
 {
 // Write your code here
 }

 bool HasNext()
 {
 // Replace this placeholder return statement with your code
 return false;
 }

 int Next()
 {
 // Replace this placeholder return statement with your code
 return -1;
 }
};

class NestedIntegers:
    # Constructor initializes a single integer if a value has been passed
    # else it initializes an empty list
    def __init__(self, integer=None):
        if integer:
            self.integer = integer
        else:
            self.n_list = []
            self.integer = 0 

    # If this NestedIntegers holds a single integer rather 
    # than a nested list, returns TRUE, else, returns FALSE
    def is_integer(self):
        if self.integer:
            return True
        return False

    # Returns the single integer, if this NestedIntegers holds a single integer
    # Returns null if this NestedIntegers holds a nested list
    def get_integer(self):
        return self.integer

    #  Sets this NestedIntegers to hold a single integer.
    def set_integer(self, value):
        self.n_list = None
        self.integer = value

    # Sets this NestedIntegers to hold a nested list and adds a nested 
    # integer to it.
    def add(self, ni):
        if self.integer:
            self.n_list = [] 
            self.n_list.append(NestedIntegers(self.integer)) 
            self.integer = None
        self.n_list.append(ni) 

    # Returns the nested list, if this NestedIntegers holds a nested list 
    # Returns null if this NestedIntegers holds a single integer
    def get_list(self):
        return self.n_list

from nested_integers import NestedIntegers

class NestedIterator:
    # Initializes the NestedIterator with nested_list
    def __init__(self, nested_list):
        # Write code here
        pass

    # checks if there are still some integers in nested_list
    def has_next(self):
        # Write code here
        pass

    # returns the next element from nested_list
    def next(self): 
        # Write code here
        pass


# ------ Please don't change the following function ----------
# flatten_list function is used for testing porpuses.
# Your code will be tested using this function
def flatten_list(nested_iterator_object):
    result = []
    while nested_iterator_object.has_next():
        result.append(nested_iterator_object.next()) 
    return result

# Quick Fix\nYou are Edward, a Senior Software Engineer who specializes in coding interview patterns, data structures and algorithms, and is great at debugging issues in code.\n\n- Edward, please keep in mind that you do not have to print the data of the placeholders. Also, do not mention anything about yourself.\n\nEdward, you are given the following data in the placeholders:\n- Function name: `Init, HasNext, Next`\n- Candidate's submitted solution code: USER_CODE\n- Error: ERROR_DESCRIPTION\n- Failed test case: FAILED_TEST_CASE\n- Coding language: `C++`\n\n- Edward, your task is to understand the type of error that is occurring in the coding language provided.\n- Once you've understood the error as per the error’s description, and why the test case failed, you will suggest how the candidate can improve their solution code to fix the error.\n- Edward, you will not give the corrected code, just a hint on what the error tells, and how to fix it.\n- Edward, please limit your response strictly to 100 words. No more words than the limit.

# Review Code\nEdward, your current task is to review the `Init, HasNext, Next` function(s) and the other function(s) invoked in it/them.\n\n-Take your time and review the candidate's solution code.\n- Do not review any extra/helper files or functions not invoked in the solution function `Init, HasNext, Next`.\n- Do not review the code of data structure objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. \n- Also, if the solution code doesn’t use the coding pattern stated above, then please encourage the candidate to reattempt the problem using that pattern corectly.

# Review time complexity\n- Please provide a brief time complexity analysis of the function(s) `Init, HasNext, Next`. \n- While calculating time complexity, include the time complexity of built-in C++ functions invoked by the code. \n- The answer should be to the point in approximately 60 words.

# Review space complexity\n- Please provide a brief space complexity analysis of the function(s) `Init, HasNext, Next`. \n- While calculating space complexity, include the space complexity of built-in C++ functions invoked by the code. \n- Do not include the space used for the input parameters and the space used for just returning an output (not used as a scratch space). \n- The answer should be to the point in approximately 60 words.

NestedArray

#include <string>

using namespace std;

class NestedArray : public DataStructure
{

 // define class attributes

private:
 void generateError(string data)
 {
 cerr << "NestedArray is not parsable: " << data;
 exit(-1);
 }

public:
 string var;

 NestedArray()
 {
 
 } 
 // return value will be passed to user program
 void *construct(string new_value, int typeOfDs)
 {
 var=new_value;
 return this;
 }

 string traverse(void *input, int typeOfDs)
 {
 return {};
 }

};

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """

        def flatten_nested_list(nested_list):
            flattened_list = []
            for item in nested_list:
                if isinstance(item, list):
                    flattened_list.extend(flatten_nested_list(item))
                else:
                    flattened_list.append(item)
            return flattened_list



        class NestedIntegers:
            # Constructor initializes a single integer if a value has been passed
            # else it initializes an empty list
            def __init__(self, integer=None):
                if integer:
                    self.integer = integer
                else:
                    self.n_list = []
                    self.integer = 0 

            # If this NestedIntegers holds a single integer rather 
            # than a nested list, returns TRUE, else, returns FALSE
            def is_integer(self):
                if self.integer:
                    return True
                return False

            # Returns the single integer, if this NestedIntegers holds a single integer
            # Returns null if this NestedIntegers holds a nested list
            def get_integer(self):
                return self.integer

            #  Sets this NestedIntegers to hold a single integer.
            def set_integer(self, value):
                self.n_list = None
                self.integer = value

            # Sets this NestedIntegers to hold a nested list and adds a nested 
            # integer to it.
            def add(self, ni):
                if self.integer:
                    self.n_list = [] 
                    self.n_list.append(NestedIntegers(self.integer)) 
                    self.integer = None
                self.n_list.append(ni) 

            # Returns the nested list, if this NestedIntegers holds a nested list 
            # Returns null if this NestedIntegers holds a single integer
            def get_list(self):
                return self.n_list

        class NestedIterator:
            # Initializes the NestedIterator with nested_list
            def __init__(self, nested_list):
                # Write your code here
                self.nested_list_stack = list(reversed(nested_list))
                

            # checks if there are still some integers in nested_list
            def has_next(self):
                # Write your code here
                while len(self.nested_list_stack) > 0:
                    top = self.nested_list_stack[-1]
                    if top.is_integer():
                        return True

                    top_list = self.nested_list_stack.pop().get_list()

                    i = len(top_list) - 1
                    while i >= 0:
                        self.nested_list_stack.append(top_list[i])
                        i -= 1
                return False

            # returns the next element from nested_list
            def next(self): 
                # Write your code here
                if self.has_next():
                    return self.nested_list_stack.pop().get_integer()
                return None
            
        nested_list =  [NestedIntegers(x) for x in flatten_nested_list(self.__inputs[0])]
        itr = NestedIterator(nested_list)

        
        expected = []
        while itr.has_next():
            expected.append(itr.next())
        
            
        actual = self.__actual_outputs[0]

        expected_outputs = []

        expected_outputs.append(expected)

        if json.dumps(expected) == json.dumps(actual):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <cctype>
#include "NestedIterator.cpp"
#include "NestedArray.cpp"

NestedIntegers BuildNestedIntegers(const std::string& str) {
 std::stack<NestedIntegers> stack;
 stack.push(NestedIntegers());

 size_t index = 0;
 while (index < str.size()) {
 if (isdigit(str[index]) || (str[index] == '-' && isdigit(str[index + 1]))) {
 int start = index;
 while (index < str.size() && (isdigit(str[index]) || str[index] == '-')) {
 index++;
 }
 int value = std::stoi(str.substr(start, index - start));
 stack.top().add(value);
 } else if (str[index] == '[') {
 stack.push(NestedIntegers());
 index++;
 } else if (str[index] == ']') {
 NestedIntegers ni = stack.top();
 stack.pop();
 stack.top().add(ni);
 index++;
 } else {
 index++; // skip commas or spaces
 }
 }

 return stack.top().getList().front(); // Root is inside one outer wrapper
}

void FlattenDirectory(NestedIntegers directory, std::vector<int>& result) {
 if (directory.isInteger()) {
 result.push_back(directory.getInteger());
 } else {
 for (const auto& item : directory.getList()) {
 FlattenDirectory(item, result);
 }
 }
}

std::vector<int> FlattenList(NestedIterator itr) {
 std::vector<int> result;
 while (itr.HasNext()) {
 result.push_back(itr.Next());
 }
 return result;
}

std::vector<int> Main(NestedArray s) {
 std::vector<int> res;

 NestedIntegers root = BuildNestedIntegers(s.var);

 std::vector<NestedIntegers> rootVec = { root };
 NestedIterator itr(rootVec);

 res = FlattenList(itr);
 return res;
}

flatten_nested_list_iterator (2).yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : [1, 2, [3, [4, 5, 6], [7, 8], 9], 10]
    output:
    - 1 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  - name: "testcase 2"
    inputs:
    - 1: [1, [2, 3], 3, [2, 3], 4, [2, 3, 4, 5]]
    output:
    - 1 : [1,2,3,3,2,3,4,2,3,4,5]
  - name: "testcase 3"
    inputs:
    - 1: [[2, 3, [2, 3]]]
    output:
    - 1 : [2,3,2,3]
  - name: "testcase 4"
    inputs:
    - 1: [1, [3, [4, [5, 6], 7], 8], 9]
    output:
    - 1 : [1,3,4,5,6,7,8,9]
  - name: "testcase 5"
    inputs:
    - 1: [[1], [3], [4, [5, [1], 6], [7], 4], [2]]
    output:
    - 1 : [1,3,4,5,1,6,7,4,2]

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1


 

 def flatten_nested_list(nested_list):

 # User input type validation check
 if type(nested_list) is not list:
 return "invalid_input"
 flattened_list = []
 for item in nested_list:
 if isinstance(item, list):
 flattened_list.extend(flatten_nested_list(item))
 elif isinstance(item,int):
 flattened_list.append(item)

 # Anything other than list and int will be considered as invalid
 else:
 return "invalid_input"

 return flattened_list

 def is_valid_1d_array(arr):
 if not isinstance(arr, list):
 return False # Not a valid 1D array if it's not a list
 
 return all(isinstance(elem, int) and not isinstance(elem, bool) for elem in arr)



 nested=self.__inputs[0]
 

 if nested=="invalid_input":
 self.store_result ("Invalid input type", ValidationFunction.FAIL)




 elif type(nested) is not list:
 self.store_result ("Invalid input type", ValidationFunction.FAIL)


 flattened=flatten_nested_list(nested)

 if any(type(x) is not int for x in flattened):
 
 self.store_result ("Input should be a valid nested list", ValidationFunction.FAIL)


 
 
 elif not (is_valid_1d_array(flattened)):
 self.store_result ("Input should be a valid nested list", ValidationFunction.FAIL)




 elif not isinstance(nested,list):
 self.store_result ("The input should be a nested list", ValidationFunction.FAIL)
 elif any(not isinstance(x,int) for x in flattened):
 self.store_result("Input should be a valid nested list", ValidationFunction.FAIL)

 elif not (1 <= len(nested) <= 200):
 self.store_result("Nested list length should be between 1 and 200", ValidationFunction.FAIL)
 

 elif any(not (1 <= x <= 10**4) for x in flattened):
 self.store_result("The nested list can have values between 1 to 10^4", ValidationFunction.FAIL)
 
 else:
 self.store_result("", ValidationFunction.PASS)

Try to solve the Flatten Nested List Iterator problem.

Stacks

Matrices

Conclusion

Flatten Nested List Iterator

Statement

Examples

Understand the problem

Figure it out!

Try it yourself