g*******y
发帖数: 1930 | 1 好久没做题了，为了20个包子，我来试试吧。
从左边开始，看第一个3-tuple,{a0, a1, a2}
maintain the following info:
current best solution length: 0
hash each new number's first occurrence: a0~0, a1~1
case1: current 3-tuple is valid
find a2 in hash table:
if (found) {
current_best = MAX(current_best, |hash[a2] - current index of a2|;
} else {
hash[a2] = current index of a2; // insert a2 into hash table.
}
case2: current 3-tuple is invalid:
possible_best = solution of (a1 ... an);
return MAX(current_best, possible_best); |
|
P*******b
发帖数: 1001 | 2 1. System design: given a key word like "kindle", return a count of how
many occurrences of this word on internet. (like search a key word on
google, return "About xxx results" ) |
|
S*********r
发帖数: 5693 | 3 Lets say you have 1 string of length N and M small strings of length L. How
do you efficiently find the occurrence of each small string in the big
string ? |
|
l********r
发帖数: 187 | 4 Hi,
I got an programming problem from Microsoft for screening purpose. Does
anyone has good idea about it? I am particularly puzzled by the second given
example. Thanks.
“bool F(string s, char ch1, char ch2, int n)”
The function determines whether or not there exists an occurrence of ch1 and
ch2 separated by a distance of no more than n in the given string s, where
s is ascii and user entered (your function needs to work on any input.) The
function must be efficient and **optimized** for both sp... 阅读全帖 |
|
l********r
发帖数: 187 | 5 Hi,
I got an programming problem from Microsoft for screening purpose. Does
anyone has good idea about it? I am particularly puzzled by the second given
example. Thanks.
“bool F(string s, char ch1, char ch2, int n)”
The function determines whether or not there exists an occurrence of ch1 and
ch2 separated by a distance of no more than n in the given string s, where
s is ascii and user entered (your function needs to work on any input.) The
function must be efficient and **optimized** for both sp... 阅读全帖 |
|
f*****e
发帖数: 57 | 6 Say you have a file containing name value pair, such as
foo: bar
a: b
foo: bar
a: c
The file may be huge, but the number of names are limited.
Given a name, find out how many times the name occurs in the file.
It looks to me there is a straight forward solution using hash table:
we preprocess the file, hash each name into the table, and keep the
count. We then use the same table to look up the name occurrence.
This should be programmed in C, so not stl. |
|
s*******f
发帖数: 1114 | 7 using System;
using System.Collections.Generic;
using System.Text;
namespace MSC
{
class Program
{
//“bool F(string s, char ch1, char
ch2, int n)”
//The function determines whether
or not there exists an occurrence of
//ch1 and ch2 separated by a
distance of no more than n in the given
//string s, where s is ascii and
user entered (your function needs
//to work on any input.) The
function must be efficient and
//**optimized** for both space... 阅读全帖 |
|
g*********s
发帖数: 1782 | 8
anagrams
why "the", "fell" not in the collection? so single occurrences are
excluded?
of
it |
|
a***y
发帖数: 547 | 9 assume the result after XOR is T,
then let P = -1 XOR T,
find the occurrence of P in original array.
if P occurs odd times, then only one odd,
otherwise, multiple.
Not sure whether this is the answer. |
|
m**q
发帖数: 189 | 10 这个题目是删除所有a，b，c的occurrence么？
还是只删除按顺序出现的abc？
前者的话，两个指针，做in-place deletion就行了，O(n) |
|
g**********y
发帖数: 14569 | 11 觉得不需要找first occurrence, 直接binary search左右边界，code更简单。
public int[] findRange(int[] a, int value) {
int low = findLeft(a, value, 0, a.length);
int high = findRight(a, value, 0, a.length);
return new int[]{low, high};
}
private int findLeft(int[] a, int value, int lower, int upper) {
int mid = (lower + upper) / 2;
if (mid == lower) return a[mid]==value? lower : lower+1;
if (a[mid] >= value) {
return findLeft(a, value, l... 阅读全帖 |
|
g**********y
发帖数: 14569 | 12 觉得不需要找first occurrence, 直接binary search左右边界，code更简单。
public int[] findRange(int[] a, int value) {
int low = findLeft(a, value, 0, a.length);
int high = findRight(a, value, 0, a.length);
return new int[]{low, high};
}
private int findLeft(int[] a, int value, int lower, int upper) {
int mid = (lower + upper) / 2;
if (mid == lower) return a[mid]==value? mid : mid+1;
return a[mid] >= value? findLeft(a, value, lower, mid) : findLeft(a, value... 阅读全帖 |
|
g**f
发帖数: 414 | 13 如果有很多text data，可以看 co－occurrence。
比如两个 word A，B 常常同时出现在相近的位置（small text window size）。
那么 他们有可能是近意词。
为了提高准确率，可以 extract key sentence segments 然后分析
比如原文常常是ruby on rails（ROR） 或 ruby on rails,i.e., ror.
就可以分析 （ 或 i.e.等符号。
btw，inverted lists一般都存位置信息。
But in general synonym detection and word disambiguation is a tricky problem. |
|
y****d
发帖数: 52 | 14 有没有朋友有类似的经历？
我现在学校做postdoc，持有cap-exempt的H1B，有效至今年8月31日。半个月前拿到一个
公司的offer，公司希望我9月1日就开始上班。我第一次申请cap-subject的H1B，
公司律师说2007年有一个什么memo，即使有cap，10月1日之前也能合法工作。
因为我现在的H1B 8月31日到期，律师递交了两份申请：
一份是H1B extension, 将我现在的H1B延长到9月30日；
一份是H1B transfer, 将我的H1B的sponsor转到新的公司，9月1日开始。
各位觉得靠谱吗？ USCIS批准的可能性大吗？
要是USCIS只能准许10月1日开始新的cap-subject H1B的话，那我9月份是不是就
只能回国签证去了？ 多谢！
这是我从网上找的一个类似的case：
Question 7: A Ph.D. student began her first H-1B employment in August 2009,
working as a postdoctoral associate at a university, w... 阅读全帖 |
|
c******r
发帖数: 225 | 15 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 order.
check and print non-duplicate lines. performance time analysis.
sort the n line based on the # of numbers in each line o(nlgn)
only lines that have the same # of numbers will be compared
suppose we have a set of m lines of length k
for each line in line_set:
sort numbers in each line ~ o(klgk)
then build a hashmap as a helper data structure
for al... 阅读全帖 |
|
k****n
发帖数: 369 | 16
actually, we will traverse all the posting list at most once,
so it's O(n)
like this:
record all the occurrence positions in the longer array in the following
posting list
a[0]: 1 5 7 8 13 19
a[1]: 2 9 20
a[2]: 13 15 17
...
keep a cursor in each posting list.
firstly locate the 1st ordered positions
then move the a[0] cursor forward and check if there is need to update.
the number of updates is at most sum of all posting lists lenghts
the number of checks is complicated, but seems also O(n) |
|
k****n
发帖数: 369 | 17 preprocess the array once, append the position of the occurrence for each a[
i] to a list
visit long array once, append at most once, should be O(n) |
|
a**********2
发帖数: 340 | 18 1.一组用户信息，包括first name， last name，phone number等等，设计一个结构存
储这些信息，能够动态添加，并且能根据first name或者last name进行查找。
我就想到用两个multimap存储，不知道有什么好的思路
2.顺便问道老题
In our indexes, we have millions of URLs each of which has a link to some
page contents, that is, URL->contents. Now, suppose a user types a query
with wild cards *, which represent 0 or multiple occurrences of any
characters, how do you build the indexes such that such a type of query can
be executed efficiently by finding all corresponding URLs->contents
ef... 阅读全帖 |
|
d********w
发帖数: 363 | 19 拼写检查做法有个计算编辑距离，http://en.wikipedia.org/wiki/Levenshtein_distance
google人工智能老大曾经写过一个非常简短但很高效的拼写检查器，http://norvig.com/spell-correct.html.
下面这个题目也有些类似
Write a program that reads a large list of English words (e.g. from /usr/
share/dict/words on a unix system) into memory, and then reads words from
stdin, and prints either the best spelling suggestion, or "NO SUGGESTION" if
no suggestion can be found. The program should print ">" as a prompt before
reading each word, and should loop until killed.
Yo... 阅读全帖 |
|
k***t
发帖数: 276 | 20 来自主题: JobHunting版 - 问个算法题 也来凑个热闹。主要是练练trie。
花了些时间才调通:( 谁帮忙给Review一下？谢了。
运行结果：
ad: 5
bc: 3
bb: 2
aaa: 1
aa: 1
源码：
#include
#include
using namespace std;
struct Node {
int cnt;
char c;
struct Node *n[26];
char *p; // to the 1st occurrence in the original input string
};
#define idx(x) (x-'a')
void add2trie (Node *r, char *p1, char *p2) {
char *p; Node *cur=r; Node *n;
p=p1;
cur=r;
while (p!=p2 && cur->n[idx(*p)]) {cur=cur->n[idx(*p)]; ++p;}
if (p==p2) { cur->cnt++;... 阅读全帖 |
|
S**I
发帖数: 15689 | 21 ☆─────────────────────────────────────☆
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... 阅读全帖 |
|
i*******e
发帖数: 240 | 22
Foreach line in document
Traverse trie following this line
If this line is closing to the end and isKey == true in the trie
then ignore this line because it must have occurred before
else if this line is closing to the end and isKey == false in the trie
then isKey = true and keep this line in the output (this is the
firs time occurrence)
顺序遍历每一行，当读到第i行结尾处，发现trie中的isKey为true （初始值都是false
）则说明之前有过相同的行出现过，就应该ignore他。如果没有出现过，把isKey设置
为true，保留该行。继续读取下一行直至所有 |
|
y*******o
发帖数: 6632 | 23 hashmap
所有四位数0000 to 9999做hash key，value是出现次数
然后遍历， if（occurrence）
++value
if（value>1)
break;
return key; |
|
k*****y
发帖数: 744 | 24 Python写了一个，练练手
L = ['fooo', 'barr', 'wing', 'ding', 'wing']
S = 'lingmindraboofooowingdingbarrwingmonkeypoundcake'
# L1 stores distinct stings in L
# multiples counts the corresponding multiples
L1 = []
multiples = []
for str in L:
if str not in L1:
L1.append(str)
multiples.append(L.count(str))
# k is the lenght of each substring
k = len(L[0])
match = [0]*len(S)
checklist = []
for i in range(0, len(L1)):
mul = multiples[i]
list_pos = []
# find all possible positio... 阅读全帖 |
|
k*****y
发帖数: 744 | 25 Python写了一个，练练手
L = ['fooo', 'barr', 'wing', 'ding', 'wing']
S = 'lingmindraboofooowingdingbarrwingmonkeypoundcake'
# L1 stores distinct stings in L
# multiples counts the corresponding multiples
L1 = []
multiples = []
for str in L:
if str not in L1:
L1.append(str)
multiples.append(L.count(str))
# k is the lenght of each substring
k = len(L[0])
match = [0]*len(S)
checklist = []
for i in range(0, len(L1)):
mul = multiples[i]
list_pos = []
# find all possible positio... 阅读全帖 |
|
S******t
发帖数: 151 | 26 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. ... 阅读全帖 |
|
p*****2
发帖数: 21240 | 27 前两天有人问DP和Greedy的区别，今天做了一道题不错。我先用DP解，当时感觉有点别
扭，因为觉得好像有条件没有用上，结果超时。后来才意识到这题是Greedy. 想感觉一
下DP和Greedy的可以练练。
Sergey attends lessons of the N-ish language. Each lesson he receives a
hometask. This time the task is to translate some sentence to the N-ish
language. Sentences of the N-ish language can be represented as strings
consisting of lowercase Latin letters without spaces or punctuation marks.
Sergey totally forgot about the task until half an hour before the next
lesson and hastily scribbled some... 阅读全帖 |
|
s**********n
发帖数: 1019 | 28 做人要诚实啊...
A potential U.S. Customs and Border Patrol employee was arrested after he
revealed to Yuma agents during a job interview that he previously molested
children and animals, according to agency officials.
On July 2, Cody Slaughter, 22, of Somerton, told Border Patrol officials
about incidents in his past including the molestation of a young child and
having sexual interaction with multiple animals, according to Major Leon
Wilmot, a spokesman for the Yuma County Sheriff's Office.
Slaughter... 阅读全帖 |
|
i**********e
发帖数: 1145 | 29 string ( const char * s );
Content is initialized to a copy of the string formed by the null-
terminated character sequence (C string) pointed by s. The length of the
character sequence is determined by the first occurrence of a null character
(as determined by traits.length(s)). This version can be used to initialize
a string object using a string literal constant.
http://www.cplusplus.com/reference/string/string/string/ |
|
t*********h
发帖数: 941 | 30 for first Q:
for each char:
find all its occurrence.
expand it to its righthand side and and if <=1 instance left, stop
result: return the longest which appears more than once? |
|
z****p
发帖数: 18 | 31
I guess you are right.
However, then the answer should be C(L) = 1.1111... (with L occurrences of 1
's after the decimal point).
Of course, the final answer to the complexity problem is O(1). |
|
h******3
发帖数: 351 | 32 a startup company. requires using java.
1. input is a file log.data
I am good
I am better
I am excellent
output:
I 3
am 3
good 1
better 1
excellent 1
My idea:
read the file line by line
for each word within that line
cal a hash value of that word
persist the hash value and {word,ocurrences} into hashMap
Iterate the hashMap, output each word and its occurrences.
Cant finish a clean code.
Coding, Coding, Coding is the king
2. using a shell script to count all the lines of all log files under .... 阅读全帖 |
|
y******u
发帖数: 804 | 33 最近在上coursera的课。看到一个mapreduce的伪实现，参考一下。
in python
MapReduce.py
import json
class MapReduce:
def __init__(self):
self.intermediate = {}
self.result = []
def emit_intermediate(self, key, value):
self.intermediate.setdefault(key, [])
self.intermediate[key].append(value)
def emit(self, value):
self.result.append(value)
def execute(self, data, mapper, reducer):
for line in data:
record = json.loads(line)
mapper(rec... 阅读全帖 |
|
y******u
发帖数: 804 | 34 如果想连连mapreduce算法，下面python script能模拟
MapReduce.py
import json
class MapReduce:
def __init__(self):
self.intermediate = {}
self.result = []
def emit_intermediate(self, key, value):
self.intermediate.setdefault(key, [])
self.intermediate[key].append(value)
def emit(self, value):
self.result.append(value)
def execute(self, data, mapper, reducer):
for line in data:
record = json.loads(line)
mapper(record)
... 阅读全帖 |
|
e*****n
发帖数: 316 | 35 关于string的，是否用DP，请指教
Consider an arbitrary string made up of N digits 0-9, e.g., S="01703406777".
What's an efficient algorithm to figure out if there exists any digit D in
the string that has 3 occurrences with equal gaps in the string, i.e., in
the example string S, D=0 occurs at 1st (from left), 4th and 7th positions
in the string. Also, 7 occurs (with 0 gap) in the last 3 positions. You only
need to find one set of 3 positions for the digit in the string. |
|
p*****2
发帖数: 21240 | 36 很多人都说把这150题做了一遍或几遍，但是我感觉算法题才是重点，其他的很多题面
试基本碰不上，没看出来有必要全做。这里总结一下自己认为重要的题。
第一章 ：
全部重要 (1.6, 1.7 Leetcode上有）。
1.5 面A碰到 (string compression)
1.7面Z碰到 (set 0)
1.8面Bigfish碰到 (string rotation)
第二章 (2.4, 2.5 Leetcode上有）：
全部重要。
2.2面Bigfish碰到 (find kth)
第三章 ：
感觉就是3.2 (min stack), 3.5 (two stack queue) 重要。两道题面M被问到过。3.6
(sort stack)感觉也有可能被考到。
第四章 （4.1， 4.3， 4.5 Leetcode上有）：
感觉4.2, 4.3, 4.5，4.6， 4.7 重要。4.5 (valid BST)面E，Q碰到过
第五章：5.4 (n & (n-1))
第六章：6.5 (drop egg)
第七章：7.3 (line intersection)，7.6 (line passes m... 阅读全帖 |
|
f*********d
发帖数: 140 | 37 first, arra[0] is the last occurrence of 9, then you will get last 9, which
maybe not even valid result for the final solution
second, how to update array, any suggestion or hint? Thanks!
Overall, thanks for your help and idea!
minimum |
|
c**1
发帖数: 71 | 38 of course I mean last occurrence so far. |
|
l******9
发帖数: 26 | 39 my own o(m*n) solution
* it only can handle unique number in b[]
public static int f(int[] a, int[] b)
{
int n = a.length;
int m = b.length;
int min = Integer.MAX_VALUE;
int minEnd = -1;
int[] pos = new int[m]; // the last occurrence of b[i] in a[]
int[] len = new int[m]; // the length of the last sequence ending at b[i
]
Arrays.fill(pos, -1);
Arrays.fill(len, 0);
for (int j = 0; j < n; ++j) {
// search a[j] in b[]
int i;
for (i = 0; i < ... 阅读全帖 |
|
W***o
发帖数: 6519 | 40 我在分析一个犯罪数据，从2001年到2013年的，有大概6GB， CSV格式。里面大概有20
个columns,但是我只对其中几栏需要分析。比如我想分析每种犯罪在每年的数量，所以
我想能否用这样一个key: ， 也就是犯罪类型和年份这个pair作为key,
然后这个key所对应的value就是sum of the occurrences of theft in 2005.
请教一下大侠这种是否可行？有没有更好的方法？谢谢，10个包子感谢 |
|
p****o
发帖数: 46 | 41 不是很清楚, 这９５％指的是url长度排序的95%, 还是出现的所有url的95%?
比方说
url length: occurrence
1: 1
2: 1
3: 1
...
94: 1
95: 2
...
99: 0
100:1
如果按url"长度"排序的95%: (1+2+..94+95+95)/96
而如果按"所有"url排序的95%: (1+2+..94+95)/95
指的是哪一种?
5% |
|
s********u
发帖数: 1109 | 42 各种不顺，早上apple来了拒信，下午google面的也不好，阿森纳还输球。。
可能还是沟通能力太差了，应该是很简单的题目，就是不知道他想说什么。
我发觉面试相比leetcode一大难度就是有时候面试官会说的比较vague，要靠自己问。
。要是他每次都直接把题目书写出来，倒是方便多了。。
就是实现一个strchr，只不过第二个参数不是字符，而是字符串，返回第一次出现的指
针。
/*
Find the first occurrence in str of _any_ character in set. Both are NULL
terminated ASCII C-strings. This is like strchr, except that the second
parameter functions as a set, rather than a single character.
str set returns
qxcdef csz str + 2 == &str[2]
axcdef wya str + 0 == &str[0]
axcdef cxa... 阅读全帖 |
|
s********u
发帖数: 1109 | 43 各种不顺，早上apple来了拒信，下午google面的也不好，阿森纳还输球。。
可能还是沟通能力太差了，应该是很简单的题目，就是不知道他想说什么。
我发觉面试相比leetcode一大难度就是有时候面试官会说的比较vague，要靠自己问。
。要是他每次都直接把题目书写出来，倒是方便多了。。
就是实现一个strchr，只不过第二个参数不是字符，而是字符串，返回第一次出现的指
针。
/*
Find the first occurrence in str of _any_ character in set. Both are NULL
terminated ASCII C-strings. This is like strchr, except that the second
parameter functions as a set, rather than a single character.
str set returns
qxcdef csz str + 2 == &str[2]
axcdef wya str + 0 == &str[0]
axcdef cxa... 阅读全帖 |
|
s**********k
发帖数: 88 | 44 show and resolve conflict among multiples users' calendar
scheduling periodic event
alarm before event occurrence |
|
g*********5
发帖数: 1145 | 45 面的sdet
第一次，online写code，给一段string，和pattern string，找出pattern的
occurrence，然后写各种test case
（PS：真心感觉amazon爱问string，估计kindle的原因）
第二次，cloud drive组的manager，问了些background的东西，然后问题（大意）You
are presented a photo app and there is an album icon. Tapping the album
allows you to see the photos of that album. How do you test this?
这东西要怎么回答才能满意？貌似要不停追问interviewer以发掘出更多问题？ |
|
R******9
发帖数: 267 | 46 1. Given an increasing int array, find the smallest integer that is greater
than a given number.
我用的是C数组，interviewer又问如果输入的数组指针是空的，code会在哪行 core
dump
2. Given a log with entries starting with timestamp
2014－05－19 ...
2014－05－21 .....
# Get the number of occurrences of unique log entry for 2014-05-21.
# Find any log entries that have the letter A or B
3. class A;
class B;
class C {
A* a_;
B* b_;
...
};
implement constructor, copy constructor, = and destructor of C.
写 assignment oper... 阅读全帖 |
|
p********n
发帖数: 165 | 47 Space O(1)
Time O(n)
// Given a string, return the longest substring that contains at most // two
characters.
// solution: scan the string and update the first and second letter's last
occurrence
// indices, and update the solution's start index.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}
int solu_start = 0;
int first_end, second_end;
char first = input[0];
char second;
int curr = 1;
while (curr < input.size() && in... 阅读全帖 |
|
p********n
发帖数: 165 | 48 Space O(1)
Time O(n)
// Given a string, return the longest substring that contains at most // two
characters.
// solution: scan the string and update the first and second letter's last
occurrence
// indices, and update the solution's start index.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}
int solu_start = 0;
int first_end, second_end;
char first = input[0];
char second;
int curr = 1;
while (curr < input.size() && in... 阅读全帖 |
|
m********t
发帖数: 13072 | 49 一般都是网上说我弱智，
生活中，夸我IQ，回避EQ的，数不胜数。。。基本上每次认识一个新人，对我背景根本
没有了解，就开始了，
我耳根子都听出浆子了
每次发生点occurrence，保证就有人跳出来，主动说，月光真是有先见之明，不愧高智
商，非常英明，早点听你的就好了 |
|
l********g
发帖数: 372 | 50 报点最近的面经，都是电面中的，攒点rp顺便求bless!
L家的：
1. Given two (dictionary) words as Strings, determine if they are isomorphic
. Two words are called isomorphic if the letters in one word can be remapped
to get the second word. Remapping a letter means replacing all occurrences
of it with another letter while the ordering of the letters remains
unchanged. No two letters may map to the same letter, but a letter may map
to itself.
Example:
Given "foo", "app"; returns true
we can map 'f' -> 'a' and 'o' -> 'p'
G... 阅读全帖 |
|
