Tech Qu: Data structure to store and add arbitrarily large number

Data structure to store and add arbitrarily large number

Hi folks, I decided to play around with some of the silliness known as technical questions. At one time obtaining a University Degree was sufficient proof – until grade standards started diving to 20,000 leagues under the sea. In general, there are many right answers.

 

a) Design a data structure to store an arbitrarily large number
b) How will you use it to store two such number and add them.
c) Write down the class (code) for the data structure

 

We assume integers and not negative.

 

If it is arbitrary real then use:

Code Snippet

1. struct ArbitraryReal
2.  {
3.    public Stack<byte> LeftOf;
4.    public Stack<byte> RightOf;
5.    public bool Sign;
6.  }

This is an all in one function that could be decomposed..

• Take the string, break into characters, then convert to integer.
  • Conversion was done with an old fashion C approach
• Add the integers (doing a carryover)
• push the result into a new stack
• convert the stack to a character string
• return the string
  

Code Snippet

1. public static string Add(string a, string b)
2. {
3.   // Assume both are positive and integers
4.   var aStack = new Stack<int>();
5.   var bStack = new Stack<int>();
6.   var cStack = new Stack<int>();
7.   char zero = '0';
8.   foreach (var a1 in a.ToCharArray())
9.   {
10.     int diff = a1 - zero;
11.     if (diff > -1 && diff < 10)
12.     {
13.       aStack.Push(diff);
14.     }
15.     else
16.     {
17.       throw new DataException("Not 0 - 9");
18.     }
19.   }
20.   foreach (char a1 in b.ToCharArray())
21.   {
22.     int diff = a1 - zero;
23.     if (diff > -1 && diff < 10)
24.     {
25.       bStack.Push(diff);
26.     }
27.     else
28.     {
29.       throw new DataException("Not 0 - 9");
30.     }
31.   }
32.   int carryover = 0;
33.  
34.   while (aStack.Count > 0 && bStack.Count > 0)
35.   {
36.     int sum = aStack.Pop() + bStack.Pop() + carryover;
37.     if (sum > 9)
38.     {
39.       carryover = 1;
40.       sum -= 10;
41.     }
42.     else
43.       carryover = 0;
44.     cStack.Push(sum);
45.   }
46.   while (aStack.Count > 0)
47.   {
48.     int sum = aStack.Pop() + carryover;
49.     if (sum > 9)
50.     {
51.       carryover = 1;
52.       sum -= 10;
53.     }
54.     else
55.     {
56.       carryover = 0;
57.     }
58.     cStack.Push(sum);
59.   }
60.   while (bStack.Count > 0)
61.   {
62.     int sum = bStack.Pop() + carryover;
63.     if (sum > 9)
64.     {
65.       carryover = 1;
66.       sum -= 10;
67.     }
68.     else
69.     {
70.       carryover = 0;
71.     }
72.     cStack.Push(sum);
73.   }
74.   if (carryover > 0)
75.     cStack.Push(carryover);
76.   var results = new StringBuilder();
77.   while (cStack.Count > 0)
78.     results.Append(cStack.Pop());
79.   return results.ToString();
80. }

 

To test the code:

Code Snippet

1. var rnd = new Random();
2.       for (int i = 0; i < 10000; i++)
3.       {
4.         var a = rnd.Next().ToString();
5.         var b = rnd.Next().ToString();
6.         var test = Questions.Add(a, b);
7.         Console.WriteLine(String.Format("{0}+{1}={2}",a,b,test));
8.         if (long.Parse(test) != long.Parse(a) + long.Parse(b))
9.         {
10.           throw new Exception("Unit Test failed");
11.         }
12.       }

 

Variations:

• You can check (and discard) comma(,) and other symbols ($) that have no numeric consequences.
• With the +/- real case, you can do multiple tests for negative (i.e. (1234), or  1234- or –1234) giving robustness.
• You can even work with complex (real and imaginaries)

Code Snippet

1. struct ArbitraryComplex
2.     {
3.       public Stack<byte> LeftOf;
4.       public Stack<byte> RightOf;
5.       public bool Sign;
6.       public Stack<byte> iLeftOf;
7.       public Stack<byte> iRightOf;
8.       public bool iSign;    
9.     }