How to Solve The Two-Sum Problem in C# (Time Complexity)

You nailed it at evaluating postfix expressions. You impressed the interviewer with your solution. Now, you’re asked about the time complexity of finding the sum of two elements in two arrays.

Time complexity is a mechanism to compare the performance of two algorithms as the input size grows. Time complexity measures the number of operations instead of execution time.

Time complexity and Big-O Notation

Well-known algorithms and common patterns of code have already a time complexity associated to it.

For example, performing an assignment or checking if a dictionary contains a key have constant time. It means, it will always take the same amount of operations to check if a dictionary contains a key, not matter the size of the dictionary.

Looping through the elements of an array has linear time. Dealing with matrices using two nested loops has quadratic time. Dividing an array into halves each time has logarithmic time. Do you remember binary search? It has logarithmic time.

Time complexity uses a mathematical notation to describe the complexity of an algorithm, called Big-O notation.

Big-O notation assigns a function to the complexity of an algorithm. Do you remember functions from Math class, right? So, constant time is O(1), linear time is O(n), quadratic time is O(n^2) and logarithmic time is O(logn).

You could use this Big-O cheatsheet to find the complexity and BigO notation of well-know algorithms.

Remember time complexity measures number of operations, not execution time. An algorithm with smaller number of operations has better time complexity than another one with a larger amount of operations.

Two Sum Problem in C#

The interview goes like this. The interviewer asks you to introduce yourself. You answer using the elevator pitch you prepared. Then, he suggests to start a whiteboard exercise. You open Notepad++, Visual Studio Code or your favorite editor. And, there you go.

Given two array of integers, find a pair of elements, one from each array, that adds up to zero. The size and the order of the elements aren’t specified. They may be sorted or not

First approach: Nested loops

Your first and obvious approach is to roll two loops and check every pair of elements in the two arrays. If the two arrays contain lots of elements, it would be slow. But it will get the task done.

for (int i = 0; i < a.Length; i++)
{
    for (int j = 0; j < b.Length; j++)
    {
        if (a[i] + b[j] == 0)
        {
            Console.WriteLine("Found");
        }
    }
}

The interviewer asks you about the time complexity of this solution. Since, you have to traverse the second array per every element in the first array, you will end up with n x m operations. With n and m the lengths of each array. So, you answer your solution has quadratic time or O(n^2). Right!

Better approach: Dictionary or set

Then, he asks you to do better. He asks for a linear solution.

To have a linear solution, you will have to get rid of traversing the second array. The problem will be solved if you know if any element in the first array has its inverse in the second array.

With a dictionary or a set with the elements of the second array, you can only traverse the first array and check for its inverse in the dictionary. Since, checking if a dictionary or a set contains a key has constant time, you will have a linear solution. It will loop through the first array only once.

var set = new HashSet<int>(b);
for (int i = 0; i < a.Length; i++)
{
    if (set.Contains(-a[i]))
    {
        Console.WriteLine("Found");
    }
}

Voilà! That’s how we can find the sum of two elements in linear time. Another happy interview! This time, you have in your toolbox time complexity. Not only for next interviews, but for everyday programming.

If you’re getting ready for your next interview, check these remote interviews types and tips and follow these ten tips to solve your next interview coding challenge.

Happy coding!

Five lessons after five years as a software developer

Five years of experience. Two companies. Two roles. These are 5 lessons I learned after my first five years as a software engineer.

1. You are not your code

Don’t judge someone by his code. Don’t take it personally. You could miss professional connections or friendships by judging someone by his code.

Assume everyone does his best with the resources he has. There always will be different opinions on how to do things. In the future, you will have one about your current work!

2. Coding is not the only thing

Collaboration is key. You won’t be locked in a basement coding. You will have to talk to clients, conduct meetings, agree on estimations, and ask for help.

In the beginning, I only wanted to code. I didn’t attend meetings, answer phone calls, or even reply to emails. I had to learn there’s more than only source code.

3. You don’t have to feel miserable

Change jobs when you feel your life is miserable or wasted because you woke up and realized you have to go to work or to that particular place.

Find a way to motivate yourself. Start a side project, learn a new stack, discover a new way of doing your work. Or, update your CV and LinkedIn profile and move on.

4. Bus syndrome: Don’t have hero developers

I know, I know! It feels great when you were the one who saved the day. But, if you are the only one who can solve some type of issue or know how a component works, then it will make you indispensable. And, therefore, irreplaceable.

If you’re a hero, you can’t get sick, go on vacations, or be promoted. Don’t be a hero. Be a team player.

Take every chance to share what you know and mentor juniors in your team.

5. Have a minimum viable product ASAP

A beautiful website or mobile app can make a huge difference. But, start small with finished core features and iterate on that.

In the beginning, you will have to set up the system through scripts or do some manual configuration. It’s better to demo an entire feature with an unpolished UI than a very awesome UI that does simply nothing.

Voilà! Those are my five lessons. Yours might be different. Interested in more career lessons? Check my lessons on remote work and the things I wished I knew before becoming a software engineer.

Happy coding!

Postfix Notation: An Interview Exercise

You are applying for your first position or for a new job. You are asked to complete a coding exercise: evaluate an expression in postfix notation. Let’s see what is postfix notation and how to evaluate postfix expressions in C#.

What is Postfix Notation?

Math and some programming languages use the infix notation. It places the operator between the two operands. And, it uses parenthesis to group operations. For example, a + b and (a + b)*c.

Unlinke infix notation, postfix notation places the operator after the two operands. And, it doesn’t use any parenthesis to group expresions. For example, a b + , and a b + c * are two expression in postfix notation.

Postfix expressions are evaluated from left to right. The expression 2 3 1 * + 9 - in postfix notation is equivalent to (2 + (3 * 1)) - 9.

Interview Question

This is your interview question: Write a C# program to evaluate a postfix mathematical expression. For example, 1 1 +, 1 1 1 + +, 1 1 + 2 3 * -.

During your technical interview, don’t rush to start coding right away. Follow the next steps:

• Understand the problem
• Come up with some examples. What’s the simplest case? Any edge cases?
• Ask clarification questions. Do you need to validate your input values?
• Think out loud your solution. Your interviewer wants to see your thought process.
• Make assumptions on the input. Start with the simplest case and work through a complete solution.

Evaluate postfix expressions

To evaluate a postfix expression, you need a stack.

A stack is a pile-like data structure. Stacks support two operations: add something to the pile, push, and remove something from the pile, pop.

When evaluating a postfix notation, we use a stack to hold either values from the input or already computed values.

This is the pseudocode to evaluate a postfix expression:

1. Create an stack
2. Split input string
3. If the first splitted value is a number, push it to the stack.
4. But, if it’s an operator, pop the two operands from the stack. Do the Math operation and push the result back to the stack.
5. Go to next splitted value and repeat
6. Finally, return value in the stack

Let’s C#!!!

Now, head to Visual Studio or Visual Studio Code and create a new project. This is how we evaluate a postfix expression in C#.

First, let’s split the input string with the Split() method. To identify the operators and operands, we can use either string comparisons or regular expressions. Let’s use regular expressions.

Regex _operandRegex = new Regex(@"-?[0-9]+");
Regex _operatorRegex = new Regex(@"[+\-*\/]");
        
public string Evaluate(string postfixExpression)
{
    var tokens = new Stack();
    string[] rawTokens = postfixExpression.Split(' ');
    foreach (var t in rawTokens)
    {
        if (_operandRegex.IsMatch(t))
        {
            tokens.Push(t);
        }
        else if (_operatorRegex.IsMatch(t))
        {
            var t1 = tokens.Pop().ToString();
            var t2 = tokens.Pop().ToString();
            var op = t;

            var result = EvaluateSingleExpression(t2, t1, op);
            if (result != null)
            {
                tokens.Push(result);
            }
        }
    }
    if (tokens.Count > 0)
    {
       return tokens.Pop().ToString();
    }

    return "";
}

private static string EvaluateSingleExpression(string value1, string value2, string op)
{
    var operand1 = Convert.ToDouble(value1);
    var operand2 = Convert.ToDouble(value2);

    if (op == "+")
    {
        var result = operand1 + operand2;
        return Convert.ToString(result);
    }
    // Similar logic for other operators

    return null;
}

Voila! That’s how we can evaluate postfix expressions in C#. For more tips to prepare yourself for your next interview, check my interview tips. Also, check my post on the difference between Func and Action in C# and how to solve the two-sum problem. Those are another two common interview questions.

Happy coding!

Visual Studio 2022 setup for C# (theme, settings, extensions)

Visual Studio is the de facto IDE for C#. You will spend countless hours inside Visual Studio. You are better off spending some time to customize it to boost your productivity.

My Visual Studio setup is heavily inspired by De-Cruft Visual Studio. It aims to leave more space to the text editor by removing unneeded menus and bars.

These are the theme, settings and extensions I use to be more productive with Visual Studio.

1. Theme and Layout

• Color theme: Dark
• Text Editor theme: Solarized Dark
• Font: FiraCode 14pt
• Zoom: 110%
• Windows:
  • Left
    • Test Explorer
    • Source Control Explorer
  • Right
    • Properties
    • Solution Explorer
    • Git Changes
    • Team Explorer
  • Bottom
    • Output
    • Error List
    • C# Interactive: A C# REPL, so you don’t have to create a Console project to try things out

2. Settings

To change your Visual Studio settings, go to “Tools” menu and then to “Options”.

On the left pane, you will find Visual Studio settings groupped by features, languages and extensions.

In “Text Editor”, unselect Enable mouse click to perform Go to Definition, Selection Margin and Indicator margin.

Next, uncheck Disable CodeLens. Only activate Show Test Status and Show C# References.

Next, in C# specific settings, enable Line numbers. And, hide Navigation Bar and Code Outlining.

Go down to Advanced settings to Add missing using directives on paste. Yeap, Visual Studio can add missing using staments when you paste some code. That’s a time saver!

After installing “Productivity Power Tools” extension, unselect Compress blank lines and Compress lines that do not have any alphanumeric characters. Code looks weird compressed.

Speaking of extensions, after installing “VSVim” extension, use Handle all with Visual Studio. This way, we have the best of both worlds. And, we still have Control + C and Control + V.

For shortcuts, add Ctrl+Shift+w to easily close all documents from the keyboard.

3. Extensions

• VSVim It enables Vim keybindings in the text editor
• Productivity Power Tools
  • Editor Guidelines: Add a Solarized Magenta guideline at column 120
  • Fixed Mixed Tabs
  • Custom Document Well
  • Match Margin
• VSColorOutput It gives you a fancier Output tab with colors
• SaveAllTheTime No more Ctrl + S. It saves automatically all modified files. Why this feature isn’t included in Visual Studio out-of-the-box? It’s already present in Visual Studio Code!
• SolutionColor It colors the solution bar per project. No more editing production code without noticing it. Use Solarized theme, too. Red for Beta and Magenta for Production
• LocateInTFS It finds the location of the selected file in the Source Control Explorer tab
• AddNewFile It adds new files directly from the Solution Explorer. Forget about Right Click -> Add -> New Folder, to then add the file you want. You can create folders and files in from a single pop-up window. You only need to hit Shift + F2 and type the path, name and extension of your new file.
• SemanticColorizer It colors fields, classes, methods and more. Make extension methods italics, only
• NUnit 3 Test Adapter. A must-have
• MappingGenerator It creates mappings from one object to another and from a list of parameters to an object. You need to initialize an object with sample values? In your tests for example? MappingGenerator does it for you!
• CodeMaid It cleans and formats your files. It remove extra blank lines. It removes and sorts your using statements. It removes extra spaces before and after parenthesis. You got the idea!.
• AsyncMethodNameFixer To not to forget to add the Async suffix on async method names.
• Multiline Search and Replace No need to copy and paste your code into Notepad++ to replace multiple lines at once.
• Line Endings Unifier Yes, it unifies the line endings of your files. You can choose the line ending you want to use in your files. Depending on the number of files in your solution, it could take a couple of seconds. But it does its job!
• Moq.Autocomplete If you use Moq to create fakes, this extension is for you. Inside the Setup() methods, it autocompletes the parameter list of the faked method using It.IsAny<T>() for each parameter. A time saver! I use this extension along with these snippets for Moq.
• Open Command Line: Right click on a project or solution and open a Terminal in the folder of that solution or project. Or, simply press Alt + Space.

4. Presentation mode

Fire a new instance from Visual Studio Developers Tools command prompt, using

devenv /RootSuffix Demo

It will open a separate and clean instance with no configurations or extensions. Any changes made to this instance won’t affect the “normal” instance next time you open Visual Studio.

To make Visual Studio work in Presentation mode:

• Remove Navigation Outline, Server Explorer, Toolbox, Git changes, and Properties. Only keep Solution Explorer.
• Disable CodeLens.
• Use Cascadia Mono, 14pt.
• Change Output and Developer Powershell font to Consolas 14pt.
• Increase size of tooltips:
  • Change Statement Completion font size to 12pt.
  • Change Editor Tooltip font size to 13pt.
• Change text highlight color to yellow.
• Use 120% as default zoom level.
• Install SaveAllTheTime.
• Optionally install the GitHub theme.
• Optionally install the MarkdownEditor extension to present using markdown files.

Voilà! That’s how I use Visual Studio 2019 for C# coding. If you’re wondering what’s Vim and why you should learn it, check my post Learning Vim for Fun and Profit.

For more productivity tools and tricks, check these programs that saved me 100 hours and how I used a Visual Studio extension and a Git feature to get rid of two recurrent review comments.

Happy coding!

What the Func, Action? Func vs Action

What’s the difference between Func and Action in C#? This is a common C# interview question. Let’s find it out!

The difference between Func and Action is the return type of the method they point to. Action references a method with no return type. And, Func references a method with a return type.

What are delegates?

It all starts with delegates.

A delegate is a pointer to a method with some input parameters and possibly a return type.

In other words, a delegate is a variable that references a method that has a given signature. Both, Func and Action are built-in delegate types.

Delegates are helpful when working with higher-order functions. This is, functions that take functions as parameter or return another function. For example, JavaScript callbacks and Python decorators are high-order functions.

Now that it’s clear what delegates are, let’s see some Func and Action declarations. For example,

• Action<Employee> holds a void method that receives Employee as parameter.
• Action, a void method without any parameters.
• Func<Employee, string> represents a method that receives an Employee and returns a string.
• Func<string> doesn’t have any parameters and returns string.

When declaring Func references, the last type inside <> tells the return type of the method being referenced. For Action references, since they don’t have a return type, the types inside <> show the input parameter types.

How to use Func and Action in a method?

You have already used Func, if you have used LINQ. But, in general, we use them as lambda expressions.

A lambda expression is a shorthand notation to write a method without a name, only with the body and the parameter list.

For example, let’s find the employees who have worked for more than ten years.

var allEmployees = new List<Employee> { /* Some employees here */ };

Func<Employee, bool> p = (t) => t.YearsWorked >= 10;
allEmployees.Where(p);

Or just simply

allEmployees.Where(t => t.YearsWorked >= 10);

How to declare a method that receives Func or Action?

To a declare a method that uses Func or Action as an input parameter, you have to use them like regular paramaters. Then, you have to either call Invoke on it or put parenthesis next to the name passing the appropiate parameters.

Let’s see an example of a method that uses Func.

public Employee DoSomething(Func<Employee, string> func)
{
    var employee = new Employee();
    
    // var result = func.Invoke(employee);
    // Or simply
    var result = func(employee);
    //           ^^^^^
    
    // Do something with the result here

    return employee;
}

A real-world example

Func and Action are great as small factory methods. They can be used in helper or utility methods to separete business logic from generic code.

Let’s see Func in action! Here is an example of Func from Insight.Database to create a ReliableConnection, a database connection that automatically retries on certain errors.

The ExecuteWithRetry method retries things and uses Func for the operation to retry. Some of the code has been removed for brevity.

public class RetryStrategy : IRetryStrategy
{
    public TResult ExecuteWithRetry<TResult>(IDbCommand commandContext, Func<TResult> func)
    {
        int attempt = 0;
        TimeSpan delay = MinBackOff;

        while (true)
        {
            try
            {
                return func();
                //     ^^^^^
            }
            catch (Exception ex)
            {
                // if it's not a transient error, then let it go
                if (!IsTransientException(ex))
                    throw;

                // if the number of retries has been exceeded then throw
                if (attempt >= MaxRetryCount)
                    throw;
                    
                // some lines removed for brevity

                // wait before retrying the command
                // unless this is the first attempt or first retry is disabled
                if (attempt > 0 || !FastFirstRetry)
                {
                    Thread.Sleep(delay);

                    // update the increment
                    delay += IncrementalBackOff;
                    if (delay > MaxBackOff)
                        delay = MaxBackOff;
                }

                // increment the attempt
                attempt++;
            }
        }
    }
}

And, this is how to use the method to open a connection.

public class ReliableConnection : DbConnectionWrapper
{
    public override void Open()
    {
        RetryStrategy.ExecuteWithRetry(null, () => { InnerConnection.Open(); return true; });
    }
}

Voilà! That’s the difference between Func and Action. Remember that they only represent the signature of a method. You can define or pass around the body later.

If you want to know more about LINQ, check my quick guide to LINQ. All you need to know about LINQ in 15 minutes or less. To learn how to use Insight.Database, check how to create a CRUD API with ASP.NET Core and Insight.Database.

Happy Funcy time!