## Monday, February 15, 2016

### LeetCode OJ - Fraction to Recurring Decimal

Problem:

Solution:

Just grade school algorithm, doing trial division and remember all the seen remainders, if we ever get to the seen remainder again then just stop the loop.

The tricky part of getting the judge to like my solution is to make sure it works on all huge integers, in particular, (1 << 31) is tricky because you cannot take negative on it in a 32 bit integer, so I must expand to 64 bits integers. Not great, but it worked and simple enough than to worry about all sort of possibilities.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/fraction-to-recurring-decimal/

#include "LEET_FRACTION_TO_RECURRING_DECIMAL.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_FRACTION_TO_RECURRING_DECIMAL
{
typedef long long int64;

class Solution
{
public:
void fractionPart(ostringstream& ss, int64 numerator, int64 denominator)
{
vector<int64> quotient_digits;
map<int64, size_t> remainder_index;
int found = -1;
while (true)
{
if (numerator == 0)
{
break;
}
numerator *= 10;
map<int64, size_t>::iterator probe = remainder_index.find(numerator);
if (probe != remainder_index.end())
{
found = probe->second;
break;
}
remainder_index.insert(pair<int64, size_t>(numerator, quotient_digits.size()));
int64 quotient = numerator / denominator;
int64 remainder = numerator % denominator;
quotient_digits.push_back(quotient);
numerator = remainder;
}
ss << ".";
for (size_t i = 0; i < quotient_digits.size(); i++)
{
if (i == found)
{
ss << "(";
}
ss << quotient_digits[i];
}
if (found != -1)
{
ss << ")";
}
}

string fractionToDecimal(int numerator, int denominator)
{
int64 n = numerator;
int64 d = denominator;

bool positive = true;
if (n < 0)
{
positive = !positive;
n *= -1;
}
if (d < 0)
{
positive = !positive;
d *= -1;
}

ostringstream ss;
if (!positive && n != 0)
{
ss << "-";
}
ss << n / d;
int64 remainder = n % d;
if (remainder != 0)
{
fractionPart(ss, remainder, d);
}
return ss.str();
}
};
};

using namespace _LEET_FRACTION_TO_RECURRING_DECIMAL;

int LEET_FRACTION_TO_RECURRING_DECIMAL()
{
Solution solution;
cout << solution.fractionToDecimal(1, 2) << endl;
cout << solution.fractionToDecimal(2, 1) << endl;
cout << solution.fractionToDecimal(2, 3) << endl;
cout << solution.fractionToDecimal(1, 7) << endl;
cout << solution.fractionToDecimal(1, 70) << endl;
cout << solution.fractionToDecimal(1, 99) << endl;
cout << solution.fractionToDecimal(-50, 8) << endl;
cout << solution.fractionToDecimal((1 << 31), 1) << endl;
cout << solution.fractionToDecimal(1, (1 << 31)) << endl;
return 0;
}

## Sunday, February 14, 2016

### LeetCode OJ - Verify Preorder Serialization of a Binary Tree

Problem:

Solution:

If the string is simply a '#' sign, it is valid.
If the string begins with a number, then it should follows with a string that represents a tree, and then another string that represent a tree.

The problem is that we do not know how to split the string into that two halves, so let the recursion do it. The first recursive call should return the beginning of the next string, then we are good to go!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

#include "LEET_VERIFY_PREORDER_SERIALIZATION_OF_A_BINARY_TREE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_VERIFY_PREORDER_SERIALIZATION_OF_A_BINARY_TREE
{
class Solution
{
public:
int next(string& preorder, size_t start)
{
int end = start;
while (end < preorder.size())
{
if (preorder[end++] == ',')
{
break;
}
}
return end;
}

size_t verify(string& preorder, size_t start)
{
if (start == preorder.length())
{
return -1;
}
if (preorder[start] == '#')
{
return next(preorder, start);
}
else
{
int leftStart = next(preorder, start);
int rightStart = verify(preorder, leftStart);
if (rightStart == -1)
{
return -1;
}
else
{
return verify(preorder, rightStart);
}
}
}

bool isValidSerialization(string preorder)
{
int end = verify(preorder, 0);
return end == preorder.length();
}
};
};

using namespace _LEET_VERIFY_PREORDER_SERIALIZATION_OF_A_BINARY_TREE;

int LEET_VERIFY_PREORDER_SERIALIZATION_OF_A_BINARY_TREE()
{
Solution solution;
cout << (solution.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#") == true) << endl;
return 0;
}

### LeetCode OJ - Reconstruct Itinerary

Problem:

Solution:

The problem wasn't very explicit, but in fact it is asking for a path that use all the tickets. I just used recursive backtracking for the purpose.

The algorithm can be further improved by replacing the vector<string, bool> (as a list of available/used destination) to a data structure that allow us to remove and iterate fast. A doubly linked list will serve the purpose. I thought of something similar when I tried N-Queens.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/reconstruct-itinerary/

#include "LEET_RECONSTRUCT_ITINERARY.h"
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_RECONSTRUCT_ITINERARY
{
class Solution
{
public:
vector<string> findItinerary(vector<pair<string, string>> tickets)
{
map<string, vector<pair<string, bool>>> dest;

// Step 1: Build the map
for (size_t i = 0; i < tickets.size(); i++)
{
string src = tickets[i].first;
string dst = tickets[i].second;
map<string, vector<pair<string, bool>>>::iterator probe = dest.find(src);
if (probe == dest.end())
{
dest.insert(pair<string, vector<pair<string, bool>>>(src, vector<pair<string, bool>>()));
}
dest[src].push_back(pair<string, bool>(dst, true));
}

// Step 2 : Sort the destination vector
for (map<string, vector<pair<string, bool>>>::iterator di = dest.begin(); di != dest.end(); di++)
{
sort(di->second.begin(), di->second.end());
}
vector<string> soln;
soln.push_back("JFK");
this->findItinerary("JFK", soln, tickets.size() + 1, dest);
return soln;
}

bool findItinerary(string current, vector<string>& soln, int goal, map<string, vector<pair<string, bool>>>& dest)
{
map<string, vector<pair<string, bool>>>::iterator probe = dest.find(current);
if (probe == dest.end())
{
return (soln.size() == goal);
}
else
{
vector<pair<string, bool>> & dstvector = probe->second;
for (size_t i = 0; i < dstvector.size(); i++)
{
if (dstvector[i].second)
{
dstvector[i].second = false;
soln.push_back(dstvector[i].first);
if (findItinerary(dstvector[i].first, soln, goal, dest))
{
return true;
}
soln.pop_back();
dstvector[i].second = true;
}
}
return (soln.size() == goal);
}
}
};
};

using namespace _LEET_RECONSTRUCT_ITINERARY;

int LEET_RECONSTRUCT_ITINERARY()
{
Solution solution;
vector<pair<string, string>> itin;
// [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
//itin.push_back(pair<string, string>("MUC", "LHR"));
//itin.push_back(pair<string, string>("JFK", "MUC"));
//itin.push_back(pair<string, string>("SFO", "SJC"));
//itin.push_back(pair<string, string>("LHR", "SFO"));

// [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
//itin.push_back(pair<string, string>("JFK", "SFO"));
//itin.push_back(pair<string, string>("JFK", "ATL"));
//itin.push_back(pair<string, string>("SFO", "ATL"));
//itin.push_back(pair<string, string>("ATL", "JFK"));
//itin.push_back(pair<string, string>("ATL", "SFO"));

// [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]
itin.push_back(pair<string, string>("JFK", "KUL"));
itin.push_back(pair<string, string>("JFK", "NRT"));
itin.push_back(pair<string, string>("NRT", "JFK"));

vector<string> result = solution.findItinerary(itin);
for (size_t i = 0; i < result.size(); i++)
{
cout << result[i] << endl;
}
return 0;
}

## Saturday, February 13, 2016

### LeetCode OJ - Kth Largest Element in an Array

Problem:

Solution:

I implemented QuickSelect, a variant of QuickSort.
The idea is simple, just do partitioning as usual in QuickSort, but instead of recursing on two branches, just recurse on one them.

Getting all the details for the 3 way partitioning is tricky. I spent some good time on it. Again, printing out immediate state in a nicely formatted manner helped a lot.

The randomization of the pivot is important, that bring crazy amount of performance gain when the input is already sorted as expected.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/kth-largest-element-in-an-array/

#include "LEET_KTH_LARGEST_ELEMENT_IN_AN_ARRAY.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// #define LOG

namespace _LEET_KTH_LARGEST_ELEMENT_IN_AN_ARRAY
{
class Solution
{
private:
int findKthSmallest(vector<int>& nums, int start, int end, int k)
{
if (nums.size() == 1)
{
return nums[0];
}
#ifdef LOG
cout << "Starting a call" << endl;
#endif
int pivotIndex = rand() % (end - start) + start;
swap(nums[start], nums[pivotIndex]);

int pivot = nums[start];
int left = start;
int right = end;

// Maintain these variables
int smallerEnd = left;             // [left, smallerEnd) are strictly smaller than the pivot
int smallerOrEqualEnd = left + 1;  // [smallerEnd, smallerOrEqualEnd) are smaller or equal to the pivot
int largerBegin = right;           // [largerBegin, right) are strictly larger than the pivot

while (true)
{
while (smallerOrEqualEnd < nums.size() && nums[smallerOrEqualEnd] <= pivot)
{
if (nums[smallerOrEqualEnd] < pivot)
{
swap(nums[smallerEnd], nums[smallerOrEqualEnd]);
smallerEnd++;
}

smallerOrEqualEnd++;
}

while (largerBegin > 0 && nums[largerBegin - 1] > pivot)
{
largerBegin--;
}
#ifdef LOG
cout << "Before swap" << endl;
PrintState(nums, left, smallerEnd, smallerOrEqualEnd, largerBegin, right);
cout << endl;
#endif
if (smallerOrEqualEnd == largerBegin)
{
break;
}

// [left, smallerEnd) are strictly smaller than the pivot
// [smallerEnd, smallerOrEqualEnd) are equal to the pivot
// [largerBegin, right) are strictly larger than the pivot

// nums[smallerEnd] = pivot
// nums[smallerOrEqualEnd] > pivot
// nums[largerBegin - 1] <= pivot
if (nums[largerBegin - 1] == pivot)
{
swap(nums[smallerOrEqualEnd], nums[largerBegin - 1]);
smallerOrEqualEnd++;
largerBegin--;
}
else
{
nums[smallerEnd] = nums[largerBegin - 1];
nums[largerBegin - 1] = nums[smallerOrEqualEnd];
nums[smallerOrEqualEnd] = pivot;
smallerEnd++;
smallerOrEqualEnd++;
largerBegin--;
}
#ifdef LOG
cout << "After swap" << endl;
PrintState(nums, left, smallerEnd, smallerOrEqualEnd, largerBegin, right);
cout << endl;
cout << endl;
#endif
}

int smallPortionLength = smallerEnd - left;
if (k < smallPortionLength)
{
return this->findKthSmallest(nums, left, smallerEnd, k);
}
else
{
k -= smallPortionLength;
int pivotPortionLength = smallerOrEqualEnd - smallerEnd;
if (k < pivotPortionLength)
{
return pivot;
}
else
{
k -= pivotPortionLength;
return this->findKthSmallest(nums, smallerOrEqualEnd, right, k);
}
}
}

void PrintState(vector<int>& nums, int left, int smallerEnd, int smallerOrEqualEnd, int largerBegin, int right)
{
cout << "[";
for (int i = left; i < smallerEnd; i++)
{
cout << nums[i] << " ";
}
cout << "][";
for (int i = smallerEnd; i < smallerOrEqualEnd; i++)
{
cout << nums[i] << " ";
}
cout << "]";
for (int i = smallerOrEqualEnd; i < largerBegin; i++)
{
cout << nums[i] << " ";
}
cout << "[";
for (int i = largerBegin; i < right; i++)
{
cout << nums[i] << " ";
}
cout << "]" << endl;
}
public:
int findKthLargest(vector<int>& nums, int k)
{
return this->findKthSmallest(nums, 0, nums.size(), nums.size() - k);
}
};
};

using namespace _LEET_KTH_LARGEST_ELEMENT_IN_AN_ARRAY;

int LEET_KTH_LARGEST_ELEMENT_IN_AN_ARRAY()
{
int data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
vector<int> case1 = vector<int>(data, data + _countof(data));
Solution solution;
cout << solution.findKthLargest(case1, 1) << endl;
return 0;
}

## Saturday, February 6, 2016

### Polynomial processing in Python

These days I have been working on learning Python. I heard again and again that Python is easy to code and one can write something very quickly, so I would like to spend some time on it to get proficient on it. At the same time, I ran into a small problem that I need to solve with my studies in Algebraic Geometry, so I decided to force myself to write this piece of code in Python.

The full source code to the whole program is here on GitHub.

https://github.com/cshung/MiscLab/tree/master/GreatestCommonDivisor

The program has a very simple main driver. It simply compute the GCD of a few polynomials.

from polynomial_module import *

# Problem 8a
print polynomial.polynomial_gcd(
polynomial.polynomial_gcd(
polynomial.from_string("x^4 + x^2 + 1"),
polynomial.from_string("x^4 - x^2 - 2x - 1")),
polynomial.from_string("x^3 - 1"))

# Problem 8b
print polynomial.polynomial_gcd(
polynomial.polynomial_gcd(
polynomial.from_string("x^3 + 2x^2 - x - 2"),
polynomial.from_string("x^3 - 2x^2 - x + 2")),
polynomial.from_string("x^3 - x^2 - 4x + 4"))

Needless to say, these are the problems I wanted to solve.

The from_string method implies I wrote a parser for the strings. For the purpose of parsing these strings, I defined a small grammar for these strings and wrote a top-down recursive parser for it.

The GCD method is a simple Euclidean algorithm for computing GCD. In order to manipulate the polynomials in the algorithm, I wrote all four arithmetic operations in polynomial.

In order to make sure we have the precision we wanted, I used rational arithmetic. In Python, all numbers are big integer by default, so if the input has finite precision, the output will have finite precision, and we can always represent it as a fraction, that's why I introduced the rational class for that purpose.

## Monday, February 1, 2016

### LeetCode OJ - Clone Graph

Problem:

Solution:

Simply clone it with a map to avoid cloning the same node twice.

There was a stupid story when I keep getting time limit exceeded, turn out I was passing the map by value, the cloning time is overwhelming.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/clone-graph/

#include "LEET_CLONE_GRAPH.h"
#include <unordered_map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_CLONE_GRAPH
{
struct UndirectedGraphNode
{
int label;
vector<UndirectedGraphNode *> neighbors;
UndirectedGraphNode(int x) : label(x) {};
};
class Solution
{
private:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& context)
{
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>::iterator probe = context.find(node);
if (probe == context.end())
{
UndirectedGraphNode* clone = new UndirectedGraphNode(node->label);
context.insert(pair<UndirectedGraphNode*, UndirectedGraphNode*>(node, clone));
for (size_t i = 0; i < node->neighbors.size(); i++)
{
clone->neighbors.push_back(this->cloneGraph(node->neighbors[i], context));
}
return clone;
}
else
{
return probe->second;
}
}

public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node)
{
if (node == NULL)
{
return NULL;
}
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> context;
return this->cloneGraph(node, context);
}
};
};

using namespace _LEET_CLONE_GRAPH;

int LEET_CLONE_GRAPH()
{
UndirectedGraphNode a(1);
UndirectedGraphNode b(2);
a.neighbors.push_back(&b);
b.neighbors.push_back(&a);
Solution s;
UndirectedGraphNode* c = s.cloneGraph(&a);
cout << c->label << endl;
cout << c->neighbors.size() << endl;
cout << c->neighbors[0]->label << endl;
cout << c->neighbors[0]->neighbors.size() << endl;
cout << c->neighbors[0]->neighbors[0]->label << endl;
return 0;
}