Ashay Raut
BAN USERIn single array
Method to find subarray of equal 0's and 1's is :
1. Replace each 0 by -1
2. Take cumulative sum in array say "csum[i]=a[0]+a[1]+..+a[i]
3. Let len1 = the max index 'i' where you have csum[i]=0
4. Take hashmap<int,int> hmap
int len2=MIN_INT;
for(int i=0;i<len_of_array;i++)
{
if(!(hmap.containsKey(csum[i])) // csum[i] acts as key and its not present
{
hmap.put(csum[i],i) ; // put it with index i as value
}
else // key is present already in hashmap
{
int lenTemp = i - hmap.get(csum[i]);
if(len2<lenTemp)
len2=lenTemp
}
}
ans = max(len1,len2)
We can use this method for this question by merging both arrays to one array.
There are two ways of locking database - Pessimistic and Optimistic.
Pessimistic used:
In the banking application example, an account is locked as soon as it is accessed in a transaction. Attempts to use the account in other transactions while it is locked will either result in the other process being delayed until the account lock is released, or that the process transaction will be rolled back. The lock exists until the transaction has either been committed or rolled back.
If Optimistic is used :
In the banking application example, the amount of an account is saved when the account is first accessed in a transaction. If the transaction changes the account amount, the amount is read from the store again just before the amount is about to be updated. If the amount has changed since the transaction began, the transaction will fail itself, otherwise the new amount is written to persistent.
I have taken this from wiki : Please read complete article from
wiki/Lock_(database)
Here, dp[i] stores minimum steps to reach end from ith position.
Initially, dp[n-1]=0 because frog is at end. Start from right end and go towards left to calculate steps.
#include<stdio.h>
#include<limits.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
int *dp;
void calc(int *a,int index,int n,int steps)
{
if(index<0)
return;
int myMin=INT_MAX;
for(int i=1;i<=a[index] && index+i<n;i++)
{
int x = dp[index+i];
if(x<myMin)
myMin = x;
}
if(myMin<dp[index]-1)
dp[index]=myMin+1;
calc(a,index-1,n,steps+1);
}
int main()
{
int n;
cin>>n;
int *a = (int*)calloc(n,sizeof(int));
dp = (int*)calloc(n,sizeof(int));
for(int i=0;i<n;i++)
{
cin>>a[i];
dp[i]=INT_MAX;
}
dp[n-1]=0;
//cout<<calc(a,0,n,0)<<endl;
calc(a,n-1,n,0);
cout<<dp[0]<<endl;
return 0;
}
For Amazon, prepare Algos and DS very well..coz its need for all rounds..When I cracked it after 3 attempts, I compiled all questions here.
- Ashay Raut May 09, 2014ashayraut.wordpress.com/interview-preparation-best-100/