How to Shift Array Elements in C# (Space Complexity)

Here you are in another interview. You start to feel confident from your last interview. You have already evaluated postfix expressions and solved the two-number sum problem. Now, the interviewer challenges you with a new exercise: How to shift arrays elements to the right. Let’s solve it.

Given an array of integers and an integer k, rotate all elements k positions to the right. For example: After rotating [1,2,3,4,5,6] two positions to the right is [5,6,1,2,3,4]

Obivous solution: loop and bound checking

Your first approach is to roll a loop through the array and put in a second array each element shifted to the right.

You have to take care of elements near the end of the array. Otherwise, you will get outside of the array and an exception will be thrown. So, you add an if to check you keep it inside the bounds.

Something like this:

static int[] Shift(int[] array, int k)
{
    var result = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
    {
      if ((i + k) >= array.Length)
        result[(i + k) - array.Length] = array[i];
      else
        result[i + k] = array[i];
    }
    return result;
}

Modulus operator without bound checking

You can do better. Can you remove the bound checking?–the interviewer says.

Now, you start to use an example. If array=[1,2,3,4,5,6], k=1 and i=5, the last element must be the first one and so on and so forth. It reminds you the modulus operator (%).

The modulus operator, instead of dividing two numbers, calculates the remainder of dividing those two numbers.

Since the remainder is less than the divisor, you will always be inside the size of the array, if you use the modulus with the array length. So, you modify your previous solution.

static int[] Shift(int[] array, int k)
{
    var result = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
    {
      result[(i + k) % array.Length] = array[i];
    }
    return result;
}

What is Space complexity?

What is the space complexity of this solution?–the interviewer asks.

Space complexity is a metric to compare the amount of memory required to run an algorithm in relation to its input size. If the input gets bigger, how much storage the algorithm requires?

Since you are using a temporay array, the storage will be proportional to the size of the array. So, it’s linear!

Right!–the interviewer replies. Can you come up with a constant solution?–he suggests.

You have to get rid of the temporary array! What if you shift one element at a time and the repeat the process as many times as needed? This solution isn’t the most performant, but it uses constant space.

This time you have to shift the array backwards to only keep one element of the array in a temporary variable.

static int[] Shift(int[] array, int k)
{ 
    for (int times = 0; times < k; times++)
    {
      int tmp = array[array.Length - 1];
      for (int i = array.Length - 1; i > 0; i--)
      {
          array[i] = array[i - 1];
      }
      array[0] = tmp;
    }
        
    return array;
}

What about if you would’ve started with a one-line declarative LINQ solution? The interview could go in a different direction?

static int[] Shift(int[] array, int k)
    => array.Skip(array.Length - k)
        .Concat(array.Take(array.Length - k))
        .ToArray();

Voilà! Another happy interview! That’s how to shift the elements of an array and what space complexity is. For more interview preparation posts, check interview types and tips for your next interview and ten tips to solve your next interview coding challenge.

Happy coding!

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!