pretonesio
BAN USER 1of 1 vote
AnswersGiven a n by m matrix of bits find the largest X that is formed in the matrix and return the size of the diagonal of that X. An X is defined as 2 equally sized diagonals that share a single 1.
 pretonesio in United States for Powerpoint
For instance, the matrix:
00100001
00010010
00001100
00001100
00010010
00100001
Will return a size of 1, because the given X is invalid as the middle part does not share a single 1. On the other hand, the following matrix
101
010
101
Will return a value of 3, as the diagonal is 3. Write such program, Report Duplicate  Flag  PURGE
Microsoft SDE2 Algorithm  5of 7 votes
AnswersWhat is the minimum representation in bits of two positions on an 8x8 chessboard?
 pretonesio in United States for Outlook Report Duplicate  Flag  PURGE
Microsoft SDE1 Brain Teasers
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[i1]) c++, i++;
ret += s[i1];
ret += c + '0';
}
}

pretonesio
November 07, 2013 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[si1]) 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;
}

pretonesio
November 05, 2013 Just Kidding! That's O(n^2) :P
 pretonesio September 11, 2013O(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++;
}
}
}

pretonesio
September 11, 2013 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 = n1;
i = n1;
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;
}

pretonesio
September 11, 2013 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!
 pretonesio September 07, 2013I 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[i1][j1] + 1 : 0;
// Calculating topRight
for (int i = 0; i < m; i++)
topRight[i][n1] = matrix[i][n1];
for (int i = 0; i < n; i++)
topRight[0][i] = matrix[0][i];
for (int i = 1; i < m; i++)
for (int j = n2; j >= 0; j)
topRight[i][j] = (matrix[i][j]) ? topRight[i1][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[m1][i] = matrix[m1][i];
for (int i = m2; i >= 0; i)
for (int j = 1; j < n; j++)
botLeft[i][j] = (matrix[i][j]) ? botLeft[i+1][j1] + 1 : 0;
// Calculating botRight
for (int i = 0; i < m; i++)
botRight[i][n1] = matrix[i][n1];
for (int i = 0; i < n; i++)
botRight[m1][i] = matrix[m1][i];
for (int i = m2; i >= 0; i)
for (int j = n2; 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 < m1; i++) {
for (int j = 1; j < n1; j++) {
curMinVal = min(min(botRight[i+1][j+1],
botLeft[i+1][j1]),
min(topRight[i1][j+1],
topLeft[i1][j1]));
if (curMinVal > maxMinVal)
maxMinVal = curMinVal;
}
}
return (2*maxMinVal) + 1;
}

pretonesio
September 07, 2013 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!
 pretonesio August 29, 2013Exactly! But I know there is a way of solving the problem with only 10 bits. However I'm not sure how.
 pretonesio August 28, 2013One 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 07 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.
 pretonesio August 28, 2013That's good enough to only represent one position. We need to represent 2.
 pretonesio August 28, 2013
RepGet powerful wazifa to know who did black magic. Guru Ji is the master of black magic totke, kala jadu ...
Open Chat in New Window
O(n)
 pretonesio December 19, 2013