男生找男友:我希望你至少是0.628,如果是0.942那就更好了。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 2861|回复: 6
收起左侧

Palantir Online Coding Test

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

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

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

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

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

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

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

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:
. 鍥磋鎴戜滑@1point 3 acres
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.

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. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
A few examples are below.
.鏈枃鍘熷垱鑷1point3acres璁哄潧 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Input:
3
1 5 2
2 4 7
3 6 9
Output:
7 2

The basins, labeled with A’s and B’s, are: .鏈枃鍘熷垱鑷1point3acres璁哄潧
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
1 2 5 4 2
. from: 1point3acres.com/bbs 3 3 5 2 1

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
B B B C C -google 1point3acres
B B C C C

Input:
4
0 2 1 3
2 1 0 4
.鏈枃鍘熷垱鑷1point3acres璁哄潧3 3 3 3 . 1point 3acres 璁哄潧
5 5 2 1 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
Output:
7 5 4 .鏈枃鍘熷垱鑷1point3acres璁哄潧

. more info on 1point3acres.comThe basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B .鏈枃鍘熷垱鑷1point3acres璁哄潧
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));
                }
               
        }


}



补充内容 (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. visit 1point3acres.com for more.
LZ 有结果了吗。我最近也接到了这个online test。正准备做。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
被拒了~sigh...同学加油! 争取去onsite.
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-22 12:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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