Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem 5: Sorting a Stack

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Though the output is right, logic used for golang solution is wrong. I printed out the stack for the code for each outer for loop iteration and the output is given below:

Issue in code line: for !tmpStack.Empty() && tmp1.(int) > tmp.(int) {...

tmpStack:: {[23]} input: {[34 3 31 98 92]} tmpStack:: {[23 92]} input: {[34 3 31 98]} tmpStack:: {[23 92 98]} input: {[34 3 31]} tmpStack:: {[31]} input: {[34 3 98 92 23]} tmpStack:: {[23]} input: {[34 3 98 92 31]} tmpStack:: {[23 31]} input: {[34 3 98 92]} tmpStack:: {[23 31 92]} input: {[34 3 98]} tmpStack:: {[23 31 92 98]} input: {[34 3]} tmpStack:: {[3]} input: {[34 98 92 31 23]} tmpStack:: {[3 23]} input: {[34 98 92 31]} tmpStack:: {[3 23 31]} input: {[34 98 92]} tmpStack:: {[3 23 31 92]} input: {[34 98]} tmpStack::

A

Anonymous

· 2 years ago

Guys,

Either you treat stack as a stack, or as an array. What the heck is line:15 from your js solution? That's clearly accessing something by index.

            // While the temporary stack is not empty and the top element
            // of the temporary stack is greater than the current element,
            // push elements from the temporary stack back to the original stack.
            while (tempStack.length && tempStack[tempStack.length - 1] > temp) {
                stack.push(tempStack.pop());
            }
Show 1 reply
A

Anonymous

· 2 years ago

It's horrible user experience to spend time for custom Stack implementation while we have slice for solution.

Show 1 reply
A

Anonymous

· 3 years ago

"""
My solution:
Time Complexity:
The main loop iterates through each element in the original stack once.
In the worst case, for each element, you might have to pop elements from the temporary stack until
the correct position is found.
Therefore, the time complexity is O(N^2), where N is the number of elements in the stack.
Space Complexity:
The space complexity is O(N) since you are using two additional stacks
(original_stack and temp_stack), and their combined size depends on the number of elements in the original stack.
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:

    def __init__(self):
        self.top = None
        self.count = 0
    def size(self):
        return self.count

    def is_empty(self):
        r

Reading Progress

0%

Vote for new content