## Flipkart Interview Question

• 0

Country: India
Interview Type: Phone Interview

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

1. Keep the sum array which holds the total sum from beginning to the index
2. Every time a subtract/add happens, add/subtract the value from the sum array after the index i

Comment hidden because of low score. Click to expand.
2

By doing so, the total sum would O(1), and add/subtract will be O(n).

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

segment tree

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

To do both operations efficiently, I would go for a Binary Indexed Tree (also known as Fenwick Tree). This supports operations 1 and 2 in O(log N) time, O(N) space.

``````int tree[MAX], N; // indices 1..N

void Update(int x, int value) {
for (; x <= N; x += (x & -x))
tree[x] += val;
}
void GetSum(int x) {
int sum = 0;
for (; x > 0; x -= (x & -x))
sum += tree[x];
return sum;
}``````

Check community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

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

The interviewer is a poor interviewer.

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

i think the Fenwick tree for sum on array could be more appropriate. It compute sum from range [L,R] bt O(lgN) and change operation for O(lgN)

Comment hidden because of low score. Click to expand.
2

This is the optimal solution (considering both operations).

But the question is unreasonable for interviews. Very unreasonable.

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

Okay, this is my solution which uses O(sqrt N) space, operation 1 can be done in O(sqrt x) and operation 2 can be done in O(1). Worse time complexity than Fenwick tree but better space complexity and better complexity for operation 2.

Store sums in an array s like this:

s = sum(arr[0^2..1^2])
s = sum(arr[1^2..2^2])
s = sum(arr[2^2..3^2])
s = sum(arr[3^2..4^2])
s = sum(arr[4^2..5^2])
.
.

Extra space = O(sqrt N)

Now operation 1 can be done by adding elements of s from 0 to floor(sqrt x) + elements of arr from 2^(floor(sqrt x)) to x = O(sqrt x)

Operation 2 can be done in O(1) time, just add/subtract value t from the corresponding element in s.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

If the array has say a 100,000 elements.
Then create a map <index,sum>
map = sum of first 1000 elements
map = sum of elements 1001 to 2000
..
..
map = sum of last 1000 elements

If 10001 element is modified. Then the value of map should also be modified.

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.