Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
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;
}
point update? do you mean element update?
- Chris August 31, 2017fenwick-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