Short C++ Program Answers

by Curtis Krauskopf

Two factors are important with the "Showing Skills" type questions. The first is to create a working program that solves the problem. The second factor is to do the work within the time you've allotted yourself.

Giving an accurate time estimate is a skill that I've had to learn to develop. I practice it daily by challenging myself even on routine matters, such as how long will it take me to debug a problem, or how long will it take me to design a module?

Asking how long a task will take is a reasonable question for an employer or customer because they want to know when a solution will be available and how much the solution will cost.

For yourself, it's part of time management and being able to deliver projects on-time and on-budget.

The solutions for the six "Showing Skills" problems are shown in listings F through K. I've provided the time I took to create the solution. The purpose is to give you a benchmark with which to gauge your productivity. For example, if you estimate 30 minutes for a problem and you're still working on it two hours later, that should tell you something constructive about your organization, coding skills, and debugging skills.

I used all available references for my solutions. When I interview people, I allow them to use references because employers never take away your programming books when they assign you a project. When given a programming assignment, you should feel free to ask about using reference books or the Internet.

Array destruction

An array that is instantiated with the new[] operator should also be deleted using the delete[] operator. Write a program that proves that the destructors for an array are not called when the array was instantiated with new [] and the array was deleted with delete (without the delete[] syntax).

My first version of the array destruction test in Listing F did not use the VCL (a Borland C++ compiler feature) and an access violation was thrown at runtime. I tried to wrap the delete with a try/catch, but the exception still wasn't caught. The debugger told me that an EAccessViolation exception was being thrown and the C++ Builder Help told me that it was defined in the VCL. So I converted the program to use the VCL and tried it again. The VCL version does not cause an access violation at runtime, so I removed the try/catch block in the code.

// An array that is instantiated with the new[] operator 
// should also be deleted using the delete[] operator.  
// Write a program that proves that the destructors for 
// an array are not called when the array was instantiated 
// with new [] and the array was deleted with delete 
// (without the delete[] syntax).

// This program took 15 minutes to write and debug.

#include <vcl.h>
#include <iostream>

using namespace std;   // okay for small programs

int g_LiveInstances = 0;

struct Trivial {
  Trivial() {
    cout << "Creating object #" << ++g_LiveInstances << endl;
  }
  virtual ~Trivial() {
    cout << "Deleting an object" << endl;
    --g_LiveInstances;
  }
};

int main(int, char**) {
  Trivial *p = new Trivial[5];
  delete p;

  // This should show:
  //    Number of Trivial instantiations remaining: 4
  cout << "Number of Trivial instantiations remaining: ";
  cout << g_LiveInstances << endl;
  return 0;
}

Caseless string comparison

Write a String class that compares its strings by ignoring the case of the characters.

I had two choices when writing the caseless string comparison solution in Listing G. I could either create my own string class that stores a string using a has-a relationship or I could override the compare method in the std::char_traits class. The former would require me to write helper functions for all of the public and protected constructors and methods. I chose the latter solution because its code should be limited to a specialized std::char_traits class.

Notice that I didn't have to write any specialized comparison methods (operator==, operator<, operator>, and others). I used the template supplied by the STL, which calls _Traits::compare(). The static compare() method in CaselessTrait was created by debug-tracing a normal std::string comparison into the char_traits.h file. I copy-pasted the definition of compare() from char_traits into the solution and changed the comparison function from memcpy to strnicmp.

// Code and debug time:  35 minutes.

#include <iostream>
#include <string>


template <class _CharT>
class CaselessTrait : public std::char_traits<_CharT>
{
public:
  static int _STLP_CALL compare(const char* __s1, 
                                const char* __s2, 
                                size_t __n)
    { return strnicmp(__s1, __s2, __n); }

};


// Not asked for by the problem but I threw it in anyway
std::ostream
&operator<<(std::ostream &os,
            const std::basic_string<char, CaselessTrait<char>, 
            std::allocator<char> > &obj
           )
{
  os << obj.c_str();
  return os;
}


int main(int, char**) {
  typedef std::basic_string<char, CaselessTrait<char> > CaselessString;
  CaselessString test1 = "Hello World";
  CaselessString test2 = "hello world";

  std::cout << test1 << std::endl;
  std::cout << test2 << std::endl;

  if (test1 == test2) {
    std::cout << "Strings are equal" << std::endl;
  }
  else {
    std::cout << "String are not equal" << std::endl;
  }
  return 0;
}

Time difference

A comma-delimited file has two columns: timeA and timeB. Both columns are times in the following format: hh:mm [a|p]m

where:
    hh is from 1 to 12.
    mm is from 1 to 60.
    [a|p] is either an 'a' or 'p'.

Example file:
5:57 pm,10:37 am

Write a program that reads the comma-delimited text file. For each line in the text file, report the time that is earlier. Assume all times are in the same time zone and that all times are for the same day.

The time comparison solution in Listing H primarily converts both times into the number of minutes past midnight and then simply compares those two values. I added some code that reports errors, such as when the file can't be opened or when the data format is grossly wrong.

The parsing algorithm in decodeTime() assumes the data is in the right format. The problem doesn't require anything more than this but in a real interview I would ask if the program should check for incorrectly formatted data or invalid data, such as 11:88am. My am/pm detection only checks for "pm" and assumes all other values, including "PM", are "am". I could have easily used stricmp instead of operator==(), but at that point in the parser I was assuming that the data would be correctly formatted. These are the kinds of tradeoffs one makes when keeping the solution simple and staying within the deadline.

// Code and debug time:  45 minutes

#include <fstream>
#include <iostream>

// okay for small programs
using namespace std;

// Time converted to the number of minutes past midnight
typedef unsigned int Time;


// Given a data value of the form:
//   hh:mm [a|p]m
// convert the string to the number of
// minutes past midnight.
Time decodeTime(const string text) {
  string::size_type colonPos = text.find(':');
  string::size_type blankPos = text.find(' ');

  int hours = atoi(text.substr(0, colonPos).c_str());
  int mins  = atoi(text.substr(colonPos+1, blankPos-colonPos).c_str());
  string amPm = text.substr(blankPos+1);

  // "midnight" and "noon" are special because we want
  // the number of minutes past midnight... so switch a 12 into
  // a 0 to accomodate the calculation.
  if (hours == 12) hours = 0;

  Time minsPastMidnight = mins;

  if (amPm == "pm")
    minsPastMidnight += (12 + hours) * 60;
  else
    minsPastMidnight += hours * 60;

  return minsPastMidnight;
}


int main(int argc, char* argv[]) {
  ifstream csv("data.csv", ios::in);
  if (!csv) {
    cout << "Can not open data.csv\n";
    return 1;
  }

  string line;   // line from CSV file
  while (getline(csv, line, '\n')) {
    // find the ',' separator
    string::size_type commaPos = line.find(',');
    if (commaPos == string::npos) {
      cout << "Invalid CSV line: " << line << endl;
    }
    else {
      Time firstTime = decodeTime(line.substr(0, commaPos));
      Time secondTime = decodeTime(line.substr(commaPos+1));
      if (firstTime < secondTime)
        cout << line.substr(0, commaPos) << endl;
      else
        cout << line.substr(commaPos+1) << endl;
    }
  }
  return 0;
}

Recursive sort

Sort a linked list using recursion.

The recursive sort algorithm in Listing I took a lot longer than I would have expected. My implementation assumes that only the head pointer is available. A flag, sortAgain, is initialized to false and is used to tell Sort() if any of the nodes in the list were swapped. If RecursiveSort() returns with sortAgain still false, the list has been sorted. Otherwise, sortAgain is reset to false and the list is resorted.

To keep the algorithm simple, I didn't make any attempt to keep track of the sorted and unsorted parts of the list. The entire list is sorted every time RecursiveSort is called.

Recursive sort solutions that swap the key values or swap the struct's payload values should be considered failures. Shuffling the data inside of the list defeats the purpose of using a linked list. The main reason for using a linked list is because the data is supposedly large or difficult to copy. If that were not the case, then an array would have been used. List nodes are being used to point to the data. The head pointer and the next pointers are the only parts of the list that need to be modified to sort it.

Don't forget to test your final solution for an empty list and for a list with only one item in it. The first version of my algorithm would have thrown an access violation for an empty list.

// Code and debug time: 1 hour, ten minutes.

#include <stdlib.h>   // for rand()
#include <algorithm>
#include <function>
#include <iostream>

struct List {
  List(int val) : key(val), next(NULL)
  {}
  int key;
  List *next;
};


// Called by Sort(List *) to recursively sort the
// linked list.
//
List * RecursiveSort(List *current, List *prev, bool &sortAgain) {
  List *head = current;

  if (current == NULL || current->next == NULL)
    return current;    // nothing to sort

  if (current->key > current->next->key) {
    if (prev == NULL) {
      head = current->next;
      current->next = head->next;
      head->next = current;
      current = head;
      sortAgain = true;
    }
    else {
      // The unsorted order of the nodes is:
      //    prev, current, node, after
      // The sorted order of the nodes is:
      //    prev, node, current, after
      List *node = current->next;
      List *after = node->next;

      head = current->next;
      prev->next = node;
      current->next = after;
      node->next = current;

      sortAgain = true;
    }
  }

  if (current->next != NULL) {
    RecursiveSort(current->next, current, sortAgain);
  }

  return head;
}



// Sort the single-linked list.
List * Sort(List *head) {
  // Keep sorting the list until the entire
  // list is sorted.
  bool sortAgain = false;
  do {
    sortAgain = false;
    head = RecursiveSort(head, NULL, sortAgain);
  } while (sortAgain == true);
  return head;
}


// Print the keys of the list separated by commas.
void Print(const List *head) {
  const List *node = head;
  std::cout << "List: ";
  while (node != NULL) {
    std::cout << node->key << ",";
    node = node->next;
  }
  std::cout << "\n";
}



int main(int, char**)
{
  // Create an unsorted array that will
  // be transformed into an unsorted linked
  // list.
  int a[10];
  const int numElements = sizeof(a) / sizeof(int);
  for(int i = 0; i < numElements; ++i)
    a[i] = i * (i % 2 ? -1 : 1);
  randomize();
  std::random_shuffle(&a[0], &a[numElements]);

  // Transfer the unsorted array into a list...
  List *head = NULL;
  List *tail = NULL;
  for(int i = 0; i < numElements; ++i) {
    List *node = new List(a[i]);
    if (head == NULL) {
      head = node;
      tail = node;
    }
    else {
      tail->next = node;
      tail = node;
    }
  }

  std::cout << "Before sort:\n";
  Print(head);

  head = Sort(head);

  std::cout << "\nAfter sort:\n";
  Print(head);

  return 0;
}

Iterative list sorting

Sort a linked list without using recursion.

Listing J shows my solution for nonrecursively sorting the single-linked list. I cheated a little bit and used the recursive sort solution from listing I as a starting point. It's not really cheating, though, because I'm allowed to use whatever resources are available.

In the process of looking at the swap algorithm a second time, I noticed it could be improved a little. I think the version in listing J is a little clearer because only the work that's needed for the boundary condition (the very first element in the list) is inside of the if statement.

// Code and debug time: 15 minutes (using the RecursiveSort.cpp 
// as a starting point)

#include <stdlib.h>   // for rand()
#include <algorithm>
#include <function>
#include <iostream>

struct List {
  List(int val) : key(val), next(NULL)
  {}
  int key;
  List *next;
};


// Sort the single-linked list.
List * Sort(List *head) {
  if (head == NULL || head->next == NULL)
    return head;    // nothing to sort

  List *prev = NULL;
  List *current = NULL;

  bool sortAgain = false;
  do {
    sortAgain = false;
    current = head;
    prev = NULL;
    while (current != NULL && current->next != NULL) {
      if (current->key > current->next->key) {
        sortAgain = true;

        // The unsorted order of the nodes is:
        //    prev, current, node, after
        // The sorted order of the nodes is:
        //    prev, node, current, after
        List *node = current->next;
        List *after = node->next;

        if (prev == NULL) {
          head = current->next;
        }
        else {
          prev->next = node;
        }
        current->next = after;
        node->next = current;
      }
      prev = current;
      current = current->next;
    }
  } while (sortAgain == true);

  return head;
}



// Print the keys of the list separated by commas.
void Print(const List *head) {
  const List *node = head;
  std::cout << "List: ";
  while (node != NULL) {
    std::cout << node->key << ",";
    node = node->next;
  }
  std::cout << "\n";
}



int main(int, char**)
{
  // Create an unsorted array that will
  // be transformed into an unsorted linked
  // list.
  int a[10];
  const int numElements = sizeof(a) / sizeof(int);
  for(int i = 0; i < numElements; ++i)
    a[i] = i * (i % 2 ? -1 : 1);
  randomize();
  std::random_shuffle(&a[0], &a[numElements]);

  // Transfer the unsorted array into a list...
  List *head = NULL;
  List *tail = NULL;
  for(int i = 0; i < numElements; ++i) {
    List *node = new List(a[i]);
    if (head == NULL) {
      head = node;
      tail = node;
    }
    else {
      tail->next = node;
      tail = node;
    }
  }

  std::cout << "Before sort:\n";
  Print(head);

  head = Sort(head);

  std::cout << "\nAfter sort:\n";
  Print(head);

  return 0;
}

Reversing a single linked list

Reverse a single-linked list without using recursion.

My solution for reversing the single-linked list, in Listing K, was based on the code in Listing J. The solution does not overwrite the next pointer for the head node until the entire list has been sorted. I thought this would be easier than checking, on each loop iteration, if the head node was being modified.

As with the sorting solutions, any solutions that involve moving the data values instead of changing the head and next pointers is a failure.

If I were to provide the linked list problems as an interviewer, I would provide everything in the solution except for the sorting or reversing method and everything in the main() function up to the first Print method.

// Code and debug time: 20 minutes (using the 
// IterativeSort.cpp as a starting point)

#include <iostream>

struct List {
  List(int val) : key(val), next(NULL)
  {}
  int key;
  List *next;
};



// Print the keys of the list separated by commas.
void Print(const List *head) {
  const List *node = head;
  std::cout << "List: ";
  while (node != NULL) {
    std::cout << node->key << ",";
    node = node->next;
  }
  std::cout << "\n";
}


List * ReverseList(List *head) {
  if (head == NULL || head->next == NULL)
    return head;    // Nothing to reverse;

  // Reverse the list except for the
  // head node.
  List *prev = head;
  List *current = prev->next;
  while (current != NULL) {
      List *after = current->next;
      current->next = prev;    // reverse the list
      prev = current;
      current = after;
  }

  // In the reversed list, the head element becomes
  // the last element, so terminate the list at
  // the head element
  head->next = NULL;
  return prev;
}


int main(int, char**)
{
  const int numElements = 10;

  // Create a list from 0..9:
  List *head = NULL;
  List *tail = NULL;
  for(int i = 0; i < numElements; ++i) {
    List *node = new List(i);
    if (head == NULL) {
      head = node;
    }
    else {
      tail->next = node;
    }
    tail = node;
  }

  std::cout << "Before Reverse:\n";
  Print(head);

  head = ReverseList(head);

  std::cout << "\nAfter Reverse:\n";
  Print(head);

  return 0;
}

Previous Answers

More C++ Answers