创新工场招聘笔试题目

前几天去了创新工场的一个招聘笔试，刚刚收到的面试通知。给大家写下这次创新工场招聘笔试大概的题目吧，我也记得不多呀~

1. 在A*B的棋盘上，左上角是(0,0)，右下角是(A-1，B-1)，你每一步只能从(x,y)到(x+1,y), (x,y+1), (x+2,y+1), (x+1,y+2) 4个位置中的一个。求从左上角到右下角走法的数目。(这个数目可能很大，结果只需要模10 000 007即可，1

int func(int row, int col)

{

if (row < 1 || col < 1)

{

if (0 == row && col > 0 || row > 0 && 0 == col)

{

return 1; // 当只有一行或者一列时，从(0,0)到(0,col)或者是(row,0)均有一种方法，故返回1，

}

else

{

return 0; // 不满足条件

}

}

else if (1 == row && 1 == col)

{

return 2; // 当只有一行且一列时，从(0,0)到(row,col)有两种方法，故返回2

}

else if (1 == row && 2 == col || 2 == row && 1 == col)

{

return 4; //当只有两行一列或者一行两列时，从(0,0)到(row,col)有四种方法，故返回4

}

else

{

return func(row - 1, col)

+ func(row, col - 1)

+ func(row - 2, col - 1)

+ func(row - 1, col - 2);

}

}

int main()

{

cout<

system("pause");

return 0;

}

上面的方法是按题意直接写的，不难看出其中存在着 子问题重叠

#include "stdafx.h"

#include

using namespace std;

int func(int row, int col)

{

// 新建table用于存储

int *table = new int[(row + 2) * (col + 2)];

int i, j;

int res;

memset(table, 0, sizeof(int) * (row + 2) * (col + 2));

// 初始化

for (i = 1; i < (row + 2); ++i)

{

table[i * (col + 2) + 1] = 1;

对大家有用么？

}

for (i = 1; i < (col + 2); ++i)

{

table[(col + 2) + i] = 1;

}

for (i = 2; i < (row + 2); i++)

{

for (j = 2; j < (col + 2); j++)

{

// 某个点的值等于能到达该点的四个点的值相加

table[i * (col + 2) + j] = table[i * (col + 2) + j - 1]

+ table[(i - 1) * (col + 2) + j]

+ table[(i - 1) * (col + 2) + j - 2]

+ table[(i - 2) * (col + 2) + j - 1];

table[i * (col + 2) + j] %= 1000000;//取模

}

}

res = table[(row + 2) * (col + 2) - 1];

delete[]table;

return res;

}

int main()

{

cout<

system("pause");

return 0;

}

2. 给出一个自然数n(1<=n<=500000)，计算这个自然数所有因子的和。因子是只小于一个n的数，并且能找到一个自然数，使其相乘的积等于n。