• 打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮
  • 打赏支付宝扫一扫

首页

 > 

设计架构 > 

数据结构

答与微博前端教主在吃饭时讨论到的一道微软面试题

winter-cnwinter-cn • 6年前

加引号是因为我不知道是否真是微软面试题。题目是这样的:

 

有一车在某无限长公路上行驶,其起始位置和单位时间内速度均为有限大整数(正负不确定), 现有一仪器,在每一时间单位内可以探测1次车是否在指定位置,求一方法能在有限时间内求出车的速度和初始位置。

 

答曰:

解此题目分为两个步骤,第一个步骤,探测到车一次

第二个步骤,求出车的速度和位移。

 

先解答第一步骤,

 

显然,假设车位移为s,速度为v,在时间t时车的位置必定为 s+v*t

 

现在我在时间t时,可以对<s,v>值做出一次猜测<x,y>,然后探测位置 x+y*t,若这个位置有车,则第一步骤得解,若这个位置无车,则必定说明猜测<x,y>是不正确的,即可以排除解<x,y>

 

所以现在我们要构造一个序列 <x(t),y(t)>,使得对于任意的<s,v>取值,总有有限大的t使得 <x(t),y(t)> 值为 <s,v>,此问题之几何意义为将平面中的所有点映射到一个序列,下面给出其中一种最容易编程实现的解。(吃饭时我说的是螺旋形映射,但是想来似乎不如菱形映射容易编程实现)

假设s与v绝对值之和为m,则m必定有限,现在可以用以下代码所示算法检测:

var t = 0;
for(var m = 0; m < Infinity; m++) {

    for(var x = 0; x <= m; x++) {
         var y = m - x;

         if(check(x+y*(t++))) {
             break;
         }
         if(check(x+(-y)*(t++))) {
             break;
         }
         if(check((-x)+y*(t++))) {
             break;
         } 
         if(check((-x)+(-y)*(t++))) {
             break;
         } 

    } 

}  
//我知道你们看完代码肯定想揍我,没错,前面那一堆废话其实说的就是这么简单的事情......

第二个步骤,

因为第一步骤的假设<x,y>并非位置的必要条件,所以无法反过来得出探测命中车之后<s,v>必定为<x,y>。但是我们知道车的现在位置之后,可以车之速度为x,依0,1,-1,2,-2,3,-3......这样的序列依次猜测,第二次命中即可得到速度v。

由速度又可以算出初始位置s 

 

 

“看完这篇还不够?如果你也在学习IT,并希望记录自己的成长日志,请戳这里告诉我们!”
新人作者

好好学习,天天向上,有工作有兼职可以找我。微信号:gethost

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
参与讨论
后参与讨论
winter-cn
新人作者

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
48h快讯7天最热月榜More
  • 7年前

    Dijkstra算法(单源最短路径)单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。一.最短路径的最优子结构性质该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路
    收起
  • 7年前

    二叉树的非递归遍历二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照根结点-左孩子-右孩子的顺序进行访问。1.递归实现voi
    收起
  • 7年前

    淘宝名词解释产品和商品的区别:淘宝标准化产品,由类目+关键属性唯一确定。如:手机类目,关键属性是品牌和型号,NokiaN95就是一个产品,nokia是品牌,N95是型号。产品除了关键属性还包括一般信息、销售属性和非关键属性。参考:如"诺基亚N95"就是一个产品。通过类目的关键属性组合来确定唯一的产品。后台标准类目叶子节点下,一组共同特征商品的组合(例如:化妆品+雅芳+保湿单品+容量),属于同一个产品的商品可以认为对消费者的效用及使用感受是没有差别的。产品这个概念对淘宝这种C2
    收起
  • 5年前

    队列特性:先进先出(FIFO)先进队列的元素先出队列。来源于我们生活中的队列(先排队的先办完事)。队列有下面几个操作:InitQueue()  初始化队列EnQueue()进队列DeQueue()出队列IsQueueEmpty()判断队列是否为空IsQueueFull()判断队列是否已满队列可以由数组和链表两种形式实现队列操作(c语言),下面仅以数组为例:数组实现:队列数据结构typedefstructqueue
    收起
  • 7年前

    前言那个啥前面发了2篇文章讲这个商品表的设计,后面越多需求浮出水面才发现设计依旧有问题,好吧,乐观一点,正如我博客的标题一样,我在进化^_^为什么要这样设计先说几个需求,看看您现在是如何去实现:一个用户来到我们网站,在前台页面,1.他要买洗发水,他进入了洗发水的类别,他想买带去屑止痒功效的500ml的洗发水,能否直接搜索出来所有品牌带这个功效属性是500ml的洗发水2.接着他要买一件T恤,他想买V领,短袖的T恤,能否直接通过2个属性搜索出所有品牌的T恤展示给他3.他
    收起
  • 9年前

    1、反转一个链表。循环算法。1Listreverse(Listl){2if(!l)returnl;3listcur=l.next;4listpre=l;5listtmp;6pre.next=null;7while(cur){8tmp=cur;9cur=cur.ne
    收起
  • 7年前

    图的遍历图的遍历有两种遍历方式:深度优先遍历(depth-firstsearch)和广度优先遍历(breadth-firstsearch)。1.深度优先遍历基本思想:首先从图中某个顶点v0出发,访问此顶点,然后依次从v0相邻的顶点出发深度优先遍历,直至图中所有与v0路径相通的顶点都被访问了;若此时尚有顶点未被访问,则从中选一个顶点作为起始点,重复上述过程,直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。如下图中的一个无向图其深度优先遍历得到的序
    收起
  • 7年前

    1:原理以此比较相邻的两个元素,每次比较完毕最大的一个字跑到本轮的末尾。目的:按从小到大排序。方法:假设存在数组:72,54,59,30,31,78,2,77,82,72第一轮比较相邻两个元素,如果左边元素大于右边元素,则交换。72和54比较的结果就是,54在前,72在后;然后72和59比较的结果,59在前,72在后;以此类推,第一轮比较之后的结果是:54,59,30,31,72,2,77,78,72,82经过第一轮比较,最大的元素跑到了最
    收起
  • 9年前

    CodehighlightingproducedbyActiproCodeHighlighter(freeware)http://www.CodeHighlighter.com/-->/*冒泡排序基本思想将n个记录看作按纵向排列,每趟排序时自下至上对每对相邻记录进行比较,若次序不符合要求(逆序)就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置,整个排序过程共进行n-1趟,依次将关键字最小、次小、第三小的各个记录冒到表的第一个、第二个、第三个位置
    收起