uber电面面经

先谈了简历project，大概15分钟，然后发了个coderpad的连接做题。

1. 给定一个string，判断能否用这个string来组成一个palindr

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2015-1-20 20:37):
新农回复次数都有限制，求米啊

hjm0505 发表于 2015-1-20 21:18
感觉题目还好，祝楼主拿到onsite～～

谢谢，题目不算难，希望能onsite

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. /**
   
5. * If a given string can be permutated to form a palindrome string
   
6. * I - string
   
7. * O - bool, true/false
   
8. */
   
9. int is_palindrome(string &str) {
   
10.   unordered_map<char, int> table;
    
11.   for (char c : str)
    
12.     table[c]++;
    
13.   int o=0, e=0;
    
14.   for (auto p : table) {
    
15.     if (p.second&1) o++;
    
16.     else            e++;
    
17.   }
    
18.   return o<2;
    
19. }
    
20. 
    
21. /**
    
22. * Extract all even chars
    
23. * I - string
    
24. * O - chars of first half of the potential palindrome string
    
25. */
    
26. vector<char> half_string(string &str, char &mid) {
    
27.   unordered_map<char, int> table;
    
28.   for (char c : str)
    
29.     table[c]++;
    
30.   vector<char> ret;
    
31.   for (auto p : table) {
    
32.     if (!(p.second&1))
    
33.       for (int i=0; i<p.second/2; i++)
    
34.         ret.push_back(p.first);
    
35.     else
    
36.       mid=p.first;
    
37.   }
    
38.   return ret;
    
39. }
    
40. 
    
41. /**
    
42. * Generate all possible palindrome strings.
    
43. * I - string
    
44. */
    
45. void generate_palindrome(int c, int n, vector<char> &a, string &p, int v[], char &mid) {
    
46.   if (c==n) {
    
47.     string pr=p;
    
48.     reverse(pr.begin(), pr.end());
    
49.     if (mid)
    
50.       pr=mid+pr;
    
51.     pr=p+pr;
    
52.     cout<<pr<<endl;
    
53.   } else {
    
54.     for (int i=0; i<n; i++) if (!v[a[i]]) {
    
55.       v[a[i]]=1;
    
56.       p[c]=a[i];
    
57.       generate_palindrome(c+1, n, a, p, v, mid);
    
58.       v[a[i]]=0;
    
59.       while (i<n-1 && a[i+1]==a[i]) i++;
    
60.     }
    
61.   }
    
62. }
    
63. 
    
64. int main(void) {
    
65.   string str;
    
66.   cin>>str;
    
67.   if (is_palindrome(str)) {
    
68.     char mid=0;
    
69.     auto half=half_string(str, mid);
    
70.     sort(half.begin(), half.end());
    
71.     int n=half.size();
    
72.     int v[256];
    
73.     memset(v, 0, sizeof v);
    
74.     string palindrome(n, ' ');
    
75.     generate_palindrome(0, n, half, palindrome, v, mid);
    
76.   }
    
77. }
    

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主第一题是不是统计一下每个字符的出现次数
如果只有0或1个字符出现奇数次，那么就能组成palindrome？

赞~~
LZ 如何拿的面试？

圆梦梦剧场 发表于 2015-1-20 18:58
楼主第一题是不是统计一下每个字符的出现次数
如果只有0或1个字符出现奇数次，那么就能组成palindrome？

对，我就是这么答得。用hashtable记录每个字符出现的频率，然后遍历hashtable算出频率为奇数的字符数，如果小于2就可以

houqingniao 发表于 2015-1-20 19:42
赞~~
LZ 如何拿的面试？

直接网申的

感觉题目还好，祝楼主拿到onsite～～

后天面，希望不难。。。

王者无敌Alex 发表于 2015-1-26 00:21
后天面，希望不难。。。

看了些面经，感觉都不难，应该没问题的，加油！

第二题的permutation请问如何写阿