JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Foiled by a Div2-250! | Reply
I got asked in interview:
"Write a C function that accepts a sorted lowercase string, and returns a string containing in sorted order one of each character present in the input".
void Func(char *str, int length);

I got flustered (unusual at interview for me) and produced something like this:
void Func(char *str,int length)
{
 bool present[26]={false};
 for(int i=0;i<length;++i)
 {
  present[str[i]-'a']=true;
 }
 for(int i=0,p=0;i<26;++i)
 {
  if(present[i])
   str[p++]=(char)(i+'a');
 }
 str[p]='\0';
}

Pretty special, eh?
Re: Foiled by a Div2-250! (response to post by d000hg) | Reply
It is amazing how simple questions can seem very difficult when you are in an interview.

I do like looking at interview style questions though because they tend to be designed to test algorithmic and technical skills.

I like the idea of a thread containg interview questions so I will follow suit....

Here is a simple one I faced recently....

void reverse(char *abc1) {
 
	char c;
	char *abc2;
 
}



Input = null terminated character string.

Without using any other variables complete the function so that the input char string is reversed

eg. Topcoder -> redocpoT
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
Did they give you a compiler to work with or did you have to write the code out by hand? I got it but I had to fiddle with it for a few minutes. I definitely couldn't have written this out by hand and got it right the first time as it's pretty easy to be one off on the pointers, etc. :)

void reverse(char *abc1) {
    char c;
    char *abc2;
    
    c = strlen(abc1)-1;
    abc2 = new char(c);
    abc2 += c;
    while(*abc1 != '\0') {
      *abc2 = *abc1;
      --abc2;
      ++abc1;
    }
    ++abc2;
    cout<<"abc2="<<abc2<<endl;
    abc1 = abc2;
}
Re: Foiled by a Div2-250! (response to post by dcp) | Reply
This is the solution I came up with (hasn't been tested):
void reverse(char *abc1)
{ 
	char c;
	char *abc2;
 
	abc2 = abc1;
	while (*abc2 != '\0')
	    abc2++;
	abc2--;
	while (abc2 > abc1)
	{
	    c = *abc1;
	    *abc1 = *abc2;
	    *abc2 = c;
	    abc1++;
	    abc2--;
	}
}
I assumed that without using any other variables also meant without allocating any new memory and that the string was supposed to be reversed in place.
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
I don't think you are right here.

Where is abc1 pointing to?

I negelected to mention that you cannot assign new memory so your assumption was correct.

The point is when you are under pressure and you haven't got a compiler to help you it is very easy to make simple mistakes as I did in the interview.

I got there after a couple of iterations and the interviewers were happy with that.
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
I just tested it and it seems to work ok - input 'TopCoder' gives output 'redoCpoT' as expected. What did you think was the problem with it? abc1 points to the start of the substring that still needs to be swapped.
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
I think that what Stroker_Ace was missing that *abc1 is passed by the value, and outside the function the initial pointer is still pointing to the begining of the string.
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
I may be wrong but the loop exits when abc1 >= abc2.

With input of "Topcoder" this is when abc1 and abc2 both point at 'c'.

I think you need something like the following

for (;;) {
 
	++abc2;
 
	if (*abc2 == '\0') return;
 
   	--abc1;
}


Actually, come to think of it I'm not sure the problem (as specified in my interview) specified how the string was passed to the function or that there even WAS a function! (I guess I am always striving for reuseability!!!!) it just said swap a string using these three variables, one of which I assumed was a function parameter.

Perhaps my question was badly specified and I take your points slex and aussie
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
I'm still not sure what you're saying. This is what the string looks like at the beginning of each iteration (the 1 indicates the character that abc1 points to, and the 2 the character that abc2 points to):
1      2
Topcoder\0
 
 1    2
ropcodeT\0
 
  1  2
repcodoT\0
 
   12
redcopoT\0
 
   21     <-- abc1 >= abc2 so it terminates
redocpoT\0
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
He wants abc1 to point back to the beginning after the end of routine.
To do it you can add other loop going with both pointers in the opposite directions until the character after *abc2 is \0
Re: Foiled by a Div2-250! (response to post by slex) | Reply
Yeah, I guess thats what I assumed I had to do (as did my interviewers!).

Has anyone got any more of these questions they have been posed in interviews?

They are frustrating but enjoyable at the same time.
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
Well, the pointer is on the stack, so it doesn't matter if it is not reset to the beginning of the string. If it had been passed as an address to a pointer, that would have been a different story. Manipulating abc1 doesn't change the caller's abc1 pointer.

Edit: I didn't see that rserranop stated this in a comment in his code above.
Re: Foiled by a Div2-250! (response to post by slex) | Reply
void reverse(char *str1)
{
   char c = str[0];
   str[0]='\0';
   char *str2;
   while(*str1)
      str1++;
   str--;
   while(*str1){
      *str2=*str1;
      str2++;
      str1--;
   }
   *str2=c;
 
}


Is this ok?
Re: Foiled by a Div2-250! (response to post by slex) | Reply
void reverse(char * str1)
{
   char * str2=str1+strlen(str1)-1;
   while(*str1)
   {
       char c = *str2;
       *str2=*str1;
       *str1=c;
       str2--;
       str1++;
   }
   *str2='\0';
   //even when at the end str1 doesn`t point to the array. The pointer by value isn`t modified so the caller has the answer.
}
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
I assumed that without using any other variables also meant without allocating any new memory and that the string was supposed to be reversed in place.

That wasn't explicitly stated in the problem statement, so I took the liberty of exploiting it.
Re: Foiled by a Div2-250! (response to post by dcp) | Reply
No compiler was provided.

The interviewers seemed more interested in my approach.

BTW,

1. What if strlen > max char?

2. You haven't returned the correct value!

3. You edited your code whilst I was typing this!
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
You haven't returned the correct value!

Yeah, I realized that the original pointer had to point to the reversed string so that's why I made the edit. Not to be a nitpick, but this method doesn't "return" anything because the return type is void.

You're right though about the strlen being greater than max char value, I would have gotten burnt on that :)
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
Thing is, any question "write a function to do ..." is quite hard as interview questions go - often C++ questions are asking standard things like "why won't this compile" or "why will this not work right" (and 9 times out of 10 it's a question on inheritence, virtuals or copy constructors).
But being on TC means that's exactly what I do a lot already. I can't answer the questions requiring good algorithm knowledge but the kind asked in interview aren't likely to be of that sort - so I should be in a great position compared to most programmers.
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
void reverse(char *abc1) {
	char *abc2 = abc1;
	while(*abc2!=0) abc2++;
	abc2--;
	while(abc2>abc1) {
		*abc1 += *abc2;
		*abc2 = *abc1 - *abc2;
		*abc1 = *abc1 - *abc2;
		abc1++;
		abc2--;
	}
}


One less variable ;-)
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
void reverse(char *abc1) {
 
	char c;
	char *abc2=abc1;
      
        if(!*abc1) return;
        while(!*abc2) abc2++;
        abc2--;
        c = *abc2;
        *abc2 = 0;
        reverse(abc1+1);
        *abc2 = *abc1;
        *abc1 = c;  
}
 
Re: Foiled by a Div2-250! (response to post by d000hg) | Reply
I'll have go a seeing as I have been a bit picky on everyone else!. Untested so probably incorrect!!


void Func(char *str, int length) {
 
	int last = 0;
 
	for (int i = 0; i <= length; ++i) 
 
		if ( *(str + last) != *(str + i))
			*(str + (++last)) = *(str + i); 
	
	*(str + (++last)) = '\0';
 
}
Re: Foiled by a Div2-250! (response to post by Stroker_Ace) | Reply
And how come this int i is not declaring new variables.

[Edit]Irrelevant, I got lost in the threads tree.
Re: Foiled by a Div2-250! (response to post by slex) | Reply
He's solving d000hg's problem, not his own. It didn't have that constraint.
Meh? (response to post by d000hg) | Reply
Maybe I'm missing something - is there something wrong with your code?

Looks fine to me. Sure, you didn't take advantage of the string coming in sorted - but in terms of production code, I like your method a lot more than a clever/unreadable solution that tries to work with str in place in one pass.

All in all, I don't think this problem gives you the opportunity to demonstrate anything substantive.

Whenever I've administered testing for applicants, I've done the following:

1. Narrowed the field by sending out a TopCoder style challenge involving a non-trivial problem.
2. For promising applicants, we have the coder in. I sit the coder down and have them work through a real problem with our normal development tools.

Naturally, this kind of thing is only part of evaluating an applicant - but it gives me a good feel for someone's coding skill and adaptability. Writing horrible code on a blackboard does not, at least for me.
Re: Meh? (response to post by jmzero) | Reply
I thought the exact same thing, i.e. that I was missing something. Turns out, there isn't actually anything wrong with his code. I think it's his wording in his post that's misleading, making it seem as though we're supposed to be searching for a bug. ;-)
Re: Meh? (response to post by NeverMore) | Reply
Not only that, it's very nearly the best you can do (you can break out of the loop when you've found everything, which should be better on longer inputs.)
Re: Meh? (response to post by Insight) | Reply
Given that the input is sorted (and heavily constrained), if you had a huge input you could do some binary-search-esque stuff to find which letters are present without looking at a large percentage of the letters. But without some idea that there's going to be large inputs, I don't think it makes sense to jump in with that kind of optimization.

And that's the problem with this kind of problem - even if you want to demonstrate some cleverness and have a good grasp of the problem, there's no way to predict how you're being judged. d000hg's solution would have met my criteria very well - it's easy to read, easy to add to, and performs well. Is that what they wanted? Or did they want a "edit-as-you-pass-through" clever solution (which I think is horrible - negligible performance benefit over d000hg's approach, and painful to work with)? Or did they want a high-performance, binary-search-ish solution?

Whatever solution they wanted, they could have come up with a challenge that would test that skill specifically - instead of a challenge that tests your applicants ability to guess what you're looking for.
Re: Meh? (response to post by jmzero) | Reply
d000hg does not get problem correctly.

1. If we are given length for some reasons - how to return length of resulting string ? Null-terminating - but why original string is no not null-terminated ?
2. Where the heck validation for length of string in his code ? For example is length is zero (or much worse - negative) - he is touching string for some reasons.
3. Lowercase letters - but is this guaranteed ? What if something wrong in input - his program will crash touching bad stack memory.


You must understand - TopCoder algorithm skills are DIFFERENT from real skills companies looking for. They need something a lot of text books does not teach - making programs work regardless on how stupid user input is and how hostile environment they are deployed.
Re: Meh? (response to post by TAG) | Reply
You must understand - TopCoder algorithm skills are DIFFERENT from real skills companies looking for.


I've worked as a programmer in "real" companies for around 9 years, managed a lot of hiring, and dealt with high level IT staff from a lot of large companies. I can say with some confidence that different companies prioritize a lot of different things.

Maybe the interviewer did want someone to do that input validation. Or maybe they think that's a waste of time, and the person should have just solved the problem given. If my experience is any guide, they likely wanted to see how clever an algorithm could be written. But honestly, you can't know what they were after, and as an interviewee there's no safe plan except perhaps to ask: Do you want me to validate inputs? Do you want me to do this with a small, simple algorithm or something faster?

As an interviewer, the smart and fair plan is to ask a better question.
Re: Meh? (response to post by jmzero) | Reply
Correct. Most of people simply don't get pointers thing at all.
But this is expected from best candidate to ask all those questions.
Re: Meh? (response to post by jmzero) | Reply
As a mainly commercial programmer I still find it hard to switch off the part of my brain that wants to validate the input provided in SRMs!

If I was interviewing someone and posed one of the problems stated in this thread then they would get a 'bonus point' for asking questions about the range and validity of input.
Re: Meh? (response to post by jmzero) | Reply
"edit-as-you-pass-through" clever solution (which I think is horrible - negligible performance benefit over d000hg's approach, and painful to work with)

Can you elaborate on that? I don't see either why it is faster or why it is painful to work with. I have no trouble working with unique in C++ and that's how it is implemented. The reason is that it generalizes for arbitrary large alphabets. Also, I wouldn't mind maintaining the following.
// requires that s is a sorted null terminated string
// ensures that repeated letters in s are removed
// returns a pointer to the new end of the string
// ensures *result == 0
char* unique(char* s) {
  // s points to the last saved character
  // t points to the character currently examined
  char* t = s;
  do {
    if (*++t != *s) *++s = *t;
  } while (*t);
  return s;
}
I agree with you that the question is horrible. I would be very suspicious if an interviewer asks me to write a function that returns something and the signature has void for the return type. I would be even more suspicious in I'm working with C strings and there is an extra length parameter. I was also about to write a message asking what's wrong with d000hg's solution. (BTW, d000hg, your handle is horrible. It took me more time to spell it correctly than to write the rest of the message :) )

PS: In fact, I would prefer to use a smarter language that allows me to write at least the method contract comment in a way understood by tools. (for example Spec#, Java+JML, Eiffel)
Re: Meh? (response to post by rgrig) | Reply
I agree with you about d000hg's handle. For a long time I kept trying to spell it as something like dh00g, though I don't know why.
Re: Meh? (response to post by rgrig) | Reply
Well, I suppose the maintainability depends where you imagine this is going. The solution you show does move seamlessly to a longer alphabet (well, up to 256 characters, at least with that data type) - but if, say, you're going to change it to "ignore spaces in the input" or something then it's a little more awkward. With an abstract problem like this, I was probably too quick to jump to a conclusion on what kind of approach might be most maintainable - again the question is not really great.

And I suppose it also depends on the staff you have. To a lot of journeyman programmers, the code you wrote is pretty much gibberish. To others such as yourself (or most people here, I'd guess) that's a natural way to program. But writing code that's easily legible to a range of possible future staff is a worthwhile consideration - at least in many businesses.

As to speed, I think the second solution is going to run slightly faster than d000hg's - but only by a small factor (there's no complexity difference, unless the alphabet size dominates over the string length). But, in general, moving the pointers should be faster than using array indexes, and you don't have to build the string at the end (which, again, is only going to be significant if there's a large alphabet and a short string). To be clear - I wasn't trying to highlight the performance difference, rather I was trying to downplay it as very minor.
Re: Meh? (response to post by jmzero) | Reply
Since indexing an array is the same number of low-level instructions as dereferencing a pointer, the only possible difference I can see is that you might use more registers to do the array indexing, so downplaying it is appropriate :-)

Also, if you are in an interview where the interview seems to be asking you to do all kinds of trivial low-level optimizations, ask them if they use a good optimizing compiler :-p

I remember doing a question in an interview once, it was something to the effect of "write an algorithm to draw a horizontal line on a PDA with a 320x240 monotonic screen whose screen buffer is represented by an array of 32-bit integer bitmasks".

Well, as I started moving along on the whiteboard, I started noticing I was dividing (and modding) by 32 alot, and I started converting those statements to >>5 (and &31) as I was writing. Where the beginning of my code was clear and slow, the end of my code was convoluted and fast.

Then he surprised me by saying that a good optimizing compiler would have probably done most or all of those optimizations for me if I just left the code readable :-) We did have a good discussion about how one could determine whether those optimizations happen or not, and what to do if the more obscure code actually is faster.
Re: Meh? (response to post by Kawigi) | Reply
Since indexing an array is the same number of low-level instructions as dereferencing a pointer, the only possible difference I can see is that you might use more registers to do the array indexing, so downplaying it is appropriate :-)


Well, *(str + 5) is the same as str[5], but q=str[++i] is doing something different than q=++str and I can't imagine one or the other isn't going to be a little faster. Though I suppose the faster one might be the opposite of the one I picked initially - as I think there is a family of fast instructions for doing operations on [bp+ex] (so you could use ex for i). But I don't really remember x86 assembler at all - so I should probably be quiet before I say anything else that is almost certainly embarrassingly wrong.

I used to be part of the game/demo scene and worry about this kind of thing quite a bit - but even if I remembered that stuff, things have changed "a bit" since the 386. As you suggest - the value of trying to game this kind of thing is shrinking over time, and probably now tips towards de-optimization as often as not.

As to your PDA code, I did a Palm game a while back - and I ended up doing some inline assembler in drawing functions (and it made noticeable performance changes). Not every platform has progressed beyond comprehensibility.
Re: Meh? (response to post by jmzero) | Reply

Not every platform has progressed beyond comprehensibility.


lol.

I remember when I was learning little bits about the x86 architecture, there was a strange instruction that compilers used with great regularity, whose definition was basically "take the word from memory location $a+i*$b and put it into $c" or something like that, where $a, $b and $c were registers and i was an immediate (I'm probably modifying this a little bit). At first, that seemed like a really obscure instruction, until I realized the purpose was that i was the size of an element of an array, $b was the index and $a was the beginning of the array.
Re: Meh? (response to post by Kawigi) | Reply
Don't you think >>5 and &((1<<5)-1) are much better readable than /32 and %32 in case your manipulating bits?
Re: Meh? (response to post by dskloet) | Reply
But the operations with 32 weren't actually directly the manipulation of bits, they were used to decide which bits to manipulate in which integers (try writing the code yourself and that might be clearer). Using & and << is definitely more sensible than / and % if you're doing those operations on the bitmasks themselves.
Re: Meh? (response to post by Kawigi) | Reply
A compiler should be pretty smart to replace x % 32 by x & 31 because it needs to infer that x is always nonnegative. Incidentally, the latter corresponds to the mathematical operation while the first one doesn't.
Re: Meh? (response to post by rgrig) | Reply
That's the case but only if x is unsigned.
Re: Meh? (response to post by jmzero) | Reply
There are a couple of points in favor of an in-place, rather than a counting scheme. First of all, with many languages using unicode strings by default, the larger alphabet can be a very real problem. Second, the counting method allocates extra memory and will push more memory out of the cache because of that.
Re: Meh? (response to post by rgrig) | Reply
TAG,
I seriously doubt that he will be given any negative length strings. Also his solution only touches the very first char if the length of the string is zero. Last time I checked c style strings with a length of zero certainly are represented by a single character.

rgrig,
http://en.wikipedia.org/wiki/Doxygen
Re: Meh? (response to post by tster123) | Reply
tster123 You have read one part of my message - but not another. If string is null-terminated - what's the point of length argument here ? Can you clarify ?

Regarding negative length's - just take a look on bug that things like this can cause in REAL code
http://blogs.msdn.com/michael_howard/archive/2006/10/30/something-else-to-look-out-for-when-reviewing-code.aspx
Re: Meh? (response to post by TAG) | Reply
Additionally, there's a new kind of exploit that has been gaining ground lately involving integer overflow. Watching for such things in code when data came from outside the application (like from the user or from a file) is a good idea.
Re: Meh? (response to post by tster123) | Reply
Was that Doxygen link meant to be funny? Of course I know about Doxygen and of course that's not what I meant. Just take a look at the things I've already listed.
Re: Meh? (response to post by rgrig) | Reply
"PS: In fact, I would prefer to use a smarter language that allows me to write at least the method contract comment in a way understood by tools. (for example Spec#, Java+JML, Eiffel)"

I don't see how Doxygen doesn't meet this requirement. I also have to argue that writing method contracts in a specific way really has no realation to how "smart" the language is. Just the tools you are using.
Re: Meh? (response to post by tster123) | Reply
Spec#, JML, and Eiffel are all languages that allow one to express method contracts. They have semantics that make it possible to write tools that check the contract at runtime or that do static verification using a theorem prover to ensure the contract is obeyed for all possible executions. Doxygen pretty prints.

edit: I renew my plea to take a look at them if you want to understand what I am talking about.
Re: Meh? (response to post by rgrig) | Reply
I thought you were just talking about tools that format method contracts. Sorry about that. It would be nice to always work with languages like that; but alas, such is not the way of the industry.
Re: Foiled by a Div2-250! (response to post by d000hg) | Reply
How about this Java solution:
public String Func(String str)
{
	String out="";
	for (char c='a'; c<='z'; c++)
		if (str.indexOf(""+c)>=0) out+=c;
	return out;
}
Re: Foiled by a Div2-250! (response to post by dimkadimon) | Reply
Why if you do indexOf(String) then indexOf(char) is also available ?
Why using String for "out" if StringBuffer is a must here ?

Please never code like this ;-)
Re: Foiled by a Div2-250! (response to post by TAG) | Reply
Java doesn't have indexOf(char) ;).

But for some reason it has indexOf(int ch) instead.
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
But whenever I use indexOf(int) I pass in a char ;-)
Re: Foiled by a Div2-250! (response to post by TAG) | Reply
TAG,
you're kind of an ass. the Java code works and in fact so does using String instead of String buffer. BTW, incase you were implying that I don't write "REAL" code I do in fact have a job programming computers.
Re: Foiled by a Div2-250! (response to post by TAG) | Reply
Why be so negative? I was just showing an alternative approach to the problem, not trying to write perfectly structured code.

I didn't test this so I did indexOf(String) just to be certain.

I use "out" to construct and return the answer. If I was modifying the original String then I would use StringBuffer.
Re: Foiled by a Div2-250! (response to post by dimkadimon) | Reply
I think his point about using StringBuffer was because doing lots of String concatenations can be very slow and also creates more memory that needs to be garbage collected since you create a new string each time and throw away the old one. Using StringBuffer's append is faster and (if I remember correctly) it acts more like ArrayList in that it just doubles the size of the buffer whenever it runs out of space so it doesn't need to allocate and throw away memory as often.

He doesn't need to be so rude about it ;), but he's correct that using StringBuffer would probably be a better idea for something like that.
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
OK, now I see. Thanks for the explanation. I thought StringBuffer was like Vector - hell slow. I guess I was wrong.
Re: Foiled by a Div2-250! (response to post by dimkadimon) | Reply
just FYI:

I ran some speed tests on that algorithm.
2.8 seconds using String and String.indexOf(string);
1.7 seconds using String and String.indexOf(char);
.8 seconds using StringBuffer and String.indexOf(char);

although if you really were worried about effeciency you would use the original solution posted before this one. This one looks through the string for every letter of the alphabet. Better to look through the whole string and grab each letter as you pass it.
Re: Foiled by a Div2-250! (response to post by slex) | Reply
I ran each algorithm like 20 times, threw away outliers and took the average. I also created only 2 objects the whole time. Could it be that the numbers were a fluke every time? yes. But it is EXTREMELY unlikely. With such simple code and such constant times (the time rarely deviated more than .1 seconds) I am going to make the statement that Stringbuffer and indexOf(char) are faster. However, like I said, it doesn't really matter because if you wanted a fast algorithm you wouldn't be using that one.
Re: Foiled by a Div2-250! (response to post by tster123) | Reply
I wasn't saying your results are wrong. By the common sense using StringBuilder/Buffer should be defenietly faster than creating new String objects in each step. It was just a mandatory remark that one needs to be careful before drawing conclusions from VM language benchmarking.
Re: Foiled by a Div2-250! (response to post by slex) | Reply
I knew as soon as I saw those links that they were to posts by Pops :). Probably got something to do with the fact that in two of them he was replying to me ;).
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
He can be taught! :)
Re: Foiled by a Div2-250! (response to post by aussie) | Reply
I thought when I read the benchmarks that I should reply with my best Pops voice, but I decided not to bother. Of course, like you, I recognized slex's best Pops impersonation and considered replying to it with something like "who died and made you Pops?" (also without actually clicking on the links).
Re: Foiled by a Div2-250! (response to post by Kawigi) | Reply
First here you admitted that you had stopped yourself from posting, and now you are saying you've done it again twice?
Are you on some 12 steps program for posters?
Re: Foiled by a Div2-250! (response to post by dimkadimon) | Reply
If you want it to be faster (and don't need thread safety) you can try StringBuilder.
Re: Foiled by a Div2-250! (response to post by d000hg) | Reply
I'll steal my thread back to ask:
a)
If they hand me a pad of paper and say "I want a function to do...", and there is a spare PC handy, is it rude to ask to use that instead? I hate writing code on paper and it distracts me from the problem I'm trying to solve?

b)
If you are asked "write a function to..." would you assume they want error checking on pointers and so on, or just are looking for the algorithm? You can ask of course - "do you want to see me solve it or do you want to see me write production-level code" - but at my last interiew they were into letting me decide what I wanted to write!
Re: Foiled by a Div2-250! (response to post by d000hg) | Reply
If I was the interviewer...

a) Write it on paper. I know it's more difficult, you need to do it without keeping changing and recompiling the code and I would like to see if you can.

b) The working algorithm would be enough, if you want to add some validations it's fine too.
Re: Foiled by a Div2-250! (response to post by slex) | Reply
I'd say do at least basic validation (i.e. null checks). If you don't, they might just ask you to do it later, but might as well get it out of the way :-)

From my experience, being able to answer questions like "what is the runtime complexity" and "what is the space complexity" are also important :-)
Re: Foiled by a Div2-250! (response to post by d000hg) | Reply
I would implement exactly what I am asked first, without any validation. I would spell out the preconditions in comments. Then I would explain in what situations I would also write validation code and then I would also write the validation code. If they don't want the validation code they will stop you. What is important is to communicate what is your plan and what are you are doing while you are writing code. When you finish writing the code you should have a pretty good idea on what input it works.

In industry you would write validation code almost for each method. In the unlikely case that you have tools that check automatically that private methods are always called with valid data (which could be done for simple things such as nullness) then you can skip the ugly validation code.

Why do I say it's ugly? See these two pieces of code.

private Rational div(Rational a, Rational b) {
  if (a == null) throw BlaBlaException("error in Rational.div: null a");
  if (b == null) throw BlaBlaException("error in Rational.div: null b");
  if (b.getDenominator() == 0)
    throw BlaBlaException("error in Rational.div: division by zero");
  return new Rational(
    a.getNumerator() * b.getDenominator(),
    a.getDenominator() * b.getNumerator()
  );
}
And this.

/*@ requires b.getDenominator() != 0; */
private /*@non_null*/ Rational div(/*@non_null*/ Rational a, /*@non_null*/ Rational b) {
  return new Rational(
    a.getNumerator() * b.getDenominator(),
    a.getDenominator() * b.getNumerator()
  );
}
For the second one there are compilers that generate the equivalent of the IFs in the first one. There are also static tools that check whether the contract is always satisfied. It's shorter, though not as short as it could be if backwards compatibility would not be an issue. For example, in Spec# it looks like this.
private Rational! div(Rational! a, Rational! b) 
requires b.getDenominator() != 0;
{
  return new Rational(
    a.getNumerator() * b.getDenominator(),
    a.getDenominator() * b.getNumerator()
  );
}

The big problem is that the tools I'm talking about, especially the ones that do static verification, are far from being good enough for normal use. But we'll get there :)

edit: the method should be static to make sense and I didn't pay too much attention to correctness (i don't have a coeherent way of treating a 0 denominator). The point was only to illustrate what can be done if the language supports contracts. [oh, and the first time i mixed denominators/numerators -- I always forget which is which in English. I had to fix that].
RSS