|
H*M
发帖数: 1268 | 2 我也没明白什么叫hash不能在两台机器中传？
hash后ascii只有狠小的array,mapreduce的话，中间shuffle带宽肯定比这多 |
|
f*******t
发帖数: 7549 | 3 因为ascii码只有256个，所以用256的数组够用了。其实这就是简化的hash map。后面
关键字permutation的那题与这道基本相同，因为是Object所以用hash map。 |
|
w**z
发帖数: 8232 | 4 我再贴一下Java的sourcecode。不懂为什么要把正数转成负数再查溢出呢？有什么好处？
code里有Author的comments
// Accumulating negatively avoids surprises near MAX_VALUE
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* ASCII minus sig... 阅读全帖 |
|
i**********e
发帖数: 1145 | 5 HashMap 是 one to many relationship，hashtable one to one.
看情况，主要 hashtable 和 array 的区别在于前者比较 general：
比如，要计算一个字符串里每个字母的出现次数，用简单的 array 再也适合不过了。
如果只是 ascii 字符，那 256 的大小就够了。
那另外一个例子，如果要计算一本书里每个字的出现次数，那简单的 array 做不到了
。因为 key 是 word，不能直接以 index 来 hash，那就用比较general的hashtable来
做。
还有另一种情况 hashtable 是比 array 好的，就是节省空间。为什么呢？
比方你的 key 的range在于 1 - 1,000,000，但是最多你只会 insert 不超过 100 个
element。那用array来做，那相当于只用数组里的100个，其余的都是空的，非常浪费
空间。但是 hashtable就没有这个问题，因为是 dynamic 的数据结构。 |
|
r**********1
发帖数: 292 | 6 “那另外一个例子，如果要计算一本书里每个字的出现次数，那简单的 array 做不到了
。因为 key 是 word，不能直接以 index 来 hash，那就用比较general的hashtable来
做。”
我是想弄清出啊。对于这个例子，用hashtable是不是如下做法？
对于每个word，我算一个hash value, 比如把每个character的ascii码加在一块得到一
个sum值，我可以把这个sum值作为hash value。
然后，我建立一个大小为1000的数组，A，初始化为0。
然后，对于每个word，算出hash value，然后以它来作为index，把相应的A[hash]进行
++操作。
对于hash value 大于1000的，进行动态扩展数组，然后继续。
这么说来，hash table 似乎是高级的动态数组。
ihasleetcode，您觉得我的理解对吗？ |
|
w**z
发帖数: 8232 | 7 Source Code from Java
/*
* @author Lee Boynton
* @author Arthur van Hoff
* @author Josh Bloch
* @version 1.92, 04/07/06
* @since JDK1.0
*/
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* A... 阅读全帖 |
|
w*******s
发帖数: 96 | 8 再来一个拍拍：
////////////////////////////////////////////////////////////////////////////
////////
// Problem 1.1:
// Analysis and points:
// 1. strig operation(scan)
// 2. How to determine whether it's duplicate string?
// Method 1: using one hashtable, if it's already in
hashtable,
// it's duplicate, otherwise add into hashtable.
Complexity O(n)
// Method 2: for each characer, check whether it's duplicated
// ... 阅读全帖 |
|
e********r
发帖数: 2352 | 9 在本地的考试中心预约的上机考试。考试有三个部分，1.数学题，2.给出一种新的编程
语言的语法，回答相应问题，3. Programming Test 要求速度和准确性both important
Programming test 答得不好，肯定不行了，把面试题发上来让大家做做。做了3个半小
时，快累死了。
数学题基本上就是脑筋急转弯，举几个例子
1. You have three kinds of magazines, all but two are Times, all but two are
Science, all but two are Nature. How many magazines in total do you have?
3 books
2. Only one of the answers is true
A. All of the below are true
B. All answers are true
C. One of the above is true
D. All of the above are true
E. None of the above ar... 阅读全帖 |
|
h****n
发帖数: 1093 | 10 17:12
1.
vector > FindAllPairs(vector input, int givenSum)
{
vector > res;
vector oneRes;
if(input.size()<1) return res;
int i = 0; j = input.size()-1;
while(i
{
if(input[i]+input[j]
else if(input[i]+input[j]>givenSum) j--;
else
{
oneRes.clear();
oneRes.push_back(input[i]);
oneRes.push_back(input[j]);
if(find(res.begin(), res.end(), oneRes)==res.en... 阅读全帖 |
|
s*****3
发帖数: 87 | 11 对了，第一题还有个条件，就是这两个文件在两台不同的server上，并且彼此之间通信
带宽很小。我当时没有给特别肯定的回答，就说可以考虑用hash和bloom filter。然后
继续谈怎么样去用hash做，以及怎么设计hash函数(大体idea是把文件一段一段的ascii
取模)。对于第二个问题，set用bst实现，coding题我第一次写错了(当时只考虑了左右
字节点，而不是左右子树)，后来在他提醒下很快重新写了个实现。 |
|
y*****n
发帖数: 243 | 12 谢谢哦。是要找出那个不同的byte还是什么？ 不好意思我对题目不是很理解 = =是说
一个文件中有一个byte在另一个文件中没有出现过嘛？
ascii |
|
s*****3
发帖数: 87 | 13 对了，第一题还有个条件，就是这两个文件在两台不同的server上，并且彼此之间通信
带宽很小。我当时没有给特别肯定的回答，就说可以考虑用hash和bloom filter。然后
继续谈怎么样去用hash做，以及怎么设计hash函数(大体idea是把文件一段一段的ascii
取模)。对于第二个问题，set用bst实现，coding题我第一次写错了(当时只考虑了左右
字节点，而不是左右子树)，后来在他提醒下很快重新写了个实现。 |
|
y*****n
发帖数: 243 | 14 谢谢哦。是要找出那个不同的byte还是什么？ 不好意思我对题目不是很理解 = =是说
一个文件中有一个byte在另一个文件中没有出现过嘛？
ascii |
|
i******e
发帖数: 273 | 15 是不是写错了， 遍历两个字符串， 一个应该加conuter, 一个应该减，最后再检查数
组有没有那个下标不为0. 还有如果不是ASCII encoding，数组放不下了. |
|
w*******s
发帖数: 96 | 16 Two implementation. one use sort and one use hash.
//pre: str is sorted.
void PermutationWithDuplicate(char *str, int position)
{
if (position == strlen(str)) {
printf("%s", str);
return;
}
char lastChar = '\0';
for (int i = position; i
{
//skip those character which is duplicated. Since the string is
sorted, it's easy.
if (lastChar == str[i] ) continue;
lastChar = str[i];
swap(str[po... 阅读全帖 |
|
e***l
发帖数: 710 | 17 字符数字转换为整数数字，'0'代表0的ascii码 |
|
t*****s
发帖数: 14 | 18 2周前电面G家，一直没有消息，昨天果然收到据信。说是找不到和我背景match的职位
，blah blah，我觉得都是外交语言。我因为自己觉得电面过程还比较顺利，所以想拿
出来，请大家帮着分析分析，到底是什么原因被拒。
看网上一般电面都是连着两轮，但我只有一次。面试者看名字是白人，人很nice，说话
也比较清楚。一开始让我介绍了一下我简历中提到的一个项目，然后就进入coding。两
道题都是基本题。第一题是统计一个字符串里每个字符出现的次数。我先问了是ascii
还是unicode，他说unicode吧，我想这基本就是O(n)的算法，没有什么花样可以变，就
把代码写出来。他检查后觉得没有问题，然后问我如果字符串非常长的话怎么办，我于
是把数组和有关变量都改成long long。他说如果还要长怎么办，我一开始没有想到怎
么办，后来他提醒说指针，于是我理解他是希望直接用指针来index。第二题具体内容
有点忘了，大致是如何在脚本语言里动态获得对象的类。他问我能否用javascript写（
他自己是做javascript安全的），我因为有一段时间没用js，就提议用python写，他说
没问题。... 阅读全帖 |
|
h**********l
发帖数: 6342 | 19 是说遍历string要用pointer？ C string？
ascii |
|
g**********y
发帖数: 14569 | 20 我猜问题出在第一个上。
G的电面通常45分钟，会问两个coding题。第一个题判断你的水平，如果解答是他期望
的或者能解释得过去的，他就会问更难的。第二题做完一般就没时间了。如果你做到第
3道，说明你解得很快，多半会过关。
如果第一题他觉得你的方向不对或者基本功不够，第二题就是给你的最后一次机会，也
可能他已经判断不行了，剩下就是走过场。
象你说的第一题这种，问题本身不难，但是可以变化的条件很多，需要你提问把这些条
件限制住。在交流过程里，如果你问得不够多，没有问清楚，或者写得不clean, 他可
能认为你基本训练不够。第二题随便找一个，按理说他期望你能马上回答，结果你没答
上来，转到了python上。他的报告写上去就很一般，导致杯具。
这种情况发生，跟你真正水平关系不大，更多是你跟面试官交流的问题。
ascii |
|
l*********8
发帖数: 4642 | 21 Did you use a hash table to save the character counts?
ascii |
|
w****x
发帖数: 2483 | 22
Unicode的范围不是0-0xFFFE吗?? 就像ASCII一共有256个,
范围是0-255, 正好对应int rec[256]的index 0~255 |
|
p**o
发帖数: 1012 | 23 第一题map reduce行不？并发行不？非常长就是单机内存不够用吧
ascii |
|
|
|
p*******m
发帖数: 47 | 26 我5月初要去Twitter onsite，面的是 Trust & Safety team
2轮电面都比较简单，2个engineers都很nice.
但听说onsite 难度会明显加大, 而且我网上能搜到的它家的题目不多，特别是onsite,
所以心里没底，来版上求经验。
希望有面试经验的同学能和我分享, 如果不方便帖出来，你也可以我站内发信或者
email: d********[email protected]
这是recruiter给我的schedule:
11:30am 去公司签到, 然后面7个人, 其中有个 team Product Manager。每轮45min,
第1轮是 lunch interview,
7轮分别有coding, Ph.D. research presentation, large-scale system design (这
个是open question)
下面是我搜集到的Twitter的题目，有些版上有过了，给后来的同学作参考。
如果你们有新的题, 也可以回在下面.
希望版上它家的信息能多些
++++++++++++++++++++++++++++++++++++... 阅读全帖 |
|
p*****o
发帖数: 1285 | 27 Thanks. Here is the weird thing: this O(kn) method seems faster than any O(
n) implementation I tried. I have tried to mimic a hash table with an array
of 128 elements since LeetCode's test cases are limited to ASCII characters
. For the large test, the O(kn) method with map takes about 140ms, the fake
hash table method with tail pointer takes about 180ms, and the queue
implementation takes about the same amount time.
My guess is that the factor of "k" part is only run very few times, which
m... 阅读全帖 |
|
d******a
发帖数: 238 | 28 判断一个字符串输入是否有效数字；要求cover尽可能多的test case ，字符串里只有
ascii码。注意小数，正负数。
我觉得这道题其实不是很好写出好的代码啊，大家可以试着写写看，看看能不能cover
尽可能多的case. 基础题写好才是真的好啊。 |
|
w****f
发帖数: 684 | 29 Looking glassdoor's microsoft questions, do not figure out the answers
for below questions.
Did some one know the answers?
Queue with circular array
What are skip lists?
using a mac function toLower(char c) to write a toUpper(char c) function
, without using any ascii code
What is a singleton? |
|
w****f
发帖数: 684 | 30 Yes, but I am catching up...
I figured out skip list and singleton.
* Queue with circular array?
*using a mac function toLower(char c) to write a toUpper(char c)
function, without using any ascii code? |
|
w****f
发帖数: 684 | 31 Thanks for response. I knew this solution, but question is without ASCII
code. |
|
l****p
发帖数: 397 | 32 我觉得这题主要是考怎么构建树，至于树建起来了，怎么展现比较漂亮那是另一回事了
。这年头很少人会考用ASCII字符在控制台上打图形吧。顺便贴上我的实现：
class TreeNode
attr_accessor :value
attr_accessor :left
attr_accessor :right
def initialize value
@value = value
end
end
def get_trees preorder, head=0, tail=preorder.size
return [nil] if tail <= head
trees = []
for right_root in (head+1..tail)
left_trees = get_trees preorder, head+1, right_root
right_trees = get_trees preorder, right_root, tail
left_trees.each do |lt|
right_tree... 阅读全帖 |
|
G******i
发帖数: 5226 | 33 ☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Nov 9 17:30:25 2011, 美东) 提到:
听说变态的Amazon要人念code，总结了一个。
这里面叹号和圆括号单词音节有点长，也有点绕口。我个人倾向用bang和round
bracket。但bang似乎不常见。
! exclamation mark, bang
" double quote
# pound, sharp
$ dollar
% percent
& ampersand, reference
' single quote
( left/opening parenthesis/round bracket
) right/closing
[ left/opening bracket/square bracket
] right/closing
{ left/opening brace/curly bracket
} right/closing
< ... 阅读全帖 |
|
w****x
发帖数: 2483 | 34
如果是ascii是不是就用个int a[256]就可以了, 0代表没出现,-1代表dup, >=0 的代表
下标, 最后扫一遍a取>= 0的数里最小的 |
|
C****e
发帖数: 131 | 35 如下一个段code
string a = "1";
string b = "0";
cout <<(a[0] & b[0])<
输出的值是48。
我的问题是为什么不输出0，而是输出了‘0’的ASCII值。
看上去好像在&计算时，a[0]和b[0]分别做了 类型转换，从char转换到int，然后再&，
计算之后再转会char，cout时转换成了int。
这里有点糊涂，请问大家，这个计算过程是怎么样的？多谢 |
|
T**e
发帖数: 191 | 36 Suppose you are given a set of n people (with n even) to be seated at a
dinner party. The people will be seated along the two sides of a long table.
o o o o
+------------- ----+
| ... |
+------------- ----+
o o o o
Half are male, half are female. The given function g(p) identifies the
gender of a given person.
As the host, you also know an integer-valued "preference function" h(p1, p2)
for a pair of people p1, p2. The preference function ... 阅读全帖 |
|
|
g*****e
发帖数: 282 | 38 对。我还讨论了unicode，ascii，哄面试官开心 |
|
c********t
发帖数: 5706 | 39 都说local variable必须赋值，包括primitive
为啥我看到很多（大多数）程序，int[] 都不赋值就可以用和返回？比如下面统计字符
出现次数程序，对于int[] counts = new int[256];难道不用整个赋值0，再用和返回
吗？
int[] charCounts(String s) {
int[] counts = new int[256]; // maximum value of an ASCII character
char[] c = s.toCharArray();
for (int i=0;i
counts[c[i]]++;
}
return counts;
} |
|
h*********e
发帖数: 91 | 40 常看到说我们假设是asscii, 那如果不是呢，是不是就是会 》256 而已？谢谢热情的
人提供解答！ |
|
|
|
|
s*******y
发帖数: 44 | 44 其实我也是c用得比较多，就这题而言，所谓的hash其实不过是一个数组，以字符的
ascii码为index，和用table解决查找问题一样，以空间换时间。 |
|
r****m
发帖数: 70 | 45 iCloud组，所以他们问了很多文件存储方面的东西
1. Design a storage system to store files, while those files may have large
amount of duplicate content.
Count words in a document. 如果文件很大，内存装不下怎么办
2 sliding window
Memory copy
3 一个机器人，只能向下和右移动，给一个n*m的矩阵，求机器人从(1,1) 到 (m, n)
的路径树，leetcode原题
设计一个系统用来计算机器的数目
4 Lunch with Director, some detail about projects
5 N casino 30 day max profit, 每个赌场每天的盈利情况不一样，每天只能在一个赌
场，第二天只能跳跃到相邻的赌场
Max span in a tree
3 sorted linked lists find the min(|x-y|, |x-z|, |y-z|)
6 Bi... 阅读全帖 |
|
P*******b
发帖数: 1001 | 46 你定义的是stack,push进去的是int，肯定是超过ascii范围了
)) |
|
b****g
发帖数: 192 | 47 第一题
careercup里node都有指向parent的reference，所以不难。
如果面试里说没有这个reference，那就麻烦了。
第二题：
就是递归或循环的找两个字母怎么走。
先算出两个字母的坐标，用字母的ASCII值减'a'，比如c就是2，这样就能算出字母的横
纵坐标。
从（i,j）走向(m,n)就是横向走|n-j|次，纵向走|m-i|次
注意一下上下左右方向就行
trick就是字母Z要单独处理，因为那一行不能横向走，只能纵向走。 |
|
p*****p
发帖数: 379 | 48 有个问题，"abba"，你的描述好像会返回最后的a
我写了一个，看看有没有问题，想法差不多，就是循环的时候不删除到要返回的时候再
检查，这个最坏好像是n + (n - 1) / 2 + 1次（前面各出现两次最后一个出现一次）
char findFirstNonDuplicate(string str) {
int n = str.size();
if (!n) return '\0';
// assume string contains only ascii chars
int map[256] = {0};
list index_list;
for (int i = 0; i < n; ++i) {
if (!map[str[i]]) {
index_list.push_back(i);
}
++map[str[i]];
}
while (!index_list.empty()) {
if (map[str[index_li... 阅读全帖 |
|
s*****n
发帖数: 5488 | 49 bool findFirstNonDuplicate(string str, out firtchar) {
int n = str.size();
if (!n) return false;
// assume string contains only ascii chars
int map[256] = {0};
for(int i = 0 ; i < str.Length; i++)
map[str[i])++;
for (int j = 0; j < 256; j++)
if (map[j] == 1)
{
firstchar = map[j];
return true;
}
return false;
} |
|
n*****a
发帖数: 55 | 50 面一个cloud start up， 问了find first non-duplicated char 的问题。 我先用
vector写了code, interviewer 又问如果不是ASCII , 是Unicode, 该怎么办？改用map
但是他说算法不是O(n). 还有什么别的方法吗？ |
|
