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

简介: 算法题目给定一个不确定的 Json 对象,求 Json 子节点的最大深度(编程语言不限,不可写伪代码)。

image.png
算法题目
给定一个不确定的 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#"1*"##g'
\

| grep -oE
'{|}'
\

| awk
'/{/{a+=1}/}/{a-=1}{if(max

      "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 2>/dev/null)"

taobao的某个接口,结果为2

depth
"$(curl 2>/dev/null )"

相关文章
|
24天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
29天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
30 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
18天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
23天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
24天前
|
负载均衡 算法 Java
腾讯面试:说说6大Nginx负载均衡?手写一下权重轮询策略?
尼恩,一位资深架构师,分享了关于负载均衡及其策略的深入解析,特别是基于权重的负载均衡策略。文章不仅介绍了Nginx的五大负载均衡策略,如轮询、加权轮询、IP哈希、最少连接数等,还提供了手写加权轮询算法的Java实现示例。通过这些内容,尼恩帮助读者系统化理解负载均衡技术,提升面试竞争力,实现技术上的“肌肉展示”。此外,他还提供了丰富的技术资料和面试指导,助力求职者在大厂面试中脱颖而出。
腾讯面试:说说6大Nginx负载均衡?手写一下权重轮询策略?
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
59 2
|
2月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
3月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
2天前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
17 4
|
1天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?