t*******3
发帖数: 734 | 1 以下是computing degree的内容. 这跟 cs degree有什么区别呢?
General information about the computing degree here.
Tracks within the Computing Degree
MS in Computing: Information Technology
NOTE: this track has reached its capacity, we will not be accepting any more
students in this track for Fall 2011
The goal of the M.S. Computing Degree in Information Technology (MSIT) is to
train this new generation of technologists. It offers a mix of technology
and management courses to provide students with a solid backgro... 阅读全帖 |
|
g*****i
发帖数: 2162 | 2 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
g*****i
发帖数: 2162 | 3 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
b*******a
发帖数: 68 | 4 Given constant incoming requests, each associated with a unique key,
estimate the total amount of unique requests within a period of time. The
number of keys explodes the memory. Do not touch the disk. Rough estimation
is O.K
首先说明，这个题目不是很清楚。如果只是要找给定时间的统计，hash table +
counter (其实counter都不用)就好了。可是，如果是要求任意给定的时间呢？譬如，
过去1分钟，过去5分钟，过去1小时，1:00AM -- 1:30AM 等等。这类动态数据流统计一般用什么方法解决
？需要 Count-Min Sketch 变形吗？ 谢谢 |
|
S**I
发帖数: 15689 | 5 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the out... 阅读全帖 |
|
S******t
发帖数: 151 | 6 It is easy to come up with an $O(SL)$ algorithm for this problem but what is
good about this problem is that it actually has a linear time solution:
Let’s first make some notations clear:
1) |S| -> The length of S.
2) |L| -> The number of words in the list $L$.
3) $len_L$ -> The length of each string in $L$.
First we use an Aho-Corasick automaton to find out the occurrences of all
patterns. The time complexity of this step is $O(|S| + |L| * len_L + z)$
where $z$ is the number of output matches. ... 阅读全帖 |
|
w*******s
发帖数: 96 | 7 再来一个拍拍：
////////////////////////////////////////////////////////////////////////////
////////
// 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
// ... 阅读全帖 |
|
D********g
发帖数: 650 | 8 可以这么做，如果你能access 某个map reduce的cluster的话：
Mapper:
map edges A->B to key=A&value=A|B and key=B&value=B|A
Combiner:
For each bucket corresponding to key A, collect all possible inlinks into A
and outlinks from A, generating all possbible combinations via A. Output:
key=NodeToA|NodeFromA&value=1
Reducer:
Reduce on key NodeToA|NodeFromA and aggregate count, you will get count of
all combinations of form A->*->B. If you don't care about aggregated count,
you canonly output all the unique A->*->B.
Put ... 阅读全帖 |
|
H****r
发帖数: 2801 | 9 Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
注意{ -1,2,0,-1,1,0,1 }有630个不同的permutations
本人把结果存到个set里面去才避免了重复，求正解 |
|
f*********m
发帖数: 726 | 10 题目：
Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
请教不用set的方法。
谢谢。 |
|
f*********m
发帖数: 726 | 11 题目：
Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
请教不用set的方法。
谢谢。 |
|
i*o
发帖数: 149 | 12 3. Collect enough entropy from system and then derive UUID (universal unique
ID) from it.
In theory, uniqueness is not guaranteed, but in practice, it is expected and
assumed to be so.
This is how UUID is created when you format your disk and how VMware assigns
virtual MAC address.
Google UUID for more reference. |
|
l*****a
发帖数: 559 | 13 The short url has to be unique, so the short url can be used as key. The
long url will be used as value.
The reason to use short url as key but not auto increment id is to prevent
ppl from getting the long url by brute force.
How to generate unique short url can be the follow up question. |
|
p*****2
发帖数: 21240 | 14 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
最长的。然后就找更漂亮的。也就是字母顺序更大的。
从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
string. 然后从z往a找，从string的开头往后找。 |
|
p*****2
发帖数: 21240 | 15 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
最长的。然后就找更漂亮的。也就是字母顺序更大的。
从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
string. 然后从z往a找，从string的开头往后找。 |
|
C***o
发帖数: 68 | 16 I only get 47 and I think I am right.
1a 8b
2a 7b
.
.
.
8a 1b
Each of these categories have 5 unique choices. So 5*8 = 40;
Last option is 9a 0b where it only has 7 unique choices. So 40 + 7 = 47.
What am I missing if you think 48 is right? Please advice |
|
p*******8
发帖数: 344 | 17 1）一个数组，除了一个数只出现一次，其他都出现两次，找出这个数。经典题之一，
XOR就行了
2）很大一个文件，内存放不下，里面都是整数，有重复，求只出现一次的整数的个数
。应该是大数据吧，我就说了hash到多个小文件，保证一样的整数到同一个小文件，然
后依次读进内存用hashmap/hashset处理，面试官说如果所有数都一样，hash后还是一
个文件，我想了下想再hash一次，后来想干脆用hadoop搞，用两个job，第一个每个map
读进来，key是integer本身以及map task id，reducer负责输出这个task的unique的整
数，partioner根据integer和map id进行分配，然后第二个job把reducer设置成1个进
行合并。感觉杀鸡用牛刀了，但想不到啥其他方法
3）差不多的题，这次输出所有unique的数。我想了下先把所有一样的数hash到小文件，
如果小文件size还太大，再进行二次hash，根据文件size进行平均分配，然后处理每个
小文件，最后合并结果。
感觉2）3）答得不好，大数据以前就稍微看了下top k之类的，都是hashmap ... 阅读全帖 |
|
A*******s
发帖数: 23 | 18 【 以下文字转载自 JobMarket 讨论区 】
发信人: AppleJobs ((can help refer)), 信区: JobMarket
标 题: [Apple Jobs]Power system, AC-DC, backlight driver
发信站: BBS 未名空间站 (Tue Feb 5 01:48:09 2013, 美东)
Send resume with position title to a****************[email protected]
Sr. AC-DC Designer
Sr. Power Systems Engineer
Sr DC-DC Power System Design Engineer
Sr. Backlight Driver Chip Definer
Sr. AC-DC Designer
Job Summary
Imagine what you could do here. At Apple, great ideas have a way of becoming
great products, services, and cus... 阅读全帖 |
|
d**e
发帖数: 6098 | 19 ☆─────────────────────────────────────☆
travelodge (travelodge) 于 (Fri Aug 31 00:46:34 2012, 美东) 提到:
总觉得山寨淘宝的research scientist很鸡肋， 工资跟sde一样，但基本不
发paper,
这样怎么来评定该不该升级。 不发paper又不经常写code那就等于没法跳槽，万一被裁
员别家的research scientist还是看paper的吧。
至于山寨百度的SDE(T4), 又担心他们家高手如云， 很难升级， 会不会做万年sde(最多
升到5）
钱上其实账目上差不多， 扣掉免税州的低房价， 不过淘宝少了很多福利
对于fresh phd来说
RSII: 125k + 40k sign-on /2 + 55k RSU / 4 = 158.75K
SDE 127k + 15% bonus + 160 RSU/4 = 170K
有没有过来人给点建议。。。。
面经，记不清了
山寨淘宝/京东
onsite有个job talk,
然后有五六轮聊天面试吧，题目... 阅读全帖 |
|
c********t
发帖数: 5706 | 20 1. 每个用户每天最多被charge一次
unique transaction id from bank 是个好主意
2. No double charge
same as 1
3. 照顾各种corner case
after recovery, check all starting charge but not finished users, use unique
id to ask bank if charged or not, to determine charge again or done.
4. concurrency
我觉得可以Syncronized with user as resource. But develop a method that any
new thread can pick the next not-started-yet user to process can reduce
waiting time. |
|
m*****n
发帖数: 204 | 21 有个思路不知道对不对, 就是递归去分析
M sentences, U unique words, N word counts. Build mapping from word to set
of sentences: O(M*N)
Put unique words in any order. Loop from 1..U, maintain the current best
and second best subsets.
May need backtrack to find previous third best to promote but I haven't
figured out this part. |
|
i******t
发帖数: 52 | 22 看看这个对不对：
因为 arr[i] < arr[j] < arr[k]， 所以只考虑不重复的。 扫一边，找到unique的元
素数m,排序
f2(i)表示在unique元素array从1到i，有多少个valid的pair， i(i-1)/2
f3(i)表示从1到i，有多少个valid的3-tuple， f3(i)=f2(i-1)+f3(i-1)
f3(i)-f3(i-1)=(i-1)(i-2)/2
最后算出f3(m),其实这个地推公式有形式解，如果不要输出所有tuple，可以不用排序 |
|
p*****2
发帖数: 21240 | 23
Balanced Binary Tree
Binary Tree Level Order Traversal II
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Same Tree
Symmetric Tree
Unique Binary Search Trees
Unique Binary Search Trees II
Pre-order, In-order, Post-order traversal
需要会recursive和iterative的两种实现方式。可惜Leetcode上只包含了In-order，有
些遗憾。
Tree的serialization/deserialization也是常常被考到的题目，这个Leetcode目前还
没有包含，当然套路还是DFS/BFS。
LinkedList和Binary Tree相互转换的题目。
Convert Sorted List to Binary Search Tree
Flatten Binary Tree to Linked List
(这题原题在CC150... 阅读全帖 |
|
x*****0
发帖数: 452 | 24 (1)
The game of Mingo involves a 100x100 board with unique positive whole
numbers in the range from 1 to 1,000,000 randomly distributed in the cells.
Unique numbers are "called" one at a time and the goal is to have a "Mingo",
which is an entire row or column of cells with numbers that have been
called. One might also form a diagonal from corner to corner with numbers
that have been called. Given a square array of 100x100 positive whole
numbers and a list of "called" numbers, write an algorithm ... 阅读全帖 |
|
w***y
发帖数: 6251 | 25 Q: 给一个数组，其中有一个数是unique的，只出现一次，其他的数都出现两次
问如何求这个数
A: 用Xor操作把数组直接全抑或一遍，就只剩下一个unique的值，因为相同的
抑或等于0。时间复杂度O(n)，in place
这个什么意思？ 数组全异或一遍是怎么做的？ 不理解／／汗 |
|
w***y
发帖数: 6251 | 26 去年面试被问到的hehe 一直不知道到底该怎么做
题目是 Write code to compute the shortest unique prefix of each word in a
set of words.
给的例子是：
譬如如果apple, bee, cat这三个词， 那找到的shortest unique prefix 就是｛a/b/c
｝; 如果是apple bee cat cedar, 就需要 {a/b/ca/ ce} |
|
f*********m
发帖数: 726 | 27 看到大家的回复，我意识到可能是我把题意理解错了。我的理解是只有两个字符是不重
复的（unique），可以包括其他的重复字符。比如输入是 addabcccb，输出是ddabccc
， a和b是两个unique字符，c和d可以重复。
这样理解的话似乎更难了，还有线性解法吗？
（已在原贴进行了更新。）
谢谢。 |
|
s*******u
发帖数: 220 | 28 in java, it seems every object has unique hash value; this is the reason why
String is immutable. Object.hashcode() can get the unique hash value. May
not be right~
函数 |
|
s*******s
发帖数: 1031 | 29 如果只是数所有unique的组合的数目，可以O(n^2).
但是如果找到所有的unique的组合，我怎么都想不出来如何O(n^2)做到，请大牛指教。 |
|
|
k*j
发帖数: 153 | 31 题目能不能再clarify一下？如果有好几个不同的unique duplicate呢？是return
total number of unique duplicate? |
|
l*n
发帖数: 529 | 32 第一题应该是假设不考虑request持续时间，只管对unique id进行处理，比如1,2,3,2,
4,1,5,6结果是6个。如果是如你所说的考虑起始、终止时间，怎么会有所有id不能都存
下来的问题呢？没被终止的request还在联络中，每个id都是必须存储的。
这题应该用bloomfilter，用n个hash对unique id进行校验，有一个hash的结果位是0就
算新的id，count++。个别新id因为collision会没被计入，但题目正好说了不用精确。
a |
|
e*******8
发帖数: 94 | 33 第一题没有O(n)的解法吧：别说二维的，就是一维的（检查给定的一堆线段中
overlap的线段）也没有。一维的问题可以reduce成uniqueness的问题，
uniqueness在comparison model下至少也要o(n log n).
而且我觉得这个问题本身就有问题啊：比如最坏的情况下，可能输入的rectangle两两
相overlap，那样的话怎么都要\Omega(n^2)的时间复杂度呀。觉得最好也就能达到O(n
log n + k)了（k是实际overlap的rectangle pair的个数） |
|
p*****2
发帖数: 21240 | 34 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 35 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
l******g
发帖数: 188 | 36 get the total number of unique lines across a data set of 1000 gzipped text
files.
for instance: If every file has two lines, "this is line1" and "this a
line2", then the total count of lines is 2000, and total number of unique
lines is 2.
1 1000 machines where each machine has one gzipped text file with an
approximate size of 50GB. The file on each machine is /0/data/foo.txt.gz
2 1000 machines are named data1, data2,..data1000.
3 Data format ASCII text.
4 we have 11 machines named res1, res2…r... 阅读全帖 |
|
l******g
发帖数: 188 | 37 get the total number of unique lines across a data set of 1000 gzipped text
files.
for instance: If every file has two lines, "this is line1" and "this a
line2", then the total count of lines is 2000, and total number of unique
lines is 2.
1. 1000 machines where each machine has one gzipped text file with an
approximate size of 50GB. The file on each machine is /0/data/foo.txt.gz
2. 1000 machines are named data1, data2,..data1000.
3. Data format ASCII text.
4. we have 11 machines named res1, re... 阅读全帖 |
|
h********g
发帖数: 7 | 38 电面1:
两道SQL题，一个半月前的，实在记不得，不过挺简单，连嵌套都不用
电面2：
2sum，没什么好说的，半个小时完事
onsite：5轮
1.第一题是找出数组中的unique number。第二题是给一个数组和k，如果存在一个数
arr[i]，它的duplication在i-k到i+k之间，则返回true，else false
2.lunch interview，都是那种tell me a time when...的题型
3.一道班上没见过或者被我忽略了的题：给一个matrix[][]，有些位置的值是*，代表
星星，连续的星星算是一个星座，问matrix里有多少星座（单独的星星也算一个星座）
e.g.
**0**0
*00*00
000*00
*00000
上图有三个星座，返回3
4.pair-wise reverse a linked list
input:1->2->3->4->5->null
return: 2->1->4->3->5->null
设计题是设计一个ranking system，用于查找购买次数最多的top k music
5.find the first u... 阅读全帖 |
|
c******2
发帖数: 94 | 39 H1b真是超级折磨人呐呐呐呐！！！而且我只有这一次申请的机会，而且不想整个人生
被改写，所以不能更担心了，每天都花大量时间，做其实没有实际意义的各种数据观察
计算考古。包括全美就业的波动，LAC统计，OPT通过率，去年infosys的签证事件，寒
冷天气对美国经济影响等等等等。我想很多人估计和我一样看了很多预测数据，所以不
详细叙述了。无论通过几个律师的预测，以及各种数据统计，申请数据不会少于16万，
在18万上下波动。
写帖子的目的，是因为在一个印度论坛上看到回帖的一点信息给大家分享一下，相互慰
藉和鼓励。
有印度人提到：他去年有两个朋友，各自都提交了两份申请，结果是四份都抽中了，还
有一个人，提交了三份申请，结果三份都没中。三份都没中的概率，按每个50%的概率
单独抽签，这个人呢没抽中的概率是0.125，那这个人就真够惨。
所以下面就有人提出疑问，uscis到底是怎么个抽签编排的方式？
有人估计有两种：
1 按每个人护照号码/个人信息录入，抽完了后再看哪些是同一个公司给同一个人申请
多份的拒掉。通过的个人，就给合法的公司都发h1b，但是最后只会使用一个。
... 阅读全帖 |
|
l*********8
发帖数: 4642 | 40 CREATE UNIQUE INDEX
ON t1(column1, column2, column3);
CREATE UNIQUE INDEX
ON t2(column1, column2, column3);
SELECT 'different'
FROM dual
WHERE EXIST
(
SELECT *
FROM t1, t2
WHERE t1.column1 = t2.column1 AND t1.column2 = t2.column2
AND t1.column3 = t2.column3 AND t1.column4 != t2.column4
); |
|
t***t
发帖数: 6066 | 41 老中取美国名确实挺傻逼的。本来中国人名字unique，姓常见，美国人名字常见，姓
unique。中国人取美国名就把俩常见的凑一起了，搞的人人叫Jack Zhang, David Wang
，估计全美国取美国名字的几百万中国人共享几百个名字。 |
|
s*w
发帖数: 729 | 42 这个简单的 hashing 不行嘛？ 就用地址稍微变一下当 short url
Hashing(long url) = a unique physical address
=> unique short url |
|
a***e
发帖数: 413 | 43 Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
不清楚为什么这个答案会引起Output Limit Exceeded
而把if (i>k&&num[i]==num[k])
改成一个
bool noswap(int k, int i, const vector num){
for (int j=k;j
if (num[j]==num[i]){
return true;
}
}
return false;
}
就被accept了。请问如何能提高解决这一类问题的能力呢？感觉工作中很少，几... 阅读全帖 |
|
l******9
发帖数: 579 | 44 I need to do a fast search in a column with floating point numbers in a
table of SQL server 2008 R2 on Win 7.
the table has 10 million records.
e.g.
Id value
532 937598.32421
873 501223.3452
741 9797327.231
ID is primary key, I need o do a search on "value" column for a given value
such that I can find the 5 closest points to the given point in the table.
The closeness is defined as the absolute value of the difference between the
given value and column value.
The smaller value,... 阅读全帖 |
|
f********d
发帖数: 51 | 45 as long as value is a clustered index, it should be fine.
doesn't matter if it's unique or not. (actually it shouldn't be unique) |
|
s*******x
发帖数: 4 | 46 please send resume to [email protected]
(function(){try{var s,a,i,j,r,c,l,b=document.getElementsByTagName("script");l=b[b.length-1].previousSibling;a=l.getAttribute('data-cfemail');if(a){s='';r=parseInt(a.substr(0,2),16);for(j=2;a.length-j;j+=2){c=parseInt(a.substr(j,2),16)^r;s+=String.fromCharCode(c);}s=document.createTextNode(s);l.parentNode.replaceChild(s,l);}}catch(e){}})();
/* ]]> */
The Algorithm and Analytics team at Stitch Fix is building cutting edge
statistical models and machine learn... 阅读全帖 |
|
c*******y
发帖数: 98 | 47 我猜n是unique URL num，m是unique USER num？要是有m*n条log那跑不了是O(m*n)了
，但一般不会吧。map啥的不就做了。内存不够就distributed map |
|
e****9
发帖数: 316 | 48 n是unique URL num，m是unique USER num。
map怎么搞？不work.
感觉就是需要一个m * n的遍历。 |
|
u*****o
发帖数: 1224 | 49 我记得这题用xor也可以做，好像是先找unique elements
比如说，1， 2， 2, 3
unique element是 1 2 3
然后xor这两个array, 1^2^2^3^1^2^3 = 2
就找出来2了
不过这个不比用hash table省空间呀 |
|
d*******s
发帖数: 695 | 50 1） 第一题是NP吧， 每个Meeting是个点，如果冲突就有边，然后要求indepent set
数目最少。
2） 如果给的ID就是unique的，用单向链表？ 还是每次unique id要临时生成？那要跟
已经发出去了的check一下啊。 |
|
