N******n
发帖数: 3003 | 1 标 题: 怎么找到一个similarity matrix里面的不同的submatrix with hi
发信站: BBS 未名空间站 (Fri Apr 4 16:31:50 2014, 美东)
A is a symmetric matrix measuring the pair similarity between each node:
the higher value, the more similar the pair is.
我们的matrix里面每个值都是相互之间的相似性，比如50个国家直接的相似性。
如果对他的横坐标和纵坐标做hierarchical clustering, 就把相似的值都聚在一起，
如果用hotmap plot, 就会有很多hot spot.
比如：
matrix A：
【
0 30 25 1 2 3
30 0 22 2 2 1
22 20 0 2 2 2
1 2 1 0 2 2
1 2 2 3 0 9
1 1 1 2 10 0
】
很显然上面的matrix里面有两个submatrix 代表不同的... 阅读全帖 |
|
c**********e
发帖数: 2007 | 2 Suppose we have a matrix x[M][N], all entries x[i][j]
are either 0 or 1.
Q1: Find the largest square submatrix with all entries 1.
Q2: Find the largest rectangular submatrix with all entrix 1. |
|
s****t
发帖数: 36 | 3 有两道最大submatrix的题，都在careercup里面的。不太懂。
1. Image you have a square matrix, where each cell is filled with
either black or white. Design an algorithm to find the maximum
subsquare such that all four borders are filled with black pixels.
2. Given an N*N matrix of positive and negative integers, write
code to find the sub-matrix with the largest possible sum?
有人解释一下啊。
Thanks。 |
|
c********t
发帖数: 5706 | 4 在int matrix上求最大submatrix sum。
我在想对一维arr, 求最大连续sum, 有linear解法。
为什么2D似乎只有O(N^3)的解法？ |
|
c***z
发帖数: 6348 | 5
非方阵的我也做出来了，可是还是没有用。从此以后我就没有信心了。。。
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 2x5 submatrix (row 0~4, col 2~3)
1000010
0000100
001010 |
|
c***z
发帖数: 6348 | 6 I worked out the rectangular algorithm. I feel that I like these problems,
but... I am too slow I think...
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is |
|
c***z
发帖数: 6348 | 7 I finally made it. Anyone care to check it up? :)
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programm |
|
c***z
发帖数: 6348 | 8 方阵的话用Dynamic Programming
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programming. Assume we are going |
|
x***y
发帖数: 633 | 9 Hi, I'm sorry I did not check out your approach carefully and I made a
little mistake in the above analysis. It's right there are at most logM+logN
division at most, but actually in each divide, it only decreases the # of
elements; but the totaly number of rows and cols are still the name.
Consider the worse case, that each division splits the matrix into one
subMatrix with one row and subMatrix with n-1 rows, where n is # of rows of
current Matrix. If this type of split is true for evry step, t... 阅读全帖 |
|
A***W
发帖数: 419 | 10 请定义你的"矩阵运算公式".
只用矩阵乘做不到,因为 rank(A)=2,rank(B)=4,而乘积的rank总是不大于个别矩阵的
rank.
如果可以用加的话,楼上的办法是最简单的.
如果可以用子矩阵,合并矩阵的话就很简单. 比如说用Mapple
B:=<|
4],[1,2])>>; |
|
c*******d
发帖数: 255 | 11 贴一下递归的程序:
#include
using namespace std;
void printspiral(char *a, int colsize, int m, int n, int x0, int y0)
{
// a is the matrix, colsize is its original column size
// m is #rows, n is #cols in the submatrix
// x0 and y0 are the offsets of the first element of the submatrix
// check if m and n are positive
if (m<=0 || n<=0) {
cout << "zero or negative dimensions" << endl;
return;
}
|
|
s****a
发帖数: 528 | 12 没有看那些网站，自己想出来的
用另外一个矩阵B表示原矩阵A，元素值B(i,j)是原矩阵位置到左上角子矩阵的1的数目。
那么判断A(i0,j0)->A(i1,j1) 是不是全一子矩阵就可以从 B(i1,j1)+B(i0,j0)-B(i1,
j0)-B(i0,j1)
得知 O(1)
From now on, we can do dynamic programming:
assume we found the maximum sub matrix for A(1,1) -> A(i,j),
we save the maximum submatrix which has the right-bottom corner at A(i,j_k),
and A(i_k,j), and maximum submatrix without limitation
go to A(i,j+1), A(i+1,j) |
|
f****4
发帖数: 1359 | 13 来自主题: JobHunting版 - 问个面试题 void printspiral(char *a, int colsize, int m, int n, int x0, int y0)
{
// a is the matrix, colsize is its original column size
// m is #rows, n is #cols in the submatrix
// x0 and y0 are the offsets of the first element of the submatrix
// check if m and n are positive
if (m<=0 || n<=0) {
cout << "zero or negative dimensions" << endl;
return;
}
int i;
if(m>=2&&n>=2) {
// print the outer circle
for(i=0; i<=n-2; i++)
cout << a[x0*c... 阅读全帖 |
|
g**e
发帖数: 6127 | 14 第二题
s(i,j) = sum of submatrix from (0,0), to (i, j).
then the sum of submatrix (a, b), (c,d) (suppose c>a, d>b) is:
sum = s(c,d) - s(c,b) - s(a,d) + s(a,b)
update操作，改变a[i,j]的同时更新s(i,j)
初始化需要的时间O(n^2)，之后的操作都是O(1)
有更好的方法吗？thanks
1- |
|
a********9
发帖数: 129 | 15 之前稍微收集了一下
glassdoor
===================
edit distance
level traverse tree(高频）
1) Calculate the square root of a double（高频）
2) Given n intervals [si, fi], find the maximum number of overlapping
intervals.
3) Print all the paths from root to every leaf in a binary tree.
4) Print the sum of all the numbers at every vertical level in a binary tree
5) Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum ?
6) Given 1 trillion messages ... 阅读全帖 |
|
l***i
发帖数: 1309 | 16 dp(m,n) = max_{i,j} dp(i,j) + row_word[j]
or dp(i,j) + col_word[i]
dp(i,j) is the max number of char can be used in matrix[0..i-1][0..j-1]
row_word[j] is max number of char can be used in some row to make one word
in submatrix[0..m-1][j..n-1]
col_word[i] is max number of char can be used in some col to make one word
in submatrix[i..m-1][0..n-1] |
|
h*****k
发帖数: 8 | 17 应该是submatrix所有元素的和，比如指定一个submatrix, 左上角是(1,1) 右下角是 (
2,3) sum = A(1,1) + A(1,2) + A(1,3) + A(2,1) + A(2,2) + A(2,3) |
|
j****s
发帖数: 156 | 18 竟然google不到。可能是因为太简单了。
什么是principle submatrix
什么是leading principle submatrix
多谢。 |
|
x********i
发帖数: 10 | 19 1. Iterate from the leftmost column (Column 1) to the rightmost column (
Column N);
2. For each column, find all the possible combinations for continuous rows
of False;
3. For each combination of row(s), expand towards right until a True is
reached. Record the size of this submatrix.
4. The maximum of all the recorded submatrix sizes is the answer
The time complexity is O(N^3) |
|
c***z
发帖数: 6348 | 20 Any subset or min subset? For any subset, just use the mother set.
For min subset, it is the min submatrix of a binary matrix with respect to:
1. row.sum >= M
2. col.sum >= N
I would try dynamic programming but I am brain dead to think about the
details now.
A heuristic is to move a 2Mx2N submatrix around to see if we get lucky. |
|
r**u
发帖数: 1567 | 21 2. check kadane's 2-D algorithm |
|
c***z
发帖数: 6348 | 22 Q1. Describe one of your projects.
Q2. Why the copy constructor pass by reference not by value?
I said I know the general difference between passing by reference (globe
copy) and value (local copy), but I don't know if it applies here.
He told me that if I pass by value and the value is an object of another
class, then there will be an infinite loop.
(I bombed this one I think.)
Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
I started with the naive approach (go along |
|
m****u
发帖数: 3915 | 23 第二题的意思是pass by value会调用 copy constructor吧
submatrix?
and |
|
b******n
发帖数: 823 | 24 (x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1) |
|
l******o
发帖数: 144 | 25 哦, 没看清题目, 原来要求的是方阵啊, 那就简单多了. 确实可以做到O(MN)
假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
(x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1) |
|
c***z
发帖数: 6348 | 26 What I finally arrive at before timed out was this:
if there is a 1 on a line or row, change that line or row to all 1;
for each blocks of 0s, min{height, width} is the dimension of the submatrix.
two passes on the matrix, O(MN). |
|
c*******d
发帖数: 255 | 27 0001
0001
0001
这样就全变成1了吧？
submatrix. |
|
I**********s
发帖数: 441 | 28 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
I**A
发帖数: 2345 | 29 N*N是个matrix
看过求array的最大subarray
木见过怎么求matrix的subarray，你是说submatrix maybe? |
|
x***y
发帖数: 633 | 30 find a submatrix with the largest sum, similarly to find a subarray with the
largest sum in an array... |
|
A*********r
发帖数: 564 | 31 看了一下pearls， 觉得之前讨论的那个DP公式还是对的，跟pearls的预处理有同样的
效果。。
Define m(k,i,j) to be the maximum sum submatrix ending with the line A[k,i..
j]. （k is the row number, i, j is the left and right column number)
then the DP formula is m(k,i,j)=max{ 0, m(k-1,i,j)+sum{A[k,i..j]}}
注意到 m(k,1,j)其实就是第k行中从左到第j列的所有和，跟预处理的效果一样。。
你的这个例子，得到的 m(1, i,j) m(2, i,j), m(3, i, j)分别为：
（只考虑i<=j的情况）
0 0 0
0 1
3
3 5 3
2 1
1
4 7 4
4 1
0
最大和是7, m(3,1,2)也就是以第3行，第一列到第二列为最下面一条边的矩形。通过
backtrack应该可以找到前面的。。 |
|
x****3
发帖数: 62 | 32 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
x****3
发帖数: 62 | 33 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
J*********n
发帖数: 370 | 34 http://blog.csdn.net/linulysses/article/details/5594141
这里有对largest rectangle under histogram, maximal subsequence和largest
submatrix几类问题的总结，大家可以看看。但是其中largest rectangle under
histogram的O(n)算法我不太理解其正确性。
比如我有这样一个histogram {2,10, 15, 7, 9, 8, 3}，按照其中的代码
i operation stack max u v
[] 0 0 0
1 push 2 [2] 0 0 0
2 push 10 ... 阅读全帖 |
|
S**I
发帖数: 15689 | 35 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 36 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
x*******5
发帖数: 152 | 37 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_... 阅读全帖 |
|
f**y
发帖数: 10 | 38 EE方向，毕业opt身份，找工作找了3，4个月，拿了两个onsite，都不幸失败，其中一
个Broadcom的在外tinglist排了快2个月。。比较郁闷。有没有好心人能够帮忙推荐下
工作的，mobile，wireless，dsp的system engineer,application engineer,test
engineer都行。internship也没有关系，volunteer的话。。。如果符合专业也是可以
的。没工作经验的fresh实在是容易被鄙视。。如果碰巧您知道机会的话请发站内信给
我，我会第一时间把简历发给您。谢谢！
另外搭车问个算法，前段时间面到的，9x9数独验证，我写了个hash验证各行各列和
submatrix的，interviewer说还有更优解，哪位大神知道的话麻烦说个算法思路。谢谢
了。。。大家节日快乐。 |
|
i*********7
发帖数: 348 | 39
我看了一下，觉得那个证明好像不太合理。事实上binary search可以每次排除掉四个
submatrix中的三个，但是那个证明里证明的是四个sub matrix里面只可以排除掉两个
。 |
|
i*********7
发帖数: 348 | 40 我这样比较，假设我的矩阵是长m宽n，那么我每次比较的对象，就是a[m][n/2]以及a[m
/2][n]，这样比较，你就可以每次都取到四分之一个submatrix. |
|
j******2
发帖数: 362 | 41 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
results?
但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
DP。
所以DP的特征究竟是什么？ |
|
l*****n
发帖数: 577 | 42 Give a square matrix with n x n cells. Each cell is either filled with a
black pixel or a white pixel. Design an algorithm to find the maximum
subsquare such that all four borders are filled with black pixels;
Note: it is not the same as the wellknown question for the max sub-matrix
with all filled 0/1.... so the DP equation does not apply here..
Any good approach better than brute force? |
|
|
p*****2
发帖数: 21240 | 44 你说的bruteforce是什么复杂度？ N^3? |
|
l*****a
发帖数: 14598 | 45 牛人不都是拿着18W的offer然后准备找25W的？ |
|
|
l*****n
发帖数: 577 | 47 二爷您还在这坐镇呢：） yes, this is LD
N^3 is the minimum I can think , with some auxiliary space. The most naive
brute force is actually N^4..
等待二爷高招 |
|
|
l*****a
发帖数: 559 | 49 Copied the answer from careercup150. I can hardly understand the algorithm
which claimed to have complexity O^2.
Assumption: Square is of size NxN.
This algorithm does the following:
1. Iterate through every (full) column from left to right.
2. At each (full) column (call this currentColumn), look at the subcolumns (
from biggest to smallest).
3. At each subcolumn, see if you can form a square with the subcolumn as the
left side. If so, update currentMaxSize and go to the next (full) column.
4.... 阅读全帖 |
|
|
