异度部落格

学习是一种生活态度。

0%

Posted on In

【试题描述】定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

struct ListNode {
	int value;
	ListNode* next;
};

ListNode* createList(int* data, int n) {

	ListNode* headNode = NULL;
	ListNode* lastNode = NULL;

	for(int i = 0; i < n; i++) {
		ListNode* node = new ListNode();
		node->value = data[i];
		node->next = NULL;
		if(i == 0) {
			headNode = node;
		} else {
			lastNode->next = node;
		}
		lastNode = node;
	}

	return headNode;
}

void printList(ListNode* headNode) {

	if(headNode == NULL) {
		return ;
	}
	ListNode* node = headNode;
	while(node != NULL) {
		cout << node->value << " ";
		node = node->next;
	}
}

ListNode* reverseList(ListNode* headNode) {

	if(headNode == NULL) {
		return NULL;
	}

	ListNode* curNode = headNode;
	ListNode* preNode = NULL;
	ListNode* nextNode = NULL;

	while(curNode != NULL) {

		nextNode = curNode->next;
		curNode->next = preNode;
		preNode = curNode;
		curNode = nextNode;

	}
	return preNode;
}

int main() {
	int data[] = {1, 2, 3, 4, 5, 6, 7};
	int n = 7;
	ListNode* headNode = createList(data, n);
	ListNode* reverseNode = reverseList(headNode);
	printList(reverseNode);
	return 0;
}

Posted on In

【试题描述】给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。

【试题来源】 未知

【试题分析】按照常规删除链表节点的方法没有办法在O(1)复杂度内完成，因此需要转换思路，将后面一个节点的内容复制过来，然后删除其后面的那个节点，以达到删除节点的目的。

【参考代码】

struct ListNode
{
	int value;
	ListNode* next;
};

void deleteLinkNode(ListNode** pHeadNode, ListNode* pDeleteNode) {

	if(pHeadNode == NULL || pDeleteNode == NULL) {
		return ;
	}

	//删除节点在头部
	if(pDeleteNode == *pHeadNode) {
		delete pDeleteNode;
		pDeleteNode = NULL;
		*pHeadNode = NULL;
	//删除节点在末尾
	} else if(pDeleteNode->next == NULL) {
		ListNode* pNode = *pHeadNode;
		while(pNode->next != pDeleteNode) {
			pNode = pNode->next;
		}
		pNode->next = NULL;
		delete pDeleteNode;
		pDeleteNode = NULL;
	} else {
		ListNode* pNode = pDeleteNode->next;

		pDeleteNode->value = pNode->value;
		pDeleteNode->next = pNode->next;

		delete pNode;
		pNode = NULL;
	}
}

Posted on In

【试题描述】 输入一个整数数组，实现一个函数来调整该数组中数字的顺序。使得所有奇数位于数组的前半部分，所有偶数位于数组后半部分。

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

void reorder(int* data, int length) {

	int i = 0;
	int j = length - 1;

	while(i < j) {
		while(i < j && (data[i] & 1)) {
			i++;
		}

		while(i < j && !(data[j] & 1)) {
			j--;
		}

		if(i < j) {
			int tmp = data[i];
			data[i] = data[j];
			data[j] = tmp;
		}
	}
}

int main() {
	int data[] = {1,2,3,4,5,6,7,8,9,10};
	int length = 10;
	reorder(data, length);

	for(int i = 0; i < length; i++) {
		cout << data[i] << " ";
	}

	return 0;
}

Posted on In

【试题描述】把一个数组最开始的若干个元素搬到末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小元素为1.

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

int findMinNumber(int* numbers, int length) {

	if(numbers == NULL || length <= 0) {
		throw "Invalid parameters.";
	}

	int index1 = 0;
	int index2 = length - 1;
	int indexMid = (index1 + index2) / 2;
	while(numbers[index1] >= numbers[index2]) {

		if(index2 - index1 == 1) {
			return numbers[index2];
		}

		indexMid = (index1 + index2) / 2;
		if(numbers[index1] == numbers[index2]
		    && numbers[index1] == numbers[indexMid]) {
			int result = numbers[index1 + 1];
			for(int i = index1 + 1; i <= index2; ++i) {
				if(result > numbers[i]) {
					result = numbers[i];
				}
			}
		} else if(numbers[indexMid] >= numbers[index1]) {
			index1 = indexMid;
		} else if(numbers[indexMid] <= numbers[index2]) {
			index2 = indexMid;
		}
	}
	return numbers[indexMid];
}

int main() {
	int array[] = {3, 4, 5, 1, 2};
	//int array[] = {3, 4, 4, 5, 5, 6, 7, 8, 1, 2, 2, 2, 3, 3, 3};
	cout << findMinNumber(array, 5) << endl;
	return 0;
}

Posted on In

【试题描述】用两个栈实现一个队列。队列声明如下，请实现它的两个函数appendTail，deleteHead，分别完成在队列尾部插入节点和在头部删除节点。

【试题来源】未知

【参考代码】

#include <iostream>
#include <stack>
using namespace std;

template <typename T>
class MyQueue
{

public:
	void appendTail(const T& element);
	T deleteHead();

private:
	stack<T> inStack;
	stack<T> outStack;
};

template <typename T>
void MyQueue<T>::appendTail(const T& element) {

	inStack.push(element);
}

template <typename T>
T MyQueue<T>::deleteHead() {

	if(outStack.empty()) {
		//将inStack里面的数据放入outStack中
		if(!inStack.empty()) {
			while(!inStack.empty()) {
				T element = inStack.top();
				outStack.push(element);
				inStack.pop();
			}
		} else {
			throw "The Queue is empty.";
		}
	}
	T element = outStack.top();
	outStack.pop();

	return element;
}

int main() {
	MyQueue<int> queue;
	queue.appendTail(1);
	queue.appendTail(3);
	queue.appendTail(5);
	cout << queue.deleteHead() << endl;
	cout << queue.deleteHead() << endl;
	cout << queue.deleteHead() << endl;

	return 0;
}

Posted on In

最近准备重温 C++，正好看到有关类和占用空间的问题，于是整理了下。先上代码

#include <iostream>
using namespace std;

//空类型，没有任何成员
class ClassA {

};

//添加构造函数和析构函数
class ClassB {

public:
	ClassB() {};
	~ClassB() {};

};

//仅包含一个虚构函数
class ClassC {
	virtual void fun() {};
};

int main() {

	ClassA A;
	cout << "ClassA:" << sizeof(A) << endl;

	ClassB B;
	cout << "ClassB:" << sizeof(B) << endl;

	ClassC C;
	cout << "ClassC:" << sizeof(C) << endl;

	return 0;
}

结果：

ClassA:1
ClassB:1
ClassC:4

【分析】 1）ClassA 里面没有定义任何变量和函数，本应该是 0 的，但是声明变量需要占用一个字节，因此是 1。
2）ClassB 里面仅仅定义了构造函数和析构函数。调用构造函数和析构函数只需要知道地址即可，而这些函数的地址只与类型相关，而与实例无关，编译器不会因为这两个函数在实例中添加任何信息。
3）ClassC 中仅有一个虚函数。C++编译器一旦发现类型中有虚函数，就会为该类型生成虚函数表，并在该类型的每个实例中添加一个指向虚函数表的指针。

PS：编译器 GCC 4.6.2

Posted on In

【试题描述】请实现一个函数，把字符串中的每个空格替换成%20。例如输入"We are happy."，则输出"We%20are%20happy."。（不能使用任何字符串操作函数）

【试题来源】未知

【试题分析】由于不能使用字符串操作函数，因此只能一个字符一个字符的进行处理。 首先先遍历一遍字符串，统计得到所有的空格，那么替换后的字符串长度应 为len(str) + numOfBlank * 2。然后从后往前面修改字符串。算法时间复杂度O(n)。

【参考代码】

#include <cstdio>
#include <cstring>
using namespace std;

void replaceSpace(char str[], int length) {
	if(str == NULL) {
		return ;
	}

	int numOfBlank = 0;
	int i = 0;
	while(str[i] != '\0') {
		if(str[i] == ' ') {
			numOfBlank++;
		}
		i++;
	}

	int indexOriginalString = length - 1;
	int indexNewString = length + numOfBlank * 2 - 1;
	while(indexOriginalString >= 0) {
		if(str[indexOriginalString] == ' ') {
			str[indexNewString--] = '0';
			str[indexNewString--] = '2';
			str[indexNewString--] = '%';
		} else {
			str[indexNewString--] = str[indexOriginalString];
		}
		indexOriginalString--;
	}
}

int main() {
	char str[] = "We are happy.";
	//char str[] = " We are happy. ";
	//char str[] = "Wearehappy.";
	replaceSpace(str, strlen(str));
	printf("%s", str);

	return 0;
}

Posted on In

【试题描述】输入二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设遍历结果中都不包含重复数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6}，则重建出该二叉树，并以后续遍历输出。

【参考代码】

#include <iostream>
using namespace std;

struct BinaryTreeNode
{
	int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
};

BinaryTreeNode* rebulidBinaryTreeCore(int* startPreOrder, int* endPreOrder,
		int* startInOrder, int* endInOrder) {

	//先序遍历的第一个节点为根节点
	//创建根节点
	BinaryTreeNode* rootNode = new BinaryTreeNode();
	rootNode->value = startPreOrder[0];
	rootNode->left = NULL;
	rootNode->right = NULL;

	if(startPreOrder == endPreOrder) {
		if(startInOrder == endInOrder
				&& *startPreOrder == *startInOrder) {
			return rootNode;
		} else {
			throw ("Invalid input.");
		}
	}

	//在中序查找根节点
	int* rootIndex = startInOrder;
	while(rootIndex <= endInOrder && *rootIndex != rootNode->value) {
		rootIndex++;
	}
	if(rootIndex == endInOrder && *rootIndex != rootNode->value) {
		throw ("Invalid input.");
	}

	//重建左子树
	int leftTreeLength = rootIndex - startInOrder;
	if(leftTreeLength > 0) {
		rootNode->left = rebulidBinaryTreeCore(startPreOrder + 1,
				startPreOrder + leftTreeLength,
				startInOrder,
				rootIndex - 1);
	}

	//重建右子树
	if(leftTreeLength < endPreOrder - startPreOrder) {
		rootNode->right = rebulidBinaryTreeCore(startPreOrder + leftTreeLength + 1,
				endPreOrder,
				rootIndex + 1,
				endInOrder);
	}

	return rootNode;
}

BinaryTreeNode* rebulidBinaryTree(int* preOrder, int* inOrder, int n) {
	if(preOrder == NULL || inOrder == NULL || n <= 0) {
		return NULL;
	}

	return rebulidBinaryTreeCore(preOrder, preOrder + n -1,
			inOrder, inOrder + n - 1);
}

void printPostOrder(BinaryTreeNode* root) {
	if(root!= NULL) {
		if(root->left != NULL) {
			printPostOrder(root->left);
		}
		if(root->right != NULL) {
			printPostOrder(root->right);
		}
		cout << root->value << " ";
	}
	return ;
}

int main() {
	int preOrder[8] = {1,2,4,7,3,5,6,8};
	int inOrder[8] = {4,7,2,1,5,3,8,6};
	BinaryTreeNode* root = rebulidBinaryTree(preOrder, inOrder, 8);
	printPostOrder(root);
	return 0;
}

Posted on In

几乎所有的博客都可以在线阅读，或者通过 RSS 订阅源进行阅读。RSS 订阅源是一个包含博客及其所有文章条目信息的简单的 XML 文档。 程序中使用了 feedparser 第三方模块，可以轻松地从任何 RSS 或 Atom 订阅源中得到标题、链接和文章的条目。完整代码如下：

'''
Created on Jul 14, 2012

@Author: killua
@E-mail: killua_hzl@163.com
@Homepage: http://www.yidooo.net
@Decriptioin: Counting the words in a Feed

feedparser:feedparser is a Python library that parses feeds in all known formats, including Atom, RSS, and RDF.It runs on Python 2.4 all the way up to 3.2.

dataset: http://kiwitobes.com/clusters/feedlist.txt
         You can download feeds from this list. Maybe some feeds you can access in China.
'''

import feedparser
import re

#Get word from feed
def getwords(html):
    #Remove all the HTML tags
    text = re.compile(r"<[^>]+>").sub('', html)

    #Split words by all non-alpha characters
    words = re.compile(r"[^A-Z^a-z]+").split(text)

    #Convert words to lowercase
    wordlist = [word.lower() for word in words if word != ""]

    return wordlist

#Returns title and dictionary of word counts for an RSS feed
def getFeedwordcounts(url):
    #Parser the feed
    d = feedparser.parse(url)
    wordcounts = {}

    #Loop over all the entries
    for e in d.entries:
        if 'summary' in e:
            summary = e.summary
        else:
            summary = e.description

    words = getwords(e.title + ' ' + summary)
    for word in words:
        wordcounts.setdefault(word, 0)
        wordcounts[word] += 1

    return d.feed.title, wordcounts

if __name__ == '__main__':
    #count the words appeared in blog
    blogcount = {}
    wordcounts = {}

    feedFile = file('resource/feedlist.txt')
    feedlist = [line for line in feedFile.readlines()]

    for feedUrl in feedlist:
        try:
            title, wc = getFeedwordcounts(feedUrl)
            wordcounts[title] = wc
            for word, count in wc.items():
                blogcount.setdefault(word, 0)
                if count > 1:
                    blogcount[word] += 1
        except:
            print 'Failed to parse feed %s' % feedUrl

    wordlist = []
    for w, bc in blogcount.items():
        frac = float(bc) / len(feedlist)
        if frac > 0.1 and frac < 0.5:
            wordlist.append(w)

    #Write the result to the file
    datafile = file('blogdata', 'w')
    #Write result's head
    datafile.write('Blog')
    for word in wordlist:
        datafile.write('\t%s' % word)
    datafile.write('\n')
    #Write results
    for blogname, wc in wordcounts.items():
        print blogname
        datafile.write(blogname)
        for word in wordlist:
            if word in wc:
                datafile.write("\t%d" % wc[word])
            else:
                datafile.write("\t0")
        datafile.write('\n')

Posted on In

2012 Microsoft Intern Hiring Written Test

1. Suppose that a Selection Sort of 80 items has completed 32 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?
A) 16 B) 31 C) 32 D) 39 E) 40

2. Which Synchronization mechanism(s) is/are used to avoid race conditions among processes/threads in operating systems?
A) Mutex B) Mailbox C) Semaphore D) Local procedure call

3. There is a sequence of n numbers 1, 2, 3,.., n and a stack which can keep m numbers at most. Push the n numbers into the stack following the sequence and pop out randomly. Suppose n is 2 and m is 3, the output sequence may be 1, 2 or 2, 1, so we get 2 different sequences. Suppose n is 7 and m is 5, please choose the output sequences of the stack:
A) 1, 2, 3, 4, 5, 6, 7
B) 7, 6, 5, 4, 3, 2, 1
C) 5, 6, 4, 3, 7, 2, 1
D) 1, 7, 6, 5, 4, 3, 2
E) 3, 2, 1, 7, 5, 6, 4

4. What is the result of binary number 01011001 after multiplying by 0111001 and adding 1101110?
A) 0001 0100 0011 1111
B) 0101 0111 0111 0011
C) 0011 0100 0011 0101

5. What is output if you compile and execute the following code?

void main()
{
int i = 11;
int const *p = &i;
p++;
printf("%d", *p);
}
  1. 11 B) 12 C) Garbage value D) Compile error E) None of above

6. Which of following C++ code is correct?
A) int f() { int a = new int(3); return a; } B) int f() { int a[3] = {1, 2, 3}; return a; } C) vector f() { vector v(3); return v; } D) void f(int ret) { int a[3] = {1, 2, 3}; ret = a; return; }

7. Given that the 180-degree rotated image of a 5-digit number is another 5-digit number and the difference between the numbers is 78633, what is the original 5-digit number?
A) 60918 B) 91086 C) 18609 D) 10968 E) 86901

8. Which of the following statements are true?
A) We can create a binary tree from given inorder and preorder traversal sequences.
B) We can create a binary tree from given preorder and postorder traversal sequences.
C) For an almost sorted array, insertion sort can be more effective than Quicksort.
D) Suppose T(n) is the runtime of resolving a problem with n elements, T(n) = Θ(1) if n = 1; T(n) = 2T(n/2) + Θ(n) if > 1; so T(n) is Θ(n log n).
E) None of the above.

9. Which of the following statements are true?
A) Insertion sort and bubble sort are not effcient for large data sets.
B) Quick sort makes O(n^2) comparisons in the worst case.
C) There is an array: 7, 6, 5, 4, 3, 2, 1. If using selection sort (ascending), the number of swap operation is 6.
D) Heap sort uses two heap operations: insertion and root deletion.
E) None of above.

10. Assume both x and y are integers, which one of the followings returns the minimum of the two integers?
A) y ^ ((x ^ y) & ~(x < y))
B) y ^(x ^ y)
C) x ^ (x ^ y)
D) (x ^ y) ^ (y ^ x)
E) None of the above

11. The Orchid Pavilion (兰亭集序) is well known as the top of "行书" in history of Chinese literature. The most fascinating sentence "Well I know it is a lie to say that life and death is the same thing, and that longevity and early death make no difference! Alas!" ("周知一死生为虚诞，齐彭殇为妄作。") By counting the characters of the whole content (in Chinese version), the result should be 391 (including punctuation). For these characters written to a text file, please select the possible file size without any data corrupt.
A) 782 bytes in UTF-16 encoding
B) 784 bytes in UTF-16 encoding
C) 1173 bytes in UTF-8 encoding D) 1176 bytes in UTF-8 encoding
E) None of the above

12. Fill the blanks inside class definition

class Test
{
public:
____ int a;
____ int b;
public:
Test::Test(int _a, int _b) : a(_a) {b = _b;}
};
int Test::b;
int _tmain(int argc, __TCHAR *argv[])
{
Test t1(0, 0), t2(1, 1);
t1.b = 10;
t2.b = 20;
printf("%u %u %u %u", t1.a, t1.b, t2.a, t2.b);
}

Running result: 0 20 1 20
A) static/const
B) const/static
C) --/static
D) const static/static
E) None of the above

13. A 3-order B-tree has 2047 key words, what is the maximum height of the tree?
A) 11 B) 12 C) 13 D) 14

14. In C++, which of the following keyword(s) can be used on both a variable and a function?
A) static B) virtual C) extern D) inline E) const

15. What is the result of the following program?

char* f(char *str, char ch)
{
char *it1 = str;
char *it2 = str;
while (*it2 != '\0') {
while (*it2 == ch) {
it2++;
}
*it1++ = *it2++;
}
return str;
}
void main(int argc, char *argv[])
{
char *a = new char[10];
strcpy(a, "abcdcccd");

cout << f(a, 'c');
}
  1. abdcccd B) abdd C) abcc D) abddcccd E) Access Violation

16. Consider the following definition of a recursive function, power, that will perform exponentiation.

int power(int b, int e)
{
if (e == 0) return 1;
if (e %2 == 0) return power (b * b, e / 2);
return b * power(b * b, e / 2);
}

Asymptotically (渐进地) in terms of the exponent e, the number of calls to power that occur as a result of the call power(b, e) is* A) logarithmic B) linear C) quadratic D) exponential

17. Assume a full deck of cards has 52 cards, 2 black suits (spade and club) and 2 red suits (diamond and heart). If you are given a full deck, and a half deck (with 1 red suit and 1 black suit), what's the possibility for each one getting 2 red cards if taking 2 cards?
A) 1/2, 1/2 B) 25/102, 12/50 C) 50/51, 24/25 D) 25/51, 12/25 E) 25/51, 1/2

18. There is a stack and a sequence of n numbers (i.e., 1, 2, 3, ..., n). Push the n numbers into the stack following the sequence and pop out randomly. How many different sequences of the number we may get? Suppose n is 2, the output sequence may be 1, 2 or 2, 1, so we get 2 different sequences.
A) C_2n^n
B) C_2n^n - C_2n^(n + 1)
C) ((2n)!) / (n + 1)n!n!
D) n!
E) None of the above

19. Longest Increasing Subsequence (LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing. For example, LIS of {2, 1, 4, 2, 3, 7, 4, 6} is {1, 2, 3, 4, 6}, and its LIS length is 5. Considering an array with N elements, what is the lowest time and space complexity to get the length of LIS?
A) Time: N^2, Space: N^2
B) Time: N^2, Space: N
C) Time: NlogN, Space: N
D) Time: N, Space: N
E) Time: N, Space: C

20. What is the output of the following piece of C++ code?

#include <iostream>
using namespace std;*
struct Item
{
char c;
Item *next;
};
Item Routine1(Item *x)
{
Item *prev = NULL, *curr = x;
while (curr) {
Item *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
void Routine2(Item *x)
{
Item *curr = x;
while (curr) {
cout << curr->c << " ";
curr = curr->next;
}
}
void _tmain(void)
{
Item *x,
d = {'d', NULL},
c = {'c', &d},
b = {'b', &c},
a = {'a', &b};*
x = Routine1(&a);
Routine2(x);
}
  1. cbad B) badc C) dbca D) abcd E) dcba