Tag Archives: 面试

求从1到n中1出现的次数

题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

编程之美上的原题。

基本思路1：

每次判断各位是否为1，计数。然后依次/=10即可。

时间复杂度O(N*lgN)

#include <stdio.h>

int countone(int num)
{
	int cnt = 0;
	while(num)
	{
		if(num%10==1)
		{
			cnt++;
		}
		num/=10;
	}
	return cnt;
}

int countone_all(int n)
{
	int sum = 0;
	int i;
	for(i=1;i<=n;i++)
	{
		sum += countone(i);
	}
	return sum;
}

int main()
{
	int n = 12;
	printf("%d\n", countone_all(n));
	return 0;
}

#include <stdio.h>

int countone(int num)

{

int cnt = 0;

while(num)

{

if(num%10==1)

{

cnt++;

}

num/=10;

}

return cnt;

}

int countone_all(int n)

{

int sum = 0;

int i;

for(i=1;i<=n;i++)

{

sum += countone(i);

}

return sum;

}

int main()

{

int n = 12;

printf("%d\n", countone_all(n));

return 0;

}

思路2：

可以用归纳法搞出一个递推公式。

但是如书上所述，这个递推公式是有范围限制的，n最大为11111111[……]

继续阅读

求单向链表倒数第 k 个结点

Leave a reply

题目：输入一个单向链表，输出该链表中倒数第 k 个结点。

传统做法是获取到链表的长度n，然后走n-k布，此方法弱爆了……

做法：

1、指定一个新的指针，走k步。如果k布之内就到了NULL，显然无倒数第k这说法，返回错误即可。

2、新指针到位后，和root一起next，知道新指针到了NULL。此时输出root指针当前的data即可。

int ll_last_k(struct Node* root, int k)
{
	// Make two ptr diff k distance
	struct Node* ptr = root;
	for(int i=0;i<k;i++)
	{
		if(ptr==NULL)
		{
			return -1;
		}
		ptr = ptr->next;
	}
	// Both next
	while(ptr!=NULL)
	{
		ptr = ptr->next;
		root = root->next;
	}
	return root->data;
}

int ll_last_k(struct Node* root, int k)

{

// Make two ptr diff k distance

struct Node* ptr = root;

for(int i=0;i<k;i++)

{

if(ptr==NULL)

{

return -1;

}

ptr = ptr->next;

}

// Both next

while(ptr!=NULL)

{

ptr = ptr->next;

root = root->next;

}

return root->data;

}

[……]

继续阅读

大量数据取k个最大值并排序

1 Reply

需求是这样的，我们都知道，在信息检索中，经常要取top-k(一共k，而不是第k)个得分最大的文档，并且从大到小排序。

而且文档规模很大，最少也要上千万。

话说这是一道很可以拿来面试的题啊。

我们不考虑Hadoop神马的，就说说单机怎么搞。

最傻的做法就是把1000万个都存储下来，然后sort，然后取min(k, vec.size())。

这样有两个缺点：
1、内存占用非常大，其实我们只要保留最大的1000个，但这样就要保存N个。在1000万的测试中，它要占用68M[……]

继续阅读

Protected: 百度实习面

Enter your password to view comments.

两道面试题……

Leave a reply

传说百度面试题，都是字符串处理的……我目前这水平也就做这种水题了，下午莫名其妙被面试，坐等被虐了。

1、反转字符串单词。
输入I am coder4
输出coder4 am i

#include <iostream>
#include <vector>
#include <sstream>
using std::endl;
using std::cout;
using std::istringstream;
using std::vector;
using std::string;

int main()
{
	vector<string> vec;
	istringstream iss("I am Jack Chen");

	string part;
	while(iss>>part)
	{
		vec.push_back(part);
	}

	for(int i = vec.size()-1; i>=0; i--)
	{
		cout<<vec[i]<<" ";
	}
	cout<<endl;
}

#include <iostream>

#include <vector>

#include <sstream>

using std::endl;

using std::cout;

using std::istringstream;

using std::vector;

using std::string;

int main()

{

vector<string> vec;

istringstream iss("I am Jack Chen");

string part;

while(iss>>part)

{

vec.push_back(part);

}

for(int i = vec.size()-1; i>=0; i--)

{

cout<<vec[i]<<" ";

}

cout<<endl;

}

2、将string形式的浮点数转化成double/float，只允许一次遍历。
输入:123.456(string)
输出:123.456(double/float)

#include <iostream>
#include <string>
using std::ios;
using std::cout;
using std::endl;
using std::string;

int main()
{
	string str("11111.222");

	bool dn = true;
	double part1 = 0, part2 = 0;
	double tmp = 1;
	for(int i=0;i<str.length();i++)
	{
		if(str[i]=='.')
		{
			dn = false;
			continue;
		}

		if(dn)
		{
			part1 *= 10;
			part1 += (str[i] - '0');
		}
		else
		{
			tmp/=10;
			part2 += (str[i] - '0')* tmp;
		}
	}
	cout.precision(str.length() - 1);
	cout<<(part1 + part2)<<endl;

}

#include <iostream>

#include <string>

using std::ios;

using std::cout;

using std::endl;

using std::string;

int main()

{

string str("11111.222");

bool dn = true;

double part1 = 0, part2 = 0;

double tmp = 1;

for(int i=0;i<str.length();i++)

{

if(str[i]=='.')

{

dn = false;

continue;

}

if(dn)

{

part1 *= 10;

part1 += (str[i] - '0');

}

else

{

tmp/=10;

part2 += (str[i] - '0')* tmp;

}

cout.precision(str.length() - 1);

cout<<(part1 + part2)<<endl;

}

[……]

继续阅读

四号程序员

Keep It Simple and Stupid

Tag Archives: 面试

求从1到n中1出现的次数

求单向链表倒数第 k 个结点

大量数据取k个最大值并排序

Protected: 百度实习面

两道面试题……