e***s
发帖数: 799 | 1 求 Leetcode Online Judge Sort Color one pass constant space 解法。
Copy 下题目：
Given an array with n objects colored red, white or blue, sort them so that
objects of the same color are adjacent, with the colors in the order red,
white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white
, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using coun... 阅读全帖 |
|
e******x
发帖数: 184 | 2 不知道有没有人做过这道题，题目如下
There is an infinite integer grid at which N people have their houses on.
They decide to unite at a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of
all the persons.
O(n^2)的解法只能过4个case，不知道怎么优化成O(n)...
我知道Manhattan distance可以转化成|x1-x2|+|y1-y2|的形式，这样如果所求点不需
要在这N点中间选就简单... 阅读全帖 |
|
M******k
发帖数: 51 | 3 it is BST; and 8 and 8 are still adjacent in in-order traversal |
|
r********y
发帖数: 338 | 4 大家好，我有一个coding的面试题， 求大家提供思路：
大意是: 有两种长短不一样的砖， 垒砌一面任意长宽的墙， 要求是上下两层不能有砖
缝相连，问有多少种砌法？ 详细英文叙述见下。 我能用递归算出一层的所有可能的排
列数， 但是怎么有效的排除砖缝相连的情况呢？本人非计算机专业，求帮助！多谢
Your niece was given a set of blocks for her birthday, and she has decided
to build a panel using
3”×1” and 4.5”×1" blocks. For structural integrity, the spaces between
the blocks must not line up
in adjacent rows.
There are 2 ways in which to build a 7.5”×1” panel, 2 ways to build a 7.5
”×2” panel, 4 ways to
build a 12”×3” panel, and 7958 ways to bu... 阅读全帖 |
|
v****c
发帖数: 29 | 5 来自主题: JobHunting版 - G家面试题 矩阵看成是一个bipartite graph的adjacency matrix.
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解 |
|
v****c
发帖数: 29 | 6 来自主题: JobHunting版 - G家面试题 矩阵看成是一个bipartite graph的adjacency matrix.
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解 |
|
s*****1
发帖数: 134 | 7 这题BFS行不行？
3124 有3个adjacent node
1243,3241,3142,
然后再BFS下去，
当然最好还有个hash table,因为可能之前出现过的会再次出现，如果再次出现的话，
Queue就不放进去了 |
|
s*****1
发帖数: 134 | 8 这题BFS行不行？
3124 有3个adjacent node
1243,3241,3142,
然后再BFS下去，
当然最好还有个hash table,因为可能之前出现过的会再次出现，如果再次出现的话，
Queue就不放进去了 |
|
z*********n
发帖数: 1451 | 9 OPT寄出去了菜想起来，中间坐过一次cruise，这次cruise因为到的是adjacent island
,我visa过期都能去，就心理潜意识默认是国内游了。。
现在想问下，这个到底影响date of last entry into u.s.么？
如果算，我现在怎么改I765?我都已经接收到receipt number了。。
补充一下，由于这是automatic visa re-validation,我的护照海关没动，没有改I 94
，没有章，没有任何新记录或改动，这个到底影不影响date of last entry into u.s.
啊？ |
|
o***d
发帖数: 313 | 10 怎么用adjacent list觉得这么麻烦,每个node前后的edges都要管理 |
|
j*****y
发帖数: 1071 | 11 比如
A 有 friend B , C
B 有 friend A, D
C 有 friend A E
D 有 friend B.
E 有 freind C
friend 是相互的， A 是 B的friend那么B 一定也是 A的 friend
首先每个 用户有一个 唯一的 ID
给每个用户创建一个 friend list,friend list 里面存储的就是 ID, 就变成了 graph
的 adjacency-list 的表示， 每个 list可以通过 用户 id排序，那么找两个人的共同
朋友的话，线性搜索就可衣做到。 不知道有没有更好的方法存储。
linkedin 里面的 1st connection 容易实现， 它的 2nd connection, 3rd
connection,
这个是怎么做到的呢。
比如 A 加了 B, 那么 B 的 friend list 里面所有不是 A的friend的话， 就加到 A 的
2nd connection list里面， 但是感觉这么做会有冲突，比如一个人这么看是 A 的
2nd
connection, 那么看会是 A 的 3rd c... 阅读全帖 |
|
e****e
发帖数: 418 | 12 1. 150 is BST. This solution is very similar to 150.
2. Why recursion? Why not a for loop through every two adjacent letters in
the 字符串? I think "打印一个从 i,j走到 m,n的method" is a good method. |
|
w****a
发帖数: 710 | 13 Sort Colors:
Given an array with n objects colored red, white or blue, sort them so that
objects of the same color are adjacent, with the colors in the order red,
white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white
, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
翻转链表就是reverse linked list没错。 |
|
|
s*w
发帖数: 729 | 15 严重赞成 BFS 不需要完整的 graph construction
我刚写 BFS 的时候也是先上个完整的 adjacency list, 后来发现很多时候都是 用到
adj[i] 的时候再现找；大部分情况下 BFS 还没 traverse 完就找到退出了，会快很多 |
|
l*n
发帖数: 529 | 16 a quick thought: locate ridges, which divide the matrix into wells, then
recurssively merge adjacent wells. |
|
l*n
发帖数: 529 | 17 a quick thought: locate ridges, which divide the matrix into wells, then
recurssively merge adjacent wells. |
|
z********i
发帖数: 568 | 18 1。binary tree where every node has a color. Calculate the number of
disjoint three adjacent nodes.
2. timer problem：use semaphore in ISR to wake up a user function call.
三个组面试。最后一个组的manager很热情。这个manager同hr最后问：salary
expectation, preferences on which of those three groups in interview。
Salary expectation: 就说接受standard package，但没有给具体数据。最后hr问了一
下我现在的工资。Manager很想我给一个数据。
Preference on which group:回答都喜欢。
不清楚该怎样回答。 |
|
g*********e
发帖数: 14401 | 19 我建了adjacent word list
然后先bfs算最短距离
再dfs搜索所有最短距离的path 但貌似很费时间啊。放到cfree里面跑了半天还在算 |
|
c***w
发帖数: 134 | 20 这题怎么做啊？？
You are given a n*n matrix of bits (1s and 0s) where 1 represents land and 0
represents water. Adjacent 1s can be considered as joined together to form
sort of island in water. Count the number of islands |
|
c*u
发帖数: 22 | 21 三角数求最大和，如
By starting at the top of the triangle and moving to adjacent numbers on the
row below, the maximum total from top to bottom is 27
5
9 6
4 6 8
0 7 1 5
I.e. 5 + 9 + 6 + 7 = 27.
find the maximum total from top to bottom a text file containing a triangle
with 100 rows. |
|
m***n
发帖数: 9 | 22 Given a triangle, find the minimum path sum from top to bottom. Each step
you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() funct... 阅读全帖 |
|
b***e
发帖数: 1419 | 23 来自主题: JobHunting版 - 问个面试题 Dijkstra求连通算法可解。在adjacent matrix上执行Dijkstra算法，如果某一个cell
的值为1且从未被改变过，那么这个cell所对应的edge是一个canonical edge。 |
|
z*********n
发帖数: 1451 | 24 问这个是因为想确定下自己现在能做邮轮去巴哈马不能。F1可以去adjacent island,
H1B就不行。
但我这个H1B生效后，还没回过国，护照上写的还是F1（过期的），在坐游轮上我适用
F1条款还是H1B条款。
谢谢解答！ |
|
j*********g
发帖数: 36 | 25 This is not gray code. No need to formulate it as TSP. Also, debrujin
graph only gives you a problem formulation.
You can solve by finding an Eulerian tour. Each node is a 3-digit number eg
100, and two nodes 100 and 001 are adjacent if they can be combined into
1001. Now every node has equal in-degree and out-degree, thus an Eulerien
tour exists and can be found using the standard algorithm. |
|
x****1
发帖数: 118 | 26 Linkedin
phone1：烙印
lowest common ancestor w/ and w/o parent pointer
phone2：国人
search in rotated sorted array
onsite:
1.两个国人
implement addInterval(start, end) and getcoverage(),
2.两个国人
talk projects and some behavior question
3.烙印
lunch, talk about technologies interest
4.亚裔，不确定是否国人
Manager, talked a lot of behavior questions, interest and projects
5.烙印
Design: tinyurl
6.烙印+小白
1.exclusive array, give an arr1, return a new arr2, arr2[i] is the
multiplication of all elements in arr1 except arr1[i]
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 27 // How do I convert two anagrams of a word, into a common anagram in minimum
number of moves with only two types of move allowed-1-You can swap 1st and
last character (of any given string) considered as one move. 2-You can swap
any two adjacent character (of any string) considered as one move?
// assume all characters appear only once
unsigned MinSwap(string a, string b) {
if (a.empty()) {
return 0;
}
unordered_map mp;
unsigned i = 0;
for (char c : a) {
mp[c] = ... 阅读全帖 |
|
f**********t
发帖数: 1001 | 28 // How do I convert two anagrams of a word, into a common anagram in minimum
number of moves with only two types of move allowed-1-You can swap 1st and
last character (of any given string) considered as one move. 2-You can swap
any two adjacent character (of any string) considered as one move?
// assume all characters appear only once
unsigned MinSwap(string a, string b) {
if (a.empty()) {
return 0;
}
unordered_map mp;
unsigned i = 0;
for (char c : a) {
mp[c] = ... 阅读全帖 |
|
l********e
发帖数: 415 | 29 【 以下文字转载自 Biology 讨论区 】
发信人: loadingdye (Enter), 信区: Biology
标 题: Staff Scientist Position (Bioinformatics), Gladstone Research Institute, UCSF
发信站: BBS 未名空间站 (Sun Mar 16 17:31:56 2014, 美东)
Screening questions:
1. Do you have experience analyzing proteomics mass spectrometry data?
2. Do you have experience analyzing ChIP-seq and/or RNA-seq data in a
Linux environment?
3. Do you have experience generating and analyzing biological networks?
4. Do you have experience with scripting la... 阅读全帖 |
|
f******h
发帖数: 45 | 30 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
k*******r
发帖数: 355 | 31 以前版里贴过的一题
void minMSwap(int[] num, int m), return the min array after m swaps， each
swap happens only between two adjacent elements([4,2,1,3], 2 return [1,4,2,3
] )
4,2,1,3
4,1,2,3
1,4,2,3
当时贴的解法是找最小的元素，判断swap它需要的最少交换次数n，如果n<=m，swap过
来，m -= n,递归， 如果n>m?那就找次小的，重复上面的步骤
这个应该是O(n^2)时间复杂度，因为n次循环，每次循环里面找到符合交换次数的没有
用过的最小位又是O(n)的时间。
我觉得每次循环里面用heap优化，有希望把总时间降到O(nlogn), 但检查或update
heap中元素是否符合交换次数这一步还是要耗掉O(n), 这样总时间还是O(n^2)
哪位大牛贴个nlogn的完整解法？ |
|
l*********e
发帖数: 28 | 32 给一个用adjacency matrix表示的directed graph，节点的数目为n。
要求找出一个节点，它的incoming edges的数目为n-1，outgoing edges的数目为0。时
间复杂度的要求是O(n).
面完第二个面试官以后，HR过来说其他面试官有emergency meeting，之后3个面试全部
取消了。 |
|
s***f
发帖数: 226 | 33 There are a row of houses, each house can be painted with three colors red,
blue and green. The cost of painting each house with a certain color is
different. You have to paint all the houses such that no two adjacent houses
have the same color. You have to paint the houses with minimum cost. How
would you do it? |
|
r******n
发帖数: 170 | 34 Given a set of Social Network Users, for each two users: A follows B or B
follows A or A and B follow each other
Now sort the Users in the following order:
A->B->C->D
satisfying two requirements:
1. each User only show once in the list
2. A must follow B if A appears before B in the output list: A->B->C->D.
It doesn't matter if they are not adjacent to each other in the list.
我面试时说这样子的path不一定unique吧，面试官说任意一条都行。然后，我也没法简
单证明这样子的path必定存在。 |
|
l*********8
发帖数: 4642 | 35 void removeDup(string & str) {
int tail = -1;
for (int i = 0; i < str.size(); ) {
if (tail < 0 || str[i] != str[tail]) {
str[++tail] = str[i++];
} else {
--tail;
while(str[i] == str[tail + 1])
++i;
}
}
str.resize(tail+1);
} |
|
r****s
发帖数: 1025 | 36 push into stack and popup if next char is the same. |
|
S******2
发帖数: 248 | 37 和rtscts说的一样.
public static String removeDup(String str)
{
if(str == null || str.length() <= 1)
return str;
Stack stack = new Stack();
for(int i = 0; i < str.length(); i++)
{
char ch = str.charAt(i);
if(stack.isEmpty() || ch != stack.peek())
{
stack.push(ch);
}
else if(ch == stack.peek())
{
stack.pop();
}
... 阅读全帖 |
|
a**********0
发帖数: 422 | 38 请这个thread的作者解释一下 输出是什么 baaab |
|
r****s
发帖数: 1025 | 39 稍微改一下，stack也可以做出来。
public static String removeDup(String str)
{
if(str == null || str.length() <= 1)
return str;
Stack stack = new Stack();
Character last = ' ';
for(int i = 0; i < str.length(); i++)
{
char ch = str.charAt(i);
if(ch!=last && (stack.isEmpty() || ch != stack.peek()))
{
stack.push(ch);
... 阅读全帖 |
|
c*******r
发帖数: 610 | 40 不好意思，题目没有解释清楚
以下是一些测试例子：
string str1 = "geeksforgeeg";
gksfor
string str2 = "azxxxzy";
ay （3个x相邻，全删掉，然后删除z）
string str3 = "caaabbbaac";
empty string
string str4 = "gghhg";
g （先删除开始的两个g,然后删除两个h）
string str5 = "aaaacddddcappp";
a
如果是”baaab“ 应该返回空串。 |
|
l*****4
发帖数: 267 | 41 recursive和iterative各写了一下Java版本。提供的所有测试例子都通过了。
public static String remove(String s) {
if (s == null || s.length() <= 1) {
return s;
}
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
int j = i + 1;
while (j < s.length() - 1 && s.charAt(j) == s.charAt(j + 1))
j++;
String left = s.substring(0, i);
String right = s.substring(j + 1);
... 阅读全帖 |
|
e******x
发帖数: 184 | 42 因为之前发过贴，背景就不赘述了，具体说说怎么准备还有面经吧。
骑驴找马，一月底开始刷leetcode，到三月中第一个面试，刷了一遍半吧，明显觉得写
第二遍的时候思路清晰多了，code也比第一遍的简洁。其他的就是每家面试前争对性的
看面经，能看多少是多少，四家只有L面经重复率很高，g家最不能预料题型。后面准备
design的时候都是乱看，一些fb tech talk的视频还有之前有人贴过的fb design的总
结，
但我基础不好，临时抱佛脚感觉也没什么用。面经我就只贴面完有及时记下来的，反正
也给过很多朋友了，就贴上来吧。
已经签了fb，准备八月初start，有同一期的pm我，哈。
脸书:
1. Print all paths of a binary tree
I gave a recursive solution.
Then he wanted to give an iterative way.
2a. Fibonacci (iterative)
2b. Buckets of anagrams
[“cart”,”tarc”, “cat”, “act”, “ract”] -> [[“... 阅读全帖 |
|
y***n
发帖数: 1594 | 43 Given an array A (the array can be treated as a big number) and a number
n, find the biggest number that you can reach to via n swaps. A swap can
only happen in adjacent items. For example, given [1 3 4 2 5 7 9]
n=1, 3 1 4 2 5 7 9
n=2, 1 3 4 -> 1 4 3 -> 4 1 3
我写了一个，http://ideone.com/9c4Xcx 觉得不太好，求指导。。 |
|
x****k
发帖数: 34 | 44 第一题，从s开始，查看n个邻居，再查看n^2个邻居的邻居，第三步，对于n^2的节点，
查看它们的邻居。因为adjacency list是sorted，可以用binary search来检查d在不在
其中。这样整个复杂度是O(n^2 log(n))。
请教，有办法做到O(n^2)么？
第三题看起来容易，先算log(B(i)) = log(A(0)) + log(A(1)) + ...
只用log, +, -, exp，避开了除法。这样对不对？ |
|
w********0
发帖数: 377 | 45 find all different android lock screen combinations with length of 5 in a n*
n array.
The conditions are 1) just like drawing on the n*n array, once you put down
your pencil you cannot poll it up to select next number; 2) all the 5
numbers should be different; 3) the path can overlap when you go to the
other direction; 4) cannot jump over number, the next number is adjacent to
previous number, but may not be the last selected number due to overlapping
path.
求解题思路，谢谢！ |
|
c********e
发帖数: 108 | 46 提供Opentable内推，location是San Francisco Financial District
招Senior Software Engineer，（5-10 years experience，no fresh graduate）
有兴趣的可以回帖或者站内信联系啦！
Senior Software Engineer
Location
San Francisco, CA
Department
Engineering Web
State/Region
California
Category
Technology
Brief Description
Description
What you'll work on
Our roadmap is aggressive and you will play a big role in the future of
OpenTable’s footprint on the internet. You will be part of a small,
talented full stack web team focused on the ... 阅读全帖 |
|
l*********8
发帖数: 4642 | 47 所以"maximum adjacent subsequence length"可能的长度是 0 到4 之间？
是4 |
|
m*****n
发帖数: 9 | 48 所以"maximum adjacent subsequence length"可能的长度是 0 到4 之间？
是的。应该是1到4之间。如果提早得到4的话可以提早结束循环。可能我就是没和他沟
通这个。 |
|
n*****n
发帖数: 5277 | 49 可以用map+set， 每个node作为map的key，每个node的adjacent list 作为map的value
存在set里 |
|
r*****3
发帖数: 27 | 50 贪心应该可以吧
先扫一遍, 一共有多少adjacency = x
尝试翻任意一个i, 看他带来的变化是多少, 可能是负的, 然后保存最大变化y, 比如最
左端如果是 00 就是-1
中间010或者101就是 +2, 001就是 0, 等等
最后结果返回x+y |
|
