Should a PhD student compete in programming competitions?

“an advice by Manuel Blum to beginning graduate students: Brains are muscles. They grow strong with exercise. And even if they’re strong, they grow weak without it. A self-contained algorithmic puzzle with cute solutions (that one can also look up after giving up) is one of the best exercises that I’m aware of.”

 

From the Answer by Richard Peng to problem Should a PhD student compete in programming competitions?

My take on this: unless your opportunity to participate properly was severely limited during undergraduate studies (e.g. if you went to Tsinghua), wait until you got a few major publications before taking part again.

I’m saying this mainly because doing well in programming competitions after the high school level is very practice-dependent. Early graduate studies often revolve around taking courses and reading past literature. Both of these activities directly conflict with the time required to stay in touch with the problem style and maintaing a reasonable coding speed.

That being said, it’s also my impression that as the main activity shifts more to developing new ideas, doing a few problems once a while is quite beneficial for gaining fresh perspectives on things. This is perhaps best explained via an advice by Manuel Blum to beginning graduate students: “Brains are muscles. They grow strong with exercise. And even if they’re strong, they grow weak without it.” A self-contained algorithmic puzzle with cute solutions (that one can also look up after giving up) is one of the best exercises that I’m aware of.

 

Advertisements

[OJ report] binary tree right side view

https://leetcode.com/problems/binary-tree-right-side-view/

The solution is at solution @ github .

The idea is to use DFS to do pre-order traversal of the mirror tree. At the same time, use an array to mark current level, so that we can keep from putting wrong element into the result vector.

class Solution {
public:
   void Helper( TreeNode * root, vector<int> & result,
                    int cur, vector<int> & marked ){
     if(root == NULL) return;
    // pre-order of the mirror binary tree
    // (DFS & just by swapping the traversal order)
    if( result.size() == cur ){
      // maintain a marked vector to keep from putting
      // wrong element into the result vector
      result.push_back(root->val);
    }
    Helper(root->right, result , cur+1, marked);
    Helper(root->left , result , cur+1, marked);
   }
  vector<int> rightSideView(TreeNode * root){
    vector<int> result, marked;
    if(root == NULL) return result;
    Helper(root, result, 0, marked);
    return result;
  }
};

The runtime complexity is O(n), where n is the node number.

The worst-case memory complexity is O(n) = O(n) .