Citadel 所有OA集合

The Jungle Book, 求minimum group without ancestors
类似

image
All subpalindrome
Given “aabba”, return [“a”,“b”,“aa”,“bb”,“abba”]
参考利口 午 ,DP和expand by center 都能做。
image
3. String chain 利口 依灵嗣巴
image

https://drive.google.com/drive/folders/1uqWw2GOa0bMUSRls4LWrtw_0eBnU9u2o?usp=sharing

  1. 题目情境是predator和pray,其实就是在一个有向无环图里找最长路径的长度,给的数据是一个数组,代表每个节点的前一个节点。

  2. 问一个字符串有多少个不同的回文子串。

  3. 情境变了但和第一题类似,仍然是有向无环图里找最长路径的长度,不过需要先把图里的边构造出来。节点是字符串,边s1->s2代表字符串s1删掉某个字符后等于s2。
    (这是个图不是树,所以会有一个节点多个root的情况。从入度为0的点开始做BFS就可以了)
    最后一题有一个hidden testcase 有 memory error没过

第一题很简单,类似把"13Sep2018"转换成"20180913"这样的日期string转换,可以秒掉


第二题给一串不同时刻的stock price, 每个时刻可以卖出/买入,求最大的profit


第三题把tree用(root(child)(child))的形式表示,输出string。感觉蛮难的,最后差点没做完
image


  1. 一个array, 每次要选择两个数a1, a2从array中remove,然后把他们的和sum = a1+a2方进入数组中,而且这一步操作的cost = sum = a1+a2, 问把数组减少到只有一个元素的时候最小的cost是多少。 其实挺简单的一道题,但是有一个case怎么写都超时

  2. huffman 编码,第一题debug花了太多时间,这道题没写完,自己本来也不熟悉

  3. 需要实现一个http get的api,这道题是最后看了一眼标题,完全没时间写了

  4. 给n个数,两两合并,合并n-1次。每次合并花费两数之和,总花费n-1次,求最小总花费。 —用minheap做的

  5. leetcode 239变种

补充;关于magical binary string那题,一个大的magical string可以最终划分到一个个最小单元的magical string.如10,1100,111000,11110000…,其他的可由这些拼接起来.所要做的就是把长度越大的单元尽可能往前交换。想了好久,感谢舍友启发。
image
image
image
image

citadel OA集合.7z (1.6 MB)

1 2 100 为何答案是 197?

参考

https://massivealgorithms.blogspot.com/2016/05/tree-s-expression.html

跟Lc那道stocks不太一样,这里是买入1 买入2 ,手上俩股, 然后卖出 ,profit = 2*100 -1 -2 = 197.

思路的话,找peak(比两边的点大),peak前面的非 peak的点全部买入

citadel_OA.zip (727.8 KB)

1 Like