CareerCup

O(n)

void rmDup(string &str) {
   set<char> s;
   for (int i = 0; i < str.size(); i++) {
       if (s.find(str[i]) == s.end()) {
           s.insert(str[i]);
       } else {
           str.erase(i,1);
       }
   }
}

void encode(string &s, string &ret) {
    for (int i = 1; i <= s.size(); i++) {
        int c = 1;
        while (i < s.size() and s[i] == s[i-1]) c++, i++;
        ret += s[i-1];
        ret += c + '0';
    }
}

Generate palindromes in decimal, then for every one check if they are also palindromes in octal. Here is an example of my method finding all palindromes smaller than int max that fit the criteria. It runs in under 0.01s and is O(n), n being the number of digits of the largest palindrome to be generated.

char num[20];

bool isOctPal(unsigned int n) {
    int s = sprintf(num, "%o", n);
    for (int i = 0; i < s/2; i++)
        if (num[i] != num[s-i-1]) return false;
    printf("%d %o\n", n, n);
    return true;
}

int main() {
    int max = 21474;
    for (int n = 0; n < max; n++) {
        int number = n, rem = 0, reverse = 0, pdrome, no_digits = 1;
        while (number != 0)
            reverse = reverse * 10 + number % 10, number /= 10 , no_digits *= 10;
        pdrome = n <= 9 ? n : (no_digits / 10) * n + reverse % (no_digits / 10);
        isOctPal(pdrome);
    }
    return 0;
}

Just Kidding! That's O(n^2) :P

O(n) O(1)!

void sort(int arr[], int n) {
    int nextNonNeg = 0;
    int i = 0;
    for (i, nextNonNeg; i < n; i++, nextNonNeg++)
        if (arr[i] > 0)
            break;

    for (i; i < n; i++) {
        if (arr[i] < 0) {
            int t = arr[i];
            memmove(&(arr[nextNonNeg + 1]), 
                    &(arr[nextNonNeg]), 
                    sizeof(int) * (i - nextNonNeg));
            // swap(arr, i, nextNonNeg);
            arr[nextNonNeg] = t;
            nextNonNeg++;
        }
    }
}

O(n) and O(n)

void sort(int arr[], int n) {
    int dup[n];
    memcpy(dup, arr, sizeof(int) * n);

    int nextNonNeg = 0;
    int i = 0;
    for (i, nextNonNeg; i < n; i++, nextNonNeg++)
        if (arr[i] > 0)
            break;
    for (i; i < n; i++) {
        if (arr[i] < 0) {
            swap(arr, i, nextNonNeg);
            nextNonNeg++;
        }
    }

    int lastNeg = n-1;
    i = n-1;
    for (i, lastNeg; i >= 0; i--, lastNeg--)
        if (dup[i] < 0)
            break;
    for (i; i >= 0; i--) {
        if (dup[i] > 0) {
            swap(dup, i, lastNeg);
            lastNeg--;
        }
    }

    for (int i = 0; i < n; i++)
        if (arr[i] > 0)
            arr[i] = dup[i];
}

int main() {
    int arr[] = { -1, 1, 3, -2, 2, -3, -88, -5, 55, -9 };
    int n = 10;
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    sort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

As explanation for the runtime, the solution is T(n, m) = 5*n*m which is O(n*m). The 5 is since we have 5 n*m loops. And memory is M(n, m) = 4*n*m which is O(n*m), just like OP mentioned. Again, great solution!

I have implemented your algorithm, and it seems to work fine! I really like your solution, easy to implement and very effective!

int findGreatestX(bool **matrix, int m, int n) {
    int **topLeft = new int*[m];
    for (int i = 0; i < m; i++)
        topLeft[i] = new int[n];

    int **topRight = new int*[m];
    for (int i = 0; i < m; i++)
        topRight[i] = new int[n];

    int **botLeft = new int*[m];
    for (int i = 0; i < m; i++)
        botLeft[i] = new int[n];

    int **botRight = new int*[m];
    for (int i = 0; i < m; i++)
        botRight[i] = new int[n];

    // Calculating topLeft
    for (int i = 0; i < m; i++)
        topLeft[i][0] = matrix[i][0];

    for (int i = 0; i < n; i++)
        topLeft[0][i] = matrix[0][i];

    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            topLeft[i][j] = (matrix[i][j]) ? topLeft[i-1][j-1] + 1 : 0;

    // Calculating topRight
    for (int i = 0; i < m; i++)
        topRight[i][n-1] = matrix[i][n-1];

    for (int i = 0; i < n; i++)
        topRight[0][i] = matrix[0][i];

    for (int i = 1; i < m; i++)
        for (int j = n-2; j >= 0; j--)
            topRight[i][j] = (matrix[i][j]) ? topRight[i-1][j+1] + 1 : 0;

    // Calculating botLeft
    for (int i = 0; i < m; i++)
        botLeft[i][0] = matrix[i][0];

    for (int i = 0; i < n; i++)
        botLeft[m-1][i] = matrix[m-1][i];

    for (int i = m-2; i >= 0; i--)
        for (int j = 1; j < n; j++)
            botLeft[i][j] = (matrix[i][j]) ? botLeft[i+1][j-1] + 1 : 0;


    // Calculating botRight
    for (int i = 0; i < m; i++)
        botRight[i][n-1] = matrix[i][n-1];

    for (int i = 0; i < n; i++)
        botRight[m-1][i] = matrix[m-1][i];

    for (int i = m-2; i >= 0; i--)
        for (int j = n-2; j >= 0; j--)
            botRight[i][j] = (matrix[i][j]) ? botRight[i+1][j+1] + 1 : 0;


    int maxMinVal = 0;
    int curMinVal;

    for (int i = 1; i < m-1; i++) {
        for (int j = 1; j < n-1; j++) {
            curMinVal = min(min(botRight[i+1][j+1],
                                botLeft[i+1][j-1]),
                            min(topRight[i-1][j+1],
                                topLeft[i-1][j-1]));
            if (curMinVal > maxMinVal)
                maxMinVal = curMinVal;
        }
    }
    
    return (2*maxMinVal) + 1;
}

Two diagonals of 1's that are of the same size.
101
010
100
Doesn't not have equally sized diagonals

Nice!!! I think you got it! Love your solution, great job!

Exactly! But I know there is a way of solving the problem with only 10 bits. However I'm not sure how.

One way of doing it with 11 bits is like the following:
You use 6 bits to represent your first position, and you use 5 bits to represent your second. You first position is represented by a simple x,y bit scheme. The second position will be represented as follows:
If 5 bits for the second position are passed in, make a x,y grid on the opposite half of the board and use the 5 bits to locate the second position.
If 4 bits are passed in, do the same thing as previously but in the opposite quadrant on the same half of the first picked point.
If 3 bits, use them to find it on the opposite eight on the same quadrant
If 2 bits , on the opposite sixteenth of the same eight
If 1, on the same thirtysecondth of the same sixteenth
if no bits, the second position is right below/above the first one

So basically you exploit the fact that no 2 pieces can be in the same place and save a bit

It is true that a naive way can use 12 bits. All you need to do is label the different rows and columns of the board from 0-7 and use that as a x,y guide. That way, just like you described, you can use 12 bits. However, I know there is a way of doing it with only 10 bits. I'm just not sure how.

That's good enough to only represent one position. We need to represent 2.