s*********d
发帖数: 2406 | 1 没什么好说的，还是自己不行。
第一题
abstract class absClass
{
public int AddTwoNumbers(int Num1, int Num2)
{
return Num1 + Num2;
}
public abstract int MultiplyTwoNumbers(int Num1, int Num2);
}
实例化 absclass
interviewer 说 不需要用考到任何算法知识。只考java。
answer ：
public class aaClass extends absClass {
public int MultiplyTwoNumbers(int Num1, int Num2){
int multiplyresult = 0 ;
multiplyresult=Num1*Num2;
return multiplyresult;
}
这个有什么问题？
Q2:经典题
Q2:
Given a sorted 2-D array (M x N) containing integers with the following
properties:
* All integers in any row are sorted left to right
* The first integer in any row is greater than the last integer in the
previous row
E.g.
1 3 5 7
10 11 16 20
23 30 34 50
我先说从last column search 再在row line search O（N+M);
interview说有better 方法。
我说可以用binary search。
他说combine both。 我就total lost了（我就没想出来怎么叫combine both）
死活想不出来 在m/2 n/2 开始binary search。
之后提出跟种方法。比如展开成1D 直接做binary search。得到否定答案。
说了用对角线 查找 也不是最优的。
interviewer 提示了说matrix 很大
谈论了半天不得要领。
直接先写程序，那时，心都凉了，紧张死了。后来连怎么算[][]size的搞错了。
哎。
肯定挂了。
讨论贴：
http://stackoverflow.com/questions/2457792/given-a-2d-array-sor
increasing-order-from-left-to-right-and-top-to-bottom
问个问题，在java 里2D是怎么放的？ 如果实际上是1D存储的话。是不是用1D更快。
在讨论贴了好像O（logn))并不是比(n+M)更快。
谢谢 | p*****2
发帖数: 21240 | | p*****2
发帖数: 21240 | 3 第二题两次binary search是不是就行了？ | w****x
发帖数: 2483 | 4
第二题他说combine both是不是指的是当M, N很大的时候， 开始用binary search, 当
范围缩小后再用linear scan，因为数量小的时候linear scan效率更高？ 不过放在这也没什么意
思， 毕竟不是像quick sort那样会产生很多小节点.
写程序不会叫你写二分的solution吧。。。
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| s*********d
发帖数: 2406 | 5 估计是了。这是个问题
public class aaClass extends absClass {
public long MultiplyTwoNumbers(int Num1, int Num2){
long multiplyresult = 0 ;
multiplyresult=Num1*Num2;
return multiplyresult;
} | y*******g
发帖数: 6599 | 6 你以前的答案是对的，这个错了。
【在 s*********d 的大作中提到】
: 估计是了。这是个问题
: public class aaClass extends absClass {
: public long MultiplyTwoNumbers(int Num1, int Num2){
: long multiplyresult = 0 ;
: multiplyresult=Num1*Num2;
:
: return multiplyresult;
: }
| p*****2
发帖数: 21240 | 7
为什么还需要linear scan呢？
【在 w****x 的大作中提到】
:
: 第二题他说combine both是不是指的是当M, N很大的时候， 开始用binary search, 当
: 范围缩小后再用linear scan，因为数量小的时候linear scan效率更高？ 不过放在这也没什么意
: 思， 毕竟不是像quick sort那样会产生很多小节点.
: 写程序不会叫你写二分的solution吧。。。
| s******n
发帖数: 3946 | 8 第一题太搞了吧，就是要用add实现multiply，他没提示你？？？
第二题就是M*N一维数组的binary search。复杂度log(M*N) | s*********d
发帖数: 2406 | 9 我问了他要不要实现，他说不要的！说这题就靠java 基本
【在 s******n 的大作中提到】
: 第一题太搞了吧，就是要用add实现multiply，他没提示你？？？
: 第二题就是M*N一维数组的binary search。复杂度log(M*N)
| w****x
发帖数: 2483 | 10
不知道面试官什么意思， 没太大必要用，比如quicksort当样本很小的时候用
insertsort是为了避免产生很多递归小节点， 这里就直接下来了没多大必要， 不知道
interviewer要什么结果， 可能interviewer随便说说的吧
【在 p*****2 的大作中提到】
:
: 为什么还需要linear scan呢？
| | | w****x
发帖数: 2483 | 11
为什么是一维数组？？
【在 s*********d 的大作中提到】
: 我问了他要不要实现，他说不要的！说这题就靠java 基本
| p*****2
发帖数: 21240 | 12
为什么一维数组？这个不是logN+logM的复杂度吗？这题L面过我，我就是用的logN+
logM的。
【在 s******n 的大作中提到】
: 第一题太搞了吧，就是要用add实现multiply，他没提示你？？？
: 第二题就是M*N一维数组的binary search。复杂度log(M*N)
| y**********u
发帖数: 6366 | 13 第一题难道不用二进制？？？
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| b******v
发帖数: 1493 | 14 log(mn)=log(m)+log(n)
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 为什么一维数组？这个不是logN+logM的复杂度吗？这题L面过我，我就是用的logN+
: logM的。
| p*****2
发帖数: 21240 | 15
我数学太差了。呵呵。
【在 b******v 的大作中提到】
: log(mn)=log(m)+log(n)
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
| p*****2
发帖数: 21240 | 16
这个比较靠谱。不然没什么好考察的。
【在 y**********u 的大作中提到】
: 第一题难道不用二进制？？？
| y*******g
发帖数: 6599 | | w****o
发帖数: 2260 | 18 第二题的2D Matrix 和这个网站上的数组不一样吧。你的这个数组更简单些。
http://stackoverflow.com/questions/2457792/given-a-2d-array-sor
这道题就做两次binary search就好了。先是最后一列，确定某行，然后在那行在做一
次BS.
http://stackoverflow.com/questions/2457792/given-a-2d-array-sor
的解法，本版过去有讨论过。
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| S******t
发帖数: 151 | 19 Java不懂，第一题就不讨论了
第二题我看了很久都不明白这和1D的binary search有任何区别
任意一个sorted array不都可以排成这样一个2d matrix么
没有任何附加信息啊，还是O(logM + logN)啊。。。
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| w****x
发帖数: 2483 | 20
你面试时候写的是binary search的code? 那得花多长时间啊
【在 p*****2 的大作中提到】
:
: 这个比较靠谱。不然没什么好考察的。
| | | a*******o
发帖数: 67 | 21 弱问一下L家是哪家？
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| p*****2
发帖数: 21240 | 22
好像code不长呀。不过那时候我太弱了，只是有个概念，code里有bug，但是还给我过
了。
【在 w****x 的大作中提到】
:
: 你面试时候写的是binary search的code? 那得花多长时间啊
| m***n
发帖数: 2154 | 23 在stackoverflow上看到一个算法。。不知道对不对
bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int
maxY)
if (minX == maxX and minY == maxY and arr[minX,minY] != value)
return false
if (arr[minX,minY] > value) return false; // Early exits if the value can't
be in
if (arr[maxX,maxY] < value) return false; // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
print nextX,nextY
return true
}
else if (arr[nextX,nextY] < value)
{
if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
return true
return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
return true
reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
} | s*********d
发帖数: 2406 | 24 我自己做出来了，主要是边界条件的问题。
public boolean bsearch2(int[][] p, int val, int xlo, int xhi, int ylo,
int yhi) {
if (xlo == xhi && ylo == yhi && (p[xlo][ylo] != val))
return false;
if (p[xlo][ylo] > val)
return false;
if (p[xhi][yhi] < val)
return false;// end conditon
int midi = (xlo + xhi) / 2;
int midj = (ylo + yhi) / 2;
//binary search
if (p[midi][midj] == val) {
System.out.println(midi);
System.out.println(midj);
return true;
} else if (p[midi][midj] < val) {
if (bsearch2(p, val, midi, midi, midj + 1, yhi)) {
return true;
} else
return bsearch2(p, val, midi + 1, xhi, ylo, yhi);
} else if (p[midi][midj] > val) {
if (bsearch2(p, val, midi, midi, ylo, midj-1)) {
return true;
} else
return bsearch2(p, val, xlo, midi - 1, ylo, yhi);
}
return false;
} | i**********e
发帖数: 1145 | 25 写了非递归的版本：
const int MAX_ROW = 512;
const int MAX_COL = 512;
int searchRow(int A[][MAX_COL], int m, int target) {
int L = 0, R = m-1;
while (L < R) {
int M = (L+R+1)/2;
if (target < A[M][0]) {
R = M-1;
} else {
L = M;
}
}
return (A[L][0] <= target) ? L : -1;
}
int searchCol(int A[][MAX_COL], int row, int n, int target) {
int L = 0, R = n-1;
while (L < R) {
int M = (L+R+1)/2;
if (target < A[row][M]) {
R = M-1;
} else {
L = M;
}
}
return (A[row][L] == target) ? L : -1;
}
bool search(int A[][MAX_COL], int m, int n, int target) {
int row = searchRow(A, m, target);
if (row == -1) return false;
int col = searchCol(A, row, n, target);
if (col == -1) return false;
return true;
} | w****x
发帖数: 2483 | 26
这个不对吧, 怎么一横一竖跑两遍就完了呢?? 我贴一个超长版的:
int _inner_search_row(int A[M][N], int nIterRow, int nIterCol, int nTg);
int _inner_search_col(int A[M][N], int nIterRow, int nIterCol, int nTg);
bool FindTarget2(int A[M][N], int nTg)
{
int nIterRow = 0;
int nIterCol = N-1;
while (nIterCol >= 0 && nIterRow < M && A[nIterRow][nIterCol] != nTg)
{
nIterRow = _inner_search_row(A, nIterRow, nIterCol, nTg);
nIterCol = _inner_search_col(A, nIterRow, nIterCol, nTg);
}
return nIterRow >= 0 && nIterRow < M;
}
int _inner_search_col(int A[M][N], int nIterRow, int nIterCol, int nTg)
{
if (nIterCol < 0 && nIterRow >= M)
return nIterCol;
int nBeg = 0;
int nEnd = nIterCol;
while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd)/2;
if (A[nIterRow][nMid] == nTg || (A[nIterRow][nMid] < nTg
&& (nMid == nIterCol || A[nIterRow][nMid+1] >= nTg)))
return nMid;
else if (A[nIterRow][nMid] < nTg)
nBeg = nMid + 1;
else nBeg = nMid - 1;
}
return -1;
}
int _inner_search_row(int A[M][N], int nIterRow, int nIterCol, int nTg)
{
if (nIterCol < 0 && nIterRow >= M)
return nIterRow;
int nBeg = nIterRow;
int nEnd = M-1;
while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd)/2;
if (A[nMid][nIterCol] == nTg || (A[nMid][nIterCol] > nTg
&& (nMid == 0 || A[nMid-1][nIterCol] <= nTg)))
return nMid;
else if (A[nMid][nIterCol] < nTg)
nBeg = nMid + 1;
else nBeg = nMid - 1;
}
return -1;
}
【在 i**********e 的大作中提到】
: 写了非递归的版本：
: const int MAX_ROW = 512;
: const int MAX_COL = 512;
: int searchRow(int A[][MAX_COL], int m, int target) {
: int L = 0, R = m-1;
: while (L < R) {
: int M = (L+R+1)/2;
: if (target < A[M][0]) {
: R = M-1;
: } else {
| q***y
发帖数: 236 | 27 弱问，第二题最优解不是Young tableau http://en.wikipedia.org/wiki/Young_tableau linear search吗，从左下角开始，复杂度 O(m+n)?
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| l*****a
发帖数: 14598 | 28 binary search一遍结束，你这个recursion cost有点大
int
't
【在 m***n 的大作中提到】
: 在stackoverflow上看到一个算法。。不知道对不对
: bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int
: maxY)
: if (minX == maxX and minY == maxY and arr[minX,minY] != value)
: return false
: if (arr[minX,minY] > value) return false; // Early exits if the value can't
: be in
: if (arr[maxX,maxY] < value) return false; // this subrange at all.
: int nextX = (minX + maxX) / 2
: int nextY = (minY + maxY) / 2
| l*****a
发帖数: 14598 | 29 第一题到底考什么？
为什么不是
return Num1*Num2;
如果说溢出的话，那个Add就不溢出了？
请牛人指点！！！
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| l*****a
发帖数: 14598 | 30 根据题意，实际上可以看成一个有序一维数组。一遍binary search will work
bool contains(int a[][],int index,int target)
{
int y=index%n;
int x=index/n;
return target==a[x][y];
}
bool Search(int a[][],int m,int n,int target)
{
int lo=0;
int hi=m*n-1;
int x,y;
while(lo
{
int mid=lo+(hi-lo)>>1;
if(contains(a,mid,target) return true;
if(target
else lo=mid;
}
if(contains(a,hi,target) return true;
if(contains(a,lo,target) return true;
return false;
} | | | p*****2
发帖数: 21240 | 31
chengdu说的，考察的是binary search。
【在 l*****a 的大作中提到】
: 第一题到底考什么？
: 为什么不是
: return Num1*Num2;
: 如果说溢出的话，那个Add就不溢出了？
: 请牛人指点！！！
| i**********e
发帖数: 1145 | 32 对所有行第一列进行 binary search，然后对那一行的所有列进行第二次的 binary
search.
先找出最大的一行的第一个值满足 <= target 条件，然后要找的target必定在那一行
的其中一列。如果不在的话，那就代表matrix没有那个值。
【在 w****x 的大作中提到】
:
: 这个不对吧, 怎么一横一竖跑两遍就完了呢?? 我贴一个超长版的:
: int _inner_search_row(int A[M][N], int nIterRow, int nIterCol, int nTg);
: int _inner_search_col(int A[M][N], int nIterRow, int nIterCol, int nTg);
: bool FindTarget2(int A[M][N], int nTg)
: {
: int nIterRow = 0;
: int nIterCol = N-1;
: while (nIterCol >= 0 && nIterRow < M && A[nIterRow][nIterCol] != nTg)
: {
| i**********e
发帖数: 1145 | 33 不是。
读清楚题意，这个是每一列的第一个值大于之前一行的最后一个值。
Young tableau 是某一列的值不小于之前一行同一列的值。
【在 q***y 的大作中提到】
: 弱问，第二题最优解不是Young tableau http://en.wikipedia.org/wiki/Young_tableau linear search吗，从左下角开始，复杂度 O(m+n)?
| l*********8
发帖数: 4642 | 34 没人回，我回一下吧：）
LinkedIn
【在 a*******o 的大作中提到】
: 弱问一下L家是哪家？
| w****x
发帖数: 2483 | 35
是吗? 我一直认为是不断的search, 下面这个matrix找左下角的7:
1 2 3 4
3 5 8 9
6 6 8 10
7 15 18 20
我的方法是 4->9 9->5 5->15, 15->7
你怎么一行一列找出来??
【在 i**********e 的大作中提到】
: 对所有行第一列进行 binary search，然后对那一行的所有列进行第二次的 binary
: search.
: 先找出最大的一行的第一个值满足 <= target 条件，然后要找的target必定在那一行
: 的其中一列。如果不在的话，那就代表matrix没有那个值。
| p*****2
发帖数: 21240 | 36
你这个例子不是这道题的吧？
【在 w****x 的大作中提到】
:
: 是吗? 我一直认为是不断的search, 下面这个matrix找左下角的7:
: 1 2 3 4
: 3 5 8 9
: 6 6 8 10
: 7 15 18 20
: 我的方法是 4->9 9->5 5->15, 15->7
: 你怎么一行一列找出来??
| y*******g
发帖数: 6599 | 37 我已经说过了，第一题没什么考点。。
http://www.mitbbs.com/article0/JobHunting/32088049_0.html
【在 l*****a 的大作中提到】
: 第一题到底考什么？
: 为什么不是
: return Num1*Num2;
: 如果说溢出的话，那个Add就不溢出了？
: 请牛人指点！！！
| w****x
发帖数: 2483 | 38
晕, 还以为是杨氏矩阵, 不好意思哈哈
【在 p*****2 的大作中提到】
:
: 你这个例子不是这道题的吧？
| d******a
发帖数: 238 | 39 写个简单的啊，O(lgn)时间，O(1)空间。
const int ROW = 100;
const int COLUMN = 50;
int get_value(int a[][COLUMN], int m, int n, int pos)
{
int row_pos = pos / n;
int col_pos = pos % n;
return a[row_pos][col_pos];
}
bool binary_search(int a[][COLUMN], int m, int n, int target)
{
int middle;
int start = 0;
int end = m * n - 1;
int middle_value;
while(start <= end)
{
middle = start + (end - start) / 2;
middle_value = get_value(a, m, n, middle);
if( target == middle_value)
return true;
else if(target < middle_value)
{
end = middle - 1;
}
else
{
start = middle + 1;
}
}
return false;
} | X*K
发帖数: 87 | 40 第一题如果不考虑溢出的话似乎也就是加一个可有可无的@Override了：
public class aaClass extends absClass {
@Override
public int MultiplyTwoNumbers(int Num1, int Num2) {
int multiplyresult = 0 ;
multiplyresult=Num1*Num2;
return multiplyresult;
}
【在 s*********d 的大作中提到】
: 没什么好说的，还是自己不行。
: 第一题
: abstract class absClass
: {
: public int AddTwoNumbers(int Num1, int Num2)
: {
: return Num1 + Num2;
: }
: public abstract int MultiplyTwoNumbers(int Num1, int Num2);
: }
| | | l*****a
发帖数: 14598 | 41 why not
return Num1*Num2?
【在 X*K 的大作中提到】
: 第一题如果不考虑溢出的话似乎也就是加一个可有可无的@Override了：
: public class aaClass extends absClass {
: @Override
: public int MultiplyTwoNumbers(int Num1, int Num2) {
: int multiplyresult = 0 ;
: multiplyresult=Num1*Num2;
:
: return multiplyresult;
: }
| w***y
发帖数: 6251 | 42 第一题什么意思？ 完全不明白在问什么。。。。。。。。。。 5555555555
第二题，就是mid =(low+high)/2, 从low = 0, high =m*n-1开始做binary search吧？
每次用/ %把 mid转化为矩阵里面的行、列值 |
|
