s********x
发帖数: 914 | 1 // input I AM Engineer
// output Engineer AM I
public static char[] reverseWordinString(char[] string){
char[] result = new char[string.length];
int k = 0;
for (int i = string.length-1; i >=0 ; ){
if (!isWord(string[i])) {
int j = i;
while (j>=0&&!isWord(string[j])) j-- ;
if (j==0 && !isWord(string[0]))
result[k++] = string[0];
for (int t = j + 1 ; t <= i ; t ++)
... 阅读全帖 |
|
T*******e
发帖数: 4928 | 2 哈，咱们思路差不多。
bool wordBreak(string s, unordered_set &dict) { //Time: O(n^2)
int sSize=s.size();
if(sSize<=0||dict.empty()) return false;
vector isWord(sSize+1, false);
isWord[0]=true;
for(int i=1; i<=sSize; ++i) {
for(int j=i-1; j>=0; --j) {
if(dict.find(s.substr(j, i-j))!=dict.end() &&isWord[j]) {
isWord[i]=true;
break;
}
}
}
return isWord[sSize];
}
reused |
|
p*****2
发帖数: 21240 | 3 trie =
isword: false
add = (trie, word)->
if word.length is 0
trie.isword = true
else
ch = word[0]
trie[ch] = {isword:false} unless trie[ch]?
add(trie[ch], word[1..])
exists = (trie, word)->
return trie.isword if word.length is 0
ch = word[0]
trie[ch]? and exists trie[ch], word[1..] |
|
k****n
发帖数: 8684 | 4 #!/usr/local/bin/perl
open FH, shift @ARGV;
map{ chomp; $isword{uc join "", sort /./g} .= "$_+" } ;
map{ chop $isword{$_} } keys %isword;
请问大牛们，
1）这两个map执行什么操作？
2）有什么经典的perl书籍可看吗？
多谢了。 |
|
h****n
发帖数: 1093 | 5 来自主题: JobHunting版 - 贡献一道题 写了一个，没测，楼主测测有问题告诉我
bool isWord(string s)
{
if(s=="this") return true;
if(s=="is") return true;
if(s=="desk") return true;
if(s=="top") return true;
if(s=="desktop") return true;
return false;
}
void Helper(string &inputS, int start, string &tmpStr, vector &res)
{
if(start == inputS.size())
{
//删除多余的空格
tmpStr.erase(tmpStr.end()-1);
res.push_back(tmpStr);
//补回来以便正确的backtracking
tmpStr.push_back(' ');
return;
}
int i;
stri... 阅读全帖 |
|
r**d
发帖数: 90 | 6 来自主题: JobHunting版 - 贡献一道题 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
static private bool isWord(string s)
{
switch (s)
{
case "this":
case "is":
case "a":
case "all":
case "some":
case "allsome":
return true;
}
return fal... 阅读全帖 |
|
s********u
发帖数: 1109 | 7 之前有人放过这个题，就是提供一个bool isWord(string s)的函数，要求得到一个
string拆成若干个word的所有组合，word之间用空格隔开。
自己写了下，用递归 + memoization，想问问这个题有iteration的做法么？如果是每
个string有唯一解（只有一种拆法）呢？
vector wordBreak( string str, map >& cache){
vector vs;
if( str.empty() ){
vs.push_back(str);
return vs;
}
if(cache.count(str) > 0)
return cache[str];
string prefix;
string suffix;
vector segSuffix;
for( int len = 1;len <= str.s... 阅读全帖 |
|
g**********y
发帖数: 14569 | 8 字母重不重复出现没关系，大致code:
public void dfs(String str, Trie trie) {
if (str.length() == 0) {
if (trie.isWord()) print(trie.word);
}
char number = str.charAt(0);
for (c : getCharacter(number)) {
Trie next = trie.get(c);
if (next != null) dfs(str.substring(1), next);
}
} |
|
p*****2
发帖数: 21240 | 9
DP呀。简单来写。
List Split(string s)
{
if(s.Length==0)
return null;
List output;
for(int i=0;i
{
if(isWord(s.SubString(0,i+1))
{
output.Add(s.SubString(0,i+1));
List tmp=Split(s.SubString(i+1,s.Length-i-1));
if(tmp!=null)
output.AddRange(tmp);
break;
}
}
return output;
} |
|
s******n
发帖数: 226 | 10 简单写一下把
input char a[n];
func(char* a){
int n = strlen(a);
int f[n];
for(int i=0;i
int max =0;
for(int j=i;j>=0;j--){
if(isWord(a,j,i) && f[j]+1>max){
max = f[j]+1; f[i] = max;
// prev array to bookkeep
// max can be defined using different standard.
}
}
}
} |
|
m***n
发帖数: 2154 | 11 这题标准解法怎样的？
能想到的 办法 一是拆字， 二是trie，取最长路径包含最多isWord =true ?
大家讨论一下。。 |
|
g**********y
发帖数: 14569 | 12 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... 阅读全帖 |
|
w****x
发帖数: 2483 | 13 DP解法:
dpRec[strlen(str)]
dpRec[i]: if true, previous character can split to words
for (int i = 0; i < strLen; i++)
for (int j = i; j >=0 && !dpRec[i]; j--)
dpRec[i] = true if dpRec[j] && isWord(str[j..i])
时间复杂度O(n^2) |
|
o******a
发帖数: 90 | 14 这周一去onsite了一个在湾区的小游戏公司，回来后跟HR通了电话，大概意思是onsite
是过了，但是因为我的OPT七月才开始，之前他们不能让我工作（我说unpaid行不，他
们说不行，要工作就要pay），结果没有拿到offer。。。这个也怪我，之前不是很明白
，以为只要unpaid就什么时候都可以工作，现在才发现原来OPT开始的时间太晚也是个
Deal Breaker。。。想请教一下坛子里的大牛有没有遇到过这样的问题？如果要是7月
份开始工作的话，现在找工作是不是有点早了。。。？我现在主要找的都是小公司，大
公司像Google，Facebook，Microsoft之类都已经木有戏了。。。如果哪位大牛有过这
方面经验或者了解一二，欢迎指点迷津，小弟感激不尽。
虽然开始逛本版不久，但还是看了很多面经，现在也回报一下社会吧！题都比较简单，
大家也就简单看一下。
1。设计一个算法，判断五子棋谁赢了。输入是一个棋盘，黑白子已经摆好，只要判断
输出boolean就行。follow－up：用什么方式改进brute－force的递归？
2。设计题。假设一个手机游戏，有地图的那种，屏幕只能显示整个地... 阅读全帖 |
|
g*********e
发帖数: 14401 | 15 usually the dictionary is built and you are given functions like isWord() to
use.
You can build dictionary by hash table, or trie |
|
m******s
发帖数: 204 | 16 前一个想法需要记录很多无用的中间信息，下面的想法除了hash table, 还需记录额外
的m个boolean：IsCombination(c[m-1, m-1]), IsCombination(c[m-2, m-1])...
IsCombination(c[k, m-1])原因是避免重复计算， 试想如果已经递归过IsCombination
(c[k, ... m-1], 那么相应的一些较短的以c[m-1]结尾的字符串也被判断过。
和zhangchitc 想法的区别在于对已遍历的前k个字符不做IsCombination的考虑
代码与之前一个帖子类似但加了中间结果存储：
bool IsCompositeWord(char* word， int start, int end, bool* table)
{
//check whether it is recorded before
if (table[start] == false)
return false;
//check all possible pair: check first is word or n... 阅读全帖 |
|
D**f
发帖数: 439 | 17 貌似这里出现过了，但不记得有没有人做出来过。
给你一个起始字符串，一个终点字符串，每一步你可以插入，删除，改变一个字符，但
要求结果是个字典中的word（已经提供 bool isWord(string) 这个函数）。
求最小步数，给出time complexity. |
|
r**d
发帖数: 90 | 18 来自主题: JobHunting版 - 贡献一道题 给定 bool isWord(string s)
create function to print all words based on a string
for example， input: this is desktop
output is: this is desk top
this is desktop
题好象从没见过，大家讨论一下 |
|
y***5
发帖数: 21 | 19 结果：面试7家，5 onsite，3 offer。
面经：
Amazon：2轮电面，5轮onsite。2天后offer，最后decline，非常nice的manager（拿到
A offer时还在面其它公司，比较大度地祝我good luck），拒绝的时候感情上比较难受。
电面1，设计parking lot
2， intersection of sorted int array; design data structure for a phone
contact book
onsite 1: find biggest int in array,
find K biggest int in array(tradeoff between many methods),
implement using heap
2: print modification path from "head" to "tail", given isWord()
api and every time can modify 1 word in the strin... 阅读全帖 |
|
z*********8
发帖数: 2070 | 20 resume talk
算法:
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
的答案。
没答好， 用了recursion没想到DP.
问： 怎么知道某个问题可以用DP做？ |
|
s********u
发帖数: 1109 | 21 C++写了一个，如果不用DP的话，把这个map去掉即可，试了一两个字符串似乎没问题。
vector wordBreak( string s, map< string, vector >& cache){
vector vs;
vector suffixSet;
string tmp;
if( s.size() == 0 ){
vs.push_back(s);
return vs;
}
if(cache.count(s) > 0)
return cache[s];
string prefix, suffix;
for(int i = 1; i <= s.size(); i++){
prefix = s.substr(0,i);
if( isWord(prefix) ){
... 阅读全帖 |
|
s********u
发帖数: 1109 | 22 哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
比如这个题：
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
的答案。
如果要求用dp的话，递归还是要比循环好写很多吧。。 |
|
S*******C
发帖数: 822 | 23 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
w*****h
发帖数: 423 | 24 interview 1:
1. 给一个char[]和一个字典，求所有在字典中并且由char数组里字母构成的单词，假
设isWord()可以直接判断某个单词在不在字典里。
2. 数组的permutation
3. 你会怎么设计1中的字典？
interview 2:
1. 8进制数的plus one
2. 写一个树（非二叉树）的iterator,注意不是traversal，并分析复杂度。
题目都不难，但是还是避免不了小bug，希望能过吧。。。顺求bless |
|
g*****g
发帖数: 212 | 25 需要澄清，1 char数组中部分字母还是要求全部字母组成单词， 2 数组中有重复字母吗
1.1， 1.2同一个意思吧，似乎只能试该数组的permutation，挨个检查isword了。
假设全部字母组成单词，允许重复：
1.3 字典：trie，字典中所有单词，trie 路径是按 a-z顺序排序的变形词，叶子结点
保存原始单词
peek => e->e->k->p (peek)
如此 输入char数组，排序是O(n)， match O(n) |
|
f**********2
发帖数: 2401 | 26 类似电话面板的一道题，输入是一个List digits, 一串数字，每个数字对应
可以翻译为3个character。翻译后的结果的pertutation是否可以组成一个单词，如果
可以，保存为结果集，输出。
Example:
2--> 'a','b','c'
8--> 't','u','c'
如果输入是228，
228 --> 'aat','abu',...
可以用2个函数
digits2char(int d)
isWord(String u)
输出是'aat','abu',...中所有的是单词的结果。
Set phoneWords(List digits){
}
自己有点紧张，题目不难，答得不太好，小毛病很多。供大家参考 |
|
x****g
发帖数: 1512 | 27 有啥特殊要求？
public static HashSet phoneWords(List digits)
{
HashSet words = new HashSet();
StringBuilder sb = new StringBuilder(digits.Count);
phoneWords(digits, 0, words, sb);
return words;
}
public static void phoneWords(List digits, int index, HashSet<
string> words, StringBuilder sb)
{
if (index == digits.Count)
{
string word = sb.ToStr... 阅读全帖 |
|
u*****n
发帖数: 126 | 28 这家也遇到两个三哥，挂了。不过还好，没遇到三哥的公司给了offer。
Phone：
求两个List的交集，假设每个list中的interval都是disjoint的。
onsite:
1）给你一个list的字符串，找出一个list的prefix，从而可以uniquely identify每个
字符串。
Hint：此题可以用trie来解决
2）给你一棵树，implement一个iterator，可以是BFS或者DFS。要求用iterative
method来实现。
Hint：选择DFS
3）压缩算法。用树的变形来表示一个string，比如 B->left = A, B->right = A, 此
种情况我们可以把B的left, right同时指向A。
问题1）对于一个有n个节点的树，可以表示的最长string的长度
问题2）implement get(Tree t, int position)，返回这个字符串在position的字符。
Hint：exponential + binary search
4)猜字游戏，有一个board和dictionary，从一个字符出发... 阅读全帖 |
|
d******e
发帖数: 2265 | 29 如果是split到list.那么就是看regex split出两个还是一个lis的问题了。
如果split到一个list,if isword, 指针交换，
如果split到两个lists, merge splited word和 splitters.
python的话，
>>> re.split('(W+)', 'this,,,is.a word')
['this', ',,,', 'is', '.', 'a', ' ', 'word']
剩下的没有什么难度了。 |
|
s********d
发帖数: 103 | 30 其实它的发展方向是 iSword and iGun |
|
S*******C
发帖数: 822 | 31 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
