northernlight
BAN USER
- 7
0of 0 votes
AnswersFind summation of n records added in past 60 secs
Items of the typestruct { int i; time_t timestamp; }needs to be stored in a C++ container. One of the requirement is to calculate summation of 'i' s of these items added in past 60secs.
- northernlight in United States
What container/datastructure will you use. (number of items can be in the order of 10s of thousands.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Application Engineer Algorithm - 0
0of 0 votes
AnswersI want to store an item of below structure in a C++ contrainer.
- northernlight
struct xyz
{
int i;
time_t timestamp;
}
I also want to calculate summation of 'i' of all elements in the container which have been added in past 60 secs.
Which container or data structure is best for this scenario. Should take care of iterator invalidations while calculating the summation iterating the container items (which can happen if a new element gets added when I am iterating).| Report Duplicate | Flag | PURGE
- 47
0of 0 votes
AnswersYou are given an array of N elements. Each element in the range Min of int to Max of Int. You need to find the length of longest sequence in this array such that difference of largest and smallest element of that sequence is 1. The sequence need not be sequential.
- northernlight in United Kingdom
For e.g. array[]={6,10,6,7,8,9,0}
seq {6,10} = diff is 4 len 2
seq { 10,7,8} diff is 3 len 3
seq { 7,8,9} diff 2 len 3
seq {6,6,7} diff is 1 len 3
In this example the program should return 3 .
Complexity N*longN| Report Duplicate | Flag | PURGE
Amazon Algorithm Arrays C C++
crisp
- northernlight May 12, 2014#include <stdio.h>
int findMax(int *a,int start, int end)
{
int i =start;
int index;
int max =0;
for(;i<=end;i++)
{
if(max < a[i])
{
max = a[i];
index = i;
}
}
return index;
}
void moveMaxElementToBeginning(int *a,int maxIndx,int start,int* swaps)
{
int tmp;
int i=0;
if(maxIndx == start) return;
while(maxIndx != start)
{
tmp = a[maxIndx];
a[maxIndx] = a[maxIndx -1];
a[maxIndx-1] = tmp;
maxIndx = maxIndx -1;
*swaps = *swaps -1;
}
printf("New array ");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
}
void swapToMax(int *a, int N, int nswaps)
{
int start =0;
int end = nswaps;
int maxIndx;
while(nswaps > 0)
{
maxIndx = findMax(a, start,end);
printf("found max %d indx %d\n",a[maxIndx],maxIndx);
moveMaxElementToBeginning(a,maxIndx,start,&nswaps);
printf("moved max to front %d \n",a[0]);
start = start + 1;
}
}
int main(void) {
// your code goes here
int i=0;
int a[]={2,5,1,9,3,7,2,8,9,3};
printf("Original Array\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
swapToMax(a,10,5); // 5 swaps
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
sequence shd be in the increasing order of indices, but sequence itself need not be continuous. 6 6 7 in the example is the answer.
- northernlight May 12, 2014ok, inside the 2nd for loop sum = sum - partialsum; before next iteration.
Also breakout if length > 0, no need to continue the loop, as we have started from end of array.
assuming sequence mean continuous elements
int solution(int A[],int N)
{
int sum=0;
int partialsum = 0;
if((N==1) && (A[0] == 0)) return 1;
for(int i =0;i<N;i++)
sum=sum+A[i];
if(sum==0) return N;
for(int i=N-1;i >0;i--)
{
partialsum+=A[i];
if ((sum - partialsum) ==0)
{
length = i;
return length;
}
sum = sum - partialsum;
}
return length;
}
do such questions asked in phone interview ? I can't answer such questions on phone unless I have solved this problem before and memorized it for the sake of interview.
- northernlight May 10, 2014
who down voted ??? it works perfectly...
- northernlight May 12, 2014