d*****v
发帖数: 72 | 1 刚刚结束，印度人一个小时三道题，感觉bar又往上升了，大家好好准备吧
一个单词数组，求任意两个单词的距离
实现List类，要有添加，删除，返回长度，o1复杂度
给一个嵌套list类似 {{1 1} 2 {1 1}}，每一个list里的元素相加乘以深度求和。这个
例子的话是，（1+1）*1 +２×２＋（１＋１）×１。最底层list深度是1，之前面经还
有问最顶层深度是1的情况 |
l*****a
发帖数: 14598 | 2 这不都是别人发了多少遍的吗？
看起来他们真的有题库？
【在 d*****v 的大作中提到】
: 刚刚结束，印度人一个小时三道题，感觉bar又往上升了，大家好好准备吧
: 一个单词数组，求任意两个单词的距离
: 实现List类，要有添加，删除，返回长度，o1复杂度
: 给一个嵌套list类似 {{1 1} 2 {1 1}}，每一个list里的元素相加乘以深度求和。这个
: 例子的话是，（1+1）*1 +２×２＋（１＋１）×１。最底层list深度是1，之前面经还
: 有问最顶层深度是1的情况
|
p*****2
发帖数: 21240 | 3 object test extends App{
def depth(l: Any):Int = l match {
case n: Int => 1
case l: List[Any] => 1 + l.map(depth).max
}
def cal(l:Any, depth: Int):Int = l match {
case n: Int => n*depth
case l: List[Any] => l.map(cal(_, depth-1)).sum
}
val l = List(List(1,1), 2, List(1,1))
val res = cal(l, depth(l))
println(res)
} |
r*******e
发帖数: 971 | 4 这是什么语言？
【在 p*****2 的大作中提到】
: object test extends App{
: def depth(l: Any):Int = l match {
: case n: Int => 1
: case l: List[Any] => 1 + l.map(depth).max
: }
: def cal(l:Any, depth: Int):Int = l match {
: case n: Int => n*depth
: case l: List[Any] => l.map(cal(_, depth-1)).sum
: }
: val l = List(List(1,1), 2, List(1,1))
|
r*******e
发帖数: 971 | 5 这三道题我确实都见过，第二道题自己做过。楼主居然能在60分钟做3道，真快。 |
r*******e
发帖数: 971 | |
l*****a
发帖数: 14598 | 7 这个第二题，如果有重的情况是怎么要求的
【在 d*****v 的大作中提到】
: 刚刚结束，印度人一个小时三道题，感觉bar又往上升了，大家好好准备吧
: 一个单词数组，求任意两个单词的距离
: 实现List类，要有添加，删除，返回长度，o1复杂度
: 给一个嵌套list类似 {{1 1} 2 {1 1}}，每一个list里的元素相加乘以深度求和。这个
: 例子的话是，（1+1）*1 +２×２＋（１＋１）×１。最底层list深度是1，之前面经还
: 有问最顶层深度是1的情况
|
r*******e
发帖数: 971 | |
W***8
发帖数: 44 | 9 Scala?
【在 p*****2 的大作中提到】
: object test extends App{
: def depth(l: Any):Int = l match {
: case n: Int => 1
: case l: List[Any] => 1 + l.map(depth).max
: }
: def cal(l:Any, depth: Int):Int = l match {
: case n: Int => n*depth
: case l: List[Any] => l.map(cal(_, depth-1)).sum
: }
: val l = List(List(1,1), 2, List(1,1))
|
l*****a
发帖数: 14598 | 10 似乎看懂了
用了两遍DFS,效率不太好吧
sorry不能给offer
【在 p*****2 的大作中提到】
: object test extends App{
: def depth(l: Any):Int = l match {
: case n: Int => 1
: case l: List[Any] => 1 + l.map(depth).max
: }
: def cal(l:Any, depth: Int):Int = l match {
: case n: Int => n*depth
: case l: List[Any] => l.map(cal(_, depth-1)).sum
: }
: val l = List(List(1,1), 2, List(1,1))
|
|
|
p*****2
发帖数: 21240 | 11
大牛有什么好办法吗？
【在 l*****a 的大作中提到】
: 似乎看懂了
: 用了两遍DFS,效率不太好吧
: sorry不能给offer
|
l*****a
发帖数: 14598 | 12 我想用BFS,每层压栈，直到最深的那层，然后再反过来计算
似乎也不能算太好吧
【在 p*****2 的大作中提到】
:
: 大牛有什么好办法吗？
|
p*****2
发帖数: 21240 | 13 写个scala的看看？
【在 l*****a 的大作中提到】
: 我想用BFS,每层压栈，直到最深的那层，然后再反过来计算
: 似乎也不能算太好吧
|
l*****a
发帖数: 14598 | 14 不会 :(
只学两天出去献丑也不好，还是找到用scala的工作再抓紧ramp up吧
【在 p*****2 的大作中提到】
: 写个scala的看看？
|
m*****k
发帖数: 731 | 15 难道不是double linked list？
【在 l*****a 的大作中提到】
: 这个第二题，如果有重的情况是怎么要求的
|
l*****a
发帖数: 14598 | 16 我就问,如果有重复item,需要处理吗
【在 m*****k 的大作中提到】
: 难道不是double linked list？
|
p*****2
发帖数: 21240 | 17
第二题的要求太奇葩，没法用fp来做了。
【在 l*****a 的大作中提到】
: 我就问,如果有重复item,需要处理吗
|
r*******e
发帖数: 971 | 18 不需要。
【在 l*****a 的大作中提到】
: 我就问,如果有重复item,需要处理吗
|
h*******0
发帖数: 270 | 19 我发现fp好多情况都实现不了。 昨天试着用fp写歌lru cache。 怎么想都没想明白如
何不用mutable。。
【在 p*****2 的大作中提到】
:
: 第二题的要求太奇葩，没法用fp来做了。
|
p*****2
发帖数: 21240 | 20 所以纯fp不行呀
或者做起来很麻烦
scala倒是都support 就是比较难驾驭
大概80% fp 20% imperative 这样分配比较合适
clojure也是这个套路
haskell就要上monad了
【在 h*******0 的大作中提到】
: 我发现fp好多情况都实现不了。 昨天试着用fp写歌lru cache。 怎么想都没想明白如
: 何不用mutable。。
|
|
|
m*****k
发帖数: 731 | 21 O(1) delete, 应该是给定pointer的delete，与值无关了吧。
【在 l*****a 的大作中提到】
: 我就问,如果有重复item,需要处理吗
|
z***e
发帖数: 58 | 22 #3 O(n)
public static int depthSum(String[] strs){
int depth = 1;
int totalDepth = 0;
for(String str : strs){
if(str.equals("{")){
depth ++;
totalDepth = Math.max(depth, totalDepth);
} else if(str.equals("}")){
depth --;
}
}
int sum =0;
int currentDepth = 0;
for(String str : strs){
if(str.equals("{")){
currentDepth ++;
} else if(str.equals("}")){
currentDepth --;
} else {
sum += Integer.parseInt(str)* (totalDepth - currentDepth);
}
}
return sum;
} |
c********r
发帖数: 107 | |
