TwoSum and BinarySearchTree in testdome.com; How to solve the warning message: Performance test?

Question

I'm trying to solve questions of C# programming in testdome.com, but I found problem about performance. How to solve it?

BinarySearchTree

using System;

public class Node
{
    public int Value { get; set; }

    public Node Left { get; set; }

    public Node Right { get; set; }

    public Node(int value, Node left, Node right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
}

public class BinarySearchTree
{
    public static bool Contains(Node root, int value)
    {
        Console.WriteLine("value=" + value);
        if(root == null)
            return false;
        else if(root.Value == value)
            return true;
        else if(root.Value != value)
        {
            return Contains(root.Left, value) | Contains(root.Right, value);
        }
        return false;
    }

    public static void Main(string[] args)
    {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        Console.WriteLine(Contains(n2, 3));
    }
}

Performance test on a large tree: Memory limit exceeded

https://www.testdome.com/for-developers/solve-question/7482

TwoSum

using System;
using System.Collections.Generic;

class TwoSum
{
    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
    {
        for(int ctr1=0; ctr1<list.Count; ctr1++)
        {
            for(int ctr2=0; ctr2<list.Count; ctr2++)
            {
                if ((ctr1 != ctr2) && (list[ctr1]+list[ctr2] == sum))
                    return new Tuple<int, int>(ctr1, ctr2);
            }
        }
        return null;
    }

    public static void Main(string[] args)
    {
        Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12);
        Console.WriteLine(indices.Item1 + " " + indices.Item2);
    }
}

Performance test with a large number of elements: Time limit exceeded

https://www.testdome.com/for-developers/solve-question/8125

Answer 1

For the Binary search tree, testdome.com provides a hint "If a value being searched for is smaller than the value of the node, then the right subtree can be ignored." This cuts memory consumption by half.

public static bool Contains(Node root, int value) {
    Console.WriteLine("value=" + value);
    if (root == null) {
        return false;
    }
    else if (value == root.Value) {
        return true; 
    } 
    else if (value < root.Value) {
        // Hint 2: If a value being searched for is smaller than the value of the node, 
        // then the right subtree can be ignored.
        return Contains(root.Left, value);
    }
    else {
        return Contains(root.Right, value);
    }
    return false;
}

For the TwoSum, if we assume that the values in the input array are unique, we can use a dictionary to look up an index by its value (in O(1) time). This relates to the hint "A dictionary can be used to store pre-calculated values, this may allow a solution with O(N) complexity."

// Write a function that, when passed a list and a target sum, 
// returns, efficiently with respect to time used, 
// two distinct zero-based indices of any two of the numbers, 
// whose sum is equal to the target sum. 
// If there are no two numbers, the function should return null.
public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) {

    if (list.Count < 2) {
        return null;
    }
    
    // Hint 2: A dictionary can be used to store pre-calculated values,
    // this may allow a solution with O(N) complexity.
    var indexByValue = new Dictionary<int, int>();
    for (var i = 0; i < list.Count; i++) {
        var value = list[i];
        // ensure that the values used as keys are unique
        // this is OK because we only have to return any tuple matching the sum,
        // therefore we can ignore any duplicate values
        if (!indexByValue.ContainsKey(value)) {
            indexByValue.Add(value, i);
        }
    }
    
    for (var j = 0; j < list.Count; j++) {
        var remainder = sum - list[j];
        if (indexByValue.ContainsKey(remainder)) {
            return new Tuple<int, int> (j, indexByValue[remainder]);
        }
    }
    
    return null;
}

Answer 2

Simpler way to attack the problem. The above answers are good, but think the desired result can be found quicker.

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
{
    if (list.Count < 2) { return null; }

    foreach (int i in list)
    {
        int result = sum - i;
        if(list.Contains(result))
        {
            return new Tuple<int, int>(i, result);
        }
    }

    return null;
}