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
/* Interpretation of the question: Given an N-ary 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
*/
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 a-b-c-d 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 subnet-id with the subnet-size 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 subnet-ids.
To actually count, I would create a self balancing tree in memory to count frequencies
by above subnet-id. 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 in-place
(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 map-reduce to scale to many machines.
Data can be appended if more logfiles come without the need to re-process 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 (k-1)! 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[n-1] >= departures[n-1]) 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(cg-1,0);
d++;
}
mg=std::max(cg,mg);
}
return mg;
}
/*
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 9|10|11|13 or 98|100|101|102
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;
}
/*
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 n-1, index 1 with n-2, 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[n-1-i]) for 0<=i<n/2
e[i] = max(a[i], a[n-1-i]) for 0<=i<n/2
Iterate through the array 1 to n/2-1 and check if:
f[i]>=f[i-1] AND e[i]>=e[i-1]
If that succeeded and length of a is odd, only need to check
f[n/2-1] <= 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 n-elements
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;
}
/*
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. N-k 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;
}
}
/*
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 word-index 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;
}
/*
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 {n-1, n-1} to keeps things more conventional
- {0,0} and {n-1, n-1} 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{_n-1, _n-1};
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();
}
/*
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 edge-weight (w):
sum += (n-s)*s*w
(node: an edge kind of cut's the tree in two, if a leave is cut,
it's sub-tree is 1, so 1*n paths to all vertices, if the subtree is 2, it's 2*(n-2),
because from each of the two nodes goes a path to each of the remaining n-2 nodes)
The solution looks still complicated, maybe there is an easy algo for it.
Time-Complexity: O(|V|+|E|) = O(|V|+[V]) = O(|V|) due to constraints given
Space-Complexity: 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();
}
/*
Dynamic programming problem since j[i] >= j[i-1], i[i] >= i[i-1]
can only move from left to right and top down
dp[i,j] = max(
dp[i-1,j], // if i>0
dp[i,j-1], // 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)");
}
/*
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; });
}
/*
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();
}
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 <= n-1
- 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 shunting-yard version
reference: wikipedia / Shunting-yard_algorithm
Simplified for the problem:
- two stack, one for the numbers that need to be fed into a binary-operation
- 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 Bin-Operators 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-((4-7)*3/1)\n"
"1+(2-3)*4+5-6*8-(18*12*13)-(11/(5+2+4))\n"
"((2+4)/3-2+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;
}
/*
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-((4-7)*3/1)\n"
"1+(2-3)*4+5-6*8-(18*12*13)-(11/(5+2+4))\n"
"((2+4)/3-2+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;
}
Approach 1: use a hashtable, O(1) to insert and O(n) to check
Approach 2: any form of sorted container, AVL, B-Tree, ... for O(lg(n)) insert and with vucuong020195 method to test
From the big-o 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 = m-1: 1
\ if y = n-1: 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 y-dimension = 0");
m = matrix[0].size();
if (m == 0) throw invalid_argument("matrix x-dimension = 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;
}
1) it is finding the k-thary element and return it and all that are smaller
2) A modified quick-sort 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() << ")" << "}"; }
// quick-sorts 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 = s-1; // 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 k-smallest 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();
}
1) use BFS (shortest path with no weights on edge)
2) implement no nodes and no edges, just keep the parent-pointer of the BFS traversal tree as coordinates in the chess-board
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 BFS-traversal points to it self (avoid loop over "back-edge" 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)))
/*
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();
}
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 integer-array
#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
*/
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 (c-a <= 0) return;
if (d-b <= 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
*/
it's a DP problem:
c[i]=max(c[i-l]+l, c[i-l]) / if a match (length l) was found, for all matches ending at position i
c[i]=c[i-1] / 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();
}
Repednaheeks, Android test engineer at Automated Traders Desk
I am Edna, a blogger . As an editor with a strong background in English and Hindi language. I enjoy writing ...
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 ...
how much memory do we have? how many words?
- Chris October 18, 2016this 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 hash-value 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 big-O but practically). Use a bit-array 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 hash-value is in there...)