CareerCup

//remove duplicates from result

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

#define MAX_ROW 4
#define MAX_COLUMN 3

struct ArrayIndex
{
    int rowIndex;
    int columnIndex;
    int direction;
   
};

void getNextIndex(struct ArrayIndex* obj,vector<struct ArrayIndex> *IntermediateIndex,int directionIncluded)
{
    int rowIndex =  obj->rowIndex;
    int columnIndex = obj->columnIndex;
    int direction = obj->direction;
    struct ArrayIndex IntermediatePos;
    if(directionIncluded)
    {
        if(direction)
        {
            //change columnIndex
            if ((0<= (columnIndex + 1) )&&((columnIndex + 1)<MAX_COLUMN ))
            {
                IntermediatePos.rowIndex = rowIndex;
                IntermediatePos.columnIndex= columnIndex +1;
                IntermediatePos.direction= 0;
                IntermediateIndex->push_back(IntermediatePos);
            }  
            if ((0<= (columnIndex - 1) )&&((columnIndex - 1)<MAX_COLUMN ))
            {
                IntermediatePos.rowIndex = rowIndex;
                IntermediatePos.columnIndex= columnIndex - 1;
                IntermediatePos.direction= 0;
                IntermediateIndex->push_back(IntermediatePos);
            }  
        }
        else
        {
            //change rowIndex
            if ((0<= (rowIndex + 1) )&&((rowIndex + 1)<MAX_ROW ))
            {
                IntermediatePos.rowIndex = rowIndex+1;
                IntermediatePos.columnIndex= columnIndex;
                IntermediatePos.direction= 1;
                IntermediateIndex->push_back(IntermediatePos);
            }  
            if ((0<= (rowIndex - 1) )&&((rowIndex - 1)<MAX_ROW ))
            {
                IntermediatePos.rowIndex = rowIndex-1;
                IntermediatePos.columnIndex= columnIndex;
                IntermediatePos.direction= 1;
                IntermediateIndex->push_back(IntermediatePos);
            }  
        } 
   }
   else
   {

        if ((0<= (rowIndex + 1) )&&((rowIndex + 1)<MAX_ROW ))
        {
            IntermediatePos.rowIndex = rowIndex+1;
            IntermediatePos.columnIndex= columnIndex;
            IntermediatePos.direction= 1;
            IntermediateIndex->push_back(IntermediatePos);
        }  
        if ((0<= (rowIndex - 1) )&&((rowIndex - 1)<MAX_ROW ))
        {
            IntermediatePos.rowIndex = rowIndex-1;
            IntermediatePos.columnIndex= columnIndex;
            IntermediatePos.direction= 1;
            IntermediateIndex->push_back(IntermediatePos);
        }  
        if ((0<= (columnIndex + 1) )&&((columnIndex + 1)<MAX_COLUMN ))
        {
            IntermediatePos.rowIndex = rowIndex;
            IntermediatePos.columnIndex= columnIndex +1;
            IntermediatePos.direction= 0;
            IntermediateIndex->push_back(IntermediatePos);
        }  
        if ((0<= (columnIndex - 1) )&&((columnIndex - 1)<MAX_COLUMN ))
        {
            IntermediatePos.rowIndex = rowIndex;
            IntermediatePos.columnIndex= columnIndex - 1;
            IntermediatePos.direction= 0;
            IntermediateIndex->push_back(IntermediatePos);
        }  
        //for(int i=0;i<IntermediateIndex->size();i++) cout<<IntermediateIndex[0][i].rowIndex<<"+"<<IntermediateIndex[0][i].columnIndex;
   }
}

void getNextRowColumn2(vector<ArrayIndex>*  IntermediateIndex, int depth, int directionIncluded)
{

    getNextIndex(&(IntermediateIndex[0][0]),&IntermediateIndex[1],directionIncluded);
    for(int i=0;i<IntermediateIndex[1].size();i++)
    {
        directionIncluded = 1;
        getNextIndex(&(IntermediateIndex[1][i]),&IntermediateIndex[2],directionIncluded);
    }
    IntermediateIndex[0].erase(IntermediateIndex[0].begin());
}
void getNextRowColumn(vector<ArrayIndex>*  IntermediateIndex, int depth, int directionIncluded)
{
    if(depth == 0)
    {
        for(int i=0;i<IntermediateIndex[0].size();i++)
        {
            getNextIndex(&(IntermediateIndex[0][i]),&IntermediateIndex[1],directionIncluded);
            //getNextIndex(&(IntermediateIndex[1][i]),&IntermediateIndex[2],directionIncluded);
            //IntermediateIndex[0].erase(IntermediateIndex[0].begin());
            
        }
    }
    else
    {
        for(int i=0;i<IntermediateIndex[1].size();i++)
        {
            getNextIndex(&(IntermediateIndex[1][i]),&IntermediateIndex[2],directionIncluded);
        }
    }
}
void getArrIndexFromNumber(int*rowIndex,int*columnIndex,int digit)
{
    switch(digit)
    {
        case 0:
               *rowIndex = 3;
               *columnIndex = 1;
               break;
        case 1:
               *rowIndex = 0;
               *columnIndex = 0;
               break;
        case 2:
               *rowIndex = 0;
               *columnIndex = 1;
               break;
        case 3:
               *rowIndex = 0;
               *columnIndex = 2;
               break;
        case 4:
               *rowIndex = 1;
               *columnIndex = 0;
               break;
        case 5:
               *rowIndex = 1;
               *columnIndex = 1;
               break;
        case 6:
               *rowIndex = 1;
               *columnIndex = 2;
               break;
        case 7:
               *rowIndex = 2;
               *columnIndex = 0;
               break;
        case 8:
               *rowIndex = 2;
               *columnIndex = 1;
               break;
        case 9:
               *rowIndex = 2;
               *columnIndex = 2;
               break;
    }
}

void qualifyNum(int TelKey[4][3],vector<int>& prevQualifyingNumberArray,int digits,vector<int>& qualifyingNumberArrayResult)
{
    int number = 0,tempNumber; 
    int rowIndex, columnIndex, lastDigit;
    struct ArrayIndex IntermediatePos;  
    vector<struct ArrayIndex> IntermediateIndex[3];
    //vector<int> prevQualifyingNumberArrayResult;    
    if(prevQualifyingNumberArray.size() == 0)
    {
        qualifyingNumberArrayResult.push_back(number);
        return;   
        //return prevQualifyingNumberArrayResult;
    }
    else if(prevQualifyingNumberArray.size() == 1)
    {
        getArrIndexFromNumber(&rowIndex,&columnIndex,0);        
        if ((0<= (rowIndex + 2) )&&((rowIndex + 2)<MAX_ROW ))
        {
            IntermediatePos.rowIndex = rowIndex+2;
            IntermediatePos.columnIndex= columnIndex;
            IntermediatePos.direction= 1;
            IntermediateIndex[0].push_back(IntermediatePos);
        }  
        if ((0<= (rowIndex - 2) )&&((rowIndex - 2)<MAX_ROW ))
        {
            IntermediatePos.rowIndex = rowIndex-2;
            IntermediatePos.columnIndex= columnIndex;
            IntermediatePos.direction= 1;
            IntermediateIndex[0].push_back(IntermediatePos);
        }  
        if ((0<= (columnIndex + 2) )&&((columnIndex + 2)<MAX_COLUMN ))
        {
            IntermediatePos.rowIndex = rowIndex;
            IntermediatePos.columnIndex= columnIndex +2;
            IntermediatePos.direction= 0;
            IntermediateIndex[0].push_back(IntermediatePos);
        }  
        if ((0<= (rowIndex + 2) )&&((rowIndex + 2)<MAX_COLUMN ))
        {
            IntermediatePos.rowIndex = rowIndex;
            IntermediatePos.columnIndex= columnIndex - 2;
            IntermediatePos.direction= 0;
            IntermediateIndex[0].push_back(IntermediatePos);
        }  
        //for(int i=0;i<IntermediateIndex[0].size();i++) cout<<IntermediateIndex[0][i].rowIndex<<"+"<<IntermediateIndex[0][i].columnIndex;
        //cout<<endl;
        
        getNextRowColumn(IntermediateIndex,0,1);
        for(int i=0;i<IntermediateIndex[1].size();i++)
        {
            qualifyingNumberArrayResult.push_back(TelKey[IntermediateIndex[1][i].rowIndex][IntermediateIndex[1][i].columnIndex]);
        }    
            IntermediateIndex[0].clear();
            IntermediateIndex[1].clear();
        return;
    } 
    else
    {
        for(int i=0;i<prevQualifyingNumberArray.size();i++)
        {
            number = prevQualifyingNumberArray[i];
            lastDigit = number % 10;
            getArrIndexFromNumber(&rowIndex,&columnIndex,lastDigit);
            IntermediatePos.rowIndex = rowIndex;
            IntermediatePos.columnIndex= columnIndex ;
            IntermediatePos.direction = -1 ;
            IntermediateIndex[0].push_back(IntermediatePos);
            while(IntermediateIndex[0].size())
            {   
                getNextRowColumn2(IntermediateIndex, 0, 0);
                //getNextRowColumn(IntermediateIndex, 1, 0);
                for(int j=0;j<IntermediateIndex[2].size();j++)
                {
                    tempNumber = number*10+TelKey[IntermediateIndex[2][j].rowIndex][IntermediateIndex[2][j].columnIndex];
                    qualifyingNumberArrayResult.push_back(tempNumber);
                }
                IntermediateIndex[1].clear();
            }
            IntermediateIndex[0].clear();
            IntermediateIndex[1].clear();
            IntermediateIndex[2].clear();
        }
        return;
    }

}

int main()
{
    int TelKey[4][3]={1,2,3,\
                      4,5,6,\
                      7,8,9,\
                     '*',0,'#'};
    vector<int> prevQualifyingNumberArray[100];
    prevQualifyingNumberArray[0].reserve(0);
    for(int digits=1; digits<=3;digits++)
    { 
        qualifyNum(TelKey,prevQualifyingNumberArray[digits-1],digits,prevQualifyingNumberArray[digits]);
        for(int i= 0; i<prevQualifyingNumberArray[digits].size(); i++) cout<<prevQualifyingNumberArray[digits][i]<<";";
        cout<<endl;
    }
}

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
struct node
{
    struct node*left;
    struct node*right;
    int key;
    static int maxheight;
};

int node::maxheight =0;

struct node * insert(struct node*root,int key,int height=0)
{
    if(root == NULL)
    {
        if(height>node::maxheight) node::maxheight=height;
        struct node * temp=new node;
        temp->key = key;
        temp->left=temp->right=NULL;
        return temp;
    }
    if(key > root->key)
    {
        root->right = insert(root->right,key,height+1);
    }
    else if(key < root->key)
    {
        root->left = insert(root->left,key,height+1);
    }
}

void printTree(struct node*root, int level=0, int maxheight=node::maxheight)
{
    if(root==NULL) return;
    printTree(root->left,level+1);
    for(int i=maxheight-level;i>=0;i--) cout<<"  ";
    cout<<root->key<<endl;
    if(root->key<10)  cout<<" "<<endl; 
    printTree(root->right,level+1);
    /*for(int i=maxheight-level;i>=0;i--) cout<<"  ";
    cout<<root->key<<endl;
    if(root->key<10)  cout<<" "<<endl; */
}

struct node * best_fit_memory(struct node* root,int input_block_size,struct node* best_fit=0)
{
    if(root)
    {
        if(root->key > input_block_size && ((best_fit && best_fit->key > root->key)||!best_fit))
        best_fit = root;
    }
    else
    {
        return best_fit;
    }
    if(input_block_size > root->key)
    {
        best_fit = best_fit_memory(root->right, input_block_size,best_fit);
    }
    else if(input_block_size < root->key)
    {
        best_fit = best_fit_memory(root->left, input_block_size,best_fit);
    }
    else
    {
        best_fit = root;
        //return root;
    }
    return best_fit;
}

int main()
{
    struct node*root=NULL;
    root = insert(root,8);
    printTree(root);
    cout<<"------------------------------------------------------------------------------"<<endl;
    root = insert(root,7);
    printTree(root);
    cout<<"------------------------------------------------------------------------------"<<endl;
    root = insert(root,10);
    printTree(root);
    cout<<"------------------------------------------------------------------------------"<<endl;
    root = insert(root,9);
    printTree(root);
    cout<<"------------------------------------------------------------------------------"<<endl;
    root = insert(root,5);
    printTree(root);
    cout<<"------------------------------------------------------------------------------"<<endl;
    struct node* result_best_fit = best_fit_memory(root,6);
    cout<<"for input "<<6<<"resultbest fit = "<<result_best_fit->key<<endl;
}

posting code with comments

#include <iostream>
#include <stdlib.h>

using namespace std;

int solution(char* str)
{
    //array to hold count of occurance of 26 alphabets a-z
    int characterCount[26]={0};
    int* characterPositionList[26]={0};
    int characterPositionListIndex[26]={0};
    
    int sum=0,left=0,right=0,len=0,flag=0;

    //loop from begining of str to end of str
    for(;str[len]!='\0';len++)
    {
        //str[len]-'A' converts the alphabet to int representation
        //example->if str[len] is 'A', 'A'-'A' = 0 which is the 1st index of characterCount[]
        //if str[len] is 'Z', 'Z'-'A' = 25 which is the 26th index of characterCount[] 
        characterCount[str[len]-'A']++;
    }
   
    cout<<"len="<<len<<endl;

    //loop from begining of characterCount[] to end
    for(int i=0;i<26;i++)
    {
        //if characterCount[i] is not zero, means alphabet at position has count greater than zero
        if(characterCount[i])
        {
            //create characterPositionList[i][j], where each individual element of characterPositionList[i]is a pointer to integer array
            //in ith position of characterPositionList,create another integer array
            //where i indicates the alphabet like in characterCount[i]
            //where j indicates the next occurrence of the same alphabet so that characterPositionList[i][j] is the position of the next occurence of alphbet in input array str[]
            //example in "ACAX", there are 2 occurences of A at str[0] and str[2] and total number of occurences of 'A'=2
            //so characterPositionList[0] points to array of length 2, where characterPositionList[0][0]=0 and characterPositionList[0][1]=2
            //the new array that characterPositionList[i] points to is populated in next for loop 
            characterPositionList[i] = new int[characterCount[i]];
        }
    } 

    for(int i=0;i<len;i++)
    { 
        //the new array that characterPositionList[i] points to is populated here
        //characterPositionListIndex[i] points to last element j of characterPositionList[i][j] for a given i
        characterPositionList[str[i]-'A'][characterPositionListIndex[str[i]-'A']++] = i;
    }

    for(int i=0;i<26;i++)
    {
        if(characterPositionList[i])
        {
            //consider "ACAX" and character 'C'(ie, characterPositionList[1][0]),so the character starts at position1,ie,characterPositionList[2][0]=1, call it k.
            //So it can form k+1 substrings that we can consider,ie, "AC" and "C", takinginto countfrom begining till this character
            //but we consider 1-character substrings atthe end separately with the statement "sum+=characterCount[i]"(there can be characterCount[i] 1-character substring)
            //so, we exclude 1-character-substring and consider k only.
            sum+= characterPositionList[i][0]-0;
            int j=1;
            for(;j<characterCount[i];j++)
            {
                //here consider thecharacter 'A'. It has 2 positions in "ACAX",at 0 and 2.
                //we calculate the number of characters in between excluding 'A's.There is only 1 'C'.
                //the number of substrings itcan form with left-side 'A'is 1,ie,"CA" and with right is 1,ie,"AC". So, the result is multiplied by 2 forleft-side calculation andright-side calculation
                sum+= ((characterPositionList[i][j]-characterPositionList[i][j-1]-1)*2);
            }
            //Simmilar to "sum+= characterPositionList[i][0]-0", it considers the numberofsub-strings thatcan be formed from lastoccurence ofan alphabet to end of string
            sum+= (len - characterPositionList[i][j-1]- 1);
            //sum++;
           //till now we have consideredsub-strings with the given alphabet at the end, now we consider with given alphabet in middle
           //consider string "ACAXC" and character 'C'
           //left = characterPositionList[1][0]-0=1. So, there is 1 character to the left of 'C'
           left = characterPositionList[i][0]-0;
           if(characterCount[i]>1)
           {
               //right=characterPositionList[1][1]-characterPositionList[1][0]=4-1=3
               //so,there are 3 characters in right
               right = characterPositionList[i][1]-characterPositionList[i][0]-1;
               //total permutations ofcombiningthese leftand rightcharacters to form sub-strings=(left*right)
               sum+= (left*right);
               for(j=2;j<characterCount[i];j++)
               {
                   left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
                   right = characterPositionList[i][j]-characterPositionList[i][j-1]-1;
                   sum+= (left*right);
               }
               left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
           }
           right = len-characterPositionList[i][j-1]-1;
           sum+= (left*right);
           sum+= characterCount[i];
        }
    }

   return sum;
}




int main()
{
    char str[]="ACAX";
    cout<<solution(str)<<endl;
}

#include <iostream>
#include <stdlib.h>

using namespace std;

int solution(char* str)
{
int characterCount[26]={0};
int* characterPositionList[26]={0};
int characterPositionListIndex[26]={0};

int sum=0,left=0,right=0,len=0,flag=0;

for(;str[len]!='\0';len++)
{
characterCount[str[len]-'A']++;
}

cout<<"len="<<len<<endl;

for(int i=0;i<26;i++)
{
if(characterCount[i])
{
characterPositionList[i] = new int[characterCount[i]];
}
}

for(int i=0;i<len;i++)
{
characterPositionList[str[i]-'A'][characterPositionListIndex[str[i]-'A']++] = i;
}

for(int i=0;i<26;i++)
{
if(characterPositionList[i])
{
sum+= characterPositionList[i][0]-0;
int j=1;
for(;j<characterCount[i];j++)
{
sum+= ((characterPositionList[i][j]-characterPositionList[i][j-1]-1)*2);
}
sum+= (len - characterPositionList[i][j-1]- 1);
//sum++;
left = characterPositionList[i][0]-0;
if(characterCount[i]>1)
{
right = characterPositionList[i][1]-characterPositionList[i][0];
sum+= (left*right);
for(j=2;j<characterCount[i];j++)
{
left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
right = characterPositionList[i][j]-characterPositionList[i][j-1]-1;
sum+= (left*right);
}
left = characterPositionList[i][j-1]-characterPositionList[i][j-2]-1;
}
right = len-characterPositionList[i][j-1]-1;
sum+= (left*right);
sum+= characterCount[i];
}
}

return sum;
}




int main()
{
char str[]="ACAX";
cout<<solution(str)<<endl;
}

can somebody give me a link to read about such web based designs

int longest_streak(bool a[],int k)
{
    int size = sizeof(a)/sizeof(bool);
    vector<int> countOfOneZero;
    int count = 0;
    
    for(int i = 0; i< size; )
    {
        while(a[i++]) count++;// this is count of consecutive 1
        countOfOneZero.push_back(count);
        count = 0;

        while(!a[i++]) count++;//this is count of consecutive 0
        countOfOneZero.push_back(count);
        count = 0;
    }
    if(a[i-1]) countOfOneZero.push_back(0);// if the given array ends with 1, then count of //trailing 0 is 0
//at the end of this loop countOfOneZero contains count of consecutive 1 followed by //count of consecutive 0 .... and even indexes give count of 1 and odd index gives count //of zero
   int currentStreak(0), maxStreak(0),availableFlipCount(k);
   for(vector<int>::iterator it = countOfOneZero.begin(); (it+1) != countOfOneZero.end(); it+=2)
   {
       currentStreak = 0;
       availableFlipCount = k;
 
       for(vector<int>::iterator it2 = it; (it2+1) != countOfOneZero.end(); it2+=2)
       {
           currentStreak+=*it2;
           if(availableFlipCount > *(it2+1))
           {
               currentStreak+=*(it2+1);
               availableFlipCount -= *(it2+1);
               if(!availableFlipCount)
               {
                   if((it2+1) != countOfOneZero.end())
                   {
                       currentStreak+=*(it2+2);
                       if(currentStreak > maxStreak) maxStreak = currentStreak;
                       it2 = countOfOneZero.end() -1;
                   }
               }
           }
           else
           {
               currentStreak+=availableFlipCount;
               availableFlipCount = 0;
               if(currentStreak > maxStreak) maxStreak = currentStreak;
                it2 = countOfOneZero.end() -1;

           }
       }    
   }
   
}

modify the above code
before the code "for(vector<array>::iterator it2= result.begin();it2!=result.end();it2++)"
calculate size of result into variable z.
make the loop run until z number of elements

typedef vector<int> array
vector<array> findNumberForSum(vector<int> arr, int sum)
{
    vector<array> result;
    vector<int> x;
    x.push_back(0);
    result.push_back(x);
    for(vector<int>::iterator it= arr.begin();it!=arr.end();it++)
    {
        int len = result.size();
        for(int it2=0; it2<len;it2++)
        {
            if(result[it2][result[it2].size()-1]+*it <=sum)
            {
                 vector<int> temp(result[it2]);//this array contains elements that add less than or 
                                                    //equal to sum followed by sum of integers present in
                                                    // the array
                 temp.push_back( result[it2][result[it2].size()-1] + *it);//insert new sum
                 temp[temp.siz()-2] = *it;   
            }
            
        } 
    }
    for(int i-0;i<result.size();i++)
    {
        if(result[i][result[i].size()-1] != sum)
        {
            result.erase(result.begin()+i);
        }
    }
   return result;
}

}

char findNonRepeated(string str)
{
     int count[27]={0,0,0,0,0,0,0,0,0,0,0....27 times};
     char find;
     int temp;
     for(string::reverse_iterator i=str.rbegin();i!=str.rend(),i++)
     {
         temp = *i-'a';
         if (!(temp>=0 && temp<=25 ))
         {
             temp = *i-'A';
             if (!(temp>=0 && temp<=25 ))
             temp=26;//blanc space
         }
        .if(a[temp]++==0)
             find= *it;
      
     }
    return find;
}

loop through the string from back
make an array a[26], where a[0]= count of 'a' and a[25]=count of 'z'
make a temp(find) char variable
if the char is in a[], increment count
if the char is not in a[](a[i]==0), increment count, put it into find
after the end of loop, the value of find is the 1st non-repeated char