POTW 20091022

From CSLabsWiki
Revision as of 17:51, 29 October 2009 by Torreyji (talk | contribs) (Fixed Tim's submission)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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


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)
	while (p != string && p > string)
		*string ^= *p;
		*p ^= *string;
		*string ^= *p;

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

Tim Kopp

  • Submitted: 10/29/09 1237
  • Works: Yes
  • Compile with: g++ -o potw potw20091028.cpp
  • Writeup:
My algorithm uses memory for:

2 character pointers
2 integers
1 character

My gut tells me there's a way to use less, but I couldn't think of one.
  • 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];

  cout << "String: " << string << endl;
  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')

  for(int i=0; i < count/2+1; ++i)
      tmp = *pb;