02-深圳市南山区-同行者科技有限公司面试总结

基本信息

时间:2019年7月19日10点30

地点:深圳市南山区高新南七道国家高新技术产业创新中心A座1301;这个A座地图上看不见,最后问保安才知道的,出门在外说话多讲礼貌,多问路,能节省很多麻烦。缺点就是离距离地铁站很远1.3公里,步行要十几分钟,这个天气非常热(深圳好像就没有不热的时候)

公司:深圳市同行者科技有限公司

职位:语音开发工程师

环境:环境很不错,所处的是高新技术产业园,所以在这附近的都是科技、电子行业,比如我就看到了创维的牌子。进了大厦还需要登记,否则你没办法过闸机的。登记的时候也没有怎么为难,基本是留个名字和手机号,身份证号和手机号是可选的,这个是在别的公司见不到的情况。

流程:给HR看简历,可能是根据简历给你发试卷和基本信息调查表。注明试卷和答案纸是分开的,不是直接填在试卷上。与第一家公司“中科软科技股份有限公司”不同的是,这家公司没有让我填杂七杂八的信息调查表,这样以后个人信息泄露的风险就降低了,点个赞。

面试题

面试题我拍了照,我直接上照片:

深圳市同行者科技有限公司

在我面试之前已经有两个老哥在做题了,他俩都是面试Java的。一个老哥说自己有点工作经验;另一个老哥说应届,6月底才来深圳,已经面了7/8家了,但是还没有拿到offer,做题的时候发现他跟我差不多,写不出几题,同是天涯沦落人,哈哈哈,话不多数直接上真题和正确答案。

1. 不使用语言的分割组合函数(如Java的String.split,php的explode和implode)。

1.1字符串按分割串拆分成数组

代码思路:

  1. 利用String的container方法,判断是否包含分隔符号flag
  2. 若包含,则使用indexOf返回分隔符的下标值
  3. 使用String.substring来截取字符串。substring一共有有两种用法,这里使用第二中,也就是从0截取到flag
    1. str.substring(beginIndex) ;从index向后截取所有字符串,包含beginIndex
    2. str.substring(beginIndex, endindex); 向后截取字符串,一直到endIndex。含beginIndex,不含endIndex
  4. 把步骤3截取到干净的字符串,添加到数组集合里
  5. 截取新的str,由于步骤4已经截取了第一个字符串,所以新的str也需要重新截取。方法是利用步骤3的第一种方法。具体代码是:str.substring(index + flag.length() )。原理是:从flag开始截取,但是不包含flag,所以需要加上flag的长度,也就是flag.length(),最后如此循环即可完成截取。
点击查看完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    /**
* TOO: 分割字符串返回ArrayList
*
* @author shanLan misterchou@qq.com
* @date 2019/7/19 22:02
* @return
* 测试字符串 : String str = "asf,123,dsaf,dgasd123,asdfa1,asdfs34,dfas23.-";
*/
public static String[] mySplict(String str, String flag) {
ArrayList<String> al = new ArrayList<String>();
while (str.contains(flag)) {
// 返回标记的下标
int index = str.indexOf(flag);
// 把截取好的字符串存起来
String tmp = str.substring(0, index);
al.add(tmp);
str = str.substring(index + flag.length());
}
// 兜底;若字符串里不包含flag,说明这个字符串不需要切割,那么字节添加到ArrayList里
al.add(str);
// 通过toArray方法,指定数组类型直接转换。
return al.toArray(new String[al.size()]);
}
// ------打印结果------
/*
asf
123
dsaf
dgasd123
asdfa1
asdfs34
*/

1.2实现字符串列表按分割串组合,例如数组:[“ab”,”2”],通过”&&”分隔符,组成新的字符串“ab&&2”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static String mySplict2(String[] str, String flag) {
/*
* 1.先遍历数组,取出每个元素
* 2.判断元素是否为最后一位,若是,则不再加分隔符
* */
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length; i++) {
sb.append(str[i]);
if (i < str.length - 1 ) {
sb.append(flag);
}
}
return sb.toString();
}

2. 找出不大于N的最大质数

质数和素数是同一个东西。质数(又称素数),是指在大于1的自然数中,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为素数(质数)。比1大但不是素数的数称为合数,1和0既非素数也非合数。
素数不是奇数。奇数是不能被2整除的数。比如9是奇数,但不是素数。因为9不能被2整除,所以是奇数,但9有1、3、9三个因数,所以不是素数。

在计算机中,计算整除的常用方法一般使用% 运算,读作取模运算,用法:7 % 2 = 1 。解释: 7 模以 2 ,商为3,余数为1,这就称之为取模。我目前对取模运算的理解是求余数,更加常见的应用场景:

  1. 判别奇偶数
  2. 判别素数
  3. 求最大公约数
  4. 水仙花数
  5. 模幂运算
  6. 《孙子问题(中国剩余定理)》
  7. 凯撒密码

本题是使用取模运算来判别质数,也就是素数。为了便于理解,先列出判别素数的基本思路:

基础版:

  1. 定义循环,数字 i = n ,还要定义数字 j = i - 1,都为自减。且 i 和 j 都要大于 1 (因为质数大于1)
  2. 使用取模运算,每个循环 i % j ,并且判断取模结果是否为 0 ,若为 0 则说明该数字不是一个素数,使用break跳出循环,并进行自减,一直到 j >= 2 时,若还没有跳出循环,那么此时的 i 肯定是一个质数了。因为质数的定义是不包括被1和自身的整除的数。而 j >= 2时,说明 j 到 2之间所有的数字已经遍历完成,这时还没有跳出循环就说明 i 已经符合质数了。
  3. 将符合的数字存入到ArrayList中,利用List集合的顺序存入特性,由于是自减循环,所以第一个存入的质数自然为最大的
  4. 最后使用ArrayList.get(0)取出第一个下标的数,即为不大于N的最大质数
    点击查看完整代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
    * TODO: 求不大于N的最大质数
    *
    * @author shanLan misterchou@qq.com
    * @date 2019/7/24 0:49
    */
    public static int maxPrimeNum(int n) {
    // 用来存质数
    ArrayList<Integer> arr = new ArrayList<>();
    if (n == 2 || n == 1) {
    return n;
    }
    for (int i = n - 1; i > 1; i--) {
    // 比i小1的数
    for (int j = i - 1; j > 1; j--) {
    // 非质数
    if (i % j == 0) {
    break;//跳出冫
    }
    // 只有j小于等于2,并且没有break跳出循环时,此时的i才为质数
    if (j <= 2) {
    // 存入集合中,便于后续取出
    arr.add(i);
    }
    }
    }
    // 利用ArrayList顺序存储的特性,将第一个存入的数字取出。
    // 原因是我们采用自减遍历,所以第一个遍历出来的质数是最大的
    System.err.println("不大于" + n + "的最大质数=" + arr.get(0));
    return arr.get(0);
    }

进阶版:

利用开平方根,来缩数字的范围,从而提高查找的效率。

原理:因为如果它不是质数,那么它一定可以表示成除了1和它本身之外的两个数相乘,这两个数必然有一个小于等于它的平方根。只要找到小于或等于的那个就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
for (int i = 1000; i > 2; i--) {
if (m(i)) {
System.err.println("N内最大的质数:" + i);
break;
}
}
}
public static boolean m(int num){
// 利用JDK的Math的开平方函数,来限定J的范围
for(int j = 2; j<=Math.sqrt(num);j++){
if( num % j == 0 ){
return false;
}
}
return true;
}

3. 1000个数的范围是[0,999],有两个相同的数,请设计算法找出来

既然不限定语言,我一开始想最简单的方法就是利用Java集合Set的特性来完成,事实上这种方法代码量也是最少。这里再来复习下Set的特性:存取无序;不可重复;没有下标。更详细点击这里

HashSet它的Add()添加元素的时候,会有一个Boolean的返回值。若集合中没有找到存在的元素,则可以存入并且返回True,否则返回False,所以利用该特性直接就能判断哪个元素重复了,下面上示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
// 构造一个包含1000个数字的空数组
int arr[] = new int[1000];
// 给数组赋值
for (int i = 0; i < 999; i++) {
arr[i] = i;
}
// 添加一个重复的数字
arr[999] = 888;
System.err.println(isEquals(arr));
}
public static int isEquals(int[] i) {
HashSet<Integer> hashSet = new HashSet<>();
for (int j = 0; j < i.length; j++) {
// 当添加元素返回True时不进入if
if ( !( hashSet.add( i[j] )) ) {
return i[j];
}
}
return -1;
}

4. n个人(编号1 ~ n ) 围成一圈从编号1开始报数,从1报到m,报到m的人出来,下一个人继续从1开始报数。编程求最后一个留下的人的编号。

例如:

如人数n=3,报数 m=4
第一次出队:1
第二次出队:3
最后留下: 2

1. 使用数组和for循环来解题

  1. 创建一个数组peopleFags[],数组长度为总人数,数组的每个元素下标代表每个人,数组的内容表示这个人是否被淘汰。true没有淘汰,false表示已经淘汰

  2. 最开始的时候所有人都没有淘汰,所以这个数组应该全部赋值为true

  3. 数数是从第一个人开始,所以需要定义一个变量count,初始值为0,代表第一个人

  4. 既然是数数,那么肯定要有一个变量记录已经数到了哪个人,所以定义变量index,一开始都是从第一个人开始数数,所以初始值也是0

  5. 还需要定义一个变量,记录剩余的人数,peopleResidue,一开始没有人淘汰,所以它等于总人数

  6. 所有变量定义完成之后,开始循环处理,循环的条件是总人数不小于1,也就是总人数:total > 1为条件

  7. 进入循环后应该判断当前的人peopleFags[index]是不是淘汰了,如没有淘汰,则应该把计数器count++自增一次,随后应该判断count计数器是不是等于报数,因为游戏规则表名等于报数的人要被淘汰,所以当count等于报数时,应该将当前的人赋值为false,既然已经淘汰了,所以要归零。随之还要将剩余人数减1

  8. 最后让当前index下标递进一位,并判断index是否等于总人数,如果等于总人数则表示这一轮数完了,所以应该归零重新开始计数

  9. 循环结束后遍历peopleFags[]数组,把为true的下标加1,就是最后一个人的编号。

    下面是示例代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    public static void main(String[] args) {
    int compult = compult(9, 10);
    if (compult != -1) {
    System.err.println("最后留下来的人是:" + compult);
    }
    }
    /**
    * TODO: 计算循环
    *
    * @param total 总人数
    * @param keyNumber 报数
    * @return int: 最后一个人的编号负
    * @author shanLan misterchou@qq.com
    * @date 2019/7/28 23:33
    */
    private static int compult(int total, int keyNumber) {
    // 长度为total的布尔型数组,该数组的长度为总人数,下标索引表示哪个人,元素内容True表示未淘汰,False淘汰
    boolean[] peopleFlags = new boolean[total];
    // 初始化peopleFlags数组,因为一开始所有人都没有淘汰,自然赋值为true
    for (int i = 0; i < peopleFlags.length; i++) {
    peopleFlags[i] = true;
    }
    // 剩余的人数,一开始没有人被淘汰,所以剩余人数是总人数total
    int peopleResidue = total;
    // 计数器;初始值0,每数一个人则加1,当等于总人数total时归零
    int count = 0;
    // 当前数到哪个人,从0开始计数,代表第一个人
    int index = 0;
    // 开始循环,当剩余人数小于等于1,则说明已经是最后一个人,不进入循环
    // 否则应该不累加计数器,所以跳过。
    while (peopleResidue > 1) {
    // 进入循环后,判断当前的人的peopleFlags[index]是不是true
    if (peopleFlags[index]) {
    // 能进入循环,说明还没有淘汰,所以要累加计数器
    count++;
    // 检查下计数器count,如果等于报数keyNumber,应该归零,因为等于报数的人应该被淘汰出去
    if (count == keyNumber) {
    count = 0;
    // 既然被淘汰,那么他的peopleFlags[index]应该赋值false
    peopleFlags[index] = false;
    // 既然已经淘汰了一个人,那么剩余的总人数应该-1,也就是peopleResidue - 1
    peopleResidue--;
    }
    }
    // 当前人index的下标递进一位
    index++;
    //判断当前人index下标是不是等于总人数total,如果等于则说明这一轮循环结束了,所以要归零从0开始继续循环
    if (index == total) {
    index = 0;
    }
    }
    // while循环结束后,剩余的人数是1,被淘汰的已经标记为false,现在要做的是把没有被淘汰的元素peopleFlags[index] = true 的人下标 + 1
    // 因为在人类中计数是从1开始,而我们写的程序的计数是从0开始,所以要加1
    for (int i = 0; i < total; i++) {
    if (peopleFlags[i]) {
    // 返回没有被剔除的人
    return i + 1;
    }
    }
    return -1;
    }

2. 面向对象解题思路

本题中有两个对象,一个是人People,还有一个是环Circle。

人:

  • 编号
  • 左边的People
  • 右边的People

环:

  • 总人数
  • 第一个人
  • 最后一个人
  • 添加人()
  • 删除人()

一开始,我们的环是空的,所以我们需要往环里添加人。那么人肯定有编号,所以添加人之前要给人加上编号。

接下来我们要创建一个计数器变量count,初始值为0,它主要是记录我们循环了几次,每循环一次等于数了一个人。当计数器count等于报数keyNumber的时候,说明这个人就需要被淘汰了,具体请看下面环Circle对象的代码:

点击查看-环Circle-代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package pojo;
public class circle {
private int total = 0;
private people fristPeople = null;
private people lastPeople = null;
/**
* TODO: 添加一个人到圈里
*
* @param newPeople 新添加的人
* @return void:
* @author shanLan misterchou@qq.com
* @date 2019/7/31 0:45
*/
public void addPeople(people newPeople) {
// 当圈里面的总人数为0
if (total <= 0) {
// 因为圈里没人时,那么刚添加的这个人的是第一个人,也是最后一个人
fristPeople = newPeople;
lastPeople = newPeople;
// 同理,所以这个人的左边、右边,都是这个人。
newPeople.setLeftPeople(newPeople);
newPeople.setRightPeole(newPeople);
} else {
// 如果圈里有人,则把该人加到圈的尾部,也就是将之前最后最后一个人的右边设置为新人。例如:现在新人是编号4
// 1 -> 2 -> 3 -> 4 人员顺序示意
lastPeople.setRightPeole(newPeople);
// 将新人4的左边设置为之前最后那个人,也就是编号3
newPeople.setLeftPeople(lastPeople);
// 将新人的右边,设置为第一个人,也就是编号1
newPeople.setRightPeole(fristPeople);
// 把最后一个人设置为新人
lastPeople = newPeople;
}
total++;
}
/**
* TODO: 删除圈里的人
*
* @param p 被删除的人
* @return void:
* @author shanLan misterchou@qq.com
* @date 2019/7/31 0:58
*/
public void deletPeople(people p) {
if (total <= 0) {
System.err.println("圈里总人数小于等于0 ,不能删除!");
return;
} else if (total == 1) {
// 当圈里只有一个人,此时应该游戏结束,第一个人和最后一个人都是null
fristPeople = lastPeople = null;
} else {
// 1 -> 2 -> 3 -> 4 人员顺序示意
// 当圈中的人不小于等于0、且大于1则开始正常操作
if (p == fristPeople) {
// 如果新人等于第一个人,那么他的右边是则为第一个人。例如删除编号1,删除后编号2将变成第一人
fristPeople = p.getRightPeole();
} else if (p == lastPeople) {
// 如果新人是最后一个人,删除后圈里面的最后一个人将变成他左边的人。例如删除4,最后一个人就是4的左边编号为3的人
lastPeople = p.getLeftPeople();
}
// 代码走到了这里,说明p既不是第一个人,也不是最后一个人,是处于中间的人
// 例如要删除编号为3的人,那么3删除后,2的右边是4,4的右边为2
// 以编号3为例,获取被删除people编号3左边的人编号2
people leftPeople = p.getLeftPeople();
// 获取被删除people编号3右边的人编号4
people rightPeole = p.getRightPeole();
// 将左边编号2的人的右边的人设置为编号3的人
leftPeople.setRightPeole(rightPeole);
// 将编号4的左边的人设置为编号2
rightPeole.setLeftPeople(leftPeople);
}
total--;
}
/**
* TODO: 计算。调用addPeople()和deletePeople()来完成约瑟夫环
*
* @param total 总人数
* @param keyNumber 关键数字,报数
* @return javafx.scene.shape.Circle:
* @author shanLan misterchou@qq.com
* @date 2019/7/31 1:11
*/
public static circle compar2(Integer total, Integer keyNumber) {
circle circle = new circle();
for (int i = 0; i < total; i++) {
people people = new people(i);
// 开始向圈里添加人
circle.addPeople(people);
}
Integer count = 0;
people people = circle.getFristPeople();
while (circle.getTotal() > 1) {
// 每数一个人,计数器加1次
count++;
// 如果计数器等于keyNumber,说明这个人应该被淘汰
if (count.equals(keyNumber)) {
count = 0;
circle.deletPeople(people);
}
// 当people的编号不等于keyNumber的时候,应该当前对象的右边对象赋值给people
people = people.getRightPeole();
}
return circle;
}
public circle() {
}
public circle(int total, people fristPeople, people lastPeople) {
this.total = total;
this.fristPeople = fristPeople;
this.lastPeople = lastPeople;
}
public int getTotal() {
return total;
}
public void setTotal(int total) {
this.total = total;
}
public people getFristPeople() {
return fristPeople;
}
public void setFristPeople(people fristPeople) {
this.fristPeople = fristPeople;
}
public people getLastPeople() {
return lastPeople;
}
public void setLastPeople(people lastPeople) {
this.lastPeople = lastPeople;
}
}

人People代码:

人People代码完整代码
1
2
3
4
5
6
7
public class people {
private Integer id;
private people leftPeople;
private people rightPeole;
// set / get 省略
}
}
主进程Main调用代码:
1
2
3
4
5
6
public static void main(String[] args) {
int total = 10; //定义要添加的人数
int keyNumber = 3; //数到3退出
circle circle = pojo.circle.compar2(total, keyNumber);
System.out.println( total + "个人围成一圈数数,数到" + keyNumber + "的被淘汰,最后剩下的是第" + circle.getFristPeople().getId() + "个人。");
}

3. 使用链表来解题

使用Java集合自带LinkedList来实现,借用LinkedList的Remove()后, 将任何后续元素移动到左侧(从其索引中减去一个元素)的特性实现。并且判断的条件是index 是否等于集合的最后一个下标,如果是,则说明本轮循环已经到尾部了,需要重新开始循环计数了,具体思路:

  1. 创建一个total长度集合,给集合内添加total个数组,从1开始
  2. 定义一个下标index,初始值为0 ,它代表需要删除哪个元素
  3. 定义一个循环,循环的结束条件是小于keyNumber,也就是循环次数= keyNumber - 1 次
  4. 利用 index == size() - 1 ,判断是不是已经数到了最后一个元素,如果是,则需要归零index,从0开始计数
  5. 当跳出循环时,说明此时index符合删除的条件了
  6. 使用remove(index)删除元素,该index元素的后续元素位置都会向左移动,并且索引会-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void main(String[] args) {
Integer total = 10;
Integer keyNumber = 3;
// 创建链表
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < total; i++) {
// 给链表里添加编号,从1开始
list.addLast(i + 1);
}
// 下标
int index = 0;
// 当链表的长度大于1时
while (list.size() > 1) {
// 循环,限定条件是小于keyNumber,例如keyNumber=3,所以每次循环是3-1次
for (int i = 1; i < keyNumber; i++) {
// 如果下标等于列表长度-1
int length = list.size() - 1;
// 如果下标等于最大长度-1,说明已经数到了最后一个人了,那么就需要从头开始数,也就是归零。因为最后一个人的下标就是size()-1
if (index == length) {
// 下标归零
index = 0;
}
// 防止越界
else if (index == list.size()) {
index = 1;
} else {
// 下标递进
index++;
}
}
// 删除指定下标;当上面循环结束以后,i < keyNumber跳出循环时,index++的数字正好符合游戏规则,
// 因为index是随着 i 在进行自增。例如keyNumber = 3,那么index的数字依次是:2,
// 下一轮按理说是5该删除,但是5这步骤不需要累加index了,直接走到了删除的代码,所以第二轮是删除了下标index= 4的元素
// 同上,应该累加到7的时候删除元素,但是此时代码跳到了删除元素那样,所以index没有累加,此时index是7
list.remove(index);
}
System.out.println(total + "个人围成一圈数数,数到" + keyNumber + "的被淘汰,最后剩下的是第" + list.get(0) + "个人。");
}

参考自:约瑟夫环的几种实现方式 - 菜鸟小站 - OSCHINA - https://my.oschina.net/jack90john/blog/1791110

5. 26个字母a-z,找出所有字母的组合,a,b,c,ab,abc,a~z都是一个组合(顺序无关)

待补充