Sign in to follow this  
srikanthpv

Game programmer Interview question

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
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
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[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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Skeezix
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??


Experience unfortunately...

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
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)

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 this post


Link to post
Share on other sites
Quote:
Original post by GenuineXP
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] ).
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by srikanthpv
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#


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 this post


Link to post
Share on other sites
Quote:
Original post by Antheus
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.


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

Share this post


Link to post
Share on other sites
Quote:
Original post by Spodi
And 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 Spodi
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.

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 this post


Link to post
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 this post


Link to post
Share on other sites
[quote]Original post by ToohrVyk
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.

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this