Akuna Capital OA

楼主第四题有啥想法么

huai10 发表于 2016-8-22 23:46
楼主第四题有啥想法么

1. class tt {
   
2. 
   
3.         /**
   
4.          * @param args
   
5.          */
   
6.         public static void main(String[] args) {
   
7.                 // TODO Auto-generated method stub
   
8.                 int[] nums1 = { 8, 9, 10, 1, 2, 3, 4};
   
9.                 int[] nums2 = { 8, 9, 10, 1, 2, 3};
   
10.                 int[] nums3 = { 10, 9, 2, 5, 3, 7};
    
11.                 Solution tt = new Solution();
    
12.                 List<Integer> res = tt.LongestSortedSubrange(nums1, 3);
    
13.                 for (int j = 0; j < res.size(); j++) {
    
14.                         System.out.print(res.get(j) + "\t");
    
15.                 }
    
16.                 System.out.println();
    
17.                 res = tt.LongestSortedSubrange(nums2, 3);
    
18.                 for (int j = 0; j < res.size(); j++) {
    
19.                         System.out.print(res.get(j) + "\t");
    
20.                 }
    
21.                 System.out.println();
    
22.                 res = tt.LongestSortedSubrange(nums3, 3);
    
23.                 for (int j = 0; j < res.size(); j++) {
    
24.                         System.out.print(res.get(j) + "\t");
    
25.                 }
    
26.         }
    
27. }
    
28. 
    
29. 
    
30. 
    
31. class Solution {
    
32.     public List<Integer> LongestSortedSubrange(int[] nums, int m) {
    
33.         List<Integer> res = new ArrayList<Integer>();
    
34.         if (nums == null || nums.length == 0) {
    
35.             return res;
    
36.         }
    
37.         //record every element idx
    
38.         Map<Integer, Integer> map = new HashMap<>();
    
39.                 for (int i = 0; i < nums.length; i++) {
    
40.             map.put(nums[i], i);
    
41.         }
    
42.         Arrays.sort(nums);
    
43.         dfs(nums, m, res, new ArrayList<Integer>(), nums.length - 1, map);
    
44.         return res;
    
45.     }
    
46. 
    
47.     private void dfs(int[] nums, int m, List<Integer> res, List<Integer> cur, int pos, Map<Integer, Integer> map) {
    
48.             // get the longest one
    
49.         if (pos < 0 && m >= nums.length - cur.size() && cur.size() > res.size()) {
    
50.                 res.clear();
    
51.                 res.addAll(cur);
    
52.             return;
    
53.         }
    
54.         // get the biggest summation
    
55.         if (pos < 0 && m >= nums.length - cur.size() && cur.size() == res.size()) {
    
56.             int resSum = 0, curSum = 0;
    
57.             for (int i = 0; i < cur.size(); i++) {
    
58.                 resSum += res.get(i);
    
59.                 curSum += cur.get(i);
    
60.             }
    
61.             if (curSum > resSum) {
    
62.                     res.clear();
    
63.                     res.addAll(cur);
    
64.             }
    
65.             return;
    
66.         }
    
67.         for (int i = pos; i >= 0; i--) {     
    
68.                 //begin from last one, find the longest sub-sequence
    
69.                 if (cur.isEmpty()) {
    
70.                         cur.add(nums[i]);
    
71.                         dfs(nums, m, res, cur, i - 1, map);
    
72.                         cur.remove(0);
    
73.                 }
    
74.                 //the idx of i_th element greater than the idx of 0 element of cur
    
75.                 //cannot contruct a increasing sub-sequence
    
76.                 else if (map.get(nums[i]) > map.get(cur.get(0))) {
    
77.                         if (i == 0) {
    
78.                                 dfs(nums, m, res, cur, i - 1, map);
    
79.                 }
    
80.             }
    
81.             else {
    
82.                 cur.add(0, nums[i]);
    
83.                 dfs(nums, m, res, cur, i - 1, map);
    
84.                 cur.remove(0);
    
85.             }
    
86.         }
    
87.     }
    
88. }

复制代码

不确定是否正确，只测试了简单的例子

int[] nums1 = { 8, 9, 10, 1, 2, 3, 4};

tt.LongestSortedSubrange(nums1, 3);
1        2        3        4       

int[] nums2 = { 8, 9, 10, 1, 2, 3};
res = tt.LongestSortedSubrange(nums2, 3);
8        9        10       

int[] nums3 = { 10, 9, 2, 5, 3, 7};
res = tt.LongestSortedSubrange(nums3, 3);
2        5        7

有什么想法大家讨论一下

fish444555 发表于 2016-8-23 06:36
不确定是否正确，只测试了简单的例子

int[] nums1 = { 8, 9, 10, 1, 2, 3, 4};

之前想复杂了，而且排序，应该不需要, 测试例子和输出一样

1. class tt {
   
2. 
   
3.         /**
   
4.          * @param args
   
5.          */
   
6.         public static void main(String[] args) {
   
7.                 // TODO Auto-generated method stub
   
8.                 int[] nums1 = { 8, 9, 10, 1, 2, 3, 4};
   
9.                 int[] nums2 = { 8, 9, 10, 1, 2, 3};
   
10.                 int[] nums3 = { 10, 9, 2, 5, 3, 7};
    
11.                 Solution tt = new Solution();
    
12.                 List<Integer> res = tt.LongestSortedSubrange(nums1, 3);
    
13.                 for (int j = 0; j < res.size(); j++) {
    
14.                         System.out.print(res.get(j) + "\t");
    
15.                 }
    
16.                 System.out.println();
    
17.                 res = tt.LongestSortedSubrange(nums2, 3);
    
18.                 for (int j = 0; j < res.size(); j++) {
    
19.                         System.out.print(res.get(j) + "\t");
    
20.                 }
    
21.                 System.out.println();
    
22.                 res = tt.LongestSortedSubrange(nums3, 3);
    
23.                 for (int j = 0; j < res.size(); j++) {
    
24.                         System.out.print(res.get(j) + "\t");
    
25.                 }
    
26.         }
    
27. }
    
28. 
    
29. 
    
30. 
    
31. class Solution {
    
32.     public List<Integer> LongestSortedSubrange(int[] nums, int m) {
    
33.         List<Integer> res = new ArrayList<Integer>();
    
34.         if (nums == null || nums.length == 0) {
    
35.             return res;
    
36.         }
    
37.         dfs(nums, m, res, new ArrayList<Integer>(), 0);
    
38.         return res;
    
39.     }
    
40. 
    
41.     private void dfs(int[] nums, int m, List<Integer> res, List<Integer> cur, int pos) {
    
42.             // get the longest one
    
43.         if (m >= nums.length - cur.size() && cur.size() > res.size()) {
    
44.                 res.clear();
    
45.                 res.addAll(cur);
    
46.             return;
    
47.         }
    
48.         // get the biggest summation
    
49.         if (m >= nums.length - cur.size() && cur.size() == res.size()) {
    
50.             int resSum = 0, curSum = 0;
    
51.             for (int i = 0; i < cur.size(); i++) {
    
52.                 resSum += res.get(i);
    
53.                 curSum += cur.get(i);
    
54.             }
    
55.             if (curSum > resSum) {
    
56.                     res.clear();
    
57.                     res.addAll(cur);
    
58.             }
    
59.             return;
    
60.         }
    
61.         for (int i = pos; i < nums.length; i++) {     
    
62.                 if (cur.isEmpty()) {
    
63.                         cur.add(nums[i]);
    
64.                         dfs(nums, m, res, cur, i + 1);
    
65.                         cur.remove(cur.size() - 1);
    
66.                 }
    
67.                 else if (nums[i] > cur.get(cur.size() - 1)) {
    
68.                 cur.add(nums[i]);
    
69.                 dfs(nums, m, res, cur, i + 1);
    
70.                 cur.remove(cur.size() - 1);
    
71.             }
    
72.         }
    
73.     }
    
74. }

复制代码

楼主能不能说下第五题？基本没看懂说的是什么。。。

Augustus 发表于 2016-8-24 12:39
楼主能不能说下第五题？基本没看懂说的是什么。。。

Problem 5

Word Distance

Given a sequence of words, construct an algorithm that returns the number of times word x appears within n words of word y.


上面是原题题目，我一开始也不太懂，后来看测试例子才大概了解, 下面是测试例子的输入，输出的话忘记记录了，我觉得大概意思就是x, y 间隔 n 个单词，符合这个条件的次数是多少

case 1:
Input
"I cannot simply cannot believe I ate the whole thing", "I", "cannot", 2

Output
2

Input
case 2: "big red fish small blue fish one big fish two big fish big shark", "fish", "big", 1

Output
3

Input
"up up down down left right left right b a b a select start", "down", "right", 2

Output
1

求问楼主申请的是jr developer#几？我收到了#2和#4两个欸！！！。。。都是90miin。。。。

liguanzhu92 发表于 2016-8-25 13:14
求问楼主申请的是jr developer#几？我收到了#2和#4两个欸！！！。。。都是90miin。。。。

求你们做完发面经

liguanzhu92 发表于 2016-8-25 13:14
求问楼主申请的是jr developer#几？我收到了#2和#4两个欸！！！。。。都是90miin。。。。

Jr Dev #1
字数字数字数

未开始申请的小白求科普 什么是OA啊 还有看到地里很多人说onsite 这些是什么意思呢 求前辈们科普 感激！

Daraxu 发表于 2016-8-25 21:38
未开始申请的小白求科普 什么是OA啊 还有看到地里很多人说onsite 这些是什么意思呢 求前辈们科普 感激！

OA, 就是电话面试之前做的编程测试之类的，可能也有选择题，问答题，onsite 就是去公司面对面面试之类的