Integer to Roman

http://www.leetcode.com/onlinejudge
http://en.wikipedia.org/wiki/Roman_numerals

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

/*Passed both small and large tests**/
class Solution {
    string buildDigit(string ivx, int num){//num [0~9]
        string result("");
        if (!num) return result;//0
        else if (num <= 3){//1,2,3
            for(;num>0;--num){
                result.push_back(ivx[0]);
            }
        }
        else if (num == 4 || num == 9){//4,9
            result.push_back(ivx[0]);
            result.push_back(ivx[num/4]);//1,or 2
        }
        else{//5,6,7,8
            result.push_back(ivx[1]);
            for(; num > 5; --num){
                result.push_back(ivx[0]);
            }
        }
        return result;

    }
public:
    string intToRoman(int num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        vector<string> one(3,"");
        one[0]="IVX";
        one[1]="XLC";
        one[2]="CDM";
        string result("");
        for(int ii = 0; ii < 3 && num>0; ++ii){
            int digit = num%10;
            num /= 10;
            result = buildDigit(one[ii], digit)+result;
        }
        for(;num>0;--num){
            result = one[2][2] + result;
        }
        return result;
    }
};

Insert Interval

http://www.leetcode.com/onlinejudge

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

/**Passed both small and large tests.
 * Be especially careful with the coundary cases
 * 
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (intervals.empty()) return vector<Interval>(1,newInterval);//base case 0
        int index1 = 0;
        for(; index1 < intervals.size(); ++index1){
            if (intervals[index1].start > newInterval.start) break;
        }
        if (index1){
            --index1;
            if (newInterval.start <= intervals[index1].end){//merge
                newInterval.start = intervals[index1].start;
            }else ++index1;//inclusive
        }
        int index2 = index1;//index2 >= 0
        for(; index2 < intervals.size(); ++index2){
            if (intervals[index2].end > newInterval.end) break;
        }
        if (index2 != intervals.size()){
            if (newInterval.end >= intervals[index2].start){
                newInterval.end = intervals[index2].end;
                ++index2;//skip the element
            }
        }
        vector<Interval> result(intervals.begin(),intervals.begin()+index1);
        result.push_back(newInterval);
        if (index2 <= intervals.size())
            result.insert(result.end(),intervals.begin()+index2, intervals.end());
        return result;
        
    }
};

Implement strStr()

Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

The fastest Boyer-Moorer algorithm can be found here.

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!haystack || !needle) return NULL;
        if (!*needle) return haystack;
        string const text(haystack);
        string const pattern(needle);
        size_t const pMax = pattern.size() - 1;
        for(size_t tailPos = pMax; tailPos < text.size();){
            size_t tPos = tailPos;
            int pPos = pMax;
            for(; pPos >= 0; --pPos, --tPos){
                if (text[tPos] != pattern[pPos]){
                    ++tailPos;
                    break;
                }
            }//for pPos
            if (pPos < 0) return (haystack + tailPos - pMax);
        }//for tPos
        return NULL;
    }
};

Flatten Binary Tree to Linked List

http://www.leetcode.com/onlinejudge

Similar to Convert Sorted List to Binary Search Tree.
 If there is only one branch, move that branch to the right, label left NULL, and recursively process the right child.
If there are two sub trees, take off the right subtree, RS; move the left subtree, PL, to the right, and label left NULL; process the new right child PL (the pointer, PR, will point to the last element of the right child after this process). Attached the detached RS to PR, then process on RS.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public://pre-order
    void pre_order(TreeNode * &root){
        if (!root->left && !root->right) return;
        
        if (!root->left){//left is NULL
            root = root->right;
            pre_order(root);
            return;
        }
        if (!root->right){//right is NULL
            //return;
            root->right = root->left;
            root->left = NULL;
            root = root->right;
            pre_order(root);
            return;
        }
        
        //neither children is NULL
       TreeNode* rightRoot = root->right;
        root->right = root->left;
        root->left = NULL;
        root = root->right;
        pre_order(root);
        root->right = rightRoot;
        root = rightRoot;
        pre_order(root);
        return;
        
    }
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root) return;
        pre_order(root);
        return;
    }
};

Divide Two Integers

http://www.leetcode.com/onlinejudge
Divide two integers without using multiplication, division and mod operator.

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int y = dividend;
        int x = divisor;
        bool signFlag = 0;
        if (y > 0){
            y = -y;//defualt for
            dividend = y;
            signFlag = 1;
        }
        if (x > 0){
            x = -x;//both negatives
            divisor = x;
            signFlag = !signFlag;
        }
        //     10|11
        //     00|01
        int totalShift = 0;
        while(y < x){
            ++totalShift;
            y >>= 1;
        }
        if (y == x) ++totalShift;
        --totalShift;
        // |divisor<<totalShift|    <=   |dividend|
        int result = 0;
        for(y = dividend, x = divisor<<totalShift;//y <= x
                totalShift >= 0;
                --totalShift){
            result <<= 1;
            if (y <= x){
                ++result;
                y -= x;
            }
            x >>= 1;
        }
        if (signFlag){
            result = - result;
        }
        return result;
    }
};

Distinct Subsequences

http://www.leetcode.com/onlinejudge

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE"while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

First approach is to use dynamic programming. Basically 2 cases:
1.  If current characters do not match, increment on S;
2.  If match, need to process two different cases:
    A: Using current match, increment on both S and T
    B:  keep doing case 1

/**Small test passed, but time limit exceeded for large set
*/
class Solution {
private:
    int count(string const& s, size_t s_index, string const& w, size_t w_index){
        if (s_index >= s.size() || w_index >= w.size()) return 0;
        if (s[s_index] != w[w_index]) return count(s,s_index+1,w,w_index);
        size_t result = 0;
        if (w_index +1 == w.size()) ++result;
        result += count(s, s_index+1, w, w_index+1);//search the rest part based on existing findings
        result += count(s, s_index+1, w, w_index);//new advanture regardless what found already
        return result;
    }//count()
    
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return count(S,0,T,0);
    }
};

 However, due to duplicated work, this algorithm is not efficient enough to pass large data set. Similar to the hint from the longest common sequence,  a bottom-up built table can be derived.

Notice that the current index pair (tt, ss) can depend on (ss, tt+1) and/or (ss+1,tt+1), provided that if the current character on (tt,ss) match. So the algorithm is simplified to
v[tt,ss]= {v[tt,ss] + v[tt,ss+1], if no match} or {v[tt,ss]+v[tt,ss+1]+v[tt+1,ss+1], otherwise}

And the boundary condition is filling with zeros, except for those tail match of the last char in T, which are assigned to +1.

For example, T={bag}, S={babgbag}, which should return 5.





And the dependencies are labeled by arrows:

The complete code:

/*passed both small and large tests**/

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> w(S.size()+1, 0);
        vector<vector<int> > v(T.size()+1, w);
        int maxS = S.size()-1;
        int maxT = T.size()-1;
        for(int ii = 0; ii < S.size(); ++ii){
            if (T[maxT] == S[ii]) v[maxT][ii] = 1;
        }//init
        for(int ss = maxS-1; ss>=0; --ss){
            for(int tt = maxT; tt >= 0; --tt){
                v[tt][ss] += v[tt][ss+1];
                if (T[tt] == S[ss]) v[tt][ss] += v[tt+1][ss+1] ;               
            }
        }
        return v[0][0];
    }
};

Convert Sorted List to Binary Search Tree

http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
Function vectorToList prototype trick credit to:
http://stackoverflow.com/questions/13547273/c11-defining-function-on-stdarraychar-n

Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

#include <iostream>
#include <array>
using namespace std;
/**
 * Definition for singly-linked list.*/
 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };
 
/**
 * Definition for binary tree */
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };


class Solution {
public:
    TreeNode* build(ListNode*& head, int start, int end){
      //the head points to the first element initially
        if (start > end) return NULL;
        int mid = (start+end)/2;
        TreeNode* leftChild = build(head, start, mid-1);
        //assume the head will advance (mid-start) times
        //after this above function returns, the head points to the middle element
        TreeNode* root = new TreeNode(head->val);
        root->left = leftChild;
        head = head->next;//advance in the list
        //now head points to the first element of the right half
        root->right = build(head, mid+1, end);
        //also, after this function returns, the head pointer
        //advances (end-mid), and now points to the last element in the list
        return root;
        
    }
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* it = head;
        int size = 0;
        while(it){
            ++size;
            it = it->next;
        }
        return build(head, 0, size-1);
    }
};
template<size_t N> ListNode* vectorToList(array<int, N> const& num){
  if (!N) return NULL;
  ListNode* head = new ListNode(num[0]);
  ListNode* it = head;
  for(size_t ii = 1; ii < N; ++ii, it = it->next){
    it->next = new ListNode(num[ii]);
  }//for ii
  return head;
}
int main(){
  array<int,3> a={3,5,8};
  ListNode* head = vectorToList(a);
  Solution s;
  TreeNode* root = s.sortedListToBST(head);
  cout<<"OK"<<endl;
}

Since the length of the list is needed only for counting the list-head advance steps, a slightly different version is derived:

class Solution {
public:
    TreeNode* build(ListNode*& head, int size){
        if (size<=0) return NULL;
        int half = size/2;
        TreeNode* leftChild = build(head, half);
        //assume the head will advance (mid-start) times
        //after this function returns, now the head points to the middle element
        TreeNode* root = new TreeNode(head->val);
        root->left = leftChild;
        head = head->next;
        root->right = build(head, size - half - 1);
        //also, after this function returns, the head pointer
        //advances (end-mid), and now points to the last element of the list
        return root;
        
    }
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* it = head;
        int size = 0;
        while(it){
            ++size;
            it = it->next;
        }
        return build(head, size);
    }
};

Convert Sorted Array to Binary Search Tree

http://www.leetcode.com/onlinejudge

/**passed both small and large judges.
Pretty straight forward: binary search like method.
Using the center element as the root, and recurse.
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int> const num, int const first, int const last){
        if (first > last) return NULL;
        int const center = (first+last)/2;
        TreeNode* root = new TreeNode(num[center]);
        if (first == last) return root;
        root->left = build(num, first, center-1);
        root->right = build(num, center+1,last);
        return root;
    }
    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return build(num,0,num.size()-1);
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

http://www.leetcode.com/onlinejudge

/**Passed both small and large judge.
Not so many surprise here, just pay extra attention to the boundary indices.
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int> const& preorder, int const pre_first, int const pre_last,
      vector<int> const& inorder, int const in_first, int const in_last){
          if (in_first > in_last) return NULL;
          TreeNode* root = new TreeNode(preorder[pre_first]);
          if (in_first == in_last) return root;
          size_t const r_in = distance(inorder.begin(), 
            find(inorder.begin()+in_first, inorder.begin()+in_last, root->val));
          size_t const sizeLeft = r_in - in_first;//size of left subtree
          root->left = build(preorder, pre_first+1, pre_first+sizeLeft-1,
            inorder, in_first, r_in-1);
          root->right = build(preorder, pre_first+sizeLeft+1, pre_last,
            inorder, r_in+1, in_last);
          return root;
      }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return build(preorder, 0, preorder.size()-1,
          inorder, 0, inorder.size()-1);
        
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

http://www.leetcode.com/onlinejudge

/**This one passed both small and large judge.
1. Find the root : Last element in postorder is the root; 
2. Find the position of the root in inorder.
The best strategy is to count the size of the left tree using inorder,
then use the size to split the postorder.

*/

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
#include <algorithm>
#include <map>
#include <deque>
#include <array>
#include <iostream>

using namespace std;
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
class Solution {
public:
    inline size_t valuePos(vector<int> const& v, int value){
        return distance(v.begin(),find(v.begin(), v.end(), value));
    }
    
    TreeNode* build(vector<int> const& inorder, int const in_first, int const in_last,
      vector<int> const& postorder, int const post_first, int const post_last){
          if (post_last-post_first < 0) return NULL;
          TreeNode* root = new TreeNode(postorder[post_last]);
          if (post_last - post_first == 0) return root;
          size_t const r_in = valuePos(inorder, root->val);//can narrow down the search range
          size_t const sizeL = r_in - in_first;
          root->left = build(inorder, in_first, r_in-1,
            postorder, post_first, post_first+sizeL-1);
          root->right = build(inorder, r_in+1, in_last,
            postorder, post_first+sizeL, post_last-1);
          return root;
      }
    
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (inorder.empty()) return NULL;
        return build(inorder, 0, inorder.size()-1,postorder, 0,postorder.size()-1);
    }
};

int main(){
  array<int, 3> a = {1,2,3};
  vector<int> q(a.begin(),a.end());
  vector<int> v(a.rbegin(),a.rend());
  Solution s;
  auto result = s.buildTree(q,v);
  cout<<result->val<<endl;
  return 0;
  
}

closely hovering

/**30 Answers
From the set of natural integer numbers
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}

Write an algorithm to compute the rearrangement of x that is closest 
to y but still greater than y. Both x and y have the same number of digits.

So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is
greater than y = 2410 and closer than any other arrangements of x.

And whats the time complexity of this algorithm?

- CameronWills on October 30, 2012 in United States | Report Duplicate 
*/

/**In another word, we want to find a number as small as possible,
call it hoverNumber;
First we construct the largest number from x. If this number is larger than y,
it proves the hoverNumber exists for such x,y.

Next, find the exact hoverNumber. Using DP and DFS.
Two cases:
1. when the higher digits are equal to y. Then the current digit can select
from the equal digit of y, and up;
2. when the higher digits are larger than y already. Then the current digit
should be as small as possible, selecting from the remaining digit pool.
*/
#include <iostream>
#include <vector>
#include <set>
using namespace std;

unsigned int parseInt(vector<unsigned int> const& v){
  //in vector v, v[0] is the highest digit position
  unsigned int result = 0;
  for(size_t ii = 0; ii < v.size(); ++ii){
    result = (result<<3) + (result<<1)+ v[ii];//10 = 8 + 2
  }
  return result;
}

vector<unsigned int> parseChar(unsigned int number){
  vector<unsigned int> result;
  while(number){
    result.push_back(number%10);
    number /= 10;
  }
  return vector<unsigned int>(result.rbegin(),result.rend());
}

ostream& operator<<(ostream& os, vector<unsigned int>const& v){
  for(size_t ii = 0; ii < v.size(); ++ii){
    os<<v[ii];
  }
  return os;
}

int compV(vector<unsigned int> const& v1, vector<unsigned int>const& v2,
  size_t end_index){//assume v1.size() == v2.size()
    //range [0, end_index)
    //return -1 if v1 < v2
    //return 0 if v1 == v2
    //return +1 if v1 > v2
    if (!end_index) return 0;
    for(size_t ii = 0; ii < end_index; ++ii){
      if (v1[ii] < v2[ii]) return -1;
      if (v1[ii] > v2[ii]) return 1;
    }
    return 0;
}
int compV(vector<unsigned int> const& v1, vector<unsigned int>const& v2){
  return compV(v1,v2,v1.size());
}

bool operator<(vector<unsigned int> const& v1, vector<unsigned int>const& v2){
  return (-1 == compV(v1,v2,v1.size()));
}


int hoverNumCalc(set<unsigned int>& digit_pool, vector<unsigned int>& result,
  vector<unsigned int> const& v_y){//assume the solution exists
    static int digit_level = 0;//inception...level, can use for vector index
    set<unsigned int>::iterator it = digit_pool.begin();
    if (digit_level + 1 == v_y.size()){//or use digit_pool.size() == 1
      //last element, only one way to construct the number
      result.push_back(*it);
      if (compV(result, v_y) <= 0){//not a good one
        result.pop_back();
        return -1;
      } else return 0;//succeed!
    }//if last one element
    if (0 == compV(result, v_y, digit_level)){//high digits the same
      //choose a minimum number that is barely larger than y-digit
      it = digit_pool.lower_bound(v_y[digit_level]);
    }
    for (;it != digit_pool.end();){
      result.push_back(*it);
      digit_pool.erase(it++);
      ++digit_level;
      if (!hoverNumCalc(digit_pool, result, v_y)) return 0;//relay the success
      --digit_level;
      digit_pool.insert(result.back());
      result.pop_back();
    }//for it
    return -1;
}

unsigned int hoverNumber(unsigned int number_x, unsigned int number_y){
  vector<unsigned int> vx(parseChar(number_x));
  set<unsigned int> sx(vx.begin(),vx.end());//small to big
  vector<unsigned int> vx_max(sx.rbegin(), sx.rend());//big to small
  vector<unsigned int> vy(parseChar(number_y));
  if (!(vy < vx_max)) return 0;//hoverNumber does not exist
  vx.resize(0);
  vx.reserve(vy.size());
  hoverNumCalc(sx, vx, vy);
  return parseInt(vx);
}

int main(){
  cout<<"Hello"<<endl;
  unsigned int a = 1234;
  unsigned int const b = 5678;//2410;
  unsigned int result = hoverNumber(a,b);
  if (!result) cout<<"No way!"<<endl;
  else cout<<result<<" is hovering over "<<b<<endl;

}

Big number

/**Define a structure / class to hold a very big number
(way bigger than bigint) and add a member functions to 
increment the number by 1 and decrement the number by 1

- Dee on November 06, 2012 in United States | Report Duplicate */

/**Use an array to simulate bits.
Need to take care of carry's when add/substract.
One trivial bug: negative zero. 
 */
#include <array>
#include <algorithm>
#include <iostream>
using namespace std;

class HugeNumber{
private:
  static const int DIGITS = 1000;
  array<unsigned short, DIGITS> number;//number[0] is the lowest digit
  bool negative_flag;
public:
  HugeNumber(){
    number.fill(0);negative_flag = false;
  }
  
  HugeNumber(int number_int){
    this->assign(number_int);
  }

  HugeNumber(HugeNumber const& n2){
    negative_flag = n2.negative_flag;
    for(unsigned int ii = 0; ii < DIGITS; ++ii)
      number[ii] = n2.number[ii];
  }
  HugeNumber& assign(int number_int){
    negative_flag = (number_int < 0);
    if (negative_flag) number_int = -number_int;
    for(unsigned int ii = 0; number_int; ++ii){
      number[ii] = number_int%10;
      number_int /= 10;
    }
    return *this;
  }//assign
  
  HugeNumber& operator++(){
    if (negative_flag){
      if (count(number.begin(),number.end(), 0) == DIGITS){//0
        negative_flag = false;
        ++number[0];
        return *this;
      }
      negative_flag = false;
      --(*this); 
      negative_flag = true;
      return (*this);
    }
    ++number[0];
    for(unsigned int ii = 0; ii < DIGITS-1 && number[ii] >= 10; ++ii){
      number[ii] -= 10;
      ++number[ii+1];
    }
    return *this;
  }

  HugeNumber& operator--(){
    if (count(number.begin(), number.end(), 0) == DIGITS){
      negative_flag = true;
      ++number[0];
      return *this;
    }
    if (negative_flag){
      negative_flag = false;
      ++(*this);
      negative_flag = true;
      return (*this);
    }
    for(unsigned int ii = 0; ii < DIGITS; ++ii){
      number[ii] = 9 - number[ii];
    }
    ++(*this);
    for(unsigned int ii = 0; ii < DIGITS; ++ii){
      number[ii] = 9 - number[ii];
    }
    return *this;
  }

  void output(ostream& os) const{
    if (negative_flag) os<<'-';
    for(unsigned int ii = DIGITS-1; ii > 0; --ii){
      if (!number[ii]) continue;
      os<<number[ii];
    }
    os<<number[0];//in case all digits are zero
  }

};

ostream& operator<<(ostream& os, HugeNumber& const number){
  number.output(os);
  return os;
}

int main(){
  cout<<"hello"<<endl;
  HugeNumber hn;
  hn.assign(-2);
  cout<<hn<<endl;
  ++hn;
  cout<<hn<<endl;
  ++hn;
  cout<<hn<<endl;
  ++hn;
  cout<<hn<<endl;
  ++hn;
  cout<<hn<<endl;
  ++hn;
  cout<<hn<<endl;
  --hn;
  cout<<hn<<endl;
  --hn;
  cout<<hn<<endl;
  --hn;
  cout<<hn<<endl;
  --hn;
  cout<<hn<<endl;
  --hn;
  cout<<hn<<endl;
  return 0;
}

Word evolution

/**26 Answers
Given a source string and a destination string write a program to display 
sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time 
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid 
sequence would be 
CAT -> COT -> DOT -> DOG
Another valid sequence can be 
CAT -> COT - > COG -> DOG

One character can change at one time and every resulting word has be a valid 
word from dictionary

- Dee on November 06, 2012 in United States | Report Duplicate 
*/

/**This is a graph problem. We define "neighbor" as the words off by only 
one letter.
First step, find all the neighbors of the source word. Then find the neighbors
of the neighbors... and so on, until one of them is the destination word.
*/

/**The function below has memory leak... pretty bad that sometime it eats up
1G memory...

The dictionary I used was from Ubuntu 12.04 LTS, /usr/share/dict/words
*/
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <memory>
#include <set>
#include <deque>
using namespace std;
set<string> dictParser(string fileName = "words.txt"){
  ifstream dictFile(fileName);
  set<string> result;
  if (!dictFile.good()) return result;

  dictFile.seekg (0, ios::end);
  size_t const fileLength = dictFile.tellg();
  dictFile.seekg (0, ios::beg);

  char* readInBuffer = new char[fileLength];
  dictFile.read(readInBuffer, fileLength);
  stringstream allWords(readInBuffer);
  delete[] readInBuffer;
  dictFile.close();

  string word;
  while(!allWords.eof()){
    allWords >> word;
    result.insert(word);
  }
  return result;
}

class Node{
public:
  Node(string name):word(name),parent(0){}
  string word;
  vector<Node* > children;
  Node* parent;
};

bool off_by_one(string const& s1, string const& s2){
  if (s1.length() != s2.length()) return false;
  int counter = 0;
  for(int ii = 0; ii < s1.length(); ++ii){
    if (s1[ii] != s2[ii]) ++counter;
  }
  return (1 == counter);
}
vector<string> mutationPath(string const& source, string& const dest, 
  set<string>& dict){

  vector<string> result;
  Node* sp = new Node(source);
  dict.erase(source);
  deque<Node* > frontier;
  frontier.push_back(sp);
  while(!frontier.empty()){
    Node* node = frontier.front(); frontier.pop_front();
    string const word = node->word;
    for (auto it = dict.begin(); it != dict.end();){
      string const neighbor(*it);
      if (neighbor.size() != dest.size()){dict.erase(it++); continue;}
      if (off_by_one(word, neighbor)){
        if (dest == neighbor){
          result.push_back(neighbor);
          while(node){
            result.push_back(node->word);
            node = node->parent;
          }
          return vector<string>(result.rbegin(),result.rend());
        }
        dict.erase(it++);
        auto it_n = new Node(neighbor);
        node->children.push_back(it_n);
        node->children.back()->parent = node;
        frontier.push_back(it_n);
      }else ++it;
    }//for it
  }//while not empty
  return result;
  //--------------------------
}

int main(){
  set<string> dict(dictParser());//it is sorted
  cout<<dict.size()<<endl;

  string sourceWord("cat");
  string destWord("dog");

  vector<string> path(mutationPath(sourceWord, destWord, dict));
  for(int ii = 0; ii < path.size(); ++ii){
    cout << path[ii] <<endl;
  }
  return 0;

}

And here is an improved version using smart pointers that avoids memory leak:

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <memory>
#include <set>
#include <deque>
using namespace std;
set<string> dictParser(string fileName = "words.txt"){
  ifstream dictFile(fileName);
  set<string> result;
  if (!dictFile.good()) return result;

  dictFile.seekg (0, ios::end);
  size_t const fileLength = static_cast<size_t>(dictFile.tellg());
  dictFile.seekg (0, ios::beg);

  shared_ptr<char> readInBuffer(new char[fileLength]);
  dictFile.read(readInBuffer.get(), fileLength);
  stringstream allWords(readInBuffer.get());
  //delete[] readInBuffer;
  dictFile.close();

  string word;
  while(!allWords.eof()){
    allWords >> word;
    result.insert(word);
  }
  return result;
}

class Node{
public:
  Node(string name):word(name){}
  string word;
  vector<shared_ptr<Node> > children;
  weak_ptr<Node> parent;
};

template <typename T>
int edit_distance(T const& s1, T const& s2){
  int const s1s = s1.size(), s2s = s2.size();
  vector<vector<int>> matrix(s1s+1, vector<int>(s2s+1));
  //s2 horizontal, s1 vertical
  for(int ii = 0; ii <= s1s; ++ii) matrix[ii][0] = ii;
  for(int ii = 0; ii <= s2s; ++ii) matrix[0][ii] = ii;
  for(int ii = 1; ii <= s1s; ++ii){
    for(int jj = 1; jj <= s2s; ++jj){//scan from left to right
      //line by line
      matrix[ii][jj] = min(min(matrix[ii-1][jj], matrix[ii][jj-1])+1,
        matrix[ii-1][jj-1]+static_cast<int>(s1[ii-1] != s2[jj-1]));
    }//for jj
  }//for ii
  return matrix[s1s][s2s];
}

bool off_by_one(string const& s1, string const& s2){
  if (s1.length() != s2.length()) return false;
  int counter = 0;
  for(unsigned int ii = 0; ii < s1.length(); ++ii){
    if (s1[ii] != s2[ii]) ++counter;
  }
  return (1 == counter);
}
vector<string> mutationPath(string const& source, string const& dest, 
  set<string>& dict){

  vector<string> result;
  shared_ptr<Node> sp(new Node(source));
  dict.erase(source);
  deque<shared_ptr<Node> > frontier;
  frontier.push_back(sp);
  while(!frontier.empty()){
    shared_ptr<Node> node(frontier.front()); frontier.pop_front();
    string const word = node->word;
    for (auto it = dict.begin(); it != dict.end();){
      string const neighbor(*it);
      if (neighbor.size() != dest.size()){dict.erase(it++); continue;}
      if (off_by_one(word, neighbor)){
        if (dest == neighbor){
          result.push_back(neighbor);
          while(node){
            result.push_back(node->word);
            node = node->parent.lock();
          }
          return vector<string>(result.rbegin(),result.rend());
        }
        dict.erase(it++);
        shared_ptr<Node> it_n(new Node(neighbor));
        node->children.push_back(it_n);
        node->children.back()->parent = node;
        frontier.push_back(it_n);
      }else ++it;
    }//for it
  }//while not empty
  return result;
  //--------------------------
}

int main(){
  set<string> dict(dictParser());//it is sorted
  cout<<dict.size()<<endl;

  string sourceWord("cat");
  string destWord("dog");

  vector<string> path(mutationPath(sourceWord, destWord, dict));
  for(int ii = 0; ii < path.size(); ++ii){
    cout << path[ii] <<endl;
  }
  return 0;

}

Kth Largest element of a sorted matrix

/**Given a N*N Matrix. 
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.

- 646 on November 23, 2010 | Report Duplicate */

/**For me, it is easier to think of the P-th smallest element
and then use K = N*N-P
For example we have a 4*4 matrix:
1   10 19 20
2   22 30 40
21  30 40 50
39  40 50 60
The numbers are trivial, but the orders and the positions are important.

[0,0] is the smallest.
Ignore the boundary case for now. Every element has two definite directions:
going right or down, which results a larger number.

It is simpler than Dajikstra, we only need to keep the unvisited frontier 
elements in a priority queue. Every time we pop an element, mark it visited,
and immediately push in its two neighbors, i.e. right and down neighbors.
*/
/**In C++, the default priorit_queue is a max heap, especially when less-than
is defined.
*/
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <array>
using namespace std;
template <typename T>
class Solution{
  typedef tuple<T, int, int> Element;
  class ElementMore{
  public:
    bool operator() (const Element& lhs, const Element& rhs) const{
      return get<0>(lhs) > get<0>(rhs);
  }
  };//class ElementLess
public: 
  T getSmallRank(vector<vector<T>> const& matrix, int const k){
    if (matrix.empty()) return 0;
    int const N = matrix.size();
    if (N != matrix[0].size()) return 0;//not a square matrix
    if (k < 1 || k > N*N) return 0;
    //k is the desired rank to return
    vector<vector<T>> visitFlag;
    visitFlag.resize(matrix.size());
    for(auto it = visitFlag.begin(); it != visitFlag.end(); ++it) it->resize(matrix.size());
    //init visitFlag to all 0. label 1 for visited
    Element element = make_tuple(matrix[0][0], 0, 0);//<value, row, col>
    priority_queue<Element, vector<Element>, ElementMore> frontier;
    frontier.push(element);
    visitFlag[0][0] = 1;
    for(int rank = 1; rank < k; ++rank){
      element = frontier.top(); frontier.pop();
      int const row = get<1>(element);
      int const col = get<2>(element);
      if (col + 1 < N && !visitFlag[row][col+1]){//element has a right neighbor
        frontier.push(make_tuple(matrix[row][col+1],row,col+1));
        visitFlag[row][col+1] = 1;
      }//right neighbor
      if (row + 1 < N && !visitFlag[row+1][col]){//has a down neighbor
        frontier.push(make_tuple(matrix[row+1][col],row+1,col));
        visitFlag[row+1][col] = 1;
      }//down neighbor
    }//for rank
    return get<0>(frontier.top());
  }//getSmallRankP

  T getBigRank(vector<vector<T>> const& matrix, int const k){
    return getSmallRank(matrix, matrix.size()*matrix.size()-k+1);
  }

};

int main(){
  cout<<"HEllo"<<endl;
  array<int, 4> a = {1 ,  10, 19, 20};
  array<int, 4> b = {2 ,  22, 30, 40};
  array<int ,4> c = {21,  33, 40, 50};
  array<int, 4> d = {39,  40, 51, 60};
  //ranks:        1 ,2, 3,  4,  5,  6, 7
  //elements:     1 ,2, 10, 19, 20, 21,22
  //and rank 15 is 51
  //and rank 16 is 60
  vector<vector<int>> matrix;
  matrix.resize(4);
  matrix[0].assign(a.begin(),a.end());
  matrix[1].assign(b.begin(),b.end());
  matrix[2].assign(c.begin(),c.end());
  matrix[3].assign(d.begin(),d.end());
  Solution<int> s;
  for(int ii = 1; ii <=7; ++ii){
    auto result = s.getSmallRank(matrix,ii);
    cout<<result<<endl;
  }
  cout<< s.getSmallRank(matrix, 15)<<endl<<endl;
  cout<< s.getSmallRank(matrix, 16)<<endl<<endl;
  cout<< s.getBigRank(matrix, 2)<<endl<<endl;

}

Match for semi finals

Consider a series in which 8 teams are participating. each team plays twice with all other teams. 4 of them will go to the semi final.How many matches should a team win, so that it will ensure that it will go to semi finals.?

- putta.sreenivas on May 11, 2011 | Report Duplicate

 http://www.careercup.com/question?id=9119235

56 points are distributed to 8 team. In the worst case, team0 loses all the games, he gets 0 point. team1 win two games with team0 and loses all other games, he gets 2 points. In the same way, team2 gets 4 points, team3 gets 6 points. So there are 44 points left which can be distributed to the remaining 4 teams. So the assurance points for a team should be 11 points.

- wenlei.zhouwl on May 22, 2012 

Interleave strings

The best way is to use dynamic programing. Here is an example: The two short strings are b="daba" and a="cbaa", and the long string is "dabacbaa". They are indexed 1 strings. We start from the last elements.

• Step1. Both a[4] and b[4] matches the element c[8], so the true/false grid [4,4] depends on its two neighbors, [4,3] and [3,4]. 

• Step2. For grid[4,3], a[4] matches c[7], so dependency goes up to [3,3]. 
• For grid[3,4], both a[3] and b[4] matches c[7], so dependency goes to two neighbors:[2,4] and [3,3] 

• Step3. For grid[3,3], b[3] matches c[6], so go left to [3,2]
• For gird [2,4], a[2] matches c[6], so go up to [1,4]

• Step4. For grid[3,2], no matches to c[5], halt (mark false)
• For grid[1,4], a[1] matches c[5], go up to [0,4]

• Step5-9. [0,4]->[0,3]->[0,2]->[0,1]->[0,0]

Grid [0,0] is the only true cell for base case, pass along the dependency and
we find out that [4,4] is true.
Link to the C++ code

/**Update 12/01/2012. This solution is not correct.

85 Answers
Three strings say A,B,C are given to you. Check weather 3rd string is 
interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)

- learn on August 27, 2012 in United States | Report Duplicate 
*/

/**Hints from the comments.
Simple case: pointers to A,B,C are pA,pB,pC. Compare pA (or pB) agains 
pC, if matches, ++pA (or ++pB) if none of pA or pB matches, return false

Duplication case: if pA and pB points to the same character, we call it 
a conflict. The conflict character is pushed into a FIFO queue, and do 
both ++pA and ++pB. When a non-conflict character appears, register it,
pA, for example. Keep searching until pA does not match the next character,
then you HAVE TO consider the conflict queue before using pB.

The queue should have a higher priority than pA/pB, since the queue stores
elemenens BEFORE the pointers.

When the queue is not empty, the match process switching between pA and pB
are forbidden. Since if pA is in process, the queue equivalently stores 
elements BEFORE current pB, so skipping the queue directly to pB 
is not allowed.
*/

#include <string>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
class Solution{
public:
  bool isInterleave(string const& A, string const& B, string const& C){
    if (C.length()!= A.length() + B.length()) return false;
    deque<int> conflict_que;
    int conflict_flag = 0;
    for(int aii = 0, bii = 0, cii = 0; cii < C.length(); ++cii){
      if (!conflict_que.empty() && conflict_que.front() == C[cii]){
        conflict_que.pop_front();
        continue;
      }//conflict_que has a match
      if (A[aii] == B[bii]){
        if (A[aii] == C[cii]){
          ++aii; ++bii; conflict_flag = 0;
          conflict_que.push_back(A[aii]);
          continue;
        } else return false;//A==B, but no match for C
      } else if (A[aii] == C[cii]){
        if (!conflict_que.empty() && conflict_flag == 2) return false;
        //attemp to jump over conflict_que from B
        ++aii; conflict_flag = 1;
        continue;
      } else if (B[bii] == C[cii]){
        if (!conflict_que.empty() && conflict_flag == 1) return false;
        ++bii; conflict_flag = 2;
        continue;
      } else return false;//no match at all, check queue
    }//for cii
    return true;
  }//isInterleave
};

int main(){
  cout<< "Hello"<<endl;
  string A("aaa");
  string B("abc");
  string C("aabcaa");
  Solution s;
  bool result = s.isInterleave(A,B,C);
  cout << result <<endl;
  A = "abcd"; B ="xyz"; C = "axybczd";
  result = s.isInterleave(A,B,C);
  cout<< result <<endl;
  return 0;
}