聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3619|回复: 14
收起左侧

报个zenefits的电面....

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

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

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

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

x
zenefits, 一面.....那天脑子不太好...唉..跪了....直接报题吧...
前面给了一大堆一大堆文字,其实都没用的。。。还非得要我去看...介绍了半天什么是tree. bst...之类的....
来源一亩.三分地论坛.
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].

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).

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
.1point3acres网
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
那是用什么写的呢?
.1point3acres网
是hackerranker
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-28 04:14:50 | 显示全部楼层
ManitobaFarmer 发表于 2015-4-26 11:44
那是用什么写的呢?
. 1point3acres
是hackerranker
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

kevinking813 发表于 2015-4-29 14:55:58 | 显示全部楼层
求正确接法。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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;. 1point3acres
        vector<int> inorder(nums);
        sort(inorder.begin(),inorder.end());
        unordered_map<int,int> map;-google 1point3acres
        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
    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-google 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
                    return  helper(mid+1,end1,end2-roffset+1,end2,inorder,nums,map);
    }
};
回复 支持 反对

使用道具 举报

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

  13.     boolean isBST(int[] preOrder, int leftPre, int rightPre, int leftIn, int rightIn) {
  14.         if (leftPre > rightPre) {
  15.             return true;
  16.         }. 1point3acres
  17.         if (preOrder[leftPre] < leftIn || preOrder[leftPre] > rightIn) {
  18.             return false;
  19.         }
  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);
  22.     }
复制代码
回复 支持 反对

使用道具 举报

lzd1127 发表于 2015-4-30 13:51:27 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 1point 3acres 论坛
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。. from: 1point3acres
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
  1. int pos;. more info on 1point3acres

  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;
  9.         }

  10.         private void findPreOrder(int[] array, int key, int min, int max) {
  11.                 if (pos == array.length) {
  12.                         return;
  13.                 }
  14.                 if (key > min && key < max) {. 牛人云集,一亩三分地
  15.                         pos++;
  16.                         if (pos < array.length) {
  17.                                 findPreOrder(array, array[pos], min, key);
  18.                                 findPreOrder(array, array[pos], key, max);
  19.                         }
  20.                 }
  21. -google 1point3acres
  22.         }
复制代码
刚写了个, 应该是对的吧。。欢迎指点
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

EchoO 发表于 2015-5-1 11:26:17 | 显示全部楼层
lzd1127 发表于 2015-5-1 11:02
pos没遍历完array的时候。。。遍历完就说明能建BST

这样,学习了。之前一直没想好怎么用这种construct BST的方法来验证
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-21 11:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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