朋友的G家onsite面經

1. A tree node has K children, noted as K-way tree. Each child either has a integer value or is NULL. Write a function to recursively rearrange this tree so that all the children that are not NULL are moved to the left most. All the NULL children are moved to the right. The relative sequence of the non-NULL children should stay the same after your function call.

2.1 Given a binary search tree, where each node stores an integer value, a lower bound and an upper bound. Cal

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

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

r different color, only white or black). If the adjacent place is empty and all other adjacent places are either empty or placed by a different color stone, that is a liberty.

求大米~~~

请问楼主在哪栋楼面的？

laiguojiuhao 发表于 2016-12-18 03:12
如果一个子旁边放了相同颜色的子，那么相邻的空白也不算liberty了吗

你是怎么理解这个liberty的？

第一题：

1. import java.util.*;
   
2. 
   
3. public class Solution {
   
4.     private class TreeNode {
   
5.         int val;
   
6.         List<TreeNode> children;
   
7.         public TreeNode(int val) {
   
8.             this.val = val;
   
9.             this.children = new ArrayList<>();
   
10.             for (int index = 0; index < k; index ++) children.add(null);
    
11.         }
    
12.     }
    
13.     public TreeNode rearrange(TreeNode root) {
    
14.         if (root == null) return root;
    
15.         for (TreeNode child : root.children) {
    
16.             rearrange(child);
    
17.         }
    
18.         int left = 0, right = k - 1;
    
19.         while (left < right) {
    
20.             while (left < right && root.children.get(left) != null) left ++;
    
21.             while (left < right && root.children.get(right) == null) right --;
    
22.             if (left < right) {
    
23.                 TreeNode tmpNullNode = root.children.get(left);
    
24.                 root.children.set(left, root.children.get(right));
    
25.                 root.children.set(right, null);
    
26.             }
    
27.         }
    
28.         return root;
    
29.     }
    
30. }

复制代码

第二题：

1. import java.util.*;
   
2. 
   
3. public Solution {
   
4.     private class Node {
   
5.         int val;
   
6.         Node left, right;
   
7.         public Node(int val) {
   
8.             this.val = val;
   
9.         }
   
10.     }
    
11.     public int countSum(Node root, int low, int high) {
    
12.         if (root == null) return 0;
    
13.         if (root.val > high) {
    
14.             return countSum(root.left, low, high);
    
15.         } else if (root.val < low) {
    
16.             return countSum(root.right, low, high);
    
17.         } else {
    
18.             return countSum(root.left, low, root.val) + root.val + countSum(root.right, root.val, high);
    
19.         }
    
20.     }
    
21. }

复制代码

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

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

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

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

laiguojiuhao 发表于 2016-12-18 02:29
要stable的，直接交换不行

回错了。。。回的第一题

laiguojiuhao 发表于 2016-12-18 02:29
要stable的，直接交换不行

懂了，所以双指针都应该从left 到 right，不能分布从两边开始

2.3

1. import java.util.*;
   
2. public class Solution {
   
3.     public boolean canFormSquare(int[][] points) {
   
4.         if (! isInputValid(points)) return false;
   
5.         for (int secondIndex = 1; secondIndex < 4; secondIndex ++) {
   
6.             int firstLength = countLen(points, 0, secondIndex);
   
7.             int[] firstMid = new int[]{points[0][0] + points[secondIndex][0], points[0][1] + points[secondIndex][1]};
   
8.             int secondLength = 0;
   
9.             int[] secondMid = {};
   
10.             switch(secondIndex) {
    
11.                 case 1: {
    
12.                     secondLength = countLen(points, 2, 3);
    
13.                     secondMid = new int[] {points[2][0] + points[3][0], points[2][1] + points[3][1]};
    
14.                     break;
    
15.                 }
    
16.                 case 2: {
    
17.                     secondLength = countLen(points, 1, 3);
    
18.                     secondMid = new int[] {points[1][0] + points[3][0], points[1][1] + points[3][1]};
    
19.                     break;
    
20.                 }
    
21.                 case 3: {
    
22.                     secondLength = countLen(points, 1, 2);
    
23.                     secondMid = new int[] {points[1][0] + points[2][0], points[1][1] + points[2][1]};
    
24.                     break;
    
25.                 }
    
26.             }
    
27.             if (secondLength == firstLength && firstMid[0] == secondMid[0] && firstMid[1] == secondMid[1]) return true;
    
28.         }
    
29.         return false;
    
30.     }
    
31.     private boolean isInputValid(int[][] points) {
    
32.         for (int firstIndex = 0; firstIndex < 3; firstIndex ++) {
    
33.             for (int secondIndex = firstIndex + 1; secondIndex < 4; secondIndex ++) {
    
34.                 if (points[firstIndex][0] == points[secondIndex][0] && points[firstIndex][1] == points[secondIndex][1]) return false;
    
35.             }
    
36.         }
    
37.         return true;
    
38.     }
    
39.     private int countLen(int[][] points, int index1, int index2) {
    
40.         int[] pointA = points[index1], pointB = points[index2];
    
41.         return (int)Math.pow(pointA[0] - pointB[0], 2) + (int)Math.pow(pointA[1] - pointB[1], 2);
    
42.     }
    
43.     public static void main(String[] args) {
    
44.         Solution sol = new Solution();
    
45.         int[][] points = {{0,0}, {0, 1}, {1, 0}, {1,1}};
    
46.         boolean res = sol.canFormSquare(points);
    
47.         System.out.println(res);
    
48.     }
    
49. }

复制代码

工图新一 发表于 2016-12-18 02:45
2.3

你这个只能判断是长方形吧 并不能判断是正方形