Counting Maximum Apples

A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner.

Code (O(m*n) time, O(m*n) space):

#include<iostream>
#include<stack>
using namespace std;
 
int path(int (*array)[4],int row)
{
        int **aux = new int *[row];
        for(int i=0;i<row;++i)
                aux[i]=new int[4]();
        
        aux[0][0] = array[0][0];
        for(int i=0,j=1;j<4;++j)
                aux[i][j] = aux[i][j-1] + array[i][j];
        
        for(int i=1,j=0;i<row;++i)
                aux[i][j] = aux[i-1][j] + array[i][j];
        
        for(int i=1;i<row;++i)
        {
                for(int j=1;j<4;++j)
                {
                        aux[i][j] = array[i][j] + std::max(aux[i-1][j],aux[i][j-1]);
                }
        }
        
        stack<string> st;
        
        st.push("At Destination");
        int i,j;
        for(i=row-1,j=3;i>0 && j>0;)
        {
                if(aux[i][j] - array[i][j] == aux[i-1][j])
                {
                        st.push("go down");
                        i--;
                }
                else
                {
                        st.push("go right");
                        j--;
                }
        }
        if(i==0)
                while(j--)
                        st.push("go right");
        if(j==0)
                while(i--)
                        st.push("go down");
        
        cout<<"At Source, now..\n";
        while(!st.empty())
        {
                cout<<st.top()<<"\n";
                st.pop();
        }
        return aux[row-1][3];
        
}
int main()
{
        int array[3][4]={{1,2,3,4},
                                         {1,1,1,1}, 
                                         {9,9,9,9}
                                        };
                
        int total = path(array,3);
        cout<<"Total:"<<total<<endl;
        return 0;
}

Group a linked-list based on Vowels and Consonants.

You got to move the nodes having vowels as keys to the beginning and consonants to the end. You also got to maintain the order. Example:

Input: A-M-A-Z-O-N

Output: A-A-O-M-Z-N

Code (Complexity: O(N), Space O(1))

#include<iostream>
using namespace std;
 
class Node
{
public:
        char var;
        Node *next;
        
        Node(char v,Node *next=NULL):var(v),next(next){}
};
 
Node *make_list(char array[],int size)
{
        if(size ==0)
                return NULL;
        else
        {
                Node *head = new Node('o');
                Node *temp = head;
                for(int i=0;i<size;++i)
                {
                        temp->next = new Node(array[i]);
                        temp=temp->next;
                }
                temp=head;
                head = head->next;
                delete temp;
                return head;
        }
}
void print_list(Node *head)
{
        while(head){
                cout<<head->var<<"--";
                head = head->next;
        }
        cout<<"END"<<endl;
}
void insertAfter(Node** temp,Node *n)
{
        n->next = (*temp)->next;
        (*temp)->next = n;
}
bool isVowel(char v)
{
        switch(v)
        {
                case 'A':
                case 'E':
                case 'I':
                case 'O':
                case 'U':
                        return true;
                default:
                        return false;
        }
}
Node *groupByVowels(Node *head)
{
        Node *vowel=NULL,*consonant=NULL;
        
        vowel = new Node('L');
        consonant = new Node('C');
        
        Node *tv = vowel,*tc=consonant;
        for(Node *temp=head;temp;)
        {
                Node *tt = temp->next;
                if(isVowel(temp->var)){
                        insertAfter(&tv,temp);
                        tv = tv->next;
                }
                else{
                        insertAfter(&tc,temp);
                        tc=tc->next;
                }
                temp = tt;
        }
        tv->next = consonant->next;
        tv = vowel;
        vowel=vowel->next;
        delete tv;
        return vowel;
}
int main()
{
        char array[] = {'B','E'};
        Node *head = make_list(array,sizeof(array)/sizeof(array[0]));
        print_list(head);
        head = groupByVowels(head);
        print_list(head);
}

Write a method to compute all permutations of a string.

Another "Cracking the Coding Interview" question from recursion. Implementation is done with C++.

Code:

#include<iostream>
#include<vector>
using namespace std;
void print_subset(vector<int>& v,int array[],int size,int i)
{
        if(i>=size)
        {
                for(int i=0;i<v.size();++i)
                        cout<<v[i];
                cout<<endl;
                return;
        }
        print_subset(v,array,size,i+1);
        v.push_back(array[i]);
        print_subset(v,array,size,i+1);
        v.pop_back();
}
int main()
{
        int array[3]={1,2,3};
        vector<int> v;
        v.reserve(3);
        print_subset(v,array,3,0);
        return 0;
}

Write a program to sort a stack in ascending order  You should not make any assumptions about how the stack is implemented   The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

This is a question from "Cracking the Coding Interview". The solution given there uses a stack and follows "insertion sort" technique. I present the solution in "selection sort" technique and use recursion. I used C++.

Here is the code:

#include<iostream>

#include<stack>

#include<vector>

using namespace std;

template <typename X,typename Y>

int get_size(stack<X,Y>& st)

{

if(st.empty())

return 0;

else

{

X a = st.top();

st.pop();

int sz = 1 + get_size(st);

st.push(a);

return sz;

}

}

template <typename X,typename Y>

void stack_sort_private(stack<X,Y>& st,int size,int max,int now)

{

if(now == size)

{

st.push(max);

}

else

{

X a = st.top();

st.pop();

if(max<a)

std::swap(max,a);

stack_sort_private(st,size,max,now+1);

st.push(a);

}

}

template <typename X,typename Y>

void stack_sort(stack<X,Y>& st)

{

int size = get_size(st);

for(int i = size;i>0;--i)

{

X max = st.top();

st.pop();

stack_sort_private(st,i,max,1);

}

}

int main()

{

int array[] = {7,8,9,10,1};

vector<int> v(array,array + sizeof(array)/sizeof(int));

stack<int,vector<int> > st(v);

stack_sort(st);

while(!st.empty())

{

cout<<st.top()<<",";

st.pop();

}

return 0;

}

How to allocate a 2-Dimensional array in C/C++ using only 2 malloc calls / new operators.

Code:

#include<iostream>

using namespace std;

#define ROWSIZE 3

#define COLSIZE 4

int main()

{

int *p,**q;

p = new int[ROWSIZE*COLSIZE];

for(int i=0;i<ROWSIZE;++i)

q[i] = (int *)(p + i*COLSIZE) ;

q[1][1] = 1;

for(int i=0;i<ROWSIZE;++i)

{

for(int j=0;j<COLSIZE;++j)

std::cout<<q[i][j]<<" ";

std::cout<<std::endl;

}

return 0;

}