一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2585|回复: 33
收起左侧

[算法题] Google OA 试题讨论

[复制链接] |试试Instant~ |关注本帖
Mr.111 发表于 2016-8-20 01:58:05 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
前几天投google,然后被要求做OA。一共2题,和之前地里的小伙伴发出来的题一样。
第一题还算比较简单,我用C#写的。答案在评论里,虽然不要求算法但如果哪位大神有更好的算法希望提供。
  1. You are given an integer X. You must choose two adjacent digits and replace them with the larger of these two digits.

  2. For example, from the integer X = 233614, you can obtain:
  3.     33614 (by replacing 23 with 3);
  4.     23614 (by replacing 33 with 3 or 36 with 6);
  5.     23364 (by replacing 61 with 6 or 14 with 4);

  6. You want to find the smallest number that can be obtained from X by replacing two adjacent digits with the larger of the two. In the above example, the smallest such number is 23364.

  7. Write a function:

  8.     class Solution { public int solution(int X); }

  9. that, given a positive integer X, returns the smallest number that can be obtained from X by replacing two adjacent digits with the larger of the two.

  10. For example, given X = 233614, the function should return 23364, as explained above.

  11. Assume that:

  12.     X is an integer within the range[10..1,000,000,000].

  13. In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
复制代码
第二题我到现在还没有想出来,跪求大神指点,以下是题目:
  1. You are given a listing of directories and files in a file system. Each directory and file has a name, which is a non-empty string consisting of alphanumerical characters.
  2. Additionally, the name of each file contains a single dot character; the part of the name starting with the dot is called the extension. Directory names do not contain any dots. All the names are case-sensitive.

  3. Each entry is listed on a separate line. Every directory is followed by the listing of its contents indented by one space character. The contents of the root directory are not indented.

  4. Here is a sample listing:

  5. dir1
  6. dir11
  7. dir12
  8.   picture.jpeg
  9. dir121
  10.   file1.txt
  11. dir2
  12. file2.gif

  13. We have three files (picture.jpeg, file1.txt, and file2.gif) and six directories (dir1, dir11, dir12, dir121, dir2 and the root directory).
  14. Directory dir12 contains two files (picture.jpeg and file1.txt) and an empty directory (dir121). The root directory contains two directories (dir1 and dir2).

  15. The absolute path of a file is a string containing the names of directories which have to be traversed (from the root directory) to reach the file, separated by slash characters.
  16. For example, the absolute path to the file file1.txt is "/dir1/dir12/file1.txt". Note that there is no "drive letter", such as "C:", and each absolute path starts with a slash.

  17. We are interested in image files only; that is, files with extensions.jpeg, .png or .gif (and only these extensions).
  18. We are looking for the total length of all the absolute paths leading to the image files. For example, in the file system described above there are two image files:"/dir1/dir12/picture.jpge" and "/dir2/file2.gif".
  19. The total length of the absolute paths to these files is 24 + 15 = 39.

  20. Write a function:

  21.         class Solution { public int solution(String S); }

  22. that, given a string S consisting of N characters which contain the listing of a file system, returns the total of lengths (in characters) modulo 1,000,000,0007 of all the absolute paths to the image files.

  23. For example, given the sample listing showed above, the function should return 39, as explained above. If there are no image files, the function should return 0.

  24. Assume that:
  25.         N is an integer within the range[1..3,000,000];
  26.         string S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9), spaces, dots (.) and end-of-line characters;
  27.         string S is a correct listing of a file system contents.

  28. Complexity:
  29.         expected worst-case time complexity is O(N);
  30.         expected worst-case space complexity is O(N) (not counting the storage required for input arguments).
复制代码
我是先截图,然后再打出来的,如果有什么错误希望大家能够谅解。


我看了之前地里小伙伴对这道题的评论,不知道是我没有理解还是他们的原因,感觉都没有达到要求,以下是我自己的一些想法。
- 这个题目我做了一半,关键卡在complexity的要求上(如果没有这要求我觉得其实也挺简单的)。
- 如果一个文件下有2个image文件,我觉得这个文件就要被计算2次(很多地里其他小伙伴都是计算一次,但是我觉得不对)。例如下面的输入我觉得输出应该是36 ("/dir1/dir12/p1.gif" + "/dir1/dir12/p2.png" = 18 + 18 = 36)
dir1
dir12
  p1.gif
  p2.png

最后,我估计这次OA是跪了。但是真的想知道最后一题到底应该怎么解,跪求各位大神。


评分

1

查看全部评分

stellari 发表于 2016-8-21 13:07:57 | 显示全部楼层
Mr.111 发表于 2016-8-20 04:27
这个解法我想过类似的,不过我个人觉得时间复杂度应该是O(2N)。但是之前算法课上说前面一个这么小的常数 ...

O(N)的意思不是说“最多不会超过N条(常数时间的)指令”,而是说"不会超过kN条指令",其中k为任意大的常数。所以从概念上来说,恒有O(N) = O(2N) = O(3N)... = O(10000N) =...,大O记号中,N前的常数是不会改变时间复杂度的,所以一般人们也不会用O(2N)这种说法。否则,如果N前的常数有实际意义,那么任何循环都是O(3N)以上级别的,因为循环变量自加,比较循环结束条件,跳转至循环开始处都需要至少各一条指令。

你想表达的意思应该用one-pass, two-pass表述更合适些。而@taobingxue给出的做法已经是one-pass的O(N)了。写成代码大概是这个样子的(python 3):
  1. import sys;
  2. import os;

  3. imFormats = set([".jpeg", ".gif", ".png"]);
  4. retval = 0;
  5. stack = [0];

  6. i = 0;
  7. while True:
  8.         currentLine = sys.stdin.readline();   #读一行
  9.         curLevel = len(currentLine) - len(currentLine.lstrip());   # 当前深度=前面有几个空格
  10.         currentStrip = currentLine.strip();
  11.         if not currentStrip:   
  12.                 break;
  13.        
  14.         curLen = len(currentStrip);
  15.         filename, fileext = os.path.splitext(currentLine.strip());    # 取得扩展名
  16.         # 如果当前行的深度小于栈长,说明当前的栈顶存的不是当前行的父目录。
  17.         # 于是不停pop直到找到父目录位置
  18.         while (curLevel + 1 < len(stack)):      
  19.                 stack.pop();
  20.         #找到以后把当前文件的全路径长度写入栈顶。
  21.         stack.append(stack[-1]+curLen+1);
  22.                
  23.         # 如果文件是图片,那么栈顶的值就应被加入最终结果
  24.         if (fileext in imFormats):
  25.                 retval += stack[-1];
  26.                 retval %= 1000000007

  27. print(retval);
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 02:04:30 | 显示全部楼层
本帖最后由 Mr.111 于 2016-8-20 02:08 编辑

关于第一题的解答,我的思路是尝试每一种可能,然后比较。但后来感觉从左到右是根据位数来的,即假设最后结果是4位数,那么如果某个数的千位是最小的,那后面就不用看了,但还没有尝试。以下是我的答案。时间复杂度我觉得是O(2N),因为最后找到最小的.Min()也是需要遍历一遍的
  1. public int solution(int X)
  2. {
  3.     string number = X.ToString();

  4.     if (number.Length == 1) return X;

  5.     List<int> results = new List<int>();

  6.     string left;
  7.     string right;
  8.     for (int i = 0; i < number.Length - 1; i++)
  9.     {
  10.         left = number.Substring(i, 1);
  11.         right = number.Substring(i + 1, 1);
  12.         string tempResulz;
  13.         if (Int32.Parse(left) < Int32.Parse(right))
  14.         {
  15.             tempResulz = number.Remove(i, 1);
  16.             results.Add(Int32.Parse(tempResulz));
  17.         }
  18.         else
  19.         {
  20.             tempResulz = number.Remove(i + 1, 1);
  21.             results.Add(Int32.Parse(tempResulz));
  22.         }
  23.     }

  24.     return results.Min();
  25. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 02:15:01 | 显示全部楼层
关于第二题,我的思路是先处理一下传入的S。把所有不包含image文件的directory和不是image的文件全部删除。(这部分算法我觉得应该不会计入时间和空间复杂度的计算。因为如果用string.Split("\n")来处理,源代码也是需要遍历每一个元素的,我其实就是相当于自己写了个.Split方法)剩下的就是所有image文件和包含这些image文件的directories了。然后我就不会写了,关键是不知道怎么把时间和空间复杂度都控制在O(N)。希望大神指点!
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-8-20 02:54:55 | 显示全部楼层
Mr.111 发表于 2016-8-20 02:15
关于第二题,我的思路是先处理一下传入的S。把所有不包含image文件的directory和不是image的文件全部删除。 ...

感觉不用预处理.用一个prefix string,记录当前这级之前的路径前缀.遍历的时候修改前缀,然后遍历判断是不是图片文件.输出prefix+slash+filename就可以
回复 支持 反对

使用道具 举报

taobingxue 发表于 2016-8-20 03:32:01 | 显示全部楼层
第二题大家算两次是因为他们的题目是统计包含图片文件的目录的长度对于‘/dir1/dir12/a.jpg’和‘/dir1/dir12/b.png’他们的目录都是'/dir1/dir12'。
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 03:33:16 | 显示全部楼层
dydcfg 发表于 2016-8-20 02:54
感觉不用预处理.用一个prefix string,记录当前这级之前的路径前缀.遍历的时候修改前缀,然后遍历判断是不 ...

我觉得你的方法没有达到空间复杂度O(N)的要求。最后是要返回一个总和的INT,过程中如果重复储存路径那不是会超过O(N)?比如同一个文件下有2个image文件,然后这两个image文件之前的路径都一样,那如果存2次空间复杂度岂不就不是O(N)了。
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 03:36:52 | 显示全部楼层
taobingxue 发表于 2016-8-20 03:32
第二题大家算两次是因为他们的题目是统计包含图片文件的目录的长度对于‘/dir1/dir12/a.jpg’和‘/dir1/dir ...

明白了,那样的话还是挺好算的。但这道题是要求连imange都算进去,如何保证时间和空间复杂度都是O(N)?
回复 支持 反对

使用道具 举报

taobingxue 发表于 2016-8-20 04:18:10 | 显示全部楼层
Mr.111 发表于 2016-8-20 03:36
明白了,那样的话还是挺好算的。但这道题是要求连imange都算进去,如何保证时间和空间复杂度都是O(N)?

我前天的OA跟你题目神一样的 0.0 我就是暴力扫了一遍字符串呀 @.@,用一个栈维护到达当前位置每一级目录的长度。
时间复杂度,扫一遍O(N),每一级目录最多插入一次删除一次 O(N),所以是O(N)
空间复杂度,栈最大深度其实有限,反正不超过O(N)
就这样 ? @.@?
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 04:27:47 | 显示全部楼层
taobingxue 发表于 2016-8-20 04:18
我前天的OA跟你题目神一样的 0.0 我就是暴力扫了一遍字符串呀 @.@,用一个栈维护到达当前位置每一级目录 ...

这个解法我想过类似的,不过我个人觉得时间复杂度应该是O(2N)。但是之前算法课上说前面一个这么小的常数一般不会有什么影响。但我还是想知道有没有只扫一遍,然后就能知道结果的算法。
回复 支持 反对

使用道具 举报

taobingxue 发表于 2016-8-20 04:36:07 | 显示全部楼层
本帖最后由 taobingxue 于 2016-8-20 04:37 编辑
Mr.111 发表于 2016-8-20 04:27
这个解法我想过类似的,不过我个人觉得时间复杂度应该是O(2N)。但是之前算法课上说前面一个这么小的常数 ...

大O的定义就是忽略常数的…… 所有时间复杂度都是只管数量级的?

a
-b
--c
-b

这种结构必须知道前面的结构,装逼一点,他的结构是有后效性的,不维护是不可能的
就是至少再扫一遍

所以我觉得是不可能做到你的想要的
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 04:42:58 | 显示全部楼层
taobingxue 发表于 2016-8-20 04:36
大O的定义就是忽略常数的…… 所有时间复杂度都是只管数量级的?

a

我就是想了很久很久也没想出来怎么做到O(N),然后在网上看了很多回答都不是很正确。我自己最多也就是做到了和你一样的O(2N)。这才发帖求助,其实研究了这么久也感觉不太可能完全做到O(N)。至少时间和空间复杂度里至少有1个做不到。
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-8-20 04:59:18 | 显示全部楼层
Mr.111 发表于 2016-8-20 03:33
我觉得你的方法没有达到空间复杂度O(N)的要求。最后是要返回一个总和的INT,过程中如果重复储存路径那不 ...

空间复杂度是O(N),prefixString就是一个string变量,最长就是N.
因为输入是按照层次给的,比如当前在/f1/f2文件夹下面有俩图片p1.jpg,p2.jpg那么他们都是prefixString都一样.
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-20 05:40:32 | 显示全部楼层
本帖最后由 Mr.111 于 2016-8-20 10:03 编辑
dydcfg 发表于 2016-8-20 04:59
空间复杂度是O(N),prefixString就是一个string变量,最长就是N.
因为输入是按照层次给的,比如当前在/f1/f ...

我刚刚试了一下你的方法,发现有个问题。如果是下面的输入:
  1. d1
  2. _d11
  3. __d111
  4. ___p1.gif
  5. _d12
  6. __p2.gif
复制代码
那么,d12的prefix string怎么改?prefix string只有一个,那么/d1/d11/d111是p1.gif的prefix string,然后如何把这个prefix string改成/d1/d12?如果遍历这个prefix string然后改的话,那么时间复杂度应该也就不是O(N)了吧



回复 支持 反对

使用道具 举报

zj45499 发表于 2016-8-21 13:13:17 | 显示全部楼层
这个OA不是不挂人么....
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-8-21 14:01:40 | 显示全部楼层
第二题stack。再说OA不会挂吧
回复 支持 反对

使用道具 举报

wujingzhishui 发表于 2016-8-21 15:15:34 | 显示全部楼层
gaocan1992 发表于 2016-8-21 14:01
第二题stack。再说OA不会挂吧

OA 不挂人是什么意思啊
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-8-22 04:24:45 | 显示全部楼层
wujingzhishui 发表于 2016-8-20 23:15
OA 不挂人是什么意思啊

据说google OA做的好坏都可以
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-22 11:29:12 | 显示全部楼层
stellari 发表于 2016-8-21 13:07
O(N)的意思不是说“最多不会超过N条(常数时间的)指令”,而是说"不会超过kN条指令",其中k为任意大的常 ...

认真查了一下之前学习算法的资料,结果和原理完全如同@stellari 大神说的。只能怪我之前的算法基础没有很牢固。最重要感谢@stellari 大神提供的代码。谢谢!
回复 支持 反对

使用道具 举报

 楼主| Mr.111 发表于 2016-8-22 11:30:05 | 显示全部楼层
本帖最后由 Mr.111 于 2016-8-22 11:32 编辑
zj45499 发表于 2016-8-21 13:13
这个OA不是不挂人么....

真的吗?那后续结果是什么?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 21:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表