第七章 携程电面 (1 / 2)
        一月17号下午两点，电话准时响起来，我接通电话，礼貌地自报家门。电话那端是名姓陈的资深工程师。他语速有点快，问道：“咱们现在开始吧，我先介绍一下自己，我叫陈永胜，是做技术运维的，主要负责监控数据采集和告警，以及数据可视化与运维保障。你也介绍一下你自己做过的项目吧？”

        我定了定神，开始描述自己做过的项目，包括用到的技术栈，还有实现的具体细节，大概用了大概4-5分钟。他听得比较认真，觉得可以了，然后说道：“你刚才提到了Redis，你能谈谈你们为什么要用Redis，你们做技术选型都考虑哪些因素？”

        我想了想，回答道：“用Redis主要是想改善前端页面的响应速度，提高用户满意度。我们技术选型主要考虑两个方面：第一就是开源产品的成熟度，功能的更新与维护情况，第二就是我们当前部门的技术实力，和新技术的学习曲线。因为我们是小公司，所以我们开发人员的职能和任务有些重叠交叉，例如，我们后端工程师也需要兼做运维工作，以及和前端界面的联调测试，还有数据存储、日志分布式管理，服务告警与监控。”

        等我说完，他接着发问：“你提到的日志管理，你们采取的是什么方案？”我对这一块比较熟悉，因为部门的日志管理系统就是我从零到一搭建的。我脱口而出：“我们采取的是EsticSearch、Logstash还有Kibana的一套开源系统，之前用的是Splunk日志系统，因为比较昂贵，所以我们去年就用EsticSearch替换掉了，ELK为公司省钱。”他在电话里面笑了笑，接着追问道：“你们的Trag是怎么做的？用户画像与行为分析你们有做过吗？”

        我看他迟迟不提做算法题，有点摸不清楚他的套路，于是硬着头皮回答道：“我们采用的是Zipkin分布式系统来做Trag，用户行为分析是我们组的另外一位DataStist来做的，她主要就是用SparkStream加Tablenu来做的。”他听完我的回答，顿了顿，接着他说：“咱们来做一道算法题吧？你习惯用Java还是Python，或者Gong？”我对Java比较熟悉，于是回答：“我就用Java吧”

        他接着用邮件给我发来一个链接，里面是coderpad.io在线编程面试页面。我点击链接进去以后，他已经在里面了。他贴了一道题在页面左边的文本框，我需要在右边文本框写出自己的函数，提供解决方案。

        他出的题目是Lintcode的一道老题目，二叉查找树中搜索区间，具体描述是：给定一个二叉查找树和范围[k1，k2]。按照升序返回给定范围内的节点值。我根据自己以前练习的记忆，先给他描述了一下自己的解题思路，他说：“好的，看来你做过这道题，那我们换道题吧？”

        我心里一嘀咕，这哥们也够实在的，一点都不放水啊，我只得硬充好汉，说道：“可以的。”他又贴了一道题，这下轮到我傻眼了，这道题我没见过，也没有思路。他贴完题目，说道：“我们还有25分钟，你尽量写吧，不要着急。”

        题目描述是：这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。

        费用通过一个nx3的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用。

        我猜测应该是Lintcode的题目，只是我没有刷过这道题。看样子要用动态规划来解决。我想了想，告诉他：“我打算用动态规划的方法来做这道题。”他有点愉快地说道：“嗯，你的思路是对的，你试试看。”

        既然思路对了，解题上就清晰了一些。动态规划题重点就是找到动态转换方程。我们看第i个房子涂什么颜色，由于总共只有三种颜色，所以当第i个房子涂红色时，第i-1个房子只能涂蓝色和绿色，依次递推。

        dp[[j]分别用来记录，第i个房子染红色，绿色和蓝色时的总费用。

        其中状态转移方程为：dp[[红色]=min(dp[i-1][蓝色]，dp[i-1][绿色]）

        只要将这三种情况得出的答案中的最小值就是最优解。可以直接利用原数组进行递推计算，无需使用额外空间。

        当我把动态转换方程敲在页面上，他就说：“对的，你可以开始写代码了。”

        我稍加思索，就开始写代码了。

        publitminCost(int[][]costs){

        内容未完，下一页继续阅读

更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》