狗家店面

第一次电面。刚做完，感觉要跪。面试官听起来是话少白人小哥。问题没很难但是楼主紧张脑子抽了简单followup没想出来。

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

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

祝大家能过吧，自己感觉凉了。- -

假设有传递性：
class Solution:
    def isSynonym(self, syn, queries):

        parentWord = {}

        for i, s in enumerate(syn):
            self.union(s[0], s[1], parentWord)

        res = []

        for query1, query2 in queries:
            wordList1 = query1.split()
            wordList2 = query2.split()
            if len(wordList1) != len(wordList2):
                res.append(False)
                continue
            flag = 0
            for word1, word2 in zip(wordList1, wordList2):
                if self.find(word1, parentWord) != self.find(word2, parentWord):
                    res.append(False)
                    flag = 1
                    break

            if not flag:
                res.append(True)

        return res

    def find(self, word, parentWord):
        if word not in parentWord:
            parentWord[word] = word
            return word
        tmp = word
        while parentWord[word] != word:
            word = parentWord[word]
        parentWord[tmp] = word
        return word

    def union(self, word1, word2, parentWord):
        pword1 = self.find(word1, parentWord)
        pword2 = self.find(word2, parentWord)
        parentWord[pword1] = pword2

from collections import *
class Solution:
    def isSynonym(self, syn, queries):
        wordDict = defaultdict(set)

        for i, s in enumerate(syn):
            wordDict.add(i)

        res = []

        for query1, query2 in queries:
            wordList1 = query1.split()
            wordList2 = query2.split()
            if len(wordList1) != len(wordList2):
                res.append(False)
                continue
            flag = 0
            for word1, word2 in zip(wordList1, wordList2):
                if wordDict[word1].isisjoint(wordDict[word2]):
                    res.append(False)
                    flag = 1
                    break
            
            if not flag:
                res.append(True)
        
        return res

补充内容 (2018-4-28 05:12):
should be:
            wordDict[s[0]].add(i)
            wordDict[s[1]].add(i)

shufezq 发表于 2018-4-28 04:59
一段时间没刷题了，leetcode是不是有个同义词的题目是这个意思？ 用hashmap加dfs或者union find可解，lz的b ...

这个题楼主好像没有说可以传递，如果不可以传递，union find就不适用了吧~

沙发~~~弱弱的问一下，queries = [(‘google in us’, ‘bestcompany in america’)(‘google in u.s.’, 'bestcompany in america')]的两个tuple为何一个return true 一个return false？这两个tuple不是一样的吗？

kiddyym 发表于 2018-4-28 03:46
沙发~~~弱弱的问一下，queries = [(‘google in us’, ‘bestcompany in america’)(‘google in u.s.’, ' ...

因为后面US有俩点………

Boba 发表于 2018-4-28 03:57
因为后面US有俩点………

啊酱紫，太不细心了，多谢指点！楼主用什么方法做的呢？

kiddyym 发表于 2018-4-28 04:03
啊酱紫，太不细心了，多谢指点！楼主用什么方法做的呢？

很蠢的方法，brute force，然后用syn做一个dictionary。

这题hashmap可解吧 问下楼主follow up是啥 谢谢啊

乐扣原题还是简单版的， follow up是加传递性吧

请问楼主follow up是什么呀？

一段时间没刷题了，leetcode是不是有个同义词的题目是这个意思？ 用hashmap加dfs或者union find可解，lz的brute force的方法是指用dfs？

补充内容 (2018-4-28 05:02):
对了，你这个syn的array里面只有两个括号的同义词？