Algorithms for Interview 1: Stack

Summary

The provided web content discusses the use of stacks as a fundamental data structure in solving algorithmic problems, particularly in coding interviews, with examples from LeetCode.

Abstract

The article introduces the concept of a stack, a linear data structure that operates on the Last In, First Out (LIFO) principle. It likens a stack to a pile of plates where the last plate added is the first one to be removed. The primary operations of a stack are push() to add an element to the top and pop() to remove the top element. The article further illustrates the practical application of stacks in coding interviews through three examples from LeetCode: validating parentheses, comparing backspace-affected strings, and removing adjacent duplicates in a string. Each example includes a problem description and a solution approach that leverages the stack data structure.

Opinions

The author considers stack problems as "classic" in coding interviews, implying their importance and common occurrence.
The use of a stack for solving the "Valid Parentheses" problem is presented as a straightforward and effective approach.
The article suggests that the stack's pop() function is analogous to the backspace operation in strings, which is a novel perspective on the utility of stacks.
The author implies that understanding how to manipulate strings using stacks is a valuable skill for solving algorithmic problems, as demonstrated in the "Backspace String Compare" and "Remove All Adjacent Duplicates In String" examples.

Introduction of Stack

Look at the above photo of plates, every pile of plates can represent a Stack.

Stack is an basic data structure and very useful to solve many problems. It is a array which has LIFO (last in, first out) feature.

This feature means:

Last In: If we wanna add a new element to a stack, we must add it to the top of the stack rather than other locations. Just like a pile of plates, we can only add a new plate at top every time.

First Out: If we wanna remove a existing element from a Stack, we can only remove the element at top which is the last in element. Just like a pile of plates, we can only remove the top plate every time.

Therefore, there are two principal functions of a Stack:

push(): Add an element to the top of the stack

pop(): Remove the top element

Solution:

This is a very classic Stack problem.

We can use a Stack to store previous checked brackets. When we meet a ‘closed’ bracket, the top of the Stack must be a corresponding ‘open’ bracket. If not, we return False. If yes, we pop the top element of the Stack.

Solution:

When we meet a ‘#’, the operation is removing the last character of current string, which is very similar with the Stack’s pop() function. Therefore, we can use Stack to deal with every string.

Algorithms for Interview 1: Stack

Introduction of Stack

Interview Example 1:

Problem Description:

Solution:

Interview Example 2:

Problem Description:

Solution:

Interview Example 3:

Problem Description:

Solution: