crack the coding interview

时间：2022-09-18 21:05:22

crack the coding interview

answer
c++

1.1

  1. #ifndef __Question_1_1_h__ 
  2. #define __Question_1_1_h__ 
  4. #include <string> 
  6. using std::string; 
  8. class Question1_1  
  9. { 
  10. public: 
  11. int run(); 
  12. bool isUniqueChars(const string& str); 
  13. bool isUniqueChars2(const string& str); 
  14. string result(bool value); 
  15. };  
  17. #endif // __Question_1_1_h__ 
  19. #include<iostream> 
  20. #include<string> 
  21. #include "Question1_1.h" 
  22. using namespace std; 
  24. bool Question1_1::isUniqueChars(const string& str) 
  25. { 
  26. if (str.length() > 256)  
  27. { 
  28. return false; 
  29. } 
  31. unsigned int checker = 0; 
  33. for (int i = 0; i < str.length(); ++i)  
  34. { 
  35. int value = str[i] - 'a'; 
  37. if ((checker & (1 << value)) != 0) 
  38. { 
  39. return false; 
  40. } 
  42. checker |= (1 << value); 
  43. } 
  45. return true; 
  46. } 
  48. bool Question1_1::isUniqueChars2(const string& str)  
  49. { 
  50. if (str.length() > 256)  
  51. { 
  52. return false; 
  53. } 
  55. bool ascii_set[256] = { false }; 
  57. for (int i = 0; i < str.length(); ++i)  
  58. { 
  59. int value = str[i]; 
  61. if (ascii_set[value])  
  62. { 
  63. return false; 
  64. } 
  66. ascii_set[value] = true;  
  67. } 
  69. return true; 
  70. } 
  72. /* Function to print true and false */ 
  73. string Question1_1::result(bool value) 
  74. { 
  75. if (value)  
  76. { 
  77. return "True"; 
  78. } 
  80. return "False"; 
  81. } 
  83. int Question1_1::run()  
  84. { 
  85. string input[] ={"abcde", "aba"}; 
  87. for (int i = 0; i < 2; i++)  
  88. { 
  89. cout << input[i] << " has unique characters: " << result(isUniqueChars(input[i])) << endl; 
  90. cout << input[i] << " has unique characters: " << result(isUniqueChars2(input[i])) << endl; 
  91. } 
  93. return 0; 
  94. } 

1.2

  1. #ifndef __Question_1_2_h__ 
  2. #define __Question_1_2_h__ 
  4. class Question1_2  
  5. { 
  6. public: 
  7. int run(); 
  8. void reverse(char* str); 
  9. };  
  11. #endif // __Question_1_2_h__ 
  12. #include<iostream> 
  13. #include "Question1_2.h" 
  15. using std::cout; 
  16. using std::endl; 
  18. void Question1_2::reverse(char* str)  
  19. { 
  20. char *ptrEnd = str; 
  21. char temp; 
  23. if (str)  
  24. { 
  25. while (*ptrEnd)  
  26. { 
  27. ptrEnd++; 
  28. } 
  29. ptrEnd--; 
  31. while (str < ptrEnd)  
  32. { 
  33. temp = *str; 
  34. *str++ = *ptrEnd; 
  35. *ptrEnd-- = temp; 
  36. } 
  37. } 
  38. } 
  40. int Question1_2::run()  
  41. { 
  42. char input[][10] = { "abcde", "cat" }; 
  44. for (int i = 0; i < 2; i++)  
  45. { 
  46. cout << "reversing the string: " << input[i] << endl; 
  47. reverse(input[i]); 
  48. cout << "reverse of input string is " << input[i] << endl; 
  49. } 
  51. return 0; 
  52. } 

1.3

  1. #ifndef __Question_1_3_B_h__ 
  2. #define __Question_1_3_B_h__ 
  4. #include <string> 
  6. using std::string; 
  8. class Question1_3_B  
  9. { 
  10. public: 
  11. int run(); 
  12. bool permutation(const string& a, const string& b); 
  13. string result(bool value); 
  14. };  
  16. #endif // __Question_1_3_B_h__ 
  18. #include<iostream> 
  19. #include<string> 
  20. #include<algorithm> 
  21. #include "Question1_3_B.h" 
  23. using namespace std; 
  25. bool Question1_3_B::permutation(const string& a, const string& b)  
  26. { 
  27. if (a.length() != b.length())  
  28. { 
  29. return false; 
  30. } 
  32. int ascii_set[256] = {0}; 
  34. for (int i = 0; i < a.length(); i++)  
  35. { 
  36. int val = static_cast<int>(a[i]); 
  37. ascii_set[val]++; 
  38. } 
  40. for (int i = 0; i < b.length(); i++)  
  41. { 
  42. int val = static_cast<int>(b[i]); 
  44. if ((--ascii_set[val]) < 0)  
  45. { 
  46. return false; 
  47. } 
  48. } 
  50. return true; 
  51. } 
  53. string Question1_3_B::result(bool value)  
  54. { 
  55. if (value)  
  56. { 
  57. return "True"; 
  58. } 
  60. return "False"; 
  61. } 
  63. int Question1_3_B::run()  
  64. { 
  65. string a = "apple"; 
  66. string b = "papel"; 
  68. cout << "Result for " << a << " and " << b << " is " << result(permutation(a, b)) << endl; 
  70. return 0; 
  71. } 

1.4

  1. #ifndef __Question_1_4_h__ 
  2. #define __Question_1_4_h__ 
  3. #include <memory> 
  5. class Question1_4  
  6. { 
  7. public: 
  8. int run(); 
  9. void replaceSpaces(std::unique_ptr<char[]>&, int length); 
  10. };  
  12. #endif // __Question_1_4_h__ 
  14. #include<iostream> 
  15. #include<memory> 
  16. #include<string> 
  17. #include "Question1_4.h" 
  19. using namespace std; 
  21. void Question1_4::replaceSpaces(unique_ptr<char[]> &str, int length) //char str[] 
  22. { 
  23. int newLength, spaceCount = 0; 
  25. //count the number of spaces in the given string. 
  26. for (int i = 0; i < length; i++)  
  27. { 
  28. if (str[i] == ' ')  
  29. { 
  30. spaceCount++; 
  31. } 
  32. } 
  34. //calculate new string size. 
  35. newLength = length + spaceCount * 2; 
  36. str[newLength] = '\0'; 
  38. //copying the characters backwards and inserting %20 
  39. for (int i = length - 1; i >= 0; i--)  
  40. { 
  41. if (str[i] == ' ')  
  42. { 
  43. str[newLength - 1] = '0'; 
  44. str[newLength - 2] = '2'; 
  45. str[newLength - 3] = '%'; 
  46. newLength -= 3; 
  47. }  
  48. else 
  49. { 
  50. str[newLength - 1] = str[i]; 
  51. newLength--; 
  52. } 
  53. } 
  54. } 
  56. int Question1_4::run()  
  57. { 
  58. string str = "abc d e f"; 
  60. // Increasing length of the string to meet question requirement of 'true' length by using char array. (Note: using a unique_ptr here) 
  61. auto newStr = make_unique<char[]>(str.length() + 3 * 2 + 1); 
  63. for (int i = 0; i < str.length(); i++)  
  64. { 
  65. newStr[i] = str[i]; 
  66. } 
  68. cout << "Original string is " << str << endl; 
  69. replaceSpaces(newStr, str.length()); 
  70. cout << "New string with %20 is " << newStr.get() << endl; 
  72. return 0; 
  73. } 

1.5

  1. #ifndef __Question_1_5_h__ 
  2. #define __Question_1_5_h__ 
  4. #include <string> 
  6. using std::string; 
  8. class Question1_5  
  9. { 
  10. public: 
  11. int run(); 
  12. int stringToInt(const string& value); 
  13. string intToString(int value); 
  14. int countCompression(const string& str); 
  16. /// C++ std::string is efficient and no need to use a "StringBuffer"-like structure. 
  17. string compressBetter(const string& str); 
  18. };  
  20. #endif // __Question_1_5_h__ 
  22. #include<iostream> 
  23. #include<string> 
  24. #include<sstream> 
  25. #include "Question1_5.h" 
  27. using namespace std; 
  29. int Question1_5::stringToInt(const string& value)  
  30. { 
  31. int temp; 
  32. stringstream(value) >> temp; 
  34. return temp; 
  35. } 
  37. string Question1_5::intToString(int value)  
  38. { 
  39. string temp; 
  40. stringstream convert; 
  41. convert << value; 
  42. temp = convert.str(); 
  44. return temp; 
  45. } 
  47. int Question1_5::countCompression(const string& str) 
  48. { 
  49. if (str.length() == 0)  
  50. { 
  51. return 0; 
  52. } 
  54. char last = str.at(0); 
  55. int size = 0; 
  56. int count = 1; 
  58. for (int i = 1; i < str.length(); i++)  
  59. { 
  60. if (str.at(i) == last)  
  61. { 
  62. count++; 
  63. } 
  64. else 
  65. { 
  66. last = str.at(i); 
  67. size = size + 1 + intToString(count).length(); 
  68. count = 1; 
  69. } 
  70. } 
  71. size = size + 1 + intToString(count).length(); 
  73. return size; 
  74. } 
  76. string Question1_5::compressBetter(const string& str)  
  77. { 
  78. int size = countCompression(str); 
  80. if(size >= str.length())  
  81. { 
  82. return str; 
  83. } 
  85. string newstr; 
  86. char last = str.at(0); 
  87. int count = 1; 
  89. for (int i = 1; i < str.length(); i++)  
  90. { 
  91. if (str.at(i) == last)  
  92. { 
  93. count++; 
  94. } 
  95. else 
  96. { 
  97. newstr += last; 
  98. newstr.append(intToString(count)); 
  99. last = str.at(i); 
  100. count = 1; 
  101. } 
  102. } 
  103. newstr += last; 
  104. newstr.append(intToString(count)); 
  106. return newstr; 
  107. } 
  109. int Question1_5::run()  
  110. { 
  111. string str = "abbccccccde"; 
  112. string newstr = compressBetter(str); 
  113. cout << "Original string is " << str << endl; 
  114. cout << "Compressed string is " << newstr << endl; 
  116. return 0; 
  117. } 

1.6

  2. #ifndef __Question_1_6_h__ 
  3. #define __Question_1_6_h__ 
  5. class Question1_6  
  6. { 
  7. public: 
  8. /** 
  9. * Since we can't provide variable matrix size in C++, we will do it "the c way" and will provide a 1-dimensional 
  10. * array 
  11. */ 
  12. void rotate(int* matrix, int n); 
  13. void printMatrix(int* matrix, int m, int n); 
  14. int run(); 
  15. }; 
  17. #endif // __Question_1_6_h__ 
  19. #include <iostream> 
  20. #include <memory> 
  21. #include "Question1_6.h" 
  23. using namespace std; 
  25. void Question1_6::rotate(int* matrix, int n)  
  26. { 
  27. for (int layer = 0; layer < n / 2; ++layer)  
  28. { 
  29. int first = layer; 
  30. int last = n - 1 - layer; 
  32. for (int i = first; i < last; ++i)  
  33. { 
  34. int offset = i - first; 
  35. // save top 
  36. int top = matrix[first * n + i]; 
  38. // left to top 
  39. matrix[first * n + i] = matrix[(last-offset) * n + first]; 
  41. // bottom to left 
  42. matrix[(last-offset) * n + first] = matrix[last * n + (last-offset)]; 
  44. // right to bottom 
  45. matrix[last * n + (last-offset)] = matrix[i * n + last]; 
  47. // top to right 
  48. matrix[i * n + last] = top; 
  49. } 
  50. } 
  51. } 
  53. void Question1_6::printMatrix(int* matrix, int m, int n)  
  54. { 
  55. for (int i = 0; i < m; ++i)  
  56. { 
  57. for (int j = 0; j < n; ++j)  
  58. { 
  59. cout << matrix[i * n + j] << " "; 
  60. } 
  62. cout << endl; 
  63. } 
  64. } 
  66. int Question1_6::run()  
  67. { 
  68. int matrix[][5] ={{1, 2, 3, 4, 5}, 
  69. {6, 7, 8, 9, 10}, 
  70. {11, 12, 13, 14, 15}, 
  71. {16, 17, 18, 19, 20}, 
  72. {21, 22, 23, 24, 25}}; 
  73. int* matrixPtr = (int*)matrix; 
  75. cout << "original matrix is :" << endl; 
  76. printMatrix(matrixPtr, 5, 5); 
  77. rotate(matrixPtr, 5); 
  78. cout << "rotated matrix is: " << endl; 
  79. printMatrix(matrixPtr, 5, 5); 
  81. return 0; 
  82. } 

1.7

  1. #ifndef __Question_1_7_h__ 
  2. #define __Question_1_7_h__ 
  4. class Question1_7  
  5. { 
  6. public: 
  7. /** 
  8. * Since we can't provide variable matrix size in C++, we will do it "the c way" and will provide a 1-dimensional 
  9. * array 
  10. */ 
  11. void setZeros(int* matrix, int m, int n); 
  12. void printMatrix(int* matrix, int m, int n); 
  13. int run(); 
  14. }; 
  16. #endif // __Question_1_7_h__ 
  18. #include <iostream> 
  19. #include "Question1_7.h" 
  21. using namespace std; 
  23. void Question1_7::setZeros(int* matrix, int m, int n)  
  24. { 
  25. // Assuming M,N <= 32, we'll use a bit vector to represent whether a row/col should be set with zeros. 
  26. int m_rows = 0; 
  27. int m_cols = 0; 
  29. for (int i = 0; i < m; ++i)  
  30. { 
  31. for (int j = 0; j < n; ++j)  
  32. { 
  33. if (matrix[i * n + j] == 0)  
  34. { 
  35. m_rows |= (1 << i); 
  36. m_cols |= (1 << j); 
  37. } 
  38. } 
  39. } 
  41. for (int i = 0; i < m; ++i)  
  42. { 
  43. for (int j = 0; j < n; ++j)  
  44. { 
  45. if (((m_rows & (1 << i)) != 0) || ((m_cols & (1 << j)) != 0))  
  46. { 
  47. matrix[i * n + j] = 0; 
  48. } 
  49. } 
  50. } 
  51. } 
  53. void Question1_7::printMatrix(int* matrix, int m, int n)  
  54. { 
  55. for (int i = 0; i < m; ++i) 
  56. { 
  57. for (int j = 0; j < n; ++j) 
  58. { 
  59. cout << matrix[i * n + j] << " "; 
  60. } 
  62. cout << endl; 
  63. } 
  64. } 
  67. int Question1_7::run()  
  68. { 
  69. int matrix[4][5] ={{1, 2, 3, 4, 5}, 
  70. {6, 7, 8, 9, 10}, 
  71. {11, 12, 0, 14, 15}, 
  72. {16, 17, 18, 0, 20}}; 
  73. int* matrixPtr = (int*)matrix; 
  74. cout << "original matrix is :" << endl; 
  75. printMatrix(matrixPtr, 4, 5); 
  77. setZeros(matrixPtr, 4, 5); 
  78. cout << "zeroed matrix is: " << endl; 
  79. printMatrix(matrixPtr, 4, 5); 
  81. return 0; 
  82. } 

1.8

  1. #ifndef __Question_1_8_h__ 
  2. #define __Question_1_8_h__ 
  4. #include <string> 
  6. using std::string; 
  8. class Question1_8  
  9. { 
  10. public: 
  11. string result(bool value); 
  12. bool isRotation(const string& s1, const string& s2); 
  13. int run(); 
  14. }; 
  16. #endif // __Question_1_8_h__ 
  18. #include<iostream> 
  19. #include<string> 
  20. #include "Question1_8.h" 
  22. using namespace std; 
  24. bool Question1_8::isRotation(const string& s1, const string& s2) 
  25. { 
  26. int len = s1.length(); 
  28. if(len == s2.length() && len > 0)  
  29. { 
  30. string s1s1 = s1 + s1; 
  31. return s1s1.find(s2) != string::npos; 
  32. } 
  34. return false; 
  35. } 
  37. string Question1_8::result(bool value) 
  38. { 
  39. if (value)  
  40. { 
  41. return "True"; 
  42. } 
  44. return "False"; 
  45. } 
  47. int Question1_8::run()  
  48. { 
  49. string a = "apple"; 
  50. string b = "leapp"; 
  51. cout << "Checking if string: " << a << " is a rotation of string: " << b << ": " 
  52. << result(isRotation(a, b)) << endl; 
  54. a = "james"; 
  55. b = "mesje"; 
  56. cout << "Checking if string: " << a << " is a rotation of string: " << b << ": " 
  57. << result(isRotation(a, b)) << endl; 
  59. return 0; 
  60. } 

crack the coding interview的更多相关文章

  1. Cracking the coding interview

    写在开头 最近忙于论文的开题等工作,还有阿里的实习笔试,被虐的还行,说还行是因为自己的水平或者说是自己准备的还没有达到他们所需要人才的水平,所以就想找一本面试的书<Cracking the co ...

  2. 转：Top 10 Algorithms for Coding Interview

    The following are top 10 algorithms related concepts in coding interview. I will try to illustrate t ...

  3. Cracking the coding interview 第一章问题及解答

    Cracking the coding interview 第一章问题及解答 不管是不是要挪地方,面试题具有很好的联系代码总用,参加新工作的半年里,做的大多是探索性的工作,反而代码写得少了,不高兴,最 ...

  4. Cracking the Coding Interview（Trees and Graphs）

    Cracking the Coding Interview(Trees and Graphs) 树和图的训练平时相对很少,还是要加强训练一些树和图的基础算法.自己对树节点的设计应该不是很合理,多多少少 ...

  5. Cracking the Coding Interview（Stacks and Queues）

    Cracking the Coding Interview(Stacks and Queues) 1.Describe how you could use a single array to impl ...

  6. 《Cracking the Coding Interview》读书笔记

    <Cracking the Coding Interview>是适合硅谷技术面试的一本面试指南,因为题目分类清晰,风格比较靠谱,所以广受推崇. 以下是我的读书笔记,基本都是每章的课后习题解 ...

  7. Cracking the coding interview目录及资料收集

    前言 <Cracking the coding interview>是一本被许多人极力推荐的程序员面试书籍, 详情可见:http://www.careercup.com/book. 第六版 ...

  8. Python Coding Interview

    Python Coding Interview Python Advanced Use enumerate() to iterate over both indices and values Debu ...

  9. whiteboard &amp&semi; coding interview practice

    whiteboard & coding interview practice 白板 & 面试 & 编码练习 Algorithm https://www.freecodecamp ...

随机推荐

  1. Omi原理-Hello Omi

    Hello Omi Omi框架的每个组件都继承自Omi.Component,本篇会去完成Omi的Component的基本锥形,让其能够渲染第一个组件. omi.js实现 var Omi = {}; O ...

  2. AFO

    留坑 有点绝望 状态什么的,存在么 upd at 2017/11/14还算完满地结束了OI之路了吧.

  3. requests使用retry策略

    在urllib3中使用retry 在requests中使用retry 网络请求往往会有很多不受控制的意外情况发生,有时候我们要让它let it crash,有时候我们想多尝试几次. 以前,使用retr ...

  4. Concept Drift&lpar;概念漂移&rpar;

    Introdution concept drift在机器学习.时间序列以及模式识别领域的一种现象.如果是在机器学习领域中,这个概念指的就是一个模型要去预测的一个目标变量,概念漂移就是这个目标变量随着时 ...

  5. java开发mis系统所需技术及其作用

    MIS(管理信息系统--Management Information System)系统 ,是一个由人.计算机及其他外围设备等组成的能进行信息的收集.传递.存贮.加工.维护和使用的系统. 是一门新兴的 ...

  6. asp&period;net上传大文件-请求筛选模块被配置为拒绝超过请求内容长度的请求

    HTTP错误404.13 - Not Found 请求筛选模块被配置为拒绝超过请求内容长度的请求,原因是Web服务器上的请求筛选被配置为拒绝该请求,因为内容长度超过配置的值(IIS 7 默认文件上传大 ...

  7. ldap禁止匿名用户登录

    此处默认ldap已经安装完成,安装文档传送门:https://www.cnblogs.com/crysmile/p/9470508.html openldap默认安装完成,是允许匿名用户登录的,因此需 ...

  8. 【C&plus;&plus;自我精讲】基础系列六 PIMPL模式

    [C++自我精讲]基础系列六 PIMPL模式 0 前言 很实用的一种基础模式. 1 PIMPL解释 PIMPL(Private Implementation 或 Pointer to Implemen ...

  9. 软工2017第六周团队协作——个人PSP

    10.20 --10.26本周例行报告 1.PSP(personal software process )个人软件过程. 类型 任务 开始时间                结束时间 中断时间 实际用 ...

  10. BZOJ 4236 JOIOJI（前缀和）

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=4236 [题目大意] 给出一个只包含三种字母的字符串,求出三种字母数量相等的最长子串 [ ...

相关文章