x*********n
发帖数: 29 | 1 印度人，其实还满NICE的。共面了两题，应该都是常见题。
１。给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？
我先说HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。
不知道还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING
ALGORITHM好象不是很合适吧。
２。 后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。
纠结的地方是
a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
http://www.meta-calculator.com/learning-lab/rpn-reverse-polish-
这个网站给出的结果 3 11 + 5 - = 5 - 14 = -9
这个答案和 imagong 上的 test case 是一致的。就是说 a,b,+,c,- = c-(a+b)
但其他两个网站给出的都是
http://www.mathblog.dk/tools/infix-postfix-converter/
http://mysite.verizon.net/res148h4j/javascript/script_reverse_p
3 11 + 5 - = 14 - 5 = 9
就是说 a,b,+,c,- = (a+b)-c
以前看这题没有好好研究。这次碰上估计是死了。有没有大牛帮忙解答一下。以后的面
试不至于再搞错了。痛心啊，这么简单的题没有好好准备。 | p*u
发帖数: 136 | 2 第一题：
1，解法类似出现次数多余一半的题：直接每次去掉3个不同的值就可以了
2，实现的时候，可以用hash表保存每个数字出现的次数，当hash表中节点个数为3时，
表示已经有3个不一样的值了，将所有节点的个数减1，个数为0的从hash表中删除
3，最后还留在hash表中的值，并不一定是最后的结果。
4，重新扫描一遍，记录个数，输出个数大于n/3的值。
【在 x*********n 的大作中提到】
: 印度人，其实还满NICE的。共面了两题，应该都是常见题。
: １。给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？
: 我先说HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。
: 不知道还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING
: ALGORITHM好象不是很合适吧。
: ２。 后缀波兰表达式STRING转换为中缀表达式的STRING。
: 这题本来很简单，但我可能算错了。
: 纠结的地方是
: a,b,+,c,/
: 到底是 (c/(a+b)) 还是 ((a+b)/c)
| n****e
发帖数: 678 | 3 根据wiki上的定义，应该是(a+b)/c 吧
【在 x*********n 的大作中提到】
: 印度人，其实还满NICE的。共面了两题，应该都是常见题。
: １。给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？
: 我先说HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。
: 不知道还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING
: ALGORITHM好象不是很合适吧。
: ２。 后缀波兰表达式STRING转换为中缀表达式的STRING。
: 这题本来很简单，但我可能算错了。
: 纠结的地方是
: a,b,+,c,/
: 到底是 (c/(a+b)) 还是 ((a+b)/c)
| h*****n
发帖数: 2872 | | p*******2
发帖数: 50 | 5 第一题可以用quickselect？
【在 x*********n 的大作中提到】
: 印度人，其实还满NICE的。共面了两题，应该都是常见题。
: １。给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？
: 我先说HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。
: 不知道还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING
: ALGORITHM好象不是很合适吧。
: ２。 后缀波兰表达式STRING转换为中缀表达式的STRING。
: 这题本来很简单，但我可能算错了。
: 纠结的地方是
: a,b,+,c,/
: 到底是 (c/(a+b)) 还是 ((a+b)/c)
| m********c
发帖数: 105 | 6 quickselect不行吧？知道要找的这个k是多少，是第几位
【在 p*******2 的大作中提到】
: 第一题可以用quickselect？
| m********c
发帖数: 105 | 7 下面两个链接是解法，可以找到出现次数大于n/k的所有数，time是O(n)，space是O(k)
。具体的对于k=3，space就是O(1)了
http://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-
http://www.quora.com/Algorithms/Given-an-array-of-n-elements-wh
【在 x*********n 的大作中提到】
: 印度人，其实还满NICE的。共面了两题，应该都是常见题。
: １。给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？
: 我先说HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。
: 不知道还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING
: ALGORITHM好象不是很合适吧。
: ２。 后缀波兰表达式STRING转换为中缀表达式的STRING。
: 这题本来很简单，但我可能算错了。
: 纠结的地方是
: a,b,+,c,/
: 到底是 (c/(a+b)) 还是 ((a+b)/c)
| v***n
发帖数: 562 | | g*******e
发帖数: 91 | 9 有的老/小印黑人是不客气的。我面L是被问到了pow()。之前我没刷题，但pow我是看过
的。这是我所有面试中写的最流畅的。小印还不信是对的，让我试了好几个cases。然
后俺被拒了，可怜一面都没过。
【在 x*********n 的大作中提到】
: 印度人，其实还满NICE的。共面了两题，应该都是常见题。
: １。给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？
: 我先说HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。
: 不知道还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING
: ALGORITHM好象不是很合适吧。
: ２。 后缀波兰表达式STRING转换为中缀表达式的STRING。
: 这题本来很简单，但我可能算错了。
: 纠结的地方是
: a,b,+,c,/
: 到底是 (c/(a+b)) 还是 ((a+b)/c)
| d**********x
发帖数: 4083 | 10 haha...
【在 g*******e 的大作中提到】
: 有的老/小印黑人是不客气的。我面L是被问到了pow()。之前我没刷题，但pow我是看过
: 的。这是我所有面试中写的最流畅的。小印还不信是对的，让我试了好几个cases。然
: 后俺被拒了，可怜一面都没过。
| t********e
发帖数: 12 | | t********e
发帖数: 12 | 12 持续partitioning，如果partition小于n/3，忽略；如果partition中的数字都相等，
则找到。
//return pivot position so that ary[begin...pivot]<=ary[pivot]
.end]
//or -1 if whole section are equal
static int Partition(int[] ary, int begin, int end)
{
//...
}
static bool FindItemOneThird(int[] ary, int begin, int end, out int item)
{
item = 0;
int pivotPos = Partition(ary, begin, end);
if (pivotPos == -1)
{
item = ary[begin];
return true;
}
//part1
if (pivotPos - begin + 1 > ary.Length / 3)
{
if (FindItemOneThird(ary, begin, pivotPos, out item))
return true;
}
//part2
if (end - pivotPos > ary.Length / 3)
{
if (FindItemOneThird(ary, pivotPos + 1, end, out item))
return true;
}
return false;
} | x*********n
发帖数: 29 | 13 两题答的乱七八糟，三哥居然给过了！多谢大家帮忙解答第一题，有没有朋友能指点一
下波兰表达试的问题？ | t********e
发帖数: 12 | 14 the benefit of postfix or reverse polish expression is that it's a no
brainer evaluation. i.e. when you see a operator, just do evaluation.
the order of operands is actually the same as infix expression.
so ab+c/ => (a+b) c/ => ((a+b)/c) |
|
