t****a
发帖数: 1212 | 1 来自主题: JobHunting版 - 请问G一题 三个参数
1. 序列长度
2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同 |
|
v**********r
发帖数: 40 | 2 Hashtable 记录第一次出现的Index. 扫描的时候之前有记录的话就记录那个差值。一
遍扫描。
他是一上来就心情很差。。。一个a3. |
|
d**********x
发帖数: 4083 | 3 也就是说你的hashtable里面有两个value，一个是第一次的index，一个是差值？
那问题不大啊。。。他心情不好可能是别的原因吧=。= |
|
v**********r
发帖数: 40 | 4 啊不是
是key存的是元素，value是index
另外还有一个变量来记录当前最大的差值。 |
|
|
h****n
发帖数: 1093 | 6 貌似比股票第三题还简单一点，那个需要找差值最大的 |
|
d****n
发帖数: 56 | 7 第一题可以用差值绝对值放进maxheap来做吧，
第二题总行数和每行的元素数量是不是都要纪录更新啊 |
|
c****m
发帖数: 11 | 8 赞，好主意，应该是min heap，差值最小的在堆顶，然后逐步pop出m个元素。错了，确
实应该max heap...
复杂度NlgM，如果N>>M，则只用了M的额外空间，比in-order traversal强，但是时间
复杂度好像略微高了些。
不知道这样分析对不对？ |
|
d**s
发帖数: 98 | 9 非常规的解法：
http://blog.csdn.net/anchor89/article/details/6055412
经典面试题:设计包含min函数的栈,O(1)空间实现方法
分类： 数据结构和算法 2010-12-04 22:20 2102人阅读 评论(10) 收藏 举报
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数
min、push以及pop的时间复杂度都是O(1)。
注:这是06年一道Google的面试题.
先来说个常规解和他的一个优化,常规解的时间复杂度符合要求,但需要线性的额外空间.
常规解(参考 http://zhedahht.blog.163.com/blog/static/25411174200712895228171/):
除了题目要求的栈之外新开一个栈,用来记录最小值,每当在原栈中push数据后,与最小
值栈中的栈顶元素比较,如果新值较小,则在最小值栈中push新值;否则再次push栈顶元
素.
pop的时候,只要将最小值栈也pop一下就行了.
这样,min函数只需要返回最小值栈的栈顶元素即可.
常规解空间上的一个优化:
一般... 阅读全帖 |
|
f*********m
发帖数: 726 | 10 能不能这样？
先定义两个index（index1_1, index2_1),每个指向数组头，然后比较移动，每次移动
值小的，直到两个index的和为K。然后，再定义两个index（index1_2, index2_2),每
个指向数组头，用同样的方法每次移动index1_1或 index2_1，也同时移动index1_2或
index2_2。当index1_1或 index2_1指向给定的值时，index1_1或 index2_1指向左边的
第K个数， 记录他。继续移动index1_1或 index2_1，也同时移动index1_2或 index2_2
，当index1_1或 index2_1指向给定的数时，index1_2或 index2_2指向给定的数右边第
K个数。最后比较这两个数与给定书的差值。 |
|
e****e
发帖数: 418 | 11 一电：
１。给定一个数组，求次大值。
２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
的元素类型不是整数型，可能是String, double, Date...，如何处理？
二电：
１。给一个文件，从中找电话号码。
２。什么是哈希表？解决冲突的方法？
３。分层打印二叉数。
４。二维坐标里n个点，求离原点坐标最近的k个点。
５。面向对象的设计题：停车场。
面对面一：
１。问简历
２。给定一个长度为n整数型数组，看是否满足以下条件，相临数字之差的绝对值，刚
好可以组成 1,2,...,n-1。
例子：2 5 4 6 --> 1, 2, 3 成立。
2 5 4 7 --> 1, 3, 3 不成立。
1 2 3 4 --> 1, 1, 1 不成立。
引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
面二：
１。问简历
２。求次方，底是个浮点型，指数是整型。
３。面向对象的设计题：从数据模型的角度设计购物网站。主要有哪些类，类里主要有
哪些域，如何... 阅读全帖 |
|
b****g
发帖数: 192 | 12 给定一个长度为n整数型数组，看是否满足以下条件，相临数字之差的绝对值，刚
好可以组成 1,2,...,n-1。
例子：2 5 4 6 --> 1, 2, 3 成立。
2 5 4 7 --> 1, 3, 3 不成立。
1 2 3 4 --> 1, 1, 1 不成立。
引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
不会做。。。 |
|
e****e
发帖数: 418 | 13 我用了个布耳数组，走一遍原数组，两两求差，差值作为布耳数组下标，置其值为true. |
|
h**u
发帖数: 35 | 14 "引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。"
Totally, We have n*(n-1)/2 differences. Does that mean these differences
must constitute a consequtive sequence 1, 2 .. n-1 by allowing duplicates in
it? Otherwise we could use 1 2 4 5 to generate an 1 2 3. |
|
h**u
发帖数: 35 | 15 "引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。"
Totally, We have n*(n-1)/2 differences. Does that mean these differences
must constitute a consequtive sequence 1, 2 .. n-1 by allowing duplicates in
it? Otherwise we could use 1 2 4 5 to generate an 1 2 3. |
|
f*****e
发帖数: 2992 | 16 1 2 4 5 =>
1 2 3 4
差值
in |
|
f*****e
发帖数: 2992 | 17 引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。 |
|
f*****e
发帖数: 2992 | 18 我觉得完整的表述是：
引申问题：给定一个长度为n整数型数组，看是否满足以下条件，任何位置的数字和其他
任何位置的数字的差值的绝对值，刚好可以组成 1,2,...,n-1。
找个小于n平方的时间复杂度的方法。
6 |
|
|
c********t
发帖数: 5706 | 20 我的问题是每个元素能用几次？
第一问 2,5,4,6 每个元素被用2次（头尾只用1次）
而根据你对follow up的描述，似乎1,2,3,4，可以用2-1,3-1,4-1来组成差值？
1) |
|
c********t
发帖数: 5706 | 21 嗯，同意，只有一个问题，我觉得对每一个点，应该只算上下左右4个，比如你的例子
，第一次3只应该对2起作用。然后像lz说的，比3小的算差值，比3大的push进去。 |
|
c********t
发帖数: 5706 | 22 嗯，同意，只有一个问题，我觉得对每一个点，应该只算上下左右4个，比如你的例子
，第一次3只应该对2起作用。然后像lz说的，比3小的算差值，比3大的push进去。 |
|
c********t
发帖数: 5706 | 23 再好好想想。sort了以后，三个数组，你会怎样找 最小绝对差值？
1）遍历会怎么找？
2）如果你现在取到 a 1, b 3, c 5 你下一个会怎么取？ |
|
r*******e
发帖数: 7583 | 24 没看懂。我说的是sort之后merge成一个，然后扫描merged array
现在找到了a=1, b=3, c=5，记录差值8，然后保留b,c,找c的下一个 |
|
e***l
发帖数: 710 | 25 先sort，然后从3个头开始，最小的那个元素前进。扫一遍就可以了。
这个目标函数其实就是最大最小的差值的2倍，和中间的那个数没关系 |
|
c********t
发帖数: 5706 | 26 取与两边差值最大的数，应该先取两个4. 我觉得这个greedy算法可行。不过不知怎么
证明。
(4-（1+1)) > (5-(1+4)) |
|
b******7
发帖数: 92 | 27 1)canJump
从右往左是经典dp，
f(i)表示第i+1个点跳到底n个点最小步骤
f(i) = min{1 + f(i+k)}, k = 1... A[i]
2）BST 加successor
void add_successor(TreeNode * root)
{
if(root == NULL) return NULL;
TreeNode * pre = NULL;
stack s;
for(TreeNode * p = root; p != NULL; p= p->left)
s.push(p);
while(!s.empty())
{
TreeNode * cur = s.top();
s.pop();
if(pre != NULL) pre->successor = cur;
pre = cur;
for(TreeNode * p = cur... 阅读全帖 |
|
p*****2
发帖数: 21240 | 28 来自主题: JobHunting版 - 周末出道题
第二遍k select的时候用差值进行排序。 |
|
r*******e
发帖数: 7583 | 29 最大连续差值，int[2]存lastValue和currMax吧 |
|
o******e
发帖数: 1001 | 30 第二个题目，如果只有一个break point,比较好做，其实先算一个总和，然后看不同的
分割点之前的和与总和的差值。如果多点break point,是不是用dynamic programming
了？
What
B| |
|
w********g
发帖数: 106 | 31 指出了一个design的题目。
class Msg
{
long key; // unique
long val;
};
class Window
{
Window(int nMicrosecs);
addMsg(Msg m);
Msg getMsg(long key);
Double getAvg();
};
有一个stream of messgages，把最近的一些message存到Window里面，就像个sliding
window一样。要求design这个Window class。
比如，Window里面存最近5分钟的message。
addMsg（）就要添加一个mesage。
getMsg（）就return一个message。
getAvg（）计算window里所有message的val的平均值。
要求要efficient。
我不明白他说的5分钟什么意思，因为msg数据结构里没有时间，他说我可以自己添加。
我又问：如果过去5分钟没有任何message进来，那么window就空了。他马上说：明白你
的意思，不用考虑window的这种随时间的变化。我就问... 阅读全帖 |
|
a***n
发帖数: 3633 | 32 听说这里人气旺，求教个问题。
看到之前有人问三分数组的问题，我这个问题有些类似，不过不是要求一定三等分，而是
要求三分的尽量公平。
【 以下文字转载自 Programming 讨论区 】
发信人: addin (add+in), 信区: Programming
标 题: 请教算法： 三等分石子
发信站: BBS 未名空间站 (Sat Aug 17 21:49:31 2013, 美东)
请问一个算法问题，一堆石子，重量都是整数。把他们分成三堆，重量尽可能接近,
即重量最大的那堆和最小的那堆差值最小。请问这种问题怎么处理。如果扩展成分为n
堆呢？
我知道回溯肯定可以，动态规划行不行？
多谢。 |
|
s********u
发帖数: 1109 | 33 做了一下7.6，就是找经过点最多的直线。
答案给的比较复杂，是用一个 >的hashmap，在斜率匹配的情况
下，再去vector找匹配的line，而且感觉有bug，在匹配斜率的时候没有考虑斜率无穷
大的情况。
我想了一下C++的做法，比较直观的做法是建立 的hashtable,然后重载一下
预算符，当斜率差和截距差都小于eps = 0.0001的时候视作两条线是同一条线。
但是因为重载这一块不太熟，不知道写的对不对，请大牛们指点一下：
//Given a two-dimensional graph with points on it,find a line which passes
the most number of points.
class Line{
private:
double slope;
double intercept;
bool infinity_slope;
static double eps;
public:
... 阅读全帖 |
|
|
a**d
发帖数: 85 | 35 刚从加州面完回来，很郁闷。就想写写自己最近的求职过程吧，希望版上大牛能给
点指
导。先多谢了！
本人60名左右的工科学校CS本科。今年年初好不容易拿到亚马逊的intern，然后暑
假就是让我用ruby on rails，jquery写一个front end web UI让用户填一些参数，然后
call我的team的API得到一些数据显示在网页上。主要是前端，说实话不觉得很有趣。
刚去的时候不太了解内部的git，build啥的是怎么弄的，然后开始就问了mentor很多。
开始觉得mentor(三姐）没什么挺乐于帮助吧，后来接触多了感觉有时有点annoying，
记得我在网页上的‘submit’ button旁边加了个cancel button，然后她不同意非问我
为什么加，点完以后有啥用。我说这个cancel很常见啊，一般web form submit旁边都
会有，用户不想submit就cancel然后返回上一个页面。然后她非说没必要，那我说好吧
就去掉，无所谓。然后后来和manager见面发现她打小报告说我not have a backbone..
..无语，我说跟她解释半... 阅读全帖 |
|
s********x
发帖数: 914 | 36 这个完全可以进一步优化，每次的low可以设为在B中找的元素.而且A应该选length小的
那个数组。 |
|
A*********c
发帖数: 430 | 37 没写代码，但是YY了一下，你merge两个sorted array是不是能得到O(n)的算法？ |
|
s********x
发帖数: 914 | 38 那个要additional space，而且binary search 在一个数组小另一个数组大的情况下很
快很多 |
|
|
c*****e
发帖数: 67 | 40 “每次的low可以设为在B中找的元素”
请教这是什么意思。 |
|
s********x
发帖数: 914 | 41 我试着写了一下，没有测，有bug请告诉我
public static int minDiffBetweenTwoOrderedArrays(int[] a, int[] b) {
// validate(a, b);
if (a.length > b.length) {
return minDiffBetweenTwoOrderedArrays(b, a);
} // now a.length <= b.length
int minDiff = Integer.MAX_VALUE;
int low = 0, high = b.length - 1;
for (int i : a) {
if (minDiff == 0) {
return 0;
}
if (i < b[0]) {
// element in a is less than the first element in b
... 阅读全帖 |
|
x****g
发帖数: 1512 | 42 这个就是O（n+m）？
比较两个值，那个小move哪个？
A[i]<=A[i+1]
B[j]<=B[j+1]
如果 A[i]
如果A[i+1]
如果A[i+1]>B[j]， 在该移动策略下，无论A[i+1]>B[j+1]与否A[i+1]和B[j],B[j+1
]都会发生比较。
反之同理。
i=0;
j=0;
int smallest = INT_MAX;
while(i
{
int diff = abs(A[i]-B[j]);
smallest = min(diff,smallest);
if(smallest == 0)
{
return 0;
}
if(A[i]>B[j])
{
j++;
}
else
{
i++;
}
}
return smallest. |
|
c*****e
发帖数: 67 | 43 明白你的意思了。我的版本没有利用好A也是sorted这个特性。 |
|
c*****e
发帖数: 67 | 44 跟上面Algorithmic提到的方法一样，赞. 这个应该更高效。
+1 |
|
|
g*****g
发帖数: 212 | 46 A:abs(A[i]-B[j+1])
B:abs(A[i+1]-B[j])
A
j++
else
i++ |
|
s***5
发帖数: 2136 | 47 把P中字符的序号引入S，然后S就成为一个数组，计算的结果就是求每个数字偏离其排
序（按P的字符）后位置的差值总和。
A = acbcccd
B = accccdb -> {1,2,3,4,5,6,7}
A -> {1,2,7,3,4,5,6}
就将A数组使用bubble sort排序需要swap的次数 -> 4 |
|
s***5
发帖数: 2136 | 48 把P中字符的序号引入S，然后S就成为一个数组，计算的结果就是求每个数字偏离其排
序（按P的字符）后位置的差值总和。
A = acbcccd
B = accccdb -> {1,2,3,4,5,6,7}
A -> {1,2,7,3,4,5,6}
就将A数组使用bubble sort排序需要swap的次数 -> 4 |
|
g*****g
发帖数: 34805 | 49 这东西哪有那么复杂，现在在法轮功能挣300k的，到UPA能给个400-500k的 package，
其中一多半是 Option. 能以现价上市，差价就是多赚的。碰到Zynga缩水一半，碰到
Twitter翻倍。碰到 Square打水漂。方差值很大。
结果如何主要取决你的眼光。Late stage preipo flop的概率不大。但不只是钱的问题
，Start up你容易升管理层，能学到先
进技术，对日后的生涯有好处。
anytime
to
9 |
|
g*****g
发帖数: 34805 | 50 这东西哪有那么复杂，现在在法轮功能挣300k的，到UPA能给个400-500k的 package，
其中一多半是 Option. 能以现价上市，差价就是多赚的。碰到Zynga缩水一半，碰到
Twitter翻倍。碰到 Square打水漂。方差值很大。
结果如何主要取决你的眼光。Late stage preipo flop的概率不大。但不只是钱的问题
，Start up你容易升管理层，能学到先
进技术，对日后的生涯有好处。
anytime
to
9 |
|
