📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7275| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

Samsung knox online test

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
一共三道题,第一道题是改错,大家share下思路~
1.    You are given an implementation of a function:
class Solution { public int solution(int[] A, int X); }
This function, when given a zero-indexed array A of N integers, sorted in non-decreasing order, and some integer X, looks for X in A. If X is present in A, then the function returns position of (some) occurrence of X in A. Otherwise, the function returns −1.
For example, given the following array:
  A[0] = 1    A[1] = 2    A[2] = 5
  A[3] = 9    A[4] = 9
and X = 5, the function should return 2, as A[2] = 5.
Unfortunately, there is a bug in the implementation. Find it and correct it. You should modify at most twolines of code.
Assume that:
·    N is an integer within the range [0..100,000];
·    each element of array A is an integer within the range [−2,000,000,000..2,000,000,000];
·    array A is sorted in non-decreasing order;
·    X is an integer within the range [−2,000,000,000..2,000,000,000].
Complexity:
·    expected worst-case time complexity is O(log(N));
·    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
class Solution {
    int solution(int[] A, int X) {
        int N = A.length;
        if (N == 0) {
            return -1;
        }
        int l = 0;
        int r = N - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (A[m] > X) {
                r = m - 1;
            } else {
                l = m;
            }
        }
        if (A[l] == X) {
            return l;
        }
        return -1;
    }
}
2. A binary tree is either an empty tree (represented by an empty pointer) or a node consisting of a single integer value and two binary trees called the left subtree and right subtree.
A binary tree T is given. A path in tree T is a non-empty sequence of nodes of tree T such that each consecutive node in the sequence is a subtree of its preceding node.
A path P in tree T is given. The amplitude of path P is the maximum difference between values of nodes on path P. The amplitude of tree T is the maximum amplitude of paths in T. If tree T is empty, then it does not have any paths and its amplitude is assumed to be 0.
For example, consider the following tree T consisting of nine nodes:
Sequence [9, 8, 2] is a path in this tree. Sequence [12, 8, 2] is not a path in this tree. Path [5, 8, 2] has amplitude 6. Paths [9, 8, 2] and [5, 8, 12] have amplitude 7. The amplitude of the tree is 7, as no path in it has amplitude greater than [9, 8, 2] or [5, 8, 12].
Assume that the following declarations are given:
class Tree {
  public int x;
  public Tree l;
  public Tree r;
}
Write a function:
class Solution { public int solution(Tree T); }
that, given a tree T consisting of N nodes, returns the amplitude of T.
For example, given tree T shown in the example above, the function should return 7.
Assume that:
·    N is an integer within the range [0..1,000,000];
·    each element of tree T is an integer within the range [−1,000,000,000..1,000,000,000].
Complexity:
·    expected worst-case time complexity is O(N);
·    expected worst-case space complexity is O(N).
// you can also use imports, for example:
// import java.math.*;
class Solution {
    public int solution(Tree T) {
        // write your code in Java SE 6
    }
}
3. A non-empty string S = S[0]S[1]...S[N-1] consisting of N characters is given. The K-th cyclic shift of this string, where 0 ≤ K < N, is a string T defined as follows:
T = S[K]S[K+1]...S[N−1]S[0]S[1]...S[K−1]
  
for 0 < K < N,
T = S
  
for K=0.
For example, these are all cyclic shifts of the string S = "codility":
  "codility" is 0th cyclic shift of "codility"
  "odilityc" is 1st cyclic shift of "codility"
  "dilityco" is 2nd cyclic shift of "codility"
  "ilitycod" is 3rd cyclic shift of "codility"
  "litycodi" is 4th cyclic shift of "codility"
  "itycodil" is 5th cyclic shift of "codility"
  "tycodili" is 6th cyclic shift of "codility"
  "ycodilit" is 7th cyclic shift of "codility"
If a cyclic shift of a given string S is equal to S, then it is called a cyclic automorphism of S. Each string has at least one cyclic automorphism, namely the 0th cyclic shift. For example, the 0th and 3rd cyclic shifts of the string "byebye" constitute all of its cyclic automorphisms.
Write a function:
class Solution { public int solution(String S); }
that, given a string S of length N, returns the number of cyclic automorphisms of S.
For example, given S = "byebye", the function should return 2, as explained in the example above.
Assume that:
·    N is an integer within the range [1..1,000,000];
·    string S consists only of lower-case letters (a−z).
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).
// you can also use imports, for example:
// import java.math.*;
class Solution {
    public int solution(String S) {
        // write your code in Java SE 6
    }
}

评分

参与人数 1大米 +30 收起 理由
wjl2525 + 30 感谢分享

查看全部评分


上一篇:Lending Club Engineering Assessment
下一篇:以前做竞赛的时候很有用的资料
推荐
GallenYao 2016-9-21 09:37:27 | 只看该作者
全局:
jimmytzm 发表于 2016-9-21 05:25
感谢楼主分享,刚刚收到on campus interview

小伙子不错!
回复

使用道具 举报

🔗
 楼主| sumingche 2013-10-31 04:11:43 | 只看该作者
全局:
感觉一个半小时写不出来哦
回复

使用道具 举报

🔗
ziningxiao2 2015-3-22 07:26:26 | 只看该作者
全局:
我也感觉可能来不及,不知第二题思路是怎样的比较快
回复

使用道具 举报

🔗
jimmytzm 2016-9-21 05:25:10 | 只看该作者
全局:
感谢楼主分享,刚刚收到on campus interview
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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