Chris
BAN USERSWE
 0of 0 votes
AnswersA new species has been discovered and we are trying to understand their form of communication. So, we start by identifying their alphabet. Tough Mr. Brown managed to steal a vocabulary that has words in it in ascending order and a team already identified the letters. So, we have now ordered words as sequences of numbers, print every letter once in ascending order.
 Chris in United States
[3,2]
[4,3,2]
[4,1,1]
[1, 2]
[1, 1]
alphabet: [3, 4, 2, 1] Report Duplicate  Flag  PURGE
Software Engineer Data Structures
what are the id's used for? is it desired that they are sequential (e.g. used for keys) or rather randomly distributed? How much of the range can we leave unused without overusing the range? How many keys per second? Bursts? Is a conflict acceptable or must the keys be truely unique for ever?
An approach I could imagine works is, if we have a slower transactional storage, where we can store block assignments to servers. A server picks such a block and generates sequential numbers. If he runs out of numbers (obviously k cycles before) in his blocks, he picks the next block. This has the advantage that if a server goes down, we use max blocksize numbers, usually such a transactional storage is around in the infrastructure  they are comparably slow, reliable for little data. Alternatively, the block assignment can be implemented on this same machines that delivers the key using a protocol (such as PAXOS) that allows machine failures as long as a majority of machines stays online.
I would as well try to persist the current block counter, so in the worst case, it can be read and a safe offset can be added that will waste a lot of numbers but since it should never occure it's an acceptable safety mechanism.
@ kanukadze
it looks ok to me. I don't get your constants 1 << 21 (roughly 16 MB memory, can't you use more?) The hash function has no upper limit, so it creates you an int 2^32 or 2^64 (don't kow c# that well anymore), anyway best case is 32  6 bits: 2^26 is > 2^21 so you will sooner or later access elements that aren't there... a remainder % would help although it messes up the hash distribution a bit, better is a hash function that takes the range into account and perfectly distributes in this range...
what are actually this ";6" ";21" close to the shift operators?
the idea was certainly right, I find it elegant to invert the array and work with OR before inverting the whole thing. What interview was it? was it just one or several?
how much memory do we have? how many words?
this quesion wants optimal memory usage, since we accept false negatives, we should minimize the probability of false negatives by maximizing a hash value and picking a "good" hash function. Hashtables are not optimal for such a problem due to the overhead not required in this problem (e.g. for a given hashvalue we just need a bit, conflicts don't matter, no bucket lists or open addressing required, filling all possible values is just a huge overhead  not in terms of bigO but practically). Use a bitarray and index it with a hash value. Scale the size of the array to the memory available to minimize probability of false negatives.
Preparation step:
1) create an array of max size n with int's (n ints with b bits)
2) fill the table with 0xffffffff (depending on int size)
3) for each word compute a hash: 0<= hash < n*b and unmaks the bit hash%b of array[hash/b]
Query:
compute hash for word
check if bit hash%b of array[has/b] is set. If set word is for sure not in there
If not set word is probably in there (or an other word colliding with the same hashvalue is in there...)
/* Interpretation of the question: Given an Nary tree, find
the longest sequence (path) in it.
Longest sequence: Longest sequence of vertices without
using a vertice twice by following the edges of the tree.
That is the longest path from one leave to an other leave or,
if no two leaves exist the path from the leave to the root.
Solution idea:
1) brute force: do from every Vertex a bfs to any other vertex
time: O(V*V)
disadvantage besideds time complexity: does not work well on
usual tree structure, so I had to construct a graph first.
2) improved brute force: just do it from every leave
(vertex with degree 1): minor improvement
3) Use tree structure and do it top down in O(V):
start with root
do a postorder traversal, ask each child for the maxBranchPath
and the maxDiametrePath
maxBranchPath is the longest path from any leave of the tree
rooted at a specific node to that specific node, not includinig
that node
maxDiametrePath is the longest path from any leave of the
tree rooted at a specific node to either any other leave of that
node or to that node (latter is equal to the maxBranchPath)
but not including that node
Keep track of the two largest maxBranchPath from the children
if the length of the sum of this two branch paths + 1 >
maxDiameterePath a new maxDiametere is found.
Implementation for simplicity with raw pointers
*/
#include <vector>
#include <utility>
#include <iostream>
class NNode
{
public:
using Path = std::vector<const NNode*>;
private:
int value_;
std::vector<NNode*> children_;
// maxDiametrePath and maxBranchPath are out parameteres
void getMaxDiametreMaxBranch(Path& maxDiametrePath, Path& maxBranchPath) const
{
maxDiametrePath.clear();
maxBranchPath.clear();
Path maxBranchPath2;
for(auto c : children_)
{
Path diametrePath, branchPath;
c>getMaxDiametreMaxBranch(diametrePath, branchPath);
if(diametrePath.size() > maxDiametrePath.size())
{
maxDiametrePath = std::move(diametrePath);
}
if(branchPath.size() > maxBranchPath.size())
{
maxBranchPath2 = std::move(maxBranchPath);
maxBranchPath = std::move(branchPath);
}
else if(branchPath.size() > maxBranchPath2.size())
{
maxBranchPath2 = std::move(branchPath);
}
}
if(maxDiametrePath.size() == 0)
{
maxDiametrePath.push_back(this);
}
maxBranchPath.push_back(this);
int newDiametrePathSize = maxBranchPath.size() + maxBranchPath2.size();
if(newDiametrePathSize > maxDiametrePath.size())
{
maxDiametrePath.resize(newDiametrePathSize);
std::copy(maxBranchPath.begin(), maxBranchPath.end(), maxDiametrePath.begin());
std::copy(maxBranchPath2.rbegin(), maxBranchPath2.rend(),
maxDiametrePath.begin() + maxBranchPath.size());
}
}
public:
NNode(int value) : value_(value) { }
Path getMaxDiametrePath() const
{
Path maxPath, maxBranch;
getMaxDiametreMaxBranch(maxPath, maxBranch);
return maxPath;
}
void addChild(NNode* child)
{
children_.push_back(child);
}
int getValue() const { return value_; }
};
int main()
{
NNode n1(1);
NNode n2(2);
NNode n3(3);
NNode n4(4);
NNode n5(5);
NNode n6(6);
NNode n7(7);
NNode n8(8);
NNode n9(9);
NNode n10(10);
NNode n11(11);
NNode n12(12);
NNode n13(13);
NNode n14(14);
NNode n15(15);
n14.addChild(&n15);
n11.addChild(&n14);
n9.addChild(&n13);
n7.addChild(&n11);
n7.addChild(&n12);
n7.addChild(&n10);
n7.addChild(&n9);
n6.addChild(&n8);
n2.addChild(&n6);
n2.addChild(&n7);
n1.addChild(&n2);
n1.addChild(&n3);
n1.addChild(&n4);
n1.addChild(&n5);
std::cout << "max diametre path from n1" << std::endl;
for(auto n : n1.getMaxDiametrePath())
std::cout << n>getValue() << " ";
std::cout << std::endl << std::endl << "max diametre path from n6" << std::endl;
for(auto n : n6.getMaxDiametrePath())
std::cout << n>getValue() << " ";
std::cout << std::endl << std::endl << "max diametre path from n5" << std::endl;
for(auto n : n5.getMaxDiametrePath())
std::cout << n>getValue() << " ";
std::cout << std::endl;
return 0;
}
/* output:
max diametre path from n1
15 14 11 7 2 6 8
max diametre path from n6
8 6
max diametre path from n5
5
*/

Chris
October 18, 2016 what is a subnet? Is he refering to the class a,b,c,d,(e) networks?
If so, you can determine the class of the network by the ip address.
This would reduce data, since you are not required to count the hosts within the network
(there are roughly ~2.1 Mio class a+b+c+d networks). If he want to identify potential
subnets or even hosts (belongig to a botnet?) inside the abcd networks he will not get
what he wants by spliting on 8.bit boundaries but we need to guess a subnet everywhere.
for a given IP, ignoring class a,b,c,d, there are *theoretically* 32 subnets (from single machine
to whole IP v4 range)
To simplify I would create an integer, lets call it subnetid with the subnetsize and
the remaining subnet id:
1st bit set: remaining 32 bit contain the ip
1st bit 0, 2nd bit 1: remaining 31 bits will contain the subnet (actually that does not exist in practice)
1st, 2nd 0, 3rd 1: remaining 30 bits will contain the subnet id...
With 33 bits all potential subnets are covered, each ip will create 32 such subnetids.
To actually count, I would create a self balancing tree in memory to count frequencies
by above subnetid. If memory gets full, write id:frequency into a file, ordered by id
(thus no HT, whereas a HT could be used but before writing I have to sort it inplace
(no more memory) which is not a standard HT use case ... it could be done by a custom
HT that uses open addressing... which is prefered over a tree)
Continue untill all has been processed and we have m sorted files. Merge them by key.
Traverse final file to find 4 highest values.
Can be implemented using mapreduce to scale to many machines.
Data can be appended if more logfiles come without the need to reprocess prior .processed
data.
"group together dishes with common ingredients" is ambiguous and the sample doesn't really help. Following interpretations are possible:
1) For every ingredient list common dishes, e.g. two dishes that share two ingredients get listed twice
2) For every ingredient list common dished, but avoid listing a pair twice
3) For the latter one, we could as well prefer to list the dishes which share most ingredients first
1) is easy: create a hashtable with ingredient as key and dishes as list. then out put this lists if they are bigger than 1
2) I would approach as 1) but then I could keep a matrix which stores the already output pairs (for an ingredient that is used in k dishes this is (k1)! pairs) making the whole thing exponential in time and quadratic in space (matrix), which is clearly not acceptable
I'm interested in approaches...I can't see it.
/*
solution idea (inspired by merge sort)
1) make sure both, arrival and departure times are sorted. Arrival
times are already, departure time aren't.
Then think of the arrivals and departures as of
queues and look at their first elements. The smaller one wins, if equal,
the departure wins.
if the winner is departure, a gate is freed (assume, it can go below 0)
if the winner is arrival, a gate is used
sort departure time ascending()
2) assume the arrival and departure time can be converted into some
form that allows easy comparsion of > (string representation as given
won't do it). Leave this "parsing step out" but do something like
houre*60+minute.
time complexity: O(n*lg(n)) assuming #departures and #arrivals are equal
*/
#include <vector>
#include <algorithm>
int GetGates(std::vector<int>& arrivals, std::vector<int>& departures)
{
std::sort(departures.begin(), departures.end());
int n=arrivals.size();
if(n != departures.size()) throw "#arrivals should equal #departures";
if(arrivals[n1] >= departures[n1]) throw "last departure must be after last arrival";
int a=0, d=0, mg=0, cg=0; // mg: max # gates, cg: current # gates
while(a<n)
{
if(arrivals[a] < departures[d])
{
cg++;
a++;
}
else
{
cg=std::max(cg1,0);
d++;
}
mg=std::max(cg,mg);
}
return mg;
}

Chris
September 13, 2016 /*
Given a string consisting only of digits, find the missing number.
For instance, given the string 596597598600601602
the missing number is 599. You may assume all the numbers are
positive integers and the sequence increases by one at each number
except the missing number. The numbers will have no more
than six digits and the string will have no more than
four hundred characters.
Your task is to write a function to find the missing number in the sequence.
If there should no missing number whatsoever, return a value of 1
/*
Solution:
consider sequences like 9101113 or 98100101102
just try the starting number and then try for the next+1 and next+2,
if more than one next+2 were found stop, etc...
relatively straight forward, considering the special cases
runtime: at most 6*n (which is not possible): anyway it is O(N)
space: O(1)
*/
#include <string>
#include <iostream>
using namespace std;
// gets the integer at position i with length m, returns it or 1, if none
int GetValue(const string& str, int i, int m)
{
if (i + m > str.length()) return 1;
int value = 0;
for (int j = 0; j < m; j++)
{
int c = str[i + j]  '0';
if (c < 0  c > 9) return 1;
value = value * 10 + c;
}
return value;
}
int FindMissingNumber(const string& str)
{
// note: it's easy to get rid of the logs but the code is just
// not understandable with all those counters
for (int m = 1; m <= 6; ++m)
{
int n = GetValue(str, 0, m);
if (n == 1) break;
int missingNo = 1;
bool fail = false;
for (int i = m; i != str.length(); i += 1 + log10l(n))
{
if ((missingNo == 1) &&
(GetValue(str, i, 1 + log10l(n + 2)) == n + 2))
{
missingNo = n + 1;
n+=2;
}
else if (GetValue(str, i, 1 + log10l(n + 1)) == n + 1)
{
n++;
}
else
{
fail = true;
break;
}
}
if (!fail) return missingNo;
}
return 1; // not found or no missing number
}
int main()
{
cout << "596597598600601602: " << FindMissingNumber("596597598600601602") << endl;
cout << "89101113: " << FindMissingNumber("89101113") << endl;
cout << "11111211311411511: " << FindMissingNumber("11111211311411511") << endl;
cout << "909192939495969798100101: " << FindMissingNumber("909192939495969798100101") << endl;
cout << "9899101102: " << FindMissingNumber("9899101102") << endl;
}

Chris
August 26, 2016 /*
1) all elements on the left must be <= than the element in the
middle after n such mirror operations.
2) Most perumtations that are possible are 2^(n/2), that is,
swap index 0 with n1, index 1 with n2, etc...
(independently if given mirror operation is performed outwards inwards)
3) Every element, except the middle one has two possible values,
it's value at index or it's value at mirrored index
Solution:
f[i] = min(a[i], a[n1i]) for 0<=i<n/2
e[i] = max(a[i], a[n1i]) for 0<=i<n/2
Iterate through the array 1 to n/21 and check if:
f[i]>=f[i1] AND e[i]>=e[i1]
If that succeeded and length of a is odd, only need to check
f[n/21] <= a[n/2] <= e[n/2+1] if that's true, its sortable,
obviously if array length is even, if above iteration succeeded with all checks
it is sortable.
Time complexity O(N)
Space complexicty O(1)
*/
#include <iostream>
#include <algorithm>
using namespace std;
// array with nelements
bool IsSortable(const int a[], int n)
{
for (int i = 1; i < n/2; ++i)
{
if (min(a[i], a[n  i  1]) < min(a[i  1], a[n  i]))
return false;
if (max(a[i], a[n  i  1]) > max(a[i  1], a[n  i]))
return false;
}
if (n & 1 == 1)
return min(a[n / 2  1], a[n / 2 + 1]) <= a[n / 2] &&
max(a[n / 2  1], a[n / 2 + 1]) >= a[n / 2];
return true;
}
int main()
{
int a1[]{ 1,2,3,4,5 };
cout << "a1: " << IsSortable(a1, sizeof(a1)/sizeof(int)) << endl;
int a2[]{ 5,4,3,2,1 };
cout << "a2: " << IsSortable(a2, sizeof(a2) / sizeof(int)) << endl;
int a3[]{ 1,2,6,3,4 };
cout << "a3: " << IsSortable(a3, sizeof(a3) / sizeof(int)) << endl;
int a4[]{ 4,2,1,2 };
cout << "a4: " << IsSortable(a4, sizeof(a4) / sizeof(int)) << endl;
int a5[]{ 9,8,7,6,5,4,3,2,1 };
cout << "a5: " << IsSortable(a5, sizeof(a5) / sizeof(int)) << endl;
int a6[]{ 9,8,7,6,5,4,5,2,1 };
cout << "a6: " << IsSortable(a6, sizeof(a6) / sizeof(int)) << endl;
}

Chris
August 25, 2016 /*
Linear Solution (O(N)):
 at start, let a be minimum of BST and b the maximum of BST
while(a <= b):
 If a+b > desired sum: decrease b to the next lower value
why: because if the smallest and the largest overshoot the desired sum,
every combination with the largest element will overshoot, so we can ignore
it in the future.
 If a+b < desired sum: increase a to the next higher value
why: because if the largest and the smallest will not reach the desired sum,
the smallest will not be of any help to ever reach the sum, so we can ignor
it in the future.
 If a+b = desired sum: return a,b
if loop terminates without having found anything, there is no pair that has
as sum the desired sum the "=" in the while loop assumes taking two times
the same node to build a sum is correct either.
O(N) because finding min and max takes O(lg(N)) if BST is balanced and O(N)
if it's a chain but finding aprox. Nk Predessors and k Successors takes O(N)
amortized. so it's O(N). It does not matter if BST is balanced or not.
Logarithmic solution (O(Lg(N))):
 Make a to be minimum of BST
 Make b to be maximum of BST
while (a <= b)
if a = b: return a,b
if a+b > desired sum: find bigest b that satisfies b <= desired sum  a
if a+b < desired sum: find smallest a that that satisfies a >= desired sum  b
reasoning is the same as with linear solution, just that finding those limitting values is
faster if we use binary search in a supposedly balanced BST .
The question here is how many tries are required until it converges or knows it doesn't.
I assume it is logarithmic, but I haven't managed to come up with a prove or disprove in
the time taken for this problem.
*/
#include <utility>
#include <iostream>
using namespace std;
class Node
{
private:
int _value;
Node* _left;
Node* _right;
Node* _parent = nullptr;
public:
Node(int v, Node* left, Node* right)
: _value{ v }, _left{ left }, _right{ right }
{
if (left != nullptr) left>_parent = this;
if (right != nullptr) right>_parent = this;
}
Node(int v) : Node(v, nullptr, nullptr) {}
int get_Value() const { return _value; }
pair<Node*, Node*> FindSumLinear(int sum)
{
Node *a = Min();
Node *b = Max();
while ((a != nullptr) && (b != nullptr) &&
(a>_value <= b>_value))
{
int s = a>_value + b>_value;
if (s > sum) b = b>Predecessor();
else if (s < sum) a = a>Successor();
else return pair<Node*, Node*>(a, b);
}
return pair<Node*, Node*>(nullptr, nullptr);
}
pair<Node*, Node*> FindSumLogarithmic(int sum)
{
Node *a = Min();
Node *b = Max();
while ((a != nullptr) && (b != nullptr) &&
(a>_value <= b>_value))
{
int s = a>_value + b>_value;
if (s > sum)
{
int db = sum  a>_value;
b = BinarySearchAprox(db);
if (b>_value > db) b = b>Predecessor();
}
else if (s < sum)
{
int da = sum  b>_value;
a = BinarySearchAprox(da);
if (a>_value < da) a = a>Successor();
}
else
{
return pair<Node*, Node*>(a, b);
}
}
return pair<Node*, Node*>(nullptr, nullptr);
}
private:
// returns the min note of this subtree
Node * Min()
{
Node *c = this;
while (c>_left != nullptr) c = c>_left;
return c;
}
// returns the max node of this subtree
Node * Max()
{
Node *c = this;
while (c>_right != nullptr) c = c>_right;
return c;
}
// returns predecessor or null if none
Node *Predecessor()
{
Node *c = this;
if (_left != nullptr) return _left>Max();
while (c>_parent != nullptr && c>_parent>_left == c) c = c>_parent;
return c>_parent;
}
// resturns successor or null if none
Node *Successor()
{
Node *c = this;
if (_right != nullptr) return _right>Min();
while (c>_parent != nullptr && c>_parent>_right == c) c = c>_parent;
return c>_parent;
}
// the function returns either the node with it's value or if that value
// doesn't exist in the tree a node with it's next higher or next lower value
Node* BinarySearchAprox(int value)
{
Node *n = this;
while (true)
{
if (value > n>_value && n>_right != nullptr)
n = n>_right;
else if (value < n>_value && n>_left != nullptr)
n = n>_left;
else return n; // either a match or we just can't get any closer
}
}
};
int main()
{
const char* tree = "\n"\
" 8\n"\
" / \ \n"\
" 4 12\n"\
" / \\ \\\n"\
" 2 7 14\n"\
" / / \\\n"\
" 5 13 15\n";
Node n2 = Node(2);
Node n5 = Node(5);
Node n7 = Node(7, &n5, nullptr);
Node n4 = Node(4, &n2, &n7);
Node n13 = Node(13);
Node n15 = Node(15);
Node n14 = Node(14, &n13, &n15);
Node n12 = Node(12, nullptr, &n14);
Node root = Node(8, &n4, &n12);
cout << "tree: " << tree << endl << endl;
for (int i = 1; i < 32; ++i)
{
auto result = root.FindSumLinear(i);
auto result2 = root.FindSumLogarithmic(i);
cout << endl << "result for sum " << i << ": " << endl;
if (result.first == nullptr) cout << "LIN: no two nodes found that sum up to " << i << endl;
else cout << "LIN: " << i << " = " << result.first>get_Value() << " + " << result.second>get_Value() << endl;
if (result2.first == nullptr) cout << "LOG: no two nodes found that sum up to " << i << endl;
else cout << "LOG: " << i << " = " << result2.first>get_Value() << " + " << result2.second>get_Value() << endl;
}
}

Chris
August 24, 2016 /*
Solution approach:
 it looks like a DP problem which seems to work
 How ever, I found it easier to think of it as a parsing problem:
 match first word, then progress to the next one, start with the smallest word
 store in a list the wordindex or word length
 if we reach the end without being able to further match, obviously at some point
the matching was wrong, as long as we still have alternatives at some point, so
we go back one word and retry our luck, if that fails again, go back further
everytime, when coming back try with a longer word etc...
 We could think of it as a parser if it can't decide on the next temrinal which
production it is, so it does look ahead, here it does backtrack, which is the
passive version (try all possibilities and back track vs. try o find out be
looking ahead)
 Looking at it from a runtime perspective, one could argue, the natural language is
built to require little backtracking since if it accidentially finds a word that
is part of an other word as it progresses the possibility is getting very small
that it comes very far. Whereas in a language where all combintions of letters
lead to a valid word, this wouldn't be the case.
I find it a cool question!
*/
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <sstream>
using namespace std;
const size_t MAX_WORD_LENGTH = 80;
const char* SAMPLES[] = { "thisisavalidsentence", "thisisavalidsentencewhichrequiresautomaticbacktrack"};
const char* WORD_TABLE[] {"this", "is", "a", "valid", "sentence", "auto", "automatic",
"with", "sample", "backtrack", "which", "requires",
"of", "the", "back", "track", "require", "sau"}; //"sau is pig in german :)
// primitive and not performant, returns if [s, e) is a word
bool IsWord(const string& str, int s, int e)
{
string ss = str.substr(s, e  s);
for (auto w : WORD_TABLE)
if (ss.compare(w) == 0) return true;
return false;
}
// tries to find a word starting at s, with minimal length minl int the string str
// using IsWord function, returns the length of the found word which is the
// shortest matching word with length >= minl
int FindWord(const string& str, int s, int minl)
{
int maxl = min(str.length()  s + 1, MAX_WORD_LENGTH);
for (int l = minl; l < maxl; l++)
if (IsWord(str, s, s + l)) return l;
return 0;
}
// modifies the string str to contain spaces between words, throws exception
// (of type const char*) if failed to reconstruct whole string
void ReconstructSentence(string& str)
{
vector<int> wordl; // contains the found word lengths
int i = 0; // current position
int n = str.length();
int m = 1; // minimal word size to be matched
while (i < n)
{
int l = FindWord(str, i, m);
if (l > 0)
{ // found a word
wordl.push_back(l);
i += l;
m = 1;
}
else
{ // didn't find a word, need to backtrack
if (wordl.size() == 0) throw "can't find a solution";
m = wordl.back();
wordl.pop_back();
i = m; // back track word length in string
m++; // word needs to be longer
}
}
i = 0;
for (int l : wordl)
{
i += l;
str.insert(i, " ");
i++;
}
}
int main()
{
for (auto s : SAMPLES)
{
string str(s);
ReconstructSentence(str);
cout << "sample :" << s << endl << "is: " << str << endl << endl;
}
getchar();
return 0;
}

Chris
August 24, 2016 /*
Assumptions:
 two dimensional due to given coordinates
 move in any of the 8 directions possible, if the field is a "1" , 1,1, 1, 0, 1, 1
 from {0,0} to {n1, n1} to keeps things more conventional
 {0,0} and {n1, n1} are both 1
Example
{
{1, 0, 1, 1, 0, 0},
{0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 0, 1},
{1, 1, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 1, 1, 0, 1},
}
Solution:
 If we create a graph G=(V,E) where V are the coordinates (positions) in
the array marked with 1 and E are the edges between two adjecent
coordinates that are 1, we can use bread first search to find the
shortest path between any two vertices that are connected by edges.
 V and E do not need to be objects or form a graph in a classical
representation such as adjecent list or adjecent matrix, it is
created on the fly, coordinates being the vertices and adjecents being
the list of coordinates one can go from a certain coordinate.
 the BFS traversal tree is kept in a parent array with coordinates, where
each entry has an associated coordinate with it's parent from the
tree traversal.
*/
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <sstream>
using namespace std;
class MatrixShortestPath
{
struct Position
{
int x;
int y;
};
private:
vector<vector<bool>> _field;
int _n;
public:
MatrixShortestPath(vector<vector<bool>>&& field) : _field{field}, _n(field.size())
{
_field[0][0] = true;
for (int i = 0; i < _n; i++)
if (_field[i].size() != _n)
throw invalid_argument("field size");
_field[_n  1][_n  1] = true;
}
// creates an adjecents list with positions on the fly based on the values of
// the field array
vector<Position> GetAdjecents(Position pos)
{
static const int move[8][2]{ {1,1},{0,1},{1,1},{1,0},{1,0},{1,1},{0,1},{1,1} };
vector<Position> adj;
for (int i = 0; i < 8; i++)
{
Position np{ pos.x + move[i][0], pos.y + move[i][1] };
if (np.x >= 0 && np.y >= 0 && np.x < _n && np.y < _n && _field[np.x][np.y])
adj.emplace_back(np);
}
return adj;
}
// returns the path as a string containing each position e.g. (0,0) (1,1) etc...
// using breath first search
string ComputeShortestPath()
{
vector<vector<Position>> parent(_n, vector<Position>(_n, Position{ 1,1 }));
// push start into queue and mark parent of start to it self
// (0,0) = (root of BFS traversal tree)
deque<Position> q;
parent[0][0] = Position{ 0,0 };
q.emplace_front(Position{ 0, 0});
while (!q.empty())
{
auto u = q.back();
q.pop_back();
for (auto v : GetAdjecents(u))
{
if (parent[v.x][v.y].x == 1)
{
parent[v.x][v.y] = u;
if (u.x == _n  1 && u.y == _n  1)
{
q.clear();
break;
}
q.emplace_front(v);
}
}
}
// case where destination wasn't reached
if (parent[_n  1][_n  1].x == 1)
return "no path exists";
// backtrack the BFS tree from destination to start
Position pos{_n1, _n1};
vector<Position> path;
path.emplace_back(pos);
while (pos.x != 0  pos.y != 0)
{
pos = parent[pos.x][pos.y];
path.emplace_back(pos);
}
// reverse the path and print it to string
stringstream ss;
for (int i = path.size()  1; i >= 0; i)
{
ss << string("(") << path[i].x << "," << path[i].y << ") ";
}
return ss.str();
}
};
int main()
{
MatrixShortestPath sp( {
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0 },
{ 1, 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 0, 1 },
{ 0, 0, 1, 1, 0, 1 } } );
cout << sp.ComputeShortestPath();
}

Chris
August 24, 2016 /*
I noticed the task was quite exactly specified with the few words, but it needed some repetition:
 unidirected graph with weights and no cycles: > that can be viewed as a tree
 the sum of the weight of each path: means one value for the whole structure
 shortest path between two vertices: in this setup, it's as well the shortest
weighted path because no forward and backward edges exist (would create cycles
on unidirected graph)
> no need for Djikstra or other heavy weight algos
> negative weights don't matter
Solution approach:
 pick an arbitrary node as root to start, traverse down until first leave,
note it's total tree size (=1) propagate that size to the parent, so parent
can keeps track of it's total tree size etc. While doing this for every completely
visited node store in a list it's tree size and weight of edge to parent
 when tree is completely traversed, go through the above created list
(with length n) with pairs that contain tree size (s) and edgeweight (w):
sum += (ns)*s*w
(node: an edge kind of cut's the tree in two, if a leave is cut,
it's subtree is 1, so 1*n paths to all vertices, if the subtree is 2, it's 2*(n2),
because from each of the two nodes goes a path to each of the remaining n2 nodes)
The solution looks still complicated, maybe there is an easy algo for it.
TimeComplexity: O(V+E) = O(V+[V]) = O(V) due to constraints given
SpaceComplexity: O(V)
*/
#include <vector>
#include <string>
#include <stack>
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Node
{
private:
string _id;
vector<pair<int, Node*>> _adj;
Node *_parent = nullptr; // parent
int _size = 1; // subtree sisze
int _wtop = 0; // weight to parent
bool _visited = false;
public:
Node(string id) : _id{ id } {}
void Connect(Node *adj, int w)
{
_adj.emplace_back(pair<int, Node*>(w, adj));
adj>_adj.emplace_back(pair<int, Node*>(w, this));
}
int SumAllPairWeight()
{
ClearAll();
vector<pair<int, int>> nodes; //1st: treesize, 2nd: weight to parent
stack<Node*> s;
s.push(this);
while (!s.empty())
{
auto u = s.top();
bool visit = true;
for (auto e : u>_adj)
{
auto v = e.second;
auto w = e.first;
if (v != u>_parent && !v>_visited)
{
visit = false;
s.push(v);
v>_parent = u;
v>_wtop = w;
v>_size = 1;
}
}
if (visit)
{
u>_visited = true;
s.pop();
nodes.emplace_back(pair<int, int>(u>_size, u>_wtop));
auto p = u>_parent;
if (p != nullptr)
{
p>_size += u>_size;
}
}
}
int sum = 0;
int n = nodes.size();
for (auto u : nodes)
{
int s = u.first;
int w = u.second;
sum += (n  s)*s*w;
}
return sum;
}
private:
void ClearAll()
{
unordered_set<Node*> vis;
stack<Node*> s;
s.push(this);
while (!s.empty())
{
auto u = s.top();
s.pop();
u>_visited = false;
u>_parent = nullptr;
u>_wtop = 0;
u>_size = 1;
vis.emplace(u);
for (auto e : u>_adj)
{
auto v = e.second;
if (vis.find(v) == vis.end())
{
s.emplace(v);
}
}
}
}
};
int main()
{
Node a{ "A" };
Node b{ "B" };
Node c{ "C" };
Node d{ "D" };
a.Connect(&b, 1);
b.Connect(&c, 2);
b.Connect(&d, 3);
cout << "sum (from a): " << a.SumAllPairWeight() << endl;
cout << "sum (from b): " << b.SumAllPairWeight() << endl;
getchar();
}

Chris
August 23, 2016 /*
Dynamic programming problem since j[i] >= j[i1], i[i] >= i[i1]
can only move from left to right and top down
dp[i,j] = max(
dp[i1,j], // if i>0
dp[i,j1], // if j>0
0 // if i=0 and j =0
) + c[i,j]
Timecomplexity: O(n^2)
Spacecomplexity: O(n^2), can be optimized to O(n) (need vector of size n+1)
*/
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> ParseHouses(int n, const string& houses);
int MaxCollect(int n, const string& houses)
{
auto c = ParseHouses(n, houses);
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int c1 = i > 0 ? dp[i  1][j] : 0;
int c2 = j > 0 ? dp[i][j  1] : 0;
dp[i][j] = max(c1, c2) + c[i][j];
}
}
return dp[n  1][n  1];
}
void Match(istream& iss, char c)
{
char r = '\0';
while (!iss.eof() && (r == ' '  r == '\n'  r == '\r'  r == '\0')) iss >> r;
if (r != c) throw "syntax error";
}
vector<vector<int>> ParseHouses(int n, const string& houses)
{
vector<vector<int>> res(n, vector<int>(n, 0));
stringbuf sb(houses);
istream iss(&sb);
for (int i = 0; i < n; i++)
{
Match(iss, '(');
for (int j = 0; j < n; j++)
{
int c;
iss >> res[i][j];
if (j != n  1) Match(iss, ',');
}
Match(iss, ')');
if (i != n  1) Match(iss, ',');
}
return res;
}
int main()
{
cout << MaxCollect(4, "(1,7,5,2),(5,12,3,6),(100,9,23,16),(16,4,5,9)");
}

Chris
August 23, 2016 /*
1. Copy the two arrays into one (v3)
2. Sort it according to it's Id's
3. Remove duplicates
4. Resize
5. Sort again according to weights
note: the fact the input is sorted was not used, there might be a better solution I couldn't spot
*/
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Item
{
int id;
int weight;
};
vector<Item> Merge(const vector<Item>& v1, const vector<Item>& v2)
{
vector<Item> v3(v1.size() + v2.size());
copy(v2.begin(), v2.end(), copy(v1.begin(), v1.end(), v3.begin()));
sort(v3.begin(), v3.end(), [](Item& a, Item&b) { return a.id < b.id; });
int j = 0;
for (int i = 1; i < v3.size(); ++i)
{
if (v3[j].id == v3[i].id)
{
v3[j].weight += v3[i].weight;
}
else
{
v3[++j] = v3[i];
}
}
v3.resize(j+1);
sort(v3.begin(), v3.end(), [](Item& a, Item& b) {return a.weight < b.weight; });
return v3;
}
int main()
{
vector<Item> v1{ {1,2}, {2,3}, {4, 8}, {1, 2} };
vector<Item> v2{ {3,1}, {2,7}, {9, 2}, {1, 1}, {1,1} };
auto res = Merge(v1, v2);
for_each(res.begin(), res.end(), [](Item& a) { cout << "item id: " << a.id << " weight " << a.weight << endl; });
}

Chris
August 17, 2016 /*
1. Count character occurence in input per character with a hash table
2. Construct palindrome by taking two characters out and placing them at the start and end
3. If at least one character has odd occurence, place one of it in the middle
*/
#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;
string ConstructPalindrome(const string& input)
{
int size = 0; // size of the resulting palindrome
unordered_map<char, int> cm; // character count map
// count each character, if a character occures an even amount of time,
// increase the palindrome size by that size (2 each time)
for (char c : input)
{
unordered_map<char, int>::iterator it;
if ((it = cm.find(c)) != cm.end())
{
it>second++;
if (it>second % 2 == 0) size += 2;
}
else
{
cm[c] = static_cast<int>(1);
}
}
// fix size for the case there is at least one character with an odd count
// and reserve space for result
if (size < input.size()) size++;
string result(size, ' ');
// construct result
int i = 0;
int j = size  1;
for (auto p : cm)
{
while (p.second > 1)
{
result[i++] = p.first;
result[j] = p.first;
p.second = 2;
}
if (p.second == 1) result[size / 2] = p.first;
}
return result;
}
int main()
{
cout << "aha: '" << ConstructPalindrome("aha") << "'" << endl;
cout << "ttaatta: '" << ConstructPalindrome("ttaatta") << "'" << endl;
cout << "abc: '" << ConstructPalindrome("abc") << "'" << endl;
cout << "gggaaa: '" << ConstructPalindrome("gggaaa") << "'" << endl;
getchar();
}

Chris
August 17, 2016 imagine a crane and ,loading docks as the question sugest:
1) minimize moves, assuming sorted order means that the empty dock is at the end and not in the midle somewhere after sort, it is easy:
 start with i = 1
 while i <= n1
 if box in dock i is not box i, take that box and move it to the empty dock n+1
 get box i and move it to dock i, thereby freeing dock j
 while j is not n+1: get box j and move it to dock j, asign new empty dock to j
 increment i
2) minimize distance of move
I doubt there is a perfect solution in polynominial time. I see no common subproblem, greedy choice etc. It reminds me to the rubik cubes problem. I guess best one can do is somehow try to minimize, but I wouldn't be able to come up with a solution in the remaining time without hints.
/* For the fun of it, here Dijkstra's shuntingyard version
reference: wikipedia / Shuntingyard_algorithm
Simplified for the problem:
 two stack, one for the numbers that need to be fed into a binaryoperation
 the other for operators/open parentesis (=elements) that haven't been used
 While there are tokens:
 Read a token (number, parentesis, operator)
 if token is number: push on number stack
> explanation:
> since we read infix notation, we do not know where this number binds to
> to until we see the next operator or a closing parentesis
 if token is binary operator (let's say o1):
 while o1.precedence <= elementstack.top.precedence: Evaluate()
> we know now, that no operation with a higher precedence was binding to these
> numbers we have seen before, so we can safely evaluate
> e.g. when the o1.precedence was higher, it was clear that top of number
> stack would be used with the next "number" (or term) and the current o1
> (note the = is only valid because we only consider left associative, if
> o1 was right associative it could take the argument away ... ... see wikipedia article
 push o1 on stack
> o1 needs to be evaluated later, of course
 if open parentesis: push on element stack
> explanation this is just a marker, so we know when to stop when the parentesis close
 if close parentesis:
 while(elemenstack.top != closeparentesis: Evaluate()
> a closed parentesis tells us that we must evaluate to it's left, regardless
> what follows on the right
 remove open parentesis from stack
> it's been matched with a right parentesis
 Evaluate until no BinOperators are left on elementstack
Note this version doesn't deal with the unary  eg. 12+24 won't work as well 12+34 does not work :)
*/
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
using namespace std;
class ExpressionEval
{
private:
enum class ExprElemType { OpenPar, ClosePar, BinOp };
struct ExprElem
{
char Identifier; // +,,/, ...
ExpressionEval::ExprElemType ElementType;
int Precedence; // 1,2, ... for Binary Operations
bool LeftAssocicative; // not used yet
bool RightAssociative; // not used yet
int(*BinOperation)(int, int); // the function to do the operation
};
istream& _input; // input stream
stack<const ExprElem*> _elementStack;
stack<int> _numStack;
static const ExprElem ElementTable[6];
public:
ExpressionEval(istream& input) : _input(input) {}
int EvaluateExpression()
{
// read expression piece by piece
while (!_input.eof())
{
if (_input.peek() == '\n') // get rid of the new line in the input string at the end of expression, in case...
{
_input.get();
break;
}
// see if it is an
const ExprElem* nextElement = GetExpressionElemenet();
if (nextElement == nullptr)
{ // assume it's a number
int num;
_input >> num;
_numStack.push(num);
}
else if (nextElement>ElementType == ExprElemType::BinOp)
{
while (!_elementStack.empty() &&
_elementStack.top()>ElementType == ExprElemType::BinOp &&
nextElement>Precedence <= _elementStack.top()>Precedence )
Eval();
_elementStack.push(nextElement);
}
else if (nextElement>ElementType == ExprElemType::ClosePar)
{
while (!_elementStack.empty() &&
_elementStack.top()>ElementType != ExprElemType::OpenPar)
Eval();
if (_elementStack.empty()) throw "parentesis mismatch";
_elementStack.pop();
}
else if (nextElement>ElementType == ExprElemType::OpenPar)
{
_elementStack.push(nextElement);
}
}
// evaluate remainings
while (!_elementStack.empty()) Eval();
return _numStack.top();
}
private:
// evaluate expression on the stack (operation on elementstack, numers on numberstack)
void Eval()
{
if (_elementStack.empty()) throw "operationstack empty";
if (_numStack.size() < 2) throw "more operators than operands";
const ExprElem *op = _elementStack.top(); _elementStack.pop();
if (op>ElementType != ExprElemType::BinOp) throw "support only binary operation at the moment";
int b = _numStack.top(); _numStack.pop();
int a = _numStack.top(); _numStack.pop();
_numStack.push(op>BinOperation(a, b));
}
// lookup the expression element table and return a pointer to the element or nullptr
inline const ExprElem* GetExpressionElemenet()
{
char op = _input.peek();
for (auto& elem : ElementTable)
{
if (elem.Identifier == op)
{
_input.get();
return &elem;
}
}
return nullptr;
}
};
// operator table
const ExpressionEval::ExprElem ExpressionEval::ElementTable[6] =
{
{ '+', ExpressionEval::ExprElemType::BinOp, 1, true, true, [](int a,int b) { return a + b; } },
{ '', ExpressionEval::ExprElemType::BinOp, 1, true, false, [](int a,int b) { return a  b; } },
{ '*', ExpressionEval::ExprElemType::BinOp, 2, true, true, [](int a,int b) { return a * b; } },
{ '/', ExpressionEval::ExprElemType::BinOp, 2, true, false, [](int a,int b) { return a / b; } },
{ '(', ExpressionEval::ExprElemType::OpenPar, 0, false, false, nullptr },
{ ')', ExpressionEval::ExprElemType::ClosePar, 0, false, false, nullptr },
};
int main()
{
string test = "3\n"
"19+12/4((47)*3/1)\n"
"1+(23)*4+56*8(18*12*13)(11/(5+2+4))\n"
"((2+4)/32+1)\n";
stringstream ss(test);
int n;
ss >> n;
ss.get(); // get that newline
for (int i = 0; i < n; i++)
cout << ExpressionEval(ss).EvaluateExpression() << endl;
}

Chris
July 05, 2016 /*
Solution approach
Using a handmade LL(1) Parser without real lexical analysis,
so whitespaces must not occure in the input string and token
recogniztion is primitive
It's a bit an overkill since it doesn't make use of all the information
given by the interviewer one can assume there is a "shortcut"
however, I find it rather exotic to try to find a special solution for a
problem that fits so cleanly into a theory space well understood.
Interesting situation in an interview :)

EBNF
PROGRAM = INT, NEWLINE, {EXPRLINE}
EXPRLINE = EXPR, NEWLINE
EXPR = EXPR OP1 TERM  TERM
TERM = TERM OP2 FACT  TERM
FACT = INT  '(' EXPR ')'
OP1 = '+'  ''
OP2 = '*'  '/'
INT = [''] DIGITS
DIGITS = DIGIT {DIGIT}
DIGIT = '0'  '1'  '2'  '3'  ...  '9'
NEWLINE = '\n'
EXPR and TERM are not LL(1), so convert into LL1:
EXPR = TERM {OP1 TERM}
TERM = FACT {OP2 FACT}

NOTE:
 {x}: x repated n times, 0<=n
 [y]: y occures 0 or 1 times
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Parser
{
private:
string _buffer;
int _position;
public:
Parser(string buffer) : _buffer(buffer), _position(0) {}
vector<int> Parse()
{
vector<int> result;
Program(result);
return result;
}
private:
//Production: PROGRAM = INT, NEWLINE, {EXPRLINE}
void Program(vector<int>& res)
{
int count = 0;
if (!Int(count)) throw "E1";
if (count < 0) throw "E2";
if (!NewLine()) throw "E3";
for (int i = 0; i < count; i++)
{
int eres = 0;
if (!ExprLine(eres)) throw "E4";
res.emplace_back(eres);
}
}
// Production: EXPRLINE = EXPR, NEWLINE
bool ExprLine(int& res)
{
if (!Expr(res)) return false;
if (!NewLine()) throw "E5";
}
// Production: EXPR = EXPR OP1 TERM  TERM > EXPR := TERM {OP1 TERM}
bool Expr(int& res)
{
int t2 = 0;
char op;
if (!Term(res)) return false;
while (Op1(op))
{
if (!Term(t2)) throw "E7";
if (op == '') res = t2; // should check for overflow, e.g. using safeint...
else res += t2; // may overflow...
}
return true;
}
// Production: TERM = TERM OP2 FACT  TERM > TERM = FACT {OP2 FACT}
bool Term(int& res)
{
int f2;
char op;
if (!Fact(res)) return false;
while (Op2(op))
{
if (!Term(f2)) throw "E9";
if (op == '*') res *= f2; // may overflow...
else res /= f2;
}
return true;
}
// Prodcution: FACT = INT  '(' EXPR ')'
bool Fact(int &res)
{
if (Int(res)) return true;
if (ReadIf('('))
{
if (!Expr(res)) throw "E10";
if (!ReadIf(')')) throw "E11";
return true;
}
return false;
}
// Production: OP1 = '+'  ''
bool Op1(char& res)
{
res = Peek();
return ReadIf('+')  ReadIf('');
}
// Production: OP2 = '*'  '/'
bool Op2(char& res)
{
res = Peek();
return ReadIf('*')  ReadIf('/');
}
// NEWLINE
bool NewLine()
{
return ReadIf('\n');
}
// INT
bool Int(int& res)
{
res = 0;
int sign = 1;
string digits;
if (ReadIf(''))
{
sign = 1;
if (!Digits(digits))
{
UnRead(1);
return false;
}
}
else
{
if (!Digits(digits)) return false;
}
for (int i = digits.size()1, f=1; i >=0 ; i, f*=10)
{
res += (digits[i]  '0') * f; // should check overflow with safeint or manually
}
res *= sign;
return true;
}
// DIGITS
bool Digits(string& digits)
{
char d;
digits.clear();
while (Digit(d))
{
digits.append(1, d);
}
return digits.size() > 0;
}
// DIGIT
bool Digit(char& c)
{
return ReadIfInRange('0', '9', c);
}
// Gets the current character (0 at the first call, after Read 1, etc..)
// returns '\0' if at end
char Peek()
{
if(_position < _buffer.size()) return _buffer[_position];
return '\0';
}
// Reads the current character if it is =1 (advances the current position)
bool ReadIf(char a)
{
char b;
return ReadIfInRange(a, a, b);
}
// reads the current character if in range [a..b]
// e.g. a='0' b='2', reads it if Peek()=='0' or Peek()=='1' or Peek()=='2'
bool ReadIfInRange(char a, char b, char& c)
{
c = Peek();
if (c >= a && c <= b)
{
Read();
return true;
}
return false;
}
// Read the current character
// advances current position unless at end of string
// note, '\0' may not occure in the string as symbol other then EOF
char Read()
{
char p = Peek();
if(p != 0) _position++;
return p;
}
// To go back
void UnRead(int n)
{
_position = n;
}
};
int main()
{
string s1 = "1\n1+2+3*4\n";
string s2 = "3\n"
"19+12/4((47)*3/1)\n"
"1+(23)*4+56*8(18*12*13)(11/(5+2+4))\n"
"((2+4)/32+1)\n";
cout << "test string s1:" << endl << s1 << endl << endl;
for (auto i : Parser(s1).Parse()) cout << i << endl;
cout << endl << endl << "test string s2:" << endl << s2 << endl << endl;
for (auto i : Parser(s2).Parse()) cout << i << endl;
}

Chris
July 04, 2016 Approach 1: use a hashtable, O(1) to insert and O(n) to check
Approach 2: any form of sorted container, AVL, BTree, ... for O(lg(n)) insert and with vucuong020195 method to test
From the bigo 1) looks better, I'm not sure if that's really the case in real world  how ever, depends very much on the tree implementation, could be quite bad if with lots of pointers etc...
/*
Idea:
 dynamic programming, we are interested in the max free square at x,y = FLS(x,y)
 if (x,y) is free: the new point can form a new free square of min(FLS(x+1,y),FLS(x,y+1),FLS(x+1,y+1))
note: the last FLS(x+1, y+1) can be optimized but it would work like this
 if (x,y) is not free: it will never participate in an other free square
note: even if x,y is not free, x+1,y / x,y+1 can very well contain a max square, so we need to look there
 base case(s), sigle square with size one at the right and bottom border of the matrix, if free: 1 if there is a tree: 0
matrix mxn: boolean two dimensional array, 0<=x<m, 0<=y<n
FLS stands for find largest free square
FLS(x,y) returns the edge size of the free square starting at (x,y) not the max edge size of any square within square (x,y)(m,n)
/ if M[x,y] = 1: 0, FLS(x+1, y), FLS(x, y+1)  the recursion is needed to search further, the max size at x,y is 0
/ if M[x,y] = 0 and
FLS(x,y) =  if x = m1: 1
\ if y = n1: 1
\ all other cases: min(FLS(x+1, y), FLS(x,y+1), FLS(x+1,y+1)) + 1
while going through the FLS  recursion, remember largest square
time complexity O(n*m) / don't see any optimization
space complexity O(n*m) / can be optimized with a bottom up method to something like min(m,n) + 1
max stack depth O(n+m) / can be optimized if doing bottom up instead of memozation
*/
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;
class FLS
{
private:
int m; // matrix x dimension
int n; // matrix y dimmension
const vector<vector<bool>>& matrix; // matrix with free/occupied squares (free=false, occupied=true)
vector<vector<int>> mt; // memotable that holds the already calculated squares
int maxs = 0; // greates so far seen sidelength
int maxs_x = 0; // x position where the greates sidelength was seen
int maxs_y = 0; // y position where ...
public:
FLS(const vector<vector<bool>>& amatrix) : matrix(amatrix)
{
n = matrix.size();
if (n == 0) throw invalid_argument("matrix ydimension = 0");
m = matrix[0].size();
if (m == 0) throw invalid_argument("matrix xdimension = 0");
mt = vector<vector<int>>(n, vector<int>(m, 1)); // memotable
}
int Solve(int x, int y)
{
int i = 0;
int res = mt[y][x]; // check memoization table
if (res != 1) return res; // we hit a memoized entry, return it
if (x == m  1  y == n  1)
{
res = matrix[y][x] ? 0 : 1; // basecase
}
else if (!matrix[y][x])
{
int s1 = Solve(x + 1, y);
int s2 = Solve(x, y + 1);
res = min(s1, s2);
if (res > 0) // optimze min(s1,s2,s3) by only looking at the single point the recursion didn't look
{
if (!matrix[y + res][x + res]) res++;
}
else
{
res = 1;
}
}
else
{
Solve(x + 1, y);
Solve(x, y + 1);
res = 0;
}
if(res > maxs)
{
maxs = res;
maxs_x = x;
maxs_y = y;
}
mt[y][x] = res; // memoize
return res;
}
int get_M() const { return m; }
int get_N() const { return n; }
int get_X() const { return maxs_x; }
int get_Y() const { return maxs_y; }
int get_S() const { return maxs; }
};
int main()
{
vector<vector<bool>> matrix {
{ 1, 0, 1, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 } };
FLS fls(matrix);
fls.Solve(0, 0);
cout << "matrix of dimension " << fls.get_M() << "x" << fls.get_N() << endl
<< " found largest square with side length: " << fls.get_S() << " at position " << fls.get_X() << ", " << fls.get_Y() << endl;
}

Chris
July 02, 2016 1) it is finding the kthary element and return it and all that are smaller
2) A modified quicksort partition method will do it in O(n)
3) I did it in place of the original array/vector for simplicity
#include <iostream>
#include <vector>
using namespace std;
struct Point
{
int x; int y;
Point(int ax, int ay) : x(ax), y(ay) {}
int get_DistSq() { return x*x + y*y; }
};
ostream& operator << (ostream& os, Point& p) { return os << "{" << p.x << "," << p.y << "(" << p.get_DistSq() << ")" << "}"; }
// quicksorts partition function, returns k
// partitions array [s..e] into [s..k][k+1..e] where every element in [s..k] < than every element in [k+1..e]
int Partition(int s, int e, vector<Point>& pts)
{
int p = (s + e) / 2; // pick pivot element, improvement: randomize or at least check overflow
swap(pts[p], pts[e]); // swap pivot with end element
int i = s1; // all in [s..i] <= p < all in [i+1..j]
int pv = pts[e].get_DistSq();
for (int j = s; j < e; ++j)
{
if (pts[j].get_DistSq() <= pv)
{
i++;
swap(pts[i], pts[j]);
}
}
swap(pts[i+1], pts[e]);
return i+1;
}
// changes the vector to contain the ksmallest elements at position 0..k
// smallest in this contect is the distance of the points to {0,0}
void Find(vector<Point>& pts, int k)
{
int s = 0;
int e = pts.size()1;
int m = 0;
do
{
m = Partition(s, e, pts);
if (m < k) s = m + 1; // on the left of m are not enough elements
if (m > k) e = m  1; // on the left of m are too many elements
} while (m != k);
}
int main()
{
int k = 2;
auto pts = vector<Point>{ Point(1,2), Point(2,2), Point(5,3), Point(4,2), Point(3,2), Point(2,0), Point(1,1), Point(2,1), Point(9,9) };
cout << "all points:" << endl;
for (int i = 0; i < pts.size(); i++) cout << pts[i] << " ";
Find(pts, k);
cout << endl << endl << k << " smallest point(s):" << endl;
for (int i = 0; i < k; i++) cout << pts[i] << " ";
getchar();
}

Chris
July 02, 2016 1) use BFS (shortest path with no weights on edge)
2) implement no nodes and no edges, just keep the parentpointer of the BFS traversal tree as coordinates in the chessboard
from collections import deque
N = 8
board_p = [[(1,1) for f in range(0,N)] for i in range(0,N)]
def Adjacents(u):
adj = []
for e in [(2,1),(2,1),(2,1),(2,1),(1,2),(1,2),(1,2),(1,2)]:
v = (u[0] + e[0], u[1] + e[1])
if v[0] >= 0 and v[0] < N and v[1] >= 0 and v[1] < N: adj.append(v)
return adj;
def Moves(s,t):
q = deque()
q.append(s)
board_p[s[0]][s[1]] = s # "root" of BFStraversal points to it self (avoid loop over "backedge" to s)
while q:
u = q.popleft()
if u == t: break
for v in Adjacents(u):
if board_p[v[0]][v[1]] == (1,1):
board_p[v[0]][v[1]] = u
q.append(v)
# walk the path back (using parent "pointers")
path = [(t)]
while t != s:
t = board_p[t[0]][t[1]]
path.append(t)
path.reverse()
return path
print(Moves((1,1),(5,5)))

Chris
July 01, 2016 /*
Write program that takes integer, deletes one of two consecutive digits and return greatest of all results.
Assumption:
1) consecutive means, the same digit is repeated
2) only delete one digit of such a pair
Solution:
 straight forward
 runtime O(log(n)*log(n)) / where n is the value of the integer ...
Example:
994141 > 99414
141465 > 14165
*/
#include <iostream>
using namespace std;
int RemoveConsecutiveDigit(int v)
{
int ov = v / 10;
while (ov > 0)
{
int iv = v;
int ivc = 1;
while (iv != ov)
{
if (ov % 10 == iv % 10)
{
return (v / 10 / ivc * ivc) + (v % ivc); // looks wierd, just removes the digit
}
iv /= 10;
ivc *= 10;
}
ov /= 10;
}
return v;
}
int main()
{
cout << RemoveConsecutiveDigit(994141) << endl;
cout << RemoveConsecutiveDigit(141465) << endl;
getchar();
}

Chris
June 22, 2016 Assumptions:
 use a binary representation in contrast to decimal
 do it portable (32, 64 bit)
 number can grow to no limit, except memory ...
 output has hex is sufficient
 only deal with unsigned representation
 only integers, since they are passed as integerarray
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
class LargeNumber;
ostream& operator << (ostream& os, const LargeNumber& ln);
class LargeNumber
{
friend ostream& operator << (ostream& os, const LargeNumber& ln);
public:
using dtype = unsigned int;
private:
vector<dtype> _data; // in "little endian": (data[0]^1, data[1]^(sizeof(dtype)*8), ...
public:
LargeNumber(initializer_list<dtype>&& data) : _data(data) {}
LargeNumber& operator ++()
{
size_t i = 0;
bool overflow = true;
while (overflow && i < _data.size())
{
_data[i]++;
overflow = _data[i] == 0;
i++;
}
if (overflow)
{// grow
_data.resize(_data.size() + 1);
_data[i] = 1;
}
return *this;
}
};
int main()
{
constexpr auto uintm = std::numeric_limits<LargeNumber::dtype>::max();
LargeNumber n1({ 0 });
LargeNumber n2({ uintm });
LargeNumber n3({ uintm  3, uintm, });
cout << "n1 " << n1 << endl;
cout << "++n1 " << ++n1 << endl;
cout << "++n1 " << ++n1 << endl;
cout << "n2 " << n2 << endl;
cout << "++n2 " << ++n2 << endl;
cout << "++n2 " << ++n2 << endl;
cout << "n3 " << n3 << endl;
cout << "++n3 " << ++n3 << endl;
cout << "++n3 " << ++n3 << endl;
cout << "++n3 " << ++n3 << endl;
cout << "++n3 " << ++n3 << endl;
getchar();
}
ostream& operator << (ostream& os, const LargeNumber& ln)
{
constexpr auto nc = sizeof(LargeNumber::dtype) * 2; // nible count per int
bool lz = true; // leading zero
size_t i = ln._data.size()*nc;
while (i > 0)
{
i;
auto sr = (i%nc) * 4;
auto v = (ln._data[i / nc] >> sr) & 0xf;
if (v != 0  !lz)
{
cout << hex << v;
lz = false;
}
}
return os;
}
/* output
n1
++n1 1
++n1 2
n2 ffffffff
++n2 100000000
++n2 100000001
n3 fffffffffffffffc
++n3 fffffffffffffffd
++n3 fffffffffffffffe
++n3 ffffffffffffffff
++n3 10000000000000000
*/

Chris
June 17, 2016 How about a wall follower maze solver that always has a wall to it's right? Below is a simple implementation. O(x*y*N) due the lame collision detection. But it finds it's way through dead ends etc.
Strategy is as follows:
1: find a place to start by scanning the start column (y=0, a<=x<c): there must be a point that is not surveillanced otherwise it can't start
2: go downwards so there is the left wall to it's right (looking into the "robots" direction)
3: if there is nothing on the right, go into that space (doesn't happen on the left wall)
4: if there is something ahead, turn left until way is free
5: if you somehow end up at the start position, the "maze" is not solveable
PS: There is an infinite loop if it has only one "pixel" to move at the start, we should cover that special case
Improvements:
1: proper termination
2: improve that lame collision detection to something smart, any idea?
3: Think about optimizing it, e.g. when returning from a dead end, some
#include <iostream>
using namespace std;
const int sensor_r = 2;
const int sensor_rr = sensor_r * sensor_r;
struct Pt {
int x;
int y;
Pt(int ay, int ax) { x = ax; y = ay; }
};
bool Collision(int a, int b, int c, int d, int y, int x, const Pt* ss, int nss)
{
if (y < a) return true; // hit left wall, right wall we don't check, since it is "open"
if (x < b) return true; // hit top wall
if (x >= d) return true; // hit bottom wall
for (int i = 0; i < nss; ++i) // lame collision detection on sensor
{
int dx = ss[i].x  x;
int dy = ss[i].y  y;
if (dx*dx + dy*dy <= sensor_rr)
{
return true;
}
}
return false;
}
void FindWay(int a, int b, int c, int d, const Pt* ss, int nss, char* track)
{
if (ca <= 0) return;
if (db <= 0) return;
int y = a;
int x = b;
for (x = b, y = a; x <= d && Collision(a, b, c, d, y, x, ss, nss); ++x);
if (x == d) { cout << "can't start: all starting points are checked by sensors" << endl; return; }
int ox = x;
int oy = y;
int dx = 1;
int dy = 0;
while (y < c)
{
track[x*(c  a + 1) + y] = 'O'; // +1: due to \n
if (!Collision(a,b,c,d, y  dx, x + dy, ss, nss)) // there must be something on the right to follow the "wall"
{
// if not, turn right ... and do a step in this direction
int t = dx;
dx = dy;
dy = t;
}
else if (Collision(a, b, c, d, y + dy, x + dx, ss, nss))
{
// collision ahead, turn left and do not move
int t = dx;
dx = dy;
dy = t;
continue;
}
// turned right into an empty space or just continue into the direction
x += dx;
y += dy;
if (x == ox && y == oy)
{
cout << "can't solve it, way is blocked" << endl;
return;
}
}
}
char *CreateTrackBuf(int a, int b, int c, int d);
int main()
{
int a = 0;
int b = 0;
int c = 15;
int d = 10;
char *track = CreateTrackBuf(a,b,c,d);
Pt ss[] = { {6,7} , {12,7}, {12,3} /*, {12, 2} */ };
FindWay(0, 0, 15, 10, ss, sizeof(ss) / sizeof(ss[0]), track);
cout << track;
getchar();
}
char *CreateTrackBuf(int a, int b, int c, int d)
{
if (c  a <= 0) return nullptr;
if (d  b <= 0) return nullptr;
// create a char buffer to record and print the path he went
int y2 = c  a + 1; // +1: due to '\n'
int x2 = d  b;
int os = y2 * x2;
char *po = new char[os];
for (int i = 0; i < os; ++i) po[i] = ' ';
for (int i = 1; i <= x2; i++)
{
po[i*y2  1] = '\n';
}
po[os  1] = '\0';
return po;
}
/* output on above sample:
O OOO
O OO OO
O OO O
O O
O OOO OO
O OO OO OO
O OO OOO
O O O
O OO OOO
OOOOOO OOOOO
with the 12,2 sensor (blocked path)
can't solve it, way is blocked
OOOOOOOOOOOO
O OO
O O
O O
O OOO OO
O OO OO OO
O OO OOO
O O O
O OO OOO
OOOOOO OOOOO
*/

Chris
June 16, 2016 it's a DP problem:
c[i]=max(c[il]+l, c[il]) / if a match (length l) was found, for all matches ending at position i
c[i]=c[i1] / if no matches end in i
c[i]=0 / if i =0 (supose the input string starts at 0)
result is: c[n] *100 / input string length
the code:
#include <vector>
#include <string>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int StartsWith(const string& input, int off, const string& match);
int PercentageMatch(const string& input, const list<string>& dict)
{
if (input.size() == 0) return 100;
vector<int> c(input.size()+1, 0);
for (int i = 0; i < input.size(); ++i)
{
for (list<string>::const_iterator di = dict.begin(); di != dict.end(); ++di)
{
int l = StartsWith(input, i, *di);
if (l > 0) c[i + l] = max(c[i + l], c[i] + l);
}
c[i + 1] = max(c[i + 1], c[i]);
}
return 100 * c[input.size()] / input.size();
}
int main()
{
list<string> dict1({ "dog", "frog", "cat" }); // it said a list in the question
cout << "case 1: " << PercentageMatch("catdog", dict1) << "%" << endl;
cout << "case 2: " << PercentageMatch("cardog", dict1) << "%" << endl;
list<string> dict2({ "a", "b", "c", "da", "daf", "fghjkl" });
cout << "case 3: " << PercentageMatch("abc", dict2) << "%" << endl;
cout << "case 4: " << PercentageMatch("adaf", dict2) << "%" << endl;
cout << "case 5: " << PercentageMatch("dafghjkl", dict2) << "%" << endl; // here he must backtrack, the greedy version will not have 100% because it takes daf and misses the fghjkl
}
int StartsWith(const string& input, int off, const string& match)
{
// depending on the count of items and the length of the input string it may pay off creating a trie and using it character by character
// from the outher loop below
if (input.size()  off < match.size()) return 0;
for (int i = 0; i < match.size(); ++i)
{
if (input[off + i] != match[i]) return 0;
}
return match.size();
}

Chris
June 10, 2016
Rep
Rep
Repjudydschultz1234, Android test engineer at Eterno Infotech Pvt Ltd
Spent a weekend researching weebles in Nigeria. My current pet project is developing strategies for how to break someone's ...
RepAmber Van is the top rated company that offers friendly and professional removals services.Our featured services includes domestic moves ...
RepJames Gulledge, Dev Lead at ADP
Get you driving in comfort and class in Atlanta! Prestige Luxury Rentals offer a wide selection of premium vehicles Our ...
Open Chat in New Window
assumption: wanted is the successor of a node and it's a binary search tree, whose
inorder traversal would lead to a increasing sequence like the sample
(thus left node <= this <= right).
 Chris October 19, 2016