某大厂的面试许可证

算法 admin 190℃ 0评论

题目:

剧场随机选座,ABCD4个区,中间过道分开,随机选1-5个位置,写出核心算法

这里我用php写一个初级版本,基本能用,但性能和功能的优化还有很多工作可以作,感觉水深

<?php
 /**
  * 思路:先初始化数组
  * 优先选择中间两个区靠前的票(先购者得到好的票)
  * 如果选取多个,应该尽量连续 (坐位在一起)
  * 选取到最后无法连续才随机给出座位
  *
  * 思路可优化部分:
  * 无连续选取时,应先选取较好座位
  * 单人位应选取最小剩余座位,保证不影响其它人选取连续座位(利益最大化)
  * 并发控制,避免选取到同一个痤位
  */
header("Content-type:text/html;charset=utf-8");
$seats = array();

$area = ['A', 'B', 'C', 'D'];

$MAX_ROW = (100-50)/2+1;

$index = array(); //初始化索引数组
foreach($area as $u){
    for($i=0; $i<$MAX_ROW; $i++){
        $MAX_COLUMN = 50+$i*2;

        $index[$u][$i] = array(
            'least' =>  $MAX_COLUMN,
        );

        for($j=0; $j<$MAX_COLUMN; $j++){
            $seats[$u][$i][$j] = 0;
        }
    }
}

function select($num, $u, $i){
    global $seats, $area, $MAX_ROW, $index;
    $choose = array(
        'num' => 0,
        'seats' => array(),
    );
    $least = $index[$u][$i]['least'];
    if($least>=$num){
        $MAX_COLUMN = 50+$i*2;
        for($j=$MAX_COLUMN-$least; $j<$MAX_COLUMN; $j++){
            if(!$seats[$u][$i][$j]){
                $seats[$u][$i][$j] = 1;
                $choose['seats'][] = "area:$u|row:$i|col:$j";
                $index[$u][$i]['least']--;
                $choose['num']++;
                if($choose['num'] == $num){
                    break;
                }
            }
        }
    }
    return $choose;
}

function select_least($num, $u, $i){
    global $seats, $area, $MAX_ROW, $index;
    $choose = array(
        'num' => 0,
        'seats' => array(),
    );
    $least = $index[$u][$i]['least'];
    if($least>=0){
        $MAX_COLUMN = 50+$i*2;
        for($j=$MAX_COLUMN-$least; $j<$MAX_COLUMN; $j++){
            if(!$seats[$u][$i][$j]){
                $seats[$u][$i][$j] = 1;
                $choose['seats'][] = "area:$u|row:$i|col:$j";
                $index[$u][$i]['least']--;
                $choose['num']++;
                if($choose['num'] == $num){
                    break;
                }
            }
        }
    }
    return $choose;
}

function chose($num){
    global $seats, $area, $MAX_ROW, $index;

    if($num > 5 || $num < 1){
        die('you should enter 1-5');
    }

    $choose = array(
        'num' => 0,
    );
    $good_row = 10;
    $good_area = ['B', 'C'];

    //先取中间两个区,并且前10排比较好的区域
    foreach($area as $u){
        if(in_array($u, $good_area)){
            for($i=0; $i<$good_row; $i++){
                $choose = select($num, $u, $i);
                if($choose['num'] == $num){
                    break 2;
                }
            }
        }
    }

    foreach($area as $u){
        if(in_array($u, $good_area)){
            for($i=$good_row; $i<$MAX_ROW; $i++){
                $choose = select($num, $u, $i);
                if($choose['num'] == $num){
                    break 2;
                }
            }
        }

        if(!in_array($u, $good_area)){
            for($i=0; $i<$MAX_ROW; $i++){
                $choose = select($num, $u, $i);
                if($choose['num'] == $num){
                    break 2;
                }
            }
        }
    }

    //没有连续座位或者无座位了
    if(!$choose['num']){
        //无座位(选1个位的时候)
        if($num == 1) {
            die('seats empty!');
        } else {
            //无连续座位(选取多个位的时候),此时随机分配座位
            foreach($area as $u){
                for($i=0; $i<$MAX_ROW; $i++){
                    $choose = select_least($num, $u, $i);

                    if($choose['num'] > 0){
                        $num = $num - $choose['num'];
                        if($num == 0){
                            break 2;
                        }
                    } 
                }
            }
        }

    }
    return $choose['seats'];
}





function show($seats){
    global $area,$MAX_ROW;
    foreach($area as $u){
        echo "$u<br>";
        for($i=0; $i<$MAX_ROW; $i++){
            echo str_repeat('&nbsp;&nbsp;&nbsp;', $MAX_ROW-$i);
            $MAX_COLUMN = 50+2*$i;
            for($j=0; $j<$MAX_COLUMN; $j++){
                echo $seats[$u][$i][$j] . '|';
            }
            echo '<br>';
        }
        echo '<hr>';
    }
}

for($i=0;$i<1294;$i++){
    chose(5);
}
show($seats);

 

补充:

后面和面试官沟通,我这思路完全错了,题目只需要体现出随机就行,于是我再进行思路描述

  1. ABCD4个区是一样的,所以先考虑一个区
  2. 座位座标的关系为 a[i][j], a为26*100的数组,每行的最后一个座位标号为50+2i
  3. 确保随机出座是边座,每次随机为(1-5)个座位
  4. 根据可选集合进行随机(可选集合即动态选出可随机的座位可能集合)

最终核心思路为:

  1. 用户传入座位数
  2. 根据座位数筛选出随机可选集合(座位数为8000不到,集合会小于这个数)
  3. 随机从可选集合中选取一个元素

步骤2核心代码为:

$allow_seats = array();
for($i=0; $i<$MAX_ROW; $i++){
    for($j=0; $j<$MAX_COLUMN; $j++){
        if($a[$i][$j] == 0){
            $pass = true;//检查后面的连座是否可用

            $temp = array($a[$i][$j]);//存放选取结果
            for($k=1; $k<$num; $k++){
                //关键:边界判断, 每排最后一个位置为50+2i-1
                if(($a[$i][$j+$k]  != 0) || ($j+$k == 50+2*$i-1)){
                    $pass = false;
                    break;
                } else {
                    $temp[] = $a[$i][$j+$k];
                }
            }
            if($pass){
                $allow_seats[] = $temp;
            }
        }
    }
}

 

转载请注明:朋克网 » 某大厂的面试许可证

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址