i*******n
发帖数: 114 | 1 昨天签了offer，今天收到HR回复。
下周开始工作。
历经2个月的找工经历就此告一段落。
在这几天我会陆续分享我在湾区几个大公司的onsite面经。
在这版上潜水半年，收获颇多。
背景：
本人CS MS专业，裸奔湾区找工作2个月。 |
P**l
发帖数: 3722 | |
i*******n
发帖数: 114 | 3 nvidia interview experience
location:
NVIDIA
San Thomas Expressway, Santa Clara
duration
2 hours, 1PM to 3PM
2 interviewers, each for 1 hour
------------------------------------------
cdj
xor eax, edx
sub eax, edx
问我这段代码干嘛。就是算负数的补码(Two's Complement)，正数没变化
logic puzzle,
4 fuses, each fuse burns out in 40 minutes, create a fuse that can burn
in
20 minutes. slightly flawed problem. Because when you burn the fuse from
two
ends, it is not exactly 20 minutes. (Two combustion points are
certainly
faster than one.)
1 runtime analysis problem for the Scale heavier object identification.
You
have 8 objects that look identical to each other but 1 of the object is
heavier than the others. Please design an algorithm to pick out the
heavier
object.
You can always split the 8 objects into two groups and recursively split
the
heavier group into 2 groups until 1 object is left out. That object is
the
heavier one. However, that algorithm will require log2n time.
Better approach is you split the 8 objects into three groups and
recursively
split the one containing the heavier object(if the two groups on the
scale
are of the same weight, the heavier one must be in the third group.
Otherwise, the heavier one is in the heavier group on the scale.) into
another 3 groups until 1 object is left out. That object is the heavier
one.
That algorithm will require log3n time.
2nd interviewer asked about my research which I talked about for 20 mins
and
asked me about a programming question.(write the code to implement
binary
search algorithm.)
Do not use memory copy, pass the original array recursively to the
function
BinarySearch. |
L********n
发帖数: 930 | |
i*******n
发帖数: 114 | 5 Apple的onsite面试。
面试了2个人，每人一个小时。
第一位老印，没什么刁难，主要针对简历上的项目逐个询问。后面了问了一些简单问题
。database里面有几种join，如何handle too many requests in a server(我回答set
up a proxy cache that has two threads running concurrently. One thread
is
taking the client requests and the other one forwarding the requests to
server if the number of requests is not surpassed. Use semaphore to
coordinate the two threads)
第二位是老中，应该是被他挂了。一上来就直接说中文，整个面试都是说中文。问的都
是很基础的问题，可惜我大都不会。
how many bits in Java int type? What is the largest negative and
positive
numbers that a Java int can represent?
How many bits in Java char type?
How many bits in Java short type?
How many bits in Java double type?
String constant comparison. (Why == works on two string constants? 这人自
己
都不懂，居然说是constant folding。实际上是java有做优化，做了string constant
pool)
叫我写heap sort。我从来没用过的算法，当然不会写。然后又问我java collection提
供那些sort methods,我也没用过。所以也答不上来。
然后就是其他的基本问题。
第二天得到通知，一个OK,另一个不OK（估计就是这位老中了）。 |
i*******n
发帖数: 114 | 6 eBay面试。
应该是个prescreening phone interview.
2个老印，口音很重。几乎无法交流。
主要问了我过去做的几个项目。
因为交流有困难，所以45分钟的面试20分钟就结束了。
后来就没消息了。
绝对挂了。 |
i*******n
发帖数: 114 | 7 PayPal的笔试面试，版上一位朋友refer的。
发来5套题，一个小时后做完，发回去。大部分题目都不好做，我把其中的几道发在这
里。
希望后面有牛人帮忙解答。
What is the purpose of this function? (assume int are 32 bits)
int f( int v)
{
int t = 0;
int i;
for (i = 31; i !=0 ; i--) {
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v & 1;
return t;
}
----------------------------------------------------
Consider the following function:
int f (int num)
{
int out = 0;
for (; num > 0; num /= 10) {
int d = num % 10;
out *= 10;
out += d;
}
return out;
}
1) What does it do?
Reverse the individual digits in a number. Say a number is 3202, it will
reverse the digits into a number 2023.
2) Write the same algorithm using recursion
int f(int num, int *out)
{
if(num > 0){
int d = num % 10;
(*out) *= 10;
(*out) += d;
num /= 10;
f(num, out);
}
}
and start with
int out = 0;
f(num, &out);
------------------------------------------------- |
i*******n
发帖数: 114 | 8 ------------------------这题超难---------------------------
The string "paypal is the faster, safer way to send money" is written in a
diagonal pattern inside a rectangle: (you may want to display this pattern
in
a fixed font for better legibility).
P Y L H S S R T N
A A T A R E Y E O
P S F E F A S M E
I E T A W O D N Y
The diagonal pattern is from lower left to upper right, e.g. for a 4xN
rectangle, 1234567890 would be written as:
1 3 6 0 ...
2 5 9 ...
4 8 ...
7
Then read line after line:
PYLHSSRTNAATAREYEOPSFEFASMEIETAWODNY
Write the code that will take a string, eliminate spaces and punctuations,
calculate the size of a rectangle given a number of rows (4 in this example)
and return the converted string (e.g. an input of "paypal is the faster,
safer
way to send money" should generate the output "
pylhssrtnaatareyeopsfefasmeietawodny")
----------------------------------------------------
我感觉这道题目有问题，
1 3 6 0 ...
2 5 9 ...
4 8 ...
7
这个矩阵后面省略号的元素的规则不明了。比如第一行，是1 3 6 10 15 21还是1 3 6
10 。。。。 |
b***e
发帖数: 383 | |
s***g
发帖数: 1250 | |
|
|
t*******i
发帖数: 4960 | 11 可以上机做？
这样是手推很费劲啊。
【在 i*******n 的大作中提到】
: PayPal的笔试面试，版上一位朋友refer的。
: 发来5套题，一个小时后做完，发回去。大部分题目都不好做，我把其中的几道发在这
: 里。
: 希望后面有牛人帮忙解答。
: What is the purpose of this function? (assume int are 32 bits)
: int f( int v)
: {
: int t = 0;
: int i;
: for (i = 31; i !=0 ; i--) {
|
n***e
发帖数: 412 | 12 cong~
cs的实在是太好找工作了
【在 i*******n 的大作中提到】
: 昨天签了offer，今天收到HR回复。
: 下周开始工作。
: 历经2个月的找工经历就此告一段落。
: 在这几天我会陆续分享我在湾区几个大公司的onsite面经。
: 在这版上潜水半年，收获颇多。
: 背景：
: 本人CS MS专业，裸奔湾区找工作2个月。
|
t*******i
发帖数: 4960 | 13 眼看这象是把v的值附给t了。
int f( int v)
{
int t = 0;
int i;
for (i = 31; i !=0 ; i--) {
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v & 1;
return t;
}
【在 i*******n 的大作中提到】
: PayPal的笔试面试，版上一位朋友refer的。
: 发来5套题，一个小时后做完，发回去。大部分题目都不好做，我把其中的几道发在这
: 里。
: 希望后面有牛人帮忙解答。
: What is the purpose of this function? (assume int are 32 bits)
: int f( int v)
: {
: int t = 0;
: int i;
: for (i = 31; i !=0 ; i--) {
|
i*******n
发帖数: 114 | 14
可以上机做。反正在你电脑上1个小时做完，没人管你。
但是当时一时半会我还没看明白。
后来也没空弄了。
【在 t*******i 的大作中提到】
: 可以上机做？
: 这样是手推很费劲啊。
|
t*******i
发帖数: 4960 | 15 int f (int num)
{
int out = 0;
for (; num > 0; num /= 10) {
int d = num % 10;
out *= 10;
out += d;
}
return out;
}
1) What does it do?
上机还搞错了。
最讨厌这种移位，取余取整的，有次面试被人拿着求最大公因子的递归函数让我看是干啥的。。。带了2个数字去算，还是没看出来，还是被人看着做的，我那叫面红耳赤。 |
r*******y
发帖数: 1081 | 16
reverse the binary representation? for example v = 10. its binary form
is 1010 and it becomes 0101 after the f(v)
【在 i*******n 的大作中提到】
: PayPal的笔试面试，版上一位朋友refer的。
: 发来5套题，一个小时后做完，发回去。大部分题目都不好做，我把其中的几道发在这
: 里。
: 希望后面有牛人帮忙解答。
: What is the purpose of this function? (assume int are 32 bits)
: int f( int v)
: {
: int t = 0;
: int i;
: for (i = 31; i !=0 ; i--) {
|
T*******e
发帖数: 4928 | |
t*******i
发帖数: 4960 | 18 我上机试了一下，
std::cout << f(100) << endl;
std::cout << f(10) << endl;
std::cout << f(22010) << endl;
637534208
1342177280
1604976640
for example v = 10. its binary form
becomes 010100000....(28 0s) |
r*******y
发帖数: 1081 | 19 your output is correct. it is not just reverse the binary form since
t=t<<1 for 32 times. it should stop when v decreses to zero but it is
missing
in the code.
【在 t*******i 的大作中提到】
: 我上机试了一下，
: std::cout << f(100) << endl;
: std::cout << f(10) << endl;
: std::cout << f(22010) << endl;
: 637534208
: 1342177280
: 1604976640
: for example v = 10. its binary form
: becomes 010100000....(28 0s)
|
h*********n
发帖数: 11319 | 20 第一题应该是reverse bit in v吧
【在 i*******n 的大作中提到】
: PayPal的笔试面试，版上一位朋友refer的。
: 发来5套题，一个小时后做完，发回去。大部分题目都不好做，我把其中的几道发在这
: 里。
: 希望后面有牛人帮忙解答。
: What is the purpose of this function? (assume int are 32 bits)
: int f( int v)
: {
: int t = 0;
: int i;
: for (i = 31; i !=0 ; i--) {
|
|
|
m****t
发帖数: 555 | 21 最后一道题感觉不难，就是根据字符个数先算出矩阵宽度，再把字符映射到矩阵对应位
置。
根据题意，1234567890应该是这样的
1 3 6
2 5 9
4 8
7 0
假设矩阵行数为ROW, 处理过的字符串长N,存放在A[0..N-1].
则矩阵宽度为COL= ceiling of N/ROW;
int pos=0;
int x, y;
int xb=0;
for (c=0; c<= ROW+COL-2; c++) {
x = xb;
y = c-x;
while (x >= 0 && y <= COL-1 && pos
B[x][y] = A[pos];
pos++;
x--;
y++;
}
if (xb < ROW-1 ) xb++;
if (pos>=N) break;
}
output B[i][j]; |
x*******t
发帖数: 29 | 22 cong
looks like nvidia is really easy
【在 i*******n 的大作中提到】
: nvidia interview experience
: location:
: NVIDIA
: San Thomas Expressway, Santa Clara
: duration
: 2 hours, 1PM to 3PM
: 2 interviewers, each for 1 hour
: ------------------------------------------
: cdj
: xor eax, edx
|
i*******n
发帖数: 114 | 23 你能否把这段code做成可编译的C++或java代码，运行一下就知道对不对了。
我做了一个Java的。
结果是
“pylhtesy aatsfoe psaatn ifsyo”
和要求的
“pylhssrtnaatareyeopsfefasmeietawodny”
从第五位字符开始就不对。
但是按照题目的第一行pattern的话，第五位应该是t啊。
1 3 6 10 15 21 ....
public static String parseEncodedString(String inputString){
int numOfRows = 4;
String trimmedInputString = inputString.trim();
trimmedInputString = trimmedInputString.replace(" ", "");
trimmedInputString = trimmedInputString.replace(".", "");
trimmedInputString = trimmedInputString.replace(",", "");
trimmedInputString = trimmedInputString.replace(":", "");
trimmedInputString = trimmedInputString.replace(";", "");
trimmedInputString = trimmedInputString.replace("!", "");
trimmedInputString = trimmedInputString.replace("?", "");
trimmedInputString = trimmedInputString.replace(""", "");
trimmedInputString = trimmedInputString.replace("'", "");
int stringLength = trimmedInputString.length();
System.out.println("trimmedInputString length:" +
stringLength);
int numOfColumns = stringLength / 4;
/**
* break the string into a matrix
*/
char[][] originalStringMatrix= new char[numOfRows][numOfColumns];
/**
* to be safe
*/
int newNumOfColumns = numOfColumns + 5;
char[][] reorderedStringMatrix= new char[numOfRows][newNumOfColumns];
int counter = 0;
for(int i = 0 ; i < numOfRows; i++){
for(int j = 0 ; j < numOfColumns; j++){
originalStringMatrix[i][j] = trimmedInputString.charAt(
counter);
counter++;
}
}
System.out.println("the original string matrix looks like below:");
for(int i = 0 ; i < numOfRows; i++){
System.out.print("row:" + i + ":");
for(int j = 0 ; j < numOfColumns; j++){
System.out.print(originalStringMatrix[i][j]);
}
System.out.println("");
}
System.out.println("");
/**
* reset counter
*/
int firstRowDifference = 2;
int firstRowStartingNum = 0;
int secondRowDifference = 3;
int secondRowStartingNum = 1;
int thirdRowDifference = 4;
int thirdRowStartingNum = 3;
int fourthRowDifference = 5;
int fourthRowStartingNum = 6;
int[] differences = {firstRowDifference,
secondRowDifference,
thirdRowDifference,
fourthRowDifference};
int[] startingNums = {firstRowStartingNum,
secondRowStartingNum,
thirdRowStartingNum,
fourthRowStartingNum};
counter = 0;
System.out.println("numOfColumns=" + numOfColumns);
for(int i = 0 ; i < numOfRows; i++){
counter = startingNums[i];
for(int j = 0 ; j < newNumOfColumns; j++){
if(counter > (trimmedInputString.length() - 1)){
break;
}
System.out.println("counter=" + counter);
reorderedStringMatrix[i][j] =
trimmedInputString.charAt(counter);
counter += differences[i];
differences[i]++;
}
System.out.println("completing " + i + " row");
}
/**********
*
*
*/
StringBuilder sb = new StringBuilder();
// sb.append(trimmedInputString.charAt(0));
for(int i = 0 ; i < numOfRows; i++){
for(int j = 0 ; j < newNumOfColumns; j++){
sb.append(reorderedStringMatrix[i][j]);
}
}
return sb.toString();
}
【在 m****t 的大作中提到】
: 最后一道题感觉不难，就是根据字符个数先算出矩阵宽度，再把字符映射到矩阵对应位
: 置。
: 根据题意，1234567890应该是这样的
: 1 3 6
: 2 5 9
: 4 8
: 7 0
: 假设矩阵行数为ROW, 处理过的字符串长N,存放在A[0..N-1].
: 则矩阵宽度为COL= ceiling of N/ROW;
: int pos=0;
|
m****t
发帖数: 555 | 24 我的程序运行结果是正确的。
这个c程序输出就是 pylhssrtnaatareyeopsfefasmeietawodny
#include
#include
#include
int main()
{
char *A="paypalisthefastersaferwaytosendmoney";
char B[4][10]={};
int ROW = 4;
int COL;
int N;
COL = strlen(A)/ROW;
if (strlen(A)%ROW) {
COL++;
}
N= strlen(A);
int pos=0;
int c, xb=0;
int x, y;
for (c=0; c<= ROW+COL-2; c++) {
x = xb;
y = c-x;
while (x >= 0 && y <= COL-1 && pos
B[x][y] = A[pos];
pos++;
x--;
y++;
}
if (xb < ROW-1 ) xb++;
if (pos>=N) break;
}
for (x=0; x
for (y=0; y
putchar(B[x][y]);
return 1;
}
【在 i*******n 的大作中提到】
: 你能否把这段code做成可编译的C++或java代码，运行一下就知道对不对了。
: 我做了一个Java的。
: 结果是
: “pylhtesy aatsfoe psaatn ifsyo”
: 和要求的
: “pylhssrtnaatareyeopsfefasmeietawodny”
: 从第五位字符开始就不对。
: 但是按照题目的第一行pattern的话，第五位应该是t啊。
: 1 3 6 10 15 21 ....
: public static String parseEncodedString(String inputString){
|
i*******n
发帖数: 114 | |
i*******n
发帖数: 114 | 26 1
------》
1 3
2
------》
1 3 6
2 5
4
------》
1 3 6 0
2 5 9
4 8
7
------》
1 3 6 0 ...
2 5 9 ...
4 8 ...
7
-----------------
原来是这样子。 |
s*****y
发帖数: 897 | 27 which company you finally get the offer? |
s**********e
发帖数: 326 | 28 我来贴个general的code
void diagnalPattern(char* str, int rowNum){
int charNum = 0;
for(int i = 0; i < strlen(str); i++){
if(isValidChar(str[i])){
charNum++;
}
}
int colNum = (charNum + rowNum - 1) / rowNum;
char** arr;
arr = new char*[rowNum];
for(int i = 0; i < rowNum; i++)
arr[i] = new char[colNum];
for(int i = 0 ; i < rowNum; i++)
for(int j = 0; j < colNum; j++)
arr[i][j] = ' ';
int curPos = 0;
for(int i = 0; i < rowNum; i++)
for(int j = 0, tmp = i; j < rowNum && tmp >= 0 && j < colNum; curPos
++){
if(isValidChar(str[curPos])){
arr[tmp][j] = str[curPos];
j++; tmp--;
}
}
for(int i = 1; i < colNum; i++)
for(int tmp = i, j = rowNum - 1; j >= 0 && curPos < strlen(str) &&
tmp < colNum; curPos++){
if(isValidChar(str[curPos])){
arr[j][tmp] = str[curPos];
j--; tmp++;
}
}
for(int i = 0; i < rowNum; i++){
for(int j = 0; j < colNum; j++){
cout << arr[i][j];
}
cout << endl;
}
}
int main(){
char* input = "paypal is the faster, safer way to send money";
diagnalPattern(input, 4);
} |
s**********e
发帖数: 326 | 29 ogic puzzle,
4 fuses, each fuse burns out in 40 minutes, create a fuse that can burn
in
20 minutes. slightly flawed problem. Because when you burn the fuse from
two
ends, it is not exactly 20 minutes. (Two combustion points are
certainly
faster than one.)
这个题怎么解？ |
j*****p
发帖数: 108 | 30
我跟楼主经历非常相似，今天是工作第二天。 gxgx
【在 i*******n 的大作中提到】
: 昨天签了offer，今天收到HR回复。
: 下周开始工作。
: 历经2个月的找工经历就此告一段落。
: 在这几天我会陆续分享我在湾区几个大公司的onsite面经。
: 在这版上潜水半年，收获颇多。
: 背景：
: 本人CS MS专业，裸奔湾区找工作2个月。
|
|
|
h**********d
发帖数: 4313 | |
i*******n
发帖数: 114 | 32 原题好像是create a fuse that can burn in 25 minutes.
You take one fuse and light two ends of it. At the same time, you burn
another fuse from one end.
By the time the first fuse burns out, it is 20 minutes. So you have a fuse (
second fuse burns for 20 minutes and has 20 minutes left.) that can burn in
20 minutes.
Burn the second fuse(20min one) on two ends and burn a third fuse from one
end at the same time.
By the time the second fuse burns out, you have a 30 minute fuse(the third
one).
Now you light the two ends of the third fuse(30 minute one) and burn the
fourth fuse from one end.
By the time the third fuse finishes, the fourth fuse will have 25 minutes
left in it.
So you get a 25 minute fuse.
---------------------------------
I say this is a slightly flawed one because two combustion points
certainly burn the fuse faster than one combustion point when the two points
almost converge somewhere in the fuse.
It is like digging a tunnel from both ends. It is faster than digging it
from one end to another.
【在 s**********e 的大作中提到】
: ogic puzzle,
: 4 fuses, each fuse burns out in 40 minutes, create a fuse that can burn
: in
: 20 minutes. slightly flawed problem. Because when you burn the fuse from
: two
: ends, it is not exactly 20 minutes. (Two combustion points are
: certainly
: faster than one.)
: 这个题怎么解？
|
m********u
发帖数: 14 | 33 A recursive solution.
public static void createMatrix(
string s,
int startPosInOriginalString,
char[,] data,
int curX,
int curY,
int rowNum,
int colNum)
{
curX = curX - rowNum + 1;
if (curX < 0)
{
curX = 0;
}
if (curY >= rowNum)
{
curY = rowNum - 1;
}
for (int row = curY; row > -1; row--)
{
if (curX < colNum)
{
data[row, curX] = s[startPosInOriginalString++];
}
curX++;
if (startPosInOriginalString == s.Length)
{
return;
}
}
createMatrix(s, startPosInOriginalString, data, curX, curY + 1,
rowNum, colNum);
}
}
call:
createMatrix(s, 0, data, -1, 0, rowNum, colNum);
data will be the output.
【在 s**********e 的大作中提到】
: 我来贴个general的code
: void diagnalPattern(char* str, int rowNum){
: int charNum = 0;
: for(int i = 0; i < strlen(str); i++){
: if(isValidChar(str[i])){
: charNum++;
: }
: }
: int colNum = (charNum + rowNum - 1) / rowNum;
: char** arr;
|
f*******t
发帖数: 7549 | 34 打印矩阵很简单啊，如果我没理解错的话——
从1到0应该是：
1 3 6 0
2 5 9
4 8
7
而不是前面有人回复的：
1 3 6
2 5 9
4 8
7 0
根本不需要新建数组去存矩阵，因为ROW是固定的，所以排列有非常明确的顺序。
第一行是Array[0], Array[2], Array[5], Array[9],...从5之后每次index加4；
第二行是Array[1], Array[4], Array[8],...从4之后每次index加4；
……
以此类推，可以写出一个两层的循环直接从数组中取数字打印，做到in space解决问题 |
k****n
发帖数: 369 | 35 agree， 电面决不能把问题想复杂
【在 f*******t 的大作中提到】
: 打印矩阵很简单啊，如果我没理解错的话——
: 从1到0应该是：
: 1 3 6 0
: 2 5 9
: 4 8
: 7
: 而不是前面有人回复的：
: 1 3 6
: 2 5 9
: 4 8
|
m****t
发帖数: 555 | 36 没这么简单吧。
index的规律，不仅与row有关，与column大小也有关系.
你画个4x2和4x6的矩阵，就会发现规律不但不一样，也没有你说的那么简单。
以4x6的矩阵为例，用来排列0-23.
第三和第四行打印结果为：
3,7,11,15,19,22
6,10,14,18,21,23
你说的规律根本不对。
【在 f*******t 的大作中提到】
: 打印矩阵很简单啊，如果我没理解错的话——
: 从1到0应该是：
: 1 3 6 0
: 2 5 9
: 4 8
: 7
: 而不是前面有人回复的：
: 1 3 6
: 2 5 9
: 4 8
|
N**k
发帖数: 1522 | 37 gxgx
【在 i*******n 的大作中提到】
: 昨天签了offer，今天收到HR回复。
: 下周开始工作。
: 历经2个月的找工经历就此告一段落。
: 在这几天我会陆续分享我在湾区几个大公司的onsite面经。
: 在这版上潜水半年，收获颇多。
: 背景：
: 本人CS MS专业，裸奔湾区找工作2个月。
|
s**********e
发帖数: 326 | 38
我刚开始想的跟你一样，但是看了原题发现理解的不对，题目中给的例子是
P Y L H S S R T N
A A T A R E Y E O
P S F E F A S M E
I E T A W O D N Y
36个有效字符放在一个 4 × 9的矩阵里面，按照你的理解应该是放在一个4×10的矩阵
里面。感觉是要把所有的字符放在尽量小的矩阵里面，所有需要计算每个字符的所在位
置。
【在 f*******t 的大作中提到】
: 打印矩阵很简单啊，如果我没理解错的话——
: 从1到0应该是：
: 1 3 6 0
: 2 5 9
: 4 8
: 7
: 而不是前面有人回复的：
: 1 3 6
: 2 5 9
: 4 8
|
f*******t
发帖数: 7549 | 39 哦，不过这样规律还是存在的，我坚持认为可以in space解决。等我下班了试着写个代码
【在 s**********e 的大作中提到】
:
: 我刚开始想的跟你一样，但是看了原题发现理解的不对，题目中给的例子是
: P Y L H S S R T N
: A A T A R E Y E O
: P S F E F A S M E
: I E T A W O D N Y
: 36个有效字符放在一个 4 × 9的矩阵里面，按照你的理解应该是放在一个4×10的矩阵
: 里面。感觉是要把所有的字符放在尽量小的矩阵里面，所有需要计算每个字符的所在位
: 置。
|
h**********8
发帖数: 267 | |
|
|
h***r
发帖数: 273 | 41 挺好的, Bless~~~
。不过有份工作我
包回国。反
【在 i*******n 的大作中提到】
: 昨天签了offer，今天收到HR回复。
: 下周开始工作。
: 历经2个月的找工经历就此告一段落。
: 在这几天我会陆续分享我在湾区几个大公司的onsite面经。
: 在这版上潜水半年，收获颇多。
: 背景：
: 本人CS MS专业，裸奔湾区找工作2个月。
|
m****t
发帖数: 555 | 42 我想了一下，其实可以用一个递归公式来描述，这样可以做到in place 解决，无需额
外空间。
仅作抛砖引玉，有更好的欢迎提出。
用B[i][j]表示矩阵位置(i,j)对应的字符串中位置
B[i][j] = B[i][j-1]+ min(i, COL-j) + min(ROW-i-1, j)+1；
B[i][0] = B[[i-1][1]-1;
B[0][0]=0;
打印一行的时候，当前值可从前一个值推出。同时需要保存该行的第二个位置的值，即 B[i][1]，用来计算下一行的第一个位置值。
代码
【在 f*******t 的大作中提到】
: 哦，不过这样规律还是存在的，我坚持认为可以in space解决。等我下班了试着写个代码
|
