a**********s
发帖数: 588 | 1 Yes, I think:
Consider a 3D grid of combination (NxNxN), each node (i, j, k) stands for a
combination: the ith, jth and kth numbers (sorted from small to large).
You can essentially rule out 1/8 when you compare the required sum with that
of (n/2, n/2, n/2). So this step's complexity is actually O(lgN).
The total asymptotic cost is dominated by the sorting, which is O(NlgN).
up |
|
w********p
发帖数: 948 | 2 本来觉得我的算法在nlgn和n^2之间，没在意
看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
得懂
assuming T=16
list after sorted
1, 2, 3, 6, 7, 8, 9
1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the las |
|
w********p
发帖数: 948 | 3 我也见过这道题。我相信我的算法是nlgn, 但是有些细节不知道怎么写成sudocode |
|
H*M
发帖数: 1268 | 4 也是一个google题目
Input several pairs of numbers. The second number in the pair is larger than
the first one. You need to combine the intervals has overlap. eg:
Input: [1 3] [2 4] [5 6]
Output should be [1 4] [5 6]
Another eg: [-3 0] [8 9] [4 6] [1 3] [5 7]
output: [-3 0] [8 9] [1 3] [4 7]
Looking for a O(n) solution.
O(n)的办法没想出来,是o(nlgn)算法
连想加调试的时候花了差不多一小时。小错不断。苦死。
大家想想有没有什么好的O(n)办法吧。
另外我提醒大家，vector你要想erase好几个位置的元素的话，要注意shift.. |
|
w********p
发帖数: 948 | 5 额觉着类似greedy algorithm里schedule的题
先按第一个值排序（O(n) or O(nlgn))， 然后比较二个值得value ( O(n) )
不过一个小时写radix我觉得很牛乐。 |
|
H*M
发帖数: 1268 | 6 CLRS上是O(nlgn) ?
我怎么记得DP的啊,O(n^2) |
|
k***e
发帖数: 556 | 7 a) nlgn
b) n/e^2
c) $sum_i C_n^i (i/n)^k i$ |
|
H*M
发帖数: 1268 | 8 If there can be negative numbers in the array,can we do this:
sum all elements to the left, s[i] = sum of a[j], j=0...i
O(n) here
then sort the sum_array s, for each element in s, s[i], binary_search the v
alue GIVEN_SUM + s[i] to see if that element is in the sum_array s or not. I
f yes, we find it.
O(nlgn) |
|
H*M
发帖数: 1268 | 9 很简单，就是check 一个array里面有没有两个元素和为sum,
我用了两种方法，一个是sort之后，keep两个指针i,j一头一尾,相加如果小于sum就前移
，否则就后移。O(nlgn) time
另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个
主意点吧。O(n) with O(n) space
我写的代码如下。fail掉了。不知道为什么。
谁有什么很牛的算法更有效么？谢了。
bool checkIfTwoElementsSumToNum(vector v, int sum)
{
if(v.size() == 0)
return false;
sort(v.begin(), v.end());
unsigned i = 0,j = v.size() - 1;
while(i < j)
{
if(v[i] + v[j] == sum)
r |
|
f*****e
发帖数: 2992 | 10 二分法查找是不是应该有序?
如果排序后再查找,时间复杂度也是O(nlgn)吧? |
|
c*****o
发帖数: 178 | 11 被问到，要求不可以用extra space,但是没有复杂度限制，我就说quick sort O(nlgn)
.然后考官说你知道big O？你哪里学的？汗，对我这非cs的期待好低。。。。。。 |
|
k***e
发帖数: 556 | 12 range tree
i don't remember the exact name.
Computational Geometry Algorithms and Applications, chapter 10
nlgn preprocessing, O(lgn+matched#)
efficient
range
a |
|
m******9
发帖数: 968 | 13 先用scan的方法，比如用2 pointer都从A B的左端开始scan，将smaller numbers都
swap到A
中，然后再sort B，例如用heap sort， quick sort
整体上是O(nlgn)
rest
O(nlogn |
|
w***9
发帖数: 13 | 14 1. 这里提到过的bar组成的histogram求最大内切矩形
2. 一个问题有O(N^2)和O(NlgN)两个算法，哪些情况下我们该选N平方那个。不停问还
有什么理由没有，不知道是在期待什么理由还是想听你能说出多少。
3. 给一个字符串，比如aabbbccdeaaaee, 连续的部分要求删除重复的，返回abcdeae,
还要求记录删掉了多少个。后来发现面试官希望in place做，就是没必要多开个数组来
存之类的。
4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
阵，设计个方法来回答这个矩阵是否在这个库里。
5. 好像还有一个题，大概也是查找什么东西是不是在什么集合里之类的。确实不记得
了。
6. 问了简历里的一个project怎么做的
祝大家好运！ |
|
S**Y
发帖数: 136 | 15 1. 就是什么时候用O(n^2)的算法而不是用O(nlgn)的算法,比如用在数目少的时候会用i
nsertion sort,而不是用merge sort之类的?
2. 写个memmove function,这个谁能给个bug free的code,除了要考虑前后可能的overl
ap之外,还要考虑其他的么?谢谢 |
|
S**Y
发帖数: 136 | 16 我算了下,没觉得insertion sort n^2前的const比quick sort的nlgn前的const小啊 |
|
a******t
发帖数: 34 | 17 given an array of n elements, find if there is a subset of 3 elements sum up
to value T
with time complexity O(nlgn).
Given a M*N matrix A in which all the elements in a row and all the elements
in a column are strictly
increasing. Find a path from the smallest element (ie A[0][0]) to the
largest element (ie A[M-1][N-1])
such that the sum of the elements in the path is maximum. Time Complexity O(
m+n). Use efficient space. |
|
G**********s
发帖数: 70 | 18 1.版上讨论过，n^2 最佳了，nlgn不可能的
2.两边之和大于第三边，所以途径最多点的就是maximum把。 |
|
B*****t
发帖数: 335 | 19 1. O(nlgn) can be achieved by using FFT under some conditions. But generally
the best algorithm to find a subset of 3 elements sum up
to a given value T is O(n^2). The relationship is like radix sort vs quick
sort. But I doubt the interviewers from MS would ask such kind of questions.
2. I don't think there is such kind of algorithms with O(m+n) complexity. |
|
r********g
发帖数: 1351 | 20 我也觉得说“耗时”并不是说O(nlgn)的复杂度不够好，可能是，比如两次sort，然后
还有一对一的比较，如果字符串很长，这样就比较耗时，或者是这种情况必须完全sort
完了比较才能知道结果，可能有办法提前知道结果的，或者是不用具体比较数字的值，
只比较数字的多少就行了，虽然没有改变复杂度的量级，但还是应该节省了一点时间吧
；还有preprocessing阿，比如如果知道不一样的数字可能比较多，可以加起来mod一个
素数之类的... |
|
|
k***e
发帖数: 556 | 22 i did not say we can assure to get nlgn with this
i just mean we can improve the probability of getting better performance
btw, if you use linear selection algorithm, which is recursive solution, you
have to take take space used on the stack and you also need at least a n/5
size array to store the medians you obtained.
in |
|
a*u
发帖数: 97 | 23 又查了下，brute force就是n^2lgn, 但是现在有improved O（nlgn）算法，也有exact
bound n的算法了。恩
) |
|
a*u
发帖数: 97 | 24 是的啊，somewhat真是大牛，通读熟记了。
那里面讲是nlgn sort those suffix strings, 我看的应该是在O（n）出现之前的版本
。 |
|
K******g
发帖数: 1870 | 25 为什么这么复杂啊，我觉得很简单啊。
随便挑一个点为原点，然后求剩下的N-1个点与x轴的夹角，把所有的夹角排序，然后不
久找出在同一条直线上的点了吗？
N-1+NlgN |
|
a*u
发帖数: 97 | 26 又想一下，如果是non-negative的数组，应该用一个prefix sum array就够了，也是O(
nlgn)，也不用把题目转化再求解。
估计小尾羊这道题还是有正负，期待解答。
search? |
|
s***l
发帖数: 129 | 27 preprocess的话,RMQ可以保证O(nlgn).
.. |
|
l******o
发帖数: 144 | 28 他自己都说自己错了。
其实就是T(n,m)=T(n,m/3)+O(n)
所以T(n,n)=O(nlgn)
不是很了解你的意思
如果你是说T(n) = T(N/3) + O(N)
但是你的trivial case(N = 1， 只剩最后一列)的时候是O(N)的complexity，
如果trivial case不是constant time的，可以这样算么。？ |
|
l*********y
发帖数: 142 | 29 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
感觉这道题定义很清晰，但是只能想出O(n^2*lgn) 的brute force解法.
careercup上的讨论不清楚。谢谢。 |
|
K******g
发帖数: 1870 | 30 不明白，你这个算法怎么会是O（n^2)呢，明明就是O（n*nlgn) |
|
r****o
发帖数: 1950 | 31 找sum等于给定值的pair，复杂度O(n)，不是O(nlgn) |
|
x****r
发帖数: 99 | 32 你在找pair的时候是要用到hash map是吧？
我觉得O(NlgN）好难啊。 |
|
x****r
发帖数: 99 | 33 反正我觉得你的思路是很有道理的，不过因为数组不连续，所以实行起来很复杂，可能
需要在这种可能
跳过的情况下还是搜索两边，，这样可能就退化成O(N^2)了， 也有可能有更巧妙的方
法可以在nlgn找
到吧。 |
|
z****e
发帖数: 2024 | 34 我听说，正整数可以O(n) 排序，没找到详细资料。
我觉得如果不用hash，nlgn是不是最快了？ |
|
m*****g
发帖数: 226 | 35 don't quite understand this solution.
how about this.
for input array[0...n], asking for k (k<=n)
first sort array into sortedArray[0...n]
calculate the difference between adjacent elements, put them in a linked
list List diff;
next build a min heap of the nodes in the linked list
do n-k times
remove the min from the heap, combine with its adjacent elements in the
difference list, then update the min heap
end
this solution should give O(nlgn) time complexity
another thing, x[1] and x[n] not |
|
z*j
发帖数: 42 | 36 老大, 你真牛, 不过如果事先知道算法(最简单的divide and conquer + partition),
确实5
分钟就可以写完了, 如果是要tune 的, 那就麻烦了. 比如要保证worst case nlgn. 我
还真被问
到过.
多5分钟
搞 |
|
Z*****Z
发帖数: 723 | 37 Given a Data Structure having first n integers and next n chars. A = i1 i2 i
3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elemen
ts of the array ass A = i1 c1 i2 c2 ... in cn
O（nlgn)的算法我知道。有没有O（n)的算法？ |
|
x****r
发帖数: 99 | 38 请问一下nlgn怎么做呢？
i2 i
elemen |
|
x******3
发帖数: 245 | 39 能具体说说吗，我nlgn和O(n)的一个都不知道, 3q |
|
y*c
发帖数: 904 | 40 1. O(nlogn)
divide and conquer
abcd1234 -> ab12cd34 -> a1b2c3d4
T(n) = O(n) + 2T(n/2) -> O(nlgn)
2 O(n)
This is just like matrix transposition using O(1) space.
If we use row major, the absolute position for a[i][j] is i*n + j. After
transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
+ i' and so on. There is a paper on the proof. |
|
Z*****Z
发帖数: 723 | 41 Maximum Sum of Increasing Subsequence
Given an integer array, how will you find out the increasing subsequence whi
ch gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1) 23,30
2) 23,67
2) 50,67
3) 1,67
4) 1,30
5) 67
6) 30
but50, 67 gives the maximum sum. How to find it?
用DP，O（N）空间，O（N2）时间，是最优么？能不能像LIS那样优化成O（NlgN）？ |
|
|
j**l
发帖数: 2911 | 43 Wiki上有O(nlgn)的，方法很巧，主要是要用到二分查找来加速，关键是维护一个数组A
，A[i]保存的是长度为i的递增序列的末尾元素的最小值.
面试官估计很难相信是你当场想出来的。 |
|
Z*****Z
发帖数: 723 | 44 Young Tableau的情况可以用最小堆做到nlgn吗？
btw:数组可以转化到YT，但是YT不一定能转化回去吧？
C
小n |
|
P********l
发帖数: 452 | 45 来自主题: JobHunting版 - 狗狗面经~ 1. It is O(nlgn).
2. How about 7 cycles?
1234123L1234123L1234123L1234123L1234123L1234123L1234123L |
|
s********l
发帖数: 998 | 46 来自主题: JobHunting版 - 狗狗面经~ 对 我写错了
nlgn
lgn 不可能
反正我当时 能想出来的最好算法
就是先计算string长度
然后从长度1的开始 遇到不是重复就结束 //长度指的是pattern的长度
然后长度x 先用length%x 看length是不是这个长度的倍数
是就check不是就下一个长度 直到长度到length的一半
interviewer好像很高兴 这个就是他要的答案
兴高采烈的让我coding~ |
|
n*****0
发帖数: 133 | 47 来自主题: JobHunting版 - 狗狗面经~ 请问这个方法为什么是O(nlgn)的? |
|
s********l
发帖数: 998 | 48 来自主题: JobHunting版 - 狗狗面经~ 我当时 就只想出这个了~
interviewer好像就是要的这个
他管这叫nlgn。。。 |
|
s********l
发帖数: 998 | 49 来自主题: JobHunting版 - 狗狗面经~ interviewer管这个叫nlgn
我当时也觉得confused
不过 他满意 我就不argue了 呵呵 |
|
j**l
发帖数: 2911 | 50 结合我自己的经历还有别人的面经，最近MSFT, GOOG, AMZN等大公司的面试题似乎不再
那么难了，也就是基本上是版上反复讨论的经典中等难度题，而那些比较难的题目，比
如直方图下的最大矩形面积，最大全1子矩阵，最长递增子序列的NlgN解法，复制有
random指针的链表，几乎没有被考到。
但是就这样，offer也不容易拿到。因为对这些不难的题目，你要做的快，又要少bug，
还要能考虑到各种情况，代码要写的整洁简明健壮，还有些soft skills的考查。
每个准备面大公司的人，还是要把版上反反复复提到的中等难度以下的题目多做多写代
码多总结，这才能把握住最近时间这个题目本身难度降低的机遇。 |
|
