Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Could you provide the link of this problem in codechef? I just curious how to solve it... Thanks!
Wow, you have to use heavy-light decomposition on array, then by karatsuva algoithm with persistent segment tree you can get a polynomial, but to convert it you have to apply discrete fourier transform and then by jhonson's algorihm you will get the ans.
Hope you will get it, or feel free to ask me :)
Looks like a good interview question with scope for extending question to solve for cases where #elements is very large / #evaluations is very large
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class FunctionEvaluator {
int n;
int[] a;
int[][] fD;
public FunctionEvaluator(int n, List<Integer> val) {
this.n = n;
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = val.get(i);
}
fD = new int[n][2];
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new FileReader(args[0]));
// read elements
String line;
line = in.readLine().trim();
int n = Integer.parseInt(line);
List<Integer> l = new LinkedList<Integer>();
line = in.readLine();
String token[] = line.split(" ");
for (String s : token) {
int x = Integer.parseInt(s);
l.add(x);
}
FunctionEvaluator wrapper = new FunctionEvaluator(n, l);
List<Integer> left = new LinkedList<Integer>();
List<Integer> right = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
line = in.readLine();
token = line.split(" ");
int x1 = Integer.parseInt(token[0]);
int x2 = Integer.parseInt(token[1]);
left.add(x1);
right.add(x2);
}
wrapper.setFunctionData(left, right);
// edits / evaluatiosn
line = in.readLine().trim();
int k = Integer.parseInt(line);
for (int i = 0; i < k; i++) {
line = in.readLine();
token = line.split(" ");
int opType = Integer.parseInt(token[0]);
int x1 = Integer.parseInt(token[1]);
int x2 = Integer.parseInt(token[2]);
if (opType == 1) {
wrapper.setElement(x1, x2);
} else {
int res = wrapper.evaluate(x1, x2);
System.out.println(res);
}
}
}
// using brute force
int evaluate(int begin, int end) {
int res = 0;
for (int i = begin - 1; i < end; i++) {
res += evaluate(i);
}
return res;
}
int evaluate(int fi) {
int res = 0;
for (int j = fD[fi][0]-1; j < fD[fi][1]; j++) {
res += a[j];
}
System.out.println("DEBUG fi=" + fi + "\t(" + fD[fi][0] + "," + fD[fi][1] + ") " + res);
return res;
}
void setElement(int i, int val) {
a[i - 1] = val;
System.out.println("DEBUG " + Arrays.toString(a));
}
private void setFunctionData(List<Integer> left, List<Integer> right) {
for (int i = 0; i < n; i++) {
fD[i][0] = left.get(i);
fD[i][1] = right.get(i);
}
}
}
My very basic solution: for each value in the array, just keep track of affected functions.
class Function {
int li, ri, value;
void computeValue(List<Number> numbers) {
value = 0;
for (int j = li; j <= ri; j++) {
value += numbers.get(j-1).value;
}
}
}
class Number {
public Number(int value) {
this.value = value;
}
int value;
List<Function> affectedFunctions = new ArrayList<>();
}
void queriesAndFunctions(InputStream is) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(is));
int N = Integer.parseInt(bf.readLine());
List<Number> numbers = new ArrayList<>();
String[] numberStrs = bf.readLine().split("\\ ");
for (int i = 0; i < N; i++) {
numbers.add(new Number(Integer.parseInt(numberStrs[i])));
}
List<Function> functions = new ArrayList<>();
for (int i = 0; i < N; i++) {
Function func = new Function();
String[] extremes = bf.readLine().split("\\ ");
func.li = Integer.parseInt(extremes[0]);
func.ri = Integer.parseInt(extremes[1]);
func.computeValue(numbers);
for (int j = func.li; j <= func.ri; j++) {
numbers.get(j-1).affectedFunctions.add(func);
}
functions.add(func);
}
int Q = Integer.parseInt(bf.readLine());
for (int i = 0; i < Q; i++) {
String[] queryPars = bf.readLine().split("\\ ");
int type = Integer.parseInt(queryPars[0]);
int arg1 = Integer.parseInt(queryPars[1]);
int arg2 = Integer.parseInt(queryPars[2]);
if (type == 1) {
Number num = numbers.get(arg1-1);
num.value = arg2;
for (Function func : num.affectedFunctions) {
func.computeValue(numbers);
}
} else if (type == 2) {
int sum = 0;
for (int f = arg1-1; f < arg2; f++) {
sum += functions.get(f).value;
}
System.out.println(sum);
}
}
}
I didn't understand this test. Could you please what are these functions and this Type1 and Type2?
- ftonello November 12, 2014