Difference between revisions of "POTW 20091022"

From CSLabsWiki
Jump to: navigation, search
(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 17: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;
}