h****e
发帖数: 928 | 1 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
多见。主要是考写code的能力，而且一般不限制用什么编程语言，
让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
不是简单的0/1关系。
题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
"1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
用的是一般公认的比较原则，上边的例子中
5.01 > 4.99.6 > 3.0 > 1.2.3。 |
p*****2
发帖数: 21240 | 2
先split，然后一个一个比较？
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
h****e
发帖数: 928 | 3 差不多百分百的都是说要这么做的，但是差别就在于能不能写出来，
被指出bug以后能不能改过来。
【在 p*****2 的大作中提到】
:
: 先split，然后一个一个比较？
|
b***m
发帖数: 5987 | 4 嗯，其实这种题更实用，比一些花哨的算法题强多了。其它类似合并两个已排序的数组
（或者链表）、在行和列都已排序的二维数组中查找一个数的位置等等，都是很不错的
题。 |
l****c
发帖数: 782 | 5 我想用个recursion，string碰到最后或是碰到".",取之前的部分转成int比较，有大小
了就返回，没有大小了就recursion到下一部分。 |
b***m
发帖数: 5987 | 6 不过碰到这种题我真想用Perl来实现，简直简单透了。:-) |
R********y
发帖数: 88 | 7 C#里可以直接把string转换成Version类型，然后直接比吧... C++不知道有没有
想到个无关的，以前总有题目问string是不是valid的整数，或者这个string是不是
valid的版本号等等，能不能直接
try
{ new Version("1.2.3");}
catch
(return false;}
return true;
???
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
p*****2
发帖数: 21240 | 8 好久没写了。刚才写了一个练练。大牛给指点一下。
class Version implements Comparable
{
private String version;
private String[] getNumbers(String ver)
{
return ver.split("\\.");
}
public Version(String _version)
{
version=_version;
}
public String getVersion()
{
return version;
}
public int compareTo(Version v)
{
String[] arr1=getNumbers(version);
String[] arr2=getNumbers(v.getVersion());
int i=0;
while(i
{
int num1=Integer.parseInt(arr1[i]);
int num2=Integer.parseInt(arr2[i]);
if(num1!=num2)
return num1-num2;
i++;
}
if(arr1.length==arr2.length)
return 0;
else
return arr1.length-arr2.length;
}
} |
h****e
发帖数: 928 | 9 可以用Perl之类的scripting language解这道题，但是只要是想把
每一个部分当作整数处理的话就会有一些微妙的bug。这里不用考虑
无效的输入的问题，也不用考虑int overflow的问题。我一般是看到
code写完以后，给出一个例子指出bug的存在。
C#的Version class好象只支持最多含4个部分的版本，题目要求的
是任意长度的，例如"1.2.3.4.5"，所以就不能直接用了。
http://msdn.microsoft.com/en-us/library/system.version.aspx |
h****e
发帖数: 928 | 10 二爷做得好快。不过至少有两个问题。例如下面的两组版本比较
你的程序给出的结果不对：
1.60 > 1.7
1.2.3 > 1.2
【在 p*****2 的大作中提到】
: 好久没写了。刚才写了一个练练。大牛给指点一下。
: class Version implements Comparable
: {
: private String version;
:
: private String[] getNumbers(String ver)
: {
: return ver.split("\\.");
: }
:
|
|
|
l***i
发帖数: 1309 | 11 做成vector再比较？
s1="1.2.3"
s2="19.28.10.18"
// return: version comparison
// -1 if s1 < s2,
// 0 if s1 == s2
// 1 if s1 > s2
int version_cmp(string s1, string s2)
{
vector v1, v2;
for(int i=0; i
int p = i;
for(; i
;
string sub = s1.substr(p, i-p);
v1.push_back(atoi(sub.c_str()));
}
for(int i=0; i
int p = i;
for(; i
;
string sub = s2.substr(p, i-p);
v1.push_back(atoi(sub.c_str()));
}
for(int i=0; i
if (v1[i] != v2[i]) return v1[i] - v2[i];
}
return v1.size() - v2.size();
} |
p*****2
发帖数: 21240 | 12
update 了一下。第一个问题要转成int，第二个问题我想错了，我想的是String的比较
了。越短越大，实际上是越短应该越小。再帮我看看，多谢。
【在 h****e 的大作中提到】
: 二爷做得好快。不过至少有两个问题。例如下面的两组版本比较
: 你的程序给出的结果不对：
: 1.60 > 1.7
: 1.2.3 > 1.2
|
b***m
发帖数: 5987 | 13 这题的确有点意思。不过1.60和1.7到底应该哪个大呀？
【在 h****e 的大作中提到】
: 二爷做得好快。不过至少有两个问题。例如下面的两组版本比较
: 你的程序给出的结果不对：
: 1.60 > 1.7
: 1.2.3 > 1.2
|
p*****2
发帖数: 21240 | 14
LZ是对的。应该1.60大。因为60>7。
【在 b***m 的大作中提到】
: 这题的确有点意思。不过1.60和1.7到底应该哪个大呀？
|
d**********x
发帖数: 4083 | 15 1.60大啊。
有个著名的笑话。某开源软件就是不出1.0版本，总是在0.9.x晃悠
后来终于出到了0.9.9，大家想这回你没办法了吧
作者嘿嘿一笑，放出0.9.10版本
【在 b***m 的大作中提到】
: 这题的确有点意思。不过1.60和1.7到底应该哪个大呀？
|
b***m
发帖数: 5987 | 16 嗯，我没注意你的代码，只是确认一下。
【在 p*****2 的大作中提到】
:
: LZ是对的。应该1.60大。因为60>7。
|
b***m
发帖数: 5987 | 17 我擦，这下所有人都疯了。
【在 d**********x 的大作中提到】
: 1.60大啊。
: 有个著名的笑话。某开源软件就是不出1.0版本，总是在0.9.x晃悠
: 后来终于出到了0.9.9，大家想这回你没办法了吧
: 作者嘿嘿一笑，放出0.9.10版本
|
w****x
发帖数: 2483 | 18
const char* getNum(const char* q, int& res)
{
const char* p = q;
if (NULL == p) return NULL;
res = 0;
while (*p != '.' && *p != 0)
res = 10*res + *p++ - '0';
if (*p == '.') p++;
return p;
}
bool lessThan(const char* str1, const char* str2)
{
if (NULL == str1 || NULL == str2)
return false;
const char* p1 = str1;
const char* p2 = str2;
while (*p1 != 0 && *p2 != 0)
{
int x,y;
p1 = getNum(p1, x);
p2 = getNum(p2, y);
if (x < y) return true;
if (x > y) return false;
}
return *p1 == 0 && *p2 != 0;
}
【在 h****e 的大作中提到】
: 二爷做得好快。不过至少有两个问题。例如下面的两组版本比较
: 你的程序给出的结果不对：
: 1.60 > 1.7
: 1.2.3 > 1.2
|
l****c
发帖数: 782 | 19 写的蠢了点，但是也算是个思路吧，面试官
int compareVersion(string s1, int index1, string s2, int index2) {
//if s1 is larger, return 1, if s2 is larger return 2, else return 0
if (index1 < s1.size() && index2 < s2.size()) {
int tmpIndex1 = index1;
int prev1 = 0;
while (tmpIndex1 < s1.size()&&s1[tmpIndex1]!='.') {
int cur = (int)(s1[tmpIndex1] - '0');
prev1 = prev1*10 + cur;
tmpIndex1++;
}
int prev2 = 0;
int tmpIndex2 = index2;
while (tmpIndex2 < s2.size()&&s2[tmpIndex2]!='.') {
int cur = (int)(s2[tmpIndex2] - '0');
prev2 = prev2*10 + cur;
tmpIndex2++;
}
if (prev1 > prev2) return 1;
else if (prev1 < prev2) return 2;
else return compareVersion(s1, tmpIndex1+1, s2, tmpIndex2+1);
}
else if (index1 < s1.size()) {
int tmpIndex1 = index1;
int prev1 = 0;
while (tmpIndex1 < s1.size()&&s1[tmpIndex1]!='.') {
int cur = (int)(s1[tmpIndex1] - '0');
prev1 = prev1*10 + cur;
tmpIndex1++;
}
if (prev1>0) return 1;
else return 0;
}
else if (index2 < s2.size()) {
int tmpIndex2 = index2;
int prev2 = 0;
while (tmpIndex2 < s2.size()&&s2[tmpIndex2]!='.') {
int cur = (int)(s2[tmpIndex2] - '0');
prev2 = prev2*10 + cur;
tmpIndex2++;
}
if (prev2>0) return 2;
else return 0;
}
else return 0;
} |
h****e
发帖数: 928 | 20 二爷和lanti同学（除去typo外）的代码就剩下一个比较tricky的bug了：
1.2 > 1.05
但是两位给出的是1.2 < 1.05。假设你们同意这是一个bug，下面就是
怎么fix的问题了。 |
|
|
p*****2
发帖数: 21240 | 21
我开始晕了。这个规律还没想太明白。
【在 h****e 的大作中提到】
: 二爷和lanti同学（除去typo外）的代码就剩下一个比较tricky的bug了：
: 1.2 > 1.05
: 但是两位给出的是1.2 < 1.05。假设你们同意这是一个bug，下面就是
: 怎么fix的问题了。
|
y*******g
发帖数: 6599 | 22 直接比数字大小吧？
leading 0不影响
【在 p*****2 的大作中提到】
:
: 我开始晕了。这个规律还没想太明白。
|
p*****2
发帖数: 21240 | 23
他是说1.2>1.05
直接比大小的话5>2
【在 y*******g 的大作中提到】
: 直接比数字大小吧？
: leading 0不影响
|
l****c
发帖数: 782 | 24 yangcheng是说直接比较'.'后面的数字大小
【在 p*****2 的大作中提到】
:
: 他是说1.2>1.05
: 直接比大小的话5>2
|
l****c
发帖数: 782 | 25 还是觉得recursion简单。就是我之前的代码需要安装lz最后的解释再改一下。 |
p*****2
发帖数: 21240 | 26
1.60 > 1.7
【在 l****c 的大作中提到】
: yangcheng是说直接比较'.'后面的数字大小
|
l****c
发帖数: 782 | 27 lz的意思是1.7更大？
【在 p*****2 的大作中提到】
:
: 1.60 > 1.7
|
p*****2
发帖数: 21240 | 28 我觉得得clarify规则。
我不太理解为什么2>05， 60>7
好像一个按照string来处理，一个按照int来处理的 |
y*******g
发帖数: 6599 | 29 那只能leading 0特殊处理了。
有leading 0的时候补齐成一样长， 2和05变成20 和 05 然后比数字。
02 和 035同理
【在 p*****2 的大作中提到】
: 我觉得得clarify规则。
: 我不太理解为什么2>05， 60>7
: 好像一个按照string来处理，一个按照int来处理的
|
w****x
发帖数: 2483 | 30
按字符串比就行了吧
【在 y*******g 的大作中提到】
: 那只能leading 0特殊处理了。
: 有leading 0的时候补齐成一样长， 2和05变成20 和 05 然后比数字。
: 02 和 035同理
|
|
|
R********y
发帖数: 88 | 31 假设已经split好了，比较中间a和b的大小
int countZero(string s)
{
int count = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] != '0') return count;
count ++;
}
}
bool isBigger(string a, string b)
{
if (countZero(a) < countZero(b)) return true;
if (countZero(a) > countZero(b)) return false;
return Int(a) > Int(b);
} |
R********y
发帖数: 88 | 32 或者还是可以用C#偷懒。我印象里Versoin类型，超过四位的后面自动忽略。所以用个
loop比较，相等的情况下，看字串里是否含点。不含，相等。含，取第一个点以后的字
串，转换成Version类型继续比。 |
R********y
发帖数: 88 | 33 .00和.000，我的code会显示前者比后者大。这个按照规则应该怎么说？
【在 R********y 的大作中提到】
: 假设已经split好了，比较中间a和b的大小
: int countZero(string s)
: {
: int count = 0;
: for (int i = 0; i < s.length(); i++)
: {
: if (s[i] != '0') return count;
: count ++;
: }
: }
|
b*******y
发帖数: 2048 | 34 这是要找出最大的一个数还是要排序阿？
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
h****e
发帖数: 928 | 35 我认为
1.60 > 1.7
1.2 > 1.05
单纯只考虑第一个小数点以后的数字就不能给出正确的解法。
另外还要支持多个小数点的情况，例如1.2.0和1.05，这时候.2.0
并不是一个有效的数字，不能和.05直接比较。
因此本题的关键是看出每个部分之间不是纯粹的string或者int比较，
需要使用类似Runkuraqay给出的数零或者补零的解法。
在实际面试时，我都会给出一定的提示和解释。最后和面试者的感叹
就是写这样一个小小的版本比较的程序都会有隐藏挺深的bug。
还有我不会纠结1.2和1.2.0到底谁大谁小的问题，不要搞得大家
都很累。:) |
b*******y
发帖数: 2048 | 36 这个规则好复杂啊
1.60，1.05和1.2中至少有一个是不合格的输入吧。。。
不然1.1000算啥？
1.1000
1.999
1.1
1.0001
要咋排序？ |
l*****a
发帖数: 14598 | 37 就两个排什么序？
【在 b*******y 的大作中提到】
: 这个规则好复杂啊
: 1.60，1.05和1.2中至少有一个是不合格的输入吧。。。
: 不然1.1000算啥？
: 1.1000
: 1.999
: 1.1
: 1.0001
: 要咋排序？
|
h****e
发帖数: 928 | 38 用小一些的数字大小关系就会更明显一些：
1.10 > 1.9 > 1.1 > 1.05 > 1.0.1 > 1.0
【在 b*******y 的大作中提到】
: 这个规则好复杂啊
: 1.60，1.05和1.2中至少有一个是不合格的输入吧。。。
: 不然1.1000算啥？
: 1.1000
: 1.999
: 1.1
: 1.0001
: 要咋排序？
|
b*******y
发帖数: 2048 | 39 回帖不爬楼啊。。。明明是3个
【在 l*****a 的大作中提到】
: 就两个排什么序？
|
h*****n
发帖数: 188 | 40 for the first section, compare integers
for the rest, compare floating numbers.
0.01
0.99
0
0.2
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
|
|
C***U
发帖数: 2406 | 41 s.split(`.`)
haha
【在 h****e 的大作中提到】
: 差不多百分百的都是说要这么做的，但是差别就在于能不能写出来，
: 被指出bug以后能不能改过来。
|
g*********e
发帖数: 14401 | 42 int getNum(char **s){
if(**s == '\0')
return 0;
int val=0;
while(**s != '.' && **s != '\0'){
val = val*10 + (**s)-'0';
(*s)++;
}
return val;
};
int compareVersion( char * s1, char * s2){
if(*s1 == '\0' && *s2 == '\0')
return 0;
if(*s1 == '.')
s1++;
if(*s2 == '.')
s2++;
int a = getNum(&s1);
int b = getNum(&s2);
printf("comparing %d and %d\n", a, b);
if(a > b)
return 1;
else if(a < b)
return -1;
else{
return compareVersion(s1, s2);
}
}; |
g*********e
发帖数: 14401 | 43 fix after the leading zero issue
int getNum(char **s, int &leadZeros){
if(**s == '\0')
return 0;
int val=0;
bool lead=true;
leadZeros=0;
while(**s != '.' && **s != '\0'){
if(lead && **s == '0')
leadZeros++;
else
lead = false;
val = val*10 + (**s)-'0';
(*s)++;
}
return val;
};
int compareVersion( char * s1, char * s2){
if(*s1 == '\0' && *s2 == '\0')
return 0;
if(*s1 == '.')
s1++;
if(*s2 == '.')
s2++;
int leada, leadb;
int a = getNum(&s1, leada);
int b = getNum(&s2, leadb);
a = a*leadb;
b = b*leada;
if(a > b)
return 1;
else if(a < b)
return -1;
else{
return compareVersion(s1, s2);
}
}; |
l*********8
发帖数: 4642 | 44 1.2 怎么会比 1.05大？
1.2 > 1.0.5 倒是真的。
你的意思是 1.05 相当于1.0.5 ？
【在 h****e 的大作中提到】
: 我认为
: 1.60 > 1.7
: 1.2 > 1.05
: 单纯只考虑第一个小数点以后的数字就不能给出正确的解法。
: 另外还要支持多个小数点的情况，例如1.2.0和1.05，这时候.2.0
: 并不是一个有效的数字，不能和.05直接比较。
: 因此本题的关键是看出每个部分之间不是纯粹的string或者int比较，
: 需要使用类似Runkuraqay给出的数零或者补零的解法。
: 在实际面试时，我都会给出一定的提示和解释。最后和面试者的感叹
: 就是写这样一个小小的版本比较的程序都会有隐藏挺深的bug。
|
g*********e
发帖数: 14401 | 45
1.2当然比1.05大啊
1.05 > 1.0.5
【在 l*********8 的大作中提到】
: 1.2 怎么会比 1.05大？
: 1.2 > 1.0.5 倒是真的。
: 你的意思是 1.05 相当于1.0.5 ？
|
S*********g
发帖数: 5298 | 46 你所说的bug，其实就是看面试者是不是能考虑全你所谓的一般公认原则
你要是真把这些原则全都明明白白写下来，看还有几个人会错
这个题也就是在考回字有几个写法
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
b*******y
发帖数: 2048 | 47 public int Compare(String s1, String s2)
{
String[] a1 = s1.Split('.');
String[] a2 = s2.Split('.');
int i=0;
while(i
{
ss1=a1[i];
ss2 = a2[i];
int num1 =integer.parseInt(ss1);
int num2 = integer.parseInt(ss2);
if(num1==0 || num2 ==0)
return num1-num2;
while(ss1.charAt(0)=='0')
{
ss1 = ss1.subString(1);
num2 *=10;
}
while(ss2.charAt(0)=='0')
{
ss2 = ss2.subString(1);
num1 *=10;
}
if(num1!=num2)
return num1-num2;
i++
}
if(a1.Length == a2.Length)
return 0;
else
return a1.Length-a2.Length;
}
【在 h****e 的大作中提到】
: 用小一些的数字大小关系就会更明显一些：
: 1.10 > 1.9 > 1.1 > 1.05 > 1.0.1 > 1.0
|
l*********8
发帖数: 4642 | 48 我跟peking2一样不能理解
1.60 > 1.7
1.2 > 1.05
我这样理解：
1.05 < 1.2是因为
1.05 < 1.06 < 1.07 < ....... < 1.18 < 1.19 < 1.20 ,而1.20把末尾的0省去就变成
1.2
但如果末尾的0可以省去， 1.60 就等同于 1.6， 就应该比1.7小。
【在 h****e 的大作中提到】
: 我认为
: 1.60 > 1.7
: 1.2 > 1.05
: 单纯只考虑第一个小数点以后的数字就不能给出正确的解法。
: 另外还要支持多个小数点的情况，例如1.2.0和1.05，这时候.2.0
: 并不是一个有效的数字，不能和.05直接比较。
: 因此本题的关键是看出每个部分之间不是纯粹的string或者int比较，
: 需要使用类似Runkuraqay给出的数零或者补零的解法。
: 在实际面试时，我都会给出一定的提示和解释。最后和面试者的感叹
: 就是写这样一个小小的版本比较的程序都会有隐藏挺深的bug。
|
b*******y
发帖数: 2048 | 49 我理解题目了
看这个例子
这样解读
1.十〉 1.九 〉 1.一 〉1.零点五 > 1.零.一 >1.零
10是指10
05是指0.5
然后从左边比到右边 |
b*******y
发帖数: 2048 | 50 反正俺是看了半小时才明白规则
面试遇到可以直接跪了 |
|
|
w****x
发帖数: 2483 | 51 我觉得这题如果用其它语言来做必须拒绝用任何类似split的函数， c++作太吃亏了 |
t********e
发帖数: 1169 | |
l*********8
发帖数: 4642 | 53 谢谢！ 这个解释倒说得通
【在 b*******y 的大作中提到】
: 我理解题目了
: 看这个例子
: 这样解读
: 1.十〉 1.九 〉 1.一 〉1.零点五 > 1.零.一 >1.零
: 10是指10
: 05是指0.5
: 然后从左边比到右边
|
h*****f
发帖数: 248 | 54 not so efficient...
#include
#include
#include
#include
#include
#include
int compare(const std::string& v1, const std::string& v2) {
std::vector version1;
std::vector version2;
std::istringstream is1(v1);
std::istringstream is2(v2);
std::string token1;
std::string token2;
double d1, d2;
bool exist1 = true, exist2 = true;
while (true) {
if (exist1) exist1 = std::getline(is1, token1, '.');
if (exist2) exist2 = std::getline(is2, token2, '.');
if (!exist1 && !exist2) break;
if (exist1) {
std::istringstream(token1) >> d1;
version1.push_back(d1);
}
if (exist2) {
std::istringstream(token2) >> d2;
version2.push_back(d2);
}
if (exist1 && exist2) {
if (token1.size() != token2.size()) {
std::stringstream ss1;
std::stringstream ss2;
ss1 << d1;
ss2 << d2;
if (token1.length() > ss1.str().length() || token2.length()
> ss2.str().length()) {
token1.insert(0, "0.");
std::istringstream(token1) >> d1;
version1.back() = d1;
token2.insert(0, "0.");
std::istringstream(token2) >> d2;
version2.back() = d2;
}
}
}
}
size_t x = 0, xe = version1.size();
size_t y = 0, ye = version2.size();
while (x < xe && y < ye) {
if (version1[x] > version2[y]) {
return 1;
}
else if (version2[x] > version1[y]) {
return -1;
}
x++;
y++;
}
if (xe == ye) return 0;
if (xe > ye) return 1;
return -1;
}
int main() {
/*
std::string v1;
std::string v2;
std::getline(std::cin, v1);
std::getline(std::cin, v2);
std::cout << compare(v1, v2) << std::endl;
*/
assert(1 == compare("1.2", "1.05"));
assert(0 == compare("1.2.3", "1.2.3"));
assert(1 == compare("1.2", "1"));
assert(-1 == compare("1", "1.2"));
assert(1 == compare("1.10", "1.9"));
assert(1 == compare("1.9", "1.1"));
assert(1 == compare("1.1", "1.05"));
assert(1 == compare("1.05", "1.01"));
assert(1 == compare("1.01", "1.0"));
return 0;
} |
i**********e
发帖数: 1145 | 55 那么 1.05 和 1.050
05 是指 0.5，那 050 是指 0.50?
按照他的意思，似乎 0.50 比 0.5 还大啊？
我觉得有 0 在前面的状况，直接去除前面的 0 再比较就可以了。一般来说很少很少人
会想到这个状况，就看改这个要改多长时间了。
【在 b*******y 的大作中提到】
: 我理解题目了
: 看这个例子
: 这样解读
: 1.十〉 1.九 〉 1.一 〉1.零点五 > 1.零.一 >1.零
: 10是指10
: 05是指0.5
: 然后从左边比到右边
|
i**********e
发帖数: 1145 | 56 是，你可以想一想用C 做程序是怎么样的。
不过可以先跟面试官讨论假设有这个split 函数，这题目考点不在实现split。
【在 w****x 的大作中提到】
: 我觉得这题如果用其它语言来做必须拒绝用任何类似split的函数， c++作太吃亏了
|
d**********x
发帖数: 4083 | 57 every sane institution has its own naming convention...
【在 i**********e 的大作中提到】
: 那么 1.05 和 1.050
: 05 是指 0.5，那 050 是指 0.50?
: 按照他的意思，似乎 0.50 比 0.5 还大啊？
: 我觉得有 0 在前面的状况，直接去除前面的 0 再比较就可以了。一般来说很少很少人
: 会想到这个状况，就看改这个要改多长时间了。
|
s********k
发帖数: 6180 | 58 上一个我写的，没有检查字符串是否都在0-9和'.'，不知道这个是否需要补上(如果某
个版本不符合要求(10.1.a)，返回什么？)。基本思路是第一个.之前按照数字大小比较
，然后其余的一个个位置比较,只要某一个位置其中一个大，剩下的就不需要比较了(比
如2.07和2.1，小数点之后后面的1》前面的0，直接2.1版本大),然后如果某个字符串先
到.,别的还有数字，那么后者大(1.05>1.0.5),如果最后一个已经晚了，另外一个还有
数字，后面大（3.2.1<3.2.10或者3.2.1<3.2.1.5）
大牛指点一下
const char *compVersion(const char *version1, const char * version2){
const char *v1 = version1;
const char *v2 = version2;
//compare the digit before first '.'
if(getNum(v1)>getNum(v2)) return v1;
else if(getNum(v1)>getNum(v2)) return v2;
while((*v1!='\0')&&(*v2!='\0'){
if((*v1-'0')>(*v2-'0')) return v1;
else if((*v1-'0')<(*v2-'0')) return v1;
if((*v1=='.') && (*v1=='.')){
v1++;
v2++;
}else if(*v1=='.'){
return v2;
}else if(*v2=='.'){
return v1;
}
}
if(v1) return v1;
if(v2) return v2;
}
int getNum(const char* str){
int num = 0;
while(*str!=='.'){
num = num*10+(*str-'0');
str++;
}
return num;
}
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
s********k
发帖数: 6180 | 59 想到一个问题，3.0.1和3.00.1哪个版本大？按照我的算法后者大
【在 s********k 的大作中提到】
: 上一个我写的，没有检查字符串是否都在0-9和'.'，不知道这个是否需要补上(如果某
: 个版本不符合要求(10.1.a)，返回什么？)。基本思路是第一个.之前按照数字大小比较
: ，然后其余的一个个位置比较,只要某一个位置其中一个大，剩下的就不需要比较了(比
: 如2.07和2.1，小数点之后后面的1》前面的0，直接2.1版本大),然后如果某个字符串先
: 到.,别的还有数字，那么后者大(1.05>1.0.5),如果最后一个已经晚了，另外一个还有
: 数字，后面大（3.2.1<3.2.10或者3.2.1<3.2.1.5）
: 大牛指点一下
: const char *compVersion(const char *version1, const char * version2){
: const char *v1 = version1;
: const char *v2 = version2;
|
d*******d
发帖数: 2050 | 60 这个题有好的一面也有不足的地方。
好的是题目内容简单，能考查面试者能否全面考虑所有edge case,以及能否通过有效交
流澄清spec,还有就是coding能力。
但是，这个问题不适合所有position.它过于依赖特定语言的特定用法，而且对于很多
人来说不是常用的。很多人一年也不会用到一次split.而且对于分别用C，c ,java,
perl的程序员来说，effort差别太大，不公平。
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
|
|
R********y
发帖数: 88 | 61 C++用boost的一样有split函数...
【在 w****x 的大作中提到】
: 我觉得这题如果用其它语言来做必须拒绝用任何类似split的函数， c++作太吃亏了
|
d********f
发帖数: 43471 | 62 这如果是bug也只能说是出题人的bug
【在 h****e 的大作中提到】
: 二爷和lanti同学（除去typo外）的代码就剩下一个比较tricky的bug了：
: 1.2 > 1.05
: 但是两位给出的是1.2 < 1.05。假设你们同意这是一个bug，下面就是
: 怎么fix的问题了。
|
s*******d
发帖数: 229 | 63 python直接字符串list做sort，一行代码 |
l*********u
发帖数: 19053 | 64 拿到第一个token＂.＂前的数字， 比较得出结果
if 前一步数字相等
loop thru the longest one(having the most token ".")
拿到下一个token＂＂前的数字，没token数字=-１
比较得出结果
end loop
end if
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
n*******e
发帖数: 612 | 65 c++ 用strtok在atoi吧
或者sscanf循环
【在 R********y 的大作中提到】
: C#里可以直接把string转换成Version类型，然后直接比吧... C++不知道有没有
: 想到个无关的，以前总有题目问string是不是valid的整数，或者这个string是不是
: valid的版本号等等，能不能直接
: try
: { new Version("1.2.3");}
: catch
: (return false;}
: return true;
: ???
|
w****x
发帖数: 2483 | 66
问题是面试官一般不熟悉boost, 这题觉得肯定要禁止用任何split函数
【在 R********y 的大作中提到】
: C++用boost的一样有split函数...
|
g*********e
发帖数: 14401 | 67
一样大
【在 s********k 的大作中提到】
: 想到一个问题，3.0.1和3.00.1哪个版本大？按照我的算法后者大
|
g*********9
发帖数: 1285 | 68 我说个最简单的解法。
把两个句号之间补0，让两个句号之间都是两位或者三位数字，包括最后一个句号之后，
把两个版本号里的句号全部去掉，把长度短的后面补0，让他们长度一样，然后转换成
long比较大小。 |
a****l
发帖数: 8211 | 69 其实从我的角度看,"不到一分钟就可以解释清楚"就是最大的bug，从专业的角度说就是
程序的requirement没有定义清楚。一个看似很简单的东西，如果不能用语言把所有的
可能性都清楚的规定出来，就会产生歧义，然后一部分人按照一种意思理解，另一部分
人按照另一种意思理解，然后做出来的东西最好的结果是当场不工作，最坏的结果是测
试时什么都好但是一到现场就翘辫子。
我觉得其实所谓的编程技巧差别不太大，就算再高技术的程序员也是难免出点纰漏的，
比如说你想的有几个边际条件要满足，结果老板跑来和你开个小会，然后再回去的时候
就忘了直接checkin了。反而是这种结构、接口、要求上的问题，最容易产生扯皮，反
反复复谁也说不服谁，最浪费时间。
从另一点上说，我觉得拿到一个题目马上就开始coding是fresh graduate的常见的毛病
。为什么说呢？我觉得是思维定式的问题。学校里的学生多年来都是习惯于老师出个题
目学生写答案，题目总是不会错的因为是老师多年检验下来的，老师也是不会来解释的
因为有什么陷阱就是要考的地方，所以看到个requirement就马上开始写代码。但是实
际工作后就会发现，那些requirements的来源的地方其实也都是些搞笑的人，很多都是
临时编凑出来的，所以不能相信这些东西的准确性，什么东西不规定清楚，最好还是别
动手干，免的吃力又不讨好。
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
m****v
发帖数: 84 | 70 基本思路还是基于vector比较，但是把有前缀零的段当作负数处理。请指教，谢
谢。
vector Sort(const vector &v) {
vector, string> > a;
for (int i = 0; i < v.size(); i++) {
vector d;
int k = 0, s = 0, z = 1, c = 1;
while (k < v[i].size()) {
if (isdigit (v[i][k])) {
s = s * 10 + (v[i][k] - '0');
c = c && v[i][k] == '0' ? 1 : 0;
z *= c ? 10 : 1;
}
else if (k == 0 || isdigit(v[i][k - 1])) {
d.push_back(z > 1 ? s * -z : s);
s = 0, z = 1, c = 1;
}
k++;
}
d.push_back(z > 1 ? s * -z : s);
a.push_back(make_pair(d, v[i]));
}
sort(a.begin(), a.end());
vector w;
for (int i = a.size() - 1; i >= 0; i--)
w.push_back(a[i].second);
return w;
} |
|
|
t****a
发帖数: 1212 | 71 我也喜欢这个题目，做为lisp初学者，上一个lisp的解
http://kangtu.me/~kangtu/study/interview.html#sec-14
核心代码只有6行
(defn value [v]
(let [nl (map #(Integer/parseInt %) (clojure.string/split v #"\."))
rst (exp 100 (- 4 (count nl)))
s (* (reduce (fn [x y] (+ (* 100 x) y)) nl) rst)]
s))
(defn hellohackie [versions]
(sort-by value versions))
(hellohackie versions) ; ("1.2.3" "3.0" "4.99.6" "5.01")
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
s*****n
发帖数: 994 | 72 在回帖框里大致写了一下
int getNumber (char * const version){
if (!version)
return -1;
in n = 0;
if (*version != '.'){
n = n*10;
n += *version - '0';
}
return n;
}
bool CompareVersion (char * const v1, char * const v2){//return if v1 later
or same as v2
while (v1 != '\0' && v2 != '\0'){
int n1 = getNumber(v1);
int n2 = getNumber(v2);
if (n1 > n2)
return true;
else if (n1 < n2)
return false;
while ('0'<*v1 && *v1 < '9'){
v1++;
}
if (v1 == '\0')
break;
else
v1++;//was at '.'
if (v2 == '\0')
break;
else
v2++;//was at '.'
while ('0'<*v2 && *v2 < '9'){
v2++;
}
}
if (v1 == '\0')
return false;
return true;
}
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
l***i
发帖数: 1309 | 73 一个新想法，假设每个token的长度都不大，double类型的精度足够，不停的比两个
double，这样可以避免很多问题。
vector vs1, vs2;
// assume s has only 0-9 and .
// and begin with digit
vector split(string s)
{
vector ans;
int i;
for(i=0; i
int p=i;
for(; i
;
ans.push_back(s.substr(p, i-p));
return ans;
}
}
vs1 = split(s1);
vs2 = split(s2);
for(int i=0; i
string s1, s2;
s1 = "0." + vs1[i];
s2 = "0." + vs2[i];
double d1, d2;
d1 = atof(s1); // this avoids 1.2 vs 1.05 issue since 0.2 > 0.05
d2 = atof(s2);
if (d1 != d2) return (d1-d2>0 ? +1 : -1);
}
return vs1.size() - vs2.size(); |
l******t
发帖数: 225 | 74
这个“当然”没看出来怎么个当然法。同一个软件如果这样标版本，那么软件作者估计
也是个文盲。
另外有的软件版本里面还有字母，也要考虑进去一起比较
【在 g*********e 的大作中提到】
:
: 一样大
|
p*********w
发帖数: 23432 | 75 我的也很简单，判断一个三角形是什么类型的三角形（比如是等边、等腰、或者其他什
么的）
【在 h****e 的大作中提到】
: 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
: 题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
: 多见。主要是考写code的能力，而且一般不限制用什么编程语言，
: 让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
: 不是简单的0/1关系。
: 题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
: "1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
: 用的是一般公认的比较原则，上边的例子中
: 5.01 > 4.99.6 > 3.0 > 1.2.3。
|
n*******0
发帖数: 2002 | 76 俺也在思考这个问题。。。。。
【在 b***m 的大作中提到】
: 这题的确有点意思。不过1.60和1.7到底应该哪个大呀？
|
j**h
发帖数: 1230 | 77 parameter normalization有时候非常简单实用啊
后，
【在 g*********9 的大作中提到】
: 我说个最简单的解法。
: 把两个句号之间补0，让两个句号之间都是两位或者三位数字，包括最后一个句号之后，
: 把两个版本号里的句号全部去掉，把长度短的后面补0，让他们长度一样，然后转换成
: long比较大小。
|
g*****e
发帖数: 282 | 78 说个实际情况，正好平时跟build team有打交道。我们公司的做法，各个sub version
section长度是确定的，不足部分补0，比如15.120809.0140.01。该题目里的情况实际
项目里不应该也不会出现的
【在 l*********8 的大作中提到】
: 我跟peking2一样不能理解
: 1.60 > 1.7
: 1.2 > 1.05
: 我这样理解：
: 1.05 < 1.2是因为
: 1.05 < 1.06 < 1.07 < ....... < 1.18 < 1.19 < 1.20 ,而1.20把末尾的0省去就变成
: 1.2
: 但如果末尾的0可以省去， 1.60 就等同于 1.6， 就应该比1.7小。
|
n****r
发帖数: 120 | 79 俺也奔一个：
static int compare(String a, String b, char c){
if (a == null) return b == null ? 0 : -1;
if (b == null) return 1;
int i = 0, j = 0;
while (i < a.length() && j < b.length()){
while (i < a.length() && a.charAt(i) == c)
i++;
while (j < b.length() && b.charAt(j) == c)
j++;
if (i>=a.length() || j >= b.length())
break;
if (a.charAt(i) == b.charAt(j)){
i++;
j++;
}else
return a.charAt(i) - b.charAt(j);
}
int cnt = 0;
while (i < a.length()){
if (a.charAt(i) != c){
cnt += a.charAt(i) - '0';
if (cnt > 0)
break;
}
i++;
}
while (j < b.length()){
if (b.charAt(j) != c){
cnt += b.charAt(j) - '0';
if (cnt > 0)
break;
}
j++;
}
return cnt;
} |
x******r
发帖数: 249 | 80 这个题目最关键的应该是在写代码前问清楚version number的convention,是否可以有
leading 0.如果可以有leading 0，那么意味着版本号的长度应该是fixed，一般两位或
者3位，那么1.4>1.09，直接比较字符串即可。"4">"09", 1.4==1.40>1.09.这同时也意
味着1.9 > 1.20，因为1.9 == 1.90 > 1.20.
如果版本号不可以有leading 0,那么要转化成整数再比较。此时1.9 < 1.20, 1.4 < 1.
09. 因为 1.4 < 1.9 == 1.09.
这两种convention我都见过。 |
