# A few interview questions

• I had an interview recently, with some fairly standard 'write this code' type questions.   In previous threads, people seemed to enjoy talking about the problems, so I thought I'd post them here for discussion:

1.  "Write a function that evaluates a polynomial.   So, you should be able to feed it the information for the equation, plus a value to evaluate it with, and return the evaluated result".

2.  "Imagine you have a 100K string filled with just the letters A-Z.  (for example "ABCBEZBAEBSHJIABHKJIH.....")  Write a function that will sort the string so that all of the As are together, all the Bs are together, all the Cs, etc. -- and in order".

3. "Imagine you have a string composed of just the chars '{([])}"  (curly braces, parens, square brackets).  Now, assume that you have normal 'mathematical rules', and that sets of parens,braces,brackets have to close in the right order.   For instance  "()", "()[]", "(({[]}))" are all valid, "(]", "([)]", "{{{{" are not.   Write a function that will take an input string and return true if the string is valid, false otherwise"

Have fun!

-cw

• The first one seems fairly standard, it should prove that the applicant can at least write a simple mathematical function and I don't think any reasonable programmer would have an issue with it:

float Polynomial (float squaredCoefficient, float normalCoefficient, float toAdd, float value)
{

float squared=valuevalue;

return (squaredCoefficientsquared) + (normalCoefficientvalue) + toAdd;
}

The second one is a bit more odd, I think that most professional programmers would use a library function to do the operation rather than try and hammer out their own version of a quick sort in an interview. Though maybe that's the point of the question, to pick up on the Not Invented Here syndrome victims?

int QsortCallback(const void pA, const void pB)
{
char A=
(char
)pA;
char B=
(char*)pB;

if (A<B)
return -1;
else if (A>B)
return 1;
return 0;
}

void SortString(char *pInput)
{
size_t len=strlen(pInput);
qsort(pInput,len,1,QsortCallback);
}

The third question is definitely a good one, at first glance I thought it was easy, but now I think about it, it does come across as kind of tricky... I thought I could do it with counting depth at first, but I eventually came up with this approach which I think is better:

typedef std::stack<char> CharStack;

bool ValidateBrackets(const char *pInput)
{
CharStack lastOpeningBraceStack;

const char *walker=pInput;
while(*walker)
{
switch(*walker)
{
case '[':
case '{':
case '(':
lastOpeningBraceStack.push(*walker);
break;
case ']':
{
if (lastOpeningBraceStack.empty())
return false;
else
{
char lastOpen=lastOpeningBraceStack.top();
if (lastOpen!='[')
return false;
lastOpeningBraceStack.pop();
}
}
break;
case ')':
{
if (lastOpeningBraceStack.empty())
return false;
else
{
char lastOpen=lastOpeningBraceStack.top();
if (lastOpen!='(')
return false;
lastOpeningBraceStack.pop();
}
}
break;
case '}':
{
if (lastOpeningBraceStack.empty())
return false;
else
{
char lastOpen=lastOpeningBraceStack.top();
if (lastOpen!='{')
return false;
lastOpeningBraceStack.pop();
}
}
break;
default:
// Return false here if want to get upset over invalid characters
break;
};
walker++;
}
return lastOpeningBraceStack.empty();
}

It's kind of a pain that I had to repeat the logic in the 3 closing brace case statements, but it's probably a bit more readable.

• @Devi said:

float Polynomial (float squaredCoefficient, float normalCoefficient, float toAdd, float value)

That's not an arbitrary polynomial.    What if I wanted   2x^5 + 4x^4 + x^3 + 15x^2 - x + 1 ?

@Devi said:

The second one is a bit more odd, I think that most professional programmers would use a library function to do the operation rather than try and hammer out their own version of a quick sort in an interview. Though maybe that's the point of the question, to pick up on the Not Invented Here syndrome victims?

int QsortCallback(const void *pA, const void *pB)

There's an O(n) solution if you're willing to absorb a relatively small memory hit; and with the stated requirements (100K string), that amounts to doing it in 1/16 the time if you're willing to spend a tiny fraction more memory.

@Devi said:

The third question is definitely a good one, at first glance I thought it was easy, but now I think about it, it does come across as kind of tricky... I thought I could do it with counting depth at first, but I eventually came up with this approach which I think is better:

typedef std::stack<char> CharStack;

Yup, at least, that's around about how I answered it.  I didn't repeat the logic three times, but I did miss that I could just check that the stack was empty at the end and instead implemented some counters that i had to get rid of later.

-cw

• @CodeWhisperer said:

1.  "Write a function that evaluates a polynomial.

Oh, my bad, I guess I didn't specifiy that it was supposed to be an arbitrary polynomial.  I thought i did... my mind is going in my old age apparently.

-cw

• @CodeWhisperer said:

There's an O(n) solution if you're willing to absorb a relatively small memory hit; and with the stated requirements (100K string), that amounts to doing it in 1/16 the time if you're willing to spend a tiny fraction more memory.

-cw

For the win!

#define MIN_CHARACTER 'A'
#define NUM_CHARACTERS 26

void BucketSort(char *pInput)
{
size_t Buckets[NUM_CHARACTERS]={0};

char *pWalker=pInput;
while(*pWalker)
{
char thisChar=*pWalker;
assert(thisChar>=MIN_CHARACTER || thisChar<MIN_CHARACTER+NUM_CHARACTERS); // Invalid character!
Buckets[thisChar-MIN_CHARACTER]++;
pWalker++;
}

pWalker=pInput;
for (int i=0; i<NUM_CHARACTERS; i++)
{
memset(pWalker,MIN_CHARACTER+i,Buckets[i]);
pWalker+=Buckets[i];
}
}

• Ding ding ding ding ding!

>g<

• 1.

`float evalPolynomial( float coefficients[], int numberOfCoefficients, float x ){    float poly = 0;    for ( int i = 0; i < numberOfCoefficients; i++ )    {        poly = ( poly * x ) + coefficients[i];    }    return poly;}`

2. Bucket sort. Make an array with 26 slots initialized to 0 then scan the array and add 1 to the corresponding array element for each element in the string. Then overwrite the old string with the appropriate number of A's then B's and so on.

3. Implement a push-down automata.

tatsu

• @CodeWhisperer said:

@Devi said:

float Polynomial (float squaredCoefficient, float normalCoefficient, float toAdd, float value)

That's not an arbitrary polynomial.    What if I wanted   2x^5 + 4x^4 + x^3 + 15x^2 - x + 1 ?

What if you wanted 2x^3y^2 + 4xy^3 + 5xy + 6x^2 + 1 ?

It's actually quite long-winded to answer, when you realise that polynomials have an arbitrary number of variables in them. I would have asked them to specify the question more completely - and if it was written by somebody who knows what they are doing, that is probably the point of the question.

@Devi said:

The third question is definitely a good one, at first glance I thought it was easy, but now I think about it, it does come across as kind of tricky... I thought I could do it with counting depth at first, but I eventually came up with this approach which I think is better:

typedef std::stack<char> CharStack;

Yup, at least, that's around about how I answered it.  I didn't repeat the logic three times, but I did miss that I could just check that the stack was empty at the end and instead implemented some counters that i had to get rid of later.

And it is a standard result in parsing theory that you cannot solve this problem without a data structure that is capable of behaving like a stack.

• @asuffield said:

I would have asked them to specify the question more completely

Then you should have asked me to specify the question more completely.   The way it was worded to me made it clear that it was a polynomial of a single variable, I should have been more specific in transcribing it here.

And it is a standard result in parsing theory that you cannot solve this problem without a data structure that is capable of behaving like a stack.

Ok...

-cw

• @tatsu said:

float evalPolynomial( float coefficients[], int numberOfCoefficients, float x )
{
float poly = 0;
for ( int i = 0; i < numberOfCoefficients; i++ )
{
poly = ( poly * x ) + coefficients[i];
}
return poly;
}

That's a very cool formulation for calculating the polynomial, I wish I had thought of it.

I'm working through some stuff on APL lately and one of the examples I worked through was calculating a polynomial just like this and it was about 10 chars, half of which don't appear on a standard keyboard.  I really wracked my brain to pull it out as a semi-joking answer, but just couldn't get it in time.  Dang.

-cw

• @CodeWhisperer said:

I'm working through some stuff on APL lately and one of the examples I worked through was calculating a polynomial just like this and it was about 10 chars, half of which don't appear on a standard keyboard.

Sketching it out on paper, I think it ended up looking something like:

+/CxX*ipC

(where C is the array of coefficients, X is the value you are evaluating on, the lower case x is actually a 'multiply' sign, i is an 'iota', and p is a 'rho')

Oh...and I think I had to set the index origin to zero, it defaults to 1 normally, otherwise you have to tuck a -1 in there.

Ah well, keeps me off the streets.

-cw

• Number 3:

```sub is_balanced(\$) {
my \$s = shift;
while (\$s =~ s,\(\)|\[\]|\{\},,g) {}
length \$s == 0;
}
print is_balanced "()", "\n";
print is_balanced "()[]", "\n";
print is_balanced "({{[]}})", "\n";
print is_balanced "(]", "\n";
print is_balanced "([)]", "\n";
print is_balanced "{{{{", "\n";
```

• /me stabs the edit time-out

And yes, I know this isn't going to be very efficient on long strings.  But the code's a whole lot simpler than the previous version. :-P

• ...and the boring but reasonably efficient version, just for the record:

```sub is_balanced(\$) {
my @stack;
foreach my \$c (split(//, shift)) {
if (@stack && \$stack[\$#stack] eq \$c) {
pop(@stack);
} else {
push(@stack, {'('=>')','['=>']','{'=>'}'}->{\$c} || "");
}
}
@stack == 0;
}
print is_balanced "()", "\n";
print is_balanced "()[]", "\n";
print is_balanced "({{[]}})", "\n";
print is_balanced "(]", "\n";
print is_balanced "([)]", "\n";
print is_balanced "{{{{", "\n";
```

• Devi obviously likes typing. Even in old VB it's simpler than that. Working from L to R, f you get a start bracket, add it to the end of a test string. If you get an end bracket, then if it matches the last byte in your test string, remove last byte from test string, otherwise it's an error. At end, ensure all have been paired off.

Function CalcBraces(sInput As String)
Dim sOutput As String, lLen As Long, lPos As Long, sByte As String
lLen = Len(sInput)
For lPos = 1 To lLen
sByte = Mid(sInput, lPos, 1)
' Opening bracket, add to end of test string
If sByte = "{" Or sByte = "[" Or sByte = "(" Then
sOutput = sOutput & sByte
Else
' Closing bracket. If matches last byte, clear last byte. Else error.
If (sByte = "}" And Right(sOutput, 1) <> "{") Or _
(sByte = "]" And Right(sOutput, 1) <> "[") Or _
(sByte = ")" And Right(sOutput, 1) <> "(") Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
sOutput = Left(sOutput, Len(sOutput) - 1)
End If
Next
' Check all paired off
If sOutput <> "" Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
MsgBox "OK"
End Function

• @vr602 said:

Devi obviously likes typing. Even in old VB it's simpler than that. Working from L to R, f you get a start bracket, add it to the end of a test string. If you get an end bracket, then if it matches the last byte in your test string, remove last byte from test string, otherwise it's an error. At end, ensure all have been paired off.

Function CalcBraces(sInput As String)
Dim sOutput As String, lLen As Long, lPos As Long, sByte As String
lLen = Len(sInput)
For lPos = 1 To lLen
sByte = Mid(sInput, lPos, 1)
' Opening bracket, add to end of test string
If sByte = "{" Or sByte = "[" Or sByte = "(" Then
sOutput = sOutput & sByte
Else
' Closing bracket. If matches last byte, clear last byte. Else error.
If (sByte = "}" And Right(sOutput, 1) <> "{") Or _
(sByte = "]" And Right(sOutput, 1) <> "[") Or _
(sByte = ")" And Right(sOutput, 1) <> "(") Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
sOutput = Left(sOutput, Len(sOutput) - 1)
End If
Next
' Check all paired off
If sOutput <> "" Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
MsgBox "OK"
End Function

Using a string when you should be using a stack? WTF?!

• @vr602 said:

Devi obviously likes typing. Even in old VB it's simpler than that. Working from L to R, f you get a start bracket, add it to the end of a test string. If you get an end bracket, then if it matches the last byte in your test string, remove last byte from test string, otherwise it's an error. At end, ensure all have been paired off.

Function CalcBraces(sInput As String)
Dim sOutput As String, lLen As Long, lPos As Long, sByte As String
lLen = Len(sInput)
For lPos = 1 To lLen
sByte = Mid(sInput, lPos, 1)
' Opening bracket, add to end of test string
If sByte = "{" Or sByte = "[" Or sByte = "(" Then
sOutput = sOutput & sByte
Else
' Closing bracket. If matches last byte, clear last byte. Else error.
If (sByte = "}" And Right(sOutput, 1) <> "{") Or _
(sByte = "]" And Right(sOutput, 1) <> "[") Or _
(sByte = ")" And Right(sOutput, 1) <> "(") Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
sOutput = Left(sOutput, Len(sOutput) - 1)
End If
Next
' Check all paired off
If sOutput <> "" Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
MsgBox "OK"
End Function

But your algorithm is identical to mine, you just take the rather odd (though not particularly bad) choice to use a string instead of a stack... Anyways, I bet mine runs faster than yours :p

• @Devi said:

But your algorithm is identical to mine, you just take the rather odd (though not particularly bad) choice to use a string instead of a stack... Anyways, I bet mine runs faster than yours :p

Isn't his string just a different form of a stack?  (There's probably some equivalence theorem for stacks I should know about, but I'm lazy and don't want to look it up).

@Devi said:

But your algorithm is identical to mine, you just take the rather odd (though not particularly bad) choice to use a string instead of a stack... Anyways, I bet mine runs faster than yours :p

Isn't his string just a different form of a stack?  (There's probably some equivalence theorem for stacks I should know about, but I'm lazy and don't want to look it up).

Similar in many respects in most programming languages in the way it can be used, except strings are immutable, which means you have to create a completely new string every time you change it, which is sloooooow.  But you could use it as a stack, I suppose.  Just because you can play Russian Roulette with a pistol with six bullets in it doesn't mean you should.

• @durnurd said:

Similar in many respects in most programming languages in the way it can be used, except strings are immutable, which means you have to create a completely new string every time you change it, which is sloooooow.  But you could use it as a stack, I suppose.  Just because you can play Russian Roulette with a pistol with six bullets in it doesn't mean you should.
Just because you can implement strings as immutables, doesn't mean you should.

• @Daid said:

@durnurd said:
Similar in many respects in most programming languages in the way it can be used, except strings are immutable, which means you have to create a completely new string every time you change it, which is sloooooow.  But you could use it as a stack, I suppose.  Just because you can play Russian Roulette with a pistol with six bullets in it doesn't mean you should.
Just because you can implement strings as immutables, doesn't mean you should.

Yet don't most of the most-used languages have immutable strings?

• @CodeWhisperer said:

3. "Imagine you have a string composed of just the chars '{([])}"  (curly braces, parens, square brackets).  Now, assume that you have normal 'mathematical rules', and that sets of parens,braces,brackets have to close in the right order.   For instance  "()", "()[]", "(({[]}))" are all valid, "(]", "([)]", "{{{{" are not.   Write a function that will take an input string and return true if the string is valid, false otherwise"

I would remove bracket pairs '()', '[]' and '{}' from the string repeatedly until no more removals can be done. If I don't end up with an empty string the original string was invalid.

• @MetalPig said:

@CodeWhisperer said:
3. "Imagine you have a string composed of just the chars '{([])}"  (curly braces, parens, square brackets).  Now, assume that you have normal 'mathematical rules', and that sets of parens,braces,brackets have to close in the right order.   For instance  "()", "()[]", "(({[]}))" are all valid, "(]", "([)]", "{{{{" are not.   Write a function that will take an input string and return true if the string is valid, false otherwise"

I would remove bracket pairs '()', '[]' and '{}' from the string repeatedly until no more removals can be done. If I don't end up with an empty string the original string was invalid.

Valid, slow and naive. The best part is you picked a bad way to do it even though two better stack-based approaches have been presented in this thread. Even a bad stack-based approach will be O(n) in time and space complexity (visit each character once, left-to-right). A pair-removal approach would be O(n^2) (for each iteration, look for a pair - reduces to n + n-1 + n-2 + ...= (n + n^2)/2). Not that strings of brackets get long enough for this to be a big problem, but c'mon.

• @Welbog said:

@MetalPig said:
@CodeWhisperer said:
3. "Imagine you have a string composed of just the chars '{([])}"  (curly braces, parens, square brackets).  Now, assume that you have normal 'mathematical rules', and that sets of parens,braces,brackets have to close in the right order.   For instance  "()", "()[]", "(({[]}))" are all valid, "(]", "([)]", "{{{{" are not.   Write a function that will take an input string and return true if the string is valid, false otherwise"

I would remove bracket pairs '()', '[]' and '{}' from the string repeatedly until no more removals can be done. If I don't end up with an empty string the original string was invalid.

Valid, slow and naive. The best part is you picked a bad way to do it even though two better stack-based approaches have been presented in this thread. Even a bad stack-based approach will be O(n) in time and space complexity (visit each character once, left-to-right). A pair-removal approach would be O(n^2) (for each iteration, look for a pair - reduces to n + n-1 + n-2 + ...= (n + n^2)/2). Not that strings of brackets get long enough for this to be a big problem, but c'mon.

Not to mention that the dry description of "removing bracket pairs" would pass the string "([)]" as valid, nor that any practical application would undoubtedly contain more than bracket chars, making Empty String a rather unsufficient qualifier.

• @dhromed said:

@Welbog said:
@MetalPig said:
@CodeWhisperer said:
3. "Imagine you have a string composed of just the chars '{([])}"  (curly braces, parens, square brackets).  Now, assume that you have normal 'mathematical rules', and that sets of parens,braces,brackets have to close in the right order.   For instance  "()", "()[]", "(({[]}))" are all valid, "(]", "([)]", "{{{{" are not.   Write a function that will take an input string and return true if the string is valid, false otherwise"

I would remove bracket pairs '()', '[]' and '{}' from the string repeatedly until no more removals can be done. If I don't end up with an empty string the original string was invalid.

Valid, slow and naive. The best part is you picked a bad way to do it even though two better stack-based approaches have been presented in this thread. Even a bad stack-based approach will be O(n) in time and space complexity (visit each character once, left-to-right). A pair-removal approach would be O(n^2) (for each iteration, look for a pair - reduces to n + n-1 + n-2 + ...= (n + n^2)/2). Not that strings of brackets get long enough for this to be a big problem, but c'mon.

Not to mention that the dry description of "removing bracket pairs" would pass the string "([)]" as valid, nor that any practical application would undoubtedly contain more than bracket chars, making Empty String a rather unsufficient qualifier.

I read "removing bracket pairs" as removing an opening bracket followed immediately by a closing bracket - essentially removing the innermost juxtaposed brackets. Your example doesn't have any, thus would not result in an empty string.

That said, the specification to which you reply was somewhat lacking, (what I took your phrase 'dry description' to mean,) by omitting this salient fact.

• @dhromed said:

@Daid said:

@durnurd said:
Similar in many respects in most programming languages in the way it can be used, except strings are immutable, which means you have to create a completely new string every time you change it, which is sloooooow.  But you could use it as a stack, I suppose.  Just because you can play Russian Roulette with a pistol with six bullets in it doesn't mean you should.
Just because you can implement strings as immutables, doesn't mean you should.

Yet don't most of the most-used languages have immutable strings?

Not exactly, it's just Java, .NET, and derivatives that force them on you (and Java strings are not entirely immutable, they're just hard to mutate). It's the sort of thing they would do, but it's not necessarily a good idea (nobody ever accused any of that family of languages of being shining examples of the right way to design languages).

Most modern languages do have a form of immutable strings available, but it's usually a secondary variant on the 'normal' string construct (like const char * in C).

• @dhromed said:

Not to mention that the dry description of "removing bracket pairs"

Dry? I specified them: "()", "[]" and "{}".

@dhromed said:

would pass the string "([)]" as valid,

No it wouldn't. Your string doesn't contain any of the pairs I mentioned.

• @PJH said:

That said, the specification to which you reply was somewhat lacking,

As you can tell from my post count, I'm new, and don't know in detail what's expected and what's not done. I'm learning fast here

• @MetalPig said:

@PJH said:

That said, the specification to which you reply was somewhat lacking,

As you can tell from my post count, I'm new, and don't know in detail what's expected and what's not done. I'm learning fast here

I'm not entirely old on here myself, but when giving specifications (anywhere) it's usually better to err on verbosity than ambiguity

Where I work, some of the specifications are usually laden with ambiguity and while not WTF-worthy to deserve mention on here, do get my goat when I've interpreted it "the way it was done last time, and the time before" only to be told some development time down the line "no, that's not what we meant."

• @MetalPig said:

@CodeWhisperer said:

3. "Imagine you have a string composed of just the chars '{([])}"  (curly braces, parens, square brackets).  Now, assume that you have normal 'mathematical rules', and that sets of parens,braces,brackets have to close in the right order.   For instance  "()", "()[]", "(({[]}))" are all valid, "(]", "([)]", "{{{{" are not.   Write a function that will take an input string and return true if the string is valid, false otherwise"

I would remove bracket pairs '()', '[]' and '{}' from the string repeatedly until no more removals can be done. If I don't end up with an empty string the original string was invalid.

This does require looping through the string up to half the number of characters in the string.  A stack-based approach would only need to go through once.

As for immutable strings... well, I don't imagine using a simple char * would allow for easy stack-based operation if you were planing on just mutating the string.

• @Welbog said:

@vr602 said:

Devi obviously likes typing. Even in old VB it's simpler than that. Working from L to R, f you get a start bracket, add it to the end of a test string. If you get an end bracket, then if it matches the last byte in your test string, remove last byte from test string, otherwise it's an error. At end, ensure all have been paired off.

Function CalcBraces(sInput As String)
Dim sOutput As String, lLen As Long, lPos As Long, sByte As String
lLen = Len(sInput)
For lPos = 1 To lLen
sByte = Mid(sInput, lPos, 1)
' Opening bracket, add to end of test string
If sByte = "{" Or sByte = "[" Or sByte = "(" Then
sOutput = sOutput & sByte
Else
' Closing bracket. If matches last byte, clear last byte. Else error.
If (sByte = "}" And Right(sOutput, 1) <> "{") Or _
(sByte = "]" And Right(sOutput, 1) <> "[") Or _
(sByte = ")" And Right(sOutput, 1) <> "(") Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
sOutput = Left(sOutput, Len(sOutput) - 1)
End If
Next
' Check all paired off
If sOutput <> "" Then
MsgBox "Error " & sByte & " at position " & CStr(lPos)
Exit Function
End If
MsgBox "OK"
End Function

Using a string when you should be using a stack? WTF?!

Thanks... My thinking

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.