ss Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
When n equals 3, result2 should be {9,1}?
If so, here is my pseudo-code:
while array1.length >n:
newArray = new Array();
for(int i = 0; i < array1.length/n +1; i++)
{
newArray.Add(sum(array, i*n, i*(n+1)-1); // Calculate the sum of from array1[i*n] to array1[i*(n+1)-1], and please attention to the range of index when calculating the last several numbers
}
array1 = newArray
if not, would you please to provide me more info? Thanks.
#include <iostream>
#include <vector>
/*
* Output:
* 6, 4
* FelipeCerqueira, dosSantos
*/
template<typename T>
std::vector<T> acc(std::vector<T>& V, int n) {
int len = V.size() / n;
if (V.size() % n != 0)
len++;
std::vector<T> R(len);
int c = 0;
for (int i = 0; i < V.size(); i++) {
if (i > 0 && i % n == 0)
c++;
R[c] += V[i];
}
return R;
}
template<typename T>
void test(std::vector<T>& V, int n) {
auto R = acc(V, n);
for (auto it = R.begin(); it != R.end(); it++) {
if (it != R.begin()) std::cout << ", ";
std::cout << *it;
}
std::cout << std::endl;
}
int main(void) {
std::vector<int> V1 {3, 3, 3, 1};
std::vector<std::string> V2 {"Felipe", "Cerqueira", "dos", "Santos"};
test(V1, 2);
test(V2, 2);
return 0;
}
public List<Integer> add (int [] ar, int n){
List<Integer> rst = new ArrayList<> ();
if (ar == null || ar.length == 0) {
return rst ;
}
int [] sum = new int [ar.length] ;
sum[0] = ar[0] ;
for (int i = 1; i < ar.length ;++i) {
sum[i] = sum[i - 1] + ar[i] ;
}
int i = 0 ;
int preSum = 0 ;
while (sum.length - i >= n) {
int cur = sum[i + n - 1] - preSum ;
preSum += cur ;
i += n;
rst.add(cur) ;
}
if (i < sum.length) {
int a = sum[sum.length - 1] - preSum;
rst.add(a) ;
}
return rst ;
}
Python:-
Please tell me if we can improve written code
def sumRepetation(arr,n):
newArr=[]
count = 0
sumVal = 0
arrLength = len(arr)
reminderElement = arrLength % n
restElement = arrLength - reminderElement
counterVar = 0
flag = False
for i in arr:
if count<restElement and flag == False:
sumVal+=i
count+=1
if count == n and flag == False:
newArr.append(sumVal)
count = 0
sumVal = 0
counterVar+=1
if counterVar == restElement:
flag = True
if flag == True:
sumVal+=i
if counterVar == arrLength-1 and flag == True:
newArr.append(sumVal)
print newArr
passArr=[1,1,1,1,1,1,1,1,1,1,1,1,1,1]
number = 4
sumRepetation(passArr,number)
From Question, it seems that the array will only contain 1's. I know we cant take assumptions by our own but just for a second thought. interviewee should have asked interviewer for that. If only 1's are allowed the complexity will reduce a lot otherwise the answer given by others are good enough.
If only 1's are in input array[java]:
public static void printArrayResidues(int[] array, int n) {
if(null != array || n <= 1 ){
return;
}
int len = array.length;
int tempn = n;
while( tempn < len){
int templen = len;
ArrayList<Integer> result = new ArrayList<Integer>();
while(templen > 0){
if(templen - tempn >= 0){
result.add(tempn);
}else{
result.add(templen);
}
templen -= tempn;
}
for(int i=0; i<result.size(); i++){
System.out.print(result.get(i));
if(i!=result.size()-1){
System.out.print(",");
}
}
System.out.println();
tempn *= n;
}
}
Javascript Code:
// arr = [1,1,1,1,1,1,1,1,1,1]
function addAll (arr, key) {
var res=[];
var j = 0;
var ind = 0;
var len = arr.length;
for(var i=0; i<arr.length; i++) {
if(key > len-i+1) {
if(!res[ind]){
res[ind]=0;
}
res[ind] += arr[i];
}
if((key<=(len-i+1)) && (key-j !==0)) {
if(!res[ind])
{
res[ind]=0;
}
res[ind] = res[ind] + arr[i];
j++;
}
if(key-j===0) {
j=0;
ind++;
}
}
return res;
}
console.log(addAll([1,1,1,1,1,1,1,1,1,1], 6));
int[] shortArray(int[] nums, int n) {
if(nums == null || nums.length ==0)
return new int[] {};
int len = nums.length;
if(n < 2)
return nums;
if(n >= len)
return new int[] {len};
int[] res = new int[len/n +1]; // 10/3 + 1
for(int i = 0; i < res.length; i++) {
res[i] = n;
}
res[res.length-1] = len % n;
return res;
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,1,1,1,1,1,1};
ArrayChange ac = new ArrayChange();
System.out.println(Arrays.toString(ac.shortArray(nums, 3)));
System.out.println(Arrays.toString(ac.shortArray(nums, 4)));
System.out.println(Arrays.toString(ac.shortArray(nums, 1)));
System.out.println(Arrays.toString(ac.shortArray(nums, 10)));
System.out.println(Arrays.toString(ac.shortArray(nums, 1)));
System.out.println(Arrays.toString(ac.shortArray(null, 11)));
}
public static void main(String[] args) {
int [] array = {1,1,1,1,1,1,1,1,1,1,1};
int k = 3;
for( int i = 0; i < array.length; i = i + k ){
System.out.println( addArrayItems ( i, (( array.length - i) < k )? i + array.length - i: i + k, array ));
}
}
private static int addArrayItems( int start, int end, int [] arrays ){
int sum = 0;
for( int i = start; i < end; i++ ){
sum += arrays[i];
}
return sum;
}
static ArrayList<Integer> createArray(int length1,ArrayList<Integer> sumArray1,ArrayList<Integer>array1,int n)
{
int start=0;
while(start<length1)
{
int sum=0;
if(n>array1.size())
{
for(int k=0;k<array1.size();k++)
sum=sum+array1.get(k);
}
else
for(int i=0;i<n;i++)
{
sum=sum+array1.get(0);
array1.remove(0);
}
sumArray1.add(sum);
start=start+n;
}
return sumArray1;
}
- Radha October 07, 2015