《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2755|回复: 8
收起左侧

TripAdvisor online test

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

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

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

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

x
40 分钟写两道算法题,还是有点恶心,Codility代码区域这个好像不能复制粘贴,同时这些题目题干都比较长,理解题意都要几分钟,如果不提前准备的话,很危险

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 |.鏈枃鍘熷垱鑷1point3acres璁哄潧
           |                        | 4, 12
'7'        | push 7 onto the stack  |. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
           |                        | 4, 12, 7
'+'        | perform addition       |
           |                        | 4, 19
'*'        | perform multiplication |
           |                        | 76. 鍥磋鎴戜滑@1point 3 acres
The machine will return 76 as the result as it is the topmost element of its stack.
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.-google 1point3acres
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];
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;
. 1point3acres.com/bbsA[Q] ≤ A[R] for Q < R < N.. more info on 1point3acres.com
For example, consider array A consisting of ten elements such that:
  A[0] = 4  . 鍥磋鎴戜滑@1point 3 acres
  A[1] = 2  
  A[2] = 2.鐣欏璁哄潧-涓浜-涓夊垎鍦
  A[3] = 3  
  A[4] = 1  
  A[5] = 4
  A[6] = 7  
  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:
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  .1point3acres缃
  A[2] = 2
  A[3] = 3  
  A[4] = 1  
  A[5] = 4
  A[6] = 7   鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  A[7] = 8  
  A[8] = 6. from: 1point3acres.com/bbs
  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:. Waral 鍗氬鏈夋洿澶氭枃绔,
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-google 1point3acres
第一个leetcode原题 第二题从头到尾扫描记录从头到当前点前的最大值 从尾到头扫描记录从尾到当前点后的最大 ...

我没读懂你说的第二题的解法,不过我想的是,新建两个boolean array, 一个记录从左到当前值的最大值(max),如果 max <= A,  为true,反之 false; 另一个记录从右边起到当前值的最小值(min),如果min >= A, 为true, 反之false;   如果同一个i 都为true,则返回;.鐣欏璁哄潧-涓浜-涓夊垎鍦

有更好的方法么?
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-23 13:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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