ITPub博客

工程架构方向的程序员，看到推荐/搜索/广告等和算法相关的技术，心中或多或少有一丝胆怯。但认真研究之后，发现其实没有这么难。今天的1分钟系列，给大家介绍下推荐系统中的“协同过滤”，绝无任何公式，保证大伙弄懂。什么是协同过滤（CollaborativeFiltering）？答：通过找到兴趣相投，或者有共

分离集合(disjointset)是一种经典的数据结构，它有三类操作：Make-set(a)：生成包含一个元素a的集合S；Union(X,Y)：合并两个集合X和Y；Find-set(a)：查找元素a所在集合S，即通过元素找集合句柄；它非常适合用来解决集合合并与查找的问题，也常称为并查集。一、并查集的

题目：求微信群覆盖微信有很多群，现进行如下抽象：(1)每个微信群由一个唯一的gid标识；(2)微信群内每个用户由一个唯一的uid标识；(3)一个用户可以加入多个群；(4)群可以抽象成一个由不重复uid组成的集合，例如：g1{u1,u2,u3}g2{u1,u4,u5}可以看到，用户u1加入了g1与g2

题目：求微信群覆盖微信有很多群，现进行如下抽象：(1)每个微信群由一个唯一的gid标识；(2)微信群内每个用户由一个唯一的uid标识；(3)一个用户可以加入多个群；(4)群可以抽象成一个由不重复uid组成的集合，例如：g1{u1,u2,u3}g2{u1,u4,u5}可以看到，用户u1加入了g1与g2

题目：求微信群覆盖微信有很多群，现进行如下抽象：(1)每个微信群由一个唯一的gid标识；(2)微信群内每个用户由一个唯一的uid标识；(3)一个用户可以加入多个群；(4)群可以抽象成一个由不重复uid组成的集合，例如：g1{u1,u2,u3}g2{u1,u4,u5}可以看到，用户u1加入了g1与g2

如何从n个数里找到最大值？很容易想到，用一个循环就能搞定。intfind_max(intarr[n]){intmax=-infinite;for(inti=0;i<n;i++)if(arr[i]>max)max=arr[i];returnmax;}这里，需要执行n-1次比较。如何从n个数

直奔主题，世界上“最漂亮”的排序算法。voidstooge_sort(intarr[],inti,intj){if(arr[i]>arr[j])swap(arr[i],arr[j]);if(i+1>=j)return;intk=(j-i+1)/3;stooge_sort(arr,i,j-

排序，面试中考察基本功问的比较多的问题。时间复杂度为O(n)的排序，常见的有三种：基数排序(RadixSort)计数排序(CountingSort)桶排序(BucketSort)今天，1分钟，争取让大家搞懂桶排序。画外音：百度“桶排序”，很多文章是错误的，本文内容与《算法导论》中的桶排序保持一致。桶

排序，面试中，问的比较多。时间复杂度为O(n)的排序，除了基数排序(RadixSort)，还有计数排序(CountingSort)。今天，1分钟，通过几幅图，争取让大家搞懂计数排序。计数排序的适用范围？待排序的元素在某一个范围[MIN,MAX]之间。画外音：很多业务场景是符合这一场景，例如uint3

排序，面试中考察基本功问的比较多，工作多年以后，对排序的细节记忆不那么清楚的小伙伴，面试时会比较吃亏。有一种很神奇的排序，基数排序(RadixSort)，时间复杂度为O(n)，今天花1分钟，通过几幅图，争取让大家搞懂细节。画外音：居然还有时间复杂度为O(n)的排序算法？不但有，其实还有很多。举个栗子

最烦面试官问，“为什么XX算法的时间复杂度是OO”，今后，不再惧怕这类问题。快速排序分为这么几步：第一步，先做一次partition；partition使用第一个元素t=arr[low]为哨兵，把数组分成了两个半区：左半区比t大右半区比t小第二步，左半区递归；第三步，右半区递归；伪代码为：voidq

面试中，问得比较多的几个问题之一，求斐波那契数列f(n)？画外音：姐妹篇《拜托，面试别再问我TopK了！！！》《拜托，面试别再让我数1了！！！》什么是斐波那契数列？斐波那契数列是这样一个数列，它满足：f(0)=0;f(1)=1;f(n)=f(n-1)+f(n-2)(当n>=2时)到底有几种方法

面试中，除了TopK，是否被问过：求一个正整数的二进制表示包含多少个1？画外音：姊妹篇《拜托，面试别再问我TopK了！！！》。例如：uint32_ti=58585858;i的二进制表示是：000000110111111111100110000001于是，i的二进制表示包含15个1。到底有几种方法，这

前言：本文将介绍随机选择，分治法，减治法的思想，以及TopK问题优化的来龙去脉，原理与细节，保证有收获。面试中，TopK，是问得比较多的几个问题之一，到底有几种方法，这些方案里蕴含的优化思路究竟是怎么样的，今天和大家聊一聊。画外音：除非校招，我在面试过程中从不问TopK这个问题，默认大家都知道。问题

据说，php是世界上最好的语言？画外音：phper说，不服可以点赞来辩。如果站点架构满足以下几点：使用php这类脚本语言开发需要连接后端服务，例如RPC服务、memcache、redis等流量非常大此时，通过短连接访问RPC服务、mc、redis会出现什么问题呢？典型的web架构如上：(1)最前端是

今天有个实习生问了我一个诡异的问题，“线下一台磁盘大小32G的开发机（虚拟机）打不出日志”，把追查过程和大家分享一下。画外音：贵司开发机磁盘容量多大？先du一下，查看磁盘空间：[shenjian@dev02~]#du-sch/16G/画外音：似乎还有空间。再试了一下df，发现结果不一样：[shenj

有个校招的同事问我：(1)使用ls–l查看文件，前面显示的-rwxrwxr-x是什么意思？(2)chmod755xxx.sh又是什么意思？1分钟简单说下，这两个和权限相关的问题。先说下文件类型，访问方式，权限分类。Linux下，分为这么几种文件类型：d：目录directoryl：符号链接links：

文章《一分钟了解nohup和&的功效》留了一个“nohup.out为啥没有包含stdout输出”的尾巴，今天把坑填了。测试代码是一个打印hello与循环轮数的死循环程序，每打印一行就休眠1秒。使用./a.out运行程序后，每隔一秒会在终端输出一个字符串。使用nohup./a.out运行程序后

上一篇《服务挂了，怎么自动恢复？》中留了一个作业，nohup和&究竟有啥区别？不少同学进行了回复，但并不是所有同学都理解得全对，今天把自己挖的坑自己填了。测试代码如下：是一个输出hello与循环轮数的死循环程序，每输出一行就休眠1秒。使用./a.out前台运行程序，会是什么效果呢？程序每隔一

昨天《要过年了，就别再背电脑回家》情怀了一把，没想到评论里的技术人们（特别是运维）竟如此感人。上一篇介绍多维度立体化监控，提到系统需要监控的八个维度：http接口监控log关键字监控操作系统，进程，端口http状态码服务存活性接口处理时间用户层面监控RPC接口监控其中1和2两项《通用+可扩展http