诺基亚的面试题，考得很深!!!

作者：evon0207165 | 来源：互联网 | 2023-05-18 22:18

题目很简单，但是考的很深：设计一个算法，输入一个字符串，转化为一个整数。如何设计上面的算法？我的解决方法：函数原型：intatoi（char*pnum,

题目很简单，但是考的很深：
设计一个算法，输入一个字符串，转化为一个整数。

如何设计上面的算法？

我的解决方法：
函数原型：
int atoi（char* pnum, int & error）;

需要考虑：
1. 字符串中正负号的考虑。
===》略掉正负号，先转化，转化结果乘上1或-1.

2. 字符串中有不合法字符，如何处理？
===》传入参数中加一个是否正常转化的参数，如果没有错误发生正常转化，参数为0，否则为一个代表某种错误代码的负数。
3. 字符串长度不确定，存储整数的空间不够用，怎么办？
===》存储转化后结果的空间根据字符串长度动态申请。
4. 字符串很长（比如1K个字符），超过整数的最大值，该如何存储？
===》重新定义一个结构体，分别存储大数的高位和低位。
5. 如何知道字符串的长度？
===》通过strlen获得长度或增加参数直接传递。

上面是我能想到的问题以及解决方法，肯定不全面，也有不对的地方，欢迎拍砖！！！

248 个解决方案

#1

好久不“考试”了，大家一起再回味吧......

#2

字符串很长（比如1K个字符），超过整数的最大值，该如何存储？
这一点不需要考虑，你的返回值是int 超过10位就不行了，也没必要考虑，这个不是考点。

字符串长度不确定，存储整数的空间不够用，怎么办？
存储整数的空间只需要4个字节，这是你不需要考虑的，存入字符串的buffer稍微大点就行了，多了也没用，原因上面说过了。

#3

函数原型都给出来了是int,超过的部分可能还是要舍去

#4

人家说了是转化成整数了, 你考虑的问题有点多了, 接口还没设计好, 就考虑些有的没得, 你能写出这种实现足够了.

[User:root Time:22:14:20 Path:/home/liangdong/c]$ ./output 

0 0 0

1 -1 1

2 -2 2

3 -3 3

4 -4 4

5 -5 5

6 -6 6

7 -7 7

8 -8 8

9 -9 9

10 -10 10

11 -11 11

12 -12 12

13 -13 13

14 -14 14

15 -15 15

16 -16 16

17 -17 17

18 -18 18

19 -19 19

20 -20 20

21 -21 21

22 -22 22

23 -23 23

24 -24 24

25 -25 25

26 -26 26

27 -27 27

28 -28 28

29 -29 29

30 -30 30

31 -31 31

32 -32 32

33 -33 33

34 -34 34

35 -35 35

36 -36 36

37 -37 37

38 -38 38

39 -39 39

40 -40 40

41 -41 41

42 -42 42

43 -43 43

44 -44 44

45 -45 45

46 -46 46

47 -47 47

48 -48 48

49 -49 49

[User:root Time:22:14:21 Path:/home/liangdong/c]$ cat src/main.c 

#include 

#include 

#include 

#include 



int atoi(const char *nptr) {

        int factor = 1;

        if (strncmp(nptr, "+", 1) == 0) {

                nptr += 1;

        } else if (strncmp(nptr, "-", 1) == 0) {

                nptr += 1;

                factor = -1;

        }

        int n = 0;

        while (*nptr != '\0') {

                if (!isdigit(*nptr)) {

                        break;

                }

                n = (n * 10) + (*nptr - '0');

                ++ nptr;

        }

        return factor * n;

}



int main(int argc, char* const argv[]) {

        char number[20];

        int i;

        for (i = 0; i < 50; ++ i) {

                snprintf(number, 20, "+%d", i);

                printf("%d ", atoi(number));

                snprintf(number, 20, "-%d", i);

                printf("%d ", atoi(number));

                snprintf(number, 20, "%d", i);

                printf("%d\n", atoi(number));

        }

        return 0;

}

NAME

       atoi, atol, atoll, atoq - convert a string to an integer



SYNOPSIS

       #include 



       int atoi(const char *nptr);

       long atol(const char *nptr);

       long long atoll(const char *nptr);

       long long atoq(const char *nptr);



   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):



       atoll():

           _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE || _POSIX_C_SOURCE >= 200112L;

           or cc -std=c99



DESCRIPTION

       The atoi() function converts the initial portion of the string pointed to by nptr to int.  The behavior is the same as



           strtol(nptr, (char **) NULL, 10);



       except that atoi() does not detect errors.



       The  atol()  and atoll() functions behave the same as atoi(), except that they convert the initial portion of the string to their return type of long or

       long long.  atoq() is an obsolete name for atoll().

#5

#include 

#include 

#include 

#include 



// never return an error 

int atoi(const char *nptr) {

        if (nptr == NULL) {

                return 0;

        }

        int factor = 1;

        if (strncmp(nptr, "+", 1) == 0) {

                nptr += 1;

        } else if (strncmp(nptr, "-", 1) == 0) {

                nptr += 1;

                factor = -1;

        }

        int n = 0;

        while (*nptr != '\0') {

                if (!isdigit(*nptr)) {

                        break;

                }

                n = (n * 10) + (*nptr - '0');

                ++ nptr;

        }

        return factor * n;

}



int main(int argc, char* const argv[]) {

        char number[20];

        int i;

        for (i = 0; i < 50; ++ i) {

                snprintf(number, 20, "+%d", i);

                printf("%d ", atoi(number));

                snprintf(number, 20, "-%d", i);

                printf("%d ", atoi(number));

                snprintf(number, 20, "%d", i);

                printf("%d\n", atoi(number));

        }

        return 0;

}

貌似贴了个不安全的,没判断空指针.

#6

楼主考虑的还是很多的，嗨，我只考虑整数了

int atoi(u_char *line, size_t n)
{
    int  value;

    if (n == 0) {
        return -1;
    }

    for (value = 0; n--; line++) {
        if (*line < '0' || *line > '9') {
            return -1;
        }

        value = value * 10 + (*line - '0');
    }

    if (value < 0) {
        return -1;

    } else {
        return value;
    }
}

#7

我也觉得这是一个很基础的题目，可能很多公司面试的时候都会考到，只是楼主想多了，以为大公司就考的深哦。不一定的。

#8

格式化一下代码，

int atoi(u_char *line, size_t n)

{

  int value;



  if (n == 0) {

  return -1;

  }



  for (value = 0; n--; line++) {

  if (*line < '0' || *line > '9') {

  return -1;

  }



  value = value * 10 + (*line - '0');

  }



  if (value < 0) {

  return -1;



  } else {

  return value;

  }

}

#9

为什么都以为是数字串呢，怎么没有可能是计算hash值呢？

#10

还要过滤掉首位数字是0？

#11

首位数字是0，不影响结果啊。所以不用考虑这个因素。
C语言库函数atoi实现了下列转换：
"325"     325
"-325"    -325
"a325"    0
"325a"    325

#12

若有非法字符存在，应该返回一个指示吧，而不是前面那些已经转化成的数

#13

题外话，他们不是在裁员吗？怎么还在招啊

#14

引用 13 楼的回复:

题外话，他们不是在裁员吗？怎么还在招啊

裁员肯定也会招新人的啊，不可能光出不进呀。

#15

明天就要去Nokia面试了 :D

#16

我表示LZ真的是想多了！

#17

这题目不是一个很简单的atoi的题目么，溢出的话就返回INT_MAX或者INT_MIN。
而且都告诉你返回整数了，你还费尽心思去考虑什么字符串过长，动态分配内存什么的不是蛋疼吗？题目都不看清楚都开始瞎想？

#18

怎么大家考虑的都是数字字符串了，字符字符串也要考虑啊，abcdefgh123456, a也有相应的assic码啊，特殊字符就省去好了

#19

科学计数法是否没有考虑？

#20

boost::lexical_cast

#21

很奇怪，题目并没有说是由数字组成的字符串也没有说是数学表达式，更没有说需要逆运算

他只不过是让你求 CRC16(短整型) 或 CRC32(长整型)，搞那么复杂干什么？

#22

看来我得好好补补基础了。。。

#23

看看学校一下

#24

我觉得一个函数不需要设计的过分完美，考虑所有异常情况，只需要在适当的时候加入适当的判断就好。
至于其他的异常情况，写好文档，交给更上层的调用来完成。

#25

#26

#27

该回复于2012-06-06 08:48:04被版主删除

#28

该回复于2012-06-06 09:46:44被版主删除

#29

如果是一个很大的字符串，转为整数，就有点复杂

#30

K&R第二版有这个

#31

我表示LZ真的是想多了！

#32

#33

楼主不会被录用的，
想法太多，不单纯，

#34

该回复于2012-06-06 09:46:44被版主删除

#35

考虑的全面很好，如果是找了一堆麻烦那就不对了。有些实际中不出现的问题不用考虑吧！

#36

该回复于2012-06-06 09:46:44被版主删除

#37

楼主想法不错！

#38

LZ真的想多了 int返回就表明了
下面是本人版本：

int atoi(char* str,int *err)

{

  int len=lstrlenA(str);

  int ret=0;



  int i=0;

  if('-'==str[0]||'+'==str[0])

  {

      i=1;

  }

  for(;i
  {

      if(str[i]<'0'||str[i]>'9')

      {

        *err=1;

        ret=0;

        break;

      }

      ret=ret*10+(str[i]-'0');

  }

  if('-'==str[0])

  {

      ret=~ret+1;

  }

  return ret;

}

#39

该回复于2012-06-06 09:57:41被版主删除

#40

该回复于2012-06-06 09:57:14被版主删除

#41

该回复于2012-06-06 09:57:52被版主删除

#42

楼主运气好，我去nokia面试的时候的题目是atoi的加强版，
除了传入字符外，还需要一个表示N进制的传入参数，意思是返回任意进制的整数。
表示在半个小时内想出很OK的方案并用英语跟老外沟通解释压力很大。

#43

该回复于2012-06-06 09:46:59被版主删除

#44

我觉得应该一位一位转

#45

#46

该回复于2012-06-06 09:58:13被版主删除

#47

该回复于2012-06-06 09:58:21被版主删除

#48

#include 

#include 



int zsh_atoi(const char *str)

{

	int ret = 0;

	int tmp;

	int flag = 0;

	if(!str) return 0;

	while(isspace(*str)) ++ str;

	if('-' == *str) {

		flag = 1;

		++str;

	}

	while(isdigit(*str)) {

		tmp = ret * 10 + (*str - '0');

		ret = tmp;

		++str;

	}

	if(flag) return -ret;

	return ret;

}



int main(int argc, char *argv[])

{

	fprintf(stdout, "%d ...\n", zsh_atoi("	  1237891234567788324"));//有没有好的方法判断是否溢出

	fprintf(stdout, "%d ...\n", zsh_atoi(" 	-456"));

	fprintf(stdout, "%d ...\n", zsh_atoi("789abc"));

	fprintf(stdout, "%d ...\n", zsh_atoi("abc789"));

	fprintf(stdout, "%d ...\n", zsh_atoi("-abc"));

	fprintf(stdout, "%d ...\n", zsh_atoi("-789abc"));

	fprintf(stdout, "%d ...\n", zsh_atoi("abc789abc"));

	fprintf(stdout, "%d ...\n", zsh_atoi("-abc789abc"));

	return 0;

}

效率应该还可以，不过如何判断是否有乘法溢出呢？用判断加减法溢出的方法行不通。判断是否有溢出标志？高人指教下。

#49

该回复于2012-06-06 10:07:26被版主删除

#50

先
http://www.microsoft.com/visualstudio/en-us/products/2010-editions/visual-cpp-express
右边Visual C++ 2010 Express下面的Select language...下拉选‘简体中文’，再按Install Now按钮

再参考
C:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src\xtoa.c

推荐阅读

ip
【BZOJ1076】【SCOI2008】奖励关（DP、期望、状压）

DescriptionclickmeSolution套路的状压期望DP题。。。考虑倒退期望：设fi,jrolepresentationstyleposi ... [详细]

蜡笔小新 2023-10-15 10:43:49
ip
Comet OJ - Contest #2 B　她的想法、他的战斗（概率　＋　数学）

题目描述Takuru是一名情报强者，所以他想利用他强大的情报搜集能力来当中间商赚差价。Takuru的计划是让Hinae帮他去市场上买一个商品，然后再以另一个价格卖掉它。Takur ... [详细]

蜡笔小新 2023-10-15 11:48:13
ip
UNP总结 Chapter 12~14 IPv4与IPv6的互操作性、守护进程和inet超级服务器、高级I/O函数

一、IPv4与IPv6的互操作性1.IPv4客户与IPv6服务器拥有双重协议栈的主机的一个基本特性就是：其上运行的IPv6服务器既能应付IPv4客户，又能应付IPv6客户。这是通过使用IPv4映射 ... [详细]

蜡笔小新 2024-09-30 18:55:51
ip
[USACO 2006 November Gold] 玉米地Corn Fields

题目描述　　FarmerJohn新买了一块长方形的牧场，这块牧场被划分成M行N列(1<M<12;1<N<12)，每一格都是一块正方形的土地。FJ打 ... [详细]

蜡笔小新 2024-09-29 11:31:29
ip
3357: [Usaco2004]等差数列

3357:[Usaco2004]等差数列TimeLimit:10SecMemoryLimit:128MBSubmit:321Solved:153[Submit][Status][D ... [详细]

蜡笔小新 2024-09-29 09:37:36
io
九宫格计算

九宫格计算. ... [详细]

蜡笔小新 2024-09-30 19:37:45
buffer
＜C/C++＞输入整型数组和排序标识，对其元素按照升序或降序进行排序

题目描述输入整型数组和排序标识，对其元素按照升序或降序进行排序（一组测试用例可能会有多组数据）本题有多组输入，请使用whil ... [详细]

蜡笔小新 2024-09-30 18:28:29
int
主席树学习

很好的博客：https:blog.csdn.netqq_39809664articledetails79934516可持久化数组#include#inclu ... [详细]

蜡笔小新 2024-09-30 15:02:35
header
openssl 实现https 网站

下面是一个用openssl实现获取https网页内容的demo，整个流程比较简单，主要封装的API如下staticinthttps_init(http ... [详细]

蜡笔小新 2024-09-29 16:41:10
ip
opencv3用椭圆拟合二维点集fitEllipse函数

#include#include#includeusingnamespacecv;usingname ... [详细]

蜡笔小新 2024-09-29 10:47:44
ip
flex 联机游戏开发中国象棋游戏:(一)核心逻辑

在开发四国军棋的游戏中，通过flex联机游戏开发-四国军棋游戏(五)-提炼棋类开发api,我们提炼出了第一个关于棋类游戏开发的api-FlexChessAPI,这个a ... [详细]

蜡笔小新 2024-09-26 19:21:43
ip
JavaBean和Map 转换用反射方法实现

由于JavaBean（实体类）结构与Map类似，我们可以把JavaBean与Map进行转换 ... [详细]

蜡笔小新 2024-09-26 16:42:58
int
APUE学习笔记可变参数（apue中错误输出函数的实现）

2019独角兽企业重金招聘Python工程师标准voiderr_dump(constchar*fmt,){va_listap;va_start(ap,fmt);初始化 ... [详细]

蜡笔小新 2023-10-16 10:06:39
io
[APIO2012]派遣解题报告

796.[APIO2012]派遣在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为Master。 ... [详细]

蜡笔小新 2023-10-15 20:32:49
main
P2765 魔术球问题（网络流，隐式图构造）

P2765魔术球问题这道题的思路实在是太罕见了，所以发一篇blog从某一新放入的球开始看起1.放入原来的柱子上2.放入新的柱子并将每个点进行拆点࿰ ... [详细]

蜡笔小新 2023-10-15 12:54:08

evon0207165

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章