Microsoft Interview Question
Software Engineer / DevelopersGuys this is not a puzzle,
they are asking you to sort out an algo for the problem
Finding the result is not the point..
yes u r right ern, this is a typical subset sum problem ...
scan the the values ...and store them...
after scanning first 2 8's list should be ..16,88
after scanning first 3 8's list should be ...24,96,888
we can find the soln if we proceed in this way...
with no order of operation:
8+8*8*8+8-8-8-8-8
8+8*8*8-8+8-8-8-8
8+8*8*8*8/8-8-8-8
8+8*8+8-8*8-8-8-8
8+8*8-8+8*8-8-8-8
8+8*8*8/8*8-8-8-8
8+8+8-8*8*8-8-8-8
8+8-8+8*8*8-8-8-8
8-8+8+8*8*8-8-8-8
8*8/8+8*8*8-8-8-8
8/8*8+8*8*8-8-8-8
8+8*8/8*8*8-8-8-8
8+8/8*8*8*8-8-8-8
8+8*8*8-8-8+8-8-8
8+8*8*8-8*8/8-8-8
8+8*8*8-8/8*8-8-8
8+8*8*8-8-8-8+8-8
8+8*8*8-8-8*8/8-8
8+8*8*8-8-8/8*8-8
8+8*8*8-8-8-8-8+8
8+8*8*8-8-8-8*8/8
8+8*8*8-8-8-8/8*8
with no order of operation:
8+8*8*8+8-8-8-8-8
8+8*8*8-8+8-8-8-8
8+8*8*8*8/8-8-8-8
8+8*8+8-8*8-8-8-8
8+8*8-8+8*8-8-8-8
8+8*8*8/8*8-8-8-8
8+8+8-8*8*8-8-8-8
8+8-8+8*8*8-8-8-8
8-8+8+8*8*8-8-8-8
8*8/8+8*8*8-8-8-8
8/8*8+8*8*8-8-8-8
8+8*8/8*8*8-8-8-8
8+8/8*8*8*8-8-8-8
8+8*8*8-8-8+8-8-8
8+8*8*8-8*8/8-8-8
8+8*8*8-8/8*8-8-8
8+8*8*8-8-8-8+8-8
8+8*8*8-8-8*8/8-8
8+8*8*8-8-8/8*8-8
8+8*8*8-8-8-8-8+8
8+8*8*8-8-8-8*8/8
8+8*8*8-8-8-8/8*8
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Plus88888888
{
class Program
{
static void PrintArray(int[] arr, int index)
{
Console.Write("{0} ", arr[0]);
for (int i = 1; i < index; i++)
{
Console.Write(" + {0}", arr[i]);
}
Console.WriteLine();
}
static int CalculateValue(int n)
{
int result = 0;
for (int i = 0; i < n; i++)
{
result = (result * 10) + 8;
}
return result;
}
static void CalculateEightEights(int numEightLeft, int[] arr, int index, int currentResult)
{
int tmp = 0;
if (numEightLeft == 0)
{
if (currentResult == 1000)
{
PrintArray(arr, index);
return;
}
}
for (int i = 1; i <= numEightLeft; i++)
{
tmp = CalculateValue(i);
arr[index] = tmp;
CalculateEightEights(numEightLeft - i, arr, index+1, currentResult+tmp);
}
}
static void Main(string[] args)
{
int[] arr = new int[8];
CalculateEightEights(8, arr, 0, 0);
}
}
}
@Anonymous, cud u plz explain the code? I dont think this code will work. It will sum up eight 8s, four 88s, two 888s,... so on.
Am I missing something obvious?
I am modifying Anonymous code as follows:
int[] arr = new int[8];
int index = 0;
void calculateEightEights(int target, int numEightLeft)
{
int prevResult = 0, curResult = 0;
for (int i=1; i<=numEightLeft; i++)
{
curResult = (curResult * 10) + 8;
if (curResult > target)
{
arr[index++] = prevResult;
calculateEightEights(target - prevResult, numEightLeft - i + 1);
}
prevResult = curResult;
}
}
To invoke the method: calculateEightEights(1000,8);
For simplicity I have taken global variables. We can avoid using them as found in anonymous code.
Hope this would help. Let me know the bugs,if any.
Thanks.
namespace Plus88888888
{
class Program
{
static void PrintArray(int[] arr, int index)
{
Console.Write("{0} ", arr[0]);
for (int i = 1; i < index; i++)
{
Console.Write(" + {0}", arr[i]);
}
Console.WriteLine();
}
static int CalculateValue(int n)
{
int result = 0;
for (int i = 0; i < n; i++)
{
result = (result * 10) + 8;
}
return result;
}
static void CalculateEightEights(int numEightLeft, int[] arr, int index, int currentResult)
{
int tmp = 0;
if (numEightLeft == 0)
{
if (currentResult == 1000)
{
PrintArray(arr, index);
return;
}
}
for (int i = 1; i <= numEightLeft; i++)
{
tmp = CalculateValue(i);
arr[index] = tmp;
CalculateEightEights(numEightLeft - i, arr, index+1, currentResult+tmp);
}
}
static void Main(string[] args)
{
int[] arr = new int[8];
CalculateEightEights(8, arr, 0, 0);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Plus88888888
{
class Program
{
static void PrintArray(int[] arr, int index)
{
Console.Write("{0} ", arr[0]);
for (int i = 1; i < index; i++)
{
Console.Write(" + {0}", arr[i]);
}
Console.WriteLine();
}
static int CalculateValue(int n)
{
int result = 0;
for (int i = 0; i < n; i++)
{
result = (result * 10) + 8;
}
return result;
}
static void CalculateEightEights(int numEightLeft, int[] arr, int index, int currentResult)
{
int tmp = 0;
if (numEightLeft == 0)
{
if (currentResult == 1000)
{
PrintArray(arr, index);
return;
}
}
for (int i = 1; i <= numEightLeft; i++)
{
tmp = CalculateValue(i);
arr[index] = tmp;
CalculateEightEights(numEightLeft - i, arr, index+1, currentResult+tmp);
}
}
static void Main(string[] args)
{
int[] arr = new int[8];
CalculateEightEights(8, arr, 0, 0);
}
}
}
888
- Anonymous October 16, 201088
8
8
8
----------
1000