一家公司让做 4 个面试题，投入不少精力做完之后，就回了句代码风格不规范，再问就没回应了。不知道具体哪里不规范应该怎样改进？

2020-04-10 22:04:59 +08:00
 sxxkgoogle

一家公司让做 4 个面试题，投入不少精力做完之后，就回了句代码风格不规范，再问就没回应了。不知道具体哪里不规范应该怎样改进？贴出来题目和我的答案，请大家指点赐教。

第一题, TreeNode 查询 已知有如下⼀一个树状数据结构：

let tree = {
    id: '1',
    label: 'first',
    children: [
        {
            id: '2',
            label: 'second'
        },
        {
            id: '3',
            label: 'third',
            children: [
                {
                    id: '4',
                    label: 'fourth'
                },
                {
                    id: '5',
                    label: 'fifth'
                }
            ]
        }
    ]
};

请实现⼀一个查询函数，通过输⼊入 Tree 的 Root Node 和 Id，返回与其匹配的节点，函数原型如 下（注意：请不不要在函数内部直接⽤用 console.log 打印出来）：

findNodeById(root: TreeNode, id: string): TreeNode;

这是第一题我的答案（虽然题目不是 java 的，但他们邮件里提到可以用任意语言作答）：

public class GetTreeNode {
	public static void main(String[] args) {
		String json1 = "{\r\n" + 
				"    id: '1',\r\n" + 
				"    label: 'first',\r\n" + 
				"    children: [\r\n" + 
				"        {\r\n" + 
				"            id: '2',\r\n" + 
				"            label: 'second'\r\n" + 
				"        },\r\n" + 
				"        {\r\n" + 
				"            id: '3',\r\n" + 
				"            label: 'third',\r\n" + 
				"            children: [\r\n" + 
				"                {\r\n" + 
				"                    id: '4',\r\n" + 
				"                    label: 'fourth'\r\n" + 
				"                },\r\n" + 
				"                {\r\n" + 
				"                    id: '5',\r\n" + 
				"                    label: 'fifth'\r\n" + 
				"                }\r\n" + 
				"            ]\r\n" + 
				"        }\r\n" + 
				"    ]\r\n" + 
				"}";

		JSONObject jObject1 = new JSONObject(json1);
		String id = "2";
		JSONObject returnNode = findNodeById(jObject1, id);
		System.out.println(returnNode);


	}

	private static JSONObject findNodeById(JSONObject jObject1, String id) {
		JSONObject returnNode = null;
		for (int i = 0; i < jObject1.names().length(); i ++) {
			String key = jObject1.names().getString(i);
			if (key.equals("id")) {

				String value = jObject1.getString(key);
				if (((String) value).equals(id)) {
					returnNode = new JSONObject(jObject1.toString());
					return returnNode;
				}
			} else {
				Object value = jObject1.get(key);
				if (returnNode == null) {
					returnNode = handleValue(value, id);					
				} else {
					handleValue(value, id);
				}
			}
			
		}
		return returnNode;
		


	}

	private static JSONObject handleValue(Object value, String id) {
		JSONObject returnNodeh = null;
		if (value instanceof JSONObject) {
			returnNodeh = findNodeById((JSONObject) value, id);
		} else if (value instanceof JSONArray) {
			returnNodeh = handleJSONArray((JSONArray) value, id);
		}
		return returnNodeh;

	}

	private static JSONObject handleJSONArray(JSONArray jsonArray, String id) {
		JSONObject returnNodea = null;
		for (int i = 0; i < jsonArray.length(); i ++) {
			if (returnNodea == null) {
			returnNodea = handleValue(jsonArray.get(i), id);
			} else {
				handleValue(jsonArray.get(i), id);
			}
		}
		return returnNodea;

	}
}

第二题：学⽣生按成绩分组 实现⼀一个 groupBy 函数，将学⽣生按照成绩等级进⾏行行分组。

// 成绩等级分为 A 、B 和 C 三级
function getGrade(score){
return score < 60 ? 'C' : score < 80 ? 'B' : 'A';
};
// 学⽣生及其成绩
let students = [
{name: '张三', score: 84},
{name: '李李四', score: 58},
{name: '王五', score: 99},
{name: '赵六', score: 69}
];

实现该函数：groupBy(students); 输出为：

{
'A': [
{name: '王五', score: 99},
{name: '张三', score: 84}
],
'B': [{name: '赵六', score: 69}],
'C': [{name: '李李四', score: 58}]
}

第二题答案：

public class GroupByStudents {
	public static void main(String[] args) {

		String input = "[\r\n" + "{name: '张三', score: 84},\r\n" + "{name: '李李四', score: 58},\r\n"
				+ "{name: '王五', score: 99},\r\n" + "{name: '赵六', score: 69}\r\n" + "];";

		JSONArray students = new JSONArray(input);
		JSONObject studentGroups = groupBy(students);
		System.out.println(studentGroups);

	}

	private static String getGrade(int score) {
		return score < 60 ? "C" : score < 80 ? "B" : "A";
	}

	private static JSONObject groupBy(JSONArray students) {
		JSONObject studentGroups = new JSONObject("{}");
		for (int i = 0; i < students.length(); i ++) {
			JSONObject student = students.getJSONObject(i);
			int score = student.getInt("score");
			String grade = getGrade(score);
			studentGroups.append(grade, student);
			
		}

		return studentGroups;
	}

}

第三题：字符串串 Parse 请设计⼀一个字符串串 parse 函数，可以将输⼊入的字符串串分解为对应的树状结构，⽐比如：

// 例子 1
let input = 'int';
let result = parse(intput);
// result 结果为：
// {
// type: 'int'
// };

// 例子 2
let input = 'Array<bool>';
let result = parse(intput);
// {
// type: 'Array',
// typeArgs: [{
// type: 'bool'
// }]
// };

// 例子 3
let input = 'Array<Array<string>>';
let result = parse(intput);
// {
// type: 'Array',
// typeArgs: [{
// type: 'Array',
// typeArgs: [{
// type: 'string'
// }]
// }]
// };

// 例子 4
let input = 'Map<string, Array<bool>>';
let result = parse(intput);
// {
// type: 'Map',
// typeArgs: [{
// type: 'string'
// }, {
// type: 'Array',
// typeArgs: [{
// type: 'bool'
// }]
// }]
// };

同理理，该 parse 函数可以分解如下任意情况，⽐比如：

"int"
"string"
"bool"
"Array<int>"
"Array<Array<int>>"
"Array<Array<Array<int>>>"
"Map<string, Map<string, bool>>"
"Map<Map<string, bool>, bool>"

第三题答案：

public class ParseString {
	public static void main(String[] args) {

		String input = "Map<string, Map<string, bool>>";

		JSONObject result = parse(input);
		System.out.println(result);

	}

	private static JSONObject parse(String input) {
		JSONObject jsonObj = new JSONObject("{}");
		String[] inputSplit = input.split("<", 2);
		jsonObj.append("type", inputSplit[0]);
		if (inputSplit.length == 2) { 
			loopParse(inputSplit[1].substring(0, inputSplit[1].length() - 1), jsonObj);
		}

		return jsonObj;
	}

	private static void loopParse(String string, JSONObject jsonObj) {

		List<String> result = new ArrayList<String>();
		Stack<String> stackInQuotes = new Stack<>();
		int start = 0;
		boolean inQuotes = false;
		for (int current = 0; current < string.length(); current++) {
			if (string.charAt(current) == '<') {
				stackInQuotes.add("<");
			} else if (string.charAt(current) == '>') {
				stackInQuotes.pop();
			}
			boolean atLastChar = (current == string.length() - 1);
			if (atLastChar) {
				result.add(string.substring(start));
			} else if (string.charAt(current) == ',' && stackInQuotes.isEmpty()) {
				result.add(string.substring(start, current));
				start = current + 1;
			}
		}
		
		JSONArray substringJsonArr = new JSONArray();
		for (int i = 0; i < result.size(); i ++) {
			String substring = result.get(i);
			String[] substringSplit = substring.split("<", 2);
			JSONObject substringJsonObj = new JSONObject();
			substringJsonObj.append("type", substringSplit[0]);
			if (substringSplit.length == 2) {
				loopParse(substringSplit[1].substring(0, substringSplit[1].length() - 1), substringJsonObj);
			}
			substringJsonArr.put(substringJsonObj);
		}
		
		jsonObj.append("typeArgs", substringJsonArr);

	}

}

第四题：⾃自增 ID 已知有如下⼀一个树状数据结构：

let tree = {
    id: '1',
    type: 'View',
    name: 'view',
    children: [
        {
            id: '2',
            type: 'Button',
            name: 'button'
        },
        {
            id: '3',
            type: 'View',
            name: 'view_1',
            children: [
                {
                    id: '4',
                    type: 'Button',
                    name: 'button_1'
                },
                {
                    id: '5',
                    type: 'View',
                    name: 'view_2'
                }
            ]
        }
    ]
};

name 字段的规则为整棵树不不能重复，如果遇到重复，则添加 _n 作为结尾。如果因为删除某 些节点，名字出现了了空隙，⽐比如 Tree 中有 button_1 和 button_3，但是没有 button_2，下⼀一 次插⼊入时，需要优先使⽤用 button_2，⽽而不不是 button_4 。 请实现⼀一个唯⼀一名称算法，当向整棵树的任意 children 插⼊入⼀一个新的 Node 时，可以保证 name 不不重复。 srcName 是计划向 Tree 中插⼊入节点的 name，⽐比如 button 、view, rootTreeNode 是整棵树

function getIncName(srcName: string, rootTreeNode : TreeNode): string;

第四题答案：

public class GetIncName {

	public static void main(String[] args) {
		String json1 = "{\r\n" + "    id: '1',\r\n" + "    type: 'View',\r\n" + "    name: 'view',\r\n"
				+ "    children: [\r\n" + "        {\r\n" + "            id: '2',\r\n"
				+ "            type: 'Button',\r\n" + "            name: 'button'\r\n" + "        },\r\n"
				+ "        {\r\n" + "            id: '3',\r\n" + "            type: 'View',\r\n"
				+ "            name: 'view_1',\r\n" + "            children: [\r\n" + "                {\r\n"
				+ "                    id: '4',\r\n" + "                    type: 'Button',\r\n"
				+ "                    name: 'button_1'\r\n" + "                },\r\n" + "                {\r\n"
				+ "                    id: '5',\r\n" + "                    type: 'View',\r\n"
				+ "                    name: 'view_5'\r\n" + "                }\r\n" + "            ]\r\n"
				+ "        }\r\n" + "    ]\r\n" + "}";

		JSONObject jObject1 = new JSONObject(json1);
		String srcName = "view";
		String string = getIncName(srcName, jObject1);
		System.out.println(string);

	}

	private static String getIncName(String srcName, JSONObject jObject1) {

		Map<String, ArrayList<Integer>> namesMap = new LinkedHashMap<String, ArrayList<Integer>>();
		handleJSONObject(jObject1, namesMap);
		String incName = checkSrcName(srcName, namesMap);

		return incName;
	}

	private static void handleJSONObject(JSONObject jObject1, Map<String, ArrayList<Integer>> namesMap) {
		jObject1.keys().forEachRemaining(key -> {
			Object value = jObject1.get(key);

			if (key.equals("name")) {

				String[] nameSplit = ((String) value).split("_");
				if (namesMap.containsKey(nameSplit[0])) {
					if (nameSplit.length == 2) {
						ArrayList<Integer> nameList = namesMap.get(nameSplit[0]);
						nameList.add(Integer.valueOf(Integer.parseInt(nameSplit[1])));
						namesMap.put(nameSplit[0], nameList);
					} else {
						ArrayList<Integer> nameList = namesMap.get(nameSplit[0]);
						nameList.add(Integer.valueOf(Integer.parseInt("0")));
						namesMap.put(nameSplit[0], nameList);
					}
				} else {
					if (nameSplit.length == 2) {
						ArrayList<Integer> newNameList = new ArrayList<Integer>();
						newNameList.add(Integer.valueOf(Integer.parseInt(nameSplit[1])));
						namesMap.put(nameSplit[0], newNameList);
					} else {
						ArrayList<Integer> newNameList = new ArrayList<Integer>();
						newNameList.add(Integer.valueOf(Integer.parseInt("0")));
						namesMap.put(nameSplit[0], newNameList);
					}
				}

			}
			handleValue(value, namesMap);
		});

	}

	private static void handleValue(Object value, Map<String, ArrayList<Integer>> namesMap) {
		if (value instanceof JSONObject) {
			handleJSONObject((JSONObject) value, namesMap);
		} else if (value instanceof JSONArray) {
			handleJSONArray((JSONArray) value, namesMap);
		}

	}

	private static void handleJSONArray(JSONArray jsonArray, Map<String, ArrayList<Integer>> namesMap) {
		jsonArray.iterator().forEachRemaining(element -> {
			handleValue(element, namesMap);
		});

	}
	
	private static String checkSrcName(String srcName, Map<String, ArrayList<Integer>> namesMap) {
		String[] nameSplit = srcName.split("_");
		if (namesMap.containsKey(nameSplit[0])) {
			ArrayList<Integer> nameList = namesMap.get(nameSplit[0]);
			Collections.sort(nameList);
			int availablenum = 0;
			for (int i = 0; i < nameList.size(); i ++) {
				if (nameList.get(i).intValue() != i) {
					availablenum = i;
					break;
				} else {
					availablenum = i + 1;
				}
			}
			return nameSplit[0]+"_"+availablenum;
		} else {
			return srcName;
		}
	}

}
3340 次点击
所在节点    问与答
25 条回复
mumbler
2020-04-10 22:09:38 +08:00
代码都没有注释啊
sxxkgoogle
2020-04-10 22:20:27 +08:00
@mumbler 嗯没注释，之前在网上搜好像说做面试题一般不需要吧。
also24
2020-04-10 22:25:36 +08:00
怎么感觉题目是 TypeScript 的，楼主你这面的是什么岗位？
sxxkgoogle
2020-04-10 22:39:26 +08:00
@also24 是全栈的岗位。
mcfog
2020-04-10 22:46:54 +08:00
你看你就这样贴了题目出来，还有猎头也会收集题目，培训班也有一个个安排面试拿题目给下一个的操作，所以一般不会解释过多的
raymanr
2020-04-10 22:53:49 +08:00
呃，我不是专业程序员，好奇自己的水平在专业人员眼里是啥样的，做了下第一题，各位大佬点评下

```

function findNodeById(root, id) {
let result = [];

function findOne(node, id) {
if (node["id"] == id) {
result.push(node);
}
if (node.hasOwnProperty("children")) {
node["children"].forEach(child => findOne(child, id));
}
return false;
}

findOne(root, id);
return result;
}

```
swulling
2020-04-10 22:54:07 +08:00
代码长度相比于出题人的预期略长了
aureole999
2020-04-10 23:05:26 +08:00
为什么不管什么都用 JsonObject 做呢？
题目只说有个树状结构，例子给的是 js，不代表非要用 json 来实现树，你可以自己定义 TreeNode Class 啊。如果题目要求必须用 json，那也应该把 json 映射成 java bean 再写处理的方法吧。要不你就别用 java，直接用 js 。
aureole999
2020-04-10 23:13:49 +08:00
@raymanr 第一题返回值不需要用数组。一般来说叫函数名 byId 的返回值就是唯一的，而且人家给的函数原型的返回值也不是数组。
ASpiral
2020-04-11 00:26:11 +08:00
试着做了下第一题，感觉没必要写那么长的代码吧…
const findNodeById = (root, id) => {
let target = null;
const findNode = (root, id) => {
if (target !== null) {
return;
}
if (root.id === id) {
target = root;
} else if (root.children) {
root.children.forEach(node => findNode(node, id));
}
};
findNode(root, id);
return target;
};
lithbitren
2020-04-11 02:33:06 +08:00
代码没细看，java 选手好可怕，感觉 python 都是几行以内解决的，js 写起来也就是多了半对大括号的行数。。
rabbbit
2020-04-11 03:36:06 +08:00
1
interface TreeNode {
...id: String,
...label: String,
...children?: TreeNode[]
}

function findNodeById(root: TreeNode, id: string): TreeNode {
...if (root.id === id) {
......return root;
...}
...
...if (root.children) {
......for (let i of root.children) {
.........const child = findNodeById(i, id);
.........if (child) {
............return child
.........}
......}
...} else {
... return null;
...}
}

console.assert(findNodeById(tree, '1').label === 'first', '1')
console.assert(findNodeById(tree, '2').label === 'second', '2')
console.assert(findNodeById(tree, '3').label === 'third', '3')
console.assert(findNodeById(tree, '4').label === 'fourth', '4')
console.assert(findNodeById(tree, '5').label === 'fifth', '5')
rabbbit
2020-04-11 03:51:58 +08:00
2
interface Student {
...name: string,
...score: number
}
function groupBy(students: Student[]) {
...const group: { [propName: string]: Student[] } = {};
...for (let i of students) {
......const grade = getGrade(i.score);
......if (!group[grade]) {
.........group[grade] = []
......}
......group[grade].push(i)
...}
...return group;
}
6IbA2bj5ip3tK49j
2020-04-11 04:03:08 +08:00
1，不要硬编码数据，从文件读取。方便测试，修改。
2，lambda

反正我作为 Java 开发，这样的代码风格，我是接受不了的。
lithbitren
2020-04-11 04:35:31 +08:00
几行夸张了，手撕中等题也要十行左右了。

宽搜扩展完事，这里就用字典代替树了，如果树是对象的话就更改获取属性的语句就行。
def findNodeById(root, id):
ㅤㅤd = root and [root]
ㅤㅤwhile d:
ㅤㅤㅤㅤr = next((r for r in d if r['id'] == id), None)
ㅤㅤㅤㅤif r:
ㅤㅤㅤㅤㅤㅤreturn r
ㅤㅤㅤㅤd = sum((r['children'] for r in d if 'children' in r), [])
ㅤㅤreturn None

第二题最简单
def getGrade(score):
ㅤㅤreturn score < 60 and 'C' or score < 80 and 'B' or 'A'
def groupBy(students):
ㅤㅤres = {'A': [], 'B': [], 'C': []} # res = collections.defaultdict(list)
ㅤㅤfor student in students:
ㅤㅤㅤㅤres[getGrade(student['score'])].append(student)
ㅤㅤreturn res

语法题栈实现
def parse(args):
ㅤㅤstack = [{'type': ''}]
ㅤㅤfor c in args:
ㅤㅤㅤㅤif c == ' ':
ㅤㅤㅤㅤㅤㅤcontinue
ㅤㅤㅤㅤelif c == '<':
ㅤㅤㅤㅤㅤㅤstack[-1]['typeArgs'] = [{'type': ''}]
ㅤㅤㅤㅤㅤㅤstack.append(stack[-1]['typeArgs'][0])
ㅤㅤㅤㅤelif c == ',':
ㅤㅤㅤㅤㅤㅤstack[-2]['typeArgs'].append({'type': ''})
ㅤㅤㅤㅤㅤㅤstack[-1] = stack[-2]['typeArgs'][-1]
ㅤㅤㅤㅤelif c == '>':
ㅤㅤㅤㅤㅤㅤdel stack[-1]
ㅤㅤㅤㅤelse:
ㅤㅤㅤㅤㅤㅤstack[-1]['type'] += c
ㅤㅤreturn stack[0]

O(N)的在线算法，深搜遍历，计数判断，如果离线的话可以优化到 O(logN)
def getIncName(srcName, rootTreeNode):
ㅤㅤd = set()
ㅤㅤdef dfs(r):
ㅤㅤㅤㅤr['name'].rsplit('_', 1)[0] == srcName and d.add(r['name'])
ㅤㅤㅤㅤif 'children' in r:
ㅤㅤㅤㅤㅤㅤfor child in r['children']:
ㅤㅤㅤㅤㅤㅤㅤㅤdfs(child)
ㅤㅤrootTreeNode and dfs(rootTreeNode)
ㅤㅤif srcName not in d:
ㅤㅤㅤㅤreturn srcName
ㅤㅤfor i in range(1, len(d) + 1):
ㅤㅤㅤㅤres = srcName + '_' + str(i)
ㅤㅤㅤㅤif res not in d:
ㅤㅤㅤㅤㅤㅤreturn res
rabbbit
2020-04-11 05:24:58 +08:00
@lithbitren 空格是怎么打出来的?
lithbitren
2020-04-11 05:34:27 +08:00
@rabbbit 随便找了个空白字符，ascii 码 12644
tyx1703
2020-04-11 05:37:11 +08:00
@ASpiral 你这把整个树都遍历了
@rabbbit 的答案比较好
tyx1703
2020-04-11 05:42:39 +08:00
题目用的 ts，你用 java 作答我寻思着起码手动把 TreeNode 的数据结构实现一下吧
一坨坨 json 感官上就很不舒服，更加无心阅读代码质量了
yazoox
2020-04-11 08:10:40 +08:00
有意思，关注一下

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/661313

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX