Given a set vectors of integers v1 and v2, implement an iterator to return their elements alternately.
Implement the ZigzagIterator methods.
Simple problem but multiple solutions.
- Solution 1: If the pointers passed at create time are temp. pointers and if we have to allocate for entire set of vectors, simply calculate the total number of elements and allocate memory for total number of elements copy vector elements alternately and maintain current index. This solution has space overhead in case if we can reuse vectors addresses.
- Solution 2: Simple solution , where we maintain array of vectors, vectors sizes, current vector indices, next vector-id, etc. In next() function save the value from vector pointing to next-vector-id and id pointing to that vector index. Increment vector index and next-vector-id.
Find the next vector-id where the vector is still having some elements. This involves a small while loop. - Solution 3: I learnt it now. Maintain Queue of vectors. In C, we better use only array, but treat that array as Queue. This queue will only have active vectors. For this we maintain number of active vectors. If any current vector is exhasted with elements, overwrite that vector information with the active vector which is pointing at the last active index. Decrement the active vectors count.
I have implemented this solution and submitted which worked fine. But now I am getting doubt why no failures.
One example:
Input vectors v1:[1,2,3], v2=[91], v3=[21,34], v4=[9,8,7,6]
output1: 1,
output2: 91
This v2 is no longer required,
overwrite with v4.
then existing data will be: v1=[2,3],v2=[9,8,7,6], v3[21,34]
output3:21, output4:2,
output4 will be 2 which is wrong, actual expected should 9.
Now I understood why that solution worked, It worked because number of vectors are only 2.
In case if any vector is exhausted, we should move back the vectors next to it, which involves a while loop with small code segment.
So we should not call it as a queue because we are not deleting vectors in FIFO order.
We should call it as set of active vectors.
- Solution 4: We can still do another optimization. We need not maintain the set of current vector indices. We can only maintain one vector index. We can increment this vector index for every cycle (after visiting all the vectors once).
Solution 2 implementation:
struct ZigzagIterator {
int **vectors; // set of vectors
int *v_sizes; // vectors sizes
int *c_vids; // current indices of each vector
int numv; // number of vectors
int nxt_vid; // next vector index to be selected
int hasNext; // true if iterator still has elements, else false
};
struct ZigzagIterator *zigzagIteratorCreate(int* v1, int v1Size, int* v2, int v2Size) {
struct ZigzagIterator *it;
it = (struct ZigzagIterator *) calloc(1, sizeof(struct ZigzagIterator));
it->vectors = (int **)calloc(2, sizeof(int*));
it->v_sizes = (int *)calloc(2, sizeof(int));
it->c_vids = (int *)calloc(2, sizeof(int));
it->vectors[0] = v1;
it->vectors[1] = v2;
it->v_sizes[0] = v1Size;
it->v_sizes[1] = v2Size;
it->hasNext = 1;
it->numv = 2;
if (v1Size)
it->nxt_vid = 0;
else if (v2Size)
it->nxt_vid = 1;
else
it->hasNext = 0;
return it;
}bool zigzagIteratorHasNext(struct ZigzagIterator *iter) {
return iter->hasNext;
}int zigzagIteratorNext(struct ZigzagIterator *iter) {
int vid = iter->nxt_vid, ret, nvid;
if (!iter->hasNext)
return -1;
ret = iter->vectors[vid][iter->c_vids[vid]];
iter->c_vids[vid] ++;
vid = (vid+1) % iter->numv;
while ((iter->c_vids[vid] == iter->v_sizes[vid]) &&
(vid != iter->nxt_vid))
vid = (vid+1) % iter->numv;
if ((vid == iter->nxt_vid) && (iter->c_vids[vid] == iter->v_sizes[vid]))
iter->hasNext = 0;
iter->nxt_vid = vid;
return ret;
}/** Deallocates memory previously allocated for the iterator */
void zigzagIteratorFree(struct ZigzagIterator *iter) {
/*for (int ii=0;ii<iter->numv; ii++)
free(iter->vectors[ii]); not allocated for iter*/
free(iter->vectors);
free(iter->c_vids);
free(iter->v_sizes);
free(iter);
return;
}
Solution 3 implementation:
struct ZigzagIterator {
int **Avectors; // set of active vectors
int *v_sizes; // vectors sizes
int *c_vids; // current indices of each vector
int actv; // number of active vectors
int nxt_vid; // next vector index to be selected
int hasNext; // true if iterator still has elements, else false
};
struct ZigzagIterator *zigzagIteratorCreate(int* v1, int v1Size, int* v2, int v2Size) {
struct ZigzagIterator *it;
it = (struct ZigzagIterator *) calloc(1, sizeof(struct ZigzagIterator));
it->Avectors = (int **)calloc(2, sizeof(int*));
it->v_sizes = (int *)calloc(2, sizeof(int));
it->c_vids = (int *)calloc(2, sizeof(int));
it->Avectors[0] = v1;
it->Avectors[1] = v2;
it->v_sizes[0] = v1Size;
it->v_sizes[1] = v2Size;
it->hasNext = 1;
it->actv = 2;
if (v1Size){
it->nxt_vid = 0;
if (!v2Size)
it->actv--;
}
else if (v2Size){
it->nxt_vid = 0;
it->Avectors[0] = v2;
it->v_sizes[0] = v2Size;
it->actv --;
}
else
it->hasNext = 0;
return it;
}bool zigzagIteratorHasNext(struct ZigzagIterator *iter) {
return iter->hasNext;
}int zigzagIteratorNext(struct ZigzagIterator *iter) {
int vid = iter->nxt_vid, ret, nvid;
int *tmpp, tmpi;
if (!iter->hasNext)
return -1;
ret = iter->Avectors[vid][iter->c_vids[vid]];
iter->c_vids[vid] ++;
/* If all elements of vector is returned,
remove from queue (move back all vectors next to it )
*/
if (iter->c_vids[vid] == iter->v_sizes[vid]){
for (int ii= vid; ii<iter->actv-1; ii++) {
iter->Avectors[ii] = iter->Avectors[ii+1];
iter->c_vids[ii] = iter->c_vids[ii+1];
iter->v_sizes[ii] = iter->v_sizes[ii+1]; }
iter->actv--;
}
if (!iter->actv){
iter->hasNext = 0;
return ret;
}
vid = (vid+1) % iter->actv;
iter->nxt_vid = vid;
return ret;
}/** Deallocates memory previously allocated for the iterator */
void zigzagIteratorFree(struct ZigzagIterator *iter) {
/*for (int ii=0;ii<iter->numv; ii++)
free(iter->vectors[ii]); not allocated for iter*/
free(iter->Avectors);
free(iter->c_vids);
free(iter->v_sizes);
free(iter);
return;
}
Please provide your comments.
