Coding brain teaser to update an array (language agnostic)

Question

All,

I need a clever way to implement this algorithm (for work) as quickly and cleanly as possible: I think I've removed all the language specific issues and boiled it down to this:

I have two arrays: A and B.

A has a list of names in it {Apple, Apple, Banana, Banana, Banana, Carrot, ...} each i-th value has no upper limit on the number of times it can appear in A. There can be just one "Apple" or a zillion.

Each entry in A has a matching entry in B. (many to many mapping). For example:

A[0] = "Apple"      B[0] = "0027"
A[1] = "Apple"      B[1] = "0028"
A[2] = "Banana"     B[2] = "0073"
A[3] = "Banana"     B[3] = "0041"
A[4] = "Banana"     B[4] = "0069"

If there are 100 or fewer instances of an entry in A, (if there are <= 100 Bananas) then they must all share the same initial "B" value. If there are more than 100, then the first 100 must share the same B values, but the next 100 will have the B[i + 100] th value.

Example if there are 102 apples

A[0]   = "Apple"       B[0]   = "0027"
A[1]   = "Apple"       B[1]   = "0028"
...
A[99]  = "Apple"       B[99]  = "0073"
A[100] = "Apple"       B[100] = "0041"
A[101] = "Apple"       B[101] = "0069"
A[102] = "Banana"      B[102] = "0123"

Then the result that I want is this:

A[0]   = "Apple"       B[0]   = "0027"
A[1]   = "Apple"       B[1]   = "0027"
...
A[99]  = "Apple"       B[99]  = "0027"
A[100] = "Apple"       B[100] = "0041"
A[101] = "Apple"       B[101] = "0041"
A[102] = "Banana"      B[102] = "0123"

I'm sure there are some super brains out there that can come up with the crappy algorithm I've devised, so let's see it!

Edit: Guess I should point out that this was for work. I thought this was a fun challenge that someone might want to look at and possibly come up with a better solution than the one I came up with.

Edit: thanks to daniel for pointing out my dumb mistakes.

My solution just for comparison:

(pseudo code)

first make a hash/dictionary of B, called d where d[ "Apple" ] = number of instances of Apple in A.

while (i < A.count)
{
    string cmp = A[i];
    int v = d[cmp];
    int j=i;

    while (v--) {
       B[j++] = B[i];

       if (j %100 == 0)
       i += j
    }
    i+= d[cmp];
}

doing this from memory, hope I didn't screw up an indexes...

Answer 1

I'd want to build up a dictionary/hashtable, something like

{'Apple':
    {'NumberSeen':102,
     'BValues':['0027','0041']
    },
 'Banana':
    {'NumberSeen':1,
     'BValues':['0123']
    }
}

Then you loop over this, adding a new b value if NumberSeen%100 = 1, then recreate the B-array from this dictionary.

EDIT: This gets you a readable solution which handles an unsorted list. I just saw your 'list is sorted' comment, which means you can do it a lot simpler, in O(1) space, but I'm not sure how clear the code would be.

Answer 2

My suggestion in C# as far as I unterstood the question and assuming the arrays are sorted.

String[] A = GetAs();
String[] B = GetBs();

Int32 count = 0;
Int32 index = 1;

while (index < A.Length)
{
   if (A[index] != A[index - 1])
   {
      count = 0;
   }

   currentCount++;

   if ((A[index] == A[index - 1]) && (count % 100 != 1))
   {
      B[index] = B[index - 1];
   }

   index++;
}

If one likes it compact (and a zero based count).

String[] A = GetAs();
String[] B = GetBs();

Int32 c = 0, i = 1;

while (i < A.Length)
{
   c = (A[i] == A[i - 1]) ? c + 1 : 0;

   B[i] = ((A[i] == A[i - 1]) && (c % 100 != 0)) ? B[i - 1] : B[i];

   i++;
}

Answer 3

String curFruit = A[0];
int curFruitCount = 0;
for (int i = 1; i < A.length; i++) {
    if (A[i].equals(curFruit) && curFruitCount < 100) {
        B[i] = B[i-1];
        curFruitCount++;
    }else{
        curFruit = A[i];
        curFruitCount = 1;
    }
}

Answer 4

I really like Daniel Brückner's solution but I think you might be able to make one enhancement on it. Assuming the 'A's are sorted and spurts of 100 consecutive identical fruits are common, then you could take advantage of that by adding the following check:

String[] A = GetAs();
String[] B = GetBs();
Int32 c = 0, i = 1;
while (i < A.Length)
{   
    if(i+99 < A.Length && A[i] == A[i+99])
    {
        for(int j=1;j<100;j++) b[i+j] = b[i];

        i = i+99;
    }
    else
    {
        B[i] = (A[i] == A[i - 1]) ? B[i - 1] : B[i];   
        i++;
    }
}