1小时前Google Intern面经

heronalps

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

heronalps

贴一个第一题的代码，同志们看看有什么问题？

class DoublyLinkedListNode{
int val;
DoublyLinkedListNode next;
DoublyLinkedListNode prev;
public DoublyLinkedListNode(int val) {
this.val = val;
}
}
public class Solution {
public static int findConsecutive(DoublyLinkedListNode head, int[] nodeIds) {
int count = 0;
Set<DoublyLinkedListNode> set = new HashSet<>();
for(int node : nodeIds) {
set.add(getNodeFromId(head, node));
}
for (int i = 0; i < nodeIds.length; i++) {
DoublyLinkedListNode curr = getNodeFromId(head, nodeIds[i]);
if (set.contains(curr)) {
set.remove(curr);
count++;
} else {
continue;
}
DoublyLinkedListNode left = curr;
DoublyLinkedListNode right = curr;
while (set.contains(right.next)) {
set.remove(right.next);
right = right.next;
}
while (set.contains(left.prev)) {
set.remove(left.prev);
left = left.prev;
}
}
return count;
}
private static DoublyLinkedListNode getNodeFromId(DoublyLinkedListNode head, int nodeId) {
for (int i = 0; i < nodeId - 1 && head != null; i++) {
head = head.next;
}
return head;
}

复制代码

cxw111

heronalps 发表于 2018-1-18 03:17
之前没刷过这道题。感谢！

没事请问第一题前后连续是指一个node的prev和next都不为空么

dingshilun

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

heronalps

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

heronalps

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

heronalps

cxw111 发表于 2018-1-17 19:29
没事请问第一题前后连续是指一个node的prev和next都不为空么

第二题，当时面试官一只在问，有没有什么方法，可以不用遍历整个字典？你有什么想法吗？

cxw111

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

sky9999

用prefix 来处理 dict 的words，如果prefix不匹配，所有包含该prefix的word都不匹配。

sky9999

heronalps 发表于 2018-1-19 01:54
第二题，当时面试官一只在问，有没有什么方法，可以不用遍历整个字典？你有什么想法吗？

预处理字典 dict--> trie