crack the coding interview

answer

c++

1.1

#ifndef __Question_1_1_h__ 
#define __Question_1_1_h__ 
 
#include <string> 
 
using std::string; 
 
class Question1_1  
{ 
public: 
    int run(); 
    bool isUniqueChars(const string& str); 
    bool isUniqueChars2(const string& str); 
    string result(bool value); 
};  
 
#endif // __Question_1_1_h__ 
 
#include<iostream> 
#include<string> 
#include "Question1_1.h" 
using namespace std; 
 
bool Question1_1::isUniqueChars(const string& str) 
{ 
    if (str.length() > 256)  
    { 
        return false; 
    } 
 
    unsigned int checker = 0; 
     
    for (int i = 0; i < str.length(); ++i)  
    { 
        int value = str[i] - 'a'; 
 
        if ((checker & (1 << value)) != 0) 
        { 
            return false; 
        } 
 
        checker |= (1 << value); 
    } 
 
    return true; 
} 
 
bool Question1_1::isUniqueChars2(const string& str)  
{ 
    if (str.length() > 256)  
    { 
        return false; 
    } 
 
    bool ascii_set[256] = { false }; 
 
    for (int i = 0; i < str.length(); ++i)  
    { 
        int value = str[i]; 
 
        if (ascii_set[value])  
        { 
            return false; 
        } 
 
        ascii_set[value] = true;     
    } 
 
    return true; 
} 
 
/* Function to print true and false */ 
string Question1_1::result(bool value) 
{ 
    if (value)  
    { 
        return "True"; 
    } 
 
    return "False"; 
} 
 
int Question1_1::run()  
{ 
    string input[] ={"abcde", "aba"}; 
 
    for (int i = 0; i < 2; i++)  
    { 
        cout << input[i] << " has unique characters: " << result(isUniqueChars(input[i])) << endl; 
        cout << input[i] << " has unique characters: " << result(isUniqueChars2(input[i])) << endl; 
    } 
 
    return 0; 
} 

1.2

#ifndef __Question_1_2_h__ 
#define __Question_1_2_h__ 
 
class Question1_2  
{ 
public: 
    int run(); 
    void reverse(char* str); 
};  
 
#endif // __Question_1_2_h__ 
#include<iostream> 
#include "Question1_2.h" 
 
using std::cout; 
using std::endl; 
 
void Question1_2::reverse(char* str)  
{ 
    char *ptrEnd = str; 
    char temp; 
 
    if (str)  
    { 
        while (*ptrEnd)  
        { 
            ptrEnd++; 
        } 
        ptrEnd--; 
 
        while (str < ptrEnd)  
        { 
            temp = *str; 
            *str++ = *ptrEnd; 
            *ptrEnd-- = temp; 
        } 
    } 
} 
 
int Question1_2::run()  
{ 
    char input[][10] = { "abcde", "cat" }; 
 
    for (int i = 0; i < 2; i++)  
    { 
        cout << "reversing the string: " << input[i] << endl; 
        reverse(input[i]); 
        cout << "reverse of input string is " << input[i] << endl; 
    } 
 
    return 0; 
} 

1.3

#ifndef __Question_1_3_B_h__ 
#define __Question_1_3_B_h__ 
 
#include <string> 
 
using std::string; 
 
class Question1_3_B  
{ 
public: 
    int run(); 
    bool permutation(const string& a, const string& b); 
    string result(bool value); 
};  
 
#endif // __Question_1_3_B_h__ 
 
#include<iostream> 
#include<string> 
#include<algorithm> 
#include "Question1_3_B.h" 
 
using namespace std; 
 
bool Question1_3_B::permutation(const string& a, const string& b)  
{ 
    if (a.length() != b.length())  
    { 
        return false; 
    } 
 
    int ascii_set[256] = {0}; 
 
    for (int i = 0; i < a.length(); i++)  
    { 
        int val = static_cast<int>(a[i]); 
        ascii_set[val]++; 
    } 
 
    for (int i = 0; i < b.length(); i++)  
    { 
        int val = static_cast<int>(b[i]); 
 
        if ((--ascii_set[val]) < 0)  
        { 
            return false; 
        } 
    } 
 
    return true; 
} 
 
string Question1_3_B::result(bool value)  
{ 
    if (value)  
    { 
        return "True"; 
    } 
 
    return "False"; 
} 
 
int Question1_3_B::run()  
{ 
    string a = "apple"; 
    string b = "papel"; 
 
    cout << "Result for " << a << " and " << b << " is " << result(permutation(a, b)) << endl; 
     
    return 0; 
} 

1.4

#ifndef __Question_1_4_h__ 
#define __Question_1_4_h__ 
#include <memory> 
 
class Question1_4  
{ 
public: 
    int run(); 
    void replaceSpaces(std::unique_ptr<char[]>&, int length); 
};  
 
#endif // __Question_1_4_h__ 
 
#include<iostream> 
#include<memory> 
#include<string> 
#include "Question1_4.h" 
 
using namespace std; 
 
void Question1_4::replaceSpaces(unique_ptr<char[]> &str, int length) //char str[] 
{ 
    int newLength, spaceCount = 0; 
 
    //count the number of spaces in the given string. 
    for (int i = 0; i < length; i++)  
    { 
        if (str[i] == ' ')  
        { 
            spaceCount++; 
        } 
    } 
 
    //calculate new string size. 
    newLength = length + spaceCount * 2; 
    str[newLength] = '\0'; 
 
    //copying the characters backwards and inserting %20 
    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--; 
        } 
    } 
} 
 
int Question1_4::run()  
{ 
    string str = "abc d e f"; 
 
    // Increasing length of the string to meet question requirement of 'true' length by using char array. (Note: using a unique_ptr here) 
    auto newStr = make_unique<char[]>(str.length() + 3 * 2 + 1); 
 
    for (int i = 0; i < str.length(); i++)  
    { 
        newStr[i] = str[i]; 
    } 
 
    cout << "Original string is " << str << endl; 
    replaceSpaces(newStr, str.length()); 
    cout << "New string with %20 is " << newStr.get() << endl; 
  
    return 0; 
} 

1.5

#ifndef __Question_1_5_h__ 
#define __Question_1_5_h__ 
 
#include <string> 
 
using std::string; 
 
class Question1_5  
{ 
public: 
    int run(); 
    int stringToInt(const string& value); 
    string intToString(int value); 
    int countCompression(const string& str); 
 
    /// C++ std::string is efficient and no need to use a "StringBuffer"-like structure. 
    string compressBetter(const string& str); 
};  
 
#endif // __Question_1_5_h__ 
 
#include<iostream> 
#include<string> 
#include<sstream> 
#include "Question1_5.h" 
 
using namespace std; 
 
int Question1_5::stringToInt(const string& value)  
{ 
    int temp; 
    stringstream(value) >> temp; 
 
    return temp; 
} 
 
string Question1_5::intToString(int value)  
{ 
    string temp; 
    stringstream convert; 
    convert << value; 
    temp = convert.str(); 
 
    return temp; 
} 
 
int Question1_5::countCompression(const string& str) 
{ 
    if (str.length() == 0)  
    { 
        return 0; 
    } 
 
    char last = str.at(0); 
    int size = 0; 
    int count = 1; 
 
    for (int i = 1; i < str.length(); i++)  
    { 
        if (str.at(i) == last)  
        { 
            count++; 
        } 
        else 
        { 
            last = str.at(i); 
            size = size + 1 + intToString(count).length(); 
            count = 1; 
        } 
    } 
    size = size + 1 + intToString(count).length(); 
 
    return size; 
} 
 
string Question1_5::compressBetter(const string& str)  
{ 
    int size = countCompression(str); 
 
    if(size >= str.length())  
    { 
        return str; 
    } 
 
    string newstr; 
    char last = str.at(0); 
    int count = 1; 
 
    for (int i = 1; i < str.length(); i++)  
    { 
        if (str.at(i) == last)  
        { 
            count++; 
        } 
        else 
        { 
            newstr += last; 
            newstr.append(intToString(count)); 
            last = str.at(i); 
            count = 1; 
        } 
    } 
    newstr += last; 
    newstr.append(intToString(count)); 
 
    return newstr; 
} 
 
int Question1_5::run()  
{ 
    string str = "abbccccccde"; 
    string newstr = compressBetter(str); 
    cout << "Original string is " << str << endl; 
    cout << "Compressed string is " << newstr << endl; 
  
    return 0; 
} 

1.6

 
#ifndef __Question_1_6_h__ 
#define __Question_1_6_h__ 
 
class Question1_6  
{ 
public: 
    /** 
     * Since we can't provide variable matrix size in C++, we will do it "the c way" and will provide a 1-dimensional 
     * array 
     */ 
    void rotate(int* matrix, int n); 
    void printMatrix(int* matrix, int m, int n); 
    int run(); 
}; 
 
#endif // __Question_1_6_h__ 
 
#include <iostream> 
#include <memory> 
#include "Question1_6.h" 
 
using namespace std; 
 
void Question1_6::rotate(int* matrix, int n)  
{ 
    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 = matrix[first * n + i]; 
 
            // left to top 
            matrix[first * n + i] = matrix[(last-offset) * n + first]; 
 
            // bottom to left 
            matrix[(last-offset) * n + first] = matrix[last * n + (last-offset)]; 
 
            // right to bottom 
            matrix[last * n + (last-offset)] = matrix[i * n + last]; 
 
            // top to right 
            matrix[i * n + last] = top; 
        } 
    } 
} 
 
void Question1_6::printMatrix(int* matrix, int m, int n)  
{ 
    for (int i = 0; i < m; ++i)  
    { 
        for (int j = 0; j < n; ++j)  
        { 
            cout << matrix[i * n + j] << " "; 
        } 
 
        cout << endl; 
    } 
} 
 
int Question1_6::run()  
{ 
    int matrix[][5] ={{1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10}, 
                      {11, 12, 13, 14, 15}, 
                      {16, 17, 18, 19, 20}, 
                      {21, 22, 23, 24, 25}}; 
    int* matrixPtr = (int*)matrix; 
     
    cout << "original matrix is :" << endl; 
    printMatrix(matrixPtr, 5, 5); 
    rotate(matrixPtr, 5); 
    cout << "rotated matrix is: " << endl; 
    printMatrix(matrixPtr, 5, 5); 
  
    return 0; 
} 

1.7

#ifndef __Question_1_7_h__ 
#define __Question_1_7_h__ 
 
class Question1_7  
{ 
public: 
    /** 
    * Since we can't provide variable matrix size in C++, we will do it "the c way" and will provide a 1-dimensional 
    * array 
    */ 
    void setZeros(int* matrix, int m, int n); 
    void printMatrix(int* matrix, int m, int n); 
    int run(); 
}; 
 
#endif // __Question_1_7_h__ 
 
#include <iostream> 
#include "Question1_7.h" 
 
using namespace std; 
 
void Question1_7::setZeros(int* matrix, int m, int n)  
{ 
    // Assuming M,N <= 32, we'll use a bit vector to represent whether a row/col should be set with zeros. 
    int m_rows = 0; 
    int m_cols = 0; 
 
    for (int i = 0; i < m; ++i)  
    { 
        for (int j = 0; j < n; ++j)  
        { 
            if (matrix[i * n + j] == 0)  
            { 
                m_rows |= (1 << i); 
                m_cols |= (1 << j); 
            } 
        } 
    } 
 
    for (int i = 0; i < m; ++i)  
    { 
        for (int j = 0; j < n; ++j)  
        { 
            if (((m_rows & (1 << i)) != 0) || ((m_cols & (1 << j)) != 0))  
            { 
                matrix[i * n + j] = 0; 
            } 
        } 
    } 
} 
 
void Question1_7::printMatrix(int* matrix, int m, int n)  
{ 
    for (int i = 0; i < m; ++i) 
    { 
        for (int j = 0; j < n; ++j) 
        { 
            cout << matrix[i * n + j] << " "; 
        } 
 
        cout << endl; 
    } 
} 
 
 
int Question1_7::run()  
{ 
    int matrix[4][5] ={{1, 2, 3, 4, 5}, 
                       {6, 7, 8, 9, 10}, 
                       {11, 12, 0, 14, 15}, 
                       {16, 17, 18, 0, 20}}; 
    int* matrixPtr = (int*)matrix; 
    cout << "original matrix is :" << endl; 
    printMatrix(matrixPtr, 4, 5); 
     
    setZeros(matrixPtr, 4, 5); 
    cout << "zeroed matrix is: " << endl; 
    printMatrix(matrixPtr, 4, 5); 
  
    return 0; 
} 

1.8

#ifndef __Question_1_8_h__ 
#define __Question_1_8_h__ 
 
#include <string> 
 
using std::string; 
 
class Question1_8  
{ 
public: 
    string result(bool value); 
    bool isRotation(const string& s1, const string& s2); 
    int run(); 
}; 
 
#endif // __Question_1_8_h__ 
 
#include<iostream> 
#include<string> 
#include "Question1_8.h" 
 
using namespace std; 
 
bool Question1_8::isRotation(const string& s1, const string& s2) 
{ 
    int len = s1.length(); 
 
    if(len == s2.length() && len > 0)  
    { 
        string s1s1 = s1 + s1; 
        return s1s1.find(s2) != string::npos; 
    } 
 
    return false; 
} 
 
string Question1_8::result(bool value) 
{ 
    if (value)  
    { 
        return "True"; 
    } 
 
    return "False"; 
} 
 
int Question1_8::run()  
{ 
    string a = "apple"; 
    string b = "leapp"; 
    cout << "Checking if string: " << a << " is a rotation of string: " << b << ": " 
         << result(isRotation(a, b)) << endl; 
 
    a = "james"; 
    b = "mesje"; 
    cout << "Checking if string: " << a << " is a rotation of string: " << b << ": " 
        << result(isRotation(a, b)) << endl; 
 
    return 0; 
} 

crack the coding interview

crack the coding interview

1.1

1.2

1.3

1.4

1.5

1.6

1.7

1.8

推荐阅读