由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - Facebook Phone Interview
相关主题
● 大家帮忙看看这个4sum怎么就不对● 小弟求问LinkedIn那道Deep Iterator的题
● combinations 有没有 iterative的方法阿 ?● 发个g的电面
● Max Points on a Line 用c++map老是没法compile● 灭三哥也不容易
● 求点评：电话面试（今天第二天没有消息回复，感觉可能挂了）● 问个算法题
● 弱问一道G题● 问一下careercup一道题
● G电面题 + 求祝福● 问个最近面试里的题目
● 问一道题● L家的高频题merge k sorted arrays giving iterators求讨论！
● 关于Hash_map● Bloomberg 电面
相关话题的讨论汇总
话题: int话题: pair话题: map话题: integer话题: mymap
进入JobHunting版参与讨论
1 (共1页)
b****u
发帖数: 37
1
Question: For some N, print all the solutions of A * B = C * D where A, B, C
, D are all 1-N.
eg. n=2
print:
1 * 1 = 1 * 1
1 * 2 = 1 * 2
1 * 2 = 2 * 1
2 * 1 = 1 * 2
2 * 1 = 2 * 1
2 * 2 = 2 * 2
请问各位有什么好的解法？
b****p
发帖数: 216
2
先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?
f*****e
发帖数: 2992
3
map行不行？

C

【在 b****u 的大作中提到】
: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2
s*********s
发帖数: 318
4
1 * 4 = 4 * 1
这个也算吧。

【在 b****p 的大作中提到】
: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?
c****9
发帖数: 164
5
Hash_Map> Amap;
For(int i=0;i For(int j=0;j A[i*j] = Pair(i,j);
然后对hashmap做print
r*******e
发帖数: 7583
6
map value 应该是 list of pairs 吧

【在 c****9 的大作中提到】
: Hash_Map> Amap;
: For(int i=0;i: For(int j=0;j: A[i*j] = Pair(i,j);
: 然后对hashmap做print
e*******i
发帖数: 56
7
#include
#include
#include
using namespace std;
void printEqProducts(int n)
{
typedef unordered_multimap > MyMap;
typedef unordered_map ProductMap;
MyMap resMap;
ProductMap proMap;
for(int i=1; i<=n;i++)
for(int j=1;j<=n;j++)
{
resMap.insert( MyMap::value_type(i*j, pair(i, j)) );
proMap.insert( pair(i*j,i*j) );
}
pair eqRange;
MyMap::const_iterator it1;
MyMap::const_iterator it2;
ProductMap::const_iterator it;
for(it=proMap.begin();it!=proMap.end(); ++it)
{
eqRange=resMap.equal_range(it->second);
for(it1=eqRange.first; it1!=eqRange.second; ++it1)
{
for(it2=eqRange.first; it2!=eqRange.second; ++it2)
{
cout<< it1->second.first <<" * "<second.second<<"
= "<< it2->second.first <<" * "<second.second < }
}
}
}
int main()
{
printEqProducts(3);
}
z*******o
发帖数: 4773
8
N之间的任意i,j,
求i*j的所有因子.
g*******s
发帖数: 2963
9
用一个map的试试
#include
#include
#include
using namespace std;
void factorMutiplication(int n)
{
// hash all combinations
map>> map;
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
map[i*j].push_back(make_pair(i,j));
// print all combinations
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
{
vector> match = map[i*j];
for(int k=0; k cout< <<" = "
< < }
}
int main()
{
factorMutiplication(4);
cin.get();
return 0;
}
e***a
发帖数: 1661
10
did u work it out?

C

【在 b****u 的大作中提到】
: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2
相关主题
● G电面题 + 求祝福● 小弟求问LinkedIn那道Deep Iterator的题
● 问一道题● 发个g的电面
● 关于Hash_map● 灭三哥也不容易
进入JobHunting版参与讨论
b****u
发帖数: 37
11
我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。

【在 e***a 的大作中提到】
: did u work it out?
:
: C
b****u
发帖数: 37
12
不知道版上哪位大神有更好的解法。很好奇。

【在 b****u 的大作中提到】
: 我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。
S********e
发帖数: 28
13
Would it work if we change the equation to be 'A * B / C = D'?
That way, we would basically transform the original question to something
similar to '3Sum', with an extra condition that 'A * B % C == 0' must return
true.
E*****g
发帖数: 4
14
A/C = D/B
然后找所有小于n的互质的pair，每个pair对应一个base等式。对于每一个base等式，
通过上下左右同乘以整数来找所有的等式。
h****g
发帖数: 105
15
感觉和permutation题类似。如果 两因子一样，那么这一对就只会产生一组解(1,1,1,1
and 2,2,2,2) 如果两因子不一样 会产生四组解(abab,abba,baab,baba.)只计算这些
base可能会减少复杂度
S******6
发帖数: 55
16
觉得用map做已经算比较优的算法了
期待更好算法。。。
x******e
发帖数: 18
17
同意zhuangtuo的想法，伪代码如下：
for i=1:N
for j=1:N
for all common divisors k of i*j
if k<=N && (i*j)/k <= N
print (i,j,k, (i*j)/k)
时间复杂度：O(N^(5/2)), 还有没有更高效的方法？

C

【在 b****u 的大作中提到】
: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2
w*********m
发帖数: 4740
18
this seems the right direction

【在 b****p 的大作中提到】
: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?
j**h
发帖数: 1230
19
void printN(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
Set pairSet = getPairSet(i * j);
for (Pair pair : pairSet) {
System.out.println(i + "*" + j + "=" + pair.i + "*" +
pair.j);
}
}
}
}
Map> map = new HashMap>();
Set getPairSet(int product) {
if (map.containsKey(new Integer(product)))
return map.get(new Integer(product));
Set pairSet = new HashSet();
for (int i = 1; i < product; i++) {
if (product % i == 0)
pairSet.add(new Pair(i, product / i));
}
map.put(new Integer(product), pairSet);
return map.get(new Integer(product));
}
class Pair {
int i;
int j;
public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}
b****u
发帖数: 37
20
Question: For some N, print all the solutions of A * B = C * D where A, B, C
, D are all 1-N.
eg. n=2
print:
1 * 1 = 1 * 1
1 * 2 = 1 * 2
1 * 2 = 2 * 1
2 * 1 = 1 * 2
2 * 1 = 2 * 1
2 * 2 = 2 * 2
请问各位有什么好的解法？
相关主题
● 问个算法题● L家的高频题merge k sorted arrays giving iterators求讨论！
● 问一下careercup一道题● Bloomberg 电面
● 问个最近面试里的题目● a problem from leetcode: high efficiency algorithm for combinations problem
进入JobHunting版参与讨论
b****p
发帖数: 216
21
先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?
f*****e
发帖数: 2992
22
map行不行？

C

【在 b****u 的大作中提到】
: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2
s*********s
发帖数: 318
23
1 * 4 = 4 * 1
这个也算吧。

【在 b****p 的大作中提到】
: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?
c****9
发帖数: 164
24
Hash_Map> Amap;
For(int i=0;i For(int j=0;j A[i*j] = Pair(i,j);
然后对hashmap做print
r*******e
发帖数: 7583
25
map value 应该是 list of pairs 吧

【在 c****9 的大作中提到】
: Hash_Map> Amap;
: For(int i=0;i: For(int j=0;j: A[i*j] = Pair(i,j);
: 然后对hashmap做print
e*******i
发帖数: 56
26
#include
#include
#include
using namespace std;
void printEqProducts(int n)
{
typedef unordered_multimap > MyMap;
typedef unordered_map ProductMap;
MyMap resMap;
ProductMap proMap;
for(int i=1; i<=n;i++)
for(int j=1;j<=n;j++)
{
resMap.insert( MyMap::value_type(i*j, pair(i, j)) );
proMap.insert( pair(i*j,i*j) );
}
pair eqRange;
MyMap::const_iterator it1;
MyMap::const_iterator it2;
ProductMap::const_iterator it;
for(it=proMap.begin();it!=proMap.end(); ++it)
{
eqRange=resMap.equal_range(it->second);
for(it1=eqRange.first; it1!=eqRange.second; ++it1)
{
for(it2=eqRange.first; it2!=eqRange.second; ++it2)
{
cout<< it1->second.first <<" * "<second.second<<"
= "<< it2->second.first <<" * "<second.second < }
}
}
}
int main()
{
printEqProducts(3);
}
z*******o
发帖数: 4773
27
N之间的任意i,j,
求i*j的所有因子.
g*******s
发帖数: 2963
28
用一个map的试试
#include
#include
#include
using namespace std;
void factorMutiplication(int n)
{
// hash all combinations
map>> map;
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
map[i*j].push_back(make_pair(i,j));
// print all combinations
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
{
vector> match = map[i*j];
for(int k=0; k cout< <<" = "
< < }
}
int main()
{
factorMutiplication(4);
cin.get();
return 0;
}
e***a
发帖数: 1661
29
did u work it out?

C

【在 b****u 的大作中提到】
: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2
b****u
发帖数: 37
30
我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。

【在 e***a 的大作中提到】
: did u work it out?
:
: C
相关主题
● 问个递归的问题● combinations 有没有 iterative的方法阿 ?
● 写的LRU通不过大数据，帮忙看看● Max Points on a Line 用c++map老是没法compile
● 大家帮忙看看这个4sum怎么就不对● 求点评：电话面试（今天第二天没有消息回复，感觉可能挂了）
进入JobHunting版参与讨论
b****u
发帖数: 37
31
不知道版上哪位大神有更好的解法。很好奇。

【在 b****u 的大作中提到】
: 我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。
S********e
发帖数: 28
32
Would it work if we change the equation to be 'A * B / C = D'?
That way, we would basically transform the original question to something
similar to '3Sum', with an extra condition that 'A * B % C == 0' must return
true.
E*****g
发帖数: 4
33
A/C = D/B
然后找所有小于n的互质的pair，每个pair对应一个base等式。对于每一个base等式，
通过上下左右同乘以整数来找所有的等式。
h****g
发帖数: 105
34
感觉和permutation题类似。如果 两因子一样，那么这一对就只会产生一组解(1,1,1,1
and 2,2,2,2) 如果两因子不一样 会产生四组解(abab,abba,baab,baba.)只计算这些
base可能会减少复杂度
S******6
发帖数: 55
35
觉得用map做已经算比较优的算法了
期待更好算法。。。
x******e
发帖数: 18
36
同意zhuangtuo的想法，伪代码如下：
for i=1:N
for j=1:N
for all common divisors k of i*j
if k<=N && (i*j)/k <= N
print (i,j,k, (i*j)/k)
时间复杂度：O(N^(5/2)), 还有没有更高效的方法？

C

【在 b****u 的大作中提到】
: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2
w*********m
发帖数: 4740
37
this seems the right direction

【在 b****p 的大作中提到】
: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?
j**h
发帖数: 1230
38
void printN(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
Set pairSet = getPairSet(i * j);
for (Pair pair : pairSet) {
System.out.println(i + "*" + j + "=" + pair.i + "*" +
pair.j);
}
}
}
}
Map> map = new HashMap>();
Set getPairSet(int product) {
if (map.containsKey(new Integer(product)))
return map.get(new Integer(product));
Set pairSet = new HashSet();
for (int i = 1; i < product; i++) {
if (product % i == 0)
pairSet.add(new Pair(i, product / i));
}
map.put(new Integer(product), pairSet);
return map.get(new Integer(product));
}
class Pair {
int i;
int j;
public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}
h**o
发帖数: 548
39
为什么？

【在 w*********m 的大作中提到】
: this seems the right direction
A*****o
发帖数: 284
40
献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
#include
#include
#include
using namespace std;
int n;
void printPair(int a, int b) {
int m = a * b;
int x, y;
for (x = m/max(a,b); x <= (int)sqrt(double(m)); x++) {
if (m%x == 0) {
y = m / x;
printf("%d * %d = %d * %d\n", a, b, x, y);
printf("%d * %d = %d * %d\n", a, b, y, x);
printf("%d * %d = %d * %d\n", b, a, x, y);
printf("%d * %d = %d * %d\n", b, a, y, x);
}
}
}
void printEquation(int n) {
if (n <= 0) {
return;
}
int a, b;
for (a = 1; a <= n; a++) {
printf("%d * %d = %d * %d\n", a, a, a, a);
for (b = a+1; b <= n; b++) {
printPair(a, b);
}
}
}
int main() {
cin >> n;
printEquation(n);
return 0;
}
相关主题
● 求点评：电话面试（今天第二天没有消息回复，感觉可能挂了）● 问一道题
● 弱问一道G题● 关于Hash_map
● G电面题 + 求祝福● 小弟求问LinkedIn那道Deep Iterator的题
进入JobHunting版参与讨论
w**t
发帖数: 893
41


【在 A*****o 的大作中提到】
: 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
: #include
: #include
: #include
: using namespace std;
: int n;
: void printPair(int a, int b) {
: int m = a * b;
: int x, y;
: for (x = m/max(a,b); x <= (int)sqrt(double(m)); x++) {
w**t
发帖数: 893
42
x = m/max(a,b); 好像不对呀。2*3=1*6. we cannot start from 2
But the overall this direction seems right. I cannot see the extra space
taken by map solution provide gain for time complexity as big O.

【在 A*****o 的大作中提到】
: 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
: #include
: #include
: #include
: using namespace std;
: int n;
: void printPair(int a, int b) {
: int m = a * b;
: int x, y;
: for (x = m/max(a,b); x <= (int)sqrt(double(m)); x++) {
w*****d
发帖数: 105
43
我也是这个思路。先把所有abab的情况收集起来，然后找所有ab=cd的情况，这里注意
一下去重，可以约定必须c<=d。

,1

【在 h****g 的大作中提到】
: 感觉和permutation题类似。如果 两因子一样，那么这一对就只会产生一组解(1,1,1,1
: and 2,2,2,2) 如果两因子不一样 会产生四组解(abab,abba,baab,baba.)只计算这些
: base可能会减少复杂度
e***n
发帖数: 42
44
来个java的：
public static void twoProduct(int n){

Map> m = new HashMap String>>();

for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if (m.containsKey(i*j)){
m.get(i*j).add(Integer.toString(i) + '*' + Integer.toString(
j));
}
else{
ArrayList tmp = new ArrayList();
tmp.add(Integer.toString(i) + '*' + Integer.toString(j));
m.put(i*j, tmp);
}
}
}

for (Entry> tmp : m.entrySet()){
for (int i=0; i for (int j=0; j System.out.println(tmp.getValue().get(i) + "=" + tmp.
getValue().get(j));
}
}
}
}
A*****o
发帖数: 284
45
没有太明白... 请给个反例?

【在 w**t 的大作中提到】
: x = m/max(a,b); 好像不对呀。2*3=1*6. we cannot start from 2
: But the overall this direction seems right. I cannot see the extra space
: taken by map solution provide gain for time complexity as big O.
1 (共1页)
进入JobHunting版参与讨论
相关主题
● Bloomberg 电面● 弱问一道G题
● a problem from leetcode: high efficiency algorithm for combinations problem● G电面题 + 求祝福
● 问个递归的问题● 问一道题
● 写的LRU通不过大数据，帮忙看看● 关于Hash_map
● 大家帮忙看看这个4sum怎么就不对● 小弟求问LinkedIn那道Deep Iterator的题
● combinations 有没有 iterative的方法阿 ?● 发个g的电面
● Max Points on a Line 用c++map老是没法compile● 灭三哥也不容易
● 求点评：电话面试（今天第二天没有消息回复，感觉可能挂了）● 问个算法题
相关话题的讨论汇总
话题: int话题: pair话题: map话题: integer话题: mymap

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑