Thursday, October 31, 2013

Use Priority Queue to find k largest/smallest elements from a sequence

/*
 * Internally Priority queue is implemented as a min_heap
 * so we can utilize the min_heap's properties to implement our code
*/

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void k_largest(vector<int> a, int n, int k){  
    int i;
    vector<int> ans;
    priority_queue<int, vector<int>, greater<int>> p;     // this is a min_heap
 
 
    for(i=0;i<k;i++)
        p.push(a[i]);
    //cout<<p.top()<<endl;
    for(i=k; i<n; i++)
        if(a[i]>(p.top())){
            p.pop();
            p.push(a[i]);
       }
 
    for(; !p.empty(); p.pop())
        ans.push_back(p.top());
     
 
    for(i=0;i<(int)ans.size();i++)
        printf("%d ",ans[i]);
    puts("");
}

int main(){
    vector<int> a{6, 7, 2, 3, 5, 1, 8, 4, 10};
    int len = a.size();
    int k = 3;
    k_largest(a, len, k);
    return 0;
}

Wednesday, October 16, 2013

Ubuntu 中文输入法安装 ibus

Ubtuntu 12.04 中自带了中文输入法,在英文系统中同样已经预装了ibus,只需要下载一下简体中文语言包,即可通过Ctrl+Space进行输入法到切换。
如何安装简体中文语言包?
依次选择 Sytem Setting --> Language Support --> Install/Remove Languages后,将出现如下图所示窗口:
将右侧 Installed 栏的选择框勾选后,单击按钮 Apply Changes,之后会要求你输入密码,输入完成之后,系统将会自动下载并安装简体中文语言包。
一般情况下Ubuntu12.04中已经预装了ibus,如果你在进行下一步的时候提示了错误,在终端输入以下指令安装一些必须的库文件:
1sudo apt-get install ibus ibus-clutter ibus-gtk ibus-gtk3 ibus-qt4
如何设置ibus框架?
设置ibus框架请在终端输入以下指令:
1im-switch -s ibus
完成以上步骤后建议注销系统(亲测12.04 时未注销也可正常执行后面步骤,如果后面步骤无效,请尝试注销)
如何安装拼音引擎?
在Ubuntu12.04中已默认安装拼音引擎,如果你在进行下一步的时候未发现拼音(或其它)选项,请在终端输入以下相关指令:
1ibus拼音:      sudo apt-get install ibus-pinyin
2ibug五笔:      sudo apt-get install ibus-table-wubi
3谷歌拼音输入法: sudo apt-get install ibus-googlepinyin
4Sun拼音输入法:  sudo apt-get install ibus-sunpinyin
如何启动ibus框架?
启动ibus框架请在终端输入以下指令:
1ibus-setup
此时,IBus Preferences 设置会打开,可能会提示监控程序未启动,单击 Yes 即可,切换至 Input Method 选项卡中,选择自己喜欢的输入方式,并可自定义切换快捷键,界面应当大致如下图:
通常情况下,ibus图标(一个小键盘)会出现在右上角的任务栏中,大致如下图所示:

有时候它会开个小差跑出去玩,可以通过在终端输入以下指令叫它回家吃饭:
1ibus-daemon -drx
更多细节设置可自行研究,全都在ibus的设置面板里。

如果想安装最新的gcin中文输入法,请参考:

Wednesday, October 2, 2013

Interview Question: Convert a numeric string to an integer


#include<stdio.h>
#include<cctype>

int StrtoDecInt(const char* str){
    static const int MAX = (int)((unsigned)~0>>1);
    static const int MIN = -(int)((unsigned)~0 >> 1) - 1;

    unsigned int n = 0;
    int sign = 1;
    unsigned int c;

    while (isspace(*str))
        ++str;

    if( *str == '-' || *str == '+'){
        if(*str == '-')
            sign = -1;
        ++str;
    }

    while(isdigit(*str)){
        c=*str-'0';
        if(sign >0 && (n > MAX/10 || (n == MAX/10 && c > MAX % 10))){
            n = MAX;
            break;
        }else if (sign < 0 && (n > (unsigned) MIN/10 || (n== (unsigned) MIN/10 && c > (unsigned) MIN % 10))){
            n = MIN;
            break;
        }
        n = n*10 +c;
        ++str;
    }
    return sign > 0 ? n:-n;
}

int main(){
    const char* numstr="331";
    int num = StrtoDecInt(numstr);
    printf("number is : %d\n", num);
    return 0;
}

Interview Question: Find the deepest node in a binary tree

(1)
#include<iostream>
#include<queue>

using namespace std;

struct Node{
    int data;
	Node* left, *right;
    Node(){ data=-1; }
    Node(int value):data(value),left(nullptr),right(nullptr){}
};

class bst_tree{
public:
	bst_tree(){ root = nullptr; }
	void insert(int num) { insert(root, num); }
	Node *get_deepest_node(Node* );
	Node *getRoot();
private:
	Node* root;
    void insert(Node *&, int);
};

Node* bst_tree::get_deepest_node(Node* rt){
	if(rt==nullptr)
		return nullptr;
	queue qnode;
	qnode.push(rt);
	Node* tmp=nullptr;
	while(!qnode.empty()){
		tmp = qnode.front();
		qnode.pop();
		if(tmp->left) qnode.push(tmp->left);
		if(tmp->right) qnode.push(tmp->right);
	}
    			temp = temp->left;
		else
			temp = temp->right;
	}
	if(!q) q = new Node(num);
	else{
		if(num < prev->data)
			prev->left = new Node(num);
		else
			prev->right = new Node(num);
	}
}

Node* bst_tree::getRoot(){
    return root;
}

int main(){
	
	bst_tree bst;
	bst.insert(1);
	bst.insert(2);
	bst.insert(3);
	bst.insert(4);
        Node* tree_root = bst.getRoot();
        cout<<tree_root->data<<endl;
        Node* d = bst.get_deepest_node(tree_root);
        cout<<"the deepest node is :"<<d->data<<endl;
	return 0;
}
(2)
#include<iostream>
#include<queue>

using namespace std;

template <typename T>
struct Node{
	Node *leftchild, *rightchild;
	T data;
};

template <typename T>
class BinarySearchTree{
public:
    BinarySearchTree(){ rootNode=nullptr;};
    void insert(T);
	void search(T);
    Node* get_deepest_node(Node* );
private:


	Node *rootNode;
};

template<typename T>
void BinarySearchTree::insert(T newNum){
	cout<<"e;Insert: "e;<<newNum<<endl;
	Node *newNode = new Node;

	newNode->data = newNum;
	newNode->leftchild = newNode->rightchild = nullptr;

	Node * prev = nullptr;
	if(rootNode == nullptr)
		rootNode = newNode;
	else{
		Node *current =  rootNode;

		while(current){
			prev = current;
			if(newNode -> data <= current -> data)
				current = current -> leftchild;
			else
				current = current -> rightchild;
		}

		if(newNode -> data <= prev->data)
			prev -> leftchild = newNode;
		else
			prev -> rightchild = newNode;
	}
}

template<typename T>
void BinarySearchTree::search(T toFindNum){
	Node *current = rootNode;
//	Node *parent = rootNode;
	bool rootflag = false;
	if(current->data == toFindNum){
		rootflag = true;
		cout<<"e;Found the element, it is root."e;<<endl;
	}
    else{
    	while(current && current -> data != toFindNum){
    		//parent = current;
    		if(current -> data >= toFindNum)
    			current = current -> leftchild;
    		else
    			current = current -> rightchild;
    	}
    	if(current && !rootflag)
    		cout<<"Found the element!"<<endl;
        else
            cout<<"e;Couldn't find the element"e;<<endl;
    }
}

template<typename T>
Node* BinarySearchTree::get_deepest_node(Node* root){
    if(root==nullptr)
        return nullptr;
    queue*> qnode;
    qnode.push(root);
    
    Node* current;
    while(!qnode.empty()){
        current = qnode.front();
        qnode.pop();
        if(current->left) qnode.push(current->left);
        if(current->right) qnode.push(current->right);
    }
    return current;
}

int main(){
	BinarySearchTree b;
	b.insert(7);
        b.insert(5);
        b.insert(11);
	b.search(10);

	BinarySearchTree c;
	c.insert('k');
	c.search('v');

	return 0;
}