c***z
发帖数: 6348 | 1 【 以下文字转载自 DataSciences 讨论区 】
发信人: chaoz (面朝大海，吃碗凉皮), 信区: DataSciences
标 题: T家在线题2道
发信站: BBS 未名空间站 (Thu Jun 19 21:00:22 2014, 美东)
已经悲剧
题1：anagram of a palindrome 要求O(N)
int isAnagrmaOfPalindrome(char *string){
unsigned int bitc = 0, i = 0;
int out = 0;
while(*string){
i = *(string++) - 'a';
bitc ^= (1 << i);
}
out = (int)(bitc & (bitc - 1));
return !out;
}
题2：重新排序整数的digits使其最大化 (e.g. 3515 -> 5531) 要求O(1)
int largestSibling(int N) {
int digit;
int temp = 0;
int output = 0;
for (digit=9;digit>0;digit--)
for (temp=N;temp>0;temp/=10)
if (temp%10==digit) output = output + digit*10;
return output;
}
感想：这和data scientist有什么关系嘛？ |
y***n
发帖数: 1594 | |
h**6
发帖数: 4160 | |
a******p
发帖数: 157 | 4 第一题也有些不对劲
如果输入是a输出false
【在 c***z 的大作中提到】
: 【 以下文字转载自 DataSciences 讨论区 】
: 发信人: chaoz (面朝大海，吃碗凉皮), 信区: DataSciences
: 标 题: T家在线题2道
: 发信站: BBS 未名空间站 (Thu Jun 19 21:00:22 2014, 美东)
: 已经悲剧
: 题1：anagram of a palindrome 要求O(N)
: int isAnagrmaOfPalindrome(char *string){
: unsigned int bitc = 0, i = 0;
: int out = 0;
: while(*string){
|
c*****l
发帖数: 1493 | 5 lz你这么牛都挂了...
我也悲剧了.hr说什么这题是测试ds背景的,一看是sde,非常无语.
【在 c***z 的大作中提到】
: 【 以下文字转载自 DataSciences 讨论区 】
: 发信人: chaoz (面朝大海，吃碗凉皮), 信区: DataSciences
: 标 题: T家在线题2道
: 发信站: BBS 未名空间站 (Thu Jun 19 21:00:22 2014, 美东)
: 已经悲剧
: 题1：anagram of a palindrome 要求O(N)
: int isAnagrmaOfPalindrome(char *string){
: unsigned int bitc = 0, i = 0;
: int out = 0;
: while(*string){
|
a**********0
发帖数: 422 | 6 不是双重循环 外层循环是从1到10 总体也就是10n 也就是O（n） 如果字符串长度为n
的话
【在 h**6 的大作中提到】
: 第二题双重循环，不是O(1)啊。
|
a**********0
发帖数: 422 | 7 第二题 我觉得constant是什么意思呢？
假设使用java表示一个整数 整数最大是27... 是个具体的数 也就是说即使按照数字的
位数来算 数字最多也是整数位
所以我觉得 你可以这样
建立一个int【】 长度为10 扫描一次 记录每个数字出现的次数 这个过程就是
constant 为什么 因为位数有上限 然后在循环一次 从后向前构造最大数
尽管看上去像是o（n） 但是n由于java存储的原因是有上限的 比如 int最多不超过100位 |
a**********0
发帖数: 422 | 8 第一题什么意思呢
给出一个字符串 判断是不是某个Palindrome的anagram吗
出现次数为奇数个的字母最多只有一个 这不是判断条件吗 什么意思 能把题目完整写
一下吗 |
f*******r
发帖数: 1086 | |
b***y
发帖数: 177 | 10 http://comproguide.blogspot.com/2013/11/checking-if-any-anagram
【在 a**********0 的大作中提到】
: 第一题什么意思呢
: 给出一个字符串 判断是不是某个Palindrome的anagram吗
: 出现次数为奇数个的字母最多只有一个 这不是判断条件吗 什么意思 能把题目完整写
: 一下吗
|
|
|
l*********8
发帖数: 4642 | 11 第二题，如果是32位整数，最多10个digit。逐个digit处理的话，最多10次。勉强可以
算O(10) = O(1)吧。 按digit的数目n来算，就是O(n)。 如果按输入的数据的范围M来
算，就是O(log M);
【在 c***z 的大作中提到】
: 【 以下文字转载自 DataSciences 讨论区 】
: 发信人: chaoz (面朝大海，吃碗凉皮), 信区: DataSciences
: 标 题: T家在线题2道
: 发信站: BBS 未名空间站 (Thu Jun 19 21:00:22 2014, 美东)
: 已经悲剧
: 题1：anagram of a palindrome 要求O(N)
: int isAnagrmaOfPalindrome(char *string){
: unsigned int bitc = 0, i = 0;
: int out = 0;
: while(*string){
|
l*********8
发帖数: 4642 | 12 第二题要我做的话， 只能这样：
int largestSibling(int n) {
int count[10] = {0};
for ( ; n; n/=10)
++count[n%10];
int ans = 0;
for (int i=9; i>=0; i--)
for ( ; count[i]; --count[i])
ans = ans * 10 + i;
return ans;
}
【在 l*********8 的大作中提到】
: 第二题，如果是32位整数，最多10个digit。逐个digit处理的话，最多10次。勉强可以
: 算O(10) = O(1)吧。 按digit的数目n来算，就是O(n)。 如果按输入的数据的范围M来
: 算，就是O(log M);
|
l*********8
发帖数: 4642 | 13 刚才看到和apprentice的解法一样的。
【在 l*********8 的大作中提到】
: 第二题要我做的话， 只能这样：
: int largestSibling(int n) {
: int count[10] = {0};
: for ( ; n; n/=10)
: ++count[n%10];
: int ans = 0;
: for (int i=9; i>=0; i--)
: for ( ; count[i]; --count[i])
: ans = ans * 10 + i;
:
|
l*********8
发帖数: 4642 | 14 输入a返回true
我觉得第一题没问题
【在 a******p 的大作中提到】
: 第一题也有些不对劲
: 如果输入是a输出false
|
c*******y
发帖数: 98 | |
c***z
发帖数: 6348 | 16 来自jobvite的坑爹的ＨＲ说面ＳＱＬ
codility的坑爹test给了这两题
我含着眼泪做完，以为能run就ok
submit了也没个comfirmation email什么的
最后自己抽抽了，给了各反馈说这test完全没有意义
综合以上，要是能过就是奇迹了 |
c***z
发帖数: 6348 | 17 I think so too. There is no way for O(1), since we still need to go over all
the digits no matter what.
【在 l*********8 的大作中提到】
: 第二题，如果是32位整数，最多10个digit。逐个digit处理的话，最多10次。勉强可以
: 算O(10) = O(1)吧。 按digit的数目n来算，就是O(n)。 如果按输入的数据的范围M来
: 算，就是O(log M);
|
c***z
发帖数: 6348 | 18 IIRC
第一题固定小写 yes
第二题固定正整数 yes |
d**k
发帖数: 797 | 19 第二题可能overflow不？
【在 c***z 的大作中提到】
: IIRC
: 第一题固定小写 yes
: 第二题固定正整数 yes
|
a**********0
发帖数: 422 | 20 有可能啊 其实吧Integer.MAX_VALUE拿出来是27多少多少 肯定溢出了
所以必须return long
【在 d**k 的大作中提到】
: 第二题可能overflow不？
|
|
|
a**********0
发帖数: 422 | 21 我的意思是不用找最大的排列 直接把7放在第一位就溢出了
【在 a**********0 的大作中提到】
: 有可能啊 其实吧Integer.MAX_VALUE拿出来是27多少多少 肯定溢出了
: 所以必须return long
|
a***n
发帖数: 623 | 22 第一题
这个解法是很巧妙，能保证string中没有或只有一个奇数次的字符。
不过是我理解题目理解错了吗？
我觉得比如”aabbc“这种应该return false？因为无论怎么进行anagram变换都不可能
变成palindrome呀……
【在 c***z 的大作中提到】
: IIRC
: 第一题固定小写 yes
: 第二题固定正整数 yes
|
b********r
发帖数: 620 | 23 大牛，您老人家可能题做多了做糊涂了。
啥是anagram变换？aabbc -> abcba?
【在 a***n 的大作中提到】
: 第一题
: 这个解法是很巧妙，能保证string中没有或只有一个奇数次的字符。
: 不过是我理解题目理解错了吗？
: 我觉得比如”aabbc“这种应该return false？因为无论怎么进行anagram变换都不可能
: 变成palindrome呀……
|
t*******i
发帖数: 4960 | 24 haha,同感。
【在 b********r 的大作中提到】
: 大牛，您老人家可能题做多了做糊涂了。
: 啥是anagram变换？aabbc -> abcba?
|
s*i
发帖数: 5025 | 25 你这题2的解根本就是错的。3515你的程序给出的答案是140。
【在 c***z 的大作中提到】
: IIRC
: 第一题固定小写 yes
: 第二题固定正整数 yes
|
s*i
发帖数: 5025 | 26 这个思路跟我想的一样，只不过算 x*10的那里，可以用pow(10, x)。当然这个pow 函
数还得自己实现。
【在 l*********8 的大作中提到】
: 第二题要我做的话， 只能这样：
: int largestSibling(int n) {
: int count[10] = {0};
: for ( ; n; n/=10)
: ++count[n%10];
: int ans = 0;
: for (int i=9; i>=0; i--)
: for ( ; count[i]; --count[i])
: ans = ans * 10 + i;
:
|
s*i
发帖数: 5025 | 27 我觉得好像是说输入一个palinrome word，看有多少个不同的anagram?
【在 a**********0 的大作中提到】
: 第一题什么意思呢
: 给出一个字符串 判断是不是某个Palindrome的anagram吗
: 出现次数为奇数个的字母最多只有一个 这不是判断条件吗 什么意思 能把题目完整写
: 一下吗
|
y**********a
发帖数: 824 | 28 第一题：O(n)
boolean anagramParlindrom(String s) {
Map m=new HashMap<>();
for (char c:s.toCharArray())
if (m.containsKey(c)) m.put(c, m.get(c)+1);
else m.put(c, 1);
int c=0;
for (Map.Entry e:m.entrySet())
c+=e.getValue()%2;
return c<=1;
}
第二题：O(len(n))
int countSort(int n) {
if (n==0) return 0;
int[] count=new int[10];
while (n!=0) {
++count[n%10];
n/=10;
}
StringBuilder s=new StringBuilder();
for (int i=9;i>=0;--i)
for (int j=0;j
return Integer.parseInt(s.toString());
} |
s*i
发帖数: 5025 | 29 喜欢这两个思路！
第二个更有意思！string转数字开销大不大？
【在 y**********a 的大作中提到】
: 第一题：O(n)
: boolean anagramParlindrom(String s) {
: Map m=new HashMap<>();
: for (char c:s.toCharArray())
: if (m.containsKey(c)) m.put(c, m.get(c)+1);
: else m.put(c, 1);
: int c=0;
: for (Map.Entry e:m.entrySet())
: c+=e.getValue()%2;
: return c<=1;
|
y**********a
发帖数: 824 | 30
O(n)
【在 s*i 的大作中提到】
: 喜欢这两个思路！
: 第二个更有意思！string转数字开销大不大？
|
