一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2672|回复: 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. .1point3acres缃
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. . From 1point 3acres bbs

Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin. . more info on 1point3acres.com
.鐣欏璁哄潧-涓浜-涓夊垎鍦
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. . more info on 1point3acres.com

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.
. 1point3acres.com/bbs
A few examples are below.

Input:
3
1 5 2
2 4 7
3 6 9
Output:
7 2
. Waral 鍗氬鏈夋洿澶氭枃绔,
The basins, labeled with A’s and B’s, are: .鐣欏璁哄潧-涓浜-涓夊垎鍦
A A B . more info on 1point3acres.com
A A B
A A A
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9 . Waral 鍗氬鏈夋洿澶氭枃绔,
1 2 5 4 2
3 3 5 2 1 . 1point3acres.com/bbs

Output:
11 7 7


The basins, labeled with A’s, B’s, and C’s, are:
A A A A A . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
A A A A A
B B A C C . 鍥磋鎴戜滑@1point 3 acres
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 . 1point 3acres 璁哄潧

Output: . From 1point 3acres bbs
7 5 4 .1point3acres缃

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

本身就是抱着打酱油的心态去的,要是能给下一面,算是走了狗屎运了~ 希望大家能找到理想的工作offer。.鏈枃鍘熷垱鑷1point3acres璁哄潧



. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2014-7-3 06:03):. Waral 鍗氬鏈夋洿澶氭枃绔,
这里定义的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));
                }
               
        }

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
. From 1point 3acres bbs


补充内容 (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.1point3acres缃
LZ 有结果了吗。我最近也接到了这个online test。正准备做。

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-11 23:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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