Difference between revisions of "POTW 20091022"

From CSLabsWiki
(Way to go Sam!)
(Added solutions)
Line 41: Line 41:
   
 
<code><pre>Q: Question</pre></code>
 
<code><pre>Q: Question</pre></code>
  +
  +
== Submissions ==
  +
=== Sam Payson ===
  +
*Submitted: 10/23/09 0316
  +
*Works: Yes
  +
*Compile with: gcc -Wall problem.c -o reverse
  +
*Writeup: This program uses 4 bytes of memory (on a system with 32-bit pointers) in
  +
addition to the memory used by the string itself.
  +
*Code:
  +
<code lang="c"><pre>
  +
#include <stdio.h>
  +
  +
void reverse(char * string)
  +
{
  +
char * p = string;
  +
while (*p != 0x0)
  +
++p;
  +
--p;
  +
while (p != string && p > string)
  +
{
  +
*string ^= *p;
  +
*p ^= *string;
  +
*string ^= *p;
  +
--p;
  +
++string;
  +
}
  +
}
  +
  +
int main(int argc, char * argv[])
  +
{
  +
if (argc != 2)
  +
{
  +
printf("usage: reverse [string]\n");
  +
return 1;
  +
}
  +
reverse(argv[1]);
  +
printf("%s\n", argv[1]);
  +
return 0;
  +
}
  +
</pre></code>
  +
  +
=== Tim Kopp ===
  +
*Submitted: 10/23/09 0316
  +
*Works: Yes
  +
*Compile with: gcc -Wall problem.c -o reverse
  +
*Writeup: This program uses 4 bytes of memory (on a system with 32-bit pointers) in
  +
addition to the memory used by the string itself.
  +
*Code:
  +
<code lang="c++"><pre>
  +
/*
  +
* Filename: potw20091022.cpp
  +
* Author: Tim Kopp
  +
* Description: Reverse a c-string, memory use trumps runtime.
  +
* Last Modified: 10/29/2009
  +
*/
  +
  +
#include <iostream>
  +
#include <cstring>
  +
using namespace std;
  +
  +
void reverse(char * string);
  +
  +
int main()
  +
{
  +
const char* tmp = "Hello COSI!";
  +
char* string = new char[11];
  +
strcpy(string,tmp);
  +
  +
  +
cout << "String: " << string << endl;
  +
reverse(string);
  +
cout << "Reversed: " << string << endl;
  +
return 0;
  +
}
  +
  +
void reverse(char * string)
  +
{
  +
char * pf;
  +
pf = string;
  +
char * pb;
  +
pb = string;
  +
char tmp;
  +
int count=-1;
  +
  +
while(*pf != '\0')
  +
{
  +
pf++;
  +
count++;
  +
}
  +
pf--;
  +
  +
for(int i=0; i < count/2+1; ++i)
  +
{
  +
tmp = *pb;
  +
*pb=*pf;
  +
*pf=tmp;
  +
pf--;
  +
pb++;
  +
}
  +
return;
  +
}
  +
</pre></code>

Revision as of 18:19, 29 October 2009

Problem Statement

In place c-string reversal
Question posed by: Jacob Torrey
Source: AIS Interview Question
Date Posed: 2009-10-22
First Answered By: Sam Payson


It is your first day of work at Acme Corp, the world-renowned widget company. You have been hired as a software developer in their widgetOS department. Your first task is to implement a function to reverse a C-string in place, however, widgetOS is known for being about as frugal with memory as a good Vermonter is with maple syrup. Below is the skeleton of your function:

void reverse(char * string);

The input string will be a C-string (meaning it is an array characters ending with a '\0' character) and will contain only alphabetic, numeric, and whitespace characters ([a-z][A-Z][0-9]\s\t\r\n).

You must use as little memory as possible (run-time is your secondary concern) and keep in mind of memory usage of any other functions that you call.

Submission and Grading

There will be two winners: the first person to submit a correct answer, and the "best" answer as determined by the problem poser.

You should submit the function, a main function showing it working, a makefile or the compiler arguments to compile your code, and a short write-up describing the memory usage of your function. You should use C or C++. Please submit your solution by emailing it to the problem poser.

Requests for Clarification

Please make all requests for clarification here in the form of:

Q: Question

Submissions

Sam Payson

  • Submitted: 10/23/09 0316
  • Works: Yes
  • Compile with: gcc -Wall problem.c -o reverse
  • Writeup: This program uses 4 bytes of memory (on a system with 32-bit pointers) in

addition to the memory used by the string itself.

  • Code:
#include <stdio.h>

void reverse(char * string)
{
	char * p = string;
	while (*p != 0x0)
		++p;
	--p;
	while (p != string && p > string)
	{
		*string ^= *p;
		*p ^= *string;
		*string ^= *p;
		--p;
		++string;
	}
}

int main(int argc, char * argv[])
{
	if (argc != 2)
	{
		printf("usage: reverse [string]\n");
		return 1;
	}
	reverse(argv[1]);
	printf("%s\n", argv[1]);
	return 0;
}

Tim Kopp

  • Submitted: 10/23/09 0316
  • Works: Yes
  • Compile with: gcc -Wall problem.c -o reverse
  • Writeup: This program uses 4 bytes of memory (on a system with 32-bit pointers) in

addition to the memory used by the string itself.

  • Code:
/*
 * Filename: potw20091022.cpp
 * Author: Tim Kopp
 * Description: Reverse a c-string, memory use trumps runtime.
 * Last Modified: 10/29/2009
 */

#include <iostream>
#include <cstring>
using namespace std;

void reverse(char * string);

int main()
{
  const char* tmp = "Hello COSI!";
  char* string = new char[11];
  strcpy(string,tmp);


  cout << "String: " << string << endl;
  reverse(string);
  cout << "Reversed: " << string << endl;
  return 0;
}

void reverse(char * string)
{
  char * pf;
  pf = string;
  char * pb;
  pb = string;
  char tmp;
  int count=-1;

  while(*pf != '\0')
    {
      pf++;
      count++;
    }
  pf--;

  for(int i=0; i < count/2+1; ++i)
    {
      tmp = *pb;
      *pb=*pf;
      *pf=tmp;
      pf--;
      pb++;
    }
  return;
}