Showing posts with label Programming. Show all posts
Showing posts with label Programming. Show all posts

Program for Validating whether Brackets are Closing in Correct Order

Here is the C++ program which would solve the problem given below. The code was compiled and testing for few of the inputs. The validation of the brackets are done using simple logic using IF conditions.

Given a stream of string S of ‘(‘, ’)’, ‘{‘, ‘}’, ‘[‘, ‘]’, determine if the input string is valid i.e. brackets must close in correct order i.e. ‘(‘ with ‘)’, ‘{‘ with ‘}’ and ‘[‘ with ‘]’.

Given a string of length N, output ‘Correct’ if brackets close in correct order else output ‘Incorrect’.

Suggestions are welcomed and in case you have a better program, please post it in the comment section.

For More Programming Codes - CLICK HERE




#include iostream
#include stdio.h
#include string.h

using namespace std;

#define MAX 100

char str[100];

struct stack{
    char holdSymbols[MAX];
    int top;
}stackObject;


void pushSymbol(char item)
{
    stackObject.top++;
    stackObject.holdSymbols[stackObject.top] = item;
}

void popSymbol()
{
    stackObject.top--;
}


char* validString(char* input1){

    stackObject.top = -1;
    int i;

    for(i=0;input1[i]!=NULL;i++){
        if(input1[i]!=' '){
            if (i==0){
                pushSymbol(input1[i]);
            }else{
                if(stackObject.holdSymbols[stackObject.top]=='{' && input1[i]=='}'){
                    popSymbol();
                }else if(stackObject.holdSymbols[stackObject.top]=='(' && input1[i]==')'){
                    popSymbol();
                }else if(stackObject.holdSymbols[stackObject.top]=='[' && input1[i]==']'){
                    popSymbol();
                }else{
                    pushSymbol(input1[i]);
                }
            }
        }
    }


    char *output;

    if (stackObject.top == -1){
        output = "Correct";
    }else{
        output = "Incorrect";
    }

    cout << output;

    return output;
}


int main()
{
    char temp[100]={"({} [((({{}}) [{()}]) )])"};

    validString(temp);

    return 0;
}

Largest Square in a Matrix of NxN - C++ Program Code

Here is the C++ program to solve the problem of finding the largest square in a matrix of a given size NxN. Here i have put two versions of the program one which gives the matrix and other which give a Char* output as asked in TechGig coding challenge.

In the program the input is provided through a char* input array and then converted for manipulations. Please don't completely rely on my program, as i am still learning programming (always will be learning).

Suggestions are welcomed and in case you have a better program, please post it in the comment section.

Note: For Techgig code challenge you need to work on the output a bit as the testcases are not getting passed, even though the default testcase gets passed. 



C++ For TechGig Code Challange (Geekathon):

 #include string.h
#include stdio.h
#include iostream
#include string
#include sstream

using namespace std;

/* Function to get minimum of three values */
int min(int a, int b, int c)
{
    int m = a;
    if (m > b)
        m = b;
    if (m > c)
        m = c;
    return m;
}

char* biggestSquare(char* input1[])
{
    int tROW=0,tCOL=0;
    bool gotColumnCount = false;

    /*------- Get count of rows and column in a given input ------*/

    for (int i=0,COL=0;input1[i]!=NULL;i++){

        string inputData(input1[i]);
        char* c = &inputData[0];

        for (;*c;c++)
        {
            if(gotColumnCount==false && *c!='#'){
                tCOL++;
            }
        }

        gotColumnCount = true;
        tROW=i+1;
    }

    /*------ Allocating memory for matrix array -------*/

    int matrixData[50][50];


    /*------ Creating matrix array from char* -------*/

    for (int i=0;input1[i]!=NULL;i++){

        string inputData(input1[i]);
        int colCount=0;
        char* c = &inputData[0];

        for (;*c;c++)
        {
            if(*c!='#'){

                if (*c=='1'){
                    matrixData[i][colCount] = 1;
                }else{
                    matrixData[i][colCount] = 0;
                }

                //cout << "Test" << matrixData[i][colCount];
                colCount++;
            }           
        }
    }

    int sumMatrix[50][50];

    int max_of_s, max_i, max_j;

    /* Get first column */
    for(int i = 0; i < tCOL; i++)
        sumMatrix[i][0] = matrixData[i][0];

    /* Get first row */   
    for(int j = 0; j < tCOL; j++)
        sumMatrix[0][j] = matrixData[0][j];

    /* Get other entries */
    for(int i = 1; i < tROW; i++)
    {
        for(int j = 1; j < tCOL; j++)
        {
            if(matrixData[i][j] == 1)
                sumMatrix[i][j] = min(sumMatrix[i][j-1], sumMatrix[i-1][j], sumMatrix[i-1][j-1]) + 1;
            else
                sumMatrix[i][j] = 0;
        }  
    }

    /* Find the maximum entry, and indexes of maximum entry in sumMatrix */
    max_of_s = sumMatrix[0][0]; max_i = 0; max_j = 0;

    for(int i = 0; i < tROW; i++)
    {
        for(int j = 0; j < tCOL; j++)
        {
            if(max_of_s < sumMatrix[i][j])
            {
                max_of_s = sumMatrix[i][j];
                max_i = i;
                max_j = j;
            }      
        }               
    }    

    //cout << "\n Maximum size sub-matrix is: \n";

    string largeSquare;

    largeSquare = "{";

    cout << max_i  << "  " << max_of_s  << max_j << "\n";

    int reduceConst = max_j;

    for(int i = max_i; i > max_i - max_of_s; i--)
    {
        largeSquare = largeSquare + "(";

        for(int j = max_j; j > max_j - max_of_s; j--)
        {
            stringstream ss,ff;
           
            ff << max_j - j;
            ss << max_i - reduceConst;

            //cout << i << "  " << j << "\n";

            if (((i-1)==(max_i - max_of_s))&&((j-1)==( max_j - max_of_s))){               
                largeSquare = largeSquare + ss.str() + "#" + ff.str() + ")}";
            }else{
                if (((j-1)==( max_j - max_of_s))){                   
                    largeSquare = largeSquare + ss.str() + "#" + ff.str();
                }else{                   
                    largeSquare = largeSquare + ss.str() + "#" + ff.str() + ",";
                }
            }

        }
        reduceConst--;

        if ((i-1)!=(max_i - max_of_s))
            largeSquare = largeSquare + "),";
    } 

    return &largeSquare[0];
}



C++ programs for Visual Studio 2012:


#include "stdafx.h"

#include cstdio
#include iostream
#include string
#include sstream 

using namespace std;

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
    int m = a;
    if (m > b)
        m = b;
    if (m > c)
        m = c;
    return m;
}

char* biggestSquare(char* input[])
{
    int tROW=0,tCOL=0;
    bool gotColumnCount = false;

    /*------- Get count of rows and column in a given input ------*/

    for (int i=0,COL=0;input[i]!=NULL;i++){

        string inputData(input[i]);

        char* c = &inputData[0];


        for (;*c;c++)
        {
            if(gotColumnCount==false && *c!='#'){

                tCOL++;
            }
        }

        gotColumnCount = true;

        tROW=i+1;

    }

    /*------ Allocating memory for matrix array -------*/

    int **matrixData;

    matrixData=new int*[tROW]; //creates a new array of pointers to int objects

    for(int i=0; i        matrixData[i]=new int[tCOL];


    /*------ Creating matrix array from char* -------*/

    for (int i=0;input[i]!=NULL;i++){

        string inputData(input[i]);

        int colCount=0;

        char* c = &inputData[0];

        for (;*c;c++)
        {
            if(*c!='#'){

                if (*c=='1'){
                    matrixData[i][colCount] = 1;
                }else{
                    matrixData[i][colCount] = 0;
                }

                //cout << "Test" << matrixData[i][colCount];
                colCount++;
            }           
        }
    }


    int **sumMatrix;

    sumMatrix=new int*[tROW]; //creates a new array of pointers to int objects

    for(int i=0; i        sumMatrix[i]=new int[tCOL];

    int max_of_s, max_i, max_j;

    /* Set first column of S[][]*/
    for(int i = 0; i < tCOL; i++)
        sumMatrix[i][0] = matrixData[i][0];

    /* Set first row of S[][]*/   
    for(int j = 0; j < tCOL; j++)
        sumMatrix[0][j] = matrixData[0][j];

    /* Construct other entries of S[][]*/
    for(int i = 1; i < tROW; i++)
    {
        for(int j = 1; j < tCOL; j++)
        {
            if(matrixData[i][j] == 1)
                sumMatrix[i][j] = min(sumMatrix[i][j-1], sumMatrix[i-1][j], sumMatrix[i-1][j-1]) + 1;
            else
                sumMatrix[i][j] = 0;
        }  
    }


    /* Find the maximum entry, and indexes of maximum entry in S[][] */
    max_of_s = sumMatrix[0][0]; max_i = 0; max_j = 0;

    for(int i = 0; i < tROW; i++)
    {
        for(int j = 0; j < tCOL; j++)
        {
            if(max_of_s < sumMatrix[i][j])
            {
                max_of_s = sumMatrix[i][j];
                max_i = i;
                max_j = j;
            }      
        }               
    }    

    cout << "\n Maximum size sub-matrix is: \n";

    string largeSquare;

    largeSquare = "{";

    cout << max_i  << "  " << max_of_s  << max_j << "\n";

    int reduceConst = max_j;

    for(int i = max_i; i > max_i - max_of_s; i--)
    {
        largeSquare = largeSquare + "(";


        for(int j = max_j; j > max_j - max_of_s; j--)
        {
            stringstream ss,ff;

            if (((i-1)==(max_i - max_of_s))&&((j-1)==( max_j - max_of_s))){
                ff << max_j - j;
                ss << max_i - reduceConst;
                largeSquare = largeSquare + ss.str() + "#" + ff.str() + ")}";
            }else{
                if (((j-1)==( max_j - max_of_s))){
                    ff << max_j - j;
                    ss << max_i - reduceConst;
                    largeSquare = largeSquare + ss.str() + "#" + ff.str();
                }else{
                    ff << max_j - j;
                    ss << max_i - reduceConst;
                    largeSquare = largeSquare + ss.str() + "#" + ff.str() + ",";
                }
            }

        }
        reduceConst--;

        if ((i-1)!=(max_i - max_of_s))
            largeSquare = largeSquare + "),";
    } 


    cout << &largeSquare[0];

}


int _tmain(int argc, _TCHAR* argv[])
{

    char *input[10] = {"0#1#1#1#0#1#0#1","1#0#1#0#0#0#0#1","0#0#0#1#0#1#0#0","1#1#1#1#1#0#0#1","1#1#1#1#0#1#1#1","1#1#1#1#0#1#1#1","1#1#1#1#1#1#1#1","1#1#0#1#0#0#1#1"};

    biggestSquare(input);

    system("PAUSE");
    return 0;
}


Amazon Coding challenge on Time Slots

Here is the Amazon coding challenge with solution. Please do comment below if you find any issues with the solution. Ready to learn and evolve. Knowledge is Power. 

Given M busy-time slots of the team members in the Kindle team, can you print all the available time slots when all of them can schedule a meeting for a duration of K minutes.
The event time will be of the form HH MM (where 0 <= HH <= 23 and 0 <= MM <= 59). K will be in the form minutes.



Input Format:

M K [M number of busy time slots , K is the duration in minutes]
This is followed by M lines with 4 numbers on each line.
Each line will be of the form StartHH StartMM EndHH EndMM  [Eg: 9am-11am time slot will be given as 9 00 11 00]
An event time slot is of the form [Start Time, End Time) which means the start time is inclusive but not the end time;
So, an event of the form 10 00  11 00 => implies that the meeting starts at 10:00 and ends at 11:00. Hence, another meeting can start at 11:00.

Sample Input:
5 120
16 00 17 00
10 30 14 30
20 45 22 15
10 00 13 15
09 00 11 00

Sample Output:
00 00 09 00
17 00 20 45


/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include
#include
using namespace std;

int main()
{
    int bTimeSlots, duraInMin;   
    cin >> bTimeSlots >> duraInMin;
   
    int startHH, stopHH, startMM, stopMM;
    const int minPerday = 1440;
    int storeBooking[minPerday] = {0};
   
    for (int i=0;i        cin >> startHH >> startMM >> stopHH >> stopMM;
       
        if (startHH>24 or stopHH > 24 or startMM > 59 or stopMM>59)
            exit(EXIT_FAILURE);
       
        int startMeet = startHH * 60 + startMM;
        int stopMeet = stopHH * 60 + stopMM;
       
        for (int j=startMeet;j<=stopMeet;j++){
            storeBooking[j]=1;
        }       
    }
   
    int timeInterval = 0;
    int freeTimeStart=0, freeTimeStop;
   
    for (int k=0;k       
        if (storeBooking[k]==1){
            if ((k/duraInMin) > 0 && storeBooking[k-1]==0){
               
                if ((k - freeTimeStart) >= duraInMin){
               
                cout << setfill('0') << setw(2) << freeTimeStart/60
                    << " "
                    << setfill('0') << setw(2) << freeTimeStart%60
                    << " "
                    << setfill('0') << setw(2) << k/60       
                    << " "
                    << setfill('0') << setw(2) << k%60   
                    << "\n";
                }
               
            }
          
            freeTimeStart = k;
        }else if(k==minPerday -1){
            if ((k - freeTimeStart) >= duraInMin){
                int finalHH;
                if (((k+1)/60)==24){ finalHH=0; }else{finalHH = (k+1)/60; }
               
                cout << setfill('0') << setw(2) << freeTimeStart/60
                    << " "
                    << setfill('0') << setw(2) << freeTimeStart%60
                    << " "
                    << setfill('0') << setw(2) << finalHH   
                    << " "
                    << setfill('0') << setw(2) << (k+1)%60   
                    << "\n";
            }
        }
    }
      
   
}

Programming and Software interview questions, answers and materials

This website is for helping programmers successfully prepare for technical interviews questions and answers. Also enhance your knowledge on various subjects. This is being done by presenting a variety of questions, grouped by subject matter. I will try to cover subjects like C, C++, MySql, HTML5, Javascript, JQuery, MEL scripts, etc. More will come as and when requested by you.

This site will try to put forward materials, interview questions, coding challenges, code puzzles and various algorithms..

Feel Free to drop in your request as a comment below. We will address your request of any programming question.You Can Share your knowledge with us and we shall share it to rest of visitors

These questions have been pulled from our personal interview experiences with big software companies such as Google, Amazon, Accenture, Apple, Intuit, Adobe, NCR, and Oracle, just to name a few.



For More Programming related topics - CLICK HERE 

Coding Challange: