Google Interview Question
Software Engineer / Developersint* findArraySum(int* arr, int num_elem, int num_rows) {
int rem;
if((rem = num_elem%num_rows) != 0)
return null;
int* result = (int*)malloc(rem*sizeof(int));
memset(result, 0, rem);
for(int i = 0; i < rem; i++) {
for(int j = 0; j < num_rows; j++) {
result[i] = result[i] + arr[i+rem*j];
}
}
return result;
}
This should run in O(n) where n is the number of elements in the given array.
int* findArraySum(int* arr, int num_elem, int num_rows) {
int rem;
if((rem = num_elem%num_rows) != 0)
return null;
int* result = (int*)malloc(rem*sizeof(int));
memset(result, 0, rem);
for(int i = 0; i < rem; i++) {
for(int j = 0; j < num_rows; j++) {
result[i] = result[i] + arr[i+rem*j];
}
}
return result;
}
This should run in O(n) where n is the number of elements in the given array.
<pre lang="" line="1" title="CodeMonkey22451" class="run-this">#include <stdio.h>
#define MAX_COLS 10
int main()
{
int total_nums, i, k, num_rows, num_cols;
int A[8]= {3,4,7,2,2,6,0,9};
int sum[MAX_COLS];
//Initialize
for (i = 0; i < 10; i++)
{
sum[i] = 0;
}
i = 0;
k = 0;
scanf("%d", &num_rows);
// num_rows = 4;
total_nums = 8;
num_cols = (total_nums / num_rows) + ((total_nums % num_rows) ? 1: 0);
for (; i < total_nums; i++)
{
k = i % num_cols;
sum[k] += A[i];
}
for (i = 0; i < num_cols ; i++)
{
printf("The sum of %d column is %d\n",i, sum[i]);
}
}
</pre><pre title="CodeMonkey22451" input="yes">
</pre>
O(n) solution:
public static int[] sumOfCol(int[] array, int nrows) {
if (array.length % nrows == 0) {
int ncols = array.length / nrows;
int[] cols = new int[ncols];
int f = 0;
for (int i = 0 ; i < array.length ; i++) {
cols[f] += array[i];
f++;
if (f >= ncols) {
f = 0;
}
}
return cols;
}
return new int[0];
}
Think about if you have 9 elements in the array, and you want the row number to be 4, it's not possible.
Java solution
}
- Abhiraj December 30, 2011