Archives

gravatar

Coding practice of NVDA


My reviewed solution for P*B/SI C*D Engineer writing testing from my colleague and friend. Just for your consideration only, don't copy or publish without any permissions. There is no any warranties to use following in your project and solution.



1a)
class GraphNode {
    std::vector     adj_nodes;
    std::string                 node_name;
public:
    GraphNode(const char* name) : node_name(name) { }
    void                insert(GraphNode* v)    { adj_nodes.push_back(v); }
    
    const std::string&  name() const    { return node_name; }
    int                 size() const    { return adj_nodes.size(); }
    GraphNode*          operator[](int n) const { return adj_nodes[n]; }
    GraphNode*          get(int n) const { return adj_nodes[n]; }
};

1b)
void depthFirstTraversal (const GraphNode *root) {
    std::stack  stack;    
    stack.push(root);    
    while(!stack.empty()) {
        const GraphNode* vertex = stack.top();
        stack.pop();
        std::cout << vertex->name() << std::endl;
        for(int i=0, size=vertex->size(); i < size; ++i )
            stack.push( (*vertex)[i] );
    }
}


1c)
void breadthFirstTraversal (const GraphNode *root) {
    std::queue  queue;    
    queue.push(root);    
    while(!queue.empty()) {
        const GraphNode* vertex = queue.front();
        queue.pop();
        std::cout << vertex->name() << std::endl;
        for(int i=0, size=vertex->size(); i < size; ++i )
            queue.push( (*vertex)[i] );
    }
}


1d)
template struct my_hash {
  size_t operator()(const T* __s) const
  { return (size_t)__s; }
};
typedef __gnu_cxx::hash_map >  visit_hash;
bool hasCycle2 (const GraphNode* vertex, visit_hash& hash) {
    for(int i=0, size=vertex->size(); i < size; ++i ) {
        GraphNode* adj_node = (*vertex)[i];
        if(hash[ adj_node ])
            return true;
        hash[ adj_node ] = true;
        if( hasCycle2( adj_node, hash ) )
            return true;
        hash[ adj_node ] = false;
    }
    return false;
}
bool hasCycle (const GraphNode* root) {
    visit_hash   hash;
    return hasCycle2(root, hash);
}

2)
void showArcPoints(double x, double y, const Arc& arc, int n);
void printArcPoints(const Arc& arc, int n)
{
    const double diameter = arc.radius*2;
    const double cx = 0.5 * (arc.A.x + arc.B.x);
    const double cy = 0.5 * (arc.A.y + arc.B.y);
    const double dx = (arc.B.x - arc.A.x);
    const double dy = (arc.B.y - arc.A.y);
    const double length = sqrt(dx*dx + dy*dy);
    if( length == diameter )
        showArcPoints(cx,cy, arc, n);
    else if(length < diameter ) {
        const double height = sqrt( arc.radius*arc.radius - length*0.5*length*0.5);
        const double tdx = -height*dy/length;
        const double tdy =  height*dx/length;
        showArcPoints(cx+tdx, cx+tdy, arc, n);
        showArcPoints(cx-tdx, cx-tdy, arc, n);
    }
}

void showArcPoints(double x, double y, const Arc& arc, int n)
{
    double radian_A = asin((arc.A.y-y) / arc.radius);
    if(arc.A.x <= x)  radian_A = M_PI - radian_A;
    double radian_B = asin((arc.B.y-y) / arc.radius);
    if(arc.B.x <= x)  radian_B = M_PI - radian_B;
    double radian_diff = radian_A - radian_B;
    if(radian_diff < 0.0)
        radian_diff += M_PI * 2.0;
    radian_diff /= 1.0 * n;
    double radian = radian_A - radian_diff;
    std::cout << setprecision(3);
    std::cout << "(" << arc.A.x << "," << arc.A.y << ") " ;
    for(int i=0; i
        std::cout << "("
                  << arc.radius * cos(radian)
                  << ","
                  << arc.radius * sin(radian)
                  << ") ";
        radian -= radian_diff;
    }
    std::cout << "(" << arc.B.x << "," << arc.B.y << ")";
    std::cout << std::endl;
}

3)
void printDuplicates (const std::vector &items) {
    typedef std::map >   duplicate_hash;
    duplicate_hash   dup_count;  
    for(int i=0, size = items.size(); i < size; ++i )
        dup_count[ items[i] ] ++;
    duplicate_hash::const_iterator dup_iter;
    for(dup_iter = dup_count.begin(); dup_iter != dup_count.end(); ++dup_iter) {
        if(dup_iter->second >= 2)
            std::cout << dup_iter->first << std::endl;
    }
}