创新工场笔试小记

 

创新工场几道笔试题，欢迎大家讨论。

1 基本情况

笔试题量很小，答题时间1个小时。

 

1道填空题，9道左右选择题，最后一道编程题。

2 几个题目

第一题：

 

int f(int x) {
	int c = 0;
	while(x!=0) {
		x = x & (x-1);
		c++;
	}
	return c;
}

 

对于int a = 65536 + 1024 + 8 + 1; int b = f(a);执行后b等于多少？

 

第二题：

 

5个骰子，六个面分别标有1~6，现在将五个同时随机投掷，五个点数之和为下面哪个点的概率最大？

(A)14 (B)15 (C)17 (D)20

 

第三题：

 

unsigned long c = 0;
char a = 0x48;
char b = 0x52;

c = b<<8 | a;

 

请问c等于多少？

 

第四题：编程题

 

题目大概意思是：A、B两个量杯，容量分别为M升、N升，现在要用A和B给另一个量杯C盛水K升，C量杯足够大。备用水无限。编程输出每一个步骤三个杯子中的水量。比如：输出（0,0,0）,(M,0,0)等。

 

不知道题目说清楚没有？如不明白，请留言指出。

评论

30 楼 cch123 2010-09-28  

楼上的解法我来举个反例，
M=5 N=3 K=1，
实际上只需要三步就可以完成。

29 楼 piao_bo_yi 2010-09-27  

直接倒水需要两步，间接倒水需要三步。z表示间接倒水次数。

28 楼 polaris1119 2010-09-26  

piao_bo_yi 写道

2.c=0x5248
4.倒水有两种方式，直接方式，间接方式。直接-两步,间接-三步。
e.g. M=3, N=1, K=2 --->
直接方式:
(0, 1, 0)
(0, 0, 1)
(0, 1, 1)
(0, 0, 2)
间接方式:
(3, 0, 0)
(2, 1, 0)
(0, 0, 2)
本质上是M*x + N*y + (M-N)*z = K，求x,y,z的正整数解，优化方程为使2*x+2*y+3*z最小。

public class TestLinear {
    //xCo*x + yCo*y + zCo*z = right
    public static void linearEquation(int M, int N,int right)
    {
        int xCo = M > N ? M : N; 
        int yCo = M < N ? M : N; 
        int zCo = xCo - yCo;
        int times = Integer.MAX_VALUE;
        int xResult=0, yResult=0, zResult=0;
        boolean isFound = false;
        for(int i=0; i*xCo<=right; i++)
        {
            for(int j=0; i*xCo+j*yCo<=right; j++)
            {
                for(int k=0; i*xCo+j*yCo+k*zCo<=right; k++)
                {
                    if(xCo*i + yCo*j + zCo*k == right) {
                        int t = 2*xCo + 2*yCo + 3*zCo;
                        if(t < times) {//To Make the time minimal
                            isFound = true;
                            xResult = i;
                            yResult = j;
                            zResult = k;
                        }
                    }                   
                }
            }
        }
        
        if(!isFound) {
            System.out.println("Nope.");
            return;
        }
        
        System.out.println(xResult);
        System.out.println(yResult);
        System.out.println(zResult);
        
        System.out.println("Begin:");
        
        int size = 0;
        for(int i=0; i<xResult; i++)
        {
            p(xCo, 0, size);
            size += xCo;
            p(0, 0, size);
        }
        for(int i=0; i<yResult; i++)
        {
            p(0, yCo, size);
            size += yCo;
            p(0, 0, size);
        }
        for(int i=0; i<zResult; i++)
        {
            p(xCo, 0, size);
            p(xCo-yCo, yCo, size);
            size += (xCo - yCo);
            p(0, 0, size);
        }
    }
    
    public static void p(int x, int y, int z)
    {
        System.out.println("(" + x + "," + y + "," + z + ")");
    }
    
    public static void main(String[] args)
    {
        linearEquation(5, 3, 17);
    }
}

第四题思路对的，没看代码。请问一下：优化方程为使2*x+2*y+3*z最小？这个优化方程从何而来？

27 楼 piao_bo_yi 2010-09-26  

2.c=0x5248
4.倒水有两种方式，直接方式，间接方式。直接-两步,间接-三步。
e.g. M=3, N=1, K=2 --->
直接方式:
(0, 1, 0)
(0, 0, 1)
(0, 1, 1)
(0, 0, 2)
间接方式:
(3, 0, 0)
(2, 1, 0)
(0, 0, 2)
本质上是M*x + N*y + (M-N)*z = K，求x,y,z的正整数解，优化方程为使2*x+2*y+3*z最小。

public class TestLinear {
    //xCo*x + yCo*y + zCo*z = right
    public static void linearEquation(int M, int N,int right)
    {
        int xCo = M > N ? M : N; 
        int yCo = M < N ? M : N; 
        int zCo = xCo - yCo;
        int times = Integer.MAX_VALUE;
        int xResult=0, yResult=0, zResult=0;
        boolean isFound = false;
        for(int i=0; i*xCo<=right; i++)
        {
            for(int j=0; i*xCo+j*yCo<=right; j++)
            {
                for(int k=0; i*xCo+j*yCo+k*zCo<=right; k++)
                {
                    if(xCo*i + yCo*j + zCo*k == right) {
                        int t = 2*xCo + 2*yCo + 3*zCo;
                        if(t < times) {//To Make the time minimal
                            isFound = true;
                            xResult = i;
                            yResult = j;
                            zResult = k;
                        }
                    }                   
                }
            }
        }
        
        if(!isFound) {
            System.out.println("Nope.");
            return;
        }
        
        System.out.println(xResult);
        System.out.println(yResult);
        System.out.println(zResult);
        
        System.out.println("Begin:");
        
        int size = 0;
        for(int i=0; i<xResult; i++)
        {
            p(xCo, 0, size);
            size += xCo;
            p(0, 0, size);
        }
        for(int i=0; i<yResult; i++)
        {
            p(0, yCo, size);
            size += yCo;
            p(0, 0, size);
        }
        for(int i=0; i<zResult; i++)
        {
            p(xCo, 0, size);
            p(xCo-yCo, yCo, size);
            size += (xCo - yCo);
            p(0, 0, size);
        }
    }
    
    public static void p(int x, int y, int z)
    {
        System.out.println("(" + x + "," + y + "," + z + ")");
    }
    
    public static void main(String[] args)
    {
        linearEquation(5, 3, 17);
    }
}

26 楼 BloodyCoder 2010-09-26  

我一个都不会！不知道考这个题能显示出来什么

25 楼 egmacross 2010-09-26  

能做出这题的人就会创新了？

24 楼 Firklaag 2010-09-26  

长大做IT 写道

dxiao2 写道

我觉得第二个问题从期望的角度出发 应该是17.5 所以选17最接近

正解！
先算第个骰子的期望值,每面的概率都是1/6，单个骰子的期望为
1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6 = 3.5
5个骰子分别随机就是3.5*5=17.5，17或18为最接近的点数

那3个10面的骰子求和呢？，以上公式就不适用了吧

23 楼 长大做IT 2010-09-25  

dxiao2 写道

我觉得第二个问题从期望的角度出发 应该是17.5 所以选17最接近

正解！
先算第个骰子的期望值,每面的概率都是1/6，单个骰子的期望为
1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6 = 3.5
5个骰子分别随机就是3.5*5=17.5，17或18为最接近的点数

22 楼 1927105 2010-09-25  

vaneng 写道

1. 4, 这个程序就是求二进制数中1的个数
2. 组合数学里面的东西，好像叫形式幂级数，
   (x^1+x^2+...+x^6)^5 求x^14, 15, 17 20的系数
3. 0x5248, char 应该先变int
4. 最后一题算是比较有意思的一道题目。
以前见过5升 3升 求2升，不过从来没有考虑过广义的解法
刚才算了半个多小时，算是把思路理清楚了。

假设m>n, k随意。求出k=k%n, a=m,n的最大公因子，if k%a!=0 无解

否则，for(i: 1-n) 存在i，m*i%n=k%n

装水的方法就是先将m倒进n，n满倒掉，知道n不满，将n倒进c； 进行i次
将c里面倒n，n满倒掉，知道n不满，将n倒入c
再将n装满k/n次倒入c中即可。

（就是密码学里面的质数那块的知识）

写的不错，第一道题肯定是对的，后面不知所云

21 楼 polaris1119 2010-09-24  

ywz1984 写道

建议我们成立一个数学与编程的圈子，大家遇到类似的数学问题，我们通过编程方式实现出来。锻炼这样理论和实际相结合，有可以提高算法知识，同时也锻炼了思维逻辑。
大家说好不？

统一，你建一个呗，或者我建也行，不过没建过，还要研究一下怎么建。

20 楼 280511772 2010-09-24  

1+6=7
2+5=7
3+4=7

如果是4个色子我毫不犹豫选14.。但是5个，不知道

19 楼 ywz1984 2010-09-24  

建议我们成立一个数学与编程的圈子，大家遇到类似的数学问题，我们通过编程方式实现出来。锻炼这样理论和实际相结合，有可以提高算法知识，同时也锻炼了思维逻辑。
大家说好不？

18 楼 生活小丑 2010-09-24  

哎.........现在数学都忘得差不多了.........

17 楼 yangguo 2010-09-24  

vaneng 写道

1. 4, 这个程序就是求二进制数中1的个数

2. 组合数学里面的东西，好像叫形式幂级数，
   (x^1+x^2+...+x^6)^5 求x^14, 15, 17 20的系数

3. 0x5248, char 应该先变int
4. 最后一题算是比较有意思的一道题目。
以前见过5升 3升 求2升，不过从来没有考虑过广义的解法
刚才算了半个多小时，算是把思路理清楚了。

假设m>n, k随意。求出k=k%n, a=m,n的最大公因子，if k%a!=0 无解

否则，for(i: 1-n) 存在i，m*i%n=k%n

装水的方法就是先将m倒进n，n满倒掉，知道n不满，将n倒进c； 进行i次
将c里面倒n，n满倒掉，知道n不满，将n倒入c
再将n装满k/n次倒入c中即可。

（就是密码学里面的质数那块的知识）

兄弟很牛啊。应该叫母函数。

16 楼 ywz1984 2010-09-24  

就是5和30的概率相同（均为1或6）
6和29的概率相同（6组合方式为1：4，2：1；29组合方式为6：4，5：1）
类推：概率越来越大（组合方式越来越多），17、18最大且相同，忘了怎么用公式表达了

15 楼 pfans 2010-09-24  

创新工场最近大规模招聘啊。

14 楼 char1st 2010-09-24  

(5+30)/2
.............
17 或 18 符合穷举的结果,都是780个解

13 楼 黯然小伙 2010-09-24  

dxiao2 写道

我觉得第二个问题从期望的角度出发 应该是17.5 所以选17最接近

同意楼上的观点。。
我个人觉得，应该越接近所有点数中间的，几率越大。。
5*6=30
(30-4)/2=13
从5开始算的话，几率最大的应该是4+13=17
不知道对不对。

12 楼 dxiao2 2010-09-23  

我觉得第二个问题从期望的角度出发 应该是17.5 所以选17最接近

11 楼 char1st 2010-09-23  

polaris1119 写道

char1st 写道

第2题是求四元一次方程解的个数吧.

这样会太复杂了吧

   这个看每个人怎么看这题吧,
   如果能用写代码的方式解决,还是很容易的,
   不过我只会最老土的穷举法.