链家2018招聘京外笔试题（Android研发工程师）

写在前面

  有段时间没有写博客了。最近主要是在深入学习Android和准备校招。

  前段时间投了不少简历出去，陆陆续续也经历了几场笔试面试。趁着这几天开学的空闲，梳理一下周六晚做的链家笔试题。

  链家在房源信息方面做得确实是国内首屈一指，我在上海实习期间就已经切切实实体味到了，真的是，感觉走到哪儿都有它家的门店。所以这次就投了一波简历来尝试一下。

  总的来说，链家笔试的题目中规中矩，2个小时，20道选择题+3道编程题。选择题全是Android相关的基础知识，有些Android编程经验的都能做个八九不离十。编程题则是重点考察dp，难度还是有的。我只A了2.8道，有一题多重背包，dp解的，复杂度超了，只过了82%。下面来贴一下题目和个人见解，欢迎有能力全A的大神指教~

笔试题

  笔试时间：2017年09月02日 19:00–21:00
  考试类型：链家2018招聘京外笔试（Android研发工程师）

01.分小球问题

题目描述：

题目解析：

  这题说是往杯子里倒水，实际上，就是高中数学接触的那种分小球问题，只是换了种说法。我在此就将其称为分小球问题了吧。

  本题可以转化为这样的题目：有n个相同的小球，m个相同的盒子，要求每个盒子里面至少有k个小球，问一共有多少种放法？（本题的k=0）

  思路：使用二维数组dp[i][j]表示i个小球放入j个盒子的方法数。

  因为盒子可以为空，我们分两种情况来考虑：
  ①球数最少的盒子为空：那么就相当于，有一个盒子不能放球，即把i个小球放入j-1个盒子里面，就是 dp[i][j-1]。
  ②球数最少的盒子不为空：那么就相当于每个盒子里面都至少有一个小球，我们就预先把每个盒子里面放入一个小球好了，有 dp[i-j][j]。

  所以，递推公式为 dp[i][j] = dp[i][j-1] + dp[i-j][j]，这种情况在 i>=j时成立。而当 i

Java解答：

import java.util.Scanner;public class Main {public static final int maxN = 11;public static int[][] dp = new int[maxN][maxN];private static void init(){for(int i=1;i<=10;i++) {dp[0][i]=1;dp[i][1]=1;  }for(int i=1;i<maxN;i++)  for(int j=2;j<maxN;j++)  if(j<=i)dp[i][j]=dp[i][j-1]+dp[i-j][j];  elsedp[i][j]=dp[i][i]; }public static void main(String[] args) {init();Scanner in = new Scanner(System.in);int num = in.nextInt();for (int i=0; i<num; i++) {int m = in.nextInt();int n = in.nextInt();System.out.println(dp[m][n]);}in.close();return;}}

02.两端取数问题

题目描述：

题目解析：

  这题描述有点长，读了好一会儿才明白题意。（PS:吐槽一句题目：食物放越久越值钱？你是想卖82年的黄焖鸡呢，还是69年的凤爪啊？）

  整理一下题意：给定一个正整数的数组，表示一列货物的价值。第1天起，我们每天可以从最左或最右端取一个数，货物的售价=天数*货物价值。要求出这批货物最多可以卖多少钱？

  这题和上面那题一样。满满的dp感。

  假定货物总个数为 num。
  我们的思路还是建立一个二维数组 dp[x][y]，表示x~y这段货物 num天的最大售卖价格。那么有：
  ①初始化：dp[i][i]在num天的最大售价就是在第num天将其出售，于是有dp[i][i] = arr[i] * num;
  ②对于每个dp[x][y]，它的值等于 max(最后卖arr[x]的最大售价，最后卖arr[y]的最大售价)。 而最后卖arr[x]的最大售价为: (num-y+x) * arr[x] + dp[x+1][y], 最后卖arr[y]的最大售价为：(num-y+x) * arr[y] + dp[x][y-1]。
  即：dp[x][y] = Math.max((num-y+x) * arr[x]+dp[x+1][y], (num-y+x) * arr[y]+dp[x][y-1])。

  最后，dp[0][num-1]即是题目所求的 num天所有货物的最大售价。

Java解答：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int num = in.nextInt();int[] arr = new int[num];for (int i=0; i<num; i++) {arr[i] = in.nextInt();}in.close();int[][] dp = new int[num][num];for(int i=0; i<num; i++) {dp[i][i] = arr[i] * num;}for (int dis=1; dis<num; dis++) {// dis means y-xfor (int x=0; x<num-dis; x++) {dp[x][x+dis] = Math.max((num-dis)*arr[x]+dp[x+1][x+dis], (num-dis)*arr[x+dis]+dp[x][x+dis-1]);}}System.out.println(dp[0][num-1]);}}

03.多重背包问题

题目描述：

题目解析：

  这是典型的多重背包问题。因为最后没什么时间了，用c++写的朴素dp，但是复杂度太高，只过了82%。后来在网上找了一下解法，大家可以参考：P03 多重背包问题

C++解答

  给大家贴上我的c++弱鸡dp解，仅供参考，复杂度有待改进：

    #include <iostream>#include <vector>#include <algorithm>#include <numeric>#include <functional>#include <math.h>#include <string>#include <stack>#include <queue>#include <list>#include <set>#include <unordered_set>#include <unordered_map>#include <regex>#include <time.h>#include <iomanip>typedef unsigned int uint;using namespace std;/* 动态规划 */int DPKnapsack(uint c, const uint n, uint &bestV, const vector<uint> &w, const vector<uint> &v, const vector<uint> &x){   // w体积 v价值 s数量vector<vector<uint>> dp(n + 1, vector<uint>(c + 1, 0));int i, j, cur, k;// 动态规划int temp;for (i = 1; i <= n; i ++){for (j = 1; j <= c; j ++){for (k = 0; k <= x[i]; k ++){temp = j - k * w[i];xxif (temp >= 0){cur = dp[i - 1][temp] + k * v[i];dp[i][j] = dp[i][j] > cur ? dp[i][j] : cur;}else{break;}}}}bestV = dp[n][c];return 0;}int main(){// n , vuint n, v;while (cin >> n >> v){vector<uint> ws, ss, xs;uint m, w, s;ws.push_back(0);ss.push_back(0);xs.push_back(0);for (int i = 0; i < n; ++ i){cin >> m >> w >> s;ws.push_back(w);ss.push_back(s);xs.push_back(m);}uint bestS = 0;DPKnapsack(v, ws.size() - 1, bestS, ws, ss, xs);cout << bestS << endl;}return 0;}