Decision Tree

Simple parsing and traversal problem

  1. concate all strings into a single line
  2. parse the string into a binary tree
  3. pass each query in to traverse

parse(int start, int end)

  skip space
  double prob = tokenizeNextDouble

  skip space
  if (start == end)
    return new node(prob, "", null, null)
  else
    string nodeName = tokenizeNextStr
    skip space
    int leftEnd = findNextRP(start)
    leftNode = parse(start, leftEnd)
    skip space
    int rightEnd = findNextRP(start)
    rightNode = parse(start, rightENd)
    return new node(prob, nodeName, leftNode, rightNode)

calc(double p, set features) p *= prob if (p->leftNode == null) return p

if(features.count(nodeName) == 1)
    return leftNode->calc(p, features)
else
    return rightNode->calc(p, features)

The Next Number

starting from the right end, find the longest sequence such that digits[i] >= digits[i+1]

if the sequence is the whole string, we need to add a 0,i.e, the new sequence would be
digit[0] + 0 + digit[1]....digit[n-1] reversed

Otherwise, we include the next digit to the left, and the next number would be 
  smallest digit greater than that digit, and then the remaining digits in an ascending order

Square Math

Number theory related. Too hard for me.