面试算法题实例

以下算法题都是我秋招和实习在面试当中实际遇到的题目。

美团搜索

  • 给一个数组，求前 k 大的元素
  • 二分查找

触宝科技

  • 使用+，-，*，/,() 判断 4 个正整数是否可以算出 24 点 
#include <iostream>
#include <vector>
using namespace std;


bool helper2(vector<int>& v,int i,int cur) {
    if(i==v.size()) {
        if(cur==24)
            return true;
        else 
            return false;
    }
    if(helper2(v,i+1,cur+v[i]))
        return true;
    if(helper2(v,i+1,cur-v[i]))
        return true;
    if(helper2(v,i+1,cur*v[i]))
        return true;
    if(helper2(v,i+1,cur/v[i]))
        return true;
    return false;
}

bool helper(vector<int>& v){
    bool res = false;
    if(v.size()<4) return false;

    for(int i=0;i<v.size();++i) {
        for(int j=0;j<v.size()&&j!=i;++j) {
            for(int k=0;k<v.size()&&k!=i&&k!=j;++k) {
                for(int m=0;m<v.size()&&m!=i&&m!=j&&m!=k;++m) {
                    vector<int> tempv;
                    tempv.push_back(v[i]);
                    tempv.push_back(v[j]);
                    tempv.push_back(v[k]);
                    tempv.push_back(v[m]);
                   res =  helper2(tempv,1,tempv[0]);
                    if(res) {
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

int main() {
   vector<int> v{3,5,7,2};
   bool res = helper(v);
    cout << res << endl;
}

地平线

  • 给出一个 二叉搜索树求差最小的两个节点的差值
  • 给出一个数组求出最大面积

阿里

  • 反转一个句子当中的单词的顺序
  • CanTransform：
    如hit->hat，hat->cat，cat->fat。但是不能单步从hit->hog。设计算法判断给定输入能否在字典范围内经过任意次步骤完整转换。
  • 一个二叉树上求两个节点之间路径长度的最大值，说出具体的思路。

百度

  • 找到不含重复字符的最长子串的长度
  • 2n*2n 的方阵顺时针转 90 度。

快手

  • 给你1GB数据，数据都是字符串，按照字典序全排序怎么做？

旷视

  • 整型数组 on 最短的连续子数组之和 不小于 M 求得是 Min 长度

商汤

  • 按顺序打印二叉树的每一层的最后一个节点的值

小马

  • 将 1-n 这 n 个数按照 string 大小排序

依图

  • 给一个循环有序的数字查找目标元素。

  • 两个有序数组合并

  • k 个有序数组归并

  • 输入一个 2 维数组，行和列都从小到大有序，判断给定的值是否存在

  • 定义整数的位数叫做整数的长度，定义一个整数的地位只要大于等于他的高位就是不下降。给一个值 k，求出所有长度为 k 以内的满足不下降的整数的个数。

  • 给你一个字符串，是一个json格式字符串，将给定的k的v替换成指定的字符串，如果出现多层嵌套只修改最里层的。

  • 长度1001的数组只有一个数字出现大于1次，所有的数字都在1~1000，如何找到这个重复的数字，尽量的节省空间

  • 两个有序数组 一个目标值target 需要从两个有序数组当中各找到一个数字使得两个数字的和为target

  • 三个有序数组如何实现？

腾讯

  • o(n)时间，1个变量实现洗牌
  • 不用变量交换两个整型有什么方式，实现一下。
  • 写一个优化版本的快排

字节

  • 最长回文子串

  • 给你一个字符串，字符串当中是一段c语言的代码和注释，注释只有/* */这样的可以嵌套，不包含//

    1.请返回去除所有注释的代码

    2.如果代码当中的/和/可以不完全匹配如何告知出现错误

  • 给你一个2G的电脑 10G的文本 文本有1k行的字符串，要求输出所有互为逆序的字符串的组合