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

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

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.

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.