# Game programmer Interview question

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

## 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 on other sites
Quote:
 Original post by srikanthpv1. 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 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 on other sites
how is this even a interview?? If someone told me they where going to interview me and asked me this, I'd be pissed.

##### Share on other sites

Hey bro this was the easiest of the lot i got...
Good one's are yet to come...M just trying to analyze this 1 fist...

##### 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 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 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 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 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[i]));                offset += strs[i].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[i] == 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[i] == 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 on other sites
let find numbers t =  let p a b c = c^string_of_int a^b in  let n = length numbers in  let v c = code c - code '0' in  let l = v numbers.[n-1] in  let rec aux sum prod cat k s i =    let tot = sum + prod * cat in    if tot > t then None else if i < 0 then      if tot = t then Some (s "") else None    else let c = v numbers.[i] in    fold_left (fun r f -> if r <> None then r else      match f (i-1) with None -> None | Some x -> Some (s x)) None [      aux sum  prod         (c*k + cat) (10*k) (p c "" ) ;      aux sum (prod * cat)   c           10    (p c "*") ;      aux tot  1             c           10    (p c "+") ]  in aux 0 1 l 10 (p l "") (n-2)

This is an almost brute-force algorithm (the only pruning done here is to stop if the total found so far exceeds the expected total). This takes about 4ms to solve the "1231231234" = 11353 problem, and took me about 10 minutes to write.

##### Share on other sites
are there books that teach you this kind of stuff...or at least close to teaching how to solve this kind of stuff??(you know what i mean,its hard to put into words)

what do you recommend??

##### Share on other sites
Quote:
 Original post by Skeezixare there books that teach you this kind of stuff...or at least close to teaching how to solve this kind of stuff??(you know what i mean,its hard to put into words)what do you recommend??

Experience unfortunately...

##### Share on other sites
Yes, for instance Book and Book. Also peruse all parts of wikipedia related to algorithms.

The code I used was merely a brute-force search (try all combinations one after another) with implicit stack-based memoization (a consequence of the recursive approach, not of the algorithm itself) and a clever closure-based trick for outputting the result once found.

##### Share on other sites
Quote:
 Original post by ToohrVyklet find numbers t = let p a b c = c^string_of_int a^b in let n = length numbers in let v c = code c - code '0' in let l = v numbers.[n-1] in let rec aux sum prod cat k s i = let tot = sum + prod * cat in if tot > t then None else if i < 0 then if tot = t then Some (s "") else None else let c = v numbers.[i] in fold_left (fun r f -> if r <> None then r else match f (i-1) with None -> None | Some x -> Some (s x)) None [ aux sum prod (c*k + cat) (10*k) (p c "" ) ; aux sum (prod * cat) c 10 (p c "*") ; aux tot 1 c 10 (p c "+") ] in aux 0 1 l 10 (p l "") (n-2)

I know it would probably be a pain, but could you explain this pseudocode? I'm having a hard time understanding it, especially the way you use "let" to assign to several values at once (at least, that what it looks like to me [lol] ).

Interesting question. I'm going through some rigorous interviews now too, and I find the coding/algorithm questions to be a bit frustrating sometimes, especially when you only have 10 minutes to figure them out and really don't have any experience with the subject matter. And implementing sorts is a pain. [lol]

##### Share on other sites
Quote:
 Original post by GenuineXPI know it would probably be a pain, but could you explain this pseudocode? I'm having a hard time understanding it, especially the way you use "let" to assign to several values at once (at least, that what it looks like to me [lol] ).
Am not... Multiple assignment happens using let a,b = 1, 2, wheread let a b = ... defines a function 'a' with a parameter 'b'.The complete explanation:

(* Define a function "find" with parameters "numbers"   (which is the string we are analysing) and "t" (which is the   target number *)let find numbers t =  (* A printing function. Here, p 3 "*" "1+2+" outputs "1+2+3*". *)  let p a b c = c^string_of_int a^b in  (* Duh. *)  let n = length numbers in  (* Convert a character to its integer representation by transforming it     to its ASCII code and substracting the ASCII code of '0'. *)  let v c = code c - code '0' in  (* The last character in the string. This is our starting value, since     we process the string right-to-left to make parsing easier. *)  let l = v numbers.[n-1] in  (* The recursive function which processes everything. In order to evaluate     the value computed so far without having to build and parse a string, it     implements a recursive descent parser (here, "sum", "prod", "cat" and "k"     are the unrolled stack contents for grammar rules "+", "*" and "").      Parameter 's' represents the previously applied operation: it's used for     printing the result once it is found. Parameter 'i' is the current index     within the string. *)  let rec aux sum prod cat k s i =    (* Fold the stack to simulate receiving an EOF right now. *)    let tot = sum + prod * cat in    (* Overflow heuristic. If the sum so far (which can never decrease)           exceeds the target, we have to stop and backtrack. *)    if sum > t then None     (* We've reached the beginning of the stream, so there's nothing       else to do. Check if the target is reached. *)    else if i < 0 then            (* If we reached the target, return a "do nothing" string because         we're at the beginning of the string with no characters.*)      if tot = t then Some (s "") else None    (* We have to read another character. This computes its value. *)    else let c = v numbers.[i] in    (* This code attempts concatenation, multiplication and addition.        Since they all behave the same, we just put them in a list of functions        to be called, then call them until we have a solution. *)    fold_left       (* This function receives parameter 'r' representing the results         so far, and 'f' representing the next function we can try. If          'r' is a valid result, we return it. Otherwise, we look to see         if 'f' finds a solution (decreasing the index as this happens).          If a solution is found, we print the previous character and return         it. *)      (fun r f -> if r <> None then r else        match f (i-1) with None -> None | Some x -> Some (s x)) None [      (* First try: concatenation. This multiplies the character by         the current multiplier, then multiplies the multiplier by 10 *)      aux sum  prod         (c*k + cat) (10*k) (p c "" ) ;      (* Second try: multiplication. We go back once on the stack,          multiply the previous number with the multiplier, then push the         character on the stack as beginning a new number. *)      aux sum (prod * cat)   c           10    (p c "*") ;      (* Third try: addition. We go back twice on the stack and add         everything up, then push "1" as the "current product value"         and c as the "current number value". *)      aux tot  1             c           10    (p c "+") ]  (* We apply the recursive function, with a starting "current sum     value" of 0, a "current product value" of 1, and using the first      character as the "current number value". *)  in aux 0 1 l 10 (p l "") (n-2)

##### Share on other sites
Project Euler contains a lot of problems like this. Good for practicing and fun. :)

##### Share on other sites
I made a speedy algorithm that completely fails to respect order of operations. Alas. I'd have to modify it to recurse differently to keep those operations, which disallows a ton of the pruning that made it speedy. Too much work for someone else's interview [grin]

As an interesting note, this sort of thing is analogous to what my toy programming language does to convert a stream of tokens into an AST.

##### Share on other sites
Hi all...
Thats a very good way to solve the problem...But they mentioned Ansi C is not a must is always preferable....So i thought indirectly they mean its must to do in C itself then c#

##### Share on other sites
Quote:
 Original post by srikanthpvHi all... Thats a very good way to solve the problem...But they mentioned Ansi C is not a must is always preferable....So i thought indirectly they mean its must to do in C itself then c#

I find it unlikely someone will provide a C solution.

The reason is quite simple. Anyone who has dealt with such interviews in the past knows that C is implied (ANSI compliance is rarely required as such). Sometimes, C++ is also acceptable, but additional language features are never required.

As such, posting a solution in another language is just fine with respect to solving the problem, but it prevents the situation where it's possible to just copy paste the solution, especially since this type of assignments can sometimes be given out freely with longer time to submit.

What I'm simply trying to say is, someone capable of solving the problem will be able to code it in any language. There's also even a string hint in this particular problem (target value is a number, "given a string" and "a function") that can be taken advantage of in C or C++. It hints that there's little need for auxiliary structures, some complex recursive parsers or some complex class hierarchies.

But this is definitely not a C language proficiency test.

##### Share on other sites
This question was the 1 which freekd me out..But there wasnt much math in this 1 compared to the 1st....

[Edited by - srikanthpv on November 24, 2008 12:51:43 PM]

##### Share on other sites
Quote:
 Original post by AntheusI find it unlikely someone will provide a C solution.The reason is quite simple. Anyone who has dealt with such interviews in the past knows that C is implied (ANSI compliance is rarely required as such). Sometimes, C++ is also acceptable, but additional language features are never required. As such, posting a solution in another language is just fine with respect to solving the problem, but it prevents the situation where it's possible to just copy paste the solution, especially since this type of assignments can sometimes be given out freely with longer time to submit.

Or y'know, because nobody actually likes writing in C for a problem like this.

##### Share on other sites
Quote:
 Original post by SpodiAnd if you were wondering - yes, this is how I really program. Like it? I'm for hire!

I like your variable and function names :)

Quote:
 Original post by SpodiSeeing 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.

String creation can be eliminated by modifying in-place on a single copy of the string. First convert the string to a representation with alternating digits and operators. Make up some arbitrary representation for "append", for example #. This approach will require creating only a single string during the course of running the algorithm.

As noted above, pruning of too large numbers can be added because all operators +,* and append increase the final result and so termination is possible as soon as the result gets larger than the target result.

Otherwise, I second zipster's idea of trying out genetic programming. And maybe even a simple local search would work, possibly you need to throw in simulated annealing and/or random restarts if the shape of the problem state space is evil.

##### Share on other sites
[quote]Original post by sb01234
The brute force solution can be optimized a bit based on the following observation: All of +, * append will end up increasing the value of the final result. That means it's possible to use pruning to discard cases where you've not yet reached the end of the string but have already obtained a value larger than or equal to the target value.[/code]

1230456 = 6 ?

Left-to-right, 1+2+3 = 6 , so you stop.
Right-to-left, 6 = 6, so you stop.

Yet, 1+2+3+0*456 = 6 is a possible solution.

##### Share on other sites
[quote]Original post by ToohrVyk
Quote:
 Original post by sb01234The brute force solution can be optimized a bit based on the following observation: All of +, * append will end up increasing the value of the final result. That means it's possible to use pruning to discard cases where you've not yet reached the end of the string but have already obtained a value larger than or equal to the target value.[/code]1230456 = 6 ? Left-to-right, 1+2+3 = 6 , so you stop.Right-to-left, 6 = 6, so you stop.Yet, 1+2+3+0*456 = 6 is a possible solution.

Aha, didn't realize at first that zeroes were allowed