How to increment values (multiple in a continuous sequence) in a std::vector in O(1) time?

user_7971339 0
Viewed 259

ELABORATED and SIMPLIFIED-----------------------------------------------------------

The question I was asked in the coding interview required me to implement a stack. The skeleton of the class was provided with function definitions given as well. However, there was no logic inside the definitions.

class myStack {
    f1(args) {//no logic I have to code it}
    f2(args) {//no logic I have to code it}
    ........
};

These functions had to be implemented with run-time O(1). I could get simpler ones done, however, there was an increment function which I could not. (Look at comment in code section below)


void incre(int number, int increment) {
/* In this function, implement logic to implement increment of "number"
elements from the bottom of the stack by "increment".

incre(3, 5) -> means increment 3 elements from bottom of stack. Increment each by 5

*/
}

It was this function that posed a challenge as I had to do the operation in amortized O(1) time.

vec = 1 2 3 4 5
    + 1 1 1 1             // how to in O(1) time instead of loop?
vec = 2 3 4 5 5

The stack was implemented as a vector data structure inside the class by me. Since I implemented the function as a loop, I probably failed test cases.

So how to do it in O(1) time? Any data structure that could help?

c++
2 Answers

The question lacks important details. In general, it’s impossible to increment an arbitrary range of elements in O(1) time. There must be additional constraints that make it possible.

The question mentions a stack but doesn’t go into further detail. Reading between the lines it could mean that the problem asks for a stack with regular push and pop operations plus bulk increment for a range. The stack “access pattern”, i.e. elements are consumed sequentially, enables increment in O(1) time.

The key idea is to maintain a parallel array of increments. I-th item, increments[i], encodes an argument to a bulk increment operation for the range [0, i]. It starts as 0 initially. Bulk increment operation simply updates a single item in increments, which is clearly O(1) operation.

Returning a container item a[i] clearly requires a summation of increments[i] till increments[N], where N is the total size of the container. Only the last item can be produced efficiently, but that’s ok for a stack.

The pop operation should increment increments[N-1] by increments[N] prior to reducing the container size by 1.

user_44339690

As Nick answered on his post, you could try to record the increment with the corresponding value on the stack and update it just before retrieving, also passing the increment to the next position on the stack, skipping the loop entirely.

I will preserve my old answer just because it is interesting for people wanting to learn more about SIMD:

You can do that (under very limited circumstances) with SIMD.

O(1) means constant time and you may be able to do that if your vector is very small. Lets say you have an aligned vector of floats with capacity of 4 and a maximum size of 4. You could load all the vector in a single register and use a single SIMD operation to update the values of the 4 positions simultaneously. It is probably not what you wanted, but it is worth mentioning it here. For the other cases where a loop is needed, using SIMD - despite not being O(1) -, can also speed up computation significantly, and as a matter of fact, it is frequently used for operating images in memory.

SSE and AVX (NEON too in ARM) instruction sets allow you to use a 128bits or 256bits register to place 2, 4 or 8 numbers and operate them simultaneously.

You can do that using OMP SIMD (more high level) or intrinsics (low level). Or just rely on compiler optimization. If you want to use multiple threads, you can use OMP PARALLEL FOR (probably not worth in this case though).

user_60503640
Related