w*****c
发帖数: 18 | 1 电面1
1. Find successor in BST
2. Find minimum number in a rotated sorted array (当时这个题还没在
leetcode里，所以写得代码有些繁琐，估计因为这个要再电面一轮）
电面2
1. Insert a node into a sorted circular linked list ( all next element is
larger except for the last one), the given head can point to any node
1 -> 3 -> 5 ->7
^ |
| |
| _ _ _ |
如果node的值是2，则插入1和3之间；如果node的值是8或者0，插入7和1之间。
要考虑node值重复的情况，虽然结果一样，但要和面试官讨论新的节点插入的位置，可
能插入在最开始或最后，我不记得了。
例如插入3, 结果是1->3->3'->5->7或者1->3'->3->5->7
2. Clon... 阅读全帖 |
|
g**********y
发帖数: 14569 | 2 我写的慢程序：用HashMap实现的Trie. 换成char[], 对于N=7, 速度快一些，但是对N<
7, 速度更慢。可能因为解跟Hash key的位置有关。
public class WordRectangle {
private final static String DIR = "src/test/resources";
private Trie m_trie;
private String[] m_words;
public static void main(String[] args) {
WordRectangle w = new WordRectangle();
long t0 = System.currentTimeMillis();
w.find(6);
long t1 = System.currentTimeMillis();
System.out.println("Time = " + (t... 阅读全帖 |
|
g**********y
发帖数: 14569 | 3 public class Boggle {
private final int N = 5;
private HashSet m_words;
public Boggle() {
m_words = new HashSet();
}
public static void main(String[] args) {
String[] str = new String[]{
"AEBOF", "TSUVW", "RFOEG", "RSOFI", "PQWRE"
};
new Boggle().run(str);
}
public void run(String[] str) {
char[][] cs = new char[N][N];
boolean[][] used = new boolean[N][N];
m_word... 阅读全帖 |
|
n********5
发帖数: 323 | 4 一道面试题，是需要写一个函数getAnagram()
这个函数是定义在一个Class里面，这个Class还有一个函数addWord()，用来向这个类
加入任意
word。
我的思路是用hashtable，当add word的时候，把需要加入的word sort一遍，然后查找
hash，如
果已经存在，就是用linkedlist的方式，把新加的word link到最后。这样getAnagram(
)只需要遍
历一遍这个hashtable就可以知道当前输入的words 所有的Anagram。
如果考虑sort的时间复杂度是O(nlogn), hashtable的lookup是O(1)，这个getAnagram(
)函数的效
率是O(nlogn)，假设getAnagram()的pass in是需要查找的word。
这个思路还有什么其他办法可以优化的吗？或者还有其他思路吗？谢啦！ |
|
n********5
发帖数: 323 | 5 要求design整个class，包括写两个函数。
整个class带这两个函数，class design 我的思路是hashtable，Addword()我也有思路
，，不过
如果想看看能有更优解。 |
|
