Question

Microsoft | L61 | OA Coding Questions and Solutions | Set - 25 | 2022

Answer 1

Questions in OA.
image

Answer 2

  public int MinDegreeOfExtendedPalindrome(string s)
    {
        int degree = 1;
        int i = 0;
        int j = s.Length - 1;
        
        //regular palindrome
        if (CheckPalindrome(s, ref i, ref j, degree))
            return degree;

        var primes = GetPrimes(s.Length);
        int k = 0;
        while (i < j && k < primes.Length)
        {
            //check if the prime number is a divisor of s.Length
            if (s.Length % primes[k] == 0)
            {
                degree = primes[k];
                if (CheckPalindrome(s, ref i, ref j, degree))
                    return degree;
            }
            k++;
        }

        return -1;
    }

    public bool CheckPalindrome(string s, ref int i, ref int j, int degree)
    {
        while(i < j)
        {
            string a = s.Substring(i, degree);
            string b = s.Substring(j - degree + 1, degree);
            if (a.Equals(b))
            {
                i += degree;
                j -= degree;
            }
            else
                return false;
        }

        return true;
    }

    public int[] GetPrimes(int n)
    {
        var primes = new List<int>();
        primes.Add(2);
        int next = 3;
        
        while (next <= n)
        {
            int sqrt = (int)Math.Sqrt(next);
            bool isPrime = true;
            for(int i = 0; primes[i] <= sqrt; i++)
            {
                if(next % primes[i] == 0)
                {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime)
                primes.Add(next);

            next += 2;
        }

        return primes.ToArray();
    }