Stupid tax form - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

Stupid tax form

Stupid tax form# Joke - 肚皮舞运动

l*r2010-04-01 07:04

1 楼

1. Int to string (pay attention to the smallest negative number)
2. Given two sorted list, find the k smallest number (binary search)
3. You can win three kinds of basketball points, 1 point, 2 points, and 3
points. Given a total score X, print out all the combination to compose X. (
recursion/ Dp)
4. Given a stream of integers, at a given time, there is a number appeared
more than half time, how to find this number. (classic streaming algorithm
)

r*d2010-04-01 07:04

2 楼

Here is an example to show how stupid the tax form is:
page A-11
step 10. Divide line 9 by 1.5 (ok it is X 2/3)
step 11. Subtract line 10 from line 9 (isn't it 1 - 2/3 = 1/3 of line 9? )
Why shall we do it in 2 steps while we can do this easily by one step?
The problem is that I lose $$$ from the stupidity:
1. You can count state income tax in itemized deduction. Under certain cases
, you cannot get the full amount of the itemized deduction. So let's say you
get (state tax + other items) X 90% a

s*t2010-04-01 07:04

3 楼

ding
总看到itoa的题目，弱弱地问一下，是不是sprintf，ssteram之类的都不许用？
第四个题没想法

(
algorithm

【在 l*********r 的大作中提到】

: 1. Int to string (pay attention to the smallest negative number)
: 2. Given two sorted list, find the k smallest number (binary search)
: 3. You can win three kinds of basketball points, 1 point, 2 points, and 3
: points. Given a total score X, print out all the combination to compose X. (
: recursion/ Dp)
: 4. Given a stream of integers, at a given time, there is a number appeared
: more than half time, how to find this number. (classic streaming algorithm
: )

H*72010-04-01 07:04

4 楼

所以要用软件啊。不然会恶心死

m*g2010-04-01 07:04

5 楼

3是coin change的一种。就是每个都试，不算dp
4前面讨论过好象，就是用一个counter计数
cnt = 0;
curNum = 0;
while(input>>temp)
{
if(!cnt) curNum = temp;
if(temp == curNum)
cnt++;
else
cnt--;
}
大概就是这样

b*p2010-04-01 07:04

6 楼

这么笨的tax form你都能loss $$, 岂不是说明你更笨?

f*42010-04-01 07:04

7 楼

lz 面的啥职位？这4道都要求写代码么?
Given two sorted list, find the k smallest number
这个能用binary search么？谁给解释一下咋用binary search
保证list都是从小到大排序，2个list分别scan，输出小的那个值，然后那个指针后移
；得到k个停止

r*d2010-04-01 07:04

8 楼

The tax form clearly says that you have to use the numbers in your fed form
even if your deduct is limited. So it is intentionally made like that even
though it does not make sense to me. All software will do the same thing. It
is just like you can say a law is stupid, but it does not mean you can
break the stupid law.
Do not play any tricks in tax return!

【在 b********p 的大作中提到】

: 这么笨的tax form你都能loss $$, 岂不是说明你更笨?

s*t2010-04-01 07:04

9 楼

这个很直观
binary就是只保留两数组的头K个
然后比a[k/2],b[k/2]，每次缩小一般搜索范围
如果list指的是链表那还是算了。。

【在 f****4 的大作中提到】

: lz 面的啥职位？这4道都要求写代码么?
: Given two sorted list, find the k smallest number
: 这个能用binary search么？谁给解释一下咋用binary search
: 保证list都是从小到大排序，2个list分别scan，输出小的那个值，然后那个指针后移
: ；得到k个停止

f*42010-04-01 07:04

10 楼

恩，我的意思就是list的binary search。。。
顺带的，大家都是在哪里看这些题目啊？精华区？

【在 s*********t 的大作中提到】

: 这个很直观
: binary就是只保留两数组的头K个
: 然后比a[k/2],b[k/2]，每次缩小一般搜索范围
: 如果list指的是链表那还是算了。。

c*f2010-04-01 07:04

11 楼

谢谢！也问lz面的什么职位？

k*n2010-04-01 07:04

12 楼

t*n2010-04-01 07:04

13 楼

第四题对消法,如果两个整数不一样就消除
一样就计数

(
algorithm

【在 l*********r 的大作中提到】

b*92010-04-01 07:04

14 楼

第四题题目没有看懂啊。有谁能解释一下？多谢！
对消。。。计数。。。以前版上有讨论么？
哪位来帮忙解释一下！多谢！

l*a2010-04-01 07:04

15 楼

count=0;
for(int i=0;i{
if(count==0){temp=a[i];count++;}
else{ if(temp!=a[i]){count--;}
else count++;
}
}
return temp;

【在 b********9 的大作中提到】

: 第四题题目没有看懂啊。有谁能解释一下？多谢！
: 对消。。。计数。。。以前版上有讨论么？
: 哪位来帮忙解释一下！多谢！

a*12010-04-01 07:04

16 楼

每次删除2个不同的数，那剩下的数中，那个target出现的次数仍然超过总数的一半。
int nTimes = 0;
int target = 0;
for(int i=0; iif(nTimes==0){
target = a[i];
nTimes = 1;
} else {
if(target==a[i])
nTimes++;
else
nTimes--;
}
}
return target;

b*92010-04-01 07:04

17 楼

对吗？
int a[7] = {1,2,2,2,3,3,3};
算完后， nTimes = 1; Target = 3;
3没有超过一半的出现次数

【在 a*******1 的大作中提到】

: 每次删除2个不同的数，那剩下的数中，那个target出现的次数仍然超过总数的一半。
: int nTimes = 0;
: int target = 0;
: for(int i=0; i: if(nTimes==0){
: target = a[i];
: nTimes = 1;
: } else {
: if(target==a[i])
: nTimes++;

a*12010-04-01 07:04

18 楼

题目的要求是at a given time, there is a number appeared more than half time,
how to find this number. Assumption就是要有一个数出现次数超过半数吧.

b*92010-04-01 07:04

19 楼

你是对的。我忽略了这个assmuption。
有这个assumption，其实题目就转化为求出现次数最多的数。出现最多的数也就是出现
超过一半的那个数。所以大家一起对消，最后剩下的总是出现次数最多的那个数。
另外，之前完全误解了题目意思。题目应该编辑为more than half times不是more
than half time。。是次数。。不是时间。。。：）

time,

【在 a*******1 的大作中提到】

: 题目的要求是at a given time, there is a number appeared more than half time,
: how to find this number. Assumption就是要有一个数出现次数超过半数吧.

j*u2010-04-01 07:04

20 楼

3要注意按一定顺序(比如开始用2了就不能再用3了)，因为1 3 1和3 1 3算一种

【在 m*****g 的大作中提到】

: 3是coin change的一种。就是每个都试，不算dp
: 4前面讨论过好象，就是用一个counter计数
: cnt = 0;
: curNum = 0;
: while(input>>temp)
: {
: if(!cnt) curNum = temp;
: if(temp == curNum)
: cnt++;
: else