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;

}

Ubuntu 中文输入法安装 ibus

Ubtuntu 12.04 中自带了中文输入法，在英文系统中同样已经预装了ibus，只需要下载一下简体中文语言包，即可通过Ctrl+Space进行输入法到切换。

如何安装简体中文语言包？
依次选择 Sytem Setting --> Language Support --> Install/Remove Languages后，将出现如下图所示窗口：

将右侧 Installed 栏的选择框勾选后，单击按钮 Apply Changes，之后会要求你输入密码，输入完成之后，系统将会自动下载并安装简体中文语言包。

一般情况下Ubuntu12.04中已经预装了ibus，如果你在进行下一步的时候提示了错误，在终端输入以下指令安装一些必须的库文件：

1	sudo apt-get install ibus ibus-clutter ibus-gtk ibus-gtk3 ibus-qt4

如何设置ibus框架？
设置ibus框架请在终端输入以下指令：

1	im-switch -s ibus

完成以上步骤后建议注销系统（亲测12.04 时未注销也可正常执行后面步骤，如果后面步骤无效，请尝试注销）

如何安装拼音引擎？
在Ubuntu12.04中已默认安装拼音引擎，如果你在进行下一步的时候未发现拼音（或其它）选项，请在终端输入以下相关指令：

1	ibus拼音：      sudo apt-get install ibus-pinyin

2	ibug五笔：      sudo apt-get install ibus-table-wubi

3	谷歌拼音输入法： sudo apt-get install ibus-googlepinyin

4	Sun拼音输入法：  sudo apt-get install ibus-sunpinyin

如何启动ibus框架？
启动ibus框架请在终端输入以下指令：

1	ibus-setup

此时，IBus Preferences 设置会打开，可能会提示监控程序未启动，单击 Yes 即可，切换至 Input Method 选项卡中，选择自己喜欢的输入方式，并可自定义切换快捷键，界面应当大致如下图：

通常情况下，ibus图标（一个小键盘）会出现在右上角的任务栏中，大致如下图所示：

有时候它会开个小差跑出去玩，可以通过在终端输入以下指令叫它回家吃饭：

1	ibus-daemon -drx

更多细节设置可自行研究，全都在ibus的设置面板里。

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

http://hyperrate.com/thread.php?tid=28044

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;
}