亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2563|回复: 6
收起左侧

Palantir Online Coding Test

[复制链接] |试试Instant~ |关注本帖
weiqitoby600 发表于 2014-7-3 05:58:42 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@Palantir - 网上海投 - 在线笔试 |Other

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

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

x
好久没有在地里发帖子了。。。

这个Test本来是该这周一提交的,后来推迟了五天,今天下午抽时间把Palantir他家的online做了。
忘记是怎么投的简历了,好像是通过LinkedIn投的。隔了一段时间,hr就联系我了,说要给我一个Online Test。于是我就在网上找面经啊。。。版主有个面经帖子,里面对Palantir和面试有简单的介绍。看版主问题答得那么好最后还是悲剧了,而且他也说过这是个面试难度相当高的公司。今天**就是抱着试一试的态度。

下面是题目, 很长,但是晚上有面经(career cup等等), 但是有所改动,大家可以搜出来答案。我也把答案在后面贴出来。由于最后一点疏忽,让输出的部分除了一些错误,太粗心了。

题目:

A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland.
We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on the idea that water flows downhill:

If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks.
Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink, you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.

. Waral 鍗氬鏈夋洿澶氭枃绔,Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.

Your challenge is to partition the map into basins. In particular, given a map of elevations, your code should partition the map into basins and output the sizes of the basins, in descending order.

Assume the elevation maps are square. Input will begin with a line with one integer, S, the height (and width) of the map. The next S lines will each contain a row of the map, each with S integers – the elevations of the S cells in the row. Some farmers have small land plots such as the examples below, while some have larger plots. However, in no case will a farmer have a plot of land larger than S = 5000.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷-google 1point3acres
Your code should output a space-separated list of the basin sizes, in descending order. (Trailing spaces are ignored.) . From 1point 3acres bbs

While correctness and performance are the most important parts of this problem, a human will be reading your solution, so please make an effort to submit clean, readable code. In particular, do not write code as if you were solving a problem for a competition.

A few examples are below.

Input:
3
1 5 2
2 4 7
3 6 9
Output:
7 2 . 鍥磋鎴戜滑@1point 3 acres

The basins, labeled with A’s and B’s, are:
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴A A B . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
A A B
A A A
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Input:
5 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9 . visit 1point3acres.com for more.
1 2 5 4 2
3 3 5 2 1

. from: 1point3acres.com/bbs Output:
11 7 7 . Waral 鍗氬鏈夋洿澶氭枃绔,

. 1point 3acres 璁哄潧
The basins, labeled with A’s, B’s, and C’s, are: . 鍥磋鎴戜滑@1point 3 acres
A A A A A
A A A A A . from: 1point3acres.com/bbs
B B A C C
B B B C C
B B C C C . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Input:
4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1

Output:
7 5 4

The basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B . 鍥磋鎴戜滑@1point 3 acres
A B B C
A C C C

本身就是抱着打酱油的心态去的,要是能给下一面,算是走了狗屎运了~ 希望大家能找到理想的工作offer。

. Waral 鍗氬鏈夋洿澶氭枃绔,



补充内容 (2014-7-3 06:03):
这里定义的neighbor是一个cell周围八个方向的cell(不能越界)

评分

2

查看全部评分

本帖被以下淘专辑推荐:

chendora2 发表于 2014-7-4 06:03:37 | 显示全部楼层
可以用union-find的数据结构做~~
回复 支持 1 反对 0

使用道具 举报

 楼主| weiqitoby600 发表于 2014-7-3 06:01:39 | 显示全部楼层
代码:
import java.util.*;


public class Solution {

        public static void main(String args[]) throws Exception {
               
                 int[][] area = new int[5][5];
                    area[0] = new int[]{1, 0, 2, 5, 8};
                    area[1] = new int[]{2, 3, 4, 7, 9};
                    area[2] = new int[]{3, 5, 7, 8, 9};
                    area[3] = new int[]{1, 2, 5, 4, 2};
                    area[4] = new int[]{2, 3, 5, 2, 1};
               
                HashMap<String, String> result = calculateBasins(area);
                rankSink(result);
        }
       
        public static HashMap<String, String> calculateBasins(int area[][]) {
                int size = area.length;
                String basins[][] = new String [size][size];
                HashMap<String, String> map = new HashMap<String, String>();
                char uniqueSink = 'A';
                for (int x = 0; x < size; x++) {
                        for (int y = 0; y < size; y++) {
                                basins[x][y] = lowestPoint(area,x,y,'A');
                                if(map.containsKey(basins[x][y])) {
                                        String valueString = (String)map.get(basins[x][y]);
                                        StringTokenizer tokens = new StringTokenizer(valueString,":");
                                        char basinUniqueueChar = tokens.nextToken().charAt(0);
                                        int basinSize = Integer.parseInt(tokens.nextToken());
                                        basinSize = basinSize + 1;
                                        map.put(basins[x][y], basinUniqueueChar+":"+basinSize);
                                } else {
                                        map.put(basins[x][y], uniqueSink+":"+1);
                                        uniqueSink++;
                                }
                        }
                }
               
                for (int x = 0; x < size; x++) {
                        for (int y = 0; y < size; y++) {
                                System.out.print(map.get(basins[x][y])+" ");
                        }
                        System.out.println("");
                }
                return map;
        }
       
        public static String lowestPoint(int area[][],int x, int y, char ch) {
                String lowestPoint = x+","+y;
                int size = area.length;
                int leftX, leftY, rightX, rightY, topX, topY, bottomX, bottomY;
                int top_leftX, top_leftY, top_rightX, top_rightY, bottom_leftX, bottom_leftY, bottom_rightX, bottom_rightY;
                int minX, minY,minValue;
               
                leftX = x;
                leftY = y - 1;
               
                top_leftX = x-1;
                top_leftY = y-1;
               
                rightX = x;
                rightY= y + 1;
               
                top_rightX = x-1;
                top_rightY = y+1;
               
                topX = x - 1;
                topY = y;
               
                bottom_leftX = x+1;
                bottom_leftY = y-1;
               
                bottomX = x + 1;
                bottomY = y;
               
                bottom_rightX = x+1;
                bottom_rightY = y+1;
               
                minX = x;
                minY = y;
                minValue = area[x][y];
               
                if (!isOutOfBounds(leftX, leftY, size)) {
                        if (area[leftX][leftY] < minValue) {
                                minX = leftX;
                                minY = leftY;
                                minValue = area[leftX][leftY];
                        }
                }
                if (!isOutOfBounds(rightX, rightY, size)) {
                        if (area[rightX][rightY] < minValue) {
                                minX = rightX;
                                minY = rightY;
                                minValue = area[rightX][rightY];
                        }
                }
                if (!isOutOfBounds(topX, topY, size)) {
                        if (area[topX][topY] < minValue) {
                                minX = topX;
                                minY = topY;
                                minValue = area[topX][topY];
                        }
                }
                if (!isOutOfBounds(bottomX, bottomY, size)) {
                        if (area[bottomX][bottomY] < minValue) {
                                minX = bottomX;
                                minY = bottomY;
                                minValue = area[bottomX][bottomY];
                        }
                }
                if (!isOutOfBounds(top_leftX, top_leftY, size)) {
                        if (area[top_leftX][top_leftY] < minValue) {
                                minX = top_leftX;
                                minY = top_leftY;
                                minValue = area[top_leftX][top_leftY];
                        }
                }
                if (!isOutOfBounds(top_rightX, top_rightY, size)) {
                        if (area[top_rightX][top_rightY] < minValue) {
                                minX = top_rightX;
                                minY = top_rightY;
                                minValue = area[top_rightX][top_rightY];
                        }
                }
                if (!isOutOfBounds(bottom_leftX, bottom_leftY, size)) {
                        if (area[bottom_leftX][bottom_leftY] < minValue) {
                                minX = bottom_leftX;
                                minY = bottom_leftY;
                                minValue = area[bottom_leftX][bottom_leftY];
                        }
                }
                if (!isOutOfBounds(bottom_rightX, bottom_rightY, size)) {
                        if (area[bottom_rightX][bottom_rightY] < minValue) {
                                minX = bottom_rightX;
                                minY = bottom_rightY;
                                minValue = area[bottom_rightX][bottom_rightY];
                        }
                }
                if(!(minX == x && minY == y)) {
                        lowestPoint = lowestPoint(area, minX, minY, ch);
                }
                return lowestPoint;
        }
       
        public static boolean isOutOfBounds(int x, int y, int size) {
                boolean flag = false;
                if (x < 0 || x >= size) {
                        flag = true;
                }
                if (y < 0 || y >= size) {
                        flag = true;
                }
                return flag;
        }
       
        public static void rankSink(HashMap<String, String> map) {
                Collection<String> c = map.values();
               
                ArrayList<Integer> list = new ArrayList<Integer>();
                for (String s : c) {
                        String[] a = s.split(":");
                        Integer i = Integer.valueOf(a[1]);
                        list.add(i);
                }
               
                Collections.sort(list);
                Collections.reverse(list);
       
                for (int i=0; i<list.size(); i++) {
                        System.out.println(list.get(i));
                }
               
        }


}

.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2014-7-3 06:04):
解题方法参照了careercup上的一个接法。直接做了简单的修改。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-7-4 08:38:38 | 显示全部楼层
chendora2 发表于 2014-7-4 06:03
可以用union-find的数据结构做~~

zan , agree
回复 支持 反对

使用道具 举报

weiguo 发表于 2014-7-12 12:10:13 | 显示全部楼层
LZ 有结果了吗。我最近也接到了这个online test。正准备做。
回复 支持 反对

使用道具 举报

 楼主| weiqitoby600 发表于 2014-7-12 23:44:24 | 显示全部楼层
weiguo 发表于 2014-7-12 12:10
LZ 有结果了吗。我最近也接到了这个online test。正准备做。

被拒了~sigh...同学加油! 争取去onsite.
回复 支持 反对

使用道具 举报

tyr034 发表于 2014-10-14 09:11:28 | 显示全部楼层
我也收到了一个Online testing,不知道是不是都是这一题?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-18 01:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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