Category Archives: Algorithm

Simple things matter

Today, out of boring, I did visit again codility to take a few tests. Their free tests aren’t much of a challenge, so I got them one by one, each in 5 minutes or so. Then I come across a test which, to my opinion, just a little trick question:

Problem: PermMissingElem

Task description
A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:

 class Solution { public int solution(int[] A); } 


that, given a zero-indexed array A, returns the value of the missing element.
For example, given array A such that:
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.

Feel free to drop a few minutes to think it through. It isn’t even hard.

You finished your program? Ok, then let’s continue.
I took my 5 minutes and write a very simple script, including the unit tests:

First Solution
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int sum = 0;
int sumTotal = (A.length + 1) * (A.length + 2) / 2;

for (int i = 0; i < A.length; i++) {
sum = sum + A[i];
}

int result = sumTotal - sum;
return result;
}
}

Unit tests:

  • [6,5,4,3,2]
  • [2, 5, 1, 4]
  • [2]
  • [1]
  • [6,3,5,4,2,1]


All my unit tests passed. I submitted, kind of waiting for another 100%. But it was FAILED with n ~ 1,000,000.

My algorithm is right, I know that. So what’s the matter with big number?

In case you’re still wonder, here’s the program that worked and got 100% score:

Right Solution

class Solution
public int solution(int[] A) {
// write your code in Java SE 8
int sum = 0;
int sumTotal = 0;

for (int i = 0; i < A.length; i++) {
sum = sum + A[i];
}

for (int i = 1; i <= A.length + 1; i++) {
sumTotal = sumTotal + i;
}

int result = sumTotal - sum;
return result;
}
}

Can you tell the difference? :)

Google isn’t a history book anymore

Google

It’s not as cool and hot as the barrel roll trick, but the other news from Google today really catch my eyes.

The story is here.

In short, Google made changes to its algorithm to alter search result behaviors. In stead of results with more than several months old, now you get newer results (maybe only minutes after it was online).

It mean that Google changed the way they do searching. They do change. They are not satisfied with what they achieved, but they seek to improve on. And this improvement is one of the things that Google could do better.

(From my own experience, in past it took several weeks to a new blog post from WordPress make it way to Google search results.)

Cheers for it!