Game programmer Interview question
Author
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]
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....
Author
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...
how is this even a interview?? If someone told me they where going to interview me and asked me this, I'd be pissed.
Author
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...
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
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
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]
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]
Here is mine in C# - took about 20 minutes.
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!
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!
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.
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.
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 + lala;<br> <span class="cpp-keyword">if</span> (nachos > _target)<br> <span class="cpp-keyword">return</span> <span class="cpp-literal">false</span>;<br> lala = nachos;<br> lala.RemoveRange(i, <span class="cpp-literal"><span class="cpp-number">2</span></span>);<br> <span class="cpp-keyword">return</span> UBERPARSEA(lala);<br> }<br> }<br><br> <span class="cpp-keyword">return</span> <span class="cpp-literal">true</span>;<br> }<br><br> <span class="cpp-keyword">static</span> <span class="cpp-keyword">bool</span> UBERPARSEM(List<<span class="cpp-keyword">long</span>> lala)<br> {<br> <span class="cpp-keyword">for</span> (<span class="cpp-keyword">int</span> i = <span class="cpp-literal"><span class="cpp-number">1</span></span>; i < lala.Count; i += <span class="cpp-literal"><span class="cpp-number">2</span></span>)<br> {<br> <span class="cpp-keyword">if</span> (lala<span style="font-weight:bold;"> == opM)<br> {<br> <span class="cpp-keyword">long</span> nachos = lala * lala;<br> <span class="cpp-keyword">if</span> (nachos > _target)<br> <span class="cpp-keyword">return</span> <span class="cpp-literal">false</span>;<br> lala = nachos;<br> lala.RemoveRange(i, <span class="cpp-literal"><span class="cpp-number">2</span></span>);<br> <span class="cpp-keyword">return</span> UBERPARSEM(lala);<br> }<br> }<br><br> <span class="cpp-keyword">return</span> <span class="cpp-literal">true</span>;<br> }<br> }<br>}<br></pre></div><!–ENDSCRIPT–><br><br>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.This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
