反思反思基础知识之华为技术面试“悲剧鸭”

是的,这边搞着数值计算那边模拟动力学和CEL,业余也写写简单代码,前些天接到华为的一个技术面,和北研所的工程师小哥交流了一下。很直接,上来直奔主题,咱们是技术面试,有些问题一起交流交流,于是就被很简单的IT基础问题给啪啪打脸了。

此前个人感觉工科专业去写代码搞深度学习(DL)、机器学习(ML)之类也是毫无问题的,毕竟工科学的数学课程几乎都能涵盖计算机这些方向需要的数学知识,过之无不及,比如小编大机械专业,前前后后的数学课程开了高等数学(最难的数3还是)、工程矩阵理论、统计和概率论、数值分析、复变函数等,加上类似专业领域的控制工程理论、现代优化设计理论,大部分的理论和ML还是很相通的,啥线性规划、梯度下降、牛顿迭代等等,科研时候写篇论文指不定就得用到什么模拟退火算法、神经网络、遗传算法、蒙特卡罗之流,加上培养计划都有C语言、matlab等编程课程加持,更是感觉跑去干点别的应该不是啥大问题。所以一直觉得机械算是万金油,啥都接触了而且把涉及的数学都涵盖了一遍,去搞点别的还是有基础的,但是还是有跨不过的山和海啊,真要去涉猎别的学科和工程比如计算机,基础还是得牢一些,学一些,基础不好,怕是办事不牢啊,感慨到此,下面说说面试吧。

小编会python和matlab,其它C、C#、java以及scala基本上看得懂,写的话就不是那么如意了,而对相关涉及计算机底层基础的东西就不是特别的清楚了,也是之前一直忽略的内容,比如什么python如何分配内存、算法的复杂度这些以往都没放在心上,有些东西并非不懂,而是没有留个心眼关注下,复杂度怎么定义都不知道更别说去算复杂度了。这次小哥就问我了,作为外行还是有些措手不及,引以为戒。

1、内存机制

小哥:讲讲python如何分配内存吧

我:…(蒙,不懂意思)

学习学习:

内存分配就是需要用的时候分配内存,用完之后还得释放内存。我们看一个简单的例子:

a=4
b=5
print(id(a))
print(id(b))
c=5
print(id(c))

输出的内容是:

1699989264
1699989296
1699989296

可以看到b、c的地址是一样的,也就是在初始化的时候系统将一块地址分给了4和5,对于新建不同的xyz引用(引用指c=5种的c,5是引用对象),如xyz均等于5,这个地址中的存储对象是不变的,仅仅是在引用这个对象值,这就是python的内存管理机制中的引用机制。而每当被创建一次那么对应的引用就增加一次,反之亦然。

基于上述展开,涉及python的垃圾回收机制,上面提到引用次数的问题,当对象的引用次数为0的时候,那么python虚拟机就会回收这个内存,在python中通过导入gc模块设置垃圾回收机制。引用计数的增减情况:

1.1导致引用计数+1的情况

  • 对象被创建,例如a=23
  • 对象被引用,例如b=a
  • 对象被作为参数,传入到一个函数中,例如func(a)
  • 对象作为一个元素,存储在容器中,例如list1=[a,a]

1.2导致引用计数-1的情况

  • 对象的别名被显式销毁,例如del a
  • 对象的别名被赋予新的对象,例如a=24
  • 一个对象离开它的作用域,例如f函数执行完毕时,func函数中的局部变量(全局变量不会)
  • 对象所在的容器被销毁,或从容器中删除对象

需要注意的是,当使用某个引用作为参数,传递给getrefcount()时,参数实际上创建了一个临时的引用。因此,getrefcount()所得到的结果,会比期望的多1。

2、算法复杂度问题

小哥:xxxx两个数组这么比较,不用写代码,直接告诉我算法的复杂度。

我:…(蒙,听过这个词,没去系统学过)

学习学习:

算法的复杂度包括时间复杂度和空间复杂度。

2.1时间复杂度

先看看时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述。我们用O()来计时间复杂度,推导的步骤如下:

1)用常数 1 取代运行时间中的所有加法常数。
2)在修改后的运行次数函数中,只保留最高阶项。
3)如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数。

字面意思略显抽象,我们看看具体的例子。

2.1.1常数阶

n=100 #执行1次
s=(1+n)*n/2 #执行1次
print(s) #执行1次

这个算法的运行次数函数是f(n)=3。根据推导大O阶的方法,第一步把常数项3改为 1。第二步保留最高阶项,它没有最高阶项,所以这个算法的时间复杂度为T(n)=O(1)。由于无论n如何变化,函数运行次数也一样,我们把这种与问题的大小(n 的大小)无关,执行时间恒定的算法, 叫作常数阶。

2.1.2线性阶

n=100
for i in range(len(n)):
   print(i)

循环体中执行n次,复杂度为O(n)。

2.1.3对数阶

count=1
while(count<n):
   count=count*2

这里面随着循环次数的增加,指数增长,所以当2的x次方大于n时跳出循环。由此可得时间复杂度O(logn)

2.1.4平方阶

for i in range(n):
   for j in range(n):
      #....#

内外循环问题,很明显次数为n×n,时间复杂度为O(n²)。

如果内外循环次数不一致,分别为m和n,则复杂度变为O(m×n)。

而对于下面这种情形,复杂度的计算又不一样:

for i in range(n):
   for j in range(i,n):
      #....#

这种情况下,整个复杂度的计算为:n+(n-1)+(n-2)+…+3+2+1=n(n+1)/2,根据上述步骤,取最高阶然后去除相乘的常数,所以时间复杂度为O(n²)。

常用的时间复杂度所耗费的时间从小到大依次是:

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

2.2空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

(1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。

(2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

除了上述问题,小哥哥还问了我hadoop大数据的基本的思想以及存储机制,还有爬虫中如何解决登陆问题,相对来讲,后两个问题还是比前者更熟悉一些。

以上是对两个基本问题的学习总结,每天进步一点点吧,反思反思。

参考:
%1 $ S

发表评论

电子邮件地址不会被公开。 必填项已用*标注