e***n
发帖数: 42 | 1 一个文件，每行一个单词，要求编程输出所有的 anagram，比如：
input:
abc
bac
asbd
sadb
output:
[abc, bac]
[asbd, sadb]
写了一个Java的，请帮忙高手帮忙看看有什么可以改进的：
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;
import java.util.Arrays;
public class FileReadTest {
public static void main(String[] aArgs) throws IOException {
String fileName = aArgs[0];
String word;
String anagram;
Map wTable = new HashMap();
// Read words from file
List text;
Scanner scanner = new Scanner(n... 阅读全帖 |
|
e*******s
发帖数: 1979 | 2 Given an array of strings, return all groups of strings that are anagrams.
All inputs will be in lower-case
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
9章的参考程序如下, 他给每一个string换成26长度的int array. 然后用这个array生
成一个hash code. 问题是这个hashcode能够唯一对应一个anagram么. 不同的anagram
有没有对应同一个hashcode的可能 (考虑int overflow的情况下).
public class Solution {
private int getHash(int[] count) {
int hash = 0;
int a ... 阅读全帖 |
|
D********g
发帖数: 650 | 3 用HashTable存target的anagram, e.g., {s->1, c->2, d->1, b->1}。
然后用一个同等长度的window在source里平移，对每个字符，如果不在HT里，则非
anagram，否则对应字符freq --，如果freq < 0，则非；如果整个window走完，则是
anagram。
O(n) |
|
A*******e
发帖数: 2419 | 4 Given an array of strings, return all groups of strings that are anagrams.
vector anagrams(vector& strs);
难道不应该是vector>？这样才能把anagram放在一起啊。 |
|
j***y
发帖数: 2074 | 5 在看Hacking_a_Google_Interview_Handout_2.pdf，里面提到：
Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all
valid anagrams for that string (all valid rearrangements of the letters that form
valid English words)? You are allowed to pre‐compute whatever you want to and
store whatever you optionally pre‐compute on disk.
Answer: We want to use a hash table! If your interviewer really hates hash tables (which they sometimes do for some... 阅读全帖 |
|
y****e
发帖数: 1012 | 6 Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
为啥string vector太大的时候结果是错的呢？
大家帮忙看看吧~~
谢谢！
#include
#include
#include |
|
i**********e
发帖数: 1145 | 7 应该没什么问题，但不是 anagram 的你的程序也会打印。
例如 [abc, bcd]
应该是没有 anagrams 的。 |
|
p*****2
发帖数: 21240 | 8 anagram大家都知道怎么回事吧
给两个string，S和T
现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符
，问最小的操作次数可以完成这个转换
如果按照最小的次数可以有多种结果，那么输出按字典顺序最小的那个 |
|
S*******C
发帖数: 822 | 9 input是一个stirng list，判断他里面的元素是不是anagram，如果都是anagram返回
true，其他返回false，大小写有区别。写完给他解释一遍code，然后他问我有没有bug
，我看了半天胆怯的说没有，他也没跟我继续讨论corner case什么的，让我分析一下
时间复杂度。 |
|
Q**w
发帖数: 41 | 10 请问input的string list里面所有string互为anagram，还是说有不同组的anagram？ |
|
S*******C
发帖数: 822 | 11 好方法，但这题的题意是指所有的单词都组成一组anagram还是说所有的单词都可以找
到对应的anagram? |
|
d*****c
发帖数: 605 | 12 题意有点不清楚，是说这个里面只有一种anagram还是说可以有多种anagram？
bug |
|
q*z
发帖数: 13362 | 13 应该可以design一个hash，把所有的anagram map到一个值上，这样就是o（n）.
比如把字符视为27进制的数，a为1，z为26，先sort再转换，这样的hash应该是所有的
anagram map到同一个值的
hash计算可以从a到z扫描26遍，逐个进位。复杂度o（k）k为字符串长度。
注意hash变量的最大值会限制能处理的字串最大长度。 |
|
r*f
发帖数: 731 | 14 【 以下文字转载自 OnTheRoad 讨论区,原文如下 】
发信人: ryf (青山相待白云相爱), 信区: OnTheRoad
标 题: Anagrams --一种字谜游戏
发信站: Unknown Space - 未名空间 (Thu Sep 25 13:45:39 2003) WWW-POST
游戏规则：颠倒字母后组成新词，但意思和未颠倒的差不多。
举个例子---
“two plus eleven" and "one plus twelve"。
Other famous or notable anagrams:
a decimal point = I'm a dot in place
a stitch in time saves nine = this is meant as incentive
animosity = is no amity
astronomer = moon starer
circumstantial evidence = can ruin a selected victim
desperati |
|
h*****g
发帖数: 312 | 15 careercup 书上的答案对吗？
Finding if two string are anagrams of each other.
我认为
1.先判断string1 和 string2 长度是否相等
2.然后把string1 的所有字符 用个int[256]的数组过一遍，
3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
=0了就说明不match。
这几步就足够了吧？没必有想书上弄得那么complex吧？
如果我的想法不对，请帮忙给我举一个counterexample.
多谢~ |
|
|
W**********r
发帖数: 8927 | 17 没看过这题，Google了一下，说这两个是Anagram：George Bush = He bugs Gore，一
个长度是11，一个是12，因为空格数不同，还有的有Single Quote的也算，比如：A
decimal point = I'm a dot in place；那这长度判断有啥用？ |
|
h****a
发帖数: 70 | 18 比如说，一篇novel，如何group anagram: stop, post, spot....
要是用stl map的话，算法复杂度是多少？是对每个word先排序吧，
想不太明白。
谢谢！ |
|
w****x
发帖数: 2483 | 19 在一个大串中查找和另外一个字符串是anagram的子串:
GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
就是两个指针一前一后, 但是每次查找都要检查rec[256], 时间复杂度是256*O(n), 其
实还不如nlogn. 有其他简单的办法吗?? |
|
c****p
发帖数: 6474 | 20 hash一下不就行了么。。
滑动窗口，每滑动一次O1的代价。
hash不同就跳过，相同的话验证下是不是真的是anagram。 |
|
s*******f
发帖数: 1114 | 21 This is O(n). Hard to explain, but i think it deserve to go through it with
your test case.
//zzzz码遍本版，回报本版zzzz
//在一个大串中查找和另外一个字符串是anagram的子串:
//GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
string GetAnagram(const char *s, const char *sub){
int ls = strlen(s);
int lsub = strlen(sub);
if (ls < lsub || lsub < 1)
return "";
int mp[256];
memset(mp, 0, 256 * sizeof(int));
while (*sub){
++mp[*sub++];
}
const char *p = s;
int count = 0;
whil... 阅读全帖 |
|
s********x
发帖数: 914 | 22 Time Limit Exceeded了
但感觉已经cache了intermediate result了
是不是这题assume只是26个小写英文字母呢，如果是的话，用array就更快？
贴一下code
class AnagramString {
boolean visited;
String str;
private Map map = null;
AnagramString(String s) {
this.str = s;
}
boolean isAnagram(String s) {
if (this.map == null) {
this.map = new HashMap(this.str.length());
for (int i = 0; i < this.str.length(); i++) {
char c =... 阅读全帖 |
|
s********x
发帖数: 914 | 23 谢谢！
这个思路本来也有想到，感觉space开销很多。现在细想一下，确实不用inner loop的
linear search，应该会快很多。
已经过了OJ
class AnagramString {
boolean visited;
String str;
AnagramString(String s) {
this.str = s;
}
static String getKey(String s) {
char[] a = s.toCharArray();
Arrays.sort(a);
return new String(a);
}
}
public class Solution {
public ArrayList anagrams(String[] strs) {
Map> map = new HashMap
, Has... 阅读全帖 |
|
T******e
发帖数: 157 | 24 lz很下工夫啊，一个简单的anagram涉及到了这么多东西，态度值得学习。 |
|
|
|
l******n
发帖数: 1250 | 27 Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
本来还想偷懒，写个O(n2)的算法了事，结果直接被面试官叫停
后来被迫想O(n)算法，好在稀了糊涂地写出来了
我45分钟之内，就写了这一道题
看板上的其他兄弟，随便就是写两道题。 我估计不是挂掉了，就得再加面一轮。 |
|
x****u
发帖数: 12955 | 28
为什么要先sort，然后再做hash？先检测长度，不同则不是。长度相同就直接挨个比较
两个string的字母，一个从前向后，一个从后向前，任何时候有不同就证明不是，中断
循环。循环正常完毕就证明是anagram。
还有应该可以把其中一个string反过来存储。然后把两个string做一个XOR。结果不是0
的就不是。 |
|
l******s
发帖数: 3045 | 29 anagram is in different logic of palindrome |
|
x****u
发帖数: 12955 | 30
啊。错成这样。脑子糊涂了。
不过，还是不用sort，假设字符是英文字母，就设两个个26单元的array。然后一个
string从前向后，另一个sting从后向前，见到一个字符就把对应的那个array单元加一
。最后然后比较两个array，每个单元的数字都一样的就是anagram/ |
|
A*******e
发帖数: 2419 | 31 Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Input: {""}
Expect {}, not {""}. But why? |
|
发帖数: 1 | 32 代码看着有点奇怪，既然已经设置了int[] count, 每次将str的每一个字母放进去之后
，然后从0到26依次搜集这些字母，遍组成了一个hash code，这样互为anagram的两个
字符串将拥有相同的hash code. 上面求解hash的 a *= b 存在溢出的风险。 |
|
O******e
发帖数: 734 | 33 I don't know what to say about Newcastle's obsession with Spanish
omelettes except to offer this anagram puzzle:
"So, Newcastle had some good freshly baked Spanish omelettes."
=> "__ ___, ________ ______ ____ _____ ___ ______ ___
_____ __ ___!"
I'll give clues if the right questions are asked, or if someone tells a good joke.
I haven't decided what the prize will be, but it won't be a Spanish omelette. |
|
O******e
发帖数: 734 | 34 I'm no beefcake, no photo from me.
"Photos" is not what I had in mind as the solution, but who knows,
maybe we could come up with a better anagram with "photos" than
the word I had in mind for that position.
So, Newcastle had some good freshly baked Spanish omelettes.
My God, beefcake photos ____ _____ ___ ______ ___ _____ on ___! |
|
O******e
发帖数: 734 | 35 Here's my anagram that includes the word "photos":
"My dear God, alas! Don't these beefcake photos show smelliness?"
I hope those photos are not printed with a new Scratch N' Sniff scent!
http://www.promobrands.com/scratchnsniff.htm |
|
D********g
发帖数: 650 | 36 加上了backtracking:
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
f... 阅读全帖 |
|
D********g
发帖数: 650 | 37 20分钟写了大约下面的code，如果要输出string，还要backtrack:
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
for (int i = 0; i < word.length(); ++i) {
int charVal = (int) word.charAt(i);
ht[charVal] ++;
}
StringBuilder anagram = new StringBuilder();
for (int i = 0; i < ht.length; ++i) {
if (ht[i] > 0) {
anagram.append((cha... 阅读全帖 |
|
c***n
发帖数: 588 | 38 1. Given an array of words find what is and how long is the length of the
longest common substring between two words in the array. Give best solution
and provide time complexity analysis.
2. Given a list of words output the largest anagram derivative contained in
that set. The definition of an anagram derivative is: Consider the word 'cat
' as a basis, then the word 'tack' is said to an anagram derivative of 'cat'
since it can be re-arranged and appended with an alphabet to form the word
'tack'.... 阅读全帖 |
|
m********6
发帖数: 58 | 39 LZ在GOOGLE面试过两次， 第一次是大学毕业。 为了追CHICAGO的一个女孩子， 申请了
GOOGLE CHICAGO的位子。第一轮CAMPUS面试通过， 第二轮NEW YORK后， 收到CHICAGO
的EMAIL问我availability说要为我订机票第三轮面试， 三天后却收到NEW YORK的电话
说我申请的位子取消了， 我没被录用。后来我在NEW YORK找了一份IT的工作。 三年后
， 我决定跳槽其他的IT工作， GOOGLE刚巧邀请我去面试， 所以我第二次去GOOGLE面
试。 这次拿到了offer， 但是也拿到了更好的HFT的offer。虽然没去GOOGLE工作， 但
是我很喜欢GOOGLE的面试， 觉得每次都有收获。在此分享一下我被问过的问题。我也
很希望看到其他朋友们的面试问题， 我会当兴趣爱好来试解答。
Behavior Questions:
1. In java, a method declared as private restrict access to within the class
. For example, a private void do... 阅读全帖 |
|
q******n
发帖数: 661 | 40 99U Insights on making ideas happen
by Bēhance
Leadership
What Motivates Us To Do Great Work?
by Jocelyn K. Glei
608629
What motivates us to do great work? It’s an age-old question. But the age-
old answers – rewards, recognition, money, stability – no longer seem to
suffice. As we’ve shifted to a knowledge-based economy, it turns out that
what drives us has shifted, too.
Recent research reveals that when creative thinking is part and parcel of
your job description, external motivation just does... 阅读全帖 |
|
c***n
发帖数: 588 | 41 来自主题: JobHunting版 - 求解一道题 Given a list of words output the largest anagram derivative contained in
that set.
Take an anagram derivative as:
Consider the word 'cat' as a basis, then the word 'tack' is said to an
anagram derivative of 'cat' since it can be re-arranged and appended with an
alphabet to form the word 'tack'. This process can be performed repeatedly,
so that the word 'tacky' is an anagram derivative of 'tack'.
Now given a list of words output the largest anagram derivative in that list
. |
|
B**********2
发帖数: 923 | 42 Amazon
1.括号匹配
1.1 已知一个字符流，只有'('或者')'，检查是否是balance
解：用一个数maintain，以0开始，遇到'('就加1，遇到')'就减一。进行中如果小于0
，直接就return false. 全扫完如果等于0就return true, 否则return false
1.2 已知字符流包括 (,[,{ 和 ),],}，检查是否balance
解：不用数maintain，而改用一个stack，碰到匹配的就pop，否则push，空栈再碰到任
意右括号，直接return false。如果全扫完是空栈return true, 否则return false
2.Anagram
给一个数组的单词，要求输出顺序为anagram，即如果有 tea, cat, eat, 那么tea和
eat一定要挨着
解：同一anagram单词特点是把这个单词按字母排序之后，长得都一样。所以用一个字
典来维护anagram
同一单词排序后为key, 关于单词的list就是value。如果有这个key,就append到list里
，没有就另开一个。最后把这些anagram连起来输出
G... 阅读全帖 |
|
w*****1
发帖数: 6807 | 43 刚自己做了下，想法：字典肯定不能动，只能在给出的word上下功夫
1.把给出的word的所有anagrams存一个vector anagrams，用next_
permutation
2.再找每个anagrams里的词是不是在dict里面
时间复杂度应该是factorial(n)，因为所有permutations有factorial(n)个，这里n
是给出word的长度。
代码如下，已测试，板上大牛有更好想法还希望指出，我好改正
-------------------------------------------------------
vector allPermutations(string &s) {
vector result;
if (s.empty()) return result;
sort(s.begin(), s.end());
result.push_back(s);
while (next_permutation(s.begin(), s.end())) {
... 阅读全帖 |
|
w***y
发帖数: 6251 | 44 我就不一一说是哪个公司的题目了:)
1. write a function to calculate the cube square root of x
2. given a set of elements, all possible subset
3. prefix search -- given a set of words, and a prefix, find the words
starting with the prefix
4. anagram bucket - anagram means different words with the same character
set, e.g., 'cat' and 'act' are anagram . Given a set of words, group them by
anagram.
=========================================
1. iterator with filter, 跟这个帖子的 2A一样
http://www.mitbbs.com/article_t/JobHunti... 阅读全帖 |
|
R**y
发帖数: 72 | 45 ZocDoc是一个不错的公司。市场前景不错，没有对手。
Skype Interview，一个亚裔小伙，人很nice，题目也不难
Reverse Linked List.
我开始用stack实现，结果返回的head是为null，初始化赋值的地方出错
Node result = null;
Node head = result; // 这个地方，即时将来result 会赋上新值，head依然为null。
然后处理头节点的时候，没有将其的next赋为空。。。。
接着一看不行，用for loop 直接做，返回值又弄错了，返回了是反转结果的最后一个
节点。。。。
no.2 打印一个string所有可能的subset的anagram，
这道题饿做错了，我只打印了当前字符串所有可能的anagram，而且面试官没看出来我
错了，他也误以为是只打印所有anagram。
这道题如果要打印所有subset的 anagram，我觉得至少O(2^n),字串就有这么多。。。
攒个RP，这是第二个电面，发现如果做新题，很容易慌，直接就容易跪，即使能做出来
也经常出这样那样的小bug，需要面试官带着才能做对
----... 阅读全帖 |
|
R**y
发帖数: 72 | 46 ZocDoc是一个不错的公司。市场前景不错，没有对手。
Skype Interview，一个亚裔小伙，人很nice，题目也不难
Reverse Linked List.
我开始用stack实现，结果返回的head是为null，初始化赋值的地方出错
Node result = null;
Node head = result; // 这个地方，即时将来result 会赋上新值，head依然为null。
然后处理头节点的时候，没有将其的next赋为空。。。。
接着一看不行，用for loop 直接做，返回值又弄错了，返回了是反转结果的最后一个
节点。。。。
no.2 打印一个string所有可能的subset的anagram，
这道题饿做错了，我只打印了当前字符串所有可能的anagram，而且面试官没看出来我
错了，他也误以为是只打印所有anagram。
这道题如果要打印所有subset的 anagram，我觉得至少O(2^n),字串就有这么多。。。
攒个RP，这是第二个电面，发现如果做新题，很容易慌，直接就容易跪，即使能做出来
也经常出这样那样的小bug，需要面试官带着才能做对
----... 阅读全帖 |
|
g**u
发帖数: 583 | 47
to
那每一个char都可以认为是anagram么？如果是的话，是不是所有的都是可以认为都是
anagram了？
如果不是的话，那么按照anagram对称的原则，把所有的char scan一边，然后count每
个char出现的次数，有仅有一个char出现是奇数，所有其他都是偶数的话，那么就可以
把它分为一个anagram？ |
|
r********g
发帖数: 1351 | 48 申请的暑假intern，当时整体感觉不是很好，主要是只复习了算法，C++的书没看完，
发现还是自己掌握的有点窄了。已经收到信说挂了，基本都是板上出现的题，继续努力
吧。
第一个面试是老印，我觉得老听不清，还觉得是跨州所以信号不好，结果到第二个面试
才发现是带耳机影响了声音，而且以为会有编程，结果也没有。。。
1. 介绍google，这个大概用了快10分钟吧。。突然发现这时候我总是不知道该说啥。
。。虽然我不用说，但是我也不知道礼貌性地“yes”，“ok”一下是不是更好。。。
2. 简历的问题，比如我用的一些编程工具，他说他是google earth组的，然后顺便说
了一下他用的工具什么的。。
3. C/C++问题，什么是explicit，这个不会-_-！，不过他也不是单纯问这个，还给了
例子程序，问了C++ string constructor，和C里面的char array的区别什么的，还有
指针和compiler的问题。其余的估计都答出来了吧。
4. 算法，著名的anagram问题，判断2个词是不是anagram，然后是一本书里所有的
anagram，hash table和hash |
|
t**********n
发帖数: 145 | 49
==============================================================
这里的anagram不是基于语义的啦，只是基于字母组合，比如tan, nat是ant的
anagram。字典文件的每一行就是一个单词，没有其他的了。
通常的做法是，先load字典文件到一个hash，每读到一个word，按alphabeta
将letter、排序，作为hash-key，然后存进到hash里面，每个hash-key对应
一个list存有相同key的所有word。
需要求解某单词的anagram的时候，就只需要look up一下hash表就可以了。
这个方法的复杂度是O(1)。pre-computation的复杂度O(n)，其中n是字典的
大小。
此题在《Hacking Google Interview》的handout中有。 |
|
m**q
发帖数: 189 | 50 每次直接计算signature我觉得需要O(m),因为我们需要anagram所以
无法像RK算法那样增量计算，最终的复杂度应该是O(mn)
（n为字符串a的长度，m为b的长度）
我想到的一个改进是：
1） 用一个数组统计b中每个字符出现的次数，如果字符串只包含
a~z，长度为26的数组就够了，设此数组为limit[]
2） 用一个长度为m的窗口扫描a，用一个长为26的数组cnt[]统计
每个字符在窗口中出现的次数（只统计在b中出现的字符），另外
维护一个counter，
在把字符c加入窗口时，cnt[c]++, 如果cnt[c] <= limit[c]则递增counter；
在把字符c从窗口中拿走时，cnt[c]--,如果cnt[c] < limit[c]则递减counter，
当counter==m的时候则找到b的anagram。
这里counter的使用，使得每次判断anagram可以用O(1)实现，
于是整个算法可以用O(m+n)完成。
这里借鉴了 darksteel 在计算最小包含窗口那个经典题的思路。 |
|
