CareerCup

IMHO first question to be asked is - what does it mean that application 'stops working'. Does it mean it crashed, locked or exit?

int bits(unsigned char i) {
    int mask = 1;
    int count = 0;
    
    while(mask<=i) {
        if (i&mask) {
            count++;
        }
        mask <<= 1;
    }
    return count;
}

If you can ask questions, surely you should get more info on it.

They said " In the past 24 hours processing the customer order is taking really long time".
I would firstly ask what do they mean by "processing". Does it mean
- submitting order by customer on website
- getting placed order to warehouse delivery system
- getting product from warehouse to delivery team
- maybe delivering to customer, etc
In other words narrow down where the bottleneck can be.

Also is it experienced by all customers? If not, then by which? Maybe new customers, or maybe customers from specific country, or maybe customers which used specific payment way - ex paypal, or visa, or specific system or browser, or maybe only regular or prime customers?

Is this delay experienced on all goods? or only certain products?

Does nagios (or any of their network monitoring system) reports any faults?

Also product which were added in last 24 hours, was it excessive (unusual) amount of products add?

Did they have similar problem before, and if so, what was the reason?

I could go on and on...

C++ solution

RootToLeafPath.hpp

//
//  RootToLeafPath.hpp
//

#ifndef RootToLeafPath_hpp
#define RootToLeafPath_hpp

#include <stdio.h>
#include <vector>
#include <iostream>
#include <list>
#include <sstream>

using namespace std;

namespace RootToLeafPath {
    class TreeNode {
        
    public:
        TreeNode( int val ) {
            _value = val;
            _left = _right = NULL;
        }
        
        ~TreeNode() {
            // free nodes memory
        }
        
        TreeNode* addLeft(int value) {
            TreeNode* node = new TreeNode(value);
            _left = node;
            return _left;
        }

        TreeNode* addRight(int value) {
            TreeNode* node = new TreeNode(value);
            _right = node;
            return _right;
        }
        
        bool amILeaf() const {
            return (_right == NULL && _left == NULL);
        }
        
        vector<string> pathsToLeafs() {
            _paths.clear();

            list<int> path;
            travers(this, path);
            return _paths;
        }
        
    private:
        void travers(TreeNode* node, list<int> path) {
            if ( node == NULL ) {
                return;
            }

            path.push_back(node->_value);
            
            if (node->amILeaf()) {
                ostringstream pathSS;
                
                for (auto p : path) {
                    pathSS << p << "->";
                }
                string pathString;
                pathString = pathSS.str();
                pathString.erase(pathString.end()-2, pathString.end());
                
                _paths.push_back(pathString);
            }
            else {
                travers(node->_left, path);
                travers(node->_right, path);
            }
        }
        
    private:
        static vector<string> _paths;
        int _value;
        TreeNode *_left, *_right;
    };
}


#endif /* RootToLeafPath_hpp */

RootToLeafPath.cpp

#include "RootToLeafPath.hpp"
vector<string> RootToLeafPath::TreeNode::_paths;

TestCase

//
//  main.cpp
//

#include <iostream>
#include <vector>
#include "google/RootToLeafPath.hpp"

using namespace std;

int main() {
    RootToLeafPath::TreeNode root(1);
    
    root.addLeft(2)->addRight(5);
    root.addRight(3);

    auto paths = root.pathsToLeafs();
    for (auto p : paths) {
        cout << p << endl;
    }
    
    return 0;
}

To find max height of a tree - DFS algorithm should be used
NTreeGetHegiht.hpp

//
//  NTreeGetHeight.hpp
//  codility-lessons-refresh
//
//  Created by Przemek Urbanski on 17/11/16.
//  Copyright © 2016 Przemek Urbanski. All rights reserved.
//

#ifndef NTreeGetHeight_hpp
#define NTreeGetHeight_hpp

#include <stdio.h>
#include <list>
#include <vector>

using namespace std;

namespace NTreeGetHeight {
    class Graph {
    public:
        Graph(int elements);
        void addEdge(int parent, int child);
        int height();
    
    private:
        int travers(int nodeId, int nodeHeight);
        
    private:
        vector< list<int> > _nodes;
        int _height;
    };
};
#endif /* NTreeGetHeight_hpp */

NTreeGetHeight.cpp

#include "NTreeGetHeight.hpp"
#include <iostream>

using namespace std;

namespace NTreeGetHeight {
    
    Graph::Graph(int elements) {
        _nodes.resize(elements);
        _height = 0;
    }
    
    void Graph::addEdge(int parent, int child) {
        _nodes[parent].push_front(child);
    }
    
    int Graph::height() {
        // for graph with nodes count 0, 1, 2
        // its height is equal to its node cound.
        if (_nodes.size() < 3 )
            return _nodes.size();
        
        travers(0, 0);
        return _height;
    }
    
    int Graph::travers(int nodeId, int nodeHeight) {
        for (auto node : _nodes[nodeId] ) {
            _height = max( travers(node, nodeHeight+1), _height);
        }
        
        // There is a bit of optimization can be done here.
        // Keep track of visited node count.
        // Then if ( total_graph_nodes_count - visited_nodes_count <= _height )
        // you can stop traversing. As there is not enough unvisited nodes which can beat
        // current _height;
        return nodeHeight;
    }
};

Test

#include <iostream>

using namespace std;
using namespace NTreeGetHeight;

int main() {
    Graph ntree(11);
    
    ntree.addEdge(0,1);
    ntree.addEdge(0,9);
    ntree.addEdge(0,4);

    ntree.addEdge(1,2);
    ntree.addEdge(1,3);

    ntree.addEdge(9,10);

    ntree.addEdge(10,5);

    ntree.addEdge(5,6);
    ntree.addEdge(5,7);
    ntree.addEdge(5,8);
    
    cout << ntree.height();
    
    return 0;
}

// Time: O(n)
// Space: O(1)
// It will not work if there are values in array < 0
// 0 case is handled fine
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
    std::vector<int> ret;
    int processedMarker = A.size();
    
    for (int i=0; i<A.size(); i++) {
        if ( A[i] != i ) {
            int newIndex;
            
            while( A[i] != i ) {
                newIndex = A[i];
                if (A[i] == processedMarker || A[newIndex] == processedMarker )
                    break;
                
                if (A[newIndex] == A[i]) {
                    ret.push_back(A[i]);
                    A[newIndex] = processedMarker;
                    A[i] = processedMarker;
                    break;
                }
                
                swap(A[i], A[newIndex]);
            }
        }
    }
    return ret;
}

int main()
{
    vector<int> A{0,2,1,1,1,1,0,2};
    auto V = arrayDuplicates(A);
    for (auto v : V) {
        cout << v << endl;
    }
    return 0;
}

// Time: O(n)
// Space: O(1)
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
    std::vector<int> ret;
    int processedMarker = A.size();
    
    for (int i=0; i<A.size(); i++) {
        if ( A[i] != i ) {
            int newIndex;
            
            while( A[i] != i ) {
                if (A[i] == processedMarker || A[newIndex] == processedMarker )
                    break;
                
                if (A[newIndex] == A[i]) {
                    ret.push_back(A[i]);
                    A[newIndex] = processedMarker;
                    A[i] = processedMarker;
                    break;
                }
                
                swap(A[i], A[newIndex]);
            }
        }
    }
    return ret;
}