Amazon Interview Question
SDE-2sCountry: United States
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>
class SqrtDecomposition {
public:
SqrtDecomposition(const std::vector<int>& array) {
n = array.size();
blockSize = std::sqrt(n);
blocks = std::vector<int>((n + blockSize - 1) / blockSize, std::numeric_limits<int>::min());
for (int i = 0; i < n; ++i) {
blocks[i / blockSize] = std::max(blocks[i / blockSize], array[i]);
}
this->array = array;
}
int query(int L, int R) {
int maxVal = std::numeric_limits<int>::min();
while (L % blockSize != 0 && L <= R) {
maxVal = std::max(maxVal, array[L++]);
}
while (L + blockSize <= R) {
maxVal = std::max(maxVal, blocks[L / blockSize]);
L += blockSize;
}
while (L <= R) {
maxVal = std::max(maxVal, array[L++]);
}
return maxVal;
}
private:
std::vector<int> blocks;
std::vector<int> array;
int n;
int blockSize;
};
int main() {
std::vector<int> nums = {1, 5, 4, 3, 6, 7, 2};
SqrtDecomposition sd(nums);
// Example queries
std::cout << "Max between [1, 3]: " << sd.query(1, 3) << std::endl;
std::cout << "Max between [0, 6]: " << sd.query(0, 6) << std::endl;
std::cout << "Max between [4, 5]: " << sd.query(4, 5) << std::endl;
return 0;
}
Can be solved using Segment Tree
- kautscoding July 13, 2020