V1

第一题：Prefix Map。给你的是一个unordered_map，key=string， value=int，求出HashMap里面所有以prefix开头的string的value。我的做法是把词条都存到一个ordered_map（在java里应该是叫做TreeMap）里，然后Traverse

第二题：Burst array。一个Array里面都是integer，你可以remove掉里面所有出现的一个数，并且积累所有该数的和到

积分中（即数*出现次数）。但是如果这么做了，你就得把array里面所有的该数+1和该数-1 remove掉但是不积累积分。Given an array，问最多能得到多少积分。我的做法是DP建一个二维数组，其中dp[i][j]表示subarray(i,j)所能积累到的最大的积分。只是可惜有几个Test case没有过，可能有corner cases 需要考虑。

给一数组，例如[1, 2, 2, 1, 3, 3]，当取出一个数Ai时，可以得到Ai * count(Ai), 同时Ai + 1, Ai - 1, 不能再被选，如取出1时，可以得到 1 * 2, 但是2和3都不能在选，求能得到的最大的值。

类似House Robber，注意用long类似否则会overflow。

第三题：Diamond mining。给一个二维数组，里面有-1表示墙不能通过，其他数都是大于等于0表示格子的钻石数量。从左上走到右下再从右下走到左上，问最多能捡多少钻石。前提条件是从左上到右下只能向下或者向右走，从右下到左上只能向上或者向左走，而且钻石不能重复捡。我的做法是第一遍DP左上到右下，然后backtracking把第一遍最优走法中捡到的钻石清零，接着再来一遍DP从右下到左上，可是还是有Test cases没过。