请问照片后面如何写上姓名和a number - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

请问照片后面如何写上姓名和a number

请问照片后面如何写上姓名和a number# Immigration - 落地生根

f*92010-06-11 07:06

1 楼

两人，没人45分钟。
第一个：从一个array里找出等于t的数，把它们放到array后面，其他元素相对位置保
持不变，顺次迁移；
第二个：一个m x n的方格，从左上角到右下角走，只能向右或向下，总共几种走法。
问题很简单又是老题。我也都答出来了，code也写了。第二个问题我开始用计算组合数
的方法，面试官还没见过这种解法。但是最后仍然被拒了。感觉可能是答题太慢了？或
者听力不好老让第一个面试官重复问题？没办法。。。

a*u2010-06-11 07:06

2 楼

按照皮匠的步骤，在照片后面用铅笔写名字，但是表面太光滑，咋都无法写下字，那如
何办？
谢谢。

X*n2010-06-11 07:06

3 楼

第二题dp啊
设每个格的走法为t(x,y),
if (x==1||y==1)
t(x, y)=1
else
t(x, y)=t(x-1, y)+t(x, y-1)

【在 f****9 的大作中提到】

: 两人，没人45分钟。
: 第一个：从一个array里找出等于t的数，把它们放到array后面，其他元素相对位置保
: 持不变，顺次迁移；
: 第二个：一个m x n的方格，从左上角到右下角走，只能向右或向下，总共几种走法。
: 问题很简单又是老题。我也都答出来了，code也写了。第二个问题我开始用计算组合数
: 的方法，面试官还没见过这种解法。但是最后仍然被拒了。感觉可能是答题太慢了？或
: 者听力不好老让第一个面试官重复问题？没办法。。。

w*r2010-06-11 07:06

4 楼

实在不行用细的Sharpie marker.

r*u2010-06-11 07:06

5 楼

显然是组合数学的方法好啊

【在 X*********n 的大作中提到】

: 第二题dp啊
: 设每个格的走法为t(x,y),
: if (x==1||y==1)
: t(x, y)=1
: else
: t(x, y)=t(x-1, y)+t(x, y-1)

e*e2010-06-11 07:06

6 楼

use marker and write on hard surface, don't let the ink penetrate though.

X*n2010-06-11 07:06

7 楼

解释下呢？

【在 r***u 的大作中提到】

: 显然是组合数学的方法好啊

a*u2010-06-11 07:06

8 楼

非常感谢！

f*92010-06-11 07:06

9 楼

我说用dp了。
感觉挺莫名其妙被拒的。第一个面试官问完了还说it‘s good，第二个面试官连计算组
合数的方法都不会。
可能是我听力不太好交流有点问题让他们印象是比较笨？还是我答题太慢了？莫非这种
难度的题45分钟应该完成多个，每个都在白板上完成code，才算合格了？

【在 X*********n 的大作中提到】

: 第二题dp啊
: 设每个格的走法为t(x,y),
: if (x==1||y==1)
: t(x, y)=1
: else
: t(x, y)=t(x-1, y)+t(x, y-1)

A*r2010-06-11 07:06

10 楼

铅笔可以写的。换个软点芯。2 works better than HB.

P*72010-06-11 07:06

11 楼

第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)

【在 f****9 的大作中提到】

d*s2010-06-11 07:06

12 楼

我用圆珠笔

f*92010-06-11 07:06

13 楼

我说了，面试官还没见过用组合数的方法。
但是还是让写程序，而且要考虑有obstacle的情况，就是考虑有的方格不能通过的情况
。这种情况好像不能用组合数直接算吧？

【在 P*******7 的大作中提到】

: 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)

P*72010-06-11 07:06

14 楼

对于第二个问题，如果面试官就问了这一题，你花的时间就长了。因为这道题后面还有
一问，如果你保
持向下的步子一直多于或等于你向右的步子，一共多少种走法。

【在 f****9 的大作中提到】

: 我说用dp了。
: 感觉挺莫名其妙被拒的。第一个面试官问完了还说it‘s good，第二个面试官连计算组
: 合数的方法都不会。
: 可能是我听力不太好交流有点问题让他们印象是比较笨？还是我答题太慢了？莫非这种
: 难度的题45分钟应该完成多个，每个都在白板上完成code，才算合格了？

P*72010-06-11 07:06

15 楼

这道题不是google经典题目么？面试者怎么会不知道组合数方法呢...那你太冤了

【在 f****9 的大作中提到】

: 我说了，面试官还没见过用组合数的方法。
: 但是还是让写程序，而且要考虑有obstacle的情况，就是考虑有的方格不能通过的情况
: 。这种情况好像不能用组合数直接算吧？

s*y2010-06-11 07:06

16 楼

第一题，pass一遍找到有多少t,从第一个t开始顺着写非t数，最后填t。
还有什么更好的解法么。

j*u2010-06-11 07:06

17 楼

第一遍就可以把非t前移，然后从最后一个位置把t填上

【在 s********y 的大作中提到】

: 第一题，pass一遍找到有多少t,从第一个t开始顺着写非t数，最后填t。
: 还有什么更好的解法么。

j*u2010-06-11 07:06

18 楼

c# implementation，还有没有更好方法？
static void ArrayShift(T[] array, T seed) where T:IComparable
{
if (array == null)
throw new ArgumentNullException("array");
int dest = 0;
for (int i = 0; i < array.Length; ++i)
{
if (i != dest && !array[i].Equals(seed))
{
array[dest++] = array[i];
}
}
for (int i = dest; i < array.Length; ++i)
{
array[i] = seed;
}
}

【在 j*****u 的大作中提到】

: 第一遍就可以把非t前移，然后从最后一个位置把t填上

r*g2010-06-11 07:06

19 楼

我google第二题，竟然在“小学生VBS竞赛题库“里有。提示是杨辉三角算法或者回溯
法。这个回溯法应该就是DP, 杨辉三角是个什么？

d*e2010-06-11 07:06

20 楼

你的方法是对的，但code是不是写错了点？
1, 2, 3, 4, 5, 6, 7, 8
seed = 5
但由于dest一直等于0，所以6不幸被换到去1的位置了.

【在 j*****u 的大作中提到】

: c# implementation，还有没有更好方法？
: static void ArrayShift(T[] array, T seed) where T:IComparable
: {
: if (array == null)
: throw new ArgumentNullException("array");
: int dest = 0;
: for (int i = 0; i < array.Length; ++i)
: {
: if (i != dest && !array[i].Equals(seed))
: {

c*22010-06-11 07:06

21 楼

Original Array: 22 22 55 55 55 55 55 33 33 33
num=22:freq=2
num=55:freq=5
num=33:freq=3
Rotate 2:
55 55 55 55 55 33 33 33 22 22
Moved 44 to back:
0 moved:
55 55 55 55 55 33 33 33 22 22
Moved 33 to back:
3 moved:
55 55 55 55 55 22 22 33 33 33

c*22010-06-11 07:06

22 楼

int move_num_to_array_end(int array[], int size, int num)
{
int i=0,j,from;
int count=0;
int total=0;
int tail=size;
while(icount=0;
from=i;
while((array[i]==num)&&(iif (i>=tail-1) return total;

if (count) {
for(j=i;jarray[j-count]=array[j];
tail -= count;

for(j=tail;jarray[j]=num;

i=from;
}
else
i++;
}

return total;
}

f*r2010-06-11 07:06

23 楼

请问这样做可以么?
// 从一个array里找出等于t的数, 把它们放到array后面, 其他元素相对位置保持不变
, 顺次迁移.
void move_num_to_array_end(int array[], int size, int t) {
int idx = 0;
for (int i = 0; i < size; i++) {
int curInt = array[i];
if (curInt != t) {
array[idx] = array[i];
idx++;
}
}
for (;idx < size; idx++)
array[idx] = t;
}
// 一个m x n的方格, 从左上角到右下角走, 只能向右或向下, 总共几种走法.
int move_topleft_to_bottomright(int m, int n) {
if (m == 1 || n == 1)
return 1;
return (move_topleft_to_bottomright(m-1,n)+move_topleft_to_bottomright(m
,n-1));
}

c*22010-06-11 07:06

24 楼

very good. Much cleaner than mine.

【在 f*******r 的大作中提到】

: 请问这样做可以么?
: // 从一个array里找出等于t的数, 把它们放到array后面, 其他元素相对位置保持不变
: , 顺次迁移.
: void move_num_to_array_end(int array[], int size, int t) {
: int idx = 0;
: for (int i = 0; i < size; i++) {
: int curInt = array[i];
: if (curInt != t) {
: array[idx] = array[i];
: idx++;

g*62010-06-11 07:06

25 楼

第2题如果编程做，都不难。
如果用组合做，答案是等价于m+n-2个数里面取m-1个数，答案是c(m+n-2, m-1).因为总
共要走m+n-2，要在里面选m-1步向下走，或选n-1步向右走。
如果向下的步数不能超过向右的步数，该怎么算？

【在 P*******7 的大作中提到】

: 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)

f*r2010-06-11 07:06

26 楼

我觉得应该是c(m+n-2, n-1) 或者 c(m+n-2, m-1).

【在 P*******7 的大作中提到】

: 第二题很简单，不用dp，等价于m+n个数里面取m个数，答案是c(m+n, m)

g*s2010-06-11 07:06

27 楼

如果有方格不能通过的情况，确实会比较麻烦。不过还是组合问题。

【在 f****9 的大作中提到】

g*s2010-06-11 07:06

28 楼

还有优化的余地。如果数组里全是t，那第二个循环没必要了。不过不影响复杂度。

【在 f*******r 的大作中提到】

l*i2010-06-11 07:06

29 楼

这两个是等价的把

【在 f*******r 的大作中提到】

: 我觉得应该是c(m+n-2, n-1) 或者 c(m+n-2, m-1).

x*32010-06-11 07:06

30 楼

用类似quick sort里得partition，只要一次遍历数组就可以了，但是需要3个指针

【在 g*********s 的大作中提到】

: 还有优化的余地。如果数组里全是t，那第二个循环没必要了。不过不影响复杂度。

f*r2010-06-11 07:06

31 楼

sorry, cannot type Chinese in the lab.....
I think a easy fix would be #ofways(topleft->bottomright) - #ofways(topleft-
>blockA)*#ofways(blockA->bottomright) if you only face one blockA.
But it's more complicated when you face more than one blocks.

【在 g*********s 的大作中提到】

: 如果有方格不能通过的情况，确实会比较麻烦。不过还是组合问题。

e*62010-06-11 07:06

32 楼

void mv_t_to_end(int *a, int size, int t){
int i=0,j=0,k=size;
while(jif(a[j]==t){
j++;
k--;
}
else
a[i++]=a[j++];
}
while(ka[k++]=t;
}

h*62010-06-11 07:06

33 楼

如果格子不多，障碍不少，令f(i, j)为各格子通往右下角的走法数，则：
f(n-1, m-1) = 1
f(i, j) = f(i+1, j) + f(i, j+1), if a[i][j]==1
f(i, j) = 0, if a[i][j]==0
f(0, 0)就是所求答案
如果格子不少，障碍不多，那么可以用包含与排除解决。

i*e2010-06-11 07:06

34 楼

这个解法不对，有 bug.
test case:
{22,11,33,33,44,22,11}
t = 22,
output=
{11 33 33 44 44 22 22}
expected=
{11 33 33 44 11 22 22}
第一题的解：
void shiftArrayEqualsTBack(int num[], int n, int t) {
int total = 0;
for (int i = 0; i < n; i++) {
if (num[i] == t)
total++;
else
num[i-total] = num[i];
}
for (int i = n-total; i < n; i++) {
num[i] = t;
}
}
第二题的解：
const int X_MAX = 4;
const int Y_MAX = 4;
bool validLocation(int x, int y) {
if (x <= -1 || x >= X_MAX || y <= -1 || y >= Y_MAX) return false;
return true;
}
bool canReach(int map[][Y_MAX], int x, int y, bool visited[][Y_MAX]) {
if (!validLocation(x, y)) return false;
if (map[x][y]) return false;
if (x == X_MAX-1 && y == Y_MAX-1) return true;
if (visited[x][y]) return false;
visited[x][y] = true;

return canReach(map, x, y-1, visited) ||
canReach(map, x+1, y, visited) ||
canReach(map, x, y+1, visited) ||
canReach(map, x-1, y, visited);
}
int main() {
int map[X_MAX][Y_MAX] = {
{0,0,1,0},
{1,0,1,0},
{0,1,0,1},
{0,1,0,0}
};
bool visited[X_MAX][Y_MAX] = {false};
cout << canReach(map, 0, 0, visited);
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 e**********6 的大作中提到】

: void mv_t_to_end(int *a, int size, int t){
: int i=0,j=0,k=size;
: while(j: if(a[j]==t){
: j++;
: k--;
: }
: else
: a[i++]=a[j++];
: }