[Linkedin]电面新鲜面经

一共60min，简单自我介绍之后就是两个coding问题：
1. 先让写了一个reverseString，没花什么时间。

2. implements 一个Two Sum interface，里面有两个method：
    a. void store (int val) :  需要选一个数据结构作为存储，然后会不停地往里面add value。我选择的是List

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

     }
       }      
       return false;
    }     
}

follow up 是假设要call 30000次hasPair 方法 （nums 里面的值不变），如何在保证没有extra space complexit的情况下，减少 time complexity。关于这点， 我并没有想出很好的答案， 欢迎讨论！

follow up 有target 的time complexity 吗? 感觉蛮难的... 因为nums 不会改变 能够在所有store 完之后 先枚举在call hasPair 30000吗?

say543 发表于 2016-8-13 14:40
follow up 有target 的time complexity 吗? 感觉蛮难的... 因为nums 不会改变 能够在所有store 完之后 先 ...

这样会增加space complexity吧 因为有(n^2) 种可能的组合要存储

感谢楼主分享；我感觉follow-up既然有那么大的hasPair的调用，而nums不变，不如用一个hashset存所有可能的sums，在store时候更新sums，这样call hasPair的时候就可以在O(1)的时间内返回了

LearnerChao 发表于 2016-8-15 11:20
感谢楼主分享；我感觉follow-up既然有那么大的hasPair的调用，而nums不变，不如用一个hashset存所有可能的s ...

这样space complexity 会增加吗?

say543 发表于 2016-8-15 13:45
这样space complexity 会增加吗?

会增加n^2的空间