CareerCup

change the numbers representation say first number =(a+b+c+d) second number =(e+f+g+h) and then the product will be a polynomial expression

I think they was interested in Karatsuba multiplication, that give us O(n^(1,6)) rather that O(n^2) for classical approach.

A possible solution could be to use an alternate representation of the number say in a exponent form say m^n.

Once the representation is done then you can multiply arbitrary number of such numbers by doing exponent addition with common base for ex:

(2^a)*(2^b)*(2^c)*....*(2^z) = 2^(a+b+c+...+z)

Store them in lists and multiply number by number, like grade school multiplication

Store digits and multiply them one at a time, like grade school math, though order goes to n^2.

change the numbers representation say first number =(a+b+c+d) second number =(e+f+g+h) and then the product will be a polynomial expression

On a very serious note, this is what people tend to do, for real.
codeproject.com/Articles/36323/BigInt

Is this ok ?
Bit manipulation.

until Num2 becomes 0
- Shift Num2 to right. Shift Num1 to left.

Complexity Log(N2)

using System;

public class Program
{
public static void Main()
{
Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999"));
}
public static string GetProduct(string s1,string s2)
{
int digit1=0;
int digit2=0;

char[] str1=s1.ToCharArray();
char[] str2=s2.ToCharArray();
int carry;
string[] result=new string[str1.Length];
string finalproduct=string.Empty;
int padding=0;

for(int i=str1.Length-1;i>=0;i--)
{
digit1=str1[i]-'0';
string resval=string.Empty;
carry=0;
int j;
for(j=str2.Length-1;j>=0;j--)
{
digit2=str2[j]-'0';

int product=digit1*digit2+carry;
carry=product/10;
resval=resval+(product%10);

}
if(carry>0)
{
resval=resval+carry;
}
for(int k=0;k<padding;k++)
{
resval="0"+resval;
}
result[i]=resval;
padding++;
}

int max=findMax(result);
int count=0;
int car=0;

while(count<max)
{
int sum=0;

for(int x=0;x<result.Length;x++)
{

if(count<result[x].Length)
{

sum+=result[x][count]-'0';
}

}
sum+=car;
car=sum/10;
int p=sum%10;
finalproduct=p+finalproduct;
count++;
}

finalproduct=car+finalproduct;

return finalproduct.TrimStart('0');

}

public static int findMax(string[] s)
{
int max=0;
for(int i=0;i<s.Length;i++)
{
int len=s[i].Length;
max=Math.Max(max,len);
}
return max;
}
}

using System;
					
public class Program
{
	public static void Main()
	{
		Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999"));
	}
	public static string GetProduct(string s1,string s2)
	{
		int digit1=0;
		int digit2=0;
		
		char[] str1=s1.ToCharArray();
		char[] str2=s2.ToCharArray();
		int carry;
		string[] result=new string[str1.Length];
		string finalproduct=string.Empty;
        int padding=0;
		
		for(int i=str1.Length-1;i>=0;i--)
		{
			digit1=str1[i]-'0';
			string resval=string.Empty;
			carry=0;
			int j;
			for(j=str2.Length-1;j>=0;j--)
			{
				digit2=str2[j]-'0';
				
				int product=digit1*digit2+carry;
				carry=product/10;
				resval=resval+(product%10);
				
			}
			if(carry>0)
			{
				resval=resval+carry;
			}
			for(int k=0;k<padding;k++)
			{
					resval="0"+resval;
			}
	        result[i]=resval;
			padding++;
		}
		
		int max=findMax(result);
		int count=0;
		int car=0;

		while(count<max)
		{
			 int sum=0;
		 
	 	  for(int x=0;x<result.Length;x++)
		  {
	
			if(count<result[x].Length)
			{
			
				sum+=result[x][count]-'0';
			}

		  }
			sum+=car;
			car=sum/10;
			int p=sum%10;
			finalproduct=p+finalproduct;
			count++;
		}
		
		finalproduct=car+finalproduct;
		
	   return finalproduct.TrimStart('0');		
		
	}
	
	public static int findMax(string[] s)
	{
		int max=0;
		for(int i=0;i<s.Length;i++)
		{
			int len=s[i].Length;
			max=Math.Max(max,len);
		}
		return max;
	}
}

Good luck coding this optimal solution with Fast Fourier transform within 30 minutes of phone interview:

"
The basic FFT algorithm itself runs in O(n log n) time; using FFTs for integer
multiplication incurs some small additional overhead.
The fastest integer multiplication algorithm currently known, published by David Harvey
and Joris van der Hoeven in 2018, runs in O(n * (log n) * (4^log$n))) time.
Here, log$n denotes the slowly growing iterated logarithm of n, which is the number of times
one must take the logarithm of n before the value is less than 1.
"