G家的onsite

5月8号面的，刚确认了offer，回馈地里
round 1
leetcode原题，矩阵最小路径和，从矩阵左上角走到右下角，每一步往右或者往下
两个链表 求最大的公共后缀

round 2
求一个数组的 h

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

符组成，重新排列这个字符串使得没有相邻的字符是相同字符。如aab变成aba

找工作忙碌了一年终于结束了，最后祝大家好运。

Kimurate 发表于 2015-6-11 13:23
所以题目中的数组是有序的咯？

对的 数组是有序的

[1,3,4,7,8,9]的结果是3，至少有3个数大于3，题目说明里面应该加个至少

round 4 我会这么写，欢迎指正～

1. import java.util.Arrays;
   
2. import java.util.PriorityQueue;
   
3. 
   
4. /*
   
5. * 给一个字符串，该字符串由一些可能会重复的字符组成，重新排列这个字符串使得没有相邻的字符是相同字符。如aab变成aba
   
6. *
   
7. * Using priority Queue, delete 2 node each time till queue is empty
   
8. */
   
9. public class Rearrange {
   
10.         // create class to match char and its freq
    
11.         static class Node implements Comparable<Node>{
    
12.                 char val;
    
13.                 int freq;
    
14.                 Node(char val, int freq){
    
15.                         this.val = val;
    
16.                         this.freq = freq;
    
17.                 }
    
18.                 @Override
    
19.                 // Node with more freq would be in the front
    
20.                 public int compareTo(Node that) {
    
21.                         if (this.freq > that.freq) {
    
22.                                 return -1;
    
23.                         }
    
24.                         else if (this.freq < that.freq) {
    
25.                                 return 1;
    
26.                         }
    
27.                        
    
28.                         return 0;
    
29.                 }
    
30.         }
    
31.         public static String rearrage(String s){
    
32.                 if (s==null || s.length()<=1) return s;
    
33.                 // Build a max-freq priority queue
    
34.                 char[] chs = s.toCharArray();
    
35.                 int[] char_frequency = new int[128];
    
36.                 Arrays.fill(char_frequency,0);
    
37.                 for (char ch:chs) {
    
38.                         char_frequency[ch]+=1;
    
39.                 }
    
40.                 PriorityQueue<Node> pq = new PriorityQueue<Node>();
    
41.                 for (int i=0; i<char_frequency.length; i++) {
    
42.                         if (char_frequency[i]>0) {
    
43.                                 Node x = new Node((char)i,char_frequency[i]);
    
44.                                 //System.out.println(x.val+"-->"+x.freq);
    
45.                                 pq.offer(x);
    
46.                         }
    
47.                 }
    
48.                 //if freq of first ele > n/2+1, return false
    
49.                 if (pq.peek().freq>(s.length()+1)/2)  return null;
    
50.                
    
51.                 //get new string from queue
    
52.                 StringBuilder ans = new StringBuilder();
    
53.                 while (!pq.isEmpty()) {
    
54.                         Node first = pq.poll();
    
55.                         if (pq.isEmpty()) {
    
56.                                 ans.append(first.val);
    
57.                                 break;
    
58.                         }
    
59.                         Node second = pq.poll();
    
60.                         ans.append(first.val+""+second.val);
    
61. 
    
62.                         first.freq-=1;
    
63.                         second.freq-=1;
    
64.                         if (first.freq>0) pq.offer(first);
    
65.                         if (second.freq>0) pq.offer(second);
    
66.                 }
    
67.                 return ans.toString();
    
68.         }
    
69. 
    
70.         public static void main(String[] args) {
    
71.                 // TODO Auto-generated method stub
    
72.         System.out.println(rearrage("BCDAGAAAA"));
    
73.         }
    
74. 
    
75. }
    

复制代码

楼主请问 链表公共后缀的话，是不是要先求的两个链表的长度，然后对齐之后再递归啊

请问楼主round2  意思就是求第（n - h）大的数吗 ， 那可以用quick select吗。 就是leetcode第215题。谢谢~！

milanelllo13 发表于 2015-6-10 13:43
请问楼主round2  意思就是求第（n - h）大的数吗 ， 那可以用quick select吗。 就是leetcode第215题。谢谢~ ...

哈 不好意思楼主 我才发现我看错了题意~

楼主，我想再问一下，n是不一定是数组中的数对吗

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

yinloveslele 发表于 2015-6-10 11:01
楼主请问 链表公共后缀的话，是不是要先求的两个链表的长度，然后对齐之后再递归啊

你这种思路可以的，我是直接把链表遍历一遍，然后倒过来求公共前缀

milanelllo13 发表于 2015-6-10 14:34
楼主，我想再问一下，n是不一定是数组中的数对吗

对的，n不一定是数组中的，n就是这个数组中有多少个数比n大，让n最大。思路是binary search的变种，不是quick select。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

wy_19900814 发表于 2015-6-10 15:48
首先十分感谢楼主分享的题目，然后我想问一下有没有哪个大神给点最后一题的思路。

这题诈一想是想贪心， ...

这种用大根堆的算法更简单易懂，我实现完之后跟面试官解释了很久，然后又演示了几个case他才明白