一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 1944|回复: 6
收起左侧

Palantir Online Coding Test

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

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

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

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

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

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

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

题目:

A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland. . 1point3acres.com/bbs
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:
. more info on 1point3acres.com
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.

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. -google 1point3acres

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.

Your code should output a space-separated list of the basin sizes, in descending order. (Trailing spaces are ignored.) . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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 .鏈枃鍘熷垱鑷1point3acres璁哄潧
2 4 7
3 6 9. Waral 鍗氬鏈夋洿澶氭枃绔,
Output:
7 2 . From 1point 3acres bbs

The basins, labeled with A’s and B’s, are:
A A B
A A B
A A A

Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
. 1point 3acres 璁哄潧1 2 5 4 2
3 3 5 2 1

Output:
11 7 7


The basins, labeled with A’s, B’s, and C’s, are: . Waral 鍗氬鏈夋洿澶氭枃绔,
A A A A A
A A A A A
B B A C C
B B B C C . visit 1point3acres.com for more.
B B C C C

Input: . Waral 鍗氬鏈夋洿澶氭枃绔,
4 . Waral 鍗氬鏈夋洿澶氭枃绔,
0 2 1 3
2 1 0 4 -google 1point3acres
3 3 3 3
5 5 2 1

Output:
7 5 4 . 1point3acres.com/bbs

The basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B
A B B C
A C C C 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

. From 1point 3acres bbs

鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

chendora2 发表于 2014-7-4 06:03:37 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
可以用union-find的数据结构做~~
回复 支持 1 反对 0

使用道具 举报

 楼主| weiqitoby600 发表于 2014-7-3 06:01:39 | 显示全部楼层
关注一亩三分地微博:
Warald
代码:
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));
                }
               
        }


}

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (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。正准备做。
. 鍥磋鎴戜滑@1point 3 acres
被拒了~sigh...同学加油! 争取去onsite.
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-4-30 03:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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