📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

黑车面试 permutation 变形

全局:

2019(4-6月) 码农类General 本科 全职@uber - 内推 - 技术电面  | | WaitList | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
黑车面试, 一小时一道题。permutation 的变形体。题目描述:there is a set of {p1 d1 p2 d2 … pn d
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
fore p2.
想一想
后面会post solution。


评分

参与人数 2大米 +13 收起 理由
匿名用户-YNP74 + 10
financeFree + 3 很有用的信息!

查看全部评分


上一篇:马鬃旗下游戏平台twitch的onsite
下一篇:WeWork onsite面经
全局:
感谢楼主! 一个小建议:面试中尽量避免global variable,很可能会被面试官各种挑刺。

post一个我的写法

  1.     public List<List<String>> permutation(List<String> input) {
  2.         int len = input.size();
  3.         List<List<String>> res = new ArrayList<>();
  4.         boolean[] visited = new boolean[len];
  5.         dfs(input, visited, new ArrayList<>(), res);

  6.         return res;
  7.     }

  8.     private void dfs(List<String> input, boolean[] visited, List<String> cur, List<List<String>> res) {
  9.         if (cur.size() == input.size()) {
  10.             res.add(new ArrayList<>(cur));
  11.             return;
  12.         }

  13.         for (int i = 0; i < input.size(); ++i) {
  14.             if (i % 2 == 0 && visited[i] || i % 2 == 1 && (!visited[i - 1] || visited[i]))
  15.                 continue;

  16.             visited[i] = true;
  17.             cur.add(input.get(i));
  18.             dfs(input, visited, cur, res);
  19.             cur.remove(cur.size() - 1);
  20.             visited[i] = false;
  21.         }
  22.     }
复制代码


回复

使用道具 举报

全局:
抛个砖 这个应该跟lc那个有重复的permutation类似的思路吧
回复

使用道具 举报

🔗
 楼主| wz30 2019-7-27 23:42:43 | 只看该作者
全局:
yayafuture 发表于 2019-7-27 14:09
抛个砖 这个应该跟lc那个有重复的permutation类似的思路吧

对的, 就是那个思路, 不过在backtrack 判断条件时要保证constranit. 有些变形, 所以背住permutation的答案肯定不行。 还是要理解。
回复

使用道具 举报

🔗
 楼主| wz30 2019-7-27 23:44:33 | 只看该作者
全局:
本帖最后由 wz30 于 2019-7-27 23:58 编辑

下面是我的答案, 欢迎交流。solution (n!)

  1. import java.util.ArrayList;
  2. import java.util.List;

  3. public class uberInterview {
  4.     static List res;
  5.     static int[] arr;

  6.     public static void main(String[] args) {
  7.         int n = 3;
  8.         res = new ArrayList<>();
  9.         List list = new ArrayList<>();
  10.         arr = new int[2 * n];
  11.         //p1d1p2d2
  12.         //2*n
  13.         for (int i = 0; i < n; i++) {
  14.             list.add("p" + i);
  15.             list.add("d" + i);
  16.         }
  17.         //
  18.         recur(list, arr, 2 * n, "");
  19.         System.out.println("res.size()");
  20.         System.out.println(res.size());
  21.         for (int i = 0; i < res.size(); i++) {
  22.             System.out.println(res.get(i));
  23.         }

  24.     }

  25.     static void recur(List list, int[] arr, int len, String curString) {
  26.         if (curString.length() == 2* len) {

  27.             String tempString = curString;
  28.             res.add(tempString);
  29.             return;
  30.         }
  31.         for (int i = 0; i < list.size(); i++) {
  32.             if(i==0){
  33.                 if(arr==0){
  34.                     arr = 1;
  35.                 recur(list, arr, len, curString + list.get(i));
  36.                 arr = 0;
  37.                 }
  38.             }//pi not visited and di is visited
  39.             else if (arr[i-1] == 0 && list.get(i).charAt(0) == 'd') {

  40.             } else if (arr == 0) {
  41.                 arr = 1;
  42.                 recur(list, arr, len, curString + list.get(i));
  43.                 arr = 0;
  44.             }
  45.         }
  46.     }
  47. }
复制代码

回复

使用道具 举报

🔗
wangzhuyun32 2019-7-29 07:42:25 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
akdhfikbk 2020-2-22 18:37:33 | 只看该作者
全局:
我还是不会做....
哭哭啼啼
回复

使用道具 举报

🔗
 楼主| wz30 2020-2-23 00:05:33 | 只看该作者
全局:
akdhfikbk 发表于 2020-2-22 18:37
我还是不会做....
哭哭啼啼

面试考了吗?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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