Interview Question
Country: India
Interview Type: Written Test
//First put everything in a hasmap in O(n) time
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
int arr[] = {2,4,1,5,3};
int j=1;
int sum=0;
for(int i : arr)
{
sum=sum+i;
hm.put(j, sum);
j++;
}
Now when i=2 and j=5
just say hm.get(5) - hm.get(2);
you will get the answer in O(1)
int main()
{
int A[] = {1,2,3,4,5,6,7};
int i=1;
int start, end;
printf("\n please enter strt & end indexes \n");
scanf("%d %d", &start, &end );
if(!( (start >=0 && start <end) && (end < sizeof(A) ) ))
{
printf("\n entered incorrect indexes \n");
return 0;
}
while ( i< sizeof(A) )
{
A[i] += A[i-1] ;
}
if( start > 0 )
printf("\n sum from %d to %d is = %d \n", start, end, A[end]-A[start-1] );
else
printf("\n sum from %d to %d is = %d \n", start, end, A[end] );
return 0;
}
- mohit May 05, 2012