一个C++面试题[更新说明]

混不到坑的萝卜

务求完美，你还是去debug一下吧，嘿嘿

菜地一块

呵呵，嗯，是判断结尾那个地方搞错了。不是'\n'，是'\0'。

1. #include <iostream>
   
2. using namespace std;
   
3. void f(char* pSZ)
   
4. {
   
5.         char temp;
   
6.         const int iLen = strlen(pSZ);
   
7.         //整个字符串倒序
   
8.         for ( int iIndex = 0; iIndex < iLen/2; ++iIndex )
   
9.         {
   
10.                 temp = *(pSZ + iIndex);
    
11.                 *(pSZ + iIndex) = *(pSZ + iLen - 1 - iIndex);
    
12.                 *(pSZ + iLen - 1 - iIndex) = temp;
    
13.         }
    
14.         //按单词倒序
    
15.         int iBlank = 0;
    
16.         for ( int iIndex = 0; iIndex <= iLen; ++iIndex )
    
17.         {
    
18.                 if ( *(pSZ + iIndex) == ' ' || *(pSZ + iIndex) == '\0')
    
19.                 {
    
20.                         for ( int iIndex2 = iBlank; iIndex2 < iBlank + (iIndex - iBlank)/2; ++iIndex2 )
    
21.                         {
    
22.                                 temp = *(pSZ+iIndex2);
    
23.                                 *(pSZ+iIndex2) = *(pSZ + iBlank + iIndex - 1 - iIndex2);
    
24.                                 *(pSZ + iBlank + iIndex - 1 - iIndex2) = temp;
    
25.                         }
    
26.                         iBlank = iIndex + 1;
    
27.                 }
    
28.         }
    
29. }
    
30. 
    
31. int main(int argc, char** argv)
    
32. {
    
33.         char pSZ[] = "What the hell";
    
34.         cout << "before:\t" << pSZ << endl;
    
35.         f(pSZ);
    
36.         cout << "after:\t" << pSZ << endl;
    
37.         return 0;
    
38. }

复制代码

psaux

15分钟只能写成这样了

void f(char* pSZ) {
        string s = "";
        char* pch;
        pch = strtok(pSZ, " ");
        while (pch != NULL) {
                s = " " + string(pch) + s;
                pch = strtok(NULL, " ");
        }
        strcpy(pSZ, s.substr(1).c_str());
}

ingeer

不好意思沒看仔細，原來是從輸入的指針再輸出。。 拿 char * 做輸入輸出肯定不是什麼好的C++ sample了。。不過既然題目說是C++，那就來一個C++倒序吧, 這裏可以看出來C++ TEMPLATE LIB比C的強大之處。。

#include <list>
#include <sstream>
#include <iterator>
using namespace std;
   
void f(char * pSZ)
{
        istringstream iss(pSZ);
        list<string> t;
        copy(istream_iterator<string>(iss), istream_iterator<string>(), front_inserter<list<string> >(t));
        ostringstream oss;
        copy(t.begin(), t.end(), ostream_iterator<string>(oss," "));
        sprintf(pSZ, oss.str().c_str());
}

輸出會多一個空格在尾巴。。

[ 本帖最后由 ingeer 于 2011-8-16 08:28 编辑 ]

philowen

原帖由 菜地一块 于 2011-8-15 22:34 发表
呵呵，嗯，是判断结尾那个地方搞错了。不是'\n'，是'\0'。#include
using namespace std;
void f(char* pSZ)
{
        char temp;
        const int iLen = strlen(pSZ);
        //整个字符串倒序
        for ( int iIndex = 0; iIndex < iLen/2;  ...

差不多，把代码提出来成一个reverse（）函数，在两次倒序的时候可以重用。这样更完美一点。

rogerk

Bloody show off...

看没看到题目要求空间效率是O(1)阿？你这内存分配的漫天遍野的。。。template是拿来用的，不是拿来show off的。。

C++是用来解决问题的，不是用来装B的。。

原帖由 ingeer 于 2011-8-16 08:11 发表
不好意思沒看仔細，原來是從輸入的指針再輸出。。 拿 char * 做輸入輸出肯定不是什麼好的C++ sample了。。不過既然題目說是C++，那就來一個C++倒序吧, 這裏可以看出來C++ TEMPLATE LIB比C的強大之處。。

#include
#inc ...

ingeer

原帖由 rogerk 于 2011-8-16 11:47 发表
Bloody show off...

看没看到题目要求空间效率是O(1)阿？你这内存分配的漫天遍野的。。。template是拿来用的，不是拿来show off的。。

C++是用来解决问题的，不是用来装B的。。

有話好好說不行麼？ 一口一個B的，解個問題火氣這麼大？這種CODE還用SHOW OFF？工作裏基本上都是這種CODE，方便讀，好維護，出錯機率小 你滿是指針的CODE就是用來解決問題的了？不知道你們公司的CODING STANDARD是什麼，我猜基本上90%的公司都會要你回去重寫 -.-"

那麼我滿足你。。

#include <algorithm>
void f(char * pSZ)
{
        char * pEnd= std::find(pSZ, (char *)0, 0);
        std::reverse(pSZ, pEnd);
        char * p1=pSZ;
        while (p1 < pEnd)
        {
                char * p2= std::find(p1, pEnd, ' ');
                std::reverse(p1, p2);
                p1 = p2+1;
        }
}

STL裏有N多這樣的基本算法，既然考C++，不用類庫還要自己用C編算法，不是笑話麼？

rogerk

你看看楼上的这些回帖把，这个楼里除了你以外基本上所有人都明白这个题目是在考什么。。。你真的以为只有你知道这几个函数可以用阿？
这是面试题，考虑一下场景。。。

我也不知道你是真不明白还是装不明白。。。不过你要说的我也明白了，你熟读STL，还知道STL有这么多这么多算法。。牛

原帖由 ingeer 于 2011-8-16 12:13 发表

有話好好說不行麼？ 一口一個B的，解個問題火氣這麼大？這種CODE還用SHOW OFF？工作裏基本上都是這種CODE，方便讀，好維護，出錯機率小 你滿是指針的CODE就是用來解決問題的了？不知道你們公司的CODING STANDARD是什麼，我猜基本上90% ...

混不到坑的萝卜

俺在UNSW读书的时候，8门课就买过唯一一本教材，而且保存到现在的，就是那本STL的书了。偶尔翻翻还是有点意思的。

rogerk

STL是好东西。。。我也很喜欢STL..

不过，就像鱼翅是好东西一样，不过你逮到人家下碗方便面充饥的说，你们家下面条居然不放鱼翅阿，那怎么能下好面条呢，这面条怎么能吃呢，真是笑话阿。。你看，哪家面馆的面条Standard是不放鱼翅的，不放鱼翅的肯定得回去重新下阿，来来来，看我给你下一碗鱼翅捞面，哦，一碗800块啊，没关系阿，我们就这个高标准。

原帖由 混不到坑的萝卜 于 2011-8-16 12:32 发表
俺在UNSW读书的时候，8门课就买过唯一一本教材，而且保存到现在的，就是那本STL的书了。偶尔翻翻还是有点意思的。

ingeer

呵呵，樓上朋友的心態不怎麼樣啊。。另外謝謝誇獎

bullying520

LS几位说的在理 也许那位朋友确实是大牛 随便一写就写出了很神奇的代码 不过再大牛也要看清题目 否则很杯具的...装X的目的不仅没达到 反而落得一身骂名 自己心里还不爽 何必呢

rogerk

恩。。也谢谢你觉得我是在夸奖。。

原帖由 ingeer 于 2011-8-16 13:00 发表
呵呵，樓上朋友的心態不怎麼樣啊。。另外謝謝誇獎

psaux

原帖由 rogerk 于 2011-8-16 12:26 发表
你看看楼上的这些回帖把，这个楼里除了你以外基本上所有人都明白这个题目是在考什么。。。你真的以为只有你知道这几个函数可以用阿？
这是面试题，考虑一下场景。。。

我也不知道你是真不明白还是装不明白。。。不过你要说的我也明白了，你熟读STL，还知道STL有这么多这么多算法。。牛

兄弟，此言差矣。lz在1楼就说的很明白，实现功能就能拿分，如能做到内存优化，能拿到额外分。lz在35楼也说了可用c++函数，并在58楼已经申明在现场应该写不出如此代码，可能功能都实现不了。如此看来，你能在15分钟内用已知的函数实现功能，尽管不是最优，一定比实现不了功能的代码要强。另外，函数就是拿来用的，不用函数干操pointer，这才叫show off

bullying520

不管你们明白不明白 反正我是不明白了 好端端的有什么好吵的 show off的继续show 不懂的继续不懂.....
说真的 又要回到素质这个话题上了...很没劲

rogerk

原帖由 psaux 于 2011-8-16 13:16 发表


兄弟，此言差矣。lz在1楼就说的很明白，实现功能就能拿分，如能做到内存优化，能拿到额外分。lz在35楼也说了可用c++函数，并在58楼已经申明在现场应该写不出如此代码，可能功能都实现不了。如此看来，你能在15分钟内用已知的函数实现功能，尽管不是最优，一定比实现不了功能的代码要强。另外，函数就是拿来用的，不用函数干操pointer，这才叫show off

我还就不理解这题有多难了，搞这么复杂。就两个指针互相倒倒而已，10分钟写一个看看。。（手写的）


#include "stdafx.h"

void reverse(char* p1, char* p2)
{
        while (p1 != p2 && (p2-p1) > 0)
        {
                char temp = *p2;
                *p2 = *p1;
                *p1 = temp;

                p1++;
                p2--;
        }
}

void f(char* pInOut)
{
        char *p1 = NULL, *p2 = NULL;

        p1 = pInOut;
        while (*p1 != 0)
        {
                p2 = p1;
                p1++;
        }

        p1 = pInOut;
        reverse(p1, p2);

        p1 = pInOut;
        p2 = pInOut;

        while (*p1 != 0)
        {
                while (*p2 != ' ' && *p2 != 0)
                {
                        p2++;
                }

                reverse(p1, (p2-1));

                p1 = p2+1;
                p2 = p1;
        }
}

int _tmain(int argc, _TCHAR* argv[])
{
        char in[256] = "what the hell";
       
        f(in);

        printf("%s", in);
        return 0;
}

[ 本帖最后由 rogerk 于 2011-8-16 14:40 编辑 ]

菜地一块

好啦好啦，大家不要争了，又不是赢房子赢地；我到现在连工作都木有呢，呵呵
这个题目其实也是一个很小的玩意儿，与其说是编程题，不如说是数学题；如果真是在工作中遇到这样的问题，有无数种办法能够解决问题的。而且我想大部分人包括我在内都会选择STL，也不会在意那一点点的效率优劣。从这个角度上来说，其实这里很多人都是满足要求的，大家都是一个合格的开发人员。
不过我个人觉得站在应聘者的角度，这个题目主要是考察人的算法基础、逻辑思维能力等等。因为在一个很大的系统里面，可能会真的遇到对效率要求特别高的场合，例如说，海量的数据处理等。在这里，一点小小的优化，也许就能让客户端少等上几十分钟，或者让您的系统能够运行在比较破的机器上。这时候，您的数学功底可能就派上用场了。 如果真的去应聘，我想大家都会尽量想拿到那额外的分数，毕竟对方可能是想找最好的人。

乱码

c++这边比c#那边能人多

nis

2 min:

void f(char* pSZ)
{
  int iLen = strlen(pSZ);
  for(int i=0; i<iLen/2; i++)
  {
    char cTemp = *(pSZ+i);
    *(pSZ+i) = *(pSZ+iLen-i);
    *(pSZ+iLen-i) = cTemp;
  }
}

nis

[quote]原帖由 nis 于 2011-8-17 13:02 发表

优化一下：

void f(char* pSZ)
{
  int iLen = strlen(pSZ);
  char* ph = pSZ;
  char* pt = pSZ + iLen;
  for(int i=0; i < iLen/2; i++)
  {
    char cTemp = *ph;
    *ph++ = *pt;
    *pt-- = cTemp;
  }
}

菜地一块

原帖由 nis 于 2011-8-17 13:07 发表
[quote]原帖由 nis 于 2011-8-17 13:02 发表

优化一下：

void f(char* pSZ)
{
  int iLen = strlen(pSZ);
  char* ph = pSZ;
  char* pt = pSZ + iLen;
  fo ...

呵呵，LS的朋友可能没有看清题目的要求，并不是倒序那么简单哟～
如果只是单纯倒个个，直接用STL reverse函数就行了。