JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 3 4 5 ]    NEXT >
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 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 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 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 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 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
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 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.
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
[ 1 2 3 4 5 ]    NEXT >

RSS