String Formatting Question - Smartprix Coding Test

Replacement Array is an array of elements.
Format String contains conversion specifier %s, followed by optional index specifier [1], followed by optional length specifier :3.
Format String: %s[1]:3
%s is conversion specifier - mark the starting of conversion string
[1] is index specifier - corresponding index of Replacement Array
:3 is length specifier - number of characters to be taken from string



The replacement works as follows:
Example:
Replacement Array: Smart site India comparison Best
Format String: %sprix is the %s[4] online %s[3]:6 shopping %s:9 in %s
Output: Smartprix is the Best online compar shopping site in India.
If no index specifier is present with conversion specifier %s, Index 0, 1, 2, 3... are assigned to all in sequence from left to right.
In above example %sprix is %s[0]prix; %s:9 is %s[1]:9 and so on.
The specifier string is replaced by element of Replacement Array denoted by index specifier. If no element is found the specifier is not replaced.
In above example %s[4] is replaced by element at 4th index of the Replacement Array "Best". %sprix is replaced by Smartprix and so on.
%s[3]:6 is replaced by 'first 6 characters' of the element at 3rd index of the Replacement Array, i.e., "compar".
If the 'length specifier' is not present or is greater than length of the element then use whole string.
%s:9 is replaced by site, %s[4] is replaced by Best.
For any error case, specifier is not replaced.



Input:
There will be 2 lines in the input.
1st line contains space separated elements of Replacement Array
2nd line is Format String



Output:
Formatted String



INPUT 1
smart site india comaprision best
%sprix is the %s[4] online %s[3]:6 shopping %s:9 in %s
OUTPUT
smartprix is the best online comapr shopping site in india


INPUT 2
india boom startup up hub
%s %s[is] a %sing %s:5%s:5 %s[4]. and %s[6] are :4 of %s[-1].
OUTPUT
india %s[is] a booming startup hub. and %s[6] are :4 of %s[-1].


INPUT 3
hello lavish kothari
%s[2]:xyz
OUTPUT
%s[2]:xyz

#include<bits/stdc++.h>
using namespace std;

int findCase(string &b,int index)
{
    if(index+2>=b.size())
        return 1;
    /*
    if(b[index+2]!=':' && b[index+2]!='[')
        return 1;
    */
    
    if(b[index+2]==':' && index+3<b.size() && b[index+3]>='0' && b[index+3]<='9')
        return 4;
    if(b[index+2]==':')
        return 0;
    
    if(b[index+2]=='[')
    {
        int i=index+3;
        if(i>=b.size() || b[i]<='0' || b[i]>='9')
            return 0;
        while(i<b.size() && b[i]>='0' && b[i]<='9')
            i++;
        if(i==b.size())
            return 0;           // for case %s[1234
        else if(b[i]==']')
        {
            if(i+1>=b.size() || b[i+1]!=':')
                return 2;
            else if(b[i+1]==':')
            {
                if(i+2>=b.size())
                    return 0;
                else if(b[i+2]>='0' && b[i+2]<='9')
                    return 3;
                else
                    return 0;
            }
        }
        else return 1;
    }
    return 1;
}
int extract(string &b,int index)
{
    int sum=0;
    while(index<b.size() && b[index]>='0' && b[index]<='9')
    {
        sum=sum*10+b[index]-'0';
        index++;
    }
    return sum;
}
void findFormattedString(string &a,string &b)
{
    vector<string>vs;
    int start=0;int len=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==' ')
        {
            vs.push_back(a.substr(start,len));
            while(i<a.size() && a[i]==' ')
                i++;
            start=i;
            len=0;
        }
        len++;
    }
    if(a[a.size()-1]!=' ')
        vs.push_back(a.substr(start,a.size()-start));
    
    /*
    for(int i=0;i<vs.size();i++)
        cout<<"**"<<vs[i]<<endl;
    */
    int counter=0,startfrom=0;
    while(1)
    {
        int index=b.find("%s",startfrom);
        if(index<0)
            break;
        int c=findCase(b,index);
        if(c==1)
        {
            if(counter>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            b.erase(b.begin()+index,b.begin()+index+2);
            b.insert(index,vs[counter]);
            counter++;
        }
        else if(c==2)
        {
            int number=extract(b,index+3);
            if(number<0 || number>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i+1);
            b.insert(index,vs[number]);
        }
        else if(c==3)
        {
            int number1=extract(b,index+3);
            if(number1<0 || number1>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i+2);
            
            int number2=extract(b,index);
            i=index;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i);
            
            if(vs[number1].size()<=number2)
            {
                b.insert(index,vs[number1]);
            }
            else 
                b.insert(index,vs[number1].substr(0,number2));
        }
        else if(c==4)
        {
            if(counter>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int number=extract(b,index+3);
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i);
            if(vs[counter].size()<=number)
            {
                b.insert(index,vs[counter++]);
            }
            else 
                b.insert(index,vs[counter++].substr(0,number));
        }
        else if(c==0)
            startfrom=index+1;
    }
}
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    findFormattedString(a,b);
    cout<<b<<endl;
    return 0;
}

Water Jug Problem (Oracle Interview)

This problem was asked to me during my Oracle interview. The interviewer asked me to write down the code for the same.
 
Problem :

You are given three water jugs.
Let the capacity of jugs be X, Y and Z. (X >= Y >= Z).
As described in all common water jug problems, neither of the jugs has any measuring markers on it.

Initially we have only the first jug (with capacity X) fully filled up to brim (the other two jugs are initially empty).
Now you need to tell whether it is possible or not to transfer the water, in such a way that you reach to a state in which any two jugs have equal amount of water in them, and the third jug is empty.
In short, you have to divide X litre of water into two equal halves. These two equal halves can be in any of the two jugs.

Example
Suppose, X=10, Y=7, Z=3
Solution steps:
10 0 0 -> Initial State
3 7 0
0 7 3
7 0 3
7 3 0
4 3 3
4 6 0
1 6 3
1 7 2
8 0 2
8 2 0
5 2 3
5 5 0 -> Final State


C++ Program to solve this problem :

#include<bits/stdc++.h>
using namespace std;
class triplet
{
    public:
    int x,y,z;
    triplet(int x,int y,int z)
    {
        this->x=x;
        this->y=y;
        this->z=z;
    }
    
};
bool findTriplet(vector<triplet>&v,int x,int y,int z)
{
    for(int i=0;i<v.size();i++)
        if(v[i].x==x && v[i].z==z && v[i].y==y)
            return true;
    return false;
}
bool getSteps(int x,int y,int z,int X,int Y,int Z) // x y and z denotes the current capacity.
{
    static vector<triplet>v;
    if(findTriplet(v,x,y,z))
        return false;
    else 
        v.push_back(triplet(x,y,z));
    cout<<x<<" "<<y<<" "<<z<<endl;
    if(x==y && z==0)
        return true;
    if(z==y && x==0)
        return true;
    if(x==z && y==0)
        return true;
    
    /*********************************--> transferring from X <--*****************************************************/        
    if(x>0)
    {
        // transferring from x to y
        {
        int emptyy=Y-y;
        int newx,newy;
        if(emptyy>=x)
        {
            newy=y+x;
            newx=0;
        }
        else
        {
            newy=Y;
            newx=x-emptyy;
        }
        if(emptyy>0 && getSteps(newx,newy,z,X,Y,Z))
            return true;
        }
    
        // transferring from x to z
        {
        int emptyz=Z-z;
        int newx,newz;
        if(emptyz>=x)
        {
            newz=z+x;
            newx=0;
        }
        else
        {
            newz=Z;
            newx=x-emptyz;
        }
        if(emptyz>0 && getSteps(newx,y,newz,X,Y,Z))
            return true;
        }
    }
            
    /*********************************--> transferring from Y <--*****************************************************/        
    if(y>0)
    {
        // transferring from y to x
        {
        int emptyx=X-x;
        int newx,newy;
        if(emptyx>=y)
        {
            newx=x+y;
            newy=0;
        }
        else
        {
            newx=X;
            newy=y-emptyx;
        }
        if(emptyx>0 && getSteps(newx,newy,z,X,Y,Z))
            return true;
        }
    
        // transferring from y to z
        {
        int emptyz=Z-z;
        int newy,newz;
        if(emptyz>=y)
        {
            newz=z+y;
            newy=0;
        }
        else
        {
            newz=Z;
            newy=y-emptyz;
        }
        if(emptyz>0 && getSteps(x,newy,newz,X,Y,Z))
            return true;
        }
    }
            
    /*********************************--> transferring from Z <--*****************************************************/        
    if(z>0)
    {
        // transferring from z to y
        {
        int emptyy=Y-y;
        int newz,newy;
        if(emptyy>=z)
        {
            newy=y+z;
            newz=0;
        }
        else
        {
            newy=Y;
            newz=z-emptyy;
        }
        if(emptyy>0 && getSteps(x,newy,newz,X,Y,Z))
            return true;
        }
    
        // transferring from z to x
        {
        int emptyx=X-x;
        int newz,newx;
        if(emptyx>=z)
        {
            newx=z+x;
            newz=0;
        }
        else
        {
            newx=X;
            newz=z-emptyx;
        }
        if(emptyx>0 && getSteps(newx,y,newz,X,Y,Z))
            return true;
        }
    }
    return false;
}
int main()
{
    int x,y,z;
    cin>>x>>y>>z;
    if(getSteps(x,0,0,x,y,z))
        cout<<"Yes!! you got a solution!!"<<endl;
    else cout<<"No solution found!!"<<endl;
    return 0;
}

Please write comments if you find anything incorrect, or you want to share more information about the problem discussed above.