ways to improve the time of the execution - Data structures

Question

I am learning Data Structures and I am stuck in a problem I cannot find the way to improve the performance of the code. The problem is this: https://www.hackerrank.com/challenges/contacts/problem I made the solution and I could pass 3 of the 15 tests, but the rest I couldn´t because show me:

Time limit exceeded Your code did not execute within the time limits. Please optimize your code. For more information on execution time limits, refer to the environment page

I change the nested if with linq, but I couldn't get the improvement. Could you help me? I left the code I am using:

public static List<int> contacts (List<List<string>> queries)
{
    List<string> contactList = new List<string>();
    List<string> findList = new List<string>();
    List<int> result = new List<int>();
    foreach (var instruction in queries)
    {
        if (instruction[0] == "add") 
            contactList.Add(instruction[1]);
        else
            findList.Add(instruction[1]);
    }
    for(int i = 0; i < findList.Count; i++)
    {
        //-----------------------------------------------------------------------
        var counter = contactList.Where(x => x.Contains(findList[i])).Count();
        result.Add(counter);
        //-----------------------------------------------------------------------
        //foreach (var contact in contactList)
        //{
        //    if (contact.Contains(findList[i]))
        //        result[i]++;
        //}
    }
    return result;
}

Thanks in advance for your help

https://stackoverflow.com/questions/150750/hashset-vs-list-performance — Steve, Apr 22 '22 at 20:55
it should be x.Startswith - which will for sure be faster. Store them in order in a SortedSet, then iterate youself and stop once the first letter you see is not the first letter of the search string — pm100, Apr 22 '22 at 21:14

score 0 · Answer 1 · edited Apr 23 '22 at 06:17

Thanks for your advices! I made a research about the issue and I leave the solution in C#

using System.Collections.Generic;

namespace ConsoleApp2 {
internal class Program
{
    static void Main(string[] args)
    {
        var x = contacts(new List<List<string>>() {
            new List<string> {"add", "hack" },
            new List<string> {"add", "hackerrank" },
            new List<string> {"find", "hac" },
            new List<string> {"find", "hak" }
        });
    }

    public static List<int> contacts (List<List<string>> queries)
    {
        Trie trie = new Trie();
        var findList = new List<int>();
        foreach (var instruction in queries)
        {
            if (instruction[0] == "add") 
                trie.add(instruction[1]);
            else
                findList.Add(trie.find(instruction[1]));
        }
        return findList;
    }
}
class TrieNode
{
    private Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
    public int size;

    public void putChildIfAbsent(char ch)
    {
        if(!children.ContainsKey(ch))
            children.Add(ch, new TrieNode());
    }

    public TrieNode getChild(char ch)
    {
        if (children.ContainsKey(ch))
            return children[ch];
        return null;
    }
}
class Trie
{
    TrieNode root = new TrieNode();

    public void add(string str)
    {
        TrieNode curr = root;
        foreach(char ch in str)
        {
            curr.putChildIfAbsent(ch);
            curr=curr.getChild(ch);
            curr.size++;
        }
    }

    public int find(string prefix)
    {
        TrieNode curr = root;

        foreach(char ch in prefix)
        {
            curr= curr.getChild(ch);
            if (curr == null)
                return 0;
        }
        return curr.size;
    }
}

}

ways to improve the time of the execution - Data structures

1 Answers1