Write a function which, given two ASCII strings, determines if they are anagrams. Then, give algorithmic and space complexity.

Question

Sigiloso · Accepted Answer

Initial ideas included sorting the string, and checking character by character. After some probing by the interviewer, discussed how hash tables may make the problem simpler: Using a subroutine which takes a string and converts to a length 128 array, with each subscript representing the count of that ASCII character in the string. Then, in the main procedure, we can just compare the arrays returned by passing each string. In this, we see our space complexity is O(n) (since we have to store two strings of length n, plus two arrays of length 128) and algorithmically is also O(n) (since we must parse two strings of length n, then compare two arrays of length 128).

Mic · Answer

static void Main(string[] args)
        {
            bool isa = IsAnagram("hello",  "helol");
            bool isa2 = IsAnagram("hello", "leuoh");
            Console.ReadLine();
        }

        public static bool IsAnagram(string str1, string str2)
        {
            if (str1.Length != str2.Length) return false;
            char[] str1AsChar = str1.ToCharArray();
            bool[] hash = new bool[26];
            for (int i = 0; i < str1AsChar.Length; i++)
            {
                //Find your way to convert to ascii - it doesn't really matter
                hash[str1AsChar[i] - 100] = true;
            }

            for (int j = 0; j < str2.Length; j++)
            {
                //Find your way to convert to ascii - it doesn't really matter
                if (hash[str2[j] - 100] == false)
                {
                    return false;
                }

            }
            return true;
        }

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas