由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 算法题:Find the latest version
相关主题
2sigma(interview st)的input format怎么读?题都感觉做对了,面试的人也满意,为什么二面过后还是直接悲剧呢……顺便上P面经
two sigma 的online code test 的问题请教两道CS题
LC的compare version有点麻烦再问一道数组题
湾区SNS公司面经背包问题
考古到一道题求问Jane Street一道面试题
请问如何binary search出数组中的重复元素一个查找算法题
两道2009算法题G家电面题目
包子求教:用二维数组排序问题一个题
相关话题的讨论汇总
话题: find话题: latest话题: 数组话题: version
进入JobHunting版参与讨论
1 (共1页)
s********u
发帖数: 1109
1
http://www.careercup.com/question?id=5673258271637504
Find the latest version of released software. For e.g1. 2 and 2.2.. latest
is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
as string in above format.
一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
int/double/
下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
每一位都要做一次快排,也就是O(knlogn)
另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一
位只要O(n),总共O(kn)。但坏处是,比如其中一位是很大的数,那么开的空间就要很
大,其实time cost也不再是O(n),而是O(max)。
我想了一下,既然只是要求最大版本。那就从第一位开始,每一位遍历。找到最大值之
后,将所有该位不存在,或者该位小于最大值的那个vector删除,或者用bool数组标记
下false。从左到右走一遍,最后只剩下一个vector。
不知道是不是最优解法。
还有一个问题就是怎么把比如3.12.4.7转换为vector {3,12,4,7}
我想的办法是将所有'.'改成‘ ’,然后用while(stringstream >> num)
估计有更好的办法?基础不扎实,所以一会用用sscanf,一会用用stringstream,都用
不好。
q*c
发帖数: 9453
2
这太容易了吧,就是找最大值啊,用通常的字符串比较函数就行。n 算法

【在 s********u 的大作中提到】
: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
: 次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
: 每一位都要做一次快排,也就是O(knlogn)
: 另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一

s********g
发帖数: 60
3
字符串不行。比如9.0和10.0

【在 q*c 的大作中提到】
: 这太容易了吧,就是找最大值啊,用通常的字符串比较函数就行。n 算法
U**K
发帖数: 58
4
拆成数组比如[2,1,3], 数组求和,和最大的最新
L**********1
发帖数: 797
5
1.将所有的版本号转为x.xxx的格式,即保留第一个小数点,其它全部取消
2.用Double.valueOf转换
3.比大小
用的是JAVA.
O(n)
s*i
发帖数: 5025
6
2.12 将会小于2.2

[发表自未名空间手机版 - m.mitbbs.com]

【在 L**********1 的大作中提到】
: 1.将所有的版本号转为x.xxx的格式,即保留第一个小数点,其它全部取消
: 2.用Double.valueOf转换
: 3.比大小
: 用的是JAVA.
: O(n)

y*******8
发帖数: 2377
7
3.1.12 和3.2.1?

【在 U**K 的大作中提到】
: 拆成数组比如[2,1,3], 数组求和,和最大的最新
s******8
发帖数: 4192
8
这个一直有争议的是3.1到底比3.02高还是低?
t**********r
发帖数: 2153
9
java 用 comparable.

【在 s********u 的大作中提到】
: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
: 次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
: 每一位都要做一次快排,也就是O(knlogn)
: 另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一

s*w
发帖数: 729
10
正好昨天也在用 istringstream parse 字符串,共享一下
string line;
while(getline(cin,line)) {
istringstream iss(line);
vector vi;
int tmp;
do {
iss >> tmp;
iss.ignore(256,'.');
if(iss.good())
vi.push_back(tmp);
} while(iss.good());
}

【在 s********u 的大作中提到】
: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
: 次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
: 每一位都要做一次快排,也就是O(knlogn)
: 另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一

相关主题
请问如何binary search出数组中的重复元素题都感觉做对了,面试的人也满意,为什么二面过后还是直接悲剧呢……顺便上P面经
两道2009算法题请教两道CS题
包子求教:用二维数组排序问题再问一道数组题
进入JobHunting版参与讨论
q*c
发帖数: 9453
11
那就分段比字符串,比的时候长度相等就比大学,长度不等那么长的大。首字符为零去
掉。

【在 s********g 的大作中提到】
: 字符串不行。比如9.0和10.0
s********u
发帖数: 1109
12
这明显不对吧。比如3.4和3.2.23,后者长度更长,但前者更新。
似乎转换成数组是逃不掉的了

【在 q*c 的大作中提到】
: 那就分段比字符串,比的时候长度相等就比大学,长度不等那么长的大。首字符为零去
: 掉。

f*****n
发帖数: 224
13
1. 换成数组
2. qsort(),然后自己编一个函数比较大小

【在 s********u 的大作中提到】
: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
: 次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
: 每一位都要做一次快排,也就是O(knlogn)
: 另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一

f*****n
发帖数: 224
14
1. 换成数组
2. qsort(),然后自己编一个函数比较大小

【在 s********u 的大作中提到】
: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
: 次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
: 每一位都要做一次快排,也就是O(knlogn)
: 另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一

f*****n
发帖数: 224
15
1. 换成数组
2. qsort(),然后自己编一个函数比较大小

【在 s********u 的大作中提到】
: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经,感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复,一种解法是把3.1.3转换成一个数组{3,1,3},然后对所有数组补0,再依
: 次从右往左对每一位排序(有点像radix sort)但是这样感觉还是比较繁琐,相当于对
: 每一位都要做一次快排,也就是O(knlogn)
: 另一位说用radixsort,就是从右往左,每次做一个bucket sort。这样的好处是,每一

c******y
发帖数: 29
16
javascript好像可以直接比较?
m*******m
发帖数: 80
17
1. 转换成数组应该是逃不了, 那些比较String的函数总是会把3.14当做比3.2更高版本
.
2. java的话用comparator写比较的逻辑
q*c
发帖数: 9453
18
是每段内比啊,从左到右,第一个不等的决定大小。
不能转换,因为接下来溢出等问题坑爹。

【在 s********u 的大作中提到】
: 这明显不对吧。比如3.4和3.2.23,后者长度更长,但前者更新。
: 似乎转换成数组是逃不掉的了

1 (共1页)
进入JobHunting版参与讨论
相关主题
一个题考古到一道题
周末上道题请问如何binary search出数组中的重复元素
C++里如何将一个vector转换成priority_queue两道2009算法题
sliding window面试题包子求教:用二维数组排序问题
2sigma(interview st)的input format怎么读?题都感觉做对了,面试的人也满意,为什么二面过后还是直接悲剧呢……顺便上P面经
two sigma 的online code test 的问题请教两道CS题
LC的compare version有点麻烦再问一道数组题
湾区SNS公司面经背包问题
相关话题的讨论汇总
话题: find话题: latest话题: 数组话题: version