DoZerg
BAN USERPersonal Information
Name: DAI ZHAO Sex: Male
Date of Birth: October 16, 1982 Birth Place: Hunan Province, China
Telephone: +86-15986679914 E-mail: daidodo@gmail.com
Work Experience
Jan. 2010 - present Tencent Technologies Co. Ltd. as a senior Linux Software Engineer
Jul. 2007- Jul. 2009 Xunlei Technologies Inc. as a Linux Software Engineer.
Education
Sep. 2004- Jul 2007 Dept. of Information Science and Application, Central South University in China, M.E
Sep. 2000- Jul. 2004 Dept. of Electrical and Mechanical Engineering, Central South University in China, B.E
Computer Abilities
• Strong programming skills in C/C++ and STL, knowledge of Java, MFC and NASM assembly language;
• Experience in Servers Architectures design and implementation;
• Familiar with TCP/IP and UDP protocols;
• Experience in design and implement Distributed Database Systems;
• Good at Algorithms, Linux Kernel, Virtual Machine and Compiler Implementation, and Debugging Techniques;
• Familiar with Linux/Unix operating systems, software development and testing methodology;
• Study in File System design and implementation, including Ext2, Ext3, ReiserFS and NTFS;
• Knowledge about Cryptography, .NET framework, Web Services and Software Engineering;
Qualifications
• Strong communication skill internally and externally;
• Strong in Problem solving and Decision making;
• Have good innovation consciousness and customer centricity;
• Strong ability for team co-work and study new knowledge capability;
• Have a passion for the Games and Software design;
- -2of 6 votes
AnswersGiven a dictionary of words, and a set of characters, judge if all the characters can form the words from the dictionary, without any characters left.
- DoZerg in United States
For example, given the dictionary {hello, world, is, my, first, program},
if the characters set is "iiifrssst", you should return 'true' because you can form {is, is, first} from the set;
if the character set is "eiifrsst", you should return 'false' because you cannot use all the characters from the set.
P.S. there may be tens of thousands of words in the dictionary, and the chars set length could be up to hundreds, so I really need some efficient algorithm.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
There are 2 solutions.
First solution is a top-down way. If task A depends on task B, we say A is a child of B. Preprocess all the tasks, construct the tasks trees, then we make the roots of all trees to be the children of a virtual root (Task Init). We start from execute(Task Init):
void execute(Task A)
{
waitForFinish(A.dependencies());
A.run();
foreach(Task C in A.children())
new thread(execute(C));
}
The second solution is the bottom-up way, and needs no preprocessing:
foreach(Task A in Set)
new thread(execute(A));
void execute(Task A)
{
foreach(Task B in A.dependencies())
new thread(execute(B));
waitForFinish(A.dependencies());
A.run();
}
NOTE that the check of re-execution of tasks is omitted since it's trivial using lock or atomic.
- DoZerg March 30, 2015O(N) time solution with O(1) space.
Say the original list is n1->n2->..., and the result list' is n1'->n2'->....
First, create list' and set:
n1'.next = n1.next;
n1.next = n1';
for all nodes in list'.
Second, iterate on list and set:
n1'.random = n1.random.next;
n1.next = n1'.next; //restore n1.next
n1'.next = n1.next.next; //adjust n1'.next
for all nodes in list'.
Here is the code:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head)
return NULL;
RandomListNode * cur = head;
while(cur){
RandomListNode * n = new RandomListNode(cur->label);
n->next = cur->next;
cur->next = n;
cur = n->next;
}
cur = head;
RandomListNode * ret = cur->next;
while(cur){
RandomListNode * cp = cur->next;
assert(cp);
if(cur->random)
cp->random = cur->random->next;
cur->next = cp->next;
if(cp->next)
cp->next = cp->next->next;
cur = cur->next;
}
return ret;
}
A DP solution.
Let T(i) denotes if s.substr(i) can be split into words of the dict, then
T(i) = false || T(i + W1) || T(i + W2) || ... , if s.substr(i, Wi) is a valid word.
bool wordBreak(string s, unordered_set<string> &dict) {
if(s.empty())
return true;
if(dict.empty())
return false;
size_t maxlen = 0, minlen = -1;
for(const auto & w : dict){
maxlen = max(maxlen, w.size());
minlen = min(minlen, w.size());
}
vector<bool> dp(s.size() + 1);
dp[0] = true;
for(size_t i = 0;i < s.size();++i){
for(size_t j = minlen;j <= i + 1 && j <= maxlen;++j){
if(!dp[i + 1 - j])
continue;
if(dict.count(s.substr(i + 1 - j, j)) > 0){
dp[i + 1] = true;
break;
}
}
}
return dp.back();
}
My solution: check characters from s1 and s2 until they're different, then skip 1 character in one or both strings based on the length of them, and check if the remains are identical:
#include <iostream>
#include <string>
using namespace std;
bool help(string s1, string s2, size_t p1, size_t p2)
{
for(size_t i = 0;p1 + i < s1.size();++i)
if(s1[p1 + i] != s2[p2 + i])
return false;
return true;
}
bool solve(string s1, string s2)
{
if(s1.size() > s2.size())
s1.swap(s2);
if(s1.size() + 1 < s2.size())
return false;
for(size_t i = 0;i < s1.size();++i){
if(s1[i] == s2[i])
continue;
if(s1.size() == s2.size())
return help(s1, s2, i + 1, i + 1);
return help(s1, s2, i, i + 1);
}
return (s1.size() < s2.size());
}
int main()
{
cout<<solve("xyz", "xz")<<endl;
cout<<solve("xyz", "xyk")<<endl;
cout<<solve("xy", "xyz")<<endl;
cout<<"---\n";
cout<<solve("xyz", "xyz")<<endl;
cout<<solve("xyz", "xzy")<<endl;
cout<<solve("xyz", "x")<<endl;
cout<<solve("x", "xyz")<<endl;
}
I agree with you about the NP-hardness, and I don't like people who down-votes something without thinking.
But as I know, subset sum problem is one dimensional, and this problem could be at least a 26-D subset sum problem. And I cannot see the similar way to solve it by comparing to the normal subset sum problem.
I can see your algorithm is based on recursion, and it's right for small test cases. But it consumes too much memory by allocating a lot of int[26], which will dramatically slow down the process. And there is no booking strategy during the process, so I don't think it's efficient enough to pass the interview.
- DoZerg March 21, 2014Suppose there are n(>0) sticks of length {L1, L2, ... , Ln}, where L1<=L2<=...<=Ln, I think the answer is:
cost =
(1) 0, if n=1;
(2) L1+L2, if n=2;
(3) L1 + 2 * (L2 + L3 +...+Ln-1) + Ln, if n>2;
Prove:
Each time we combine 2 sticks to 1, there remains n-1 sticks, until there is only 1 stick. So we need to combine n-1 times. To minimize each combine cost, we should choose the shortest 2 sticks all the time.
So, the 1st combine cost is L1+L2, left n-1 sticks of lenght {L2, L3, ... , Ln};
the 2nd combine cost is L2+L3, left {L3, L4, ..., Ln};
the 3rd combine cost is L3+L4, left {L4, L5, ..., Ln};
...
the total cost is L1+2*(L2 + L3 +...+Ln-1)+Ln.
Notice that if min>=8000, whatever max is, the answer is yes, because I can get all the range by pushing button 400-420 for 20 times or more. So I need only generate all the ranges under 8000( or even smaller), then the search for [min, max] can be done in O(log N). Here is the code:
static void prepare(std::vector<int> & ranges)
{
//generate bitmap
int edge = 8000; //400 / (420 - 400) * 400
std::vector<bool> vec(edge);
int mi1, mi2;
int mi, ma;
for(int i = 0;300 * i < edge;++i){
mi1 = 300 * i;
if(mi1 >= edge)
break;
for(int j = 0;400 * j < edge;++j){
mi2 = mi1 + 400 * j;
if(mi2 >= edge)
break;
for(int k = 0;500 * k < edge;++k){
mi = mi1 + mi2 + 500 * k;
if(mi >= edge)
break;
ma = 310 * i + 420 * j + 515 * k;
for(;mi <= ma && mi < edge;++mi)
vec[mi] = true;
if(ma >= edge)
while(vec[edge - 1])
--edge;
}
}
}
//scan for ranges
ranges.clear();
bool state = true;
for(int i = 0;i < edge;++i){
if(state != vec[i]){
if(state)
ranges.push_back(i);
else
ranges.push_back(i - 1);
state = !state;
}
}
if(!state)
ranges.push_back(edge - 1);
assert(!ranges.empty());
assert((ranges.size() & 1) == 0);
//printVec(ranges); //show the ranges cannot be generated
}
bool canGet(int min, int max)
{
static std::vector<int> ranges;
assert(min <= max);
if(ranges.empty())
prepare(ranges);
//fast check
if(min < 300)
return false;
if(min > ranges.back())
return true;
//find index of min
std::vector<int>::const_iterator wh = std::lower_bound(ranges.begin(), ranges.end(), min);
if(wh != ranges.end() && *wh == min)
return false;
int mi = wh - ranges.begin();
//find index of max
wh = std::lower_bound(ranges.begin(), ranges.end(), max);
if(wh != ranges.end() && *wh == max)
return false;
int ma = wh - ranges.begin();
assert(mi <= ma);
return (ma == mi && (mi & 1) == 0);
}
After prepare(), the invalid ranges are stored in vector 'ranges', the left work is to search min and max in 'ranges' and determine whether [min, max] contains invalid ranges.
Here is the test cases:
int main()
{
std::cout<<canGet(1871, 1871)<<"\n";
std::cout<<canGet(1899, 1899)<<"\n";
std::cout<<canGet(1799, 1870)<<"\n";
std::cout<<canGet(1800, 1870)<<"\n";
std::cout<<canGet(1800, 1871)<<"\n";
std::cout<<canGet(1872, 1898)<<"\n";
}
Finally I worked out it! It can pass all the test cases before! Here is the code:
static void nextIdx(const std::vector<int> & r1,
const std::vector<int> & r2,
const std::vector<int> & idx1,
const std::vector<int> & idx2,
int & i,
int & j,
int min_i,
int min_j)
{
if(j > 0){
int rr = r1[i] + r2[j];
for(int ii = min_i;ii < int(r1.size());++ii){
int jj = idx1[ii] + 1;
if(jj < j && rr > r1[ii] + r2[jj]){
i = ii;
j = jj;
rr = r1[i] + r2[j];
}
if(!jj)
break;
}
}
if(i > 0){
int rr = r1[i] + r2[j];
for(int jj = min_j;jj < int(r2.size());++jj){
int ii = idx2[jj] + 1;
if(ii < i && rr > r1[ii] + r2[jj]){
i = ii;
j = jj;
rr = r1[i] + r2[j];
}
if(!ii)
break;
}
}
}
//find k-th min in O(N)
int kthMin(const std::vector<int> & r1, const std::vector<int> & r2, int k)
{
assert(1 <= k && k <= int(r1.size() * r2.size()));
assert(!r1.empty() && !r2.empty());
std::vector<int> idx1(r1.size(), -1);
std::vector<int> idx2(r2.size(), -1);
int ret;
for(int i = 0, j = 0, n = 1;i < int(r1.size()) && j < int(r2.size());++n){
ret = r1[i] + r2[j];
if(n == k)
break;
idx1[i] = j;
idx2[j] = i;
if(i == r1.size() - 1){
assert(j < int(r2.size()) - 1);
i = idx2[++j] + 1;
if(i > 0)
nextIdx(r1, r2, idx1, idx2, i, j, r1.size(), j + 1);
}else if(j == r2.size() - 1){
assert(i < int(r1.size()) - 1);
j = idx1[++i] + 1;
if(j > 0)
nextIdx(r1, r2, idx1, idx2, i, j, i + 1, r2.size());
}else if(r1[i + 1] < r2[j + 1]){
int jj = j;
j = idx1[++i] + 1;
nextIdx(r1, r2, idx1, idx2, i, j, i + 1, jj + 1);
}else{
int ii = i;
i = idx2[++j] + 1;
nextIdx(r1, r2, idx1, idx2, i, j, ii + 1, j + 1);
}
}
return ret;
}
And with the all test cases:
//O(N * N)
int kthMinSlow(const std::vector<int> & r1, const std::vector<int> & r2, int k)
{
assert(1 <= k && k <= int(r1.size() * r2.size()));
std::vector<int> v;
for(int i = 0;i < k && i < int(r1.size());++i)
for(int j = 0;j < k && j < int(r2.size());++j)
v.push_back(r1[i] + r2[j]);
std::sort(v.begin(), v.end());
assert(int(v.size()) >= k);
return v[k - 1];
}
void test(const int v1[], const int v2[], int N)
{
assert(N > 0);
std::vector<int> r1(v1, v1 + N);
std::vector<int> r2(v2, v2 + N);
//test
std::vector<int> t1;
for(int k = 1;k <= int(r1.size() * r2.size());++k){
t1.push_back(kthMinSlow(r1, r2, k));
//std::cout<<t1.back()<<", ";
}
//std::cout<<"\n";
std::vector<int> t2;
for(int k = 1;k <= int(r1.size() * r2.size());++k){
t2.push_back(kthMin(r1, r2, k));
//std::cout<<t2.back()<<", ";
}
//std::cout<<"\n";
if(t1 != t2)
std::cerr<<"test FAILED\n";
}
int main()
{
{
const int v1[] = {0, 1, 3, 5};
const int v2[] = {1, 2, 4, 7};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 2, 3,4,5,7,8,9,10,11};
const int v2[] = {1,20,30,40,50,60,70,80,90,100};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 30, 35};
const int v2[] = {5,6,50};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 6, 7, 9, 10, 14};
const int v2[] = {2, 3, 5, 8, 11, 16};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 2, 2, 2};
const int v2[] = {1, 2, 3, 4};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 3, 4, 10};
const int v2[] = {2, 3, 8, 9};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010};
const int v2[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 5, 6, 7, 8, 20, 21, 22};
const int v2[] = {1, 4, 5, 10, 15, 16, 17, 18};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {100,200,300,400};
const int v2[] = {1,2,3,4};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 2, 3};
const int v2[] = {1, 4, 7};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010};
const int v2[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {3,4,5,6,13,19};
const int v2[] = {1,2,5,9,10,11};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}
}
triangle type detection code:
#include <algorithm>
int triangleType(int a, int b, int c)
{
enum ERet{
scalene = 1,
isosceles = 2,
equilateral = 3,
error = 4
};
if(a <= 0 || b <= 0 || c <= 0)
return error;
if(a == b && a == c)
return equilateral;
//sort a >= b >= c
if(a < b)
std::swap(a, b);
if(a < c)
std::swap(a, c);
if(b < c)
std::swap(b, c);
if(a - b >= c)
return error;
if(a == b || b == c)
return isosceles;
return scalene;
}
The test code is
#include <iostream>
int main()
{
//genTests();
const int kTestCase[][4] = { //generated by genTests()
{-1, -1, -1, 4},
{-1, -1, 0, 4},
{-1, -1, 1, 4},
{-1, -1, 2, 4},
{-1, -1, 3, 4},
{-1, -1, 4, 4},
{-1, 0, -1, 4},
{-1, 0, 0, 4},
{-1, 0, 1, 4},
{-1, 0, 2, 4},
{-1, 0, 3, 4},
{-1, 0, 4, 4},
{-1, 1, -1, 4},
{-1, 1, 0, 4},
{-1, 1, 1, 4},
{-1, 1, 2, 4},
{-1, 1, 3, 4},
{-1, 1, 4, 4},
{-1, 2, -1, 4},
{-1, 2, 0, 4},
{-1, 2, 1, 4},
{-1, 2, 2, 4},
{-1, 2, 3, 4},
{-1, 2, 4, 4},
{-1, 3, -1, 4},
{-1, 3, 0, 4},
{-1, 3, 1, 4},
{-1, 3, 2, 4},
{-1, 3, 3, 4},
{-1, 3, 4, 4},
{-1, 4, -1, 4},
{-1, 4, 0, 4},
{-1, 4, 1, 4},
{-1, 4, 2, 4},
{-1, 4, 3, 4},
{-1, 4, 4, 4},
{0, -1, -1, 4},
{0, -1, 0, 4},
{0, -1, 1, 4},
{0, -1, 2, 4},
{0, -1, 3, 4},
{0, -1, 4, 4},
{0, 0, -1, 4},
{0, 0, 0, 4},
{0, 0, 1, 4},
{0, 0, 2, 4},
{0, 0, 3, 4},
{0, 0, 4, 4},
{0, 1, -1, 4},
{0, 1, 0, 4},
{0, 1, 1, 4},
{0, 1, 2, 4},
{0, 1, 3, 4},
{0, 1, 4, 4},
{0, 2, -1, 4},
{0, 2, 0, 4},
{0, 2, 1, 4},
{0, 2, 2, 4},
{0, 2, 3, 4},
{0, 2, 4, 4},
{0, 3, -1, 4},
{0, 3, 0, 4},
{0, 3, 1, 4},
{0, 3, 2, 4},
{0, 3, 3, 4},
{0, 3, 4, 4},
{0, 4, -1, 4},
{0, 4, 0, 4},
{0, 4, 1, 4},
{0, 4, 2, 4},
{0, 4, 3, 4},
{0, 4, 4, 4},
{1, -1, -1, 4},
{1, -1, 0, 4},
{1, -1, 1, 4},
{1, -1, 2, 4},
{1, -1, 3, 4},
{1, -1, 4, 4},
{1, 0, -1, 4},
{1, 0, 0, 4},
{1, 0, 1, 4},
{1, 0, 2, 4},
{1, 0, 3, 4},
{1, 0, 4, 4},
{1, 1, -1, 4},
{1, 1, 0, 4},
{1, 1, 1, 3},
{1, 1, 2, 4},
{1, 1, 3, 4},
{1, 1, 4, 4},
{1, 2, -1, 4},
{1, 2, 0, 4},
{1, 2, 1, 4},
{1, 2, 2, 2},
{1, 2, 3, 4},
{1, 2, 4, 4},
{1, 3, -1, 4},
{1, 3, 0, 4},
{1, 3, 1, 4},
{1, 3, 2, 4},
{1, 3, 3, 2},
{1, 3, 4, 4},
{1, 4, -1, 4},
{1, 4, 0, 4},
{1, 4, 1, 4},
{1, 4, 2, 4},
{1, 4, 3, 4},
{1, 4, 4, 2},
{2, -1, -1, 4},
{2, -1, 0, 4},
{2, -1, 1, 4},
{2, -1, 2, 4},
{2, -1, 3, 4},
{2, -1, 4, 4},
{2, 0, -1, 4},
{2, 0, 0, 4},
{2, 0, 1, 4},
{2, 0, 2, 4},
{2, 0, 3, 4},
{2, 0, 4, 4},
{2, 1, -1, 4},
{2, 1, 0, 4},
{2, 1, 1, 4},
{2, 1, 2, 2},
{2, 1, 3, 4},
{2, 1, 4, 4},
{2, 2, -1, 4},
{2, 2, 0, 4},
{2, 2, 1, 2},
{2, 2, 2, 3},
{2, 2, 3, 2},
{2, 2, 4, 4},
{2, 3, -1, 4},
{2, 3, 0, 4},
{2, 3, 1, 4},
{2, 3, 2, 2},
{2, 3, 3, 2},
{2, 3, 4, 1},
{2, 4, -1, 4},
{2, 4, 0, 4},
{2, 4, 1, 4},
{2, 4, 2, 4},
{2, 4, 3, 1},
{2, 4, 4, 2},
{3, -1, -1, 4},
{3, -1, 0, 4},
{3, -1, 1, 4},
{3, -1, 2, 4},
{3, -1, 3, 4},
{3, -1, 4, 4},
{3, 0, -1, 4},
{3, 0, 0, 4},
{3, 0, 1, 4},
{3, 0, 2, 4},
{3, 0, 3, 4},
{3, 0, 4, 4},
{3, 1, -1, 4},
{3, 1, 0, 4},
{3, 1, 1, 4},
{3, 1, 2, 4},
{3, 1, 3, 2},
{3, 1, 4, 4},
{3, 2, -1, 4},
{3, 2, 0, 4},
{3, 2, 1, 4},
{3, 2, 2, 2},
{3, 2, 3, 2},
{3, 2, 4, 1},
{3, 3, -1, 4},
{3, 3, 0, 4},
{3, 3, 1, 2},
{3, 3, 2, 2},
{3, 3, 3, 3},
{3, 3, 4, 2},
{3, 4, -1, 4},
{3, 4, 0, 4},
{3, 4, 1, 4},
{3, 4, 2, 1},
{3, 4, 3, 2},
{3, 4, 4, 2},
{4, -1, -1, 4},
{4, -1, 0, 4},
{4, -1, 1, 4},
{4, -1, 2, 4},
{4, -1, 3, 4},
{4, -1, 4, 4},
{4, 0, -1, 4},
{4, 0, 0, 4},
{4, 0, 1, 4},
{4, 0, 2, 4},
{4, 0, 3, 4},
{4, 0, 4, 4},
{4, 1, -1, 4},
{4, 1, 0, 4},
{4, 1, 1, 4},
{4, 1, 2, 4},
{4, 1, 3, 4},
{4, 1, 4, 2},
{4, 2, -1, 4},
{4, 2, 0, 4},
{4, 2, 1, 4},
{4, 2, 2, 4},
{4, 2, 3, 1},
{4, 2, 4, 2},
{4, 3, -1, 4},
{4, 3, 0, 4},
{4, 3, 1, 4},
{4, 3, 2, 1},
{4, 3, 3, 2},
{4, 3, 4, 2},
{4, 4, -1, 4},
{4, 4, 0, 4},
{4, 4, 1, 2},
{4, 4, 2, 2},
{4, 4, 3, 2},
{4, 4, 4, 3},
{0x7ffffffd, 0x7ffffffd, 0x7ffffffd, 3},
{0x7ffffffd, 0x7ffffffd, 0x7ffffffe, 2},
{0x7ffffffd, 0x7ffffffd, 0x7fffffff, 2},
{0x7ffffffd, 0x7ffffffd, 0x80000000, 4},
{0x7ffffffd, 0x7ffffffe, 0x7ffffffd, 2},
{0x7ffffffd, 0x7ffffffe, 0x7ffffffe, 2},
{0x7ffffffd, 0x7ffffffe, 0x7fffffff, 1},
{0x7ffffffd, 0x7ffffffe, 0x80000000, 4},
{0x7ffffffd, 0x7fffffff, 0x7ffffffd, 2},
{0x7ffffffd, 0x7fffffff, 0x7ffffffe, 1},
{0x7ffffffd, 0x7fffffff, 0x7fffffff, 2},
{0x7ffffffd, 0x7fffffff, 0x80000000, 4},
{0x7ffffffd, 0x80000000, 0x7ffffffd, 4},
{0x7ffffffd, 0x80000000, 0x7ffffffe, 4},
{0x7ffffffd, 0x80000000, 0x7fffffff, 4},
{0x7ffffffd, 0x80000000, 0x80000000, 4},
{0x7ffffffe, 0x7ffffffd, 0x7ffffffd, 2},
{0x7ffffffe, 0x7ffffffd, 0x7ffffffe, 2},
{0x7ffffffe, 0x7ffffffd, 0x7fffffff, 1},
{0x7ffffffe, 0x7ffffffd, 0x80000000, 4},
{0x7ffffffe, 0x7ffffffe, 0x7ffffffd, 2},
{0x7ffffffe, 0x7ffffffe, 0x7ffffffe, 3},
{0x7ffffffe, 0x7ffffffe, 0x7fffffff, 2},
{0x7ffffffe, 0x7ffffffe, 0x80000000, 4},
{0x7ffffffe, 0x7fffffff, 0x7ffffffd, 1},
{0x7ffffffe, 0x7fffffff, 0x7ffffffe, 2},
{0x7ffffffe, 0x7fffffff, 0x7fffffff, 2},
{0x7ffffffe, 0x7fffffff, 0x80000000, 4},
{0x7ffffffe, 0x80000000, 0x7ffffffd, 4},
{0x7ffffffe, 0x80000000, 0x7ffffffe, 4},
{0x7ffffffe, 0x80000000, 0x7fffffff, 4},
{0x7ffffffe, 0x80000000, 0x80000000, 4},
{0x7fffffff, 0x7ffffffd, 0x7ffffffd, 2},
{0x7fffffff, 0x7ffffffd, 0x7ffffffe, 1},
{0x7fffffff, 0x7ffffffd, 0x7fffffff, 2},
{0x7fffffff, 0x7ffffffd, 0x80000000, 4},
{0x7fffffff, 0x7ffffffe, 0x7ffffffd, 1},
{0x7fffffff, 0x7ffffffe, 0x7ffffffe, 2},
{0x7fffffff, 0x7ffffffe, 0x7fffffff, 2},
{0x7fffffff, 0x7ffffffe, 0x80000000, 4},
{0x7fffffff, 0x7fffffff, 0x7ffffffd, 2},
{0x7fffffff, 0x7fffffff, 0x7ffffffe, 2},
{0x7fffffff, 0x7fffffff, 0x7fffffff, 3},
{0x7fffffff, 0x7fffffff, 0x80000000, 4},
{0x7fffffff, 0x80000000, 0x7ffffffd, 4},
{0x7fffffff, 0x80000000, 0x7ffffffe, 4},
{0x7fffffff, 0x80000000, 0x7fffffff, 4},
{0x7fffffff, 0x80000000, 0x80000000, 4},
{0x80000000, 0x7ffffffd, 0x7ffffffd, 4},
{0x80000000, 0x7ffffffd, 0x7ffffffe, 4},
{0x80000000, 0x7ffffffd, 0x7fffffff, 4},
{0x80000000, 0x7ffffffd, 0x80000000, 4},
{0x80000000, 0x7ffffffe, 0x7ffffffd, 4},
{0x80000000, 0x7ffffffe, 0x7ffffffe, 4},
{0x80000000, 0x7ffffffe, 0x7fffffff, 4},
{0x80000000, 0x7ffffffe, 0x80000000, 4},
{0x80000000, 0x7fffffff, 0x7ffffffd, 4},
{0x80000000, 0x7fffffff, 0x7ffffffe, 4},
{0x80000000, 0x7fffffff, 0x7fffffff, 4},
{0x80000000, 0x7fffffff, 0x80000000, 4},
{0x80000000, 0x80000000, 0x7ffffffd, 4},
{0x80000000, 0x80000000, 0x7ffffffe, 4},
{0x80000000, 0x80000000, 0x7fffffff, 4},
{0x80000000, 0x80000000, 0x80000000, 4}
};
for(int i = 0;i < sizeof kTestCase / sizeof kTestCase[0];++i)
if(kTestCase[i][3] != triangleType(kTestCase[i][0], kTestCase[i][1], kTestCase[i][2]))
std::cerr<<"triangle ["<<kTestCase[i][0]<<", "<<kTestCase[i][1]
<<", "<<kTestCase[i][2]<<"] is not "<<kTestCase[i][3]<<"\n";
}
All the test cases is generated by the following code
//generate test cases
void genTests()
{
//test case
for(int a = -1;a <= 4; ++a)
for(int b = -1;b <= 4; ++b)
for(int c = -1;c <= 4; ++c){
std::cout<<"{"<<a<<", "<<b<<", "<<c<<", "
<<triangleType(a, b, c)<<"},\n";
}
const int kMax = 0x7FFFFFFF;
for(int a = -2;a <= 1; ++a)
for(int b = -2;b <= 1; ++b)
for(int c = -2;c <= 1; ++c){
std::cout<<std::hex<<"{0x"<<(a + kMax)<<", 0x"<<(b + kMax)<<", 0x"<<(c + kMax)<<", "
<<triangleType(a + kMax, b + kMax, c + kMax)<<"},\n";
}
}
Parse the expression to generate a binary tree, which has values as leaf, then eval the tree:
#include <list>
#include <iostream>
#include <cassert>
class CNode
{
CNode * parent_;
CNode * left_;
CNode * right_;
double val_;
char type_;
public:
explicit CNode(char t):parent_(NULL),left_(NULL),right_(NULL),val_(0),type_(t){}
explicit CNode(double v):parent_(NULL),left_(NULL),right_(NULL),val_(v),type_(0){}
bool hasParent() const{return (NULL != parent_);}
CNode * parent() const{return parent_;}
void setRight(CNode & n){
right_ = &n;
n.parent_ = this;
}
void setLeft(CNode & n){
left_ = &n;
n.parent_ = this;
}
bool isNumber() const{return (0 == type_);}
bool isAddMinus() const{return ('+' == type_ || '-' == type_);}
bool isMulDiv() const{return ('*' == type_ || '/' == type_);}
double calc() const{
if(isNumber())
return val_;
assert(left_ && right_);
switch(type_){
case '+':return (left_->calc() + right_->calc());
case '-':return (left_->calc() - right_->calc());
case '*':return (left_->calc() * right_->calc());
case '/':return (left_->calc() / right_->calc());
default:;
}
assert(false);
return 0;
}
};
typedef std::list<CNode> __Nodes;
const char * parseToken(const char * p, __Nodes & nodes)
{
assert(p);
if('+' == *p || '-' == *p || '*' == *p || '/' == *p){
nodes.push_back(CNode(*p++));
return p;
}else if('0' <= *p && *p <= '9'){
double v = 0;
do{
v = v * 10 + *p - '0';
++p;
}while('0' <= *p && *p <= '9');
nodes.push_back(CNode(v));
return p;
}
return NULL;
}
CNode & findHead(CNode & n)
{
CNode * p = &n;
for(;p->hasParent();p = p->parent());
return *p;
}
const CNode & findHead(const CNode & n)
{
const CNode * p = &n;
for(;p->hasParent();p = p->parent());
return *p;
}
CNode & findSubHead(CNode & n)
{
CNode * p = &n;
while(p->hasParent()){
CNode * pp = p->parent();
if(!pp->isMulDiv())
break;
p = pp;
}
return *p;
}
void adjustNodes(CNode & last, CNode & cur)
{
if(last.isNumber()){
if(cur.isAddMinus()){
cur.setLeft(findHead(last));
return;
}else if(cur.isMulDiv()){
CNode & h = findSubHead(last);
CNode * p = h.parent();
if(p)
p->setRight(cur);
cur.setLeft(h);
return;
}
}else{
if(cur.isNumber()){
last.setRight(cur);
return;
}
}
assert(false);
}
bool buildTree(__Nodes & nodes)
{
if(nodes.size() < 2)
return true;
__Nodes::reverse_iterator i = nodes.rbegin();
CNode & cur = *i++;
CNode & last = *i;
if(cur.isNumber() == last.isNumber())
return false;
adjustNodes(last, cur);
return true;
}
bool parseExpr(const char * expr, __Nodes & nodes)
{
assert(expr);
for(const char * p = expr;*p;){
if(NULL == (p = parseToken(p, nodes)))
return false;
if(!buildTree(nodes))
return false;
}
if(nodes.empty() || !nodes.back().isNumber())
return false;
return true;
}
double calcTree(const __Nodes & nodes)
{
if(nodes.empty())
return 0;
const CNode & h = findHead(nodes.front());
return h.calc();
}
double eval(const char * expr)
{
__Nodes nodes;
if(parseExpr(expr, nodes))
return calcTree(nodes);
return 0; //error format expr
}
int main()
{
std::cout<<eval("2+5/2")<<"\n"; //4.5
std::cout<<eval("12*2+5/2-3")<<"\n";//23.5
}
2.
#include <cstdio>
#include <cassert>
#include <cstring>
const int TILE_CNT = 7;
void sortTiles(char * tile)
{
char ret[TILE_CNT];
int a = 0, b = TILE_CNT;
for(int i = 0;i < TILE_CNT;++i)
if(' ' == tile[i])
ret[--b] = tile[i];
else
ret[a++] = tile[i];
memcpy(tile, ret, TILE_CNT);
}
bool readWord(FILE * fp, char word[TILE_CNT])
{
assert(fp);
for(int i = 0;i < TILE_CNT;++i){
if(feof(fp))
word[i] = 0;
else{
word[i] = fgetc(fp);
if('\n' == word[i])
word[i] = 0;
}
if(!word[i])
return true;
}
if(feof(fp) || '\n' == fgetc(fp))
return true;
while(!feof(fp) && '\n' != fgetc(fp));
return false;
}
void toLowercase(char word[TILE_CNT])
{
for(int i = 0;i < TILE_CNT;++i)
if('A' <= word[i] && word[i] <= 'Z')
word[i] += 'a' - 'A';
}
bool useTile(char tiles[TILE_CNT], char c)
{
for(int i = 0;i < TILE_CNT;++i)
if(' ' == tiles[i] || c == tiles[i]){
tiles[i] = 0;
return true;
}
return false;
}
bool testWord(const char word[TILE_CNT], const char tiles[TILE_CNT])
{
char w[TILE_CNT];
memcpy(w, word, TILE_CNT);
toLowercase(w);
char tmp[TILE_CNT];
memcpy(tmp, tiles, TILE_CNT);
for(int i = 0;i < TILE_CNT;++i)
if(!useTile(tmp, w[i]))
return false;
return true;
}
void printWord(const char word[TILE_CNT])
{
for(int i = 0;i < TILE_CNT;++i){
if(!word[i])
break;
printf("%c", word[i]);
}
printf("\n");
}
void findWords(const char * fname, const char tiles[TILE_CNT])
{
FILE * fp = fopen(fname, "r");
if(!fp)
return; //error
char tile[TILE_CNT];
memcpy(tile, tiles, TILE_CNT);
sortTiles(tile);
for(char word[TILE_CNT];!feof(fp);){
if(!readWord(fp, word))
continue;
if(testWord(word, tile))
printWord(word);
}
}
int main()
{
findWords("input.txt", "ab cdef");
}
My solution is totally brute force, so it is not efficient, but definitely right, compared to other "smarter" solutions.
For each permutation of the array, I BFS all possible permutations within one transform (swap blocks of the array). Once the final permutation (ascending order) is reached, the problem is solved.
- DoZerg March 30, 2015