d********w
发帖数: 363 | 1 You are given an unsorted array A of n elements, now construct an array B
for which
B[i] = A[j] where j is the least number such that A[j] > A[i] and j>i
if such a j does not exist B[i] = -1
Eg:
A={1,3,5,7,6,4,8}
B = {3 5 7 8 8 8 -1} |
|
o*******y
发帖数: 115 | 2 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
版上找到的题 据说有time O(n), constant space的解
讨论一下哈 |
|
e********r
发帖数: 2352 | 3 bool array [] = {T, T, T, T, T, T, T, T, T, …}
unsorted int array
int array2 [] = {3, 1, 2, 0, -1, …}
for(int i = 0; i < array2.size(); i++)
{
if(array2[i] > 0)
array[array2[i]] = false;
}
for(int i = 0; i < array.size(); i++)
if(array[i])
return i;
刚想的答案，看一下符合你的要求吗. |
|
d**0
发帖数: 124 | 4 请教一个题目： k个unsorted arrays，假设都是n个元素。怎么样快速求出median？
不能把所有的array拼到一起再做quick selection。
我用类似quick selection的方法使用同一个pivot element在k个arrays里quick
select，再求
方法应该是这样，但是复杂度分析不出来。一个naive的bound是o(kn),但是这样就和拼
到一起做quick select一样。最后猜了一个o(nlogk)但是自己也不是很信服。
请大牛指教，谢谢！ |
|
d**0
发帖数: 124 | 5 这k个arrays是unsorted的啊 你的做法是认为他sorted吧
in
in
log( |
|
m********7
发帖数: 1368 | 6 和我这个很相似。。大牛写了多久？
List * inPlaceInsertionSort(List *head){
if(!head) throw(“empty list”);
// assume head is sorted, and unsort is unsorted
List *unsort = head->next;
while(unsort){
// take the front element from unsort
List *prev = NULL;
List *iter = head;
List *key = unsort;
// iterate within sorted list
while(iter){
if(iter->data < key->data){
prev = iter;
iter = iter->next;
}
... 阅读全帖 |
|
G******i
发帖数: 5226 | 7 ☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Sat Oct 29 00:10:37 2011, 美东) 提到:
**********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You ... 阅读全帖 |
|
l****i
发帖数: 2772 | 8 我前几天G的第一个电面，最后还有几分钟，老印就出了这题。5分钟没想出一遍扫出来
的算法，老印直接和我说，时间到了，就thank you把电话挂了。期间，面我的老印还
一直和边上一个女老印讲话，我都能听到。真想投诉丫的！但是G家和我联系的HR，也
全部是老印。无语了。
挂了电话，我想了想，大概思路是这样。
比如输入 1 3 2.....
做一个interval(start,end)的结构
读到1：（1，1）
读到3：（1，1）（3，3）
读到2： （1，2）（2，3）--》（1，3）
这样就有点像合并interval的那题了。
唉，老印太狠，G的hr和我说会用google doc，结果老印无视，说只需要电话交谈。每
次给我说一个题目，就耗费1-2分钟时间。
一共电面45分钟，首先扯了15分钟的毕业论文。然后问了一堆找数字和排序的问题。每
题都是关乎Big O的。
1. sorted的数组，找一个数
2. unsorted数组，找一个数。follow up，如果知道这个unsorted数组里，只有一个数
的位置是unsorted的，怎么找出来，怎么把这个数组变为sorted。
3. 知道哪... 阅读全帖 |
|
f******h
发帖数: 45 | 9 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
J***y
发帖数: 321 | 10 There are two different reasons for bookkeeping, one is for tax purposes,
and one is for actually knowing where you stand and if you are meeting the
goals and budgets you have set...in order to make changes, or do future
planning. This does not mean you keep two sets of bookkeeping records, it
just means you extract different information from them.
Some expenses involve taking cash out of your pocket, or checking account,
or get them deducted by ebay or PayPal...or you charged them.
Some expens... 阅读全帖 |
|
m******9
发帖数: 968 | 11 问题1： 2个超大file，memory容不下，都是unsorted，假设里面全是integer。如何找
出2个文件
中的重复部分？
我看到的一个答案是：
step 1: external merge sort F1 (file 1): 将原文件分成若干个temporary
smaller
files, 对每个temporary small file进行quicksort，然后对所有smaller files 进行
multiple-way merge sort, 重新合并成一个sorted big file.
step 2: traverse F2, binary search F2's each element in F1,
step 3: 能找则是common element，如果找不到则继续读取判断下一个element
问题2： 1个超级大文件，unsorted，里面都是string。如何找出所有的anagram？
这个题没什么思路
求教了，谢谢 |
|
d****g
发帖数: 33 | 12 bb最近是不是店面变难了。尽管我没有拿到offer，感觉当初的店面和Onsite都不难。
店面题： 在unsorted array中找第一个重复的数；在unsorted array中找第k大的数。
25匹马找前3快，3个mislabeled 的装水果的盒子，最少几次判断出哪个盒子装什么。
onsite: 简单的数据结构概念，stack,tree,hashtable,static variables, list,
exception handling,程序改错。见HM的时候，也是聊了很久。国人大哥很帮忙，印度
鬼子使坏。 |
|
f*********i
发帖数: 197 | 13 求一个unsorted数组中最长的等差数列（int 数组，可递增或者递减）
如果是求unsorted的最长递增或者递减串，那么是有一个nlogn的方法，加上等差这个
条件，估计要是n2了。
我在想是不是一开始可以用动态规划的方法，创建几个数组A和B，假设原始数组为C,那
么Ai是Ci左边第一个比Ci小的数，Bi是Ci又变第一个比Ci大的数，然后通过这两个辅助
函数查找。
好像到这里就卡住了，有没有高人给个解法我？ |
|
r******n
发帖数: 170 | 14 顶！！
同时请问楼主，这几题大致怎么答的：
4.find intersections of two sorted/unsorted arrays? what if the sorted
arrays follows uniform distribution?
假如是sorted, 两个指针遍历，优先移动小的那个，time: O(min(m,n)), space: O(1)
unsorted的话，建两个hashset，互相查一遍 time:O(max(m,n)), space:O(m+n)
uniform distributed是什么意思？对算法有影响吗？
5.data structure for arithmatic expression? What OOD principal should you
use? What design pattern to use if you need to add many functions to your
data structure?
拿stack去做？ 这个有什么部分要coding吗？ 这题写起来似乎会很麻烦。 OOD问这个
似乎也不好答。
... 阅读全帖 |
|
r******n
发帖数: 170 | 15 顶！！
同时请问楼主，这几题大致怎么答的：
4.find intersections of two sorted/unsorted arrays? what if the sorted
arrays follows uniform distribution?
假如是sorted, 两个指针遍历，优先移动小的那个，time: O(m+n)), space: O(1)
unsorted的话，建两个hashset，互相查一遍 time:O(m+n), space:O(m+n)
uniform distributed是什么意思？对算法有影响吗？
5.data structure for arithmatic expression? What OOD principal should you
use? What design pattern to use if you need to add many functions to your
data structure?
拿stack去做？ 这个有什么部分要coding吗？ 这题写起来似乎会很麻烦。 OOD问这个
似乎也不好答。
6. server... 阅读全帖 |
|
b********e
发帖数: 386 | 16 sort, link list, trees are great study cases for recursion.
For link list and trees, cuz these structures are defined recursively.
Sometimes, the recursive solution is more intuitive.
Only for linked list:
a few examples:
1: Get the length of the link list
2: Get the max/min value of linked list
3: Get the nth/last nth number of the list
4: Reverse linked list(There should be 2 recursive version, one with
carryover)
5: Sort linked list (this is hard)
6: Copy linked list
7: Delete a value in a so... 阅读全帖 |
|
y****i
发帖数: 312 | 17 A家东部分店。电面略去，ONSITE两轮，第一轮2X45分钟，第二轮3X45分钟。
第一轮1：和两位PRODUCT MANAGER聊天。设计一种算法来产生UUID。 设计一套OO系统
和算法来表示学校的选课系统。
第一轮2：和一位比较senior的印度人聊天。要求设计一套LOG分析系统。3个data
centers，20台机器。要求设计一套系统可以分析产生的LOG。
第二轮1：印度：find the kth smallest number in an unsorted array. 设计一个系
统能快速通过用户ID返回ADDRESS。
第二论2：印度：merge K unsorted arrays. K way merge, minimum heap.
第二轮3：尔罗斯： 设计OO系统来表示XML，层次分明打印XML。 |
|
m*****k
发帖数: 731 | 18 my bad, sorted is quicker than unsorted.
unsorted. |
|
t********o
发帖数: 10 | 19 来自主题: JobHunting版 - 多家的面经 具体哪些公司就不提了，反正就是版上的那些大公司，把能记住的电面onsite题就混在
一块儿了。
1. anagram
2. OO design: candy bar
3. sort color
4. 给一个小写的string，例如“abcd” 输出所有大小写混合的组合
5. string to double
6. given a string words, find the shortest substring including all the given
key words
7. what is little/big endian, how to tell if one machine is little or big
endian machine？
8. power set
9. smart pointer
10. given a set of weighted intervals, find the set non-overlap weighted
intervals that has the biggest weight
11. two sum变形
12. serialize... 阅读全帖 |
|
t********o
发帖数: 10 | 20 来自主题: JobHunting版 - 多家的面经 具体哪些公司就不提了，反正就是版上的那些大公司，把能记住的电面onsite题就混在
一块儿了。
1. anagram
2. OO design: candy bar
3. sort color
4. 给一个小写的string，例如“abcd” 输出所有大小写混合的组合
5. string to double
6. given a string words, find the shortest substring including all the given
key words
7. what is little/big endian, how to tell if one machine is little or big
endian machine？
8. power set
9. smart pointer
10. given a set of weighted intervals, find the set non-overlap weighted
intervals that has the biggest weight
11. two sum变形
12. serialize... 阅读全帖 |
|
W***o
发帖数: 6519 | 21 【 以下文字转载自 Programming 讨论区 】
发信人: Wardo (餐厅忙的时候客户端，否则服务端), 信区: Programming
标 题: 说一道关于unbalanced树的面试题
发信站: BBS 未名空间站 (Fri Oct 28 16:39:00 2016, 美东)
前两天面试一个公司，题目是用bfs在tree上找string，但是unbalanced tree.
可能有点先入为主的概念，我开始“默认”这是一个unbalanced binary search tree
，写代码到一半的时候，面试的人一再强调unbalanced tree，我当时也被他弄懵了。
写到最后，他说这是一个unsorted tree，我恍然大悟，原来开始他说的unbalanced
tree就是unsorted 的意思，我k，这能是同一个概念吗
我改代码完了之后，他又继续说：这tree里可能有cycle，也就是两个parent nodes可
能会共享一个儿子或孙子node，我k，真是烦。一个tree弄的这么复杂，面试的人真是
有点变态。不过话说回来也怪我一开始没跟他问清楚！最后面试完了想... 阅读全帖 |
|
W***o
发帖数: 6519 | 22 根据我后来的感觉，面试我的这个人主要是想让我用一个额外的空间数组来track
visited
nodes，这样就会避免cycle的问题。可是，在树上用bfs的时候谁用的着额外的空间数
组来track visited node啊？因为tree根本就不应该有cycle的。
所以，那个面试从一开始他说unbalanced，我就开始犯晕。用bfs还管是否unbalanced？
面试最后他说这是一个unsorted tree，我不得不把判断left/right的那几行去掉，反
正就是统统遍历一次好了。
总之奇葩的面试: unsorted 说成unbalanced；tree里还有tmd cycle |
|
W***o
发帖数: 6519 | 23 前两天面试一个公司，题目是用bfs在tree上找string，但是unbalanced tree.
可能有点先入为主的概念，我开始“默认”这是一个unbalanced binary search tree
，写代码到一半的时候，面试的人一再强调unbalanced tree，我当时也被他弄懵了。
写到最后，他说这是一个unsorted tree，我恍然大悟，原来开始他说的unbalanced
tree就是unsorted 的意思，我k，这能是同一个概念吗
我改代码完了之后，他又继续说：这tree里可能有cycle，也就是两个parent nodes可
能会共享一个儿子或孙子node，我k，真是烦。一个tree弄的这么复杂，面试的人真是
有点变态。不过话说回来也怪我一开始没跟他问清楚！最后面试完了想骂人 |
|
e***z
发帖数: 7126 | 24 要谈排名，首先要明白什么是排名
所谓排名，就是有一个set, 这个set 里面的elements 有可能是 not sort-able的,蛋
是因为有太多教育水平或者分析水平低下的听众/观众，理解不了 unsort-able but
different 这个复杂概念,所以就强行试图设定一个映射函数，去把这些elements简单
粗暴的project到另外一个 sort-able的 set（比如1-100的有理数）里面。用以彰显排
名人和观众的弱智和悲催 |
|
发帖数: 1 | 25 你要specify不同cases的不同outcome啊，既不是每回都需要8次，也不是每回都1次，
更不是每回都n^2。而且还要算出概率，需要8次的占多少比例，需要1次的占多少，需
要粗暴穷举的占多少。
这才能衡量出你算法的精确度啊，如果碰巧赶上已经sorted的（given ascending或者
descending）题目中也没这个限制性条件，那就更好办了，都是一次性，有手指头巴拉
巴拉就行了。
这是原题，上面没做任何限制，所以才是open talk，也就是sorted和unsorted的解法
你都得考虑到。
发信人: centralla (central LA), 信区: Military
标 题: 狗家面试题目
发信站: BBS 未名空间站 (Tue Apr 24 20:20:10 2018, 美东)
There are 25 horses. At a time only 5 horses can run in the single race. How
many minimum races are required in all cases to find the top 5 ... 阅读全帖 |
|
发帖数: 1 | 26 公式计算如下：
Given n=5, n^2=25 horses, n horses each group, k fastest horses
Ask: minimum number of races
k=3，n+2=7 races
k=4, <= n+2+1(or) races
k=5, <= n+2+1+1(or) races
答案是8 or 9 races, 针对given unsorted list 和 top 5 horses 的case |
|
发帖数: 1 | 27 题目没指出这个list是sorted还是unsorted，只是让你考虑all cases
据我所知，在斯坦福上课的时候，遇到这种问题，要求学生主动把各种可能性全部答出
来，绝非计算8次那么简单，而是你把全部的cases都涵盖了，这个想象力很考人的。 |
|
发帖数: 1 | 28 unsorted list，不同算法给出的minimum 结果不一样的，题目里没有限制使用哪种算
法，只是说all cases而已。
所以你要给出至少三套算法，第一套是所有算法中worst case最min的算法I，结果是多
少，第二套是所有算法中best case最min的算法II，第三套所有算法中是average case
最min的算法III。这三个算法得出的结论是不一样的。
虽然很多人都在计算，但我真不知道大家在算什么，属于哪个case里的。 |
|
发帖数: 1 | 29 5组排序的每组排序从unsorted 到sorted，各组需要多少次races？ 是一次吗？怎么得
来的？ |
|
w******i
发帖数: 1476 | 30 SAS Interview Questions from http://www.sconsig.com/
Very Basic
What SAS statements would you code to read an external raw data file to a DATA
step?
How do you read in the variables that you need?
Are you familiar with special input delimiters? How are they used?
If reading a variable length file with fixed input, how would you prevent SAS
from reading the next record if the last variable didn't have a value?
What is the difference between an informat and a format? Name three informats
or format... 阅读全帖 |
|
c**i
发帖数: 29 | 31 今天拿到offer, 我觉得给的挺低(接近80k),希望大家给点建议,如何neigotiable? MS最高能给多少 83k?
onsite题目:
1. find all pairs in an unsorted array which has a sum of Int k
2. list out all of the files contained in this directory and any
subdirectories.
3. print out the all the node in range (min, max) of a BST.
4. Deletion a node in BST.
5. how to design a good system in general.
6. finding the Nth element in Linklist(recursive and non-recursive)
7. Web pages have been linked thru each other, how to find a cycle?
8. given a stri |
|
M****d
发帖数: 20 | 32 三个问题
1. Given a linked list, unsorted, determine the middle point of it;
2. Find the deepest common ancestor of two leaves in a binary search tree;
Do not traverse from the leaves. Instead, locate the node top/down.
How about finding the shallowest common ancestor of two leaves?
3. Given constant incoming requests, each associated with a unique key,
estimate the total amount of unique requests within a period of time.
The number of keys explodes the memory. Do not touch the disk. Rou |
|
s******t
发帖数: 2374 | 33 我来写一下吧
第一个：
1. Given a linked list, unsorted, determine the middle point of it;
class Node {
Node next;
int value;
}
int getMiddle(Node root){
Node fast=root;
Node slow=root;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
} |
|
i******t
发帖数: 158 | 34 first phone interview:
why amazon
java hibernate
DOS, DDOS (security)
写SQL 一堆
写程序: given a unsorted integer array, find two number which sum is equal
to the given number. (integer may be negative)
second phone interview:
describe hardest problem you met
java里的 final, finally, finalize
java的static
如何判断给定的地址是big-endian还是little-endian?
写程序: count the number of 0 bit in a given string
写程序: x power of y
刚面完第二次phone interview, 太紧张, 答的不好
bless me~~~ |
|
T***3
发帖数: 274 | 35 周四飞机，晚上到。晚宴就是social，面SDE和SDET的人数大致相同。
周五面试： （现在好像都是只有4轮，每轮45分钟）
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celebrity。用O(n)时间找到此celebrity。
4. 给中序后续，构建树。
其他的每轮都问了简历。
感觉答的都不错，没什么难度。不知道为啥就被拒了。总之感觉很奇怪，不过也无所谓
了。
希望对大家有帮助。 |
|
m*****n
发帖数: 5245 | 36 ☆─────────────────────────────────────☆
Tmac3 (翠喜) 于 (Mon Nov 24 16:11:29 2008) 提到:
周四飞机，晚上到。晚宴就是social，面SDE和SDET的人数大致相同。
周五面试： （现在好像都是只有4轮，每轮45分钟）
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celebrity。用O(n)时间找到此celebrity。
4. 给中序后续，构建树。
其他的每轮都问了简历。
感觉答的都不错，没什么难度。不知道为啥就被拒了。总之感觉很 |
|
k*k
发帖数: 49 | 37 算法题。。。
two sorted arrays, A, B
look for 1) intersection, 2) A-B;
later change to unsorted linked list, do the same thing...
they may spent significant amount of time on your thesis work.....
good luck :) |
|
H*****L
发帖数: 5705 | 38 2) A-B 是指 all elements in A but not in B?
sorted的话可以用两个指针比较着走那个方法吧
unsorted的话也可以用同样的，除此之外除了hash还有什么好方法么? |
|
i********r
发帖数: 12113 | 39 一个unsorted数组包含n个int值, 需要分成m段(m
中最大值最小. 能否找到mlog(n)
的算法? |
|
n******r
发帖数: 1247 | 40 来自主题: JobHunting版 - 也来说道题 sorry，I mean 1-N，unsorted
原题里改了 |
|
H*M
发帖数: 1268 | 41 感觉这题不太容易
就是一个unsorted array,求出所有consecutive sub array和为sum都不trivial
valu |
|
g*******y
发帖数: 1930 | 42 我想了一下，简单的改改好像不照
因为：
1.我们需要数组是sort的，这样对于重复的一串字母，可以只选第一个
2.swap后，数组变成unsorted了
解决方案，不用数组，该用链表
在那个for循环里面：
原来把a[i]和a[start] swap的操作，
简单的改为把a[i]从链表中提出来放到start之前的位置
然后递归
递归完了后，再把a[i]放回原来的位置
这样实现起来稍微复杂一点点，不过就可以work了，而且输出的顺序也是按照123 132
213 231 312 321这样是有序的
另外指出一个这个code里面的问题：
if(start != i && str[i]==str[start])
continue;//eliminate duplicates
要改成
if(start != i && str[i]==str[i-1])
continue;//eliminate duplicates |
|
m******9
发帖数: 968 | 43 不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celebrity。用O(n)时间找到此celebrity。
4. 给中序后续，构建树。
其他的每轮都问了简历。
感觉答的都不错，没什么难度。不知道为啥就被拒了。总之感觉很奇怪，不过也无所谓
了。
希望对大家有帮助。
Pasted from <http://www.mitbbs.com/article_ |
|
a********3
发帖数: 228 | 44 对方是印度人，俺在电话里听印度英语还是有那么点困难，有两个问题让人家重复了几次，不知道会不会减印象分。。。
1. Given an image and a query rectangle, calculate the average intensity within the rectangle. (coding)
If we have one millions of queries in one minute, how can we do the queries faster and use less space?
他push了我三次想不同优化的方法。第一次我想了一个减少时间的算法。第二次我说用cache，他问我要多大的cache，这方面我开始算错了，在他提示下重新计算。第三次他提示我有只占O(N^2)空间的cache，问我怎么实现。
2. To find a minimum number in an unsorted array, we need to compare min with each number and update min if necessary. Calculat |
|
j*****u
发帖数: 1133 | 45 thanks for sharing!
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我觉得这个题没什么意义，除非这个file是存储在distributed FS，有replica。因为
如果在单机上，要distribute要首先split这个file，这就已经是一次读写了，读写中
还有一个是remote的。有这一次读写去重已经完成了。
如果是unsorted并且bitmap不能fit到single memory，这时并行才有意义。 |
|
x***n
发帖数: 464 | 46 嗯，应该是的。Google了一下，这个题有变种。比如如果原来的数列是unsorted，de-dup后还需保
持元素在数列中原来的顺序。此外，如果不许用额外的storage等。 |
|
c***g
发帖数: 472 | 47 一个unsorted的array, 包含1 - n的没有重复的整数
如果已经知道有n-1个, 只有一个missing, 怎么做, 这个加起来和xor就行了
如果已经知道只有n-2个, 只有两个missing, 怎么做, 1 到 n加起来, 算差, 1 到n的
平方, 加起来, 算差, 然后解方程.
这中间有人提到1到n的平方算和的时候会有overflow的问题, 怎么解决? 可以不可以
先算i的平方, 然后减去array[i]的平方, i从1到n求和, 这样就没有overflow了吧
如果已经知道有n-3个, 只有三个missing, 怎么做, 还是这样求三次方的和了再解方程
么?
还有别的办法么? |
|
l******o
发帖数: 144 | 48 比如n个数unsorted，有n！种可能，难道find a target value需要
log(n!)=nlogn的时间么？显然O(n)就可以了。
n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
法硬套在这里。
n^2 numbers put in n rows, each row sorted,
you have altogether (n^2)!/[(n!)^n] possibilities,
is it Log >= nlogn ??? I think Sterling's formula
should easily confirm this? |
|
h**k
发帖数: 3368 | 49 求the first k largest elements in a unsorted array.
如果k很小，比如3，n很大，比如100000，用什么算法最好？
如果k很大，接近n，用什么算法好？
进一步问如何求前 k1至 k2个最大元素（k1
如果有duplicate value在数组中，你的算法还可以么？
将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-( |
|
l*****a
发帖数: 14598 | 50 for unsorted array,how do you know which should be discarded
and which should be kept |
|
