C# Coding Test Course, What Algorithm Should I Use to Solve It?

Coding tests are a mandatory procedure in modern IT companies. Many applicants are preparing to be evaluated on their understanding of algorithms and data structures, and their ability to solve problems based on this knowledge. In this article, we will take a closer look at how to solve algorithm problems using C#.

Problem: Valid Parentheses String

This is a problem of determining whether a given string is a valid parentheses string. The string is composed only of the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’. A valid parentheses string must satisfy the following conditions:

  • All opened parentheses must be closed by closed parentheses.
  • A closed parenthesis must always correspond to the most recent opened parenthesis.
  • The closing of parentheses should not occur before their opening.

For example, the string “{[()]}” is a valid parentheses string, while “{[(])}” is not valid.

Problem Solving Process

1. Problem Analysis

To solve this problem, we can use a stack data structure. Since the stack operates in a Last In First Out (LIFO) manner, we can add opened parentheses to the stack and, upon encountering a closed parenthesis, remove the most recently opened parenthesis from the stack. If the stack is empty after checking all parentheses, then it is a valid parentheses string.

2. Algorithm Design

The algorithm to solve this problem is as follows:

  1. Define the pairs of parentheses: { '(': ')', '{': '}', '[': ']' }
  2. Traverse the string and add opened parentheses to the stack.
  3. Upon encountering a closed parenthesis, check if it matches with the most recent opened parenthesis from the stack.
  4. If the stack is not empty or the pairs do not match, consider it an invalid string.
  5. After exploring the entire string, if the stack is empty, then it is a valid string.

3. C# Code Implementation


using System;
using System.Collections.Generic;

public class ValidParentheses
{
    public static bool IsValid(string s)
    {
        Stack stack = new Stack();
        Dictionary parentheses = new Dictionary()
        {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };

        foreach (char c in s)
        {
            // If it's an opened parenthesis, add it to the stack
            if (parentheses.ContainsKey(c))
            {
                stack.Push(c);
            }
            else
            {
                // If it's a closed parenthesis and the stack is empty, validation fails
                if (stack.Count == 0 || parentheses[stack.Pop()] != c)
                {
                    return false;
                }
            }
        }

        // If the stack is empty, it's a valid parentheses string
        return stack.Count == 0;
    }
}

class Program
{
    static void Main()
    {
        string input = "{[()]}";
        bool result = ValidParentheses.IsValid(input);
        Console.WriteLine($"\"{input}\" is it a valid parentheses string? {result}");
    }
}

4. Algorithm Analysis

The above code uses a stack to traverse the string once, resulting in a time complexity of O(n), where n is the length of the string. The space complexity is also O(n) because up to n opened parentheses can be stored on the stack. This algorithm can operate efficiently even as the input string length increases.

Conclusion

In this article, we explored how to solve the valid parentheses string problem using C#. When solving algorithm problems, it is important to analyze the problem well and choose the appropriate data structures. Utilizing simple data structures like stacks can help efficiently solve complex problems. I hope this helps in developing algorithmic thinking through a variety of problems.