Jump to content
  • Advertisement
Sign in to follow this  
srikanthpv

Game programmer Interview question

This topic is 3437 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

1. Write a function that given a string of digits and a target value, prints where to put +'s and *'s between the digits so they combine exactly to the target value. Note there may be more than one answer, it doesn't matter which one you print. Examples: "1231231234",11353 -> "12*3+1+23*123*4" "3456237490",1185 -> "3*4*56+2+3*7+490" "3456237490",9191 -> "no solution" [Edited by - srikanthpv on November 21, 2008 2:20:36 AM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by srikanthpv
1. Write a function that given a string of digits and a target value, prints where to put +'s and *'s between the digits so they combine exactly to the target value. Note there may be more than one answer, it doesn't matter which one you print.
Examples:
"1231231234",11353 -> "12*3+1+23*123*4"
"3456237490",1185 -> "3*4*56+2+3*7+490"
"3456237490",9191 -> "no solution"



I hate this kind of questions, last year i got a game interview where they gave me 1 hour to answer a bunch of question like this...

I answer as fast as possible to their questions (15minutes)... maybe not everything right... but i prefer a good conversation....

Share this post


Link to post
Share on other sites
I was thinking the same way...It took me 2 hours to reach something close by...But i dont think that guy was satisfied with it though...I am still working on the code...Will come out with it in a day...

Share this post


Link to post
Share on other sites
wait a moment...
I can easilly make up a simple algorithm that will eventually reach out but it will take forever...

kinda like

"abcdefg" ->
a+b+c+d+e+f+g ?
ab+c+d+e+f+g ?
abc+d+e+f+g ?
abcd+e+f+g ?
abcde+f+g ?> too big then
abcd+ef+g ?
abcd+efg ? not big enough then
...

but that is crap... there should be a better algorithm, no?
maybe
X / a > or <?
X / ab > or <?


no.. I cant figure it out...
whats the answer on this one?

Yours truly
K

Share this post


Link to post
Share on other sites
Does this scream "genetic programming" to anyone else? [smile]

EDIT: At any rate, as a quick and dirty solution I would probably construct a binary tree out of the digits, and iterate all the permutations of node operations looking for solutions. For a string of length N there are N-1 nodes and 3 operators (+, *, and "concat"), which is 3N-1 solutions. So not too many for a small number of digits (19683 for 10 digits), but it grows fast!

[Edited by - Zipster on November 21, 2008 5:31:39 AM]

Share this post


Link to post
Share on other sites
Here is mine in C# - took about 20 minutes.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace ConsoleApplication2
{
class Program
{
static IEnumerable<string> AllMyThingies(string input)
{
return AllMyThingies(input, 1);
}

static IEnumerable<string> AllMyThingies(string input, int offset)
{
if (offset < input.Length)
{
IEnumerable<string> a = AllMyThingies(input, offset + 1);
IEnumerable<string> b = AllMyThingies(input.Insert(offset, "+"), offset + 2);
IEnumerable<string> c = AllMyThingies(input.Insert(offset, "*"), offset + 2);
IEnumerable<string> all = a.Concat(b).Concat(c);

foreach (string v in all)
yield return v;
}

yield return input;
}

static void Main()
{
foreach (string s in Thingy("3456237490", 1185))
Console.WriteLine(s);
Console.WriteLine("Done");
Console.ReadLine();
}

static long ParseMathString(string input)
{
Regex mult = new Regex("[0-9]+\\*[0-9]+");
Regex add = new Regex("[0-9]+\\+[0-9]+");

input = RegexReplace(mult, input);
input = RegexReplace(add, input);

return long.Parse(input);
}

static long ParseWeinerMathString(string input)
{
string[] s = input.Split(new char[] { '+', '*' });
if (s.Length == 1)
return long.Parse(input);
else if (s.Length > 2)
throw new ArgumentException("Oh poopies!");
else
{
long a = long.Parse(s[0]);
long b = long.Parse(s[1]);

char op = input[s[0].Length];
if (op == '+')
return a + b;
else if (op == '*')
return a * b;
else
throw new ArgumentException("Oh poopies^2!");
}
}

static string RegexReplace(Regex regex, string input)
{
Match match;
while ((match = regex.Match(input)).Value.Length > 0)
{
long result = ParseWeinerMathString(match.Value);
input = input.Replace(match.Value, result.ToString());
}
return input;
}

static IEnumerable<string> Thingy(string input, long target)
{
foreach (string s in AllMyThingies(input))
{
if (ParseMathString(s) == target)
yield return s;
}
}
}
}




Basically, it puts a * and + in every place possible, then parses it using the ParseMathString() for complex strings and ParseWeinerMathString() for simple operations (a+b or a*b). Took 1 second to find every possible combination for "1231231234" = 11353;

And if you were wondering - yes, this is how I really program. Like it? I'm for hire!

Share this post


Link to post
Share on other sites
It's just a search space and a relatively small one. Being small a naive a try every possible combination would work well enough. At each point you could easily evaluate whether is might be possible to hit the goal (multiply up all remaining numbers) or whether you'd already blown it (add up all remaining numbers) With larger strings A* might perform quite well.

Personally as an interviewer I'd be far more interested in discussing possible techniques to solve the problem than any actual code produced. Perhaps for a junior position I would want to see code but for regular and senior programmers I think this is largely wasting peoples time.

Share this post


Link to post
Share on other sites
Well, if anyone is interested, I rewrote my piece of unreadable crap. It now takes about 100ms. Pretty much the same algorithm, but I redid the parser - now it just converts all substrings into longs once, then works with longs the rest of the way. Also, made it abort early on values too large.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication2
{
class Program
{
const long opA = -1;
const long opM = -2;
static long _target;
static int _targetLen;
static string _targetStr;

static IEnumerable<string> AllMyThingies(string input)
{
return AllMyThingies(input, 1);
}

static IEnumerable<string> AllMyThingies(string input, int offset)
{
if (offset < input.Length)
{
IEnumerable<string> a = AllMyThingies(input, offset + 1);
IEnumerable<string> b = AllMyThingies(input.Insert(offset, "+"), offset + 2);
IEnumerable<string> c = AllMyThingies(input.Insert(offset, "*"), offset + 2);
IEnumerable<string> all = a.Concat(b).Concat(c);

foreach (string v in all)
yield return v;
}

yield return input;
}

static void Main()
{
Stopwatch w = new Stopwatch();
w.Start();
foreach (string s in Thingy("3456237490", 1185))
Console.WriteLine(s);
w.Stop();
Console.WriteLine(w.ElapsedMilliseconds);
Console.ReadLine();
}

static long ParseMathString(string input)
{
string[] strs = input.Split(new char[] { '+', '*' });

foreach (string s in strs)
{
if ((s.Length > _targetLen) || (s.Length == _targetLen && s[0] > _targetStr[0]))
return -1;
}

List<long> values = new List<long>(strs.Length * 2);

int offset = -1;
for (int i = 0; i < strs.Length - 1; i++)
{
values.Add(int.Parse(strs));
offset += strs.Length + 1;

char c = input[offset];
if (c == '+')
values.Add(opA);
else if (c == '*')
values.Add(opM);
}

values.Add(long.Parse(strs[strs.Length - 1]));

if (!UBERPARSEM(values))
return -1;
if (!UBERPARSEA(values))
return -1;

return values[0];
}

static IEnumerable<string> Thingy(string input, long target)
{
_target = target;
_targetStr = target.ToString();
_targetLen = _targetStr.Length;
foreach (string s in AllMyThingies(input))
{
if (ParseMathString(s) == target)
yield return s;
}
}

static bool UBERPARSEA(List<long> lala)
{
for (int i = 1; i < lala.Count; i += 2)
{
if (lala == opA)
{
long nachos = lala[i - 1] + lala[i + 1];
if (nachos > _target)
return false;
lala[i - 1] = nachos;
lala.RemoveRange(i, 2);
return UBERPARSEA(lala);
}
}

return true;
}

static bool UBERPARSEM(List<long> lala)
{
for (int i = 1; i < lala.Count; i += 2)
{
if (lala == opM)
{
long nachos = lala[i - 1] * lala[i + 1];
if (nachos > _target)
return false;
lala[i - 1] = nachos;
lala.RemoveRange(i, 2);
return UBERPARSEM(lala);
}
}

return true;
}
}
}


Seeing as all the ParseMathString() calls now only take about 20-30ms, looks like the only place to really improve now is to just make less strings... checking every combination is clearly not ideal.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!