CareerCup

Create a map<timestamp,sessionid>, find key=t1 and remove all sessions from original map with sessionid having timestamp > t1.

Definite Approach:
1. Start with 1,3.
2. Maximum number accessible with above numbers is 1+3=4.
3. Next number to be accessed 5. Max number until now is 4.
4. Next number is 5+4=9
5. Numbers are 1,3,9. Repeat steps 2,3,4.
Example- Max number accessible=1+3+9=13. Next number to be accessed is 14.
Next number is 13+14=27...
Numbers are 1,3,9,27.

Difference between crash and exception in c++ -

Exceptions are defined situations which c++ can manage and handle.
Some undefined behaviors like null pointer dereferencing is not handled through exception, and so causes the program to crash.

Time - O(n), Space-O(n) is following
take a vector,
navigate each element in the array, maintain one pointer for curpos.
insert the element if of alternate sign, otherwise move next. keep moving until element found.
insert found element with alternate sign in vector.
delete element from the array.

This solultion is simple, does not seem like Amazon type :)

#include<iostream>
using namespace std;

int main()
{

        int num1=100, num2=145;
        //unit digit is num1%10, 10th digit is (num1/10)%10, 100th digit is num1/100
        int digit1,digit10,digit100=1;
        for(;num1<=num2;num1++)
        {
                digit1=num1%10;
                digit10=(num1/10)%10;
                if(digit10>digit100 && digit1>digit10)
                        cout<<num1<<"\t";
        }
        return 0;
}

I wrote a simpler program that takes a pointer to middle of an integer array instead of map.

char arr[]="*##*###*****####*#*###*";
        int len=strlen(arr);
        cout<<"len="<<len<<endl;
        int *newarr=new int[2*len+1];
        int newdistance[2*len+1];               //distance between pair with same number

        int *arrpos=newarr+len-1;               //allow negative positions also
        int *distance=newdistance+len-1;        //distance  for negative  positions

        for(int i=-len;i<=len; i++)
                arrpos[i]=-100,distance[i]=0;
        int pos=0;                      //universal position of each character

        for(int i=0;i<len;i++)
        {
                if(arr[i]=='*') //* is +1
                        pos++;
                else
                        pos--;  //# is -1
                if(arrpos[pos]!=-100)   //this number was encountered before
                        distance[pos]=i-arrpos[pos];
                else            //first time pos found
                        arrpos[pos]=i;  //save position of number
        }
        int max=0;
        int maxpos=0;
        for(int i=-len;i<=len;i++)
        {
                if(arrpos[i]!=-100)
                {
                        cout<<"Largest distance for number "<<i<<" is "<<distance[i]<<" ,1st occr="<<arrpos[i]<<endl;
                        //now find largest of all distances, that is the largest subarray.
                        if(max<distance[i])
                        {
                                max=distance[i];
                                maxpos=arrpos[i];
                        }
                }
        }
        cout<<"max subarray of equal number of * and # is of length "<<max<<" and starts at pos "<<maxpos+1<<endl;
        return 0;

Output is

len=23
Largest distance for number -4 is 0 ,1st occr=21
Largest distance for number -3 is 16 ,1st occr=6
Largest distance for number -2 is 14 ,1st occr=5
Largest distance for number -1 is 16 ,1st occr=2
Largest distance for number 0 is 12 ,1st occr=1
Largest distance for number 1 is 12 ,1st occr=0
Largest distance for number 2 is 0 ,1st occr=11
max subarray of equal number of * and # is of length 16 and starts at pos 7