Amazon Interview Question for SDE-2s


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Chris August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n-1 operations to build the sum, and n-1 to distribute (if you draw it), but that's not really the matter

- Chris August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You Can reduce to Single pass by using copy on Write and sharing the data object of each node but still it is O(n) solution.

There is no way you can do it faster than that, as you must visit all nodes to get its content

- hprem991 August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@hprem991 how does copy on write work?

- Chris August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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 August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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?

- Chris August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- hprem991 August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- hprem991 August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@hprem991:
"each node has a function called updateOnWrite()" that means when I write, each node is called. I write n times, I call n times each node... code it, believe me, what you are talking about doesn't exist. I know this patterns quite well ;-)

- Chris August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK,

I got what you are saying, you are talking about for every update you have to call up the nodes to update it content.

what if we always point a node.value to the value of a global variable? I'll try to give you a code later after work, but I think I can make it work.

- hprem991 August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ben August 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't it possible to make parallel calculations?
Then the solution will be O(2*log(n)).

- Azamat August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution is something called a graph's diameter.

It can be solved in O(N) using 2 BFS.

- Ted October 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous November 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Alex November 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can convert it to K centres problem to find value for this in the more general case.

- karankapoor.nsit October 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- smartboy October 12, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More