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

原创

霍格沃兹测试开发

修改于 2020-07-20 10:08:58

3820

修改于 2020-07-20 10:08:58

文章被收录于专栏：测吧测试开发

算法题目

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

{
   "item":{
          "data": {
            "text": "123",
        },
        "children": [{
            "data": {
                "text": "234"
            },
            "children": []
        }, {
            "data": {
                "text": "345"
            },
            "children": [{
                "data": {
                    "text": "456"
                },
                "children": []
            }, {
                "data": {
                    "text": "plid"
                },
                "children": [{
                    "data": {
                        "text": "567"
                    },
                    "children": [....]
                }, {
                    "data": {
                        "text": "678"
                    },
                    "children": [...]
                }
                ]
        }, {
                // 不确定长度的Children节点
            }
}

你知道如何解答吗？

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

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

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

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

解法一

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

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

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

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

def getAttributesFromNode(node: Node): ListBuffer[Map[String, String]] ={
  val attributesList = ListBuffer[Map[String, String]]()
  //递归获取路径,生成可定位的xpath表达式
  def getParent(node: Node): Unit = {
    if (node.hasAttributes) {
      val attributes = node.getAttributes
      var attributeMap = Map[String, String]()


      0 until attributes.getLength foreach (i => {
        val kv = attributes.item(i).asInstanceOf[Attr]
        attributeMap ++= Map(kv.getName -> kv.getValue)
      })
      attributeMap ++= Map("name()" -> node.getNodeName)
      attributeMap ++= Map("innerText" -> node.getTextContent.trim)
      attributesList += attributeMap
    }


    if (node.getParentNode != null) {
      getParent(node.getParentNode)
    }
  }
  getParent(node)
  //返回一个从root到leaf的属性列表
  return attributesList.reverse


}

解法二

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

depth(){
echo "$1" \
sed 's#"[^"]*"##g'  \
|  grep -oE  '{|}' \
| awk '/{/{a+=1}/}/{a-=1}{if(max<a) max=a}{print max,a}END{print "max depth="max}'
}


# 结果貌似是6
depth  '
{
   "item":{
          "data": {
            "text": "123",
        },
        "children": [{
            "data": {
                "text": "234"
            },
            "children": []
        }, {
            "data": {
                "text": "345"
            },
            "children": [{
                "data": {
                    "text": "456"
                },
                "children": []
            }, {
                "data": {
                    "text": "plid"
                },
                "children": [{
                    "data": {
                        "text": "567"
                    },
                    "children": [....]
                }, {
                    "data": {
                        "text": "678"
                    },
                    "children": [...]
                }
                ]
        }, {
                // 不确定长度的Children节点
            }
}
'  


# testerhome的json接口，貌似是4
depth "$(curl https://testerhome.com/api/v3/topics.json 2>/dev/null)" 
# taobao的某个接口，结果为2
depth "$(curl http://ip.taobao.com/service/getIpInfo.php?ip=63.223.108.42 2>/dev/null )"

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java