Template class to demonstrate array manipulation

Question

Today I didn't pass the test task for the position C++ junior/middle developer. What i did wrong? Please help improve myself.

---

Task:

Description.

Write a template class - an array of any type of data, and tests to demonstrate the work with this class. Should be implemented all the methods also acceptable to extend the functionality.

Tests:

The solution should show a class with the following tests:

Working with numbers (int):

1.in loop insert 20 random numbers ranging from 0 to 100.

2.sorting the resulting set of numbers in ascending order.

3.remove each second element.

4.insert 10 random numbers ranging from 0 to 100 at random positions.

5.cleaning container.

After each stage you need to display the contents of the array onto the screen.

Working with objects (std: string):

1.in loop insert 15 randomly chosen words consisting of letters in lowercase.

2.sorting a set of words in ascending order.

3.removing each word comprising any of the letters a, b, c, d, e.

4.inserting 3 new randomly selected words on a random position.

After each stage you need to display the contents of the array onto the screen.

Class interface:

template <typename TData>
class CArray
{

public:

    CArray();

    CArray( const CArray & _array );

    ~CArray();

    void push_back( const TData & _value );

    void insert( unsigned int _index, const TData & _value );

    void erase( unsigned int _index );

    void clear();

    unsigned int size() const;

    TData & operator[](unsigned int _index );
};

Implementation:

#ifndef CARRAY_HPP__
# define CARRAY_HPP__

#include <stdexcept>
#include <iterator>
#include <ostream>
#include <cstdlib>
#include <ctime>


namespace test
{
namespace util
{

///**********************
class RandGenerator
{
public:
  RandGenerator(
      unsigned int _upperbound = RAND_MAX
    )
    : _mUpperbound(_upperbound)
  {
    std::srand( static_cast<unsigned int>(std::time(0)) );
  }

  int operator()()
  {
    return std::rand() % _mUpperbound;
  }

  int operator()(
      unsigned int _upperbound
    )
  {
    return std::rand() % _upperbound;
  }

  void set_seed(
      unsigned int _seed
    )
  {
    std::srand( _seed );
  }

  void set_upperbound(
      unsigned int _upperbound
    )
  {
    _mUpperbound = _upperbound;
  }

private:
  unsigned int _mUpperbound;

};



///**********************
template <typename TClass>
class _CArrayIter : 
    public std::iterator<std::random_access_iterator_tag, TClass>
{
  friend class CArray;

public:
  explicit _CArrayIter(
      TClass * _ptype
    ) : _mTptr( _ptype )
  {}

  const TClass & operator*() const
  {
    return *_mTptr;
  }

  TClass & operator*()
  {
    return *_mTptr;
  }

  const TClass * operator->() const
  {
    return _mTptr;
  }

  TClass * operator->()
  {
    return _mTptr;
  }

  _CArrayIter& operator++()
  {
    ++_mTptr;
    return *this;
  }

  _CArrayIter operator++( int )
  {
    return _CArrayIter( _mTptr++ );
  }

  _CArrayIter& operator--()
  {
    --_mTptr;
    return *this;
  }

  _CArrayIter operator--( int )
  {
    return _CArrayIter( _mTptr-- );
  }

  const _CArrayIter& operator[](
      std::size_t _idx
    ) const
  {
    return _mTptr[ _idx ];
  }

  _CArrayIter& operator[](
      std::size_t _idx
    )
  {
    return _mTptr[ _idx ];
  }

  _CArrayIter& operator+=(
      std::size_t _val
    )
  {
    _mTptr += _val; return *this;
  }

  _CArrayIter& operator-=(
      std::size_t _val
    )
  {
    _mTptr -= _val; return *this;
  }

  _CArrayIter operator+(
      std::size_t _val
    )
  {
    return _CArrayIter( _mTptr + _val );
  }

  _CArrayIter operator-(
      std::size_t _val
    )
  {
    return _CArrayIter( _mTptr - _val );
  }

  friend bool operator==(
      const _CArrayIter & _lhs, 
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr == _rhs._mTptr;
  }

  friend bool operator!=(
      const _CArrayIter & _lhs,
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr != _rhs._mTptr;
  }

  friend bool operator>(
      const _CArrayIter & _lhs, 
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr > _rhs._mTptr;
  }

  friend bool operator<(
      const _CArrayIter & _lhs, 
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr < _rhs._mTptr;
  }

  friend bool operator>=(
      const _CArrayIter & _lhs, 
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr >= _rhs._mTptr;
  }

  friend bool operator<=(
      const _CArrayIter & _lhs, 
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr <= _rhs._mTptr;
  }

  friend _CArrayIter operator+(
      std::size_t _st, 
      const _CArrayIter & _iter
    )
  {
    return _CArrayIter( _iter._mTptr + _st );
  }

  friend std::size_t operator-(
      const _CArrayIter & _lhs, 
      const _CArrayIter & _rhs
    )
  {
    return _lhs._mTptr - _rhs._mTptr;
  }

private:
  TClass *_mTptr;
};

}

///**********************
template <typename TData>
class CArray
{
  static const unsigned int CARRAY_DEFAULT_CAPACITY = 512;

public:
  typedef test::util::_CArrayIter<TData>        iterator;
  typedef test::util::_CArrayIter<const TData>  const_iterator;

  CArray(
      unsigned int _capacity = CARRAY_DEFAULT_CAPACITY
    ): _mArray(static_cast<TData*>(::operator new[](_capacity * sizeof(TData)))),
       _mCurPos(0), _mEnd(_capacity)
  {}

  CArray(
      const CArray & _array
    ): _mArray(static_cast<TData*>(::operator new[](_array._mEnd * sizeof(TData)))),
       _mCurPos(_array._mCurPos), _mEnd(_array._mEnd)
  {
    _copy_n_init_from( _array._mArray, _array._mCurPos );
  }

  ~CArray()
  {
    _destruct_objects();
    ::operator delete[]( _mArray );
  }

  void init_reserve(
      unsigned int _count
    )
  {
    if( _count + _mCurPos >= _mEnd )
    {
      _mEnd = _mCurPos + _count;
      _realloc_mem_copy();
    }
    for( unsigned int end = _mCurPos + _count; _mCurPos < end; ++_mCurPos )
      ::new(_mArray + _mCurPos) TData();
  }

  void push_back(
      const TData & _value
    )
  {
    if( _mCurPos == _mEnd )
      _realloc_mem_copy();
    ::new(_mArray + _mCurPos) TData( _value );
    _mCurPos++;
  }

  void insert(
      unsigned int _index,
      const TData & _value
    )
  {
    if( _index > _mCurPos )
      _throw_out_of_range();
    if( _index < _mCurPos )
    {
      _move_mem_insert( _index );
      ::new(_mArray + _index) TData( _value );
      _mCurPos++;
    }
    else
      push_back( _value );
  }

  void erase(
      unsigned int _index
    )
  {
    if( _index >= _mCurPos )
      _throw_out_of_range();
    _move_mem_erase(_index);
    _mCurPos--;
  }

  void clear()
  {
    _destruct_objects();
    _mCurPos = 0;
  }

  unsigned int size() const
  {
    return _mCurPos;
  }

  const TData & at(
      unsigned int _index
    ) const
  {
    if( _index >= _mCurPos )
      _throw_out_of_range();
    return _mArray[ _index ];
  }

  TData & operator[](
      unsigned int _index
    )
  {
    return _mArray[ _index ];
  }

  iterator begin()
  {
    return iterator(_mArray);
  }

  iterator end()
  {
    return iterator(_mArray + _mCurPos);
  }

  const_iterator cbegin() const
  {
    return const_iterator( _mArray );
  }

  const_iterator cend() const
  {
    return const_iterator( _mArray + _mCurPos );
  }

  friend std::ostream& operator<<(
      std::ostream & _outstream,
      const CArray & _obj
    )
  {
    for( unsigned int i = 0; i < _obj._mCurPos; ++i )
      _outstream << _obj._mArray[ i ] << "|";
    return _outstream;
  }

private:
  TData * _mArray;
  unsigned int _mCurPos, _mEnd;

  void _destruct_objects();
  void _realloc_mem_copy();
  void _move_mem_insert( unsigned int );
  void _move_mem_erase( unsigned int );
  void _copy_n_init_from( const TData*, unsigned int, unsigned int = 0, unsigned int = 0 );

  CArray& operator=( const CArray& )
  {}
};

///**********************
template <typename TData>
inline void CArray<TData>::_destruct_objects()
{
  for( unsigned int i = 0; i < _mCurPos; ++i )
    _mArray[ i ].TData::~TData();
}

template <typename TData>
void CArray<TData>::_realloc_mem_copy()
{
  _mEnd *= 2;
  TData * tmp = static_cast<TData*>(::operator new[]( _mEnd * sizeof( TData ) ));
  for( unsigned int i = 0; i < _mCurPos; ++i )
  {
    ::new(tmp + i) TData( _mArray[ i ] );
    _mArray[ i ].TData::~TData();
  }
  ::operator delete[]( _mArray );
  _mArray = tmp;
}

template <typename TData>
inline void CArray<TData>::_move_mem_insert(
    unsigned int _from
  )
{
  ::new(_mArray + _mCurPos) TData( _mArray[_mCurPos - 1] );
  for( unsigned int i = _mCurPos - 1; i > _from; --i )
    _mArray[ i ] = _mArray[ i - 1 ];
}

template <typename TData>
inline void CArray<TData>::_move_mem_erase(
    unsigned int _index
  )
{
  for( unsigned int i = _index; i < _mCurPos - 1; ++i )
    _mArray[ i ] = _mArray[ i + 1 ];
  _mArray[ _mCurPos - 1 ].TData::~TData();
}

template <typename TData>
inline void CArray<TData>::_copy_n_init_from( 
    const TData *_src, 
    unsigned int _length,
    unsigned int _srcPos,
    unsigned int _dstPos
  )
{
  for( unsigned int i = 0; i < _length; ++i )
    ::new(_mArray + _dstPos++) TData( _src[ _srcPos++ ] );
}
}

#endif // !CARRAY_HPP__

And main.cpp:

#include <iostream>
#include <algorithm>
#include <string>
#include "CArray.hpp"

static const unsigned int MAX_WORD_LENGTH = 5; // = total length + min word length
static const unsigned int MIN_WORD_LENGTH = 3;

static inline bool _cmp(
    const std::string & s1,
    const std::string & s2
  )
{
  return s1.size() < s2.size();
}

template <typename Generator>
static std::string _generate_word(
    Generator g
  )
{
  std::string str;
  for( unsigned int j = 0, end = g( MAX_WORD_LENGTH ) + MIN_WORD_LENGTH; j < end; ++j )
      str.push_back( 'a' + g() );
  return str;

}



int main()
{
  test::CArray<int> c(20);
  test::util::RandGenerator gen( 100 );

  c.init_reserve( 20 );
  std::generate( c.begin(), c.end(), gen );
  std::cout << "Test int1:\n" << c << std::endl;

  std::sort( c.begin(), c.end() );
  std::cout << "\nTest int2:\n" << c << std::endl;

  for( unsigned int i = c.size() - 1; i > 0; --i )
    if( (i & 1) != 0 )
      c.erase( i );
  std::cout << "\nTest int3:\n" << c << std::endl;

  for( unsigned int i = 0; i < 10; ++i )
    c.insert( gen( c.size() ), gen() );
  std::cout << "\nTest int4:\n" << c << std::endl;

  c.clear();
  std::cout << "\nTest int5:\n" << c << std::endl;

  std::cout << "Integer testsuite done\n\n";


  test::CArray<std::string> b; 
  const std::string pattern( "abcde" );
  gen.set_upperbound( 26 );

  for( unsigned int i = 0; i < 15; ++i )
    b.push_back( _generate_word(gen) );
  std::cout << "\nTest str1:\n" << b << std::endl;

  std::sort( b.begin(), b.end(), _cmp );
  std::cout << "\nTest str2:\n" << b << std::endl;

  for( unsigned int i = 0; i < b.size(); ++i )
    if( b[ i ].find_first_of( pattern ) != std::string::npos )
      b.erase( i-- );
  std::cout << "\nTest str3:\n" << b << std::endl;

  for( unsigned int i = 0; i < 3; ++i )
    b.insert(gen(b.size()), _generate_word(gen) );
  std::cout << "\nTest str4:\n" << b << std::endl;

  std::cout << "\nString testsuite done\n" << std::endl;

  return 0;
}

Working code and all tests pass.

Answer 1

Failed requirements

The requirements say

1.in loop insert 15 randomly chosen words consisting of letters in lowercase.

But what you actually did was randomly generate letter combinations. To me, a word is something like "word", not "abcd". This suggests to me that you failed this requirement.

3.removing each word comprising any of the letters a, b, c, d, e.

What you did

  for( unsigned int i = 0; i < b.size(); ++i )
    if( b[ i ].find_first_of( pattern ) != std::string::npos )
      b.erase( i-- );

So any word containing a, b, c, d, or e is erased. But the requirement says "comprising".

Let's check a dictionary:

1. to include or contain: The Soviet Union comprised several socialist republics.
2. to consist of; be composed of: The advisory board comprises six members.
3. to form or constitute: Seminars and lectures comprised the day's activities.

The first definition suggests that containing might be enough. But if you look at the example and at the other definitions, they paint a different story. To comprise of something means that all of the contents are the something. So a word like "cab" is comprised of a, b, c, d, and e. A word like "word" is not, even though it contains a d. So I believe that you failed this requirement.

Others have already said why your implementation might have been questionable. But you may have failed purely on interpretation of the requirements. Yes, my interpretation might be pedantic, but if your potential employer has legal contracts, those will be interpreted by equally pedantic lawyers.

If unsure, ask. It is not at all uncommon for interviews to be deliberately pedantic like this to weed out people who don't ask for clarification.

Answer 2

You should read this: https://lokiastari.com/posts/Vector-ResourceManagementAllocation

note it is part of a series of 5 articles.

• They did not ask for an iterator. So I am not sure why there is one.
• Underscore at the bininning of an identifier is never a good idea.
  The rules about its usage are complex at best. Also most people don't know them so avoid using them if you can. Most importantly though is that you violated the rules and used a reserved identifier.
• You code does not implement the rule of three.
  There is no assignment operator. To be honest I would have been happier to see move semantics implemented over iterators.
  It's hard to see that you made this private. But it's sill wrong. You should not have a body (to make sure you get a linker error if you accidentally use it) or use C++11 = delete; syntax to remove it.
• Your layout is very non standard for C++
  I have seen this style in other languages like javascript but not in C++

The alignment of you parameters just looks funny.

CArray(
    unsigned int _capacity = CARRAY_DEFAULT_CAPACITY
  ): _mArray(static_cast<TData*>(::operator new[](_capacity * sizeof(TData)))),
     _mCurPos(0), _mEnd(_capacity)
{}

void init_reserve(
    unsigned int _count
  )
{ /* STuff */ 
}

Looks nicer and easier to read like this:

CArray(std::size_t capacity = 512)
    : mArray(allocateSpace(capacity)
    , mCurPos(0)
    , mEnd(capacity)
{}

void init_reserve(std::size_t count)
{ /* STuff */ 
}

• Use {} for all sub blocks (especially in an interview) But especially in real life. You don't want to debug that situation where the loop or condition dependent on two statements rather than one.

Example: Apple SSL bug

if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
    goto fail;
    goto fail;

• Your implementation of init_reserve() does not provide the strong exception guarantee. If something fails your object is left in an invalid state.
• Your void insert(unsigned int _index,const TData & _value) is broken.
  It uses placement new to add the new item. Even though the memory location it uses has already been constructed (it was in use so it should be good). In this case you should be using copy construction (or move construction).
• Why is the at() const and operator[] non const. I would expect to see two of each (both const and non cost of each).
• If you are going to define operator<<() you should also define operator>>() for symmetry.
• The _destruct_objects() should probably delete the objects in reverse order.

Answer 3

• Don't define functions with a leading underscore, those names are reserved by the standard.
• Don't use (s)rand. Instead use std::mt19937 and std::uniform_int_distribution. For some real depth on the topic.
• Your RandGenerator class feels like unnecessary boilerplate to me, and it feels like a poor fit for _generate_word() since you specify the range of characters in the constructor for RandGenerator rather than the function itself. You rely on the callsite also specifiying set_upperbound(26).
• Is 512 a reasonable default capacity?
• You can omit return 0
• No assignment operator is defined in the CArray class, violating the rule of 3. I appreciate you may not have had control over the interface though. (Move ctors would also have been good to see).