Register

GO Classes DPP | PYTHON & DSA |PYTHON

172 views
2 2 votes

Consider the following Python function $\verb|mystery_ds|$ that processes a list of integers:

def mystery_ds(arr):
    stack = []
    result = [0] * len(arr)
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    return result
    
input_arr = [15, 20, 10, 25, 18]


What is the sum of the elements in the $\verb|result|$ list after $\verb|mystery_ds(input_arr)|$ is executed?

1 Answer

1 1 vote
The function initializes an empty stack and a result list of the same length as the input, filled with zeros: [0, 0, 0, 0, 0].

i = 0, arr[i] = 15: The stack is empty, so 0 is appended to the stack. stack is [0].
i = 1, arr[i] = 20: arr[stack[-1]] (15) is less than arr[i] (20). The stack top (0) is popped, and result[0] is set to 20. The stack is now empty. 1 is appended to the stack. stack is [1], result is [20, 0, 0, 0, 0].
i = 2, arr[i] = 10: arr[stack[-1]] (20) is not less than arr[i] (10). 2 is appended to the stack. stack is [1, 2].
i = 3, arr[i] = 25: arr[stack[-1]] (10) is less than arr[i] (25). The stack top (2) is popped, result[2] is set to 25. stack is [1]. arr[stack[-1]] (20) is less than arr[i] (25). The stack top (1) is popped, result[1] is set to 25. The stack is now empty. 3 is appended to the stack. stack is [3], result is [20, 25, 25, 0, 0].
i = 4, arr[i] = 18: arr[stack[-1]] (25) is not less than arr[i] (18). 4 is appended to the stack. stack is [3, 4].
The loop finishes. The final result list is [20, 25, 25, 0, 0].

Step 2: Calculate the sum of elements in the final result list

The sum of the elements in the final result list is calculated:

20+25+25+0+0=70

Answer:

The sum of the elements in the result list is 70.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | PYT...Next → · GO Classes DPP | PYT...
← Previous in category · GO Classes DPP | PYT...Next in category → · GO Classes DPP | PYT...
Position:
Show:

Related questions

0 0 votes
1 1 answer
157
157 views
GO Classes asked Feb 3
157 views
GO Classes DPP | PYTHON & DSA |BINARY TREE
A binary tree $T$ is constructed such that for every node $N$, the number of nodes in its left subtree $L(N)$ and right subtree $R(N)$ satisfy the condition: $\mid \opera...
0 0 votes
1 1 answer
148
148 views
GO Classes asked Feb 3
148 views
GO Classes DPP | PYTHON & DSA |HASHING
Consider a custom Python-style hash table implementation using Linear Probing to resolve collisions. The hash table has a size of $m=11$ $($indices $0$ to $10 )$ and uses...
1 1 vote
1 1 answer
401
401 views
GO Classes asked Feb 3
401 views
GO Classes DPP | PYTHON & DSA |BST
In a binary search tree (BST) where all keys are distinct, which of the following properties are TRUE regarding tree traversals and structure?The In-order traversal of an...
0 0 votes
1 1 answer
178
178 views
GO Classes asked Feb 3
178 views
GO Classes DPP | PYTHON & DSA |GRAPH
Consider an Adjacency List representation of a directed graph $G=(V, E)$ with $n$ vertices and $m$ edges, implemented using Python's $\verb|dict|$ where keys are vertex I...