某互联网公司2014 Java工程师面试试题

高校俱乐部 java工程师 面试题 

CSDN-木水辰

毕业生北京邮电大学

本题目由某互联网公司系统架构师提供,用于考察Java工程师职位面试候选者的入职资格。

同学们,这道题目很简单,如果你能控制自己不在第一时间去依赖搜索引擎,不到处搜罗答案,而是静下心来,仔细读题,思考,然后亲手写下属于自己的代码,我们会竖起大拇指,开心的对你说:你是最棒的。thumbs_up


题目描述:

在A,B两个城市之间设有N个路站(如下图中的S1,且N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。
A,B的一条通路是指:从A出发,可经过任一路段到达S1,再从S1出发经过任一路段,…最后到达B。通路上路段距离之和称为通路距离(最大距离≤1000)。当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。
例如:下图所示是当N=1时的情况:

从A到B的通路条数为6,但因其中通路5+5=4+6,所以满足条件的不同距离的通路条数为5。

数据结构:             

N记录A,B间路站的个数                                     

D[I][0]记录第I-1到第I路站间路段的个数                                   

 D[I][1],D[I][2]……记录每个路段距离

G[X]标记长度为X的通路是否可能

B数组在穷举过程中记录当前路

B[I]表示第I-1到第I路站之间选择哪一条路段


算法提示:

本题采用穷举算法,穷举所有可能的路径,求出它们的长度,并在一标记数组中标记该长度为可能,最后计算所有的可能标记个数。

穷举时采用回溯法,最初从11……111这样的路径开始,每次都从最后一个路站开始往前寻找当前路径可修改的地方,直到当前路径变得无法修改为止。


答题提示:

面试官通过这道题,考察学生对数据结构, 二维数组的熟悉程度,以及在语法、语义、语用以及算法优化方面的能力。

程序书写过程中需要注意:

- 语法:语法的正确书写,包括格式
- 语义:对循环、分支等语义的理解与掌握
- 语用:对变量命名、表达式及语句的组合使用
- 算法优化:如果要提高运行效率,可以在算法上寻找突破口,也可以采用空间换时间的通用原则。

同学们直接回复本贴,贴出自己的解题代码,正确答案会在每天18:00(答案开放时间:2014.04.30 - 2014.05.11,不含周末及节假日)通过你们在高校俱乐部的注册邮箱发送给你们。

回帖方法:

- 成为俱乐部编程挑战群成员:点击屏幕上方,【俱乐部编程挑战群】旁边的【加入】按钮即可一键式加入;

- 如果还不是高校俱乐部会员,首先点击这里注册:会员注册

创建
2014-04-29
浏览
88450次
最新回复
2015-01-25
回复
26
6

某超大号的阴阳玉

毕业生桂林电子科技

 

java完全不懂。只好写伪代码一样的东西……

public void Search(int Node,int NodeId,int totalLength)

{
    if(N>Node)
 {
  for(int i=0;i<D[Node][0];i++)
  {
   search(Node+1,i+1,totalLength+D[Node][NodeId]);
  }
 }
 else{
  totalLength+=D[Node][NodeId];
  G[totalLength]=true;
 }

}

 

总之……这回纯属打酱油。

 

2014年04月30日 18:02:50

chengxiang9207

毕业生沈阳职业技术

G[X]标记长度为X的通路是否可能 这句没怎么理解

以下就是根据我的理解,还没考虑到运行效率

public class T {

    public List G=new ArrayList();

    public int num;

    public void go(int[][] D, int i, int[] B) { 

        if (i == D.length) {

            num=0;

            for (int j : B) {

            num=num+j;

            }

            if(!G.contains(num)){

                G.add(num);

            }

            return;

        }

        else {

            for (int j = 1; j <= D[i][0]; j++) {

            B[i] = D[i][j];

            go(D, i + 1, B);

            }

        }

    }

    public static void main(String[] args) {

        int[][] D = {{3,5,7,4},{2,6,5}};

        T t=new T();

        t.go(D, 0, new int[D.length]);

        System.out.println("所以满足条件的不同距离的通路条数为"+t.G.size());

    }

}

2014年04月30日 19:18:55

chengxiang9207

毕业生沈阳职业技术

格式呢 

2014年04月30日 19:21:04

无敌大饺子

毕业生浙江经贸职业

 

可以用递推的方法来做.

设点A为0, 点B为n + 1, dp[i][j]表示从A点到i点是否存在一条距离总和为j的路径.

那么有dp[i + 1][j + len] = true 满足dp[i][j] = true, len为一条从i到i + 1边的长度.

复杂度约为O(路站数*两点间最多边数*最大路径距离和).

贴下C++的代码,题目里没有输入输出格式,自己编了一些规则.

其实程序里还可以加一些常数上点优化,如第二层循环,j只需要循环到A点到i点的最大通路距离和就够了.

#include <cstdio>
#include <memory.h>
#include <vector>
using namespace std;
const int MAX = 1001;//路径总和最大值

bool dp[103][MAX];//dp[i][j]表示从A点到i点是否存在距离总和为j的路径
vector<int>g[103];//g[i]存放点i到点i + 1的边

int main(int argc, char const *argv[]){
    int n, ans = 0;
    scanf("%d", &n);//n为路站数量,0表示A点,n + 1表示B点
    for(int i = 0; i <= n; ++i){
        int m;//m表示点i到点i + 1的边数量
        scanf("%d", &m);
        for(int j = 0; j < m; ++j){
            int len;
            scanf("%d", &len);    
            g[i].push_back(len);
        }
    }

    dp[0][0] = true;//A点到A点距离为0的路径肯定是存在的
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j < MAX; ++j){
            if(dp[i][j] == true){
                for(int k = 0; k < g[i].size(); ++k){
                    int len = g[i][k];
                    dp[i + 1][j + len] = true;
                }
            }
        }
    }

    for(int i = 0; i < MAX; ++i){
        if(dp[n + 1][i] == true){
            ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

2014年05月01日 16:43:58

a574939970

毕业生北京城市学院

当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)

import java.util.HashSet;

import java.util.Set;

 

public class TestNode1 {

    static Set setG = new HashSet();// 用来装不同的 可行的 通路长度

 

    public static void main(String[] args) {

        int[] d4 = { 843 };

        int[] d3 = { 12 };

        int[] d2 = { 10984 };

        int[] d1 = { 5810 };

        Node n5 = new Node(nullnull);// 终点

        Node n4 = new Node(d4, n5);

        Node n3 = new Node(d3, n4);

        Node n2 = new Node(d2, n3);

        Node n1 = new Node(d1, n2);

 

        search(n1, n3, 0);

        System.out.println(setG);// 输出可行的通路长度

    }

 

    static void search(Node start, Node end, int dis) {

        if (start.next != null) {

            for (int distance : start.distanceToNext) {

                int temp = dis + distance;

                search(start.next, end, temp);

            }

        else {

            setG.add(dis);

        }

    }

 

}

 

class Node {

    int[] distanceToNext;// 到下一个节点的各个距离

    Node next;// 下一个节点

 

    public Node(int[] d, Node next) {

        distanceToNext = d;

        this.next = next;

    }

 

}

2014年05月04日 14:23:12

a574939970

毕业生北京城市学院

import java.util.HashSet;

 

public class TestNode1 {

 

    public static void main(String[] args) {

        int[][] distance = { { 574 }, { 65 } };

        HashSet<Integer> setG = new HashSet<Integer>();

 

        for (int i = 0; i < distance.length; i++) {

            HashSet<Integer> temp = new HashSet<Integer>();

            temp.addAll(setG);

            setG.clear();

            for (int dd : distance[i]) {

                if (i == 0) {

                    setG.add(dd);

                }

                for (int d : temp) {

                    setG.add(d + dd);

                }

            }

        }

 

        System.out.println(setG);

    }

}

2014年05月05日 10:39:13

a574939970

毕业生北京城市学院

迭代的

2014年05月05日 10:39:55

Gwanwlw

毕业生西北大学

# -*- coding:utf-8 -*-
import time
starttime = time.clock()
f = open("E:\\csdn\\test.txt", "r")
#n = input()                               #一共n个路站
n = int(f.readline())
L = [0]                                   #
for i in range(n+1):                      #n个路站对应n+1段路  
  #a = map(int, raw_input().split())       #a表示第i段路的所有路径长度
  a = map(int, f.readline().split())
  L = set([lx+ax for lx in L for ax in a])#递推去掉等长路径,构造新的路径   
print len(L)
endtime = time.clock() 
print endtime-starttime
f.close()

 

随机生成100段路,每段路20个分支的数据运行了下,花了37s

递推:F(n)记录前n段路的不同路径长度,然后递推F(n+1)

2014年05月05日 18:25:52

椰树海岛

指导老师北京理工大学


import java.util.HashSet;
import java.util.Set;

public class MyNode {

    public static void main(String[] args) {
        int[] v4 = { 5, 4, 7 };
        int[] v3 = { 6, 3 };
        int[] v2 = { 1, 2 };
        int[] v1 = { 8, 9 };
        Node n5 = new Node(null, null);// 从终点开始
        Node n4 = new Node(v4, n5);
        Node n3 = new Node(v3, n4);
        Node n2 = new Node(v2, n3);
        Node n1 = new Node(v1, n2);

        Set<Integer> sets = new HashSet<Integer>();// 可行的通路距离
        MyNode myNode = new MyNode();
        myNode.test(n3, n4, 0, sets);
        System.out.println(sets);// 打印看看
        sets.clear();
        myNode.test(n2, n4, 0, sets);
        System.out.println(sets);// 打印看看
    }

    /**
     * 计算路径
     * @param start
     * @param end
     * @param dis
     * @param sets
     */
    public void test(Node start, Node end, int dis, Set<Integer> sets) {
        if (start.next != null) {
            for (int n : start.toNext) {
                int temp = dis + n;
                test(start.next, end, temp, sets);
            }
        } else {
            sets.add(dis);
        }
    }

}

// 用树结构来表示
class Node {
    int[] toNext;// 到下一个节点的各个距离
    Node next;// 下一个节点

    public Node getNext() {
        return next;
    }

    public Node(int[] toNext, Node next) {
        this.toNext = toNext;
        this.next = next;
    }

}

结果是否满足?

[7, 8, 10, 11, 13]
[8, 9, 10, 11, 12, 13, 14, 15]

2014年05月05日 22:58:33

剑圣风暴

毕业生西南大学

搞了一天 总算大概先穷举出来了。。

 

#include <stdio.h>
#include <stdlib.h>
#include<string.h>


const int N =3;


int D[N][21]={{3,2,3,5},  //D[0]
            {2,4,9},      //D[1]
            {2,6,7}};     //D[2]

int B[N];

int *sum=NULL;


void fun(int n) //路段个数
{
    static int index = 0;
    if(n==-1)
    {
        for(int j=0;j<N;j++)
        {
            sum[index]+=B[j];
        }
        index++;
        return;
    }
    for(int i=1;i<=D[n][0];i++) //各个路段里面路的条数
    {
        B[n] = D[n][i]; //得到当前距离
        fun(n-1);        
    }
}


int main(void)
{    

    int RoadNum=1;
    for(int i=0;i<N;i++)
    {
        RoadNum *=D[i][0];
    }

    sum = (int *)malloc(sizeof(int)*RoadNum);//

    memset(sum,0,RoadNum*(sizeof(int)));

    fun(N-1);


    for(int m=0;m<RoadNum;m++)
    {
        printf("%d ",sum[m]);
    }

    free(sum);
    return 0;
}

 

2014年05月07日 08:25:41

Purple_eye

毕业生福建农林大学

//不知道对不对。。感觉如果要记录的话b数组应该是二维的。。

import java.util.Scanner;
class Text
{
    public static void main(String[] agrs)
    {
        Scanner input=new Scanner(System.in);
        int n;
        int[][] d; 
        n = input.nextInt();
        d = new int[n+1][];
        for(int i = 0;i < n+1; i++)
        {
            int c;
            c = input.nextInt();
            d[i] = new int[c+1];
            d[i][0] = c;
            for(int j = 1;j <= c; j++)
            {
                d[i][j]= input.nextInt();
            }
        }
        int numOfLead = getLead(d);
        System.out.println(numOfLead);
    }
    public static int getLead(int[][] d)
    {
        int[] g = new int[1005];
        g[0]=1;
        for(int i = 0;i < d.length; i++)
        {
            int[] temg = new int[1005];
            for(int j = 0;j < d[i][0]; j++)
            {
                for(int k = 0; k <= 1000; k++)
                {
                    if(g[k] == 1)
                    {
                        temg[k+d[i][j]]=1;
                    }
                }
            }
            g=temg;
        }
        int tab = 0;
        for(int i = 0;i < 1005; i++)
        {
            if(g[i] == 1)
                tab++;
        }
        return tab;
    }
}

2014年05月07日 16:22:16

Elmman

毕业生中南大学

public class CountRoad{
    public static void main(String[] args){
        int N = 1;
        int[][] D = {{},{3,5,7,4},{2,6,5}};
        int number = count(N,D);
        System.out.println("A到B的通路数为:"+number);
    }
    public static int count(int N,int[][] D){
        boolean[] G = new boolean[1000];
        int[] B = new int[100];
        int number = 0;
        traversal(N+1,D,G,B);
        for(boolean n:G){
            if(n){
                number++;
            }
        }
        return number;
    }
    public static void traversal(int node,int[][] D,boolean[] G,int[] B){
        if(node>0){
            for(int i=1;i<=D[node][0];i++){
                B[node] = D[node][i];
                traversal(node-1,D,G,B);
                int X = calculateDistance(B);
                G[X]=true;
                System.out.println(X);
            }
        }
    }
    public static int calculateDistance(int[] B){
        int X = 0;
        for(int n:B){
            X+=n;
        }
        return X;
    }
}

2014年05月09日 11:05:31

fengfujie

毕业生黑龙江大学

#include <stdio.h>
#include <stdlib.h>
#include<string.h>


const int N =3;


int D[N][21]={{3,2,3,5},  //D[0]
            {2,4,9},      //D[1]
            {2,6,7}};     //D[2]

int B[N];

int *sum=NULL;


void fun(int n) //路段个数
{
    static int index = 0;
    if(n==-1)
    {
        for(int j=0;j<N;j++)
        {
            sum[index]+=B[j];
        }
        index++;
        return;
    }
    for(int i=1;i<=D[n][0];i++) //各个路段里面路的条数
    {
        B[n] = D[n][i]; //得到当前距离
        fun(n-1);        
    }
}


int main(void)
{  

    int RoadNum=1;
    for(int i=0;i<N;i++)
    {
        RoadNum *=D[i][0];
    }

    sum = (int *)malloc(sizeof(int)*RoadNum);//

    memset(sum,0,RoadNum*(sizeof(int)));

    fun(N-1);


    for(int m=0;m<RoadNum;m++)
    {
        printf("%d ",sum[m]);
    }

    free(sum);
    return 0;
}

2014年05月09日 14:01:15

老萨

毕业生西安工程大学

这题一看第一眼觉得应该使用递归去做。

如下递归代码。


    public  void findRoad(int node,int distance){
        if(node==N+1)
        {
            if(distance>MAX_LOAD_SUM)
                return;
//            System.out.println(distance);
//            System.out.println(resultSet.size());
            resultSet.add(distance);
//            G[distance]=1;
            return;
        }
        for(int j=1;j<=D[node][0];j++){
//            System.out.println(node);
            B[node]=j;
            findRoad(node+1, D[node][j]+distance);
        }
    }

当结点数N稍微大一点,结点之间的通路稍微多一点,程序就慢的不像话了。

接着就是迭代代替递归。


    public void findRoadWithFor(){
//        int a[]=D[0];
        int a[]={};
        for(int i=0;i<N+1;i++){
            a=findSumRoadDistance(a,D[i]);
        }
        System.out.println("结果2:"+a.length);
    }
    /**
     * 前一个路段的所有路长,和后一个路段的所有路长两两相加
     * 去除重复
     * */
    public int[] findSumRoadDistance(int a[],int d[]){
        Set<Integer> set=new HashSet<Integer>();
        if(a.length==0){
            for(int j=1;j<d.length;j++)
                set.add(d[j]);
        }else {
            for(int i=0;i<a.length;i++){
                for(int j=1;j<d.length;j++)
                    set.add(a[i]+d[j]);
            }
        }
        
        Integer objects[]=(Integer[])set.toArray(new Integer[0]);
        int result[]=new int[objects.length];
        for(int i=0;i<result.length;i++)
            result[i]=objects[i];
        return result;
    }


运行时间很乐观,100结点下,通路20个,t<100ms~

Over!

2014年05月09日 21:00:41

者望守想梦

毕业生中山大学

 

不好意思,想写成C++的,result函数用递归实现遍历,isExist数组一开始全部初始化为false,遍历过程中找到存在一条长度为length的路径时就把isExist[length]赋值为true。传入参数解释:n为路站个数加1(m个路站其实有m+1个路段选择);numOfPath存每个路段的不同的路径数目;dis二维数组存放每一路径具体长度;current这个值存放当前已到达的第几(从0开始计时)路段。一看题目就知道要深度优先搜索,于是马上用递归来实现,一开始以为用了递归就以为可以省了自己回溯的麻烦,但其实不是这样,还是需要回溯操作,因为已经过路径总长度需要回溯取值(不可能一直把total值递增)。最后,我用一个栈来跟踪递归,保证每次可以准备地从栈顶中取到已经过路径总长度。下面程序中没有main函数,但已经过测试,应该不会错吧。

#include<stack>
using namespace std;
bool isExist[1001];
int total = 0;
stack<int> s;
int getNowScore()
{
    if(s.empty())
        return 0;
    else return s.top();
}
void result(int n, int numOfPath[], int dis[][21], int current)
{
    for(int i = 0; i < numOfPath[current]; i++)
    {
        if(i == 0)
        {
            total = getNowScore() + dis[current][i];
            s.push(total);
        }
        else
        {
            s.pop();
            total = getNowScore() + dis[current][i];
            s.push(total);
        }
        if(current < n)
        {
            result(n, numOfPath, dis, current + 1);
        }
        else
        {
            isExist[total] = true;
        }
        if(i == numOfPath[current] - 1)
            s.pop();//回溯到上一级
    }
}

 

2014年05月11日 16:47:39

老萨

毕业生西安工程大学

你针对你的程序 

生成的数据进行测试

时间消耗如何?

2014年05月12日 18:40:28

者望守想梦

毕业生中山大学

我用的小数据,就没去计算时间消耗了,反正就是全部路径跑一遍,应该都差不多把

2014年05月12日 18:45:07

JackieTan

毕业生武汉大学

 

 

题目解读:

1、题目的意思理解了,但是题目没有给出明确的输入输出格式要求;

2、题目给出的要求很费解,如果你给定了路径信息D,那么记录A,B间路站个数的N也就有了,N是要最后输出吗?还有用D[I][0]记录路段的个数,但是D[I]本身的长度不就是路段的个数么?这样反而导致信息冗余而且程序处理起来很不方便。当然上述两者如果是作为输出的要求那就另当别论了;

3、很典型的给出“递推式”求“通式”,Sn-1—〉Sn的通路给定,求S0(A)到Sn的通路;

4、因为没太看出题目的要求,所以就默认为仅输出不同距离的通路总数。

思路:

1、算法上,最先想到的是用递归实现,据说递归的效率低于循环,后期可以考虑用循环改写;

2、不打算自己设计存储结构,暂时借助java已有的HashSet类。

代码:

import java.util.HashSet;
public final class Client{
    
    /**题目给出的demo数据作为默认值**/
    static int[][] D = new int[][]{{3,5,4,7},
                                   {2,6,5}
                                  };
    
    public static void main(String[] args)
    {        
        HashSet<Integer> A_B = foo_N(D.length-1);
        
        System.out.println(A_B.size());        
    }
    
    /**Sn-1—〉Sn,相当于实现递推式**/
    static HashSet<Integer> foo(int n, HashSet<Integer> S_n_1)
    {
        HashSet<Integer> S_n;
        
        if(S_n_1 == null)
        {
            S_n = new HashSet<Integer>(D[n].length);
            for(int i=1; i<D[n].length; i++)
            {
                S_n.add(D[n][i]);
            }
            return S_n;
        }
        
        /**HashSet的初始容量为A到S_n_1通路数乘以S_n_1—〉S_n通路数**/
        S_n = new HashSet<Integer>(S_n_1.size()*(D[n].length-1));
        
        for(int i=1; i<D[n].length; i++)
        {
            for(int cell : S_n_1)
            {
                S_n.add(cell + D[n][i]);
            }
        }
        
        return S_n;
    }
    
    static HashSet<Integer> foo_N(int N)
    {
        if(N == 0)
        {
            return foo(N, null);
        }
        
        HashSet<Integer> S_N_1 = foo_N(N-1);
        
        return foo(N, S_N_1);
    }
}

 

 

2014年05月23日 16:13:29

大漠小帆

毕业生武汉理工大学

请问现在还发答案不?搞不定啊

2014年05月29日 16:52:23

CSDN-木水辰

毕业生北京邮电大学

你需要先回帖写出自己的思路和代码,然后发送邮件到studentclub@csdn.net,邮件标题写明【某互联网公司2014 Java工程师面试试题】,并在邮件中说明你的CSDN ID,索取正确答案。

2014年05月29日 16:56:03
Top_arrow