一亩三分地论坛

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

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

Startup MuleSoft OD Codility 电面

[复制链接] |试试Instant~ |关注本帖
mit2015 发表于 2015-6-6 08:06:00 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Mulesoft SF骡子 - 猎头 - 在线笔试 |Pass在职跳槽

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

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

x
老年码农重新找工,刚过了一轮 在线笔试 OD for SF downtown Startup MuleSoft, 贴上来回馈大家。  多谢各位了, 下周下一轮电面 以后会继续分布共享面经!

一共三题, 都比较简单:
1. In this problem we consider binary trees, represented by pointer data structures.. from: 1point3acres.com/bbs
A binary tree is either an empty tree or a node (called the root) consisting of a single integer value and two further binary trees, called the left subtree and the right subtree. For example, the figure below shows a binary tree consisting of six nodes. Its root contains the value 5, and the roots of its left and right subtrees have the values 3 and 10, respectively. The right subtree of the node containing the value 10, as well as the left and right subtrees of the nodes containing the values 1, 20 and 21, are empty trees.

                               
登录/注册后可看大图
A binary tree can be given using a pointer data structure. Assume that the following declarations are given:
class Tree {
  public int x;
  public Tree l;
  public Tree r;
}
An empty tree is represented by an empty pointer (denoted by NULL, null, None, nil etc.). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
A path in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The length of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 20, 3, 21 is not a valid path.
The height of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.
A binary tree T is given. A node of tree T containing value V is described as visible if the path from the root of the tree to that node does not contain a node with any value exceeding V. In particular, the root is always visible and nodes with values lower than that of the root are never visible.
For example, the tree shown in the above figure has four visible nodes: namely, those with values 5, 10, 20 and 21. The node with value 1 is not visible because there is a node with value 10 on the path from the root to that node. The node with value 3 is not visible because its value is lower than that of the root, which has value 5.
Write a function:
class Solution { public int solution(Tree T); }
that, given a binary tree T consisting of N nodes, returns its number of visible nodes. For example, given the tree shown in the figure above, the function should return 4, as explained above.
Given tree T with the following structure:

                               
登录/注册后可看大图
the function should return 2, because the only visible nodes are those with value 8.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The trees from the above two figures can be denoted as:

  (5, (3, (20, None, None), (21, None, None)), (10, (1, None, None), None))
and:

  (8, (2, (8, None, None), (7, None, None)), (6, None, None))
Assume that:
  • N is an integer within the range [0..50,000];
  • each value in tree T is an integer within the range [−100,000..100,000];
  • the height of tree T (number of edges on the longest path from root to leaf) is within the range [−1..500].
Complexity:
  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N).
2. Write a function:
class Solution { public int solution(int[] A); }
that, given a zero-indexed array A consisting of N integers, returns the value (or one of the values) that occurs most often in this array.
For example, given array A such that:
. 1point 3acres 璁哄潧
  A[0] = 20  A[1] = 10  A[2] = 30  A[3] = 30  A[4] = 40  A[5] = 10
the function may return 10 or 30.
Assume that:
  • N is an integer within the range [1..200,000];
  • each element of array A is an integer within the range [0..10,000].
Complexity:
  • expected worst-case time complexity is O(N*log(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.

3. Assume that the following declarations are given:
class IntList {
  public int value;
  public IntList next;. 1point3acres.com/bbs
}
Write a function:
class Solution { public int solution(IntList L, int M); }
that, given a single-linked list L consisting of N integers and a positive integer M, returns the value stored in the M-th element in the list, counting from the end, assuming that the last element in the list has index 1. The function should return −1 if it is not possible to return such a value.
For example, given L such that:

  L = 1 -> 2 -> 3 -> 4
and M = 2, the function should return 3, because the second element counting from the end of the list has value 3.
Assume that:
  • N is an integer within the range [0..100,000];
  • M is an integer within the range [1..1,000,000,000];
  • each element of L can be any integer from the interval [−2,147,483,648..2,147,483,647].
Complexity:
  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(1).

.鏈枃鍘熷垱鑷1point3acres璁哄潧

-google 1point3acres

评分

1

查看全部评分

niubi 发表于 2015-10-4 06:17:47 | 显示全部楼层
感谢lz分享!第一题图片不能加载了。。。
回复 支持 反对

使用道具 举报

八月 发表于 2015-10-22 10:37:34 | 显示全部楼层
感谢分享,再过两天就准备做了呢,虽然他们不限时间
回复 支持 反对

使用道具 举报

luofeidream 发表于 2015-12-8 06:29:26 | 显示全部楼层
八月 发表于 2015-10-22 10:37
感谢分享,再过两天就准备做了呢,虽然他们不限时间

你好,我也收到了,你怎么知道是不限时间呢?我看地里另外一个人说有限时的。。
回复 支持 反对

使用道具 举报

luofeidream 发表于 2015-12-8 06:30:04 | 显示全部楼层
请问楼主,编程语言可以选其他的吗比如python
回复 支持 反对

使用道具 举报

八月 发表于 2015-12-8 09:38:00 | 显示全部楼层
luofeidream 发表于 2015-12-8 06:29
你好,我也收到了,你怎么知道是不限时间呢?我看地里另外一个人说有限时的。。

我的意思是他没有deadline。。因为我现在还没做。。。。一直没时间。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 20:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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