一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2720|回复: 14
收起左侧

报个zenefits的电面....

[复制链接] |试试Instant~ |关注本帖
calvinq 发表于 2015-4-24 14:22:39 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@zenefits - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
zenefits, 一面.....那天脑子不太好...唉..跪了....直接报题吧...
前面给了一大堆一大堆文字,其实都没用的。。。还非得要我去看...介绍了半天什么是tree. bst...之类的..... visit 1point3acres.com for more.
.1point3acres缃
Given a list of numbers, determine whether it can represent the pre-order traversal list of a binary search tree (BST).

Input
The first line contains the number of test cases, T. T lines follow, consisting of two lines each.
The first line of each test case contains the number of nodes in the tree, N. In next line there will a list of N unique numbers, where each number is from the range [1, N].
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Output
For each test case, print the string “YES” if there exists a BST whose pre-order traversal is equal to the list, otherwise print the string “NO” (without quotes, preserving capitalization).
. 1point3acres.com/bbs
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 100

Sample Input
5
3
1 2 3
3
2 1 3
6
3 2 1 5 4 6
4
1 3 4 2
5
3 4 5 1 2
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Sample Output
YES
YES
YES
NO
NO

Explanation
  • The first three cases are from the above examples.
  • In case 4, after encountering the 3, the 4tells us we are on the right sub-tree, which means no values smaller than 3 are allowed any longer. So when we see the 2 we know the list is invalid.
  • Similarly, in case 5, after encountering the 3, the 4 and 5 tell us we are on the right sub-tree, so the subsequent encounter of values 2 and 1, which belong in the left sub-tree, tells us that the list is not valid as a pre-order traversal of a BST.


其实面试官人挺好的...唉...都怪自己卡机了....
事后想想没什么难吧...就利用bst的性质...一直recur下去...看有没有出现..右subtree里面的node. 比root还大的.就可以了吧...我觉得.....欢迎大家讨论哈..

评分

1

查看全部评分

本帖被以下淘专辑推荐:

refurbish 发表于 2015-4-24 15:03:11 | 显示全部楼层
感谢lz分享。z家电面也是用hackerrank?
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-25 13:30:47 | 显示全部楼层
refurbish 发表于 2015-4-24 15:03
感谢lz分享。z家电面也是用hackerrank?

不是耶~~~~
回复 支持 反对

使用道具 举报

ManitobaFarmer 发表于 2015-4-26 11:44:10 | 显示全部楼层
calvinq 发表于 2015-4-25 13:30. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不是耶~~~~

那是用什么写的呢?
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-28 04:14:41 | 显示全部楼层
ManitobaFarmer 发表于 2015-4-26 11:44
那是用什么写的呢?

是hackerranker
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-28 04:14:50 | 显示全部楼层
ManitobaFarmer 发表于 2015-4-26 11:44
那是用什么写的呢?

是hackerranker
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-28 04:20:58 | 显示全部楼层
ManitobaFarmer 发表于 2015-4-26 11:44
那是用什么写的呢?

啊.不好意思.。是hackerranker...
回复 支持 反对

使用道具 举报

kevinking813 发表于 2015-4-29 14:55:58 | 显示全部楼层
求正确接法。。
回复 支持 反对

使用道具 举报

kevinking813 发表于 2015-4-30 04:33:09 | 显示全部楼层
我方法好麻烦。
思路就是Leetcode Construct BST from inorder and preorder
只要边建立边检查就好了。。。。

class Solution {
public:
    bool canbepreorder(vector<int> &nums) {
        if (nums.size() <= 1)
                return true;
        vector<int> inorder(nums);
        sort(inorder.begin(),inorder.end());
        unordered_map<int,int> map;
        for (int i = 0; i < inorder.size(); i++)
                map[inorder[i]] = i;
        return helper(0,nums.size()-1,0,nums.size()-1,inorder,nums,map);
    }
    // begin1 map to inorder // begin2  map to nums. 1point3acres.com/bbs
    bool helper(int begin1, int end1, int begin2, int end2, vector<int> &inorder, vector<int> &nums, unordered_map<int,int> &map) {
            if (begin1 > end1 || begin2 > end2 || end1-begin1 != end2 - begin2) {
                    return false;
            }
            if (begin1 == end1 && begin2 == end2)
                    if (inorder[begin1] == nums[begin2])
                            return true;
                    else {
                            return false;
                    }
            int mid = map[nums[begin2]];  // pos in inorder array.鏈枃鍘熷垱鑷1point3acres璁哄潧
            if (mid < begin1 || mid > end1) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                    return false;
            }
            int loffset = mid - begin1;
            int roffset = end1 - mid;
            if (loffset > 0 && roffset > 0)
                    return  helper(begin1,mid-1,begin2+1,begin2+loffset,inorder,nums,map) && helper(mid+1,end1,end2-roffset+1,end2,inorder,nums,map);
            else if (loffset > 0)
                    return  helper(begin1,mid-1,begin2+1,begin2+loffset,inorder,nums,map);
            else.1point3acres缃
                    return  helper(mid+1,end1,end2-roffset+1,end2,inorder,nums,map);
    }
};. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

jas7 发表于 2015-4-30 13:46:35 | 显示全部楼层
我不知道写的对不对。
  1. * Determine if the numbers in array A can form a Binary Search Tree. The numbers in A are supposed to be the
  2.      * pre-order traversal of a BST
  3.      *
  4.      * @param A
  5.      * [url=home.php?mod=space&uid=160137]@return[/url] True if A really is a pre-order traversal of a BST and False if not
  6.      */. 1point 3acres 璁哄潧
  7.     boolean isBST(int[] A) {
  8.         if (A == null || A.length == 0) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.             return false;
  10.         }
  11.         return isBST(A, 0, A.length - 1, 1, A.length);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.     }

  13.     boolean isBST(int[] preOrder, int leftPre, int rightPre, int leftIn, int rightIn) {
  14.         if (leftPre > rightPre) {
  15.             return true;. from: 1point3acres.com/bbs
  16.         }
  17.         if (preOrder[leftPre] < leftIn || preOrder[leftPre] > rightIn) {. 1point 3acres 璁哄潧
  18.             return false;
  19.         }. From 1point 3acres bbs
  20.         return isBST(preOrder, leftPre + 1, leftPre + (preOrder[leftPre] - leftIn), leftIn, preOrder[leftPre] - 1)
  21.                 && isBST(preOrder, leftPre + (preOrder[leftPre] - leftIn) + 1, rightPre, preOrder[leftPre] + 1, rightIn);. 鍥磋鎴戜滑@1point 3 acres
  22.     }
复制代码
回复 支持 反对

使用道具 举报

lzd1127 发表于 2015-4-30 13:51:27 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
  1. int pos;

  2.         public boolean isPreOrderBST(int[] array) {
  3.                 if (array == null || array.length == 0) {
  4.                         return false;
  5.                 }
  6.                 pos = 0;
  7.                 findPreOrder(array, array[0],Integer.MIN_VALUE, Integer.MAX_VALUE);
  8.                 return pos == array.length;. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         }

  10.         private void findPreOrder(int[] array, int key, int min, int max) {
  11.                 if (pos == array.length) {
  12.                         return;
    . 1point3acres.com/bbs
  13.                 }
  14.                 if (key > min && key < max) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                         pos++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.                         if (pos < array.length) {
  17.                                 findPreOrder(array, array[pos], min, key);. more info on 1point3acres.com
  18.                                 findPreOrder(array, array[pos], key, max);
  19.                         }
  20.                 }

  21.         }
复制代码
刚写了个, 应该是对的吧。。欢迎指点
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-30 14:19:55 | 显示全部楼层
kevinking813 发表于 2015-4-30 04:33
我方法好麻烦。
思路就是Leetcode Construct BST from inorder and preorder
只要边建立边检查就好了。。 ...

不好意思啊..我也没写出来啊....
我大概的想法也是这样..我每搜一次.都要check一次..老麻烦了.
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-5-1 09:51:23 | 显示全部楼层
lzd1127 发表于 2015-4-30 13:51
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. 1point3acres.com/bbs

想支持楼主,请点 ...

有点没看懂,这样什么时候return false呢?
回复 支持 反对

使用道具 举报

lzd1127 发表于 2015-5-1 11:02:15 | 显示全部楼层
EchoO 发表于 2015-5-1 09:51
有点没看懂,这样什么时候return false呢?

pos没遍历完array的时候。。。遍历完就说明能建BST
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-5-1 11:26:17 | 显示全部楼层
lzd1127 发表于 2015-5-1 11:02
pos没遍历完array的时候。。。遍历完就说明能建BST
. 鍥磋鎴戜滑@1point 3 acres
这样,学习了。之前一直没想好怎么用这种construct BST的方法来验证
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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