z****e
发帖数: 54598 | 1 完整代码，基本上是白话，直接看就是了
import java.util.*;
public class Solution {
public int longestConsecutive(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
int max = 1;
Map map = new HashMap();
for(int i:num){
if(!map.containsKey(i)){
Interval interval = new Interval();
if(map.containsKey(i+1)) interval.upperBound = map.get(i+1).
upp... 阅读全帖 |
|
u*****o
发帖数: 1224 | 2 最近这道题很火爆！我找来貌似最EFFICIENT的CODE看（就是传说中的SIEVE OF
ERATOSHENES，多高端的名字！！），发现这么一行
请大家看第三行，第四行。。。为什么要用MEMSET这个function呢。。bool
array的话默认就是0吧。。。是不是为了省MEMORY呢？我直觉是。。。
走过路过的牛牛们指点一下吧。。。
void runEratosthenesSieve(int upperBound) {
int upperBoundSquareRoot = (int)sqrt((double)upperBound);
bool *isComposite = new bool[upperBound + 1];
memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
... 阅读全帖 |
|
h*********3
发帖数: 111 | 3 你得到每个upperbound后，为什么还要binary search呢，难道不是只可能在
upperbound 和 upperbound-1 之间取一个吗？
比如 target is 31,
ceiling(pow(31,1/2)) = 5, 就只需要考虑 2^4 和2^5,
ceiling(pow(31,1/3)) = 4, 就只需要考虑 3^3 和3^4
一直到 ceiling(sqrt(31)) = 6,
ceiling(pow(31,1/6)) = 2, 只考虑 6^2 |
|
r****c
发帖数: 2585 | 4 第二题
public boolean recCheckBST(TreeNode node, int upperBound, int lowerBound) {
if (node == null) {
return true;
}
if (node.val <= upperBound && node.val >=lowerBound) {
return recCheckBst(node.left, root.val, lowerBound) && recCheckBst(node
.right, upperBound, rootNode.Val);
}
}
public boolean checkBst(TreeNode root) {
if (root == null) {
// ask the interviewer what should return;
return recCheckBst(root, Long.MAX, Long.MIN);
} |
|
l********6
发帖数: 129 | 5 虽然没做过 但是目测复杂度也就是降到nlogn吧 不知道有没有大神能想出线性的解法
nlogn的话就从后往前遍历 用一个set存之前的那些数 然后拿到下一个数的时候 在set
里面找upperbound 然后得出upperbound前面有多少个数 再把这个数插到upperbound之
前 整体上相当于维护一颗bst（实际上是rbtree）
[在 lalo (lalo) 的大作中提到：]
：给一个数组，比如【5，2，6，1】
：对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比
它小；1的右边0个比它小.
：........... |
|
r*********n
发帖数: 4553 | 6 upperBound是什么？比如让你找第999个prime number，你怎么确定upperBound呢？ |
|
c********l
发帖数: 8138 | 7 if (node.val <= upperBound && node.val >=lowerBound) {
return recCheckBst(node.left, root.val, lowerBound) && recCheckBst(node
.right, upperBound, rootNode.Val);
}
你这后面漏了一句“return false;”
node |
|
l********6
发帖数: 129 | 8 为什么是O(n)？你的while loop并不能保证每次查找upperbound的时间达到O(1)啊，你
的smaller存的是每一个A[i]的upperbound，但是每次查找的过程都是顺着smaller里面
存的下标往前找，直到找到第一个A[index]可以满足A[i] > A[indx]，这是线性不是常
量的复杂度啊，方便的话求详解~~ |
|
q***e
发帖数: 21 | 9 一个二维数组cost[n][n]，行表示category，列表示该category所在的序列。cost[i][
j]表示category i安排到序列位置j对应的cost,cost>0。要从所有的category中取出一
些category以及它们对应的序列,使得category对应的序列的cost在一个upperbound内
总和的的值最大。需要考虑如果cost,upperbound都为double的情况，或者都为integer
的情况。可以有一些category不被选。
要求只能的DP。 |
|
w**a
发帖数: 6 | 10 在一个正六边形里最多可以放几个点？
constraints：任何两点之间的距离不能小于d。
能给出比较tight 的upperbound也行
我想到了一个upperbound：用六边形的面积除以半径为d/4的圆。但这个bound不tight
我还有一个猜想：是不是用这些点构成等边三角形，可以得到最多的点？这个对么？可
以证明么？ |
|
x******a
发帖数: 6336 | 11 钱是不是给个upperbound，告诉文科生们：沙茶，不要在网上吹了 |
|
|
c*******d
发帖数: 255 | 13 3这题，应该可以O(sqrt(n))解决
n = (s+1)+(s+2)+...+(s+k)
= ks + k(k+1)/2
其中 s>=0, k>=2 都是整数
所以 k(k+1)/2 <= n，由此可以得到k的upperbound k0，大约是sqrt(n)的量级
然后做个循环，k=2, ..., k0，判断 [n - k(k+1)/2]/k 是否是整数就可以了
BST |
|
y*c
发帖数: 904 | 14 这道题，如果没有编过，电面写出正确code是很有难度的。我用两种方法编过，一种就
是jntl说的根据x[lowerbound], x[upperbound]和x[middle]跟要寻找的target做比较
，分情况进行判断，很subtle。另一种就是找出最大值（类似于找first occurrence
in a sorted array），然后找到递增的subsequence进行binary search，都是log n |
|
d********w
发帖数: 363 | 15 binary search是最经典的算法之一，编程珠玑上说只有10%的人能写对，看来还是很有
挑战的：-), 需要小心的是区间的开闭，取中点是否会overflow, 确定新upperbound和
lowerbound的范围，会不会死循环
其实还可以衍生其他问题，比如：
1）如果找不到元素，返回应该插入的位置
2）如果数组允许有重复，寻找最小的那个i，使得arr[i] = v， （第一次出现的位置）
3）如果数组允许有重复，寻找最大的那个i，使得arr[i] = v
4）如果数组允许有重复，寻找最小的那个i，使得arr[i] > v
5）如果数组允许有重复，寻找最大的那个i，使得arr[i] < v
6）给2个有序数组，大小一致，如何求他们的median
7）循环数组的二分查找
欢迎大家补充，除了最后2个，其他不难，但是要保证没有bug就需要多练了。
参考资料：
http://en.wikipedia.org/wiki/Binary_search
Programing pearls: Ch4, Ch9.3 |
|
p*****u
发帖数: 310 | 16 不会的， 她也是这样说的。 其实call 5的 左子树3的时候， 5就作为upper bound传
下去了，在call 3的右子树6的时候， 6得到3的 upperbound，就是5，所以这是检查了
的。
IsvaidBST（5－>left, 5, INT_MIN) then
IsvaidBST（3－>right, 5, 3)
invalid. |
|
S******n
发帖数: 132 | 17 来自主题: JobHunting版 - 问到G家题 是不需要，这个题目是不是也可以转化
有duplicate的BST找lowerbound和upperbound？ |
|
f***s
发帖数: 112 | 18 电面，第二道coding，naive解法是直接上一个hashset然后统计漏掉的，0(n) 空间复
杂度。
顺便说了下多元一次方程，面试官说这个方法对k很小的解法还行，k多了就复杂度上去
了。
然后提示 100用几位可以表示，我说7位，因为 128是1-100的二进制表达upperbound。
然后说到了对于每一位进行单独处理，0-127的sum结果是每一位的1和0出现的次数一样
，面试官表示在right path。 |
|
l********6
发帖数: 129 | 19 你的内循环不算数么？你那个while loop做的事情还是在sorted array里面从大到小顺
序查找一个upperbound啊 |
|
q***e
发帖数: 21 | 20
不需要。有些category也许没有使用，关键在于低于upperbound的最大值 |
|
h****8
发帖数: 599 | 21 今天刚刚看到海报贴出来 体重分级对我很有利阿 149~181lb级 我正好在upperbound附近
有哪位参加过比赛的哥们说说接近比赛前期的训练应该如何调整？有什么注意事项？10
月9号晚上比赛 |
|
h****8
发帖数: 599 | 22 correct. The tables and formulas usually give an upperbound of 1rep max.
requires |
|
s*******e
发帖数: 664 | 23 ☆─────────────────────────────────────☆
coconut (向唐僧大师学习中) 于 (Wed Aug 19 20:40:43 2009, 美东) 提到:
前两星期 interview 被问到一个问题：given a binary tree, how to
store/restore its structure efficiently. 该问题只管 structure，不管
其中的 node 等。俺的解是 2 bits per node，DFS 。又被问到什么情况下
能更小些（balanced tree，然后 compression，最好用 BFS）。结果他又提
到什么 theoretical upperbound / lowerbound 等，没明白咋回事，不过好
在不用回答。
问题是：这东西有啥应用？
☆─────────────────────────────────────☆
goodbug (好虫) 于 (Wed Aug 19 20:45:34 2009, 美东) 提到:
您老也找工作，估计就是self balanced |
|
t******r
发帖数: 209 | 24 Here is recurrence deduction:
if
sum(T(n)-T(i)) = O(n^2) (1
and T(1) = 0 and T(2) = 1,
how to deduce the tightest upperbound of T(n)? |
|
t******r
发帖数: 209 | 25 Here is recurrence deduction:
if
sum(T(n)-T(i)) = O(n^2) (1
and T(1) = 0 and T(2) = 1,
how to deduce the tightest upperbound of T(n) complexitiy? |
|
a*****h
发帖数: 484 | 26 That's more like an upperbound to me, while if the first player don't pick
the number randomly, but strategically, you're never gonna get this much ($1
).
,
make |
|
k*****y
发帖数: 744 | 27 Well, I think they might probably ask:
Would you like to bet 20:1 on your answer 741 is correct?
Are you truely 95% confident that 741 is correct?
I think if you are only 95% confident, you should not make the bet; though
if you are more than 96% confident, then you should.
I don't know how to answer this kind of questions. But to be safe, I think I
might find a rigorous lowerbound A and upperbound B, so hopefully [A, B] is
my almost 100% confidence interval, and take 95% percent middle part(or
... 阅读全帖 |
|
k*****y
发帖数: 744 | 28 Well, I think they might probably ask:
Would you like to bet 20:1 on your answer 741 is correct?
Are you truely 95% confident that 741 is correct?
I think if you are only 95% confident, you should not make the bet; though
if you are more than 96% confident, then you should.
I don't know how to answer this kind of questions. But to be safe, I think I
might find a rigorous lowerbound A and upperbound B, so hopefully [A, B] is
my almost 100% confidence interval, and take 95% percent middle part(or
... 阅读全帖 |
|
t******3
发帖数: 431 | 29 how to get the output dataset from this procedure? Like to find the charts
that has outliers ( out of the upperbound), but can't figure out how to
automate that. Currently I have to look at the output chart one by one.
Any suggestion? |
|
m*z
发帖数: 2356 | 30 【 以下文字转载自 pennystock 俱乐部 】
发信人: mmz (酱爆), 信区: pennystock
标 题: GTE
发信站: BBS 未名空间站 (Fri Oct 23 17:16:01 2009, 美东)
Is a good candidate to buy dip?
In weekly chart,
MACD is above 0 which implies that the underlying moving averages are
trending higher.
CMF is very bullish
Volume is increasing, but it is not peak yet which is good.
however the oscillator has moved above the critical value of 80 and is now
overbought. And candle body is outside of upperbound of BB. |
|
m*z
发帖数: 2356 | 31 Is a good candidate to buy dip?
In weekly chart,
MACD is above 0 which implies that the underlying moving averages are
trending higher.
CMF is very bullish
Volume is increasing, but it is not peak yet which is good.
however the oscillator has moved above the critical value of 80 and is now
overbought. And candle body is outside of upperbound of BB. |
|
m*z
发帖数: 2356 | 32 还拉啊, 都翻倍了! 已经冲到BB的upperbound外面了, 短期没多少空间了. |
|
