面试 | 卡掉不少人的一道腾讯算法面试题，高手来试试？

image

算法题目

给定一个不确定的 Json 对象，求 Json 子节点的最大深度（编程语言不限，不可写伪代码）。如下：

<pre style="margin: 0px; padding: 8px 0px 6px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial; box-sizing: border-box; background-color: rgb(247, 243, 247); border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); font-size: 10px; line-height: 12px; border-width: 1px; border-style: solid; border-color: rgb(226, 226, 226);">

1. {

2. "item":{

3. "data": {

4. "text": "123",

5. },

6. "children": [{

7. "data": {

8. "text": "234"

9. },

10. "children": []

11. }, {

12. "data": {

13. "text": "345"

14. },

15. "children": [{

16. "data": {

17. "text": "456"

18. },

19. "children": []

20. }, {

21. "data": {

22. "text": "plid"

23. },

24. "children": [{

25. "data": {

26. "text": "567"

27. },

28. "children": [....]

29. }, {

30. "data": {

31. "text": "678"

32. },

33. "children": [...]

34. }

35. ]

36. }, {

37. // 不确定长度的Children节点

38. }

39. }

</pre>

你知道如何解答吗？

给你 10 分钟时间，能否搞定？

想到答案的同学，可以在评论区回复，也可点击左下角“阅读原文”，登录 TesterHome 社区回复帖子。

你可能想不到的最佳参考答案是？

参考答案作者为@思寒，资深测试架构师，霍格沃兹测试学院校长，开源工具 AppCrawler 作者。

解法一

其实是个递归算法，Json 本质是一个 tree 节奏的数据，先把 Json 转成标准的各个语言的结构体，比如 Python 的 dict 或者 Java 的 HashMap。

剩下的就是递归判断 children 的类型并计数深度。我碰巧之前写过类似的算法，不过 Scala 的代码。。。

不得不说这个算法其实是测试工程里用的非常多的场景。用递归解决深层次数据的分析问题，在很多工具里都有一些应用的。

AppCrawler 里也有好几段是关于这个算法的使用的，比如从 Xpath 匹配的节点中反向生成 Xpath 定位表达式，把 HTML 网页的 page source 转成 Appium 兼容的 XML 格式，对数据结构做扁平化好进行数据对比。

<pre style="margin: 0px; padding: 8px 0px 6px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial; box-sizing: border-box; background-color: rgb(247, 243, 247); border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); font-size: 10px; line-height: 12px; border-width: 1px; border-style: solid; border-color: rgb(226, 226, 226);">

1. def getAttributesFromNode(node: Node): ListBuffer[Map[String, String]] ={

2. val attributesList = ListBuffer[Map[String, String]]()

3. //递归获取路径,生成可定位的xpath表达式

4. def getParent(node: Node): Unit = {

5. if (node.hasAttributes) {

6. val attributes = node.getAttributes

7. var attributeMap = Map[String, String]()

8. 0 until attributes.getLength foreach (i => {

9. val kv = attributes.item(i).asInstanceOf[Attr]

10. attributeMap ++= Map(kv.getName -> kv.getValue)

11. })

12. attributeMap ++= Map("name()" -> node.getNodeName)

13. attributeMap ++= Map("innerText" -> node.getTextContent.trim)

14. attributesList += attributeMap

15. }

16. if (node.getParentNode != null) {

17. getParent(node.getParentNode)

18. }

19. }

20. getParent(node)

21. //返回一个从root到leaf的属性列表

22. return attributesList.reverse

23. }

</pre>

解法二

巧用 Shell 脚本编程来实现一个最简单的解法，正好最近刚在霍格沃兹测试学院分享了 Linux 三剑客公开课的技术，利用 Shell 脚本来实现下面这个解法。

<pre style="margin: 0px; padding: 8px 0px 6px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial; box-sizing: border-box; background-color: rgb(247, 243, 247); border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); font-size: 10px; line-height: 12px; border-width: 1px; border-style: solid; border-color: rgb(226, 226, 226);">

1. depth(){

2. echo "$1" \

3. sed 's#"[^"]*"##g' \

4. | grep -oE '{|}' \

5. | awk '/{/{a+=1}/}/{a-=1}{if(max<a) max=a}{print max,a}END{print "max depth="max}'

6. }

7. # 结果貌似是6

8. depth '

9. {

10. "item":{

11. "data": {

12. "text": "123",

13. },

14. "children": [{

15. "data": {

16. "text": "234"

17. },

18. "children": []

19. }, {

20. "data": {

21. "text": "345"

22. },

23. "children": [{

24. "data": {

25. "text": "456"

26. },

27. "children": []

28. }, {

29. "data": {

30. "text": "plid"

31. },

32. "children": [{

33. "data": {

34. "text": "567"

35. },

36. "children": [....]

37. }, {

38. "data": {

39. "text": "678"

40. },

41. "children": [...]

42. }

43. ]

44. }, {

45. // 不确定长度的Children节点

46. }

47. }

48. '

49. # testerhome的json接口，貌似是4

50. depth "$(curl https://testerhome.com/api/v3/topics.json 2>/dev/null)"

51. # taobao的某个接口，结果为2

52. depth "$(curl http://ip.taobao.com/service/getIpInfo.php?ip=63.223.108.42 2>/dev/null )"

</pre>

点击领取：自动化+侧开+性能+简历+面试核心教程资料
http://qrcode.testing-studio.com/f?from=jianshu&url=https://ceshiren.com/t/topic/3595