Arista Networks Interview Question
Software EngineersCountry: 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