10 C# Algorithm Interview Questions and Answers

C# is a versatile and powerful programming language widely used in various domains such as web development, game development, and enterprise applications. Its strong typing, object-oriented features, and integration with the .NET framework make it a preferred choice for many developers. Mastering C# and its algorithmic applications can significantly enhance your problem-solving skills and coding efficiency.

This article provides a curated selection of C# algorithm questions designed to help you prepare for technical interviews. By working through these examples, you will gain a deeper understanding of key concepts and improve your ability to tackle complex coding challenges with confidence.

C# Algorithm Interview Questions and Answers

1. Write an algorithm to find the second largest element in an array.

To find the second largest element in an array, iterate through the array while keeping track of the largest and second largest elements. This approach ensures efficiency with a time complexity of O(n).

public int FindSecondLargest(int[] arr)
{
    if (arr.Length < 2)
    {
        throw new ArgumentException("Array must contain at least two elements.");
    }

    int first = int.MinValue;
    int second = int.MinValue;

    foreach (int num in arr)
    {
        if (num > first)
        {
            second = first;
            first = num;
        }
        else if (num > second && num != first)
        {
            second = num;
        }
    }

    if (second == int.MinValue)
    {
        throw new InvalidOperationException("No second largest element found.");
    }

    return second;
}

2. Implement a quicksort algorithm.

Quicksort is an efficient sorting algorithm using a divide-and-conquer approach. It selects a ‘pivot’ element and partitions the other elements into two sub-arrays, sorting them recursively.

using System;

public class QuickSort
{
    public static void Sort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int pivotIndex = Partition(array, left, right);
            Sort(array, left, pivotIndex - 1);
            Sort(array, pivotIndex + 1, right);
        }
    }

    private static int Partition(int[] array, int left, int right)
    {
        int pivot = array[right];
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                Swap(array, i, j);
            }
        }

        Swap(array, i + 1, right);
        return i + 1;
    }

    private static void Swap(int[] array, int a, int b)
    {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

class Program
{
    static void Main()
    {
        int[] array = { 34, 7, 23, 32, 5, 62 };
        QuickSort.Sort(array, 0, array.Length - 1);
        Console.WriteLine(string.Join(", ", array));
    }
}

3. Write a function to merge two sorted linked lists into one sorted linked list.

To merge two sorted linked lists, use a two-pointer technique. Iterate through both lists, comparing current nodes, and add the smaller node to the merged list.

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1 != null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next;
}

4. Implement a binary search algorithm.

A binary search algorithm efficiently finds an element in a sorted array by repeatedly dividing the search interval in half.

public class BinarySearch
{
    public static int Search(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (array[mid] == target)
                return mid;

            if (array[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1; // Target not found
    }
}

// Usage
int[] sortedArray = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int target = 5;
int result = BinarySearch.Search(sortedArray, target);
// result will be 4, the index of the target in the array

5. Solve the knapsack problem using dynamic programming.

To solve the knapsack problem using dynamic programming, create a 2D array where rows represent items and columns represent weight capacities.

public int Knapsack(int[] weights, int[] values, int capacity)
{
    int n = weights.Length;
    int[,] dp = new int[n + 1, capacity + 1];

    for (int i = 1; i <= n; i++)
    {
        for (int w = 0; w <= capacity; w++)
        {
            if (weights[i - 1] <= w)
            {
                dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
            }
            else
            {
                dp[i, w] = dp[i - 1, w];
            }
        }
    }

    return dp[n, capacity];
}

6. Implement a function to check if a string is a palindrome.

A palindrome is a string that reads the same forward and backward. To check if a string is a palindrome, compare it to its reverse.

public bool IsPalindrome(string s)
{
    int left = 0;
    int right = s.Length - 1;

    while (left < right)
    {
        if (s[left] != s[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

7. Write an algorithm to solve the N-Queens problem using backtracking.

The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other. Backtracking is a common technique used to solve this problem.

using System;
using System.Collections.Generic;

public class NQueens
{
    public IList<IList<string>> SolveNQueens(int n)
    {
        var solutions = new List<IList<string>>();
        var board = new char[n][];
        for (int i = 0; i < n; i++)
        {
            board[i] = new string('.', n).ToCharArray();
        }
        Solve(0, board, solutions);
        return solutions;
    }

    private void Solve(int row, char[][] board, IList<IList<string>> solutions)
    {
        if (row == board.Length)
        {
            var solution = new List<string>();
            foreach (var line in board)
            {
                solution.Add(new string(line));
            }
            solutions.Add(solution);
            return;
        }

        for (int col = 0; col < board.Length; col++)
        {
            if (IsValid(board, row, col))
            {
                board[row][col] = 'Q';
                Solve(row + 1, board, solutions);
                board[row][col] = '.';
            }
        }
    }

    private bool IsValid(char[][] board, int row, int col)
    {
        for (int i = 0; i < row; i++)
        {
            if (board[i][col] == 'Q') return false;
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (board[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < board.Length; i--, j++)
        {
            if (board[i][j] == 'Q') return false;
        }

        return true;
    }
}

8. Implement an in-order traversal of a binary tree.

In-order traversal of a binary tree visits nodes in the order: left subtree, root node, and then right subtree.

public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BinaryTree
{
    public TreeNode Root;

    public BinaryTree()
    {
        Root = null;
    }

    public void InOrderTraversal(TreeNode node)
    {
        if (node == null)
        {
            return;
        }

        InOrderTraversal(node.Left);
        Console.Write(node.Value + " ");
        InOrderTraversal(node.Right);
    }
}

9. Implement a Dijkstra’s algorithm to find the shortest path in a weighted graph.

Dijkstra’s algorithm finds the shortest path between nodes in a weighted graph by iteratively selecting the node with the smallest tentative distance.

using System;
using System.Collections.Generic;

class Graph
{
    private int vertices;
    private List<Tuple<int, int>>[] adjacencyList;

    public Graph(int vertices)
    {
        this.vertices = vertices;
        adjacencyList = new List<Tuple<int, int>>[vertices];
        for (int i = 0; i < vertices; i++)
            adjacencyList[i] = new List<Tuple<int, int>>();
    }

    public void AddEdge(int u, int v, int weight)
    {
        adjacencyList[u].Add(new Tuple<int, int>(v, weight));
    }

    public void Dijkstra(int source)
    {
        int[] distances = new int[vertices];
        bool[] shortestPathTreeSet = new bool[vertices];

        for (int i = 0; i < vertices; i++)
        {
            distances[i] = int.MaxValue;
            shortestPathTreeSet[i] = false;
        }

        distances[source] = 0;

        for (int count = 0; count < vertices - 1; count++)
        {
            int u = MinDistance(distances, shortestPathTreeSet);
            shortestPathTreeSet[u] = true;

            foreach (var neighbor in adjacencyList[u])
            {
                int v = neighbor.Item1;
                int weight = neighbor.Item2;

                if (!shortestPathTreeSet[v] && distances[u] != int.MaxValue && distances[u] + weight < distances[v])
                    distances[v] = distances[u] + weight;
            }
        }

        PrintSolution(distances);
    }

    private int MinDistance(int[] distances, bool[] shortestPathTreeSet)
    {
        int min = int.MaxValue, minIndex = -1;

        for (int v = 0; v < vertices; v++)
            if (!shortestPathTreeSet[v] && distances[v] <= min)
            {
                min = distances[v];
                minIndex = v;
            }

        return minIndex;
    }

    private void PrintSolution(int[] distances)
    {
        Console.WriteLine("Vertex \t Distance from Source");
        for (int i = 0; i < vertices; i++)
            Console.WriteLine(i + " \t\t " + distances[i]);
    }
}

10. Discuss parallel processing in C# and how it can be used to optimize algorithms.

Parallel processing in C# can be achieved using the Task Parallel Library (TPL), which provides a way to run tasks in parallel. The Parallel.For and Parallel.ForEach methods are useful for optimizing algorithms that involve loops.

using System;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        int[] numbers = new int[1000000];
        Parallel.For(0, numbers.Length, i =>
        {
            numbers[i] = i * i;
        });
    }
}

In this example, Parallel.For is used to square each element in an array concurrently, reducing the time required compared to a traditional for loop.