- In: Array | C++11 | String
- Leave a Comment
/* Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, * write a method to rotate the image by 90 degrees. */ #include <iostream> #include <array> #include <assert.h> using namespace std; template <class T, size_t COL, size_t ROW> struct Matrix { std::array<std::array<T, COL>, ROW> data; }; template <class T> void Rotate(T &t, size_t rows, size_t columns) { assert (rows == columns); int n = rows; for (int layer = 0; layer < n/2; ++layer) { int first = layer; int last = n - 1 - layer; for (int i = first; i < last; ++i) { int offset = i - first; // save top int top = t[first][i]; // left -> top t[first][i] = t[last - offset][first]; // bottom -> left t[last - offset][first] = t[last][last - offset]; // right -> bottom t[last][last - offset] = t[i][last]; // top -> right t[i][last] = top; } } } template <class T> void PrintMatrix(T &t, size_t rows, size_t columns) { for(size_t i = 0;i < rows; ++i) { for(size_t j = 0;j < columns; ++j) { cout << t[i][j] << "\t"; } cout << endl; } cout << endl; } int main() { Matrix<int, 4, 4> matrix; cout << endl << "Before Rotate:" << endl; int imagebit = 0; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { matrix.data[i][j] = imagebit++; } } PrintMatrix(matrix.data, 4, 4); cout << "After Rotate:" << endl; Rotate(matrix.data, 4, 4); PrintMatrix(matrix.data, 4, 4); return 0; }
- In: Array | C/C++ | String
- Leave a Comment
char* StrStr(const char *str, const char *target) { char *cp = (char *) str; char *s1, *s2; if ( !*target ) { return ((char *)str); } while (*cp) { s1 = cp; s2 = (char *) target; while ( *s1 && *s2 && (*s1 == *s2) ) { ++s1; ++s2; } if (!*s2) { return cp; } ++cp; } return NULL; }
- In: Array | C/C++ | String
- Leave a Comment
Implement a method to perform basic string compression using the counts of repeated characters. For example string “aabcccccaaa” would become “a2b1c5a3“. If the compressed string would not become smaller then original string then return the original string.
int CountCompression(string str) { char last = str.at(0); int size = 0, count = 1; for (int i = 1; i < str.length(); i++) { if(str.at(i) == last) { count++; } else { last = str.at(i); size += 1 + to_string(count).length(); count = 1; } } // we need to count the very last set of repeated character sets size += 1 + to_string(count).length(); return size; } string Compress(string str) { int size = CountCompression(str); if(size >= str.length()) return str; string compressStr; char last = str.at(0); int count = 1; for (int i = 1; i < str.length(); i++) { if (str.at(i) == last) { count++; } else { // insert char count and update the last char compressStr += last; compressStr += to_string(count); last = str.at(i); count = 1; } } // we need to update the very last set of repeated character sets compressStr += last; compressStr += to_string(count); return compressStr; }
- In: Array | C/C++ | String
- Leave a Comment
We are going to write a method to replace all spaces in a string with “%20”. We assume that the string have sufficient space.
void ReplaceSpaces(char *str) { int length = strlen(str); int nSpaces = 0, newLength = 0; for (int i = 0; i < length; i++) { if(str[i] == ' ') ++nSpaces; } newLength = length + nSpaces * 2; str[newLength] = '\0'; for (int i = length - 1 ; i >= 0; i--) { if (str[i] == ' ') { str[newLength - 1] = '0'; str[newLength - 2] = '2'; str[newLength - 3] = '%'; newLength -= 3; } else { str[newLength - 1] = str[i]; newLength -= 1; } } }
- In: Array | C/C++ | String
- Leave a Comment
We are going to write a method to decide if one is a permutation of the other (i.e GOD is a permutation of DOG)
bool IsPermutation(const string &s, const string &t) { if (s.length() != t.length()) { return false; } int letters[256]; for (int i = 0; i < 256; i++) { letters[i] = 0; } // count the number of each char in s for (unsigned int i = 0; i < s.length(); i++) { letters[s.at(i)]++; } for (unsigned int i = 0; i < t.length(); i++) { int c = t.at(i); if(--letters[c] < 0) { return false; } } return true; }