I got a test in C from Cryptic Studios and it's timed so I can't look at it and then go brush up. Anyone know what kind of stuff would be on it? I would consider myself proficient with C, but I would like to know what kind of stuff would be on it.
Printable View
I got a test in C from Cryptic Studios and it's timed so I can't look at it and then go brush up. Anyone know what kind of stuff would be on it? I would consider myself proficient with C, but I would like to know what kind of stuff would be on it.
I've never applied for a programming job, so I can't help you with what might be on the test. But good luck on getting the job. Game development should be fun.
C or C++? I know you said C, but they're a MMO game studio, not a low-level driver company :)
I took a C++ test when interviewing at Sybase. Very similar to the kinds of stuff you have in university (so, not too difficult). Know your OO, and know your memory management. File i/o is useful to know without having to look it up.
This was years ago, so all I can remember was they had this one question that asked, "what does this class do?" and it was some weird recursive linked list thing.
I think mostly, they just want to see that you can code, and that you're not a total waste of their time. It really helps to narrow things down and prevent the interviewers from wasting time on duds.
I kid you not. When I do phone screens, I always ask a really dumb coding question (most of the time, it's "reverse a string"), and you'd be amazed at how many candidates are all talk.
I can't speak for cryptic studios, but they're not out to trick you with trick questions. Most candidates are too daft to answer easy, straight-forward questions, so there's almost no need for it at the starting stages. :) good luck!
Oh good. Yes, I'm certain that they said C, not C++.
My specialty is low level stuff like memory management. I should refresh myself on i/o streams, I never used them much so I always looked up parameters for those functions.
Ah I see. Then i/o streams and the likes are probably very important, because I'll probably put you into the network layer somewhere hehe. Marshalling/unmarshalling, etc.
But really, don't worry about it. Do you know what position you're going for? Like, what department?
General programmer for a gaming company. I hope that they don't ask about networking, I have no knowledge of that at all. *gets scared* Well I'm off to do it and I've got my trusty C in a Nutshell book.
Good luck mate, let us know how you get on :)
:morecrying: I didn't do good, I couldn't figure out how to do one of the questions.
Can you tell me how to do this so that I don't go nuts:
Code:Given a string of 10 characters and a number, insert multiplies and
additions to make the characters equal the number
ie
1232537859, 995 -> 123*2+35*7+8*58
christ,
they expected you to come up with code to do that?
in a timed exam?
my first thought,
target = 995;
test = 1232537859;
if test is too high,
split in half and multiply two halves
12325*37859
if still too high, try addition instead
12325+37859
if still too high, split largest half, and multiply
12325*378*59
if still too high, pick largest multiple (12325*378) and try addition
etc, etc.
testing value, if too high picking the largest section and altering the operator
once all altered and still too high, split largest number and go again
if you get too low, backtrack one step and split smallest section instead
I don't know,
there's bound to be a way to do that nice & concisely
but it's certainly not obvious, and I wouldn't want to be timed to try to figure out a way of achieving it
That's kind of how I wanted to do it too, but backtracking was impossible without recursion and I didn't think the rest of it would work recursively. The other problem was a puzzle solver, I didn't get to it, but I knew how to do it.
I thought that question was a little too hard, I spent four hours on it. :morecrying:
Anyone else think they know how to do it?
the only other way I can think of right now, is the brute force approach
start with all addition
1+2+3+2+5+3+7+8+5+9
change one addition at a time into a multiple
1*2+3+2+5+3+7+8+5+9
1+2*3+2+5+3+7+8+5+9
......
1*2*3*2*5*3*7*8*5*9
then, combine first 2 digits and go again
12+3+2+5+3+7+8+5+9
......
12*3*2*5*3*7*8*5*9
then next two
1+23+2+5+3+7+8+5+9
......
1*23*2*5*3*7*8*5*9
then combining 2 sets of 2 digits
then 3 sets of two
yadda yadda
then combining one set of three digits
etc. etc.
slowly working your way up
it'd take forever to complete
but you'd hit every possible combination
I tried to do a brute force approach at first, but I couldn't figure out how to code it. :P I tried it with for loops, then recursively, then with while loops :?
I had to write a string solver too, but I just realized that I forgot to do preserve order precedence :P
Four hours? How long was this test?!? Definitely not what I would have thought. Sorry if I led you into thinking it would be easy. That's pretty insane for a test, but I would expect most everyone to mess up on that level. If you did alright for the others, you stand a chance (and you probably should have gone right to the next question if you knew how to do it - no need to spend 4 hours on one when you can do the next in half an hour).
For this one, I'd probably just go brute force and move on, and update it if I had the time.
The brute force solution space is not that huge... You have 10 characters, and the 9 spaces between them can either be a +, a * or nothing (i.e. they're connected as part of the same number). That means the full solution space has a size of 3^9 = 19683. Come to think of it, that's pretty tiny, if you don't think of it in terms of something that has to execute within the ticks of a game. That way, for brute force, you can separate the problem into "solution generator" and "solution tester" (which evaluates the expression). That second part is arguably harder to implement on the fly.
You can also do some MAJOR pruning by cutting off any search where the result exceeds the number requested, which is also pretty easy to build into your algorithm. It really is the "evaluation" part that you have to be careful of.
All that being said, my writing about it in a laid back environment doesn't compare to the high-stress environment you were in, and if they gave you 6 hours or so for the test, then I assume you were already pretty fried when you got to it. Let us know if they call you back!
3^9? Not quiet, it's a little bit more complicated than that. 3^9 tells you how many combinations of +'s, *'s, and nothings there are, but order also matters so for each of those 19,683 combinations, you have to do a permutation of all nine values. P(9, 9) = 9! = 36,2880 so, in fact, there are 7,142,567,040 solutions. That isn't easy, even for a computer. I couldn't figure out how to do the permutations anyway. :tonguewiggle:
Order? But all the numerals are in fixed positions...
The operations order, the number's positions are fixed like you said. There were nine operators.
Not really... 3^9 = every possible combination. Permutations are meaningless. "a + b + c" is the same thing as "a + b + c"Quote:
Originally Posted by ninja9578
True, but a + b * c isn't the same as a * b + c. There are lots of repeats as in the example above, but it's still a permutation.
123+2+5+3*7+8+59 = 998
I failed.
I tried working backwards...until I had a lower number to work with, and then forwards... see below if you can make sense of it
1 2 3 2 5 3 7 8 5 9 995
995-9 = 986
986/5 = 197.2
995-(5+9)=981
981/8 = 122.6
995-(8+5+9)=973
973/7 = 139
1 2 3 2 5 3 139
123+2+5+3*7+8+59 = 998
Isn't that covered by 3^9?Quote:
Originally Posted by ninja9578
If each permutation is seen as a number in base three, a+b*c could be '12' while a*b+c would be '21', and abc would be 00. The number of permutations is then the largest number representable, ie. 3^9 - for 9 base-three digits.
Lord almighty, that's a hard one. I was recently interviewed for a .NET programmer (something I know little off) and there was a 1/2 hour exam with questions on programming ("What is polymorphism?") SQL ("What is a subquery?") and web design ("What is CSS and what is it used for?"). Was pretty easy but I got some questions wrong.
Then in the interview they asked a series of "problem solving" questions, one of which was "How would you write a system that had a web interface and could sychronously communicate between two servers". That lost me, but I made up something.
Anyhow I got the job, so :D. Think of it this way: if they're cruel enough to set that as a question, would you like to work for them?
Oh, oh, I know all those! :tongue: Why couldn't they give me questions like that? :chuckle:Quote:
Originally Posted by Identity X
If you want help on this subject message me and Ill give you my mates msn.
He kinda knows everything about it.
:D
It's covered by the 3^9Quote:
Originally Posted by ninja9578
Here, let's pick a simpler example with just 3 characters. Exhaustively, the possibilities are:
1) abc
2) a+bc
3) a*bc
4) ab+c
5) ab*c
6) a+b+c
7) a*b+c
8) a+b*c
9) a*b*c
... = 3^2 = 9 possbilities.
Your permutation argument would stipulate that in this case, there are 18 possibilities, which is not true.
Arright. I did the test probably a month ago. It was the same as yours. I did quite well, imho, but nobody contacted me ever since. Time to post the working solution to the first problem, then.
Code:
//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"
//
//Solution:
#include <stdio.h>
#include <string.h>
const char symb[3]= {'+','*',' '};
void print_sequence(FILE* file, char* deststr, int nchar)
{
int i;
for(i=0; i<nchar && deststr[i]!='\0'; i++) {
if(deststr[i]==' ') continue;
fprintf(file, "%c", deststr[i]);
}
return;
}
void transform_n_check(char* deststr, const int ndigs, const int target, short *done) {
char strcopy[ndigs*2];
char* add[ndigs];
char *p;
int i= 0;
int total= 0;
for(i=0; i<ndigs*2; i++)
strcopy[i]= deststr[i];
// find all the addends
i= 0;
add[i]= strtok(strcopy, "+");
while( (p=strtok(NULL,"+")) != NULL ) {
add[++i]= p;
}
int na= i+1;
char *mult[ndigs];
int totmult;
for(i=0; i<na; i++) {
// find all the multiplications composing this addend
int j= 0;
mult[j]= strtok(add[i],"*");
while( (p=strtok(NULL,"*")) != NULL ) {
mult[++j]= p;
}
int nm= j+1;
// multiply the multiplicands of this addend together
totmult= 1;
for(j=0; j<nm; j++) {
int k;
int temp= 0;
for(k=0; k<strlen(mult[j]); k++) { // atoi skipping spaces indicating "no operator"
if(mult[j][k]==' ') continue;
temp*= 10;
temp+= mult[j][k]-'0';
}
totmult*= temp;
}
total+= totmult;
}
*done= (total==target);
return;
}
void build(int level, char *deststr, const int ndigs, const int target, short* done) {
if(level==ndigs-1) {
transform_n_check(deststr, ndigs, target, done);
// if(*done) {
// print_sequence(stdout,deststr,ndigs*2-1);
// }
return;
}
int ns;
for(ns=0; ns<3 && !*done; ns++) { // !*done avoids printing multiple solutions
deststr[level2pos(level)]= symb[ns];
build(level+1,deststr,ndigs,target,done);
}
// if(level==0 && !*done)
// strcpy(deststr,"no solution");
return;
}
int level2pos(const int level) {
return level*2+1;
}
void calculus(char* str, const int target) {
const int ndigs= strlen(str);
int totdlen= ndigs*2-1;
char deststr[totdlen+1];
int i;
for(i=0; i<ndigs; i++) {
deststr[i*2]= str[i];
deststr[i*2+1]= '!';
}
deststr[totdlen]= '\0';
int ncombs= 3^(ndigs-1);
// str= "1234"
// deststr= "1+2+3+4"
printf("\"%s\", %d -> \"", str, target);
short done= 0;
build(0, deststr, ndigs, target, &done);
if(done)
print_sequence(stdout,deststr,totdlen*2);
else
printf("no solution");
printf("\"\n");
return;
}
int main() {
calculus("1234",408);
calculus("1231231234",11353); // "12*3+1+23*123*4"
calculus("3456237490",1185); // "3*4*56+2+3*7+490"
calculus("3456237490",9191); // "no solution"
}