|
c*****a
发帖数: 808 | 2 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
public static int numOfSwap(int[]ar){
List unorder = new ArrayList();
for(int i =0;i
if(i+1ar[i+1])
unorder.add(ar[i]);
}
Collections.sort(unorder);
int biggestUnorder = unorder.get(unorder.size()-1);
if(biggestUnorder > ar[ar.length-1])
return biggestUnorder - ar[ar.length-1];
int smallestUnorder ... 阅读全帖 |
|
c*****a
发帖数: 808 | 3 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
public static int numOfSwap(int[]ar){
List unorder = new ArrayList();
for(int i =0;i
if(i+1ar[i+1])
unorder.add(ar[i]);
}
Collections.sort(unorder);
int biggestUnorder = unorder.get(unorder.size()-1);
if(biggestUnorder > ar[ar.length-1])
return biggestUnorder - ar[ar.length-1];
int smallestUnorder ... 阅读全帖 |
|
d****n
发帖数: 12461 | 4 例如len(P)=4
可以认为目标P就是1,2,3,4
原始S例如1,4,3,2
先考虑non-circular情形。计算所有的unordered pairs。例如上面(4,3),(4,2),(3,2)
就是。操作1只可以让unordered pairs增加或者减少1。所以最小操作就是unordered
pairs数目。
1432->1342->1324->1234
对于circular的情形，操作2可以让位置0的unordered pairs从k变成n-1-k。如果位置0
的数是i，那么就有i-1个unordered pairs，所以这个操作把i移到末尾以后关于i的
unordered pairs就变成了n-i。对于队尾的j，从n-j变成了j-1。i,j之间的交换只能算
一次，所以整体减少是2(i-j-1)+(i>j?)，在i=j+1时等于1。
4321->1324->1234
对于中间的数，往前还是往后移动，这个再仔细计算一下。
edit |
|
d****n
发帖数: 12461 | 5 例如len(P)=4
可以认为目标P就是1,2,3,4
原始S例如1,4,3,2
先考虑non-circular情形。计算所有的unordered pairs。例如上面(4,3),(4,2),(3,2)
就是。操作1只可以让unordered pairs增加或者减少1。所以最小操作就是unordered
pairs数目。
1432->1342->1324->1234
对于circular的情形，操作2可以让位置0的unordered pairs从k变成n-1-k。如果位置0
的数是i，那么就有i-1个unordered pairs，所以这个操作把i移到末尾以后关于i的
unordered pairs就变成了n-i。对于队尾的j，从n-j变成了j-1。i,j之间的交换只能算
一次，所以整体减少是2(i-j-1)+(i>j?)，在i=j+1时等于1。
4321->1324->1234
对于中间的数，往前还是往后移动，这个再仔细计算一下。
edit |
|
f********x
发帖数: 99 | 6 The world beyond batch: Streaming 101: A high-level tour of modern data-
processing concept
http://radar.oreilly.com/2015/08/the-world-beyond-batch-streami
by Tyler Akidau August 5, 2015
Editor’s note: This is the first post in a two-part series about the
evolution of data processing, with a focus on streaming systems, unbounded
data sets, and the future of big data.
Streaming data processing is a big deal in big data these days, and for good
reasons. Amongst them:
Businesses crave ever more tim... 阅读全帖 |
|
c*****e
发帖数: 38 | 7 oh, for this, actually linear is the lower bound.
the proof is a reduction to search an element in an unordered array.
observe that one diagonal is unordered.
if you could do this in less than linear, you would be able to search an
element in unordered array in linear. |
|
c*****e
发帖数: 38 | 8 oh, for this, actually linear is the lower bound.
the proof is a reduction to search an element in an unordered array.
observe that one diagonal is unordered.
if you could do this in less than linear, you would be able to search an
element in unordered array in linear. |
|
D**f
发帖数: 439 | 9 unordered_map 可以保证顺序的，这就是为什么叫unordered，其实也就是hash，我已
经测试过了，至于vector>,当然也行，但当时心急，加上刚做过一个unordered
_map的题目，顺手就写了。
的确，输入count为0或者负数，其实没有意义。
最郁闷的是他解释了半天我也没明白要干嘛，后来他在google Doc上给出一个例子，我
才明白。 |
|
k****i
发帖数: 347 | 10 如果我没算错的话，呵呵，0-1的uniform distribution,x1
monotonic的概率就是1/3
所以楼上应该是对的。binomial distribution,不过expectation是N/9
好奇的是，你这个unordered scores是怎么定义的？把数据shuffle一遍还算是
unordered scores么？在这个shuffle后的test statistic你们care不？ |
|
M******8
发帖数: 22 | 11
这个unordered scores他也没给详细解释什么意思。不过我觉得，这里他说unordered
是在分group的时候不用重新order那个N scores sample。只要按照给出的顺序分成
triples就成了～～
所以是不是要考虑the total permutaion of the sample?
为啥expectation是N/9呢？ |
|
c*********d
发帖数: 9770 | 12 https://www.quora.com/Why-dont-the-Chinese-royal-family-reclaim-power
Penny Peng
Penny Peng
Updated Mar 7
In Qing Dynasty, my mom’s famliy was quiet a powerful manchu noble family
in my hometown. They owned a lot of lands (which are now all in the central
downtown) in my hometown, and had an official title of 清二品 (the third
highest rank in Qing Dynasty).
Nobody in my mom’s family complains about the present life.
My grandparents and all other people of their generation experienced the
horror of ... 阅读全帖 |
|
|
v*****u
发帖数: 406 | 14 来自主题: JobHunting版 - 一道算法题 三个unorder array merge
求思路啊
我觉得用merge sort，先merge两，再merge两。
？？？ |
|
|
|
j********r
发帖数: 453 | 17 two unordered array, one long,n , one short, m, sort them into a large array
. Someone say that we can sort the short array, it's mlogm, and binary
search and insert the long, the total is nlogm. but i am not clear about the
insert part, how it can be nlogm.
If there is a better algorithm, please share.
Thank for helps. |
|
w****o
发帖数: 2260 | 18 大概知道hash, hashtable的概念，主要是为了快速的lookup。
可是如果面试的时候被问到hash, hashtable,通常他们要考核的是什么？是要实现一个
好的hash fuction呢？还是要实现一个hashtable的class?
平时自己写代码的时候如果要用到一个hashtable,是不是可以用C++ STL tr1/
hashtable来当做一个hashtable?
看了下面的链接，说是C++新的标准定义了四类hashtable,分别叫 unordered_set,
unordered_map, unordered_multiset, unordered_multimap.这些是通常意义上的
hashtale吗？
http://en.wikipedia.org/wiki/C%2B%2B0x
这个链接还说hashtables 是 unordered associative containers。我觉得
associative containers都是 (key, value)这样的。可是通常的简单的hashtable，也
就只有key,没有value, 不是ass... 阅读全帖 |
|
h****e
发帖数: 928 | 19 你得说明是unordered map，写代码的时候你可以说明一下简写成
umap之类的。有的人对map和hash的区别看得很重的。 |
|
c****m
发帖数: 11 | 20 看不明白第二个题目...
既然list是unorder的，那就用sequence里面的元素从list里面一个一个找呗？不可以
么？
them? |
|
p****3
发帖数: 448 | 21 但我还是没给出欧嗯的答案
unordered array of size N, already know more than half of the elements are
number x (duplicate). the rest of the array is unknown.
find the number x efficiently (that means O(N)) |
|
a*******y
发帖数: 1040 | 22 No, set is a binary tree which is O(logn),就用unordered——map好了 |
|
|
a**********3
发帖数: 64 | 24 为啥in fact, the cost is O(n), 不是O(nlogn)? |
|
f*****e
发帖数: 2992 | 25 因为只是partially sorted。siblings无法判断谁大谁小。 |
|
a**********3
发帖数: 64 | 26 还是不太懂，bubbleDown cost O(logn), n 次 bubbleDown不是O(nlogn)么？ |
|
M********n
发帖数: 34 | 27 每次递归heapify的时候， 比较的是半个partition的一半，
累加起来， 就不是nlgn， 而正好是O（n）。
youtube的mit课程里有10分钟专门讲这个。 |
|
|
j******2
发帖数: 362 | 29 最底层有n/2个节点，它们的比较次数是0
倒数第二层有n/4个节点，它们的比较次数是1
倒数第三层有n/8个节点，它们的比较次数是2
...
最后一层有1个节点，比较次数是log(n)-1
所以总的复杂度是:
(n/4)*1+(n/8)*2+(n/16)*3+...+1*(log(n)-1)
=n*(1/4+2/8+3/16+...)
括号里这个序列(i-1)/(2^i)是个收敛数列，其和在i->无穷时都是常数。所以一小段的
和更是常数。所以上面的式子
＝n*c |
|
|
t****t
发帖数: 387 | 31 boost
unordered map不同平台上可能不同 |
|
b****p
发帖数: 216 | 32 今天在careercup上看到一个题目。Given an unordered array of positive integers
, create an algorithm that makes sure no group of integers of size bigger
than M have the same integers.
想到的死办法就是统计每个数字的个数之后放到一个heap里面去，每次取最大的一个，
要是连续取了M次了，就取第二大的。每次可以比较一下剩下的最大数目的数字k和所有
剩下来的元素n。 如果k比 n/(M+1)*M大的话就直接fail..
不知道还有什么好办法没有 |
|
m*********a
发帖数: 3299 | 33 这种新加的东西，老方法也可以用的，自己用不用看自己的
但是如果要维护别人的东西，别人用的话，自己化点儿时间看一下就行了。
C++11 unordered map 和set还是有用的，实现从red-black tree 的o(lg(n))到hash
table的o(1)。如果不要排序的话，还是很好的选择
forward list, array 这种container可有可无。
unique point还没有用过，无所谓
lambda function可以直接在fucntion中写inline function也比较方便
不用写一个 globe 的template function了，特别是只用一次的情况下
auto看着不舒服，写着爽，但是我宁可看长长的data type，
如果 abuse auto的话，看的人就要操你妈了
质。 |
|
s******d
发帖数: 9806 | 34 hashtable is unordered, how do you come up with the twoSum then?
why you need appear times btw? |
|
m********8
发帖数: 36 | 35 unordered没关系吧， 我们只需要返回找到没有。
appear times 是可能一个数字用两次。 比如 2+2=4， 如果不记录次数的话判断不出
。 但可能用一个boolean作为flag也能记录， 剩点空间？
大牛们能不能帮忙看看这样行不？ 谢谢！
我用c++写的。
struct TwoSum {
/**
* Stores @param input in an internal data structure.
*/
public:
void store(int input){
map[input]++;
}
/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 ... 阅读全帖 |
|
r*******e
发帖数: 971 | 36 哥们，你这个算法有问题啊。
1 为啥用map不用unordered_map? map 是棵树啊，后一个才是hashMap。不过这个其实
无所谓。
2. a=(points[j].y-points[i].y)/(points[j].x-points[j].x);
结果不是整数啊，会被强制取整的啊，这样不好。
下一行也是。
3. x 是个Point啊，我记得map活着unordered——map 对［］的重载只有在x是
primitive type才行。 |
|
|
s**x
发帖数: 7506 | 38
对，算法是关键，语言没人扣细节。queue, map, unordered map, priority queue,
set 这些常用的，当然要知道。
用C的，上C十十很快。 |
|
s**x
发帖数: 7506 | 39
基本不会。c++11 要知道一些，lambda, move.
不知道也无所谓。现在FLG没人考你语言，unordered set，priority queue, vector
主要container class 必须会用才行，这些很容易考到。也𣎴用太多，基本的
插入，查询就可以了。
有人喜欢考iterator, 这个也要憧一些。然后熟悉几个design pattern, 就主攻算法就
行。 |
|
发帖数: 1 | 40
謝謝雨薇的建議！現在bar真的好高。。。
我現在遇到小公司phone screen interview要我現場debug他們給的一個Android
project，(花了比較多時間在setup project，雖然最後bug都解決，但是過幾天還是掰
掰。。)
另外一間小公司phone interview剩不到10分鐘要我 implement DFS on a unordered
binary tree in post order without recursive，(這不刷題有可能過嗎？) -> 在此
默默反駁有些人說女生面試簡單。。 |
|
q****g
发帖数: 12 | 41 Thanks!I've also found the reason from the website,
order by在select into 或者insert里面都是没用/unpredictable的:
Tables do not have an order. In other words, tables by definition are
logically an unordered set of rows. Using ORDER BY in a INSERT...SELECT or
SELECT...INTO does not mean that the data in the table is 'ordered'. The
order of rows which you see when you do a SELECT without an ORDER BY clause
is a undefined/arbitrary order chosen by the optimizer based on the physical
characteristics, indexes, |
|
w*******e
发帖数: 285 | 42 对同样的data set进行clustering，假设一个用kmean，另外一个用其他方法，都生成
相同数目的clusters，比如说5个。那么怎么比较它们之间的距离？有没有什么标准的
做法？要是用hierarchy clustering生成两颗unordered tree，那么有什么标准的
metric可以比较着两棵树之间的距离呢？ |
|
s*****c
发帖数: 36 | 43 Hi,composite:
As for user defined data type support of Cast, I think it
depends on the specified DBMS.
"Multiset" is unrelated with "Cast". It's not a function,
but a concept. It is the definition of multiset: An
unordered collection of objects that are not necessarily
distinct. The collection may be empty.
Because SQL allows duplicate rows in a table, or applied
aggregate funcitons may result in duplicate rows, by
default,
SQL treats a table generated by select or group by as a
mutliset rather |
|
q****g
发帖数: 12 | 44 Thanks!I've also found the reason from the website,
order by在select into 或者insert里面都是没用/unpredictable的:
Tables do not have an order. In other words, tables by definition are
logically an unordered set of rows. Using ORDER BY in a INSERT...SELECT or
SELECT...INTO does not mean that the data in the table is 'ordered'. The
order of rows which you see when you do a SELECT without an ORDER BY clause
is a undefined/arbitrary order chosen by the optimizer based on the physical
characteristics, indexes, |
|
c*****e
发帖数: 11 | 45 refer to boost library any, then, just try to use a unordered container with
any, passing this container.
otherwise, you can try to design a general type class, which encapulate all
the data type you wish to use, then, pass a dict or map, you can also make
it.
法吗？ |
|
c*********n
发帖数: 96 | 46 ordered products:
a[0]*b[0]
a[1]*b[0], a[0]*b[1]
a[1]*b[1]
a[1]*b[2],a[2]*b[1]
...
where ',' means unordered. return as soon as you get enough products that
covers the number of products you need. Then, in the last/ least group,
perform whatever sort that's fast. You are all set! |
|
H*M
发帖数: 1268 | 47 I just saw this problem in a forum..not sure..
my guess is: it is not possible if the points are totall unordered...
so how will u do the pre-processing? |
|
w****o
发帖数: 2260 | 48 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 弱弱的问问hash, hashtable?
发信站: BBS 未名空间站 (Wed Mar 7 22:13:29 2012, 美东)
大概知道hash, hashtable的概念，主要是为了快速的lookup。
可是如果面试的时候被问到hash, hashtable,通常他们要考核的是什么？是要实现一个
好的hash fuction呢？还是要实现一个hashtable的class?
平时自己写代码的时候如果要用到一个hashtable,是不是可以用C++ STL tr1/
hashtable来当做一个hashtable?
看了下面的链接，说是C++新的标准定义了四类hashtable,分别叫 unordered_set,
unordered_map, unordered_multiset, unordered_multimap.这些是通常意义上的
hashtale吗？
http://en.wikipedia.org/wiki/C%2B%2B0x
这个... 阅读全帖 |
|
t****t
发帖数: 6806 | 49 it's not good but acceptable.
key.
works. |
|
r*********r
发帖数: 3195 | 50 why not use the provided hash function?
when two different objects have the same hash value, they just go
into the same bucket in the separate chaining scheme, no big deal. |
|
