codility absolute distinct count from an array
|
8:06 PM |
No comments |
codility absolute distinct count from an array
so i took the codility interview test yesterday and was informed today that i failed, unfortunately i wasnt given any other information by either codility nor the employer as to where i screwed up so i would appreciate some help in knowing where i went wrong. i know codility pays alot of emphasis on how fast the program runs and how it behaves for large numbers. now i didnt copy paste the questions so this the approx of what i remember
- count the number of elements in an array a which are absolute distinct, what it means is if an array had -3 and 3 in it these numbers are not distinct because|-3|=|3|. i think an example would clear it up better
a={-5,-3,0,1,-3} the result would be 4 because there are 4 absolute distinct elements in this array.
The question also stated that a.length would be <=10000, and most importantly it stated that assume that the array is sorted in ascending order but i didnt really understand why we would need it to be sorted
IF YOU THINK I MISSED SOMETHING ASK AND I WILL TRY TO CLEAR UP THE QUESTION FURTHER.
here is my code
import java.util.HashMap; import java.util.HashSet; import java.util.Set; public class test2 { int test(int[] a){ Set s=new HashSet(); for(int i=0;i Answer by Peter Lawrey for codility absolute distinct count from an array
If the array is sorted you can find duplicates by looking a neightbours. To compare absolute values to need to start at both the start and the end. This avoid creating a new structure.
EDIT: IMHO HashMap/HashSet is O(log(log(n)) due to collisions, it is only O(1) if there is a perfect hash function. I would have thought not creating object which be much much faster but appears to be only 4x fast on my machine.
In summary, you can see that using a Set is simpler, clearer and easier to maintain. It is still very fast and would be the best solution in 98% of cases.
public static void main(String[] args) throws Exception { for (int len : new int[]{100 * 1000 * 1000, 10 * 1000 * 1000, 1000 * 1000, 100 * 1000, 10 * 1000, 1000}) { int[] nums = new int[len]; for (int i = 0; i < len; i++) nums[i] = (int) (Math.random() * (Math.random() * 2001 - 1000)); Arrays.sort(nums); long timeArray = 0; long timeSet = 0; int runs = len > 1000 * 1000 ? 10 : len >= 100 * 1000 ? 100 : 1000; for (int i = 0; i < runs; i++) { long time1 = System.nanoTime(); int count = countDistinct(nums); long time2 = System.nanoTime(); int count2 = countDistinctUsingSet(nums); long time3 = System.nanoTime(); timeArray += time2 - time1; timeSet += time3 - time2; assert count == count2; } System.out.printf("For %,d numbers, using an array took %,d us on average, using a Set took %,d us on average, ratio=%.1f%n", len, timeArray / 1000 / runs, timeSet / 1000 / runs, 1.0 * timeSet / timeArray); } } private static int countDistinct(int[] nums) { int lastLeft = Math.abs(nums[0]); int lastRight = Math.abs(nums[nums.length - 1]); int count = 0; for (int a = 1, b = nums.length - 2; a <= b;) { int left = Math.abs(nums[a]); int right = Math.abs(nums[b]); if (left == lastLeft) { a++; lastLeft = left; } else if (right == lastRight) { b--; lastRight = right; } else if (lastLeft == lastRight) { a++; b--; lastLeft = left; lastRight = right; count++; } else if (lastLeft > lastRight) { count++; a++; lastLeft = left; } else { count++; b--; lastRight = right; } } count += (lastLeft == lastRight ? 1 : 2); return count; } private static int countDistinctUsingSet(int[] nums) { Set s = new HashSet(); for (int n : nums) s.add(Math.abs(n)); int count = s.size(); return count; }
prints
For 100,000,000 numbers, using an array took 279,623 us on average, using a Set took 1,270,029 us on average, ratio=4.5
For 10,000,000 numbers, using an array took 28,525 us on average, using a Set took 126,591 us on average, ratio=4.4
For 1,000,000 numbers, using an array took 2,846 us on average, using a Set took 12,131 us on average, ratio=4.3
For 100,000 numbers, using an array took 297 us on average, using a Set took 1,239 us on average, ratio=4.2
For 10,000 numbers, using an array took 42 us on average, using a Set took 156 us on average, ratio=3.7
For 1,000 numbers, using an array took 8 us on average, using a Set took 30 us on average, ratio=3.6
On @Kevin K's point, even Integer can have collision even through it's hash values are unique, it can map to the same bucket as the capacity is limited.
public static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } public static void main(String[] args) throws Exception { Map map = new HashMap(32, 2.0f); for (int i = 0; i < 10000 && map.size() < 32 * 2; i++) { if (hash(i) % 32 == 0) map.put(i, i); } System.out.println(map.keySet()); }
prints
[2032, 2002, 1972, 1942, 1913, 1883, 1853, 1823, 1763, 1729, 1703, 1669, 1642, 1608, 1582, 1548, 1524, 1494, 1456, 1426, 1405, 1375, 1337, 1307, 1255, 1221, 1187, 1153, 1134, 1100, 1066, 1032, 1016, 986, 956, 926, 881, 851, 821, 791, 747, 713, 687, 653, 610, 576, 550, 516, 508, 478, 440, 410, 373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]
The values are in reverse order because the HashMap has generated into a LinkedList.
Answer by Ralph for codility absolute distinct count from an array
You should have pay attention to the fact that the array is sorted in ascending order.
Lets assume that there are only positive numbers, or the question was not about absolute distinct.
The you could count the Number by iterating trough the list, and increment the counter by one, if the actual element is different from the last. (and +1 for the first element)
If you understand that, you can add the absolute distinct constraint. For example by improving the algorithm by two pointers, one starting from the begin, one from the end. Then you have also to take care that both pointers works like in parallel, so that both pointers will end at 0 or the absoulte lowest number (positive/negative) - This will complicate the whole stuff a bit, but it is possible.
Answer by Stephen Chung for codility absolute distinct count from an array
Well, to be absolutely honest, you need to do better than this.
Judging from the question, I assume the list do not contain duplicates. Again, obviously the trick is the pre-sorted list. Which means that while +5 may be at the right end of the line, -5 will be at the left end of the line, since negative numbers sort in reverse to their absolute magnitude.
Start from both ends, work inwards. If the two numbers are -1 of each other, then it is not distinct. Otherwise, they are distinct, and move the end that is absolutely larger.
Go until you reach zero, or you bump into the next list -- in that case, take everything remaining in the next list as distinct as well.
This algorithm needs no hashes, no dictionaries, no data structures, and runs in O(n) time, going through the whole list exactly once.
Answer by Carlos Heuberger for codility absolute distinct count from an array
Your solution is at least one of the easiest way to do it (more readable, easier to maintain). It surely is not the most efficient one (neither the worst) and should be acceptable if not used in a time critical code.
But you should have mentioned that and suggested that there is a more efficient solution like traversing the list from both ends (as already answered). Maybe you would have got an extra point for discussing the advantages of both solution.
Tested your solution (on old (slow) laptop):
- less than 2 milliseconds for 10000 numbers
- ~450 ms for 1000000
Answer by BiGYaN for codility absolute distinct count from an array
The solution is to use the fact that the array is sorted. What you can do is to have two pointers pointing at beginning and end of the array respectively. Then based on the abs value, decrease/increase the end-pointer/beginning pointer. At the same time you'll have to keep track of repeated elements in sequence like {3,3,3,4} (the 3 should be counted once).
In all it wouldn't be too complex, I think with 20-25 loc in C.
Answer by goroncy for codility absolute distinct count from an array
Please find below implementation which is even much faster than Peter's.
if (A == null || A.length == 0) { return 0; } else if (A.length == 1 || A[0] == A[A.length - 1]) { return 1; } int absDistinct = 0; int leftCurrent; int leftNext; int rightCurrent; int rightPrevious; for (int i = 0, j = A.length; i < j; ) { leftCurrent = A[i]; rightCurrent = A[j]; leftNext = A[i + 1]; rightPrevious = A[j - 1]; if (leftCurrent + rightCurrent == 0) { while (A[i] - A[i + 1] == 0) { i++; } while (A[j] - A[j - 1] == 0) { j--; } i++; j--; absDistinct++; } else { if (leftCurrent + rightCurrent < 0) { if (leftCurrent - leftNext != 0) { absDistinct++; } i++; } else { if (rightCurrent - rightPrevious != 0) { absDistinct++; } j--; } } } return absDistinct;
The distribution of numbers is important. But if there will be lot of series of the same numbers this algo will perform better. This shows that the algorythms complexity is not the only barier to overcome. When you have the algo with the propper complexity this might be just one of the options. Linear correction of the algo is still possible. The character of input is sometimes also important.
Answer by Michelin Man for codility absolute distinct count from an array
Here is a recursive algorithm that will return the absolute unique entries in a list in a single pass, that is in O(n) time. It relies on the fact that the array is sorted and it is not using a java.util.Set.
Consider this example array {-5,-5,-3,0,1,3}
- Because the array is sorted, one of the two elements at either end of the array will have the absolute highest value: -5
- Again because the array is sorted, if that element is going to have a match, it will be its neighbour, or neighbours for multiple matches.
- So for -5 we do a single check with its neighbour: they are equal. -5 is a duplicate, so remove it, don't increase our running total and recurse.
{-5,-3,0,1,3} Now we pick -5, its unique therefore increase running total to 1 and then remove it.
{-3,0,1,3} If they two ends have equal absolute values, just remove one, it doesnt matter which, just so long as its just one. Say the first. We don't increment our running total because the value we removed was a duplicate.
{0,1,3} Now we pick 3, its unique, running total goes to 2.
{0,1} Pick 1, its unique, running total 3.
{0} Size is 1, the value is unique, increment running total and return it. 4 Correct!
package com.codility.tests; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class AbsDistinct { /** * Count the number of absolute distinct elements in an array. * The array is sorted in ascending order. */ private static int countAbsDistinct(List list, int count) { int lastIndex = list.size() - 1; if (lastIndex == -1) { // zero size list, terminate return 0; } if (lastIndex == 0) { // one element list, terminate return ++count; } if (Math.abs(list.get(0)) == Math.abs(list.get(lastIndex))) { // doesn't matter which end is removed, but to remove _only_ 1 list.remove(0); } else if (Math.abs(list.get(0)) > Math.abs(list.get(lastIndex))) { // if different to its nighbour, its unique hence count it if (list.get(0) != list.get(1)) { count++; } // now that its been accounted for, remove it list.remove(0); } else { // same logic but for the other end of the list if (list.get(lastIndex) != list.get(lastIndex - 1)) { count++; } list.remove(lastIndex); } return countAbsDistinct(list, count); } public static void main(String[] args) { if (args.length == 0) { // just run the tests List testList = new ArrayList(Arrays.asList(-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8)); List empty = new ArrayList(); List singleElement = new ArrayList(Arrays.asList(1)); List sameElement = new ArrayList(Arrays.asList(1, 1, 1, 1, 1, 1)); System.out.println("test array: " + countAbsDistinct(testList, 0)); System.out.println("empty array: " + countAbsDistinct(empty, 0)); System.out.println("single element array: " + countAbsDistinct(singleElement, 0)); System.out.println("same element array: "
Answer by Rabi for codility absolute distinct count from an array
Here is a simple solution for this.
public class test{ public static int dis(Integer[] arr) { out.println(Arrays.asList(arr)); if (arr.length == 0) { return 0; } int i = 0; int j = arr.length - 1; int c = 0; while (i <= j) { if ((j != arr.length - 1) && (Math.abs(arr[j]) == Math.abs(arr[j + 1]))) { out.println("skipping J==" + j); j--; continue; } if ((i != 0) && (Math.abs(arr[i]) == Math.abs(arr[i - 1]))) { out.println("skipping I==" + i); i++; continue; } if (Math.abs(arr[i]) < Math.abs(arr[j])) { j--; c++; } else if (Math.abs(arr[i]) > Math.abs(arr[j])) { i++; c++; } else { i++; j--; c++; } out.println("I=" + i + " J=" + j + " C=" + c); } return c; } public static void main(String[] arg){ //Integer[] a = {34,2,3,4,3,-2,3}; //out.println("distinct elements are" + dis(a)); Integer[] aa={-5,-3,0,1,3}; out.println("distinct elements count " + dis(aa)); Integer[] ab={-5,-3,0,1,3, 4, 6, 7}; out.println("distinct elements count " + dis(ab)); Integer[] ac={-5}; out.println("distinct elements count " + dis(ac)); Integer[] acc={9}; out.println("distinct elements count " + dis(acc)); Integer[] ad={9,9,9}; out.println("distinct elements count " + dis(ad)); Integer[] ae={-5,-5}; out.println("distinct elements count " + dis(ae)); Integer[] aee={1,5,5,5,5}; out.println("distinct elements count " + dis(aee)); Integer[] af={-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8}; out.println("distinct elements count " + dis(af)); } }
out put is
[-5, -3, 0, 1, 3] distinct elements count 4 [-5, -3, 0, 1, 3, 4, 6, 7] distinct elements count 7 [-5] distinct elements count 1 [9] distinct elements count 1 [9, 9, 9] distinct elements count 1 [-5, -5] distinct elements count 1 [1, 5, 5, 5, 5] distinct elements count 2 [-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8] distinct elements count 8 Answer by ordurio for codility absolute distinct count from an array
here is a python proposal i just did to practice:
def abs_distinct(A): if not A: return -1 #assume A is sorted n = len(A) left_cursor = 0 right_cursor = n-1 left_value = A[0] right_value = A[n-1] nb_abs_distinct = len(set([abs(left_value),abs(right_value)])) while left_value != right_value: # case 1: decrease right_cursor down to the next different value if abs(left_value) < abs(right_value): while A[right_cursor] == right_value: right_cursor -= 1 right_value = A[right_cursor] if abs(right_value) != abs(left_value): nb_abs_distinct += 1 # case 2: increase left_cursor to the next different value elif abs(left_value) > abs(right_value): while A[left_cursor] == left_value: left_cursor += 1 left_value = A[left_cursor] if abs(left_value) != abs(right_value): nb_abs_distinct += 1 else: while abs(left_value) == abs(right_value): left_cursor += 1 left_value = A[left_cursor] nb_abs_distinct += 1 return nb_abs_distinct Answer by FelixW for codility absolute distinct count from an array
This is my version. What do you think?
int count(vector testVector){ for(unsigned int i = 0; i < testVector.size(); i++){ // empty array, return 0 if(testVector.empty()) return 0; // one number left, must be unique, return 1; if(testVector.size() == 1) return 1; // neighbour elements are the same, delete first element if(testVector[0] == testVector[1]) { testVector.erase(testVector.begin()); return count(testVector); } // absolute value of first and last element identical, delete first element if(abs(testVector[0]) == abs(testVector[testVector.size() - 1])){ testVector.erase(testVector.begin()); return count(testVector); } // if absolute value of beginning is greater than absolute value of end, delete beginning, otherwise end if(abs(testVector[0]) > abs(testVector[testVector.size() - 1])){ testVector.erase(testVector.begin()); } else { testVector.erase(testVector.end() - 1); } // increase counter and recurse return 1 + count(testVector); } } Answer by Chris C Napier for codility absolute distinct count from an array
int count(vector &A) { int len = B.size(); if (len <= 0) return 0; // make a copy and calc absolutes of all items vector B = vector(A); for (int i = 0; i < len; i++) { if (B[i] < 0) B[i] = -B[i]; } // and sort so we have a simple absolute count sort(B.begin(), B.end()); int result = 1; //count first number always for (int j = 1; j < len; j++) { if (B[j] != B[j-1]) result++; } return result; } Answer by Raymond for codility absolute distinct count from an array
class Program { static int CountArray(int[] MyIntArray) { int countNum = 0; int[] TempIntArray = new int[MyIntArray.Length]; for (int i = 0; i < MyIntArray.Length; i++) { TempIntArray[i] = Math.Abs(MyIntArray[i]); } var queryResults = from n in TempIntArray select n; countNum = queryResults.Distinct().ToArray().Length; return countNum; } static void Main(string[] args) { Console.WriteLine("demoX6FVFB-KX8"); Random randomNumber = new Random(); int[] TheArray = new int[100]; for (int j = 0; j < TheArray.Length; j++) { TheArray[j] = randomNumber.Next(-50, 50); } int counta = Program.CountArray(TheArray); Console.WriteLine(counta); } } Answer by readedited for codility absolute distinct count from an array
this is what i came up with, not sure if the fact that it contains a for loop inside the while deems it as typical noobie mistake.
private int getDistict(int[] myaa) { int dupcount=0; int i = 0; int j = myaa.length - 1; while (i < j) { // check neighbors if(Math.abs(myaa[i]) == Math.abs(myaa[i+1])) { dupcount++; i++; continue; } // check the other side if(myaa[i] < 0) { for(int k = j; Math.abs(myaa[i]) <= Math.abs(myaa[k]); k-- ) { if(Math.abs(myaa[i])==Math.abs(myaa[k])){ dupcount++; } } } i++; } return myaa.length - dupcount; } Answer by ses for codility absolute distinct count from an array
import java.util.Arrays; public class DistinctNumbers { public static void main(String[] args) { int[][] tests = new int[][] { {-5,-3, 0, 1, 3}, //4 {-5,-5,-5,-5,-5}, // 1 { 1, 2, 3, 4, 5}, // 5 { 1}, // 1 { 1, 2}, // 2 { 1, 1}, // 1 }; for (int[] test : tests) { int count = findDistinctNumberCount( test ); System.out.println(count); } } static int findDistinctNumberCount(int[] numbers) { // 1. make everything abs. for (int i=0; i Answer by Michal B. for codility absolute distinct count from an array
.NET C#:
static int absoluteDistinctNumbers(int[] arr) { int same = 0; int l = 0; int r = arr.Length - 1; while (l < r) { if (Math.Abs(arr[l]) == Math.Abs(arr[r])) ++same; if (Math.Abs(arr[l]) > Math.Abs(arr[r])) ++l; else --r; } return arr.Length - same; }
Is there a problem with this solution? It looks much simpler than the other ones presented...and it took me like 10 minutes, so I am quite sure I did something wrong, but I have no idea what... My tests:
var arr = new int[] { 4, 2, 1, 1, -1, -5 }; var result = absoluteDistinctNumbers(arr); Debug.Assert(4 == result); arr = new int[] { 1, -1 }; result = absoluteDistinctNumbers(arr); Debug.Assert(1 == result); arr = new int[] { }; result = absoluteDistinctNumbers(arr); Debug.Assert(0 == result); arr = new int[] { 2 }; result = absoluteDistinctNumbers(arr); Debug.Assert(1 == result); arr = new int[] { 3, 3, -3 }; result = absoluteDistinctNumbers(arr); Debug.Assert(1 == result); arr = new int[] { 2, 0, 0, 0 }; result = absoluteDistinctNumbers(arr); Debug.Assert(2 == result);
Answer by danny for codility absolute distinct count from an array
The shortest version here for time complexity O(n) and O(1) memory:
int countAbsDistinct(int[] A) { int start = 0; int end = A.length - 1; if (end == -1) { // zero size list return 0; } int c = 1; // at least one abs distinct for non-empty array while(A[start]=l){ while(A[end]==list.get(--end)); // move left until different value } if (l>=r){ while(A[start]==list.get(++start)); // move right until different value } } if(start>end){ // if last movements made start index bigger than end c--; } return c; }
Answer by Tianyu Zheng for codility absolute distinct count from an array
In the case of Java, Arrays.sort() method has the best average performance. The expectation of time complexity is said to be O(N*log2N). So why not use it?
Here is a solution.
- Go through the array, turn all the negative numbers into their absolute numbers. For example, from {-5, -3, 0, 1, 3} to {5, 3, 0, 1, 3}.
- User Arrays.sort() to resort the array. For example, from {5, 3, 0, 1, 3} to {0, 1, 3, 3, 5}.
- Go through the array again, if the neighbors do not have the same value, count up.
Here is the source in Java.
int countDistinct(int[] A) { int size = A.length; if(size == 0) { return 0; } for(int i = 0; i < size; i++) { if(A[i] < 0) { A[i] = (-1) * A[i]; } } Arrays.sort(A); int count = 1; for(int i = 0; i < size - 1; i++) { if(A[i] != A[i + 1]) { count++; } } return count; }
Answer by JNL for codility absolute distinct count from an array
Heres what I coded.....Let me know if it can be improved....
import java.util.Arrays; import java.util.HashSet; /******** Joel Jun 19, 2013 ********/ public class CodilityTest { private int[] inputArray; public static int count=0; public void setInput(int [] givenIP){ this.inputArray= new int[givenIP.length]; for(int i=0; i o_hs = new HashSet(); for(int numCount=0; numCount
Answer by guest01 for codility absolute distinct count from an array
def solution1(A): indneg = -1 lena = len(A) lneg = list() lpos = list() for i in range(lena-1): if A[i] != A[i+1]: if A[i] < 0: lneg.append(A[i]) else: lpos.append(A[i]) print(lneg) print(lpos) deltalen = 0 for i in lneg: if -i in lpos: deltalen +=1 return(len(lneg)+len(lpos)-deltalen)
Answer by Indu for codility absolute distinct count from an array
int[] arr= new int[]{-5,-5,-6,-6,-6}; Set newSet = new HashSet(); for(int i=0;i
0 comments:
Post a Comment