NewGuy
BAN USER7843671@gmail.com
Here you go
void printanagram (char *s){
int count;
int len;
len = strlen(s);
//Run loop via all possible combinations 0,2^len
for(count=0;count <= pow(2,len);count++){
int i,j;
for(i=1,j=0;i<=count;j++,i<<=1){
//Check if current count & with iterator is nonzero.
// or simply check if that bit is set to one
if(count&i)
printf("%c",s[j]);
}
printf("\n");
}
}
My C implementation.Basically prints it on screen instead of returning.
#include <stdio.h>
// Space needed to store "(XXX/YYY)"
#define POSTFIX 10
void spacefinder(char *str,int size,int st,int *end){
int lastspace;
int i;
i=st;
lastspace=st;
*end=st;
while(str[i]!='\0'){
if(str[i]!=' ')
(*end)++;
else{
// Check if total size is as expected.
if(*end-st <= size - POSTFIX){
lastspace=*end;
(*end)++;
}
else
break;
}
i++;
}
// If no space found or string ends return *end , otherwise return lastspace.
if(lastspace!=st && str[i]!='\0' )
*end=lastspace;
return;
}
// Takes string and split size ( assumes size > 10 )
void splitstring(char *str,int size){
int i=0,j;
int end;
int len;
int count = 0;
char **split;
char c[POSTFIX];
char temp[POSTFIX];
c[0]='(';
len=strlen(str);
//Malloc 2d array
split=(char**)malloc (sizeof(char*));
while(i<len){
count++;
//Keep on increasing using realloc
split=(char**)realloc (split,sizeof(char*)*count);
split[count-1]=(char*)malloc (sizeof(char)*strlen(str));
spacefinder(str,size,i,&end);
//Copy result in split[count-1]
strncpy(split[count-1],str+i,end);
split[count-1][end-i]='\0';
i=end+1;
}
//Steps to append total number of messages "/XXX)" .
temp[0]='/';
itoa(count,temp+1,10);
strcat(temp,")");
//Steps to prepend count of message "(XX" and printing.
for(j=0;j<count;j++){
itoa(j+1,c+1,10);
strcat(c,temp);
strcat(split[j],c);
printf("Split string = %s,len=%d\n",split[j],strlen(split[j]));
}
}
I used following algo.
count= number of inputs
num = actual number that is added in queue
average= moving average
for count <2 , compute average normal way. (ie if( count==1) return num; if(count==2) return (num+avg)/2
for rest ,
average= ((average/(count/(count-1)) + num/count
I wrote following program with input as int but can be easily modified to accommodate float
float moving_avg(int num){
static float avg;
static int count;
float olddata;
count++;
if(count >2){
olddata= avg/(count/(count-1));
avg=olddata+(num/count);
} else if( count ==2 ){
avg=(avg+num)/2;
} else {
avg=num;
//printf("olddata=%.2f count=%d avg=%f\n",olddata,count,avg);
}
return avg;
}
Call above function to calculate the moving average .
- NewGuy November 26, 2015My implementation is equivalent to o(n). I scan column wise, and eliminate rows in next scan, which have zeros in that column. Read through the code to get idea.
int find_max(int arr[ARR][ARR]){
int j,i;
int index=0,oldindex;
bool flag=0;
float ret;
/* Start Columnwise, where you find 1,0 make that bit set/reset in index.
* Go through this till only 1 bit is set in index or you go through all the loop.
* Special conditions,
* 1. We need flag to make sure , we handle initial coloumns with all zeros.
* 2. After first iteration and first one is found ( flag ) , skip the rows where index is zero.
* 3. If index is zero after a column , reset it back to oldindex. i.e. stick with old index data.
* Enable prints to get more insight.
* */
for(j=0;j<ARR;j++){
oldindex = index;
for(i=0;i<ARR;i++){
/* Check if this row can be skipped, after first coloumn and flag set */
if(flag && j>0 && ((index & (0x1<<i))==0)) {
//printf("Skipping this row %d \n",i);
continue;
}
//TODO: Can be optimized
/* Set/Reset bit in index based on arr[i][j] */
if(arr[i][j]==1){
flag=1;
index |= 0x1 << i;
} else{
index &= ~(0x1 << i);
}
//printf("index = %d\n",index);
}
/* If index is 0 , use old index. This is needed to make sure , index values are unaffected by zero in same column. */
if(index==0) index=oldindex;
/* Check if index is perfect power of two, to break */
if(flag && (index & (index-1)) == 0){
//printf("Done\n");
break;
}
}
/* Return the row number , from index. Basically finding x in , 2^x = index*/
ret=log(index)/log(2);
//printf("only match left, index = %d\n",(int)ret);
return (int)ret;
}
Some background on this question, this was asked to me in phone interview at Nvidia. Interviewer gave me 48 hours to solve this and also warned me that do not copy from internet.
I spend almost a day thinking about how to do it . Then looked at implementation of malloc and clicked to me that I can store original address just
before return address. It worked. Need some tuning about how to fix corner cases.
After week of submission , got mail from NVIDIA for another phone interview.
Eventually, got selected after 6-7 onsite interview rounds.
Don't you need to turn 270 as well. You might face a room which has door only on 270 degrees.
- NewGuy December 13, 2015