1小时前Google Intern面经

heronalps

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

第一面：

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

第二面：

给定一个含有所有合法词汇的dictionary，以及String input。唯一允许的edit操作是remove字符，返回dictionary中与input匹配的word。

i.e. dictionary = [Hello, ello]

input = Hwellwo

return Hello

大家有什么想法？

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;
}

复制代码

heronalps

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

一个考完托福的废人

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

pumpkincat

想问下楼主为什么不同时return ello呢？

dingshilun

第一个题可以先预处理array到hashmap然后遍历一遍解决，
第二题可以对每个dict中的词扫一遍字符串看看能不能从前往后构成dict中的词，反正remove可以无限做，复杂度比较高，可以预处理每个字符的index然后用二分

flyMontain

第二题用trie?

cxw111

第二题感觉是lc的longes word through deleting

AmberWangjie

dingshilun 发表于 2018-1-13 13:27
第一个题可以先预处理array到hashmap然后遍历一遍解决，
第二题可以对每个dict中的词扫一遍字符串看看能不 ...

谢谢。请问第一题，可以说再详细一点吗？比如，怎么预处理array呢？其实楼主那个描述没太看懂

heronalps

pumpkincat 发表于 2018-1-12 18:51
想问下楼主为什么不同时return ello呢？

当时面试官要求只返回一个match entry就可以了。

heronalps

flyMontain 发表于 2018-1-13 04:18
第二题用trie?

我当时提到了第二题用trie，但是因为用户的input中，并不确定那一个字符会是多余的，所以用trie查询的时候，无法选择支路。

heronalps

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

heronalps

cxw111 发表于 2018-1-13 13:30
第二题感觉是lc的longes word through deleting

之前没刷过这道题。感谢！