Amazon Interview Question for SDE-3s


Country: United States
Interview Type: In-Person




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

point update? do you mean element update?
fenwick-tree, segment-tree if both queries have about same frequencies
an array with the calculated sum, if much more range queries occure than element ubdates
an array where I calculate the sum every time it is asked, if much more element updates happen than range queries

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

O(log n) time for the update and range sum queries, using Binary Indexed Tree.

#include <vector>
#include <iostream>

using namespace std;

class BinaryIndexedTree {
	public:
		BinaryIndexedTree(int size)
		{
			a_.resize(size + 1, 0);
		}
		void Update(int idx, int diff)
		{
			for (int i = idx + 1; i < a_.size(); i += i & -i) {
				a_[i] += diff;
			}
		}
		int GetSum(int idx) const
		{
			int sum = 0;
			for (int i = idx + 1; i > 0; i -= i & -i) {
				sum += a_[i];
			}
			return sum;
		}
	private:
		vector<int> a_;
};

class SumTracker {
	public:
		SumTracker(int size) : tree_(size)
		{
			a_.resize(size, 0);
		}
		void Update(int idx, int val)
		{
			int diff = val - a_[idx];
			a_[idx] = val;
			tree_.Update(idx, diff);
		}
		int RangeSum(int idx1, int idx2) {
			return tree_.GetSum(idx2) - tree_.GetSum(idx1 - 1);
		}
		int Size() const
		{
			return a_.size();
		}
	private:
		vector<int> a_;
		BinaryIndexedTree tree_;
};

int main(int argc, char const **argv)
{
	SumTracker t(10);
	for (int i = 0; i < t.Size(); ++i) {
		t.Update(i, i + 1);
	}
	cout << t.RangeSum(3, 5) << "\n";
	return 0;
}

- Alex November 15, 2017 | 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