Amazon Interview Question
SDE-2sCountry: United States
I assume only positive values > 0.
I fully agree with your conclusion, it means you need to visit each node to build the sum in on node and then visit again each node to copy that value to all other nodes.
I guess the question aims, what path should you take to achieve 2*(no of nodes) time units. I think you are looking at a minimum spanning tree to calculate and distribute the sum (I think there are two one should really know, but I actually need to look them up as well).
An other point of view could be, to calculate the sum, you need to see each value. there is no way you can build a sum on elements without having at least once seen all elements values. Then, since you need to copy it to all other nodes, there is no other way than visiting each node again. So, 2*n is best conceivable, I don't think you can do better either.
@ChrisK
There are multiple ways to implement it.
Design Patterns like observers can be used as well as you can set a reference of each node.data value to some common address and update that common memory location updating everynode while you calculate the total sum. Last value updated will be the value of all node.
@hprem991: I understand, maybe you could code that O(n) solution that uses only one pass to create the sum and distribute it to all nodes, assuming we had a minimal spanning tree. Maybe just with an array, calculate the sum of an array and set each element to that value. Are you sure you don't create an O(n^2) solution that just looks like O(n) on the surface?
@ChrisK,
Nope, I dont think you got what I suppose to mean.
Think you are updating a static / global variable every time you visit a node and each Node has to update its value if the value of this global / static variable is changed, that what copy on write me. Someone has rewritten the data and your data is dirty forcing a node to update its content.
Each node update its content independently.
@ChrisK
Nope, I dont think you got it.
Think you have a global / static variable holding a sum of all the node.value visited so far. Now each node has a function called updateOnWrite(); which updates it node.value if this global value changes it content. That what copy on write means, someone over written a value and you have to update you content.
Each node updates it value independently.
I think there is a solution better than 2*(n-1).
The total is n*(n+1)/2. This needs to be propogated to every node in the graph.
This can be done in approximately n + n/2 steps.
Outline of algorithm:
(For small n, this algorithm is not optimtal. For instance, for n=2
the best answer is 2 steps.)
Assume a 1-based array A, with numbers 1 through n (there is no A[0]).
Add A[n] to A[n-1] for (n+1)/2 - 1 times (or n/2 - 1 times). For even n,
add in the missing half, otherwise just add the missing 1. Then push
A[n-1] to the rest of the graph.
int count = 0;
if (n & 1) { // if n is odd
// n+1 is even, this is a whole number
count = (n+1)/2 - 1;
A[n-1] += A[1]; // 1 step
} else { // else, n is even
count = n/2 - 1;
A[n-1] += A[n/2 + 1]; // 1 step
}
// This for loop sets A[n-1] to n*(n+1)/2, the total sum
for (int i=1; i<=count; i++) {
A[n-1] += A[n]; (n+1)/2 steps if n is odd, or n/2 if even
}
// propogate the value to the rest of the graph
for (int i=1; i<=n; i++) {
if (i == n-1)
continue;
A[i] = A[n-1]; // n-1 steps
}
// If n is odd:
// Total steps: n + (n+1)/2 steps
// If n is even:
// Total steps: n + n/2 steps
O(n) time, O(1) space.
#include <vector>
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
}
void Connect(Node *to_node)
{
for (auto n : adjacent_nodes_) {
if (n == to_node) {
return;
}
}
adjacent_nodes_.push_back(to_node);
to_node->Connect(this);
}
int val_;
vector<Node *> adjacent_nodes_;
};
void DistributeSum(Node *node)
{
int sum = 0;
for (Node *n = node; n != NULL;) {
sum += n->val_;
n->val_ = numeric_limits<int>::min();
Node *next_n = NULL;
for (int i = 0; i < n->adjacent_nodes_.size() && next_n == NULL; ++i) {
if (n->adjacent_nodes_[i]->val_ != numeric_limits<int>::min()) {
next_n = n->adjacent_nodes_[i];
}
}
n = next_n;
}
node->val_ = sum;
for (auto to_node : node->adjacent_nodes_) {
to_node->val_ = sum;
}
}
int main(int argc, char const **argv)
{
Node n1(1), n2(2), n3(3), n4(4), n5(5);
n1.Connect(&n2);
n1.Connect(&n3);
n1.Connect(&n4);
n1.Connect(&n5);
n2.Connect(&n3);
n2.Connect(&n4);
n2.Connect(&n5);
n3.Connect(&n4);
n3.Connect(&n5);
n4.Connect(&n5);
DistributeSum(&n5);
cout << n1.val_ << ", ";
for (auto to_node : n1.adjacent_nodes_) {
cout << to_node->val_ << ", ";
}
cout << "\n";
return 0;
}
Fixed to actually O(n) (I accidentally posted O(n^2) as Anonymous).
#include <vector>
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
}
void Connect(Node *to_node)
{
for (auto n : adjacent_nodes_) {
if (n == to_node) {
return;
}
}
adjacent_nodes_.push_back(to_node);
to_node->Connect(this);
}
int val_;
vector<Node *> adjacent_nodes_;
};
void DistributeSum(Node *node)
{
if (node) {
int sum = node->val_;
for (auto to_node : node->adjacent_nodes_) {
sum += to_node->val_;
}
node->val_ = sum;
for (auto to_node : node->adjacent_nodes_) {
to_node->val_ = sum;
}
}
}
int main(int argc, char const **argv)
{
Node n1(1), n2(2), n3(3), n4(4), n5(5);
n1.Connect(&n2);
n1.Connect(&n3);
n1.Connect(&n4);
n1.Connect(&n5);
n2.Connect(&n3);
n2.Connect(&n4);
n2.Connect(&n5);
n3.Connect(&n4);
n3.Connect(&n5);
n4.Connect(&n5);
DistributeSum(&n5);
cout << n1.val_ << ", ";
for (auto to_node : n1.adjacent_nodes_) {
cout << to_node->val_ << ", ";
}
cout << "\n";
return 0;
}
the answer should b n*(n-1) as there each vertex will be connected to all other nodes and all needs to be added so will take n-1 time, thus for n nodes it will take n*(n-1) time. Say n=4, then total sum for all nodes {1,2,3,4} is 10, which we can make by adding other nodes to 1st node. Similarly, for 2nd,3rd and 4th. thus total time= 3+3+3+3=12.
Career Cup is soo messed up, you cant update / delete your comments and sometimes it wont post what we have submitted making us to resubmit again ??
- hprem991 August 14, 2017