## Arista Networks Interview Question

Software Engineers**Country:**India

**Interview Type:**Written Test

nice logic.

```
def frequency(input, n):
for i in range(0, len(input)):
input[i] *= (n+1)
for i in range(0, len(input)):
input[input[i]/(n+1)] += 1
for i in range(0, len(input)):
input[i] = input[i]%(n+1)
return input
input = [1, 2, 3, 4, 1, 1, 2, 4, 7]
print(frequency(input, 7))
```

The solution is clever, but it's not O(n); you have multiple iterations. The trick here is to make a decision as you're traversing through the list.

A HashMap where you increment the value on collision is O(n), but then you have to iterate through the HashMap to see which values are >1, which has a worst case of O(N).

I don't think it's possible to do in O(N) because any algorithm will require two steps:

1. Parsing the data

2. Examining the data.

Any comments?

This just iterate the array once:

```
int freq(int[] array, int n)
{
int i, index;
for (i=0; i<n; i++) {
index = array[i] % n;
array[i] = array[i]/n;
array[index] += i >= index ? 1 : n;
}
printf("Frequency of appear:index freq\n");
for (i=0; i<n; i++)
printf("%5d %d\n", i, array[i]);
return 0;
}
```

actually you should take into account fact that intergers are in range [0 .. n - 1] and n (array size). So we know that each number has a frequency between 0 and n. Suggest that we modify array and multiply each item by (n+1). For example we have array [1,1,1,0,3] n = 5. We multiply by 6 and the result is [6,6,6,0,18]. Then we iterate through we take each number val and calculate orig value i = value/6 and increment the i index of array with 1

In our case i = 6/6 = 1 , we increment a[1] ,becomes 7 then we continue with second number 6 and a[1] becomes 8 and by thrid 6 a[1] becomes 9, by 0 a[0] becomes 7,and by 18 a[3] becomes 1. Then we move through array and devide by mod each element by n+1, reminder is frequency. Here is some implementation

- EPavlova January 16, 2016