一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1345|回复: 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和面试有简单的介绍。看版主问题答得那么好最后还是悲剧了,而且他也说过这是个面试难度相当高的公司。今天**就是抱着试一试的态度。

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

. 1point 3acres 璁哄潧题目:.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:

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. . 1point3acres.com/bbs

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.

A few examples are below.

Input:
3
1 5 2
2 4 7
3 6 9
Output: . 1point 3acres 璁哄潧
7 2

The basins, labeled with A’s and B’s, are: . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
A A B .鐣欏璁哄潧-涓浜-涓夊垎鍦
A A B
A A A . from: 1point3acres.com/bbs

Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1

Output: .1point3acres缃
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 . Waral 鍗氬鏈夋洿澶氭枃绔,
B B B C C
B B C C C
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Input:
4
0 2 1 3
2 1 0 4 .1point3acres缃
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 .1point3acres缃
A B B C
A C C C

本身就是抱着打酱油的心态去的,要是能给下一面,算是走了狗屎运了~ 希望大家能找到理想的工作offer。
.鐣欏璁哄潧-涓浜-涓夊垎鍦




补充内容 (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));
                }
               
        }
. from: 1point3acres.com/bbs

}



补充内容 (2014-7-3 06:04):-google 1point3acres
解题方法参照了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. 鍥磋鎴戜滑@1point 3 acres
LZ 有结果了吗。我最近也接到了这个online test。正准备做。

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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 10:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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