一亩三分地论坛

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

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

TripAdvisor online test

[复制链接] |试试Instant~ |关注本帖
sumingche 发表于 2014-2-16 10:52:10 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@TripAdvisor - 网上海投 - 在线笔试 |Pass

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

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

x
40 分钟写两道算法题,还是有点恶心,Codility代码区域这个好像不能复制粘贴,同时这些题目题干都比较长,理解题意都要几分钟,如果不提前准备的话,很危险
. more info on 1point3acres.com
1.
A stack machine is a simple system that performs arithmetic operations on an input string of numbers and operators. It contains a stack that can store an arbitrary number of 12-bit unsigned integers. Initially the stack is empty. The machine processes a string of characters in the following way:
the characters of the string are processed one by one;
if the current character is a digit ('0'-'9'), the machine pushes the value of that digit onto its stack;
if the current character is '+', the machine pops the two topmost values from its stack, adds them and pushes the result onto the stack;
if the current character is '*', the machine pops the two topmost values from its stack, multiplies them and pushes the result onto the stack;
after the machine has processed the whole string it returns the topmost value of its stack as the result;
the machine reports an error if any operation it performs (addition or multiplication) results in an overflow;
the machine reports an error if it tries to pop an element from its stack when the stack is empty, or if the stack is empty after the machine has processed the whole string.
For example, given the string "13+62*7+*" the machine will perform the following operations:
character | comment                | stack
-----------------------------------------------
           |                        | [empty]
'1'        | push 1 onto the stack  |
           |                        | 1
'3'        | push 3 onto the stack  |
           |                        | 1, 3
'+'        | perform addition       |
           |                        | 4
'6'        | push 6 onto the stack  |
           |                        | 4, 6
'2'        | push 2 onto the stack  |
           |                        | 4, 6, 2
'*'        | perform multiplication |
           |                        | 4, 12
'7'        | push 7 onto the stack  |
           |                        | 4, 12, 7. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
'+'        | perform addition       |
           |                        | 4, 19
'*'        | perform multiplication |
           |                        | 76
The machine will return 76 as the result as it is the topmost element of its stack.. 1point3acres.com/bbs
Write a function:
class Solution { public int solution(String S); }
that, given a string S consisting of N characters containing input for the stack machine, returns the result the machine would return if given this string. The function should return −1 if the machine would report an error when processing the string.
For example, given string S = "13+62*7+*" the function should return 76, as explained in the example above. Given string S = "11++" the function should return −1.
Assume that:
the length of S is within the range [0..1,000,000];-google 1point3acres
string S consists only of the following characters: "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "+" and/or "*".
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

2.

A zero-indexed array A consisting of N integers is given. A magnitude pole of this array is an integer Q such that:
0 ≤ Q < N;.鐣欏璁哄潧-涓浜-涓夊垎鍦
A[P] ≤ A[Q] for 0 ≤ P < Q;
A[Q] ≤ A[R] for Q < R < N.. Waral 鍗氬鏈夋洿澶氭枃绔,
For example, consider array A consisting of ten elements such that:. visit 1point3acres.com for more.
  A[0] = 4  . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  A[1] = 2  
  A[2] = 2
  A[3] = 3  
  A[4] = 1  
  A[5] = 4
  A[6] = 7  . visit 1point3acres.com for more.
  A[7] = 8  
  A[8] = 6
  A[9] = 9
Number 5 is a magnitude pole of this array, because all elements to the left of A[5] have values smaller than or equal to A[5] (4, 2, 2, 3 and 1 are smaller than or equal to 4) and all elements to the right of A[5] have values greater than or equal to A[5] (7, 8, 6 and 9 are greater than or equal to 4). Number 9 is also a magnitude pole of this array.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Write a function:. more info on 1point3acres.com
class Solution { public int solution(int[] A); } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
that, given a zero-indexed array A consisting of N integers, returns any of its magnitude poles. The function should return −1 if array A does not have a magnitude pole.
For example, given array A consisting of ten elements such that:
  A[0] = 4  
  A[1] = 2  -google 1point3acres
  A[2] = 2
  A[3] = 3  
  A[4] = 1  
  A[5] = 4
  A[6] = 7  
  A[7] = 8  
  A[8] = 6
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷  A[9] = 9
the function may return 5 or 9, as explained above.
Assume that:-google 1point3acres
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2147483648..2147483647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.




评分

4

查看全部评分

cqx83 发表于 2014-2-16 12:40:53 | 显示全部楼层
投了tripadvisor一直没给我回信。。。
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-2-16 13:19:57 | 显示全部楼层
第一个leetcode原题 第二题从头到尾扫描记录从头到当前点前的最大值 从尾到头扫描记录从尾到当前点后的最大值 跟原array比较 如果原值大于等于两个数组的值 即是结果
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-2-18 01:18:01 | 显示全部楼层
回复 支持 反对

使用道具 举报

一点点飞 发表于 2014-4-16 12:33:30 | 显示全部楼层
感谢楼主!看了题目提前准备了一下!刚考完,就是这俩题。等结果吧!谢谢啦!!
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-4-17 02:07:56 | 显示全部楼层
一点点飞 发表于 2014-4-15 23:33
感谢楼主!看了题目提前准备了一下!刚考完,就是这俩题。等结果吧!谢谢啦!!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不客气哈,给加点分吧~
回复 支持 反对

使用道具 举报

heart_shine 发表于 2014-8-8 09:56:11 | 显示全部楼层
谢谢楼主分享上面的问题,正在思考ing~~~
回复 支持 反对

使用道具 举报

heart_shine 发表于 2014-8-9 01:15:56 | 显示全部楼层
lhn9021 发表于 2014-2-16 13:19. 1point3acres.com/bbs
第一个leetcode原题 第二题从头到尾扫描记录从头到当前点前的最大值 从尾到头扫描记录从尾到当前点后的最大 ...

我没读懂你说的第二题的解法,不过我想的是,新建两个boolean array, 一个记录从左到当前值的最大值(max),如果 max <= A,  为true,反之 false; 另一个记录从右边起到当前值的最小值(min),如果min >= A, 为true, 反之false;   如果同一个i 都为true,则返回;.鏈枃鍘熷垱鑷1point3acres璁哄潧
-google 1point3acres
有更好的方法么?
回复 支持 反对

使用道具 举报

genius19 发表于 2014-10-15 10:13:17 | 显示全部楼层
请问它有规定用什么语言写吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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