一些前端问题以及我的一点答案

1．某产品页面左侧的边栏是一个允许用户自定义宽度（240-420像素）的div容器，现在设计师考虑在容器内放置一个8 X 8格的国际象棋棋盘，棋盘的总宽度是一个偶数，而同时，为了良好的视觉效果，必须保证容器两边所留的空白宽度相同。于是，Web前端开发工程师A现在面临 一个难题了，那就是如果用户设置的容器宽度为奇数，必须在页面渲染的时候，将它的实际宽度减少一个像素变为一个偶数。仔细考虑之后，A决定用他所精通的 JavaScript来实现一个函数f，这个函数的参数是一个正整数，返回值是一个最接近且不大于这个正整数的偶数，例如f(240)返回 240，f(311)返回310。A很快写出了这个函数：

 

function f(n){
 if(n % 2) return n-1;
 return n;
}

 

当A的同事C仔细研究了这个函数之后，指出其实还有更高效率的写法。

(1.a) 问题：如果您是C，您将如何改良这个函数呢？


2．在休息室里，A给大家讲了一道经典的微软面试题，题目是这样的：对于给定的一个字节表示的无符号整数，求将它表示成二进制之后，“1”出现的次数。例如5=101(2)->2，11=1011(2)->3……C说这道题很容易，只需要用一个简单的function就能实现：

 

function (n){
 if(typeof n != “number” || n <= 0) return 0;
 var count = 0;
 while(n){
  count += n & 0x1;
  n >>= 1
 }
 return count;
}

 

当C写出他的答案之后，A说，是的，这是解法之一，不过这样的效率仍然不够高，实际上我有更高效率的解法：

function (n){
 if(typeof n != “number” || n <= 0) return 0;
 var count = 0;
 while(n){
   n &=  (n-1);
  count++;
 }
 return count;
}

 

(2.a) 问题：为什么A说自己的解法效率比C的解法要高？

C看了A的解法，说道，这个办法确实高明。A说，针对这道题其实还有其他解法，比如查表法，因为只有8位，所以是可以考虑的，当然位数多了的话，查表法就不适合了。这时候，C忽然想到了什么，对A说，我想到了一种JavaScript特有的解法，不用循环，多于8位也适用，效率还比较高。

(2.b) 问题：请问您想到类似这样的解法了吗？请给出您的解题思路。

 


3．让页面元素可拖动是一种常用脚本实现的交互方式。基本的拖动是用鼠标点住某个元素在一个特定的可见区域内移动。现在A遇到的一个问题是在可拖动区域内有一个椭圆形的禁区，如下所示：

    ------------------------------------------------------
    可拖动区域

                                                      
                                           （椭圆禁区）


                                             
    -------------------------------------------------------
 
已知禁区的外接矩形的左上角坐标为（left，top）、宽高为（width，height）。A打算写个函数，用来判断鼠标是否位于禁区内。

(3.a) 问题：这个函数该如何实现呢？

C提醒A说这个交互比想象中复杂，需要考虑很多细节问题。

(3.b) 问题：如果您是A，实际要实现这个交互，您认为需要考虑哪些细节问题？

 


4．糊涂的A不小心把一个设计好的页面弄乱了，现在这个页面上有若干绝对定位的div，这些div有确定的左上角（top、left）和宽高 （width、height），页面初始化后，这些div的位置有可能重叠（如果两个div有任意部分相交，就认为这两个div重叠）。
 
这种界面被人看到可就惨了，然而弄乱的div数量如此之多，A不得不用JavaScript实现一个function，这个function检查页面上所 有绝对定位的div，输出一个包含重叠的div组合的数组。（如果DIV1与DIV2相交、DIV3、DIV4、DIV5两两相交、DIV6与DIV7相 交，那么输出结果为[[DIV1,DIV2],[DIV3,DIV4,DIV5],[DIV6,DIV7]]）

(4.a) 问题：如果您是A，您将怎样实现这个function？

 


5．设计师交给A去实现一个布局，这个布局由三列等高的区域组成，左栏的宽度为40%-102px，中栏的宽度为200px，右栏的宽度为60%-102px。左中栏、右中栏之间的间隔均为2px。

一开始A觉得实现这样的布局根本不用花费什么功夫，可是具体实现的时候，却发现远没有想象中那么简单。Web标准、浏览器兼容性……各种需要考虑的细节都让A觉得自己陷入了麻烦之中。

(5.a) 问题：如果您是A，您将怎样实现这个布局？

 


6．请回顾您以往经历过的前端开发项目，谈谈您认为最能体现您前端开发水平的精彩部分。



我的一点答案：(欢迎斧正 )

 

1.a : 在传统语言中 可以用位操作提高效率：

function f(n) {
  return n&1?n-1:n;
}

 

但是对于javascript，没有整数类型只有浮点类型，位操作也提高不了效率的，但是我想不到其他方法了。
引擎会对二进制进行优化的，二进制操作引擎内部使用整数直接位运算！

2.a : 1. A 的算法每次循环只执行一次位操作，C的算法每次执行两次位操作。
2. A 算法 很快可以使 n 收敛到 0 ，循环次数为 n 二进制中1的个数，C的算法 循环次数为 n 的位数 。
总结：假设n 二进制 1的个数为 m ，总的位数为 x ，x > m ,则
A的算法执行 m 次位操作，C的算法执行 2x 次位操作。

2.b : Number 有 本地方法 toString(radix) ,
1.本地方法更快
2.字符串比数值运算（尤其javascript中的位运算 ）快

可得以下方法：

function f(n) {
   if(typeof n != "number" || n <= 0) return 0;
   var n_str=n.toString(2);
   var count=0;
   for(var i=0;i<n_str.length;i++) 
      if(n_str.charAt(i)=='1') count++;
    return count;      
}

 

Java中Number也有toString ，但是toString 也是用 java 实现的，这种情况下 java不适合这种方法，但是javascript作为解释性语言，本地方法效率不容置疑。

ps:在编程之美（Beautiful Code）第十章种群计数（Population Count） 中提出了1位记数的分治策略算法，可以在 log2 (N) (N为整数二进制的位数)内得到答案：

 

相当于合并排序，从底向上直到总体完成，只不过这里每一小步都是可以利用二进制＋并行完成的！

 

示意图：

 

 

代码：

 

/*
				计算 x 中 1的个数
				*/
				function popOne(x){
						x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
						x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
						x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
						x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
						x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
						return x;
				}

 

扩展：Counting the 1-Bits in an Array

 

目前最优解法：

1.首先 三个数 a,b,c 的所有1个数 popOne(a) +popOne(b) +popOne(c)

 

a有9个1,b 有6个1,c有8个1，h有7个1，l有9个1，则 9+6+8==7*2+9

其中算 a + b+ c的二进制结果表示 ,l表示二进制相加每位结果的低位 ,h表示二进制相加每位结果的高位位

h ← ab + ac + bc = ab + (a + b)c = ab + (a ⊕ b)c
l  ← (a ⊕ b) ⊕ c

ps:关于上述逻辑表达式的推导

需要一点数字逻辑的基础。

1.首先画出真值表 :

2.写出最小项表示的与或表达式

h=a bc + ab c + abc + abc

3.画出卡诺图

 

4.写出最简逻辑表达式

h=ab+ac+bc

同理推出 l ,注意 a ⊕ b = a b+ab

l= a ⊕ b ⊕ c

5.多输出最简推导

多个输出的表达式要不同的最小项最少

h=ab+(a+b)c=ab+( a ⊕ b )c

l=( a ⊕ b ) ⊕ c

需要5个门电路，5步运算即可。

 

 

 

 

 

 

 

 

/*
				计算 a + b+ c的二进制结果表示.
				
				@return 
				l表示二进制相加每位结果的低位
				h表示二进制相加每位结果的高位位
				*/
				function CSA(a,b,c){
					var u = a ^ b; 
					var v = c; 
					h = (a & b) | (u & v); 
					l = u ^ v;
					return {
						h:h,
						l:l
					}
				}

 

2.则 对一个数字中的每两个数加上前一步的低位结果算一下，累进可得数组中所有结果的1个数

	/*
					计算整数数组中所有数字包含 1 个数
				*/
				function popArray(A){
					var n=A.length;
					var  tot = 0,ones = 0;
					var twos=0; 
					for (var i = 0; i <= n - 2; i = i + 2) {
					var step=CSA(ones, A[i], A[i+1]) ;
					//获得高位
					twos=step.h;
					//获得低位
					ones=step.l;
					//高位立即加，低位累进
					tot = tot + popOne(twos);
					} 
					//注意所有高位的要 *2
					tot = 2*tot + popOne(ones); 
					// If there's a last one, 
					// add it in.
					if (n & 1)
					tot = tot + popOne(A[i]); 
					return tot;
					
				}

 

演示 @ google code

3.a b: 拖放实现的几个要点：

1. 定义一个拖放对象 A
2.监控 A 的 onmousedown 事件 ，记录当前拖放对象，拖放开始
3.当拖放开始时 ，监控 document 的 onmousemove  onmouseup 事件
4. 当 onmousemove  事件触发时 ，将当前事件的坐标位置改变当前拖放对象的位置
5. 当 onmouseup 事件触发时 ，取消监控document的 onmousemove onmouseup 事件

对于禁区案例，需要 则需要 在 onmousemove 事件触发式 ，随时判断当前拖放对象的边界是否接触到了禁区边界，接触的话就停止更新拖放对象的位置。
细节包括：ie，ff 鼠标位置计算的差异 ，鼠标在拖放对象的位置要固定
对于此案例，还要考虑，椭圆区域公式，而不应简单考虑矩形区域。


4.a : 题目不是很明白，如果 div1 和 div2 相交 ，div2 和 div3 相交，div1 和 div3 不相交，那应该输出什么？我这个程序输出 [ [div1 ,div2 ,div3] ] 了。

直接贴代码了，这个应该属于聚类问题，蛮麻烦的，代码不保证完全正确，只体现基本思路。（将一堆div聚成几类，每一类）

/**
  修改自 Ext.lib.Region ,详见 Extjs ext-base.js 1192行
**/

//判断两个绝对定位的div是否相交
function isCross(div1,div2) {
   var region1={
       top:div1,style.top,
       left:div1.style.left,
       bottom:div1.style.top+div1.style.height,
       right:div1.style.left+div1.style.width

    };
   
    var region2={
       top:div2,style.top,
       left:div2.style.left,
       bottom:div2.style.top+div2.style.height,
       right:div2.style.left+div2.style.width

    };
   
    var t = Math.max(region2.top, region1.top);
    var r = Math.min(region2.right, region1.right);
    var b = Math.min(region2.bottom, region1.bottom);
    var l = Math.max(region2.left, region1.left);

    if (b >= t && r >= l) return true
    else return false; 
}

//divs 为所有的绝对定位的div

//基本思想是 对每个div 把它归类到它相交的一组div

function getAllCrosses(divs) {
    //每个div所属的组
    var already={};
   
    //所有相交div集合的数组
    var result=[];
   
    for(var j=0;j<divs.length;j++) {
               
        //所有和div j 相交的 div ,div j  是否已经属于一个分组
        var subresult=already[j] || [divs[j]];
       
        for(var i=j+1;i<divs.length;i++) {
           
            //i 和 j相交了。
            if(isCross(divs[j],divs[i])) {
                subresult.push(divs[i]);               
                //把i归到这个分组去
                already[i]=subresult;
            }
        }
       
        //如果找和 j 相交的 div
        //并且 如果 j 所属的分组没有被添加到最终集合过。
        if(!already[j] && subresult.length!=1) {
            result.push(subresult);
        }
       
    }
   
    return result;
   
}

 

5.a : 涉及到 css 的列布局部分，详见：css 列布局

 

兼容 gecko,ie6,7,webkit

 

效果：

 

演示@google code

 

答案：

 

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
	"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<title>
			baidu layout
		</title>
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
		<link rel="stylesheet" type="text/css" href="../../base/css/core.css" />
		<style type="text/css">
/*<![CDATA[*/

		/*all hack for ie,shit*/

		#wrap {
		width:95%;
		margin:0 auto;
		}

		#container {
		width: 100%;/*if no ,footer 在ie6消失*/
		overflow:hidden; /*所有浏览器列背景会突破*/
		position:relative; /* ie6,7列背景会突破*/
		}

		h1 {
			font-size:30px;
		}

		.eqCol {  /*无限高列配置*/
			margin-bottom:-10000px;
			padding-bottom: 10000px;
		}

		.col {  /*负边距 + 相对定位 固定列位置*/
			float: left; margin-left: -100%; position: relative; display:inline;
		}

		/*]]>*/
		</style>
	</head>
	<body>
		<div id="wrap">
			<h1 style="text-align:center;">
				center:200px;<br />
				left:40%-102px;<br />
				right:60%-102px;
			</h1>
			<div id="container" class="clearfix">
				<div class="eqCol col" style="width:40%; left: 100%;">
					<div class="eqCol" style="background: black; margin-right: 102px; color: white;">
						left<br />
						left<br />
					</div>
				</div>
				<div class="eqCol col" style="width:60%; left: 140%;">
					<div class="eqCol" style="background: green;margin-left: 102px;">
						right<br />
						right<br />
						right<br />
						right<br />
						right<br />
						right<br />
						right<br />
						right<br />
						right<br />
					</div>
				</div>
				<div class="eqCol col" style="width:200px; background: red; left: 40%; margin-left: -100px;">
					center<br />
					center<br />
					center<br />
					center<br />
					center<br />
					center<br />
				</div>
			</div>
			<div id="footer" style="border:1px solid purple;">
				This is the footer.
			</div>
		</div>
	</body>
</html>

 

 

 

 

 

 

评论

3 楼 liuhuiashazj 2009-06-13  

收到面试通知了吗？

2 楼 yiminghe 2009-06-08  

liuhuiashazj 写道

你答得真好

我觉得不是很好啊，很多都是模模糊糊，具体答案我也搞不是很清楚

1 楼 liuhuiashazj 2009-06-08  

你答得真好