Fortsätt till huvudinnehåll

Codility tasks - Part I

I was recently faced with two codility tasks when applying for a job as an Embedded Software Engineer. For those of you who arn't familiar with Codility you can check out their website here: www.codility.com

Task one - Dominator

The first task was called Dominator. The goal was to, given a std::vector of integers, find an integer that occurs in more than half of the positions in the vector. If no dominator was found -1 should be returned.

My approach was to loop through the vector from the first to the last element, using a std::map to count the number of occurences of each integer. If the count ever reached above half the size of the vector I stopped and returned that integer and if I reached the end without finding a dominator I returned -1.

So was that a good approach? Well, the reviewer at the company rated the solution as 'pretty ok'. His preferred solution was store the first integer in the array and set a counter to 1. Then loop through the remaining integers in the vector. If the current integer in the vector is the same as the one stored, the counter is increased by one, otherwise the counter is decreased by one. If the counter ever reaches zero you throw away the stored integer and replace it with the current integer in the vector. When you finally have looped through all integers you are left with one candidate. You then need to loop through the vector again and count the occurences of the candidate to verify that this really is a dominator.

Let's check this solution in C++ code:
#include <cstddef>
#include <vector>

int getDominator(const std::vector<int>& A)
{
  if (A.empty())
  {
    return -1;
  }

  int counter = 1;
  int candidate = A[0];

  for (std::size_t i = 1; i < A.size(); ++i)
  {
    if (A[i] == candidate)
    {
      ++counter;
    }
    else
    {
      --counter;
      if (0 == counter)
      {
        candidate = A[i];
        counter = 1;
      }
    }
  }

  counter = 0;
  for (std::size_t i = 0; i < A.size(); ++i)
  {
    if (A[i] == candidate)
    {
      ++counter;
    }
  }
  int dominator = -1;
  if (counter > (A.size() / 2))
  {
    dominator = candidate;
  }

  return dominator;
}

So what do you think? Is there a better solution? Would you had figured this one out?
Stay tuned for Part II - The K-complement.


Etiketter:

Kommentarer

  1. Hitesh25 juli 2012 kl. 17:13

    Hi,

    Have you tested this solution against testcase like A[] = {1,1,1,2,2,2,1,3}?
    I don't think above solution works for above test case.

    SvaraRadera
  2. Eric Bäckhage26 juli 2012 kl. 20:18

    Hi Hitesh,

    Thanks for your comment.
    A[] = {1,1,1,2,2,2,1,3} has no dominator (no integer occurs in more than half the positions). Hence, the algorithm should return -1, which it does.

    SvaraRadera
  3. Krzysztof Kozłowski3 november 2012 kl. 08:06

    Den här kommentaren har tagits bort av skribenten.

    SvaraRadera
  4. SPSoftware18 april 2013 kl. 07:12

    i was wrote two functions.
    first using 'set' and second using 'map'.
    in case if i suspect that the function may return a value other then -1, the second algorithm is fastest.
    in other case both of them gives similar duration times, though the first is a little bit faster.
    can anybody tell me which of these solutions is satisfied (if any).
    = = =
    int function1(const std::vector & A) {
    if (A.empty()) {
    return -1;
    }
    if (A.size() == 1) {
    return 0;
    }
    std::map values;
    unsigned int half = A.size() / 2;
    for (unsigned int index = 0; index < A.size(); index++) {
    if (++values[A[index]] > half) {
    return index;
    }
    }
    return -1;
    }

    int function2(const std::vector & A) {
    if (A.empty()) {
    return -1;
    }
    if (A.size() == 1) {
    return 0;
    }
    std::set usedValues;
    unsigned int half = A.size() / 2;
    unsigned int indexMax = (unsigned int)((float)A.size() / 2.0 + 0.5);
    for (unsigned int index = 0; index < indexMax; index++) {
    if (usedValues.find(A[index]) != usedValues.end()) {
    continue;
    }
    if (std::count(A.begin() + index, A.end(), A[index]) > half) {
    return index;
    }
    usedValues.insert(A[index]);
    }
    return -1;
    }

    SvaraRadera
  5. Eric Bäckhage18 april 2013 kl. 11:59

    Hi ArkadiuszG,

    Your function1 looks pretty much like the solution that I submitted. It should be ok, just some remarks. If A.size() == 1 you probably wish to return A[0], and not 0 right?
    Secondly, try using std::size_t instead of unsigned int when looping up to A.size(). Probably it won't matter but std::size_t should always be able to represent the size of any object.

    SvaraRadera
  6. Unknown6 december 2013 kl. 00:11

    Well then what about this case [1, 1, 3, 3, 3, 3]. So here it will take 1, go to next number counter will be 2, go to next number ( 3rd position) counter will be 1 (as it is not 1). go to the next number (4th position) , counter will be 0 , take 3 and counter will be 1 and in the end counter will be 3 but since it is not counted in 4 places it will give -1. in reality it should give 3

    SvaraRadera
  7. Eric Bäckhage6 december 2013 kl. 02:09

    Hi Prashant

    The algorithm works. Codility has made a version of the Dominator problem available, you can verify it there yourself, see http://codility.com/train/. Note that you will have to make some minor changes since the version available at Codility expects the index number of the dominator to be returned and not the actual dominator value.

    SvaraRadera

Skicka en kommentar

Populära inlägg i den här bloggen

Does TDD really improve software quality?

I have asked myself this question several times, and searched for answers, without coming up with any clear answer. Therefore I have decided to go hard core TDD for a longer period of time (at least 6 months) to really evaluate the effects. There are several things that I find confusing when it comes to TDD. One example is what actually defines a unit test. What is a "unit" anyway? After reading a bit about it I found a text claiming that the "unit" is "a unit of work", i.e. something quite small. Like converting a string to UPPERCASE or splitting a string into an ['a','r', 'r', 'a', 'y'] of chars. This work is usually performed by a single call to a single method in a single, isolated, class. So, what does it mean that a class is isolated? Does it mean that it doesn't have any dependencies to other classes? NO! In the context of TDD it means that any dependencies are supplied by the test environment, for exa...
3 kommentarer
Läs mer

Been reading up on Dijkstra's search algorithm

Last weeks have been a bit slow on the algorithm front. Still on it though. I have been solving some Graph challenges on  www.hackerrank.com  and reading several different texts on Dijkstra's search algorithm. It seems like this is an algorithm that is a bit tough to understand and implement in a correct and efficient way. Dijkstra's algorithm can be used on graphs with weighted edges, i.e. different paths have different costs. As long as the weights have positive values Dijkstra's algorithm should work fine. The procedure is quite similar to Breadth First Search, the difference here being that the total edge weight can be less even when more edges are involved. It is therefore necessary to keep track of the current total, and if a shorter path is found, update the total and the parent node (can be used for printing the vertices visited when traveling the shortest distance from vertex v1 to vertex v2). Dijkstra's algorithm is also greedy, in the sense that it visi...
Skicka en kommentar
Läs mer