c********1
发帖数: 161 | 1 对，不过单从O-notation 上面分析最差的case，O(lg N) * 2 显然优于 O（N），不过
作为面试，我觉得应该都说道，看具体问题。 |
|
i**********e
发帖数: 1145 | 2 My code:
// precondition: B is sorted
// returns the index i of B such that Bi-1 < key <= Bi.
int binarySearch(int B[], int key, int L, int R) {
while (L < R) {
int M = L + (R-L)/2;
if (B[M] >= key)
R = M;
else
L = M+1;
}
assert(L == R);
assert(L >= 1);
assert(B[L-1] < key && key <= B[L]);
return L;
}
// returns the length of the longest increasing subsequence.
// Assumption is that A[i] does not contain INT_MIN or INT_MAX.
// INT_MIN and INT_MAX are simple no... 阅读全帖 |
|
S*********n
发帖数: 92 | 3 1. Recall Big O notation. A function is equal to O(g(n)) if its runtime, f(n) can be
bounded by g(n). That is, g(n) is “at least as bad” as f(n). Consider f(n) =
O(log(n!)). Does f(n) = O(n log(n))? Does f(n) = ω(1)? Ω(1)?
2. What is the difference between a map, a vector, and an array. Name a
situation for which each is uniquely well-suited.
多谢多谢！ |
|
g*****i
发帖数: 2162 | 4 先谢谢了
1. 算POLYNOMIAL，比如5x^4+6x^3-7x^2-8=?
原文说思路是减少乘法变成x^2(x(5x+6)-7)-8, 然后找数据结构存数字和运算符.
我的问题是什么数据结构呢?是否要存prefix notation?
2.给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3
分钟。但第三个烤箱有一个slot出了点问题，每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包，你需要把那半片翻个面，在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱，问烤好21片面包最少需要多少时间？如果是2100片
呢？如果是任意给定的N片，要求O(1)时间内给出最少需要的时间。
我的思路:12分钟正好20片没浪费,1-19事先算好存在array里.对吗?
3. read n lines of random numbers(space as delimiter) from a file, lines
with same numbers are treated as duplicated lines, regardless of the ... 阅读全帖 |
|
l********7
发帖数: 540 | 5 刚收到信说要些关于申请H1B的东西 有一条，不明白他们要什么，之前HR 应该已经把
我的I-20都发给他们了，他们是要1-20 么thanks a lot
"We will also need to see her I-120 AD for the notations on when she
completed her studies and the effective date of the Change of Status" |
|
j*****g
发帖数: 294 | 6
Sure.
二面是3道题目：
1. 什么是 Big O notation. 数组search的running time
2. singleton design pattern. 写一个类，然后是synronization的问题
3. 有2个字符串，比如 head tail. 第一步是用第二个字符串tail的最后一个字母(l)
替换head的最后一个字母得到heal，第二部是用tail的第一个字母替换heal的第一个字
母得到teal，以此类推 最后得到替换head为tail，要求打印所有的中间字母，并且这
些中间字母必须是合法的字母.
不知道我表达的清楚不 lol
哪个大牛回答我的问题啊？ |
|
S******t
发帖数: 151 | 7 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. ... 阅读全帖 |
|
|
h********e
发帖数: 1972 | 9 请不要吧2写到 O notation里面。。这样显得很不专业。。kO(n)基本等于O(n^2)还可能更慢。。k may even be (n^2)/2。。
这样就太慢了。。O(n)的算法很难不会考到的。会做O(nlog n)就可以了。跟k没关系。 |
|
l***i
发帖数: 1309 | 10 It is easier if you use postfix or prefix notation, then you have no ( ) to
deal with, 3 operators and 4 operands, 7! is small
just write eval_postfix() and in the function check whether it is a valid
postfix or not |
|
p*****2
发帖数: 21240 | 11 "Programming Pearls" summarizes many important topics in Computer Science,
usually in a sub-par manner. About 10% of the book is dedicated to "thinking
outside the box," and I'd say these parts really shine. Unfortunately, the
other 90% isn't nearly as good. There are inconsistencies in notation,
improperly explained terminology, and incomplete analyses. For example, his
chapter on structured testing leaves out randomized testing (which I would
argue is just as important), despite the fact that ... 阅读全帖 |
|
t********3
发帖数: 567 | 12 1. 实现pow
2. Reverse Polish notation
{"4", "1", "+", "2", "*"} -> ((4 + 1) * 2) -> 10
{"5", "8", "4", "/", "+"} -> (5 + (8 / 4)) -> 7
两个面试的 ，一个三哥，一个不知道什么国家的，不是美国人。
三哥的口音一如既往的难懂啊 |
|
a********r
发帖数: 218 | 13 那位达人能贴个Reverse Polish notation 的C++程序，我是菜鸟一个，想学习一下 |
|
g*****e
发帖数: 282 | 14 给定时间内只完成对O（MN）的优化，没能想出O（M+N）。感觉这题目挺有意思的现在
继续想，欢迎bs，欢迎版友讨论 =)
A new kind of cannon is being tested. The cannon shoots cannonballs in a
fixed direction. Each cannonball flies horizontally until it hits the ground
, and then it rests there. Cannonballs are shot from different heights, so
they hit the ground at different points.
You are given two zero-indexed arrays, A and B, containing M and N integers
respectively. Array A describes the landscape in the direction along which
the cannon is shooting... 阅读全帖 |
|
b***e
发帖数: 1419 | 15 It's just {r: sqrt(rand()), \theta: rand()*2*PI} in polar notation. |
|
|
x*******6
发帖数: 262 | 17 先把表达式转换成operand和operator的string[],再转换成postfix notation，最后用
一个stack来帮助计算 |
|
x*******6
发帖数: 262 | 18 先把表达式转换成operand和operator的string[],再转换成postfix notation，最后用
一个stack来帮助计算 |
|
s***n
发帖数: 57 | 19 Amazon:
Phone interview:
1. print out node of a graph (graph travesal).
2. OOD: design the online shopping cart; open ended question
3. There is a Web service which access DB server has performance issue; how
to identify the issue.
Onsite:
*. compute cubic root of float X;
*. Two sum.
*. check whether two input trees are mirror to each other.
*. check whether a binary tree is a BST.
*. design OOD for zoo, including cage and animals.
*. Google gmail server location question; why it is still fast ... 阅读全帖 |
|
f*******b
发帖数: 520 | 20 收到学校邮件状态已改,虽然不是APPROVED，但是是抽中了，很开心，
祝福大家都能拿到。
学校ISS原邮件如下：
Hello XX,
Yes the change of status notation has been posted to your SEVIS record.
Please provide me with your mailing address and I will mail the new I-20
Please note this does not mean your H1-B has been approved, it simply means
the application has been accepted by USCIS and is under review.
You should direct all questions about the H1-B application process to the
immigration attorney that has filed the petition. |
|
n****r
发帖数: 120 | 21 Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm notation
CommonAncestor(A, B)
1. A' <- A
2. B' <- B
3. a <- 0
4. b <- 0
5. while(A') do
6. a <- a + 1
7. A' <- A'.parent
8. while(B') do
9. b <- b + 1
10. B' <- B'.parent
11. d <- a - b
12. for i <- 1 to |d|
13. if (a > b) A <- A.parent
14. else B <- B.parnet
15. while ( A.parnet and B.parent and A.parent != B.parent )
16. A <- A.parent
17. B <- B.parent
18. return A.parent
在向上遍历到根的时候，难道不需要判断A所在... 阅读全帖 |
|
r*********n
发帖数: 4553 | 22 来自主题: JobHunting版 - 一道面试题 using peking2's notation
if i == x && j == y
dp[i][j][x][y] = -infinite |
|
r**h
发帖数: 1288 | 23 Yelp这家第一轮HR Screen的时候，HR会问你一些CS方面的基础问题
个人根据自己被问到的经历和玻璃门上的面经总结了一下（实际上没有这么多题不过基
本上都在里面），希望对申请他家的各位有所帮助
1. size of unsigned integer
2. http port no.?
3. ssl full form? (Secure Socket Layer, Encrypt in Transportation layer)
4. use of grep and kill
5. the runtime of adding something to a linked list? O(N)
6. SSL和TLS（Transport Layer Security）的区别：TLS是SSL的升级版（TLS3.0 =
SSL1.0）TLS先handshake再secure
7. hashmaps, DNS(Domain Name System),
8. python native datatypes Boolean, Number, String, Byte, List, ... 阅读全帖 |
|
r**h
发帖数: 1288 | 24 Yelp这家第一轮HR Screen的时候，HR会问你一些CS方面的基础问题
个人根据自己被问到的经历和玻璃门上的面经总结了一下（实际上没有这么多题不过基
本上都在里面），希望对申请他家的各位有所帮助
1. size of unsigned integer
2. http port no.?
3. ssl full form? (Secure Socket Layer, Encrypt in Transportation layer)
4. use of grep and kill
5. the runtime of adding something to a linked list? O(N)
6. SSL和TLS（Transport Layer Security）的区别：TLS是SSL的升级版（TLS3.0 =
SSL1.0）TLS先handshake再secure
7. hashmaps, DNS(Domain Name System),
8. python native datatypes Boolean, Number, String, Byte, List, ... 阅读全帖 |
|
r*********n
发帖数: 4553 | 25
在big O notation里面，logN+logM=log(NM)和log(N+M)没有什么区别吧
另外用binary search的方法做，可以是O(log(N+M))。 |
|
D****6
发帖数: 278 | 26 input: * + 2 3 4
output: 20
今天电面挂这儿了。这题recursion怎么做？ |
|
x********0
发帖数: 94 | 27 当年在电脑上写的面试题啊 好怀念
非recursion:
不停地找‘operation number number’ 的组合
recursion
类似的方法，不过找number的时候tricky一点。建立两个counter，一个数operator的
数量，一个数number的数量。当number的数量=operator+1，就可以切出来成为一个
number |
|
r********7
发帖数: 102 | 28 用stack， 一个stack放数字 一个stack放符号。
如果数字那个stack size 达到2， 怎pop这两个数字 并且pop一个符号 进行运算。 得
到的值再放进数字的stack。
继续读数。
直到读完input 并且符号stack为空， return 数字stack pop的元素 |
|
|
u*****o
发帖数: 1224 | 30 这题recursion比非recursion难写啊。。 |
|
L*******e
发帖数: 114 | 31 Recursive solution: 两头切不行吗？ |
|
c**1
发帖数: 71 | 32 int reverse_polish(const char*& str) {
OpCode op = getOpCode(str);
int x = reverse_polish(str);
int y = reverse_polish(str);
return op.apply(x,y);
} |
|
r********7
发帖数: 102 | 33 始终没想到 recursion， 求大神上code。。。 |
|
s***5
发帖数: 2136 | 34 从末尾开始找第一个operator，找到就把之后的两个数取出做运算，把结果放回原
string，再接着recusion。 |
|
c**1
发帖数: 71 | 35 here is the correct version:
int reverse_polish(const char*& str) {
if (is_number(str)) return parse_nuber(str);
OpCode op = getOpCode(str);
int x = reverse_polish(str);
int y = reverse_polish(str);
return op.apply(x,y);
}
note there is no error check, and note str is passed as reference to const
char*, so that functions can read what it needs as well as forwarding the
pointer. |
|
r********7
发帖数: 102 | 36 有没有java的实现方法啊，不太看得懂这个。。。 |
|
|
L*******e
发帖数: 114 | 38 试着用Java写了一个。还是不够简练。Have to use String array, otherwise cannot
push the result back to the original array.
public static int evaluate(String[] array, int from, int to){
// get first operator, backward
int j = to;
String s = array[j];
while (j >= from && !Operator.isOperator(s.charAt(0))){
s = array[--j];
}
// get operands
Operator op = Operator.getOperator(s.charAt(0));
int opIndex = j;
int a = Integer.valueOf(array[++j]);
int b = Integer.valueOf(ar... 阅读全帖 |
|
l*******e
发帖数: 127 | 39 这周四上午的电面，总的来讲题目不难，只是问一些基本概念。
第一题： 讲一下algorithm complexity，以及如果measure performance, 谈谈BIG O
notation。
第二题： 在一堆unsorted的data里，找某一个元素。告诉我不用想复杂，最简单怎么
做。那当然是scan一遍啦。然后加条件，比方说query很多啦。然后让我自己加条件，
然后讲一下这个条件下怎么优化。最后说如果data很多怎么办，如果数据是经常变得，
比如很多deletion, insertion的时候怎么办。
前两题只是进行交流，并不需要写代码。感觉更多的只是对算法和数据结构最基本的概
念谈一下。
第三题很简单： given a collection of strings, find the second longest.
我就直接写代码了，写完之后。他问我你的代码没问题，但是你考虑了two longest
string with same length情况下你怎么返回？发现这道题他的point就是想看你在写代
码前有没有关注要requirement的。告诉我这个很重要，然后我就... 阅读全帖 |
|
b*****a
发帖数: 70 | 40 I don't think there is any problem since the problem is only looking for "a"
path from source to destination. If you unset the visited notation, the
algorithm will become much slower. Therefore, I think this implementation is
pretty good in my opinion.
P.S. I think you can always ask the authors questions by emailing them. From
their amazon reviews, it seems they are really responsive and knowledgeable
. |
|
w**7
发帖数: 22 | 41 来自主题: JobHunting版 - 上一道小题 This question can be solved by (assume n has even digits for easy notation)
1. divide n in left and right, denoted as LR
2. n's closest palindrome has to be one of:
a. (L+1)(L+1), b. LL, c. (L-1)(L-1)
3. find the smallest of (a, b, c) that' greater than n, denoted as lr.
4. the rest are (l+1)(l+1), (l+2)(l+2),.... (l+m-1)(l+m-1).
when n has odd digits, the solution is the same. |
|
J****3
发帖数: 427 | 42 攒人品
From MITBBS:
1. 给一个二叉树 返回镜像 (Binary Tree Mirror)
2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
4. 给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？我先说
HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。不知道
还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING ALGORITHM
好象不是很合适吧。
5.后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。纠结的地方是a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
6. Implement pow(double a, int b)
7. 接着给Amazon的favori... 阅读全帖 |
|
y*****3
发帖数: 451 | 43 Evaluate Reverse Polish Notation那道题，超级容易的，我在Eclipse上都run通了，
但是leetcode却过不了一个最简单的case。实在是不明觉厉。。。
Submission Result: Runtime Error
Last executed input: ["0","3","/"]
public class Solution {
public int evalRPN(String[] tokens) {
java.util.Stack sTokens = new java.util.Stack();
for(int i = 0; i < tokens.length; i++)
{
if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" &&
tokens[i] != "/")
{
int currIn... 阅读全帖 |
|
c****7
发帖数: 13 | 44 用Stack比较的简单， 如果想用recursion来解的话，该如何实现呢？ |
|
s******e
发帖数: 128 | 45 Given a sequence, 3 + 4 * 5 * 6 + 3 + 7 + ... of single digits, + and *,
Evaluate it.
就是infix polish notation. 我想不出如果用 inorder recursive 或stack 怎么做。 |
|
j****l
发帖数: 85 | 46 之前好像有人整理过了，但是找不到了，我综合了几个地方的整理了一下，贡献给大家
啦。感谢原作者。
Why Yelp?
Why would we hire you?
Ideal job at Yelp?
NETWORK
What is DNS?
protocol used to transfer message in HTTP application? TCP reliable
What is SSL?
Port number for HTTP? 80
What does HTML stand for?
What is the protocol used underneath FTP?
Difference between POST and GET?
UNIX
UNIX command to search for a specific text through files in a directory.
Find number of unique lines in a file.
signal for kill command? 9, SIGKILL
What is the comma... 阅读全帖 |
|
d********i
发帖数: 582 | 47 谢谢分享。。
请问楼主M家的evaluate the value of a math expression with +,-,*,/, (, ) 这题
怎么做？
我知道有一种算法先将数学表达式转化为Reverse Polish Notation，再用stack算结果
，但这样代码貌似很长。。。不知道有没有简单点的。 |
|
U**m
发帖数: 313 | 48 1， 问了Evaluate Reverse Polish Notation的题目，但是并不是仅仅做一个函数算出
答案，而是说你要怎么样设计各个class，以及互相之间怎么联系。
2， 假设有两个Queue，不停的在进出数据。每个有一个getdata()的函数，返回一个数
据包括了时间以及一个字符串。如果从Queue1的数据的时间和Queue2的数据的时间相差
1秒的话，把两个字符串输出。
3， 如果我有一个网站，卖东西的，跟Amazon差不多这种，然后用户再抱怨我的网站非
常慢，然后聘了你当技术总工，你要怎么样改进？
4， 给一个日期，用字符串表示，比如20140608，求这个日期所在的星期的最后一天。
先说了说算法，然后再到机器上实际把这个已经有的程序debug出来。
求教应该什么方向去学习。尤其对于第3题，应该怎么解答。 |
|
M*******a
发帖数: 1633 | 49 A service system has n DIFFERENT servers; each one provides one unique
service to the clients. Clients submit requests to the service system, each
request may have multiple sub-requests; each sub-request is to a DIFFERENT
server. A request can have at most n sub-requests. Each sub-request takes 1
time unit to finish at any server. The finish time of a request is the
finish time of its LAST finished sub-request. The notation "total request
finish time" is the sum of all requests' finish time.
1. ... 阅读全帖 |
|
M*******a
发帖数: 1633 | 50 The notation "total request finish time" is the sum of all requests' finish
time.
Not
Earliest time that all request can be finished.
request |
|
