一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 848|回复: 4
收起左侧

Amazon 社招 OA 面经

[复制链接] |试试Instant~ |关注本帖
iceman 发表于 2017-10-30 06:17:55 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Amazon - 猎头 - 在线笔试 |Other在职跳槽

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

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

x
首先是timeline: 10/27/17. Waral 鍗氬鏈夋洿澶氭枃绔,

90min 2道老题 以及 15min 问卷调查(我也是醉了。。).1point3acres缃

两题地里都有,下面是我的答案, local run 可过, huan'ying'zhi'zheng:

1. Amazon warehouse: 给卡车载重M 以及一系列地点(类似 a[x][y] = z,(x, y)为以卡车为原点的坐标 z为该点货物重量) 输出距离最近的 N个点的坐标

import java.util.*;

public class Solution {

    public List<List<Integer>> topK(List<List<Integer>> input, int n,int m){
            PriorityQueue<List<Integer>> pq = new PriorityQueue<List<Integer>>(n,
                            new Comparator<List<Integer>>(){
                          public int compare (List<Integer> e1,List<Integer> e2){
                                  return e1.get(0)*e1.get(0) + e1.get(1)*e1.get(1) - e2.get(0)*e2.get(0) - e2.get(1)*e2.get(1);
                          }
                    });
            for(List<Integer> e1:input){
                    pq.add(e1);. 1point 3acres 璁哄潧
            }
            List<List<Integer>> result = new ArrayList<>();
            for(int i = 0;i < m && i < n;i++){. from: 1point3acres.com/bbs
                    result.add(pq.remove());. From 1point 3acres bbs
            }
        return result;       
    }
}


2. distance between two nodes in a bst

public class Solution {
    public static class TreeNode {
            int val;. 鍥磋鎴戜滑@1point 3 acres
            TreeNode left;
            TreeNode right;. 1point 3acres 璁哄潧
            TreeNode(int x) {
                    val = x;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            }
    }
    // main method to build BST and get dist
    public static int bstDist(int[] a,int n , int p, int q) {
            if (a == null || a.length == 0){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    return 0;
            }
            int res = 0;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷              // build BST
            TreeNode root = buildBST(a);
            // check if p, q exist in BST
            if (bstSearch(root, p) && bstSearch(root, q)) {. visit 1point3acres.com for more.
                // find LCA of p and q
                TreeNode lca = bstLca(root, p, q);
                // find length between LCA - p and LCA - q
                res += findDist(lca, p);
                res += findDist(lca, q);
            } else {
                    res = -1;
            }
            return res;
    }    public static boolean bstSearch(TreeNode root, int x) {
            boolean res = false;
            while (root != null) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    if (root.val == x) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                            return true;
                    } else if (root.val > x) {
                            root = root.left;
                    } else {
                            root = root.right;
                    }
            }
            return res;
    }
    // find LCA in BST
    public static TreeNode bstLca(TreeNode root, int p, int q) {
        if (root == null) {
            return null;
        }
        while (true) {
            if (root.val > Math.max(p, q)) {
                // p, q both in left child
                root = root.left;
            } else if (root.val < Math.min(p, q)) {
                // both in right child
. 1point3acres.com/bbs                root = root.right;
            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
            else {
                // cur root is LCA
                break;
            }
        }. from: 1point3acres.com/bbs
        return root;
    }
    // calculate dist between root and target
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴    public static int findDist(TreeNode root, int x) {. from: 1point3acres.com/bbs
            if (root == null) {
                    return 0;
            }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            int res = 0;
            while (root != null) {
                    if (root.val == x) {
                            break;
                    } else if (root.val > x) {
                            root = root.left;. more info on 1point3acres.com
                            res += 1;
                    } else {
                            root = root.right;. more info on 1point3acres.com
                            res += 1;
                    }-google 1point3acres
            }
            return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }    // build BST with insertion. 1point 3acres 璁哄潧
    public TreeNode buildBST(int[] a) {
        TreeNode root = new TreeNode(a[0]);
        for (int i = 1; i<a.length; ++i) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            createbst(root, a[i]);
        }
    }.1point3acres缃
    public static void createbst(TreeNode root, int val) {
        if (val < root.val) {
            if (root.left == null) {
                root.left = new TreeNode(val);
            } else {
                createbst(root.left,val);
            }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }else {. 鍥磋鎴戜滑@1point 3 acres
            if (root.right == null){
                root.right = new TreeNode(val);
            }else{
                createbst(root.right,val);. 鍥磋鎴戜滑@1point 3 acres
            }
        }
    }
        // find LCA in binary tree
    public TreeNode binaryTreeLCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = binaryTreeLCA(root.left, p, q);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        TreeNode right = binaryTreeLCA(root.right, p, q);
        if (left == null && right == null) {
            // not found. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            return null;
        } else if (left == null) {
            // both on right side, and right is LCA
            return right;
        } else if (right == null) {
            return left;
        } else {
            // one of left the other on right
            return root;
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
}

评分

3

查看全部评分

本帖被以下淘专辑推荐:

jie139139 发表于 2018-1-1 01:58:53 | 显示全部楼层
楼主现在不是在微软吗  打算换公司吗
回复 支持 0 反对 1

使用道具 举报

nicneo925 发表于 2017-10-31 10:55:18 | 显示全部楼层
感谢楼主分享!
回复 支持 反对

使用道具 举报

ruithumbup 发表于 2018-1-4 09:03:32 | 显示全部楼层
感谢楼主分享!
回复 支持 反对

使用道具 举报

 楼主| iceman 发表于 2018-1-8 08:55:29 | 显示全部楼层
jie139139 发表于 2018-1-1 01:58
楼主现在不是在微软吗  打算换公司吗

亚麻HR隔几周就发邮件 推了几次后想想还是去面算了 LOL
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-20 21:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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