Windows via C/C++ Chapter 2 : 字符和字符串

基础知识

1.自Windows NT起,Windows的所有版本都完全用Unicode来构建。也就是说,所有核心函数(创建窗口、显示文本、进行字符串处理等等)都需要Unicode字符串。
2.在Windows Vista以及后续系统版本中,每个Unicode字符都使用UTF-16编码,UTF全称是Unicode Transformation Format(Unicode转换格式)。UTF-16将每个字符编码为2个字节(或者说16位)。
3.C运行库中任何修改字符串的函数都存在一个安全隐患:如果目标字符串缓冲区不够大,无法容纳所生成的字符串,就会导致内存中的数据被破坏(memory corruption)。
4.strcpy和wcscpy函数(以及其他大多数字符串处理函数)的问题在于,它们没有收到指定了缓冲区最大长度的参数。
5.为了写安全的代码,我们应该放弃这些熟悉的、能修改字符串的C运行库函数(不过,strlen、wcslen和_tcslen等函数是没有问题的,因为它们不会修改传入的字符——即使它们假设字符串是以0来终止的,而这个假设有时并不一定成立)。
6.新的安全字符串函数,在应用程序中包含StrSafe.h时,String.h也会被包含进来。C运行库中现有的字符串处理函数(如_tcscpy宏后的那些函数)已被标记为废弃不用。现有的每一个函数(如_tcscpy或_tcscat),都有一个对应的新版本的函数。前面的名字相同,但最后添加了一个_s(代表secure)后缀。
Continue Reading…

Microsoft Online Test for Core Technical Positions 4: Most Frequent Logs

Time Limit:10000ms
Case Time Limit:3000ms
Memory Limit:256MB

Description

In a running system, there are many logs produced within a short period of time, we’d like to know the count of the most frequent logs.

Logs are produced by a few non-empty format strings, the number of logs is N(1<=N<=20000), the maximum length of each log is 256.

Here we consider a log same with another when their edit distance (see note) is <= 5.

Also we have a) logs are all the same with each other produced by a certain format string b) format strings have edit distance  5 of each other.

Your program will be dealing with lots of logs, so please try to keep the time cost close to O(nl), where n is the number of logs, and l is the average log length.

Note edit distance is the minimum number of operations (insertdeletereplace a character) required to transform one string into the other, please refer to

http://en.wikipedia.orgwikiEdit_distance for more details.
Continue Reading…

Microsoft Online Test for Core Technical Positions 3: Reduce inversion count

Time Limit:10000ms
Case Time Limit:1000ms
Memory Limit:256MB

Description

Find a pair in an integer array that swapping them would maximally decrease the inversion count of the array. If such a pair exists, return the new inversion count; otherwise returns the original inversion count.

Definition of Inversion: Let (A[0], A[1] … A[n], n <= 50) be a sequence of n numbers. If i < j and A[i] > A[j], then the pair (i, j) is called inversion of A.

Example:
Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2
InversionCountOfSwap({3, 1, 2})=>
{
InversionCount({1, 3, 2}) = 1 <– swapping 1 with 3, decreases inversion count by 1
InversionCount({2, 1, 3}) = 1 <– swapping 2 with 3, decreases inversion count by 1
InversionCount({3, 2, 1}) = 3 <– swapping 1 with 2 , increases inversion count by 1
}
Continue Reading…