回忆今天的华为上机考试题

今天下午参加了华为在济南的上机考试(据说上午也有一批,题不一样)。回忆一下考的题目,总体还是很水,但是最后一题还是可耻的 WA 了……

  1. 初级题(100分,6个点):送分,输入a和b,输出[a,b]之间的素数,没有时间、空间限制,而且题干用中文把算法都给描述出来了,考验你是否会打开VS或Eclipse、编译、运行……
  2. 中级题(200分,4个点):输入一串逗号分隔(脑残)的数,不超过1000且无重复,输出这串数中可以被其它数整除的数,要求按输入顺序。基本也是送分,除了输入比较恶心(一般都是输入n,然后输入n个数;这个我只能用字符串一位一位处理了)。
    样例:输入”3,4,2,6″,输出”4 6″。
  3. 高级题(300分,4个点):有N个岛,给出岛间距离,全部连通最少需要多少距离的桥?输入n(3<=n<=1000),再输入n*n的邻接矩阵表示距离(没有给出距离的范围……都没说是不是整数……),输出最短桥距离。
    明显是MST,写完贪心(Kruskal,只记得这一种,也不让上网搜)交上去WA 2/4,而且只能提交五次,改了4种版本之后依然稳定的2/4,最后就只拿到一半分。交完最后一次才想到,是不是距离可能有浮点数……
    样例输入(自己编的):
    3
    0 123 456
    123 0 789
    456 789 0
    输出:579

总之是很水的题目,而且要吐槽的是做完之后不能走(15分钟做完前两题、45分钟败完5次提交,剩下一小时就瞪着监考老师),还要做职业测试(精神病测试),做完一遍因为做的太水又被迫做了第二遍……呵呵哒。

PS: 考场上有个孩子,可怜兮兮的给监考老师说,老师我没用过VS,我只会用Code::Blocks,这个VS简单的程序也报错,blah blah……当时我就傻了,还真有只用过Code::Blocks的大神orz……

PSS: 蒋震机房的XP+VS2005真是亮瞎了朕的氪金狗眼,新建工程Debug报缺少DLL,必须先修改一个“FAT32什么什么”的选项才能用……

Another afternoon wasted: How to choose two fonts with fontconfig

After upgrading to Ubuntu 16.04, the font in my GNOME is a mess (again). So I spent another afternoon trying to figure out how to choose the fonts I need using fontconfig.

This is what I achieved using Source Sans Pro and Source Han Sans CN. The default was to use DejaVu Sans and SimSun.

My goal is to use two fonts, an English one for displaying generic characters, and a Chinese one for, um, Chinese. Although I can use a single Chinese font for both, but the English characters displayed in Chinese font is disastrous. So basically I want to tell fontconfig to use the two fonts in a preferred order: Use English one wherever possible, and fallback to the native one when the former can’t do the job.

Actually I have solved this before, but I forgot what I did back then. So I had to spend another afternoon Googling and reading their long and non-standardized docs on how to express my request in their weird XML tags. After several attempts, I found that the following configuration works just fine.

The whole XML below should be saved as ~/.config/fontconfig/conf.d/99-xiaodu.conf (create non-existent folders when needed), which is the preferred location for user-specific fontconfig files.

<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
  <!-- For other languages -->
  <match target="pattern">
    <test qual="any" name="family">
     <string>sans-serif</string>
   </test>
   <edit name="family" mode="prepend" binding="strong">
      <string>Arial</string>
    </edit>
 </match>
  <match target="pattern">
    <test qual="any" name="family">
     <string>serif</string>
    </test>
   <edit name="family" mode="prepend" binding="strong">
      <string>Times New Roman</string>
    </edit>
 </match>
  <match target="pattern">
    <test qual="any" name="family">
     <string>monospace</string>
    </test>
   <edit name="family" mode="prepend" binding="strong">
      <string>Inconsolata</string>
    </edit>
 </match>
  <!-- For Chinese -->
  <match target="pattern">
    <test name="lang">
      <string>zh-cn</string>
    </test>
   <test qual="any" name="family">
     <string>sans-serif</string>
   </test>
   <edit name="family" mode="prepend" binding="strong">
      <string>Arial</string>
      <string>Source Han Sans CN</string>
   </edit>
 </match>
  <match target="pattern">
    <test name="lang">
      <string>zh-cn</string>
    </test>
   <test qual="any" name="family">
     <string>serif</string>
    </test>
   <edit name="family" mode="prepend" binding="strong">
      <string>Times New Roman</string>
      <string>Simsun</string>
   </edit>
 </match>
  <match target="pattern">
    <test name="lang">
      <string>zh-cn</string>
    </test>
   <test qual="any" name="family">
     <string>monospace</string>
    </test>
   <edit name="family" mode="prepend" binding="strong">
      <string>Inconsolata</string>
      <string>Source Han Sans CN</string>
   </edit>
 </match>

</fontconfig>

Basically this file tells fontconfig, when the locale is zh-cn (Chinese), it should to prepend the two fonts (English and Chinese) to the matching list; otherwise just prepend the English one.

Notice that the first font in each <edit> block is the English font, where the second is the native font. You should replace the language code (RFC3066 style) and all six font names using your favorite text editor, with respect to the fonts’ types (sans, serif or mono). If you want to test your work, use fc-match with something like $ LANG=zh-CN fc-match -s sans | head -2.

I just hope one day there would be a nice GUI for all this crap.

中文摘要:这篇文章介绍如何在 Ubuntu 中通过配置 fontconfig 同时选择要使用的英文和中文字体,使用英文字体显示一般字符,中文字体显示中文字符。

回忆一下 360 实习编程题

现在两批人都考完了,来透个题。规定上说不能用笔抄,没说不能用脑子记。省略全部废话,只说题干。总体来说就是一个字:

1. 两个人A、B,从一个整数范围(说是N,目测是[1,N],题出的非常模糊)里面各选一个数a和b,然后用一个均匀随机生成器在范围里生成一个数c,看谁离c近赢,相同距离算b赢。

现在输入是N和a,求b选几的时候胜率最大,相同胜率取最小。

样例:3 1 (输出2)、4 3 (输出2),完美的避开了是0还是1开始的问题……

</题干> 卤煮做了40%(还做出过20%,应该是5个点),还想出一个边界条件没写对,不知道剩下的错在哪里。

2. 给定字符串s,由a~z和小数点“.”组成,定义操作a(s),表示将s中最早出现的连续两个点替换成一个点;定义函数f(s),表示进行多少次操作a可以使得字符串中没有连续的点。

输入为n(字符串长度),m(字符串替换操作);第二行为n长字符串;第3行开始的m行,每行有k和c,表示将s中第k个字符(从1开始数,傻叉)替换为c。要求在每次替换后,输出替换后s’当前f(s’)的值。

样例:原来的巨长无比,我就随便编一个:4 1 a..b 4 . (输出2)。

</题干> 水题,只要注意是1开始这个大坑。读入后先计算原始的f(s),然后每次操作后,拿出操作位左右各一位,判断这三位在变化前后的diff,加到原始f(s)即可(当然,过后要真的替换)。

————————————————

2/5的WA啊,哪有这么多边界条件啊,我猜是大数据点输出的时候变成了科学记数法,但是我安装了跟OJ一样的g++版本,并没有被科学……天知道为什么,呵呵哒。

另外理论题考了好多设计模式、算法、数据库的细节题,理论渣表示全靠蒙,不服跑个分。

Prevent a package from being installed on Ubuntu / 在 Ubuntu 系统中阻止安装某个软件包

This article shows how to prevent a certain package from being installed, manually or as a dependency, on Linux systems using apt (apt-get) like Ubuntu and Debian.
这篇文章介绍如何在使用 apt (apt-get) 的系统上(例如 Ubuntu 和 Debian),防止某个软件包被安装,包括手动或被依赖。

It utilizes the “pinning” feature of apt, which you can read about in detail with man apt_preferences .
使用的原理是 apt 的 “pinning” 功能,可以通过 man apt_preferences 获取详细文档。

  1. Say we want to block “ttf-mscorefonts-installer” from being installed, which is a recommended dependency of “ubuntu-restricted-extras”. When we use apt-get install ubuntu-restricted-extras , the package will be automatically installed. If we use the “–no-install-recommends” switch, many other packages will be ignored, but we just want to block that one specific package.
    假设我们不想安装 “ttf-mscorefonts-installer” 软件包,但它是 “ubuntu-restricted-extras” 的推荐依赖。如果我们使用 apt-get install ubuntu-restricted-extras 命令,则依赖软件包也会自动安装。我们可以用 “–no-install-recommends” 开关阻止推荐依赖,但是同时会阻止其它很多软件包。接下来的方法适用于只阻止特定的一个软件包。
  2. In the folder “/etc/apt/preferences.d” we create a plain text file “block-package”, with the following contents:
    在 “/etc/apt/preferences.d” 文件夹中创建一个文本文件 “block-package”,内容如下:

    Package: ttf-mscorefonts-installer
    Pin: version *
    Pin-Priority: -10
    
  3. With a negative priority, the package will not be installed either manually or as a dependency when using apt-get.
    由于设置了负优先级,在使用 apt-get 时,这个软件包无论手动还是依赖都不会被安装。

Reference: http://askubuntu.com/questions/75895/how-to-forbid-a-specific-package-to-be-installed

Debugging random lagging on Android

My Samsung tablet with Android (4.4.2, rooted) has been experiencing random lagging for a while. This affects me most when I’m playing games on it. Earlier today I finally decided to find the root of the problem.

Finding the cause

The ultimate solution is to know which application is causing the lag and disable it. I first went to Settings > General > Developer Options (If you don’t have it, go to Settings > General > About phone/device and tap “Build number” 7+ times to enable it), and ticked “Show CPU usage”. Then you would see an overlay on the top-right corner of your device showing the top (like the Linux command) processes, similar to the image below.

Then I used my device to play games, and wait for the random lagging to happen. When the device start to response slowly, I watched the CPU usage overlay and see “gzip” topping the list. If you are not familiar with Linux, gzip is a compression tool similar to RAR or 7-Zip.

Wrapping (first attempt)

I was expecting some Android application to cause the lagging, instead it’s a command gzip that can be called by anyone. The problem became finding out who called it. Since my device is rooted, I decided to replace the original gzip binary with a wrapper that can log who called it before actually gzipping. Here is the wrapping bash script I used (first version, read on for second version):

#!/system/bin/sh

OPERATION=/system/bin/gzip.real
LOGFILE=/sdcard/gziplog.txt

OPTIONS="$@"

echo "`date` + $EUID `id` + $OPERATION "$@"" >> $LOGFILE

exec $OPERATION "$@"

The script does the following: (1) Log the time, user ID (the $EUID variable turns out to be useless, but `id` worked) and command line parameters to $LOGFILE (a plain text file in the internal storage); then (2) hand over the control to real gzip so that it doesn’t break the gzip functionality.

Then I used Root Explorer to rename /system/bin/gzip to /system/bin/gzip.real, and put my script to /system/bin/gzip (remember to modify the permission to be the same as gzip.real, usually 0755).

After using the device for a while and several lagging happened, I read the logging file and got these lines:

Fri Aug 28 13:53:22 CST 2015 +  uid=2000(shell) gid=2000(shell) groups=1007(log),1009(mount),1015(sdcard_rw),1028(sdcard_r),3003(inet),3006(net_bw_stats) context=u:r:dumpstate:s0 + /system/bin/gzip.real -6
Fri Aug 28 13:54:32 CST 2015 +  uid=2000(shell) gid=2000(shell) groups=1007(log),1009(mount),1015(sdcard_rw),1028(sdcard_r),3003(inet),3006(net_bw_stats) context=u:r:dumpstate:s0 + /system/bin/gzip.real -6
Fri Aug 28 13:55:43 CST 2015 +  uid=2000(shell) gid=2000(shell) groups=1007(log),1009(mount),1015(sdcard_rw),1028(sdcard_r),3003(inet),3006(net_bw_stats) context=u:r:dumpstate:s0 + /system/bin/gzip.real -6
Fri Aug 28 13:56:53 CST 2015 +  uid=2000(shell) gid=2000(shell) groups=1007(log),1009(mount),1015(sdcard_rw),1028(sdcard_r),3003(inet),3006(net_bw_stats) context=u:r:dumpstate:s0 + /system/bin/gzip.real -6

Observe that `id` produced “uid=2000(shell) gid=2000(shell) ...” and the command called is “gzip -6“. This means gzip was called by the shell user, not a specific application, and the data to be compressed was piped in to gzip and then piped out, since there are no input or output file names. (Spoiler: Actually this has shown “context=u:r:dumpstate:s0” which indicated that it was called by “dumpstate“, but I didn’t realize for the first time.)

Wrapping (second attempt)

Then I decided to take the surveillance up a level, and used the following wrapper in place of the first version:

#!/system/bin/sh

OPERATION=/system/bin/gzip.real
LOGFILE=/sdcard/gziplog.txt
TEE="/system/bin/busybox0 tee"
PSTREE="/system/bin/busybox0 pstree"

OPTIONS="$@"

echo "[$$] `date` + $EUID `id` + $OPERATION "$@"" >> $LOGFILE
$PSTREE -p >> $LOGFILE

#exec $OPERATION "$@"
$TEE -a $LOGFILE | $OPERATION "$@"

The difference between it and the previous one is that, it uses Busybox’s “pstree” command to output the process tree of that moment, and “tee” command to record the data piped in and pipe it out again. In order for this to work, I downloaded busybox-armv7l binary (my device has ARMv7 architecture) from the official website and put it to /system/bin/busybox0 with the same permission as gzip.real. You can also use Busybox installer apps and modify the busybox path accordingly.

After a while, I got the following log this time:

[8691] Fri Aug 28 14:30:46 CST 2015 +  uid=2000(shell) gid=2000(shell) groups=1007(log),1009(mount),1015(sdcard_rw),1028(sdcard_r),3003(inet),3006(net_bw_stats) context=u:r:dumpstate:s0 + /system/bin/gzip.real -6
init(1)-+-Binder_2(2299)---{Binder_1}(2360)
        |-DaemonServer(5419)---app_process(8668)
        |-DaemonServer(6687)
<...snip...>
        |-debuggerd(2276)---dumpstate(8690)-+-gzip(8691)---busybox0(8695)
        |                                   `-top(8696)
<...snip...>
========================================================
== dumpstate: 2015-08-28 14:30:46
========================================================

Build: KOT49H.P601ZCUCNH1
Build fingerprint: 'samsung/lt033gzc/lt033g:4.4.2/KOT49H/P601ZCUCNH1:user/release-keys'
Bootloader: P601ZCUCNH1
Radio: unknown
<...snip...>

Observe that [8691] is the gzip wrapper’s PID, and it’s called by “dumpstate“, which is then called by “debuggerd“. The wrapper also logged the data to be compressed, which is 5 MB long and takes 0.14s to be compressed on my PC instead of a poor mobile device.

Final solution

A quick Google told me this is for developers to debug the system state, and since I’m not a developer in this area, I decided to disable it once for all. This is done by using Root Explorer to revoke the execute permissions from the two binaries /system/bin/{debuggerd,dumpstate}.

Now the lagging is gone.