存档

‘笔试面试题’ 分类的存档

矩阵转置 O(1)空间

2013年7月12日 8 条评论

---

题目:用O(1)的空间实现矩阵的转置

为了方便,使用一维数组来分析。所谓矩阵转置,行变列,列变行。在转置的过程中,有的元素位置是不变的;对于变化位置的元素,要求O(1)空间完成,那么这些位置的变化一定是有着规律的。

举例,2×5的矩阵,A={0,1,2,3,4,5,6,7,8,9};转置后为AT={0,5,1,6,2,7,3,8,4,9},探索下标变化:

0->0

1->2->4->8->7->5->1

3->6->3

9->9

这些下标的变化是一些环,如果我们能找到这个环,对环做移动处理,就可以O(1)完成了。

现在的问题是,我们如何知道一个环是已经处理过的,仔细观察,如果一个环被处理过,那么总能找到一个它的后继是小于它的。例如,处理了前三个环的时候,当尝试找下标4打头的环时,一直找4的后继下标,会发现后继1是小于4的,我们就知道4是存在于一条已经处理过的环,跳过。

接下来的问题是如何找到当前元素下标的前驱和后继。先求下标i转置前的下标,即i的前驱,对于m×n的矩阵,转置后为n×m,则一维数组的第i个元素表示的行列为(i/m, i%m),根据转置原理,那么这个元素在转置前的m×n矩阵中所表示的行列为(i%m, i/m),那么i在转置前一维数组中的位置为j=(i%m)×n+(i/m)。同理,下标i转置后的位置j=(i%n)×m+(i/n)。

这样,前驱后继都可以求得,找到环就移动环的元素,如果已处理过则跳过,代码如下

阅读全文...

Twitter online 两题

2013年6月15日 7 条评论

---

今天有个群里发了两道twitter online的题目,看了下,练手写一下。

题一:

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0..N−1]. Sets S[K] for 0 ≤ K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. Sets S[K] are finite for each K.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the size of the largest set S[K] for this array. The function should return 0 if the array is empty.

阅读全文...

再谈数字序列和为0

2013年5月8日 4 条评论

---

之前研究过一道微策略的笔试题-数字序列和为零,当时采用DFS做的,深感别扭,后来在Tutu_Lux的帮助下,得到一个不错的方案,思路简单,说白了就是暴搜,但实现巧妙,代码灰常漂亮。感谢Tutu_Lux

先说一下大致思路,然后贴代码,之后分析代码中的各个函数,实现充分展现了Tutu_Lux扎实的基本功和灵动的脑瓜子,哈,:-) 。

思路:

  1. 由于N是从3至9的范围,解决方案就是针对每个N的取值,先计算三个分隔符“_ + -”填入序列1-N的所有可能组合的情况总数
  2. 设置所有情况的组合序列(采用3进制的思想,即set函数)
  3. 对每种组合计算表达式值,如果为0则输出(利用栈&状态机,calculate函数)

代码如下:

阅读全文...

IP地址字符串转无符号整型uint—自动机思想【小米、腾讯面试题】

2013年5月6日 4 条评论

---

题:写一个把字符串的IP地址变成32位整数的函数,要求考察程序健壮性。

这个很能考察眼高手低的问题;如果考虑程序健壮性,有很多的非法情况需要考虑,稍有不慎就会有欠考虑的情况;如不考虑非法情况,转换的过程无非就是分解整数,合并这两步;只需两句代码就可以搞定,如下:


sscanf(ipstr, "%d.%d.%d.%d", &a, &b, &c, &d);

return (a<<24)|(b<<16)|(c<<8)|d;

但是考虑程序健壮性就没这么简单了,不过核心思想也就是上面的两句话,下面将各种错误情况定义成状态表,程序如下:

阅读全文...

小米面试题一道:N对括号所有的合法状态

2013年3月6日 15 条评论

---

给定N对括号,输出其所有的合法的组合状态,例如,N=3,所有的合法状态为:"((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路:还是深搜DFS的思路,深搜的过程关键在于记录已经用掉的左括号个数和右括号的个数,当用过的左括号个数小于右括号则非法;当二者个数和大于2N则非法;当二者个数相等且数目等于2N则为合法。

代码如下:

#include<iostream>
using namespace std;

#define PAIR 50

char str[PAIR * 2 + 1]; // 设括号对数不超过50, str记录括号组合状态

void DFS_bracket(int n, int left_used, int right_used)
{
	if(left_used == right_used && left_used + right_used == 2*n)
	{
		printf("%s\n",str);
		return;
	}
	if(left_used < right_used || left_used + right_used >= 2*n)
	{
		return ;
	}
	int index = left_used + right_used;
	str[index] = '(';
	DFS_bracket(n, left_used + 1, right_used);

	str[index] = ')';
	DFS_bracket(n, left_used, right_used + 1);
}

void main()
{
	int N;
	scanf("%d", &N);
	DFS_bracket(N,0,0);
}

阅读全文...

微策略笔试题一道:数字序列和为0

2013年3月5日 10 条评论

---

这道深搜的题目写的我心情好别扭,代码也感觉别扭。希望路过的爱动手的牛牛们指导,不管是代码还是思路方面的建议都行;/握手

题目:序列123...N,N介于3和9之间,在其中加入+、-或者空格,使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问,如何获得所有组合?

我代码的思路就是深搜,处理空格时复杂一些,具体参数见注释。

阅读全文...

兄弟单词 — 两种算法实现

2013年2月28日 2 条评论

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

阅读全文...

定长线段最多覆盖点的个数

2013年1月5日 2 条评论

---

来自之前百度一面的题目:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

题目不难,但也不是太容易想出来,两个指针前后跑的思路:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。

阅读全文...

二分查找,你真的会吗?

2012年10月6日 19 条评论

---

面试常让写二分查找或其扩展的程序,以前总觉得很简单,但是真动手写起来,细节很多,容易出错的地方也很多,真是秒杀眼高手低的利器,本节就二分查找以及相关扩展程序都实现一下,同时将可能出错的地方以及需要注意的细节也一并说明,水平有限,欢迎补充。

内容如下:

1)二分查找元素key的下标,如无 return -1

2)二分查找返回key(可能有重复)第一次出现的下标,如无return -1

3)二分查找返回key(可能有重复)最后一次出现的下标,如无return -1

4)二分查找返回刚好小于key的元素下标,如无return -1

5)二分查找返回刚好大于key的元素下标,如无return -1

注:以上所有问题可能出错的地方以及需要注意的细节说明在代码注释中。

直接上代码:

阅读全文...