Amazon Intern Phone Interview Feb 4th 2pm PST

Seattle 来的电话，Brady，一个senior software engineer，口音很正。

二话不说打开collbedit开始做题，一共做了两道……
感觉自我介绍，数据结构，OOD都白准备了2333

第一道是两个逆向的binary byte array 相加，记得leetcode有类似的，不过是list结构的integer，想法差不多

第二道题还在，贴上了：
Given a 4x4 matrix of alphabets and a search str

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

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

e的问题……

最后问我有什么questions，问了俩就结束了

求offer！！！求大米！！！



补充内容 (2016-2-18 03:48):
17th 2:45pm EST Offer Get!!

第2题，比如搜amazon,
path中，必须连续包含amazon么？可以不是amazon这个组成的order，但是必须连续包含其中的char,切每个cell只能算一个？

private static class Cell{
        int x;
        int y;
        Set<List<Integer>> path;
        private Cell(int x, int y) {
            this.x = x;
            this.y = y;
            this.path = new LinkedHashSet<>();
        }
    }
    public boolean findWord(char[][] matrix, String target) {
        if (matrix == null || matrix.length == 0
                || matrix[0].length == 0 || target == null || target.length() == 0) {
            return false;
        }

        int[][] dirs = new int[][] {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1, -1},{1, -1},{-1, 1}};
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == target.charAt(0)) {
                    if (helper(matrix, i, j, dirs, target)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean helper(char[][] matrix, int x, int y, int[][] dirs, String target) {
        int row = matrix.length;
        int col = matrix[0].length;
        int step = 0;
        Queue<Cell> queue = new LinkedList<>();
        Cell first = new Cell(x, y);
        first.path.add(Arrays.asList(x, y));
        queue.add(first); // 没加进去
        while (!queue.isEmpty()) {
            Cell currCell = queue.poll();
            step++;
            if (step == target.length()) {
                return true;
            }
            for (int[] dir : dirs) {
                int nextX = currCell.x + dir[0];
                int nextY = currCell.y + dir[1];
                List<Integer> nextPos = Arrays.asList(nextX, nextY);
                if (nextX >= 0 && nextX < row
                        && nextY >= 0 && nextY < col
                        && !currCell.path.contains(nextPos)
                        && matrix[nextX][nextY] == target.charAt(step)) {
                    Cell newCell = new Cell(nextX, nextY);
                    newCell.path = new LinkedHashSet<>(currCell.path);
                    newCell.path.add(nextPos);
                    queue.offer(newCell);
                }
            }
        }
        return false;
    }

xiaozhuxiaozhu 发表于 2016-2-5 10:57
第2题，比如搜amazon,
path中，必须连续包含amazon么？可以不是amazon这个组成的order，但是必须连续包含 ...

必须是连续的，但是可以向八个方向延伸，而且某个位置上的字母不可重复使用

gwygw 发表于 2016-2-5 12:43
我感觉可以用trie树+ＢＦＳ解决， 本身就是4 4 的数组，递归应该没什么问题吧

感觉好厉害的样子😂
（越来越觉得我offer无望……

gwygw 发表于 2016-2-5 12:43
我感觉可以用trie树+ＢＦＳ解决， 本身就是4 4 的数组，递归应该没什么问题吧

Did the problem need trie? I think it's only a BFS problem

楼主请问一下第一题怎么做啊。

dangertrip 发表于 2016-2-5 14:28
Did the problem need trie? I think it's only a BFS problem

我也是只用了bfs解的