C++编程面试：面试官希望你展示的内容

A 最近的研究 显示C++仍然是最常用的语言（在任何其他VisualStudio官方支持的语言如C语言或Visual Basic）之前。但是，尽管被几代人广泛使用和熟知——感谢它在这里已经存在了几十年，而仍然是学院里最受教育的语言——当你寻找C++开发工作时，这些事实不能保证你会被选中。这将取决于你在节目面试中的表现——以及其他因素。不管你对C++语法有多深，你记住了多少个STL组件，它将是你使用“正确的工具做正确的任务”的能力来定义你的资格。这篇文章看起来像是书中丢失的一章 编程面试揭秘你的下一份工作，第二版 [Mongan，Soujanen，Giguè重新；wrox2007]，但这是基于我参与的一次编程面试中的思考。虽然这个职位最初是为候选人谁将被面试，感觉像一个新手编程面试官可能会从这里得到一些关于什么检查候选人的想法。

在一次采访中，我被要求对一个函数进行伪编码，该函数返回作为输入的罗马数字的十进制等价值。这似乎是一个微不足道的挑战，但有抱负的候选人必须记住的是，首先，面试官并不好奇你的背景与罗马数字。他/她想要检查的是你解决问题的能力。此外，罗马数字系统与十进制系统相比也不是那么简单。它是非位置性的（从某种意义上说，你不会得到最后一个位置上的一个，倒数第二个位置上的十个，前一个位置上的几百个，等等）。除此之外，系统只包含代表10次方幂的符号 (10 ⁿ ，n=0，…，3） 和 5×10 ⁿ （n=0，…，2） . 够诡异了吧？我想知道罗马人创造这个数字系统是为了以后在节目采访中使用它。

关于这些不寻常的特征，我开始做的第一件事——当着面试官的面，手里拿着白板笔——是探索典型的等价物，简单的和不那么简单的罗马数字格，以及它们的预期结果。这两种方法都为我服务，将算法设计成一般情况，并测试我导出的解决方案的正确性。

这些和其他一些例子帮助我们确定罗马数字的一些基本语法规则。重复字符（III，CC，XXX，…）等规则；减法（IX，CD，…）；等。

例如，这些规则也有自己的局限性

换言之，重复只允许出现在字符I、X、C和M（分别为1、10、100和1000）上，而不允许出现在字符V、L、D（分别为5、50、500）上，虽然在这些示例中没有表示，但重复次数也不能超过三次。也不允许减去V，L或D。同样，第三个错误的例子表明，我们可以得到一个字符减去它的直接跟随者，但后者不能减去第三个字符（也就是说，整个罗马数字的减法部分只涉及两个字符）。

谈论所有这些规则、例外和想法，比如大声思考，把它们写在空白处（我的情况是白板，但它可能是给你的一张纸）。如果有的话，用两种不同的颜色来区分做什么和不做什么。

还有其他的语法规则，但是，与我的面试官，我们同意停止在这里，因为已经足够好，以显示一些技能在剩余的时间。

让我们开始构建函数框架、它的公共接口和预期的返回类型

函数名， rtoi（） ，是因为其意图与 原子（） . 这里有几个决定需要解释：

• 返回的类型被选择为 无符号整型 . 罗马数字既不考虑0（零）也不考虑负数。因此，我希望确保返回的类型尽可能严格。 有人可能会说 内景 ，我们本可以采用使用负数表示错误（如无效输入等）的约定，但这种方法的缺点是，函数的调用者必须采取预防措施，明确要求错误条件作为输出。如果调用者没有检查出这个结果，而只是使用结果，那么执行将变成一个不确定的状态。 所以我宁愿把错误升级。我们最近讨论了异常问题，虽然没有一个适合所有人的解决方案，但我喜欢将我的转换异常声明为STL runtime error的子类：

没有规定您的异常应该从STL继承 运行时错误 或者任何其他STL例外，但有一些共识认为，如果这种做法被广泛采用，您可以选择 捕获（…） 省略号在Windows和非Windows系统中可能会捕获除C++异常之外的东西（除了告诉你什么异常发生之外，只是出了什么问题）。 相反，其他一些作者反对抛出异常（他们认为抛出异常是以牺牲运行时开销为代价的），他们建议使用类似于旧的C global的替代方法 厄尔诺 或类似的（特别是当函数用于验证用户输入时）。这些作者建议，在没有其他尝试的情况下，异常抛出应该是最后一种方法。在我的例子中，这个函数只是一个库函数：它可能被一个UI验证器对象调用，或者被另一个不一定与用户输入相关的组件调用，所以我不能像一个人在应用程序前面尝试手动恢复那样假设，这个通用函数将通过抛出异常来对输入错误做出反应。句号。 正如您在上面的代码示例中所看到的，我为任何潜在原因创建了一个通用异常，而不是创建一个完整的异常层次结构，只要我仍然通过其 原因（） 方法（并且，在定义此异常时，通过 std：：运行时错误：：what（） 方法）具体失败的。 好了，关于异常已经说得够多了，让我们继续回顾函数接口。

• 关于它的输入参数，读者可能想知道为什么要将它声明为 常数 . 事实上，这个函数不应该以任何方式修改它的输入。因此，强制这样做并不是一个坏主意，因此，如果有一天，由于维护的结果，任何程序员修改了声明为常量的输入，应用程序将不会编译。
• 考虑输入字符串的另一个方面是我选择它作为 垫圈 而不是简单的 一串 类型。事实上，现在大多数系统都使用扩展的字符集（通常是UNICODE），因为在当前支持互联网的互联时代，它们能更好地处理国际化问题。你不必像我一样讲道理，只要你能理解你所做决定的背景。然而，一个错误的决定，会更倾向于 一串 为简单起见：从编程的角度来看，这两种类型都是同级的，专门化了一种称为basicu string（带 烧焦 和 世界卫生组织 ，取决于简单或扩展的情况）。事实上，如果面试官问你一个通用的解决方案，答案如下：

然而，对于使用STL版本的字符串而不是C样式的以0（零）结尾的字符数组的决定，人们可能会有争论。有利于STL的决定是基于这样一个事实，即它们封装了一个字符串必须完成的许多功能 安全的 . 例如，一个 世界卫生组织* 我们的对手 垫圈 可能没有预期的二进制0（零）结束字符，导致潜在的缓冲区溢出。基于STL的字符串没有这个问题，因为它处理自己的内存（第一个原因），并且它的长度不基于可能丢失的结束标志。STL字符串比C样式的字符串更安全，但这并不意味着它们是安全的。它们只是不太容易出错，因此被一些作者推荐。它们可能会带来一定的开销，但在大多数情况下，这种开销在使用C样式字符串的高质量、防御性编码版本中是不存在的。这只是一个决定程序员是想承担这些开销，还是想利用STL提供给您的那些已经出炉的版本的问题。

• 在函数定义本身内部移动之前，最后一个注释是字符串参数作为引用传递（通过添加符号和修饰符）。这是一个效率问题：如果符号不存在，字符串将按值传递，并被复制到堆栈中，从而产生开销。我宁愿避免那样。

所有这些，让我们来看看函数定义。最后，我将在这里实现一个通用版本（既然我已经提到了这种可能性）

简单地说，这个函数包含在一个通过所有输入字符串字符的循环中。对于每个字符，我们检查它是否重复最后一个字符（如果重复，我们控制重复的字符不会达到4次）。我们还通过调用内联函数来确保不是每个符号都允许重复 不可重复（…） –定义如下：

通过制造 内联 ，我们指示编译器避免进行任何涉及堆栈的显式调用。相反，此代码将在调用方法中跨越，从而进行适当的变量替换。我们可以这样定义宏

但在这种情况下，我们对传递/接收的数据控制较少。内联函数是一种更好的实践，大概不会涉及真正函数调用的开销。

然后，迭代将符号定位在当前迭代中要分析的符号旁边，并将两者传递给函数 GetNexterm（…） . 给定这两个符号，该函数的目的是确定两者是否应组合在减法中（例如IV的典型情况，其中I从V中减去），或类似VI的情况，其中迭代只考虑V，丢弃I（将由下一次迭代拾取）。

因此，该函数的输出是 结构 定义如下

正如读者所看到的 价值 成员包含要添加到当前结果的值。这个 大小 取而代之的是，成员将包含1或2，这取决于是将两个符号都视为减法符号，还是仅将第一个符号视为减法符号而忽略另一个符号。这两项活动可被视为本次会议的结束部分 对于 循环。

让我们通过定义 GetNexterm（…） 功能：

乍一看，这个函数可能看起来势不可挡，但读者会立即发现，它的逻辑是相当基本和重复的，尽管所有可能的情况。

为了完整起见，在面试之前，先对边界条件进行分析。例如，如果作为参数接收的字符串为空（相当于“”）？在我们的例子中，函数将返回0。它也可能引发异常，但我更喜欢前一个选项。

我们还应该测试最初评估的案例，以便确认/调整算法。我已经做过了，但我把这些留给读者作为练习。

从算法本身来看，它遵循复杂度分析。从这个意义上说，我们可以得出结论，它的顺序是线性的长度输入。或者，换句话说，它的复杂性是 O（n） , n 输入的长度，这是可以接受的。尽可能避免的复杂性是二次复杂性- O（无） ² ) –或者更高，更不用说指数了。

A 提供了这个函数的可能实现，以及大量的测试用例和一个逆函数itor（…）——它接受一个整数并返回其罗马等价值 在这里 .

后记

关于编程面试有一个很好的教训：不要做超出要求的事情，因为这可能会让人产生一种消极的看法，认为你在某个特定的时间很难集中精力去做必要的事情。举个例子，我本可以通过创建一个名为RomanNumeric的类来解决这个测试，该类的构造函数接收一个输入字符串，就像我刚刚定义的rtoi（）函数一样，因此我们可以稍后添加RomanNumeric对象，方法是将+运算符、乘法等重新定义为一个全新的数字类型。听起来很棒，但是…这么做有什么意义？在现实世界中，需要这种授权的数据类型的可能性有多大？诚然，本案中提出的问题是假设性的，但是，通过将假设扩展到其原始边界之外来回答假设性问题的原因是什么？

一句话：在解决一个具体的、准时的要求时飞得太高，除了让面试官担心你的能力之外，不会产生任何其他效果 提供精心设计的解决方案而不受诱惑 不必要地对其进行总体架构，可能会丢失 你得到这份工作的机会。