一亩三分地论坛

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

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

Google Embedded Software Position电面

[复制链接] |试试Instant~ |关注本帖
lfzh123 发表于 2016-5-4 23:50:21 | 显示全部楼层 |阅读模式

2016(4-6月) 电路/电子/半导体类 硕士 全职@Google - 网上海投 - 技术电面 |Pass在职跳槽

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

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

x
我就是在网站上海投的职位,也没有找人内推。安排了一次电面,面试官是个白人大哥,非常nice。之前都在准备embedded system相关的东西,谁知一点都没有问,这个更像是general hiring。
1. 有一个遥控器,只有上u下d左l右r四个按键和一个确定键x,输入是一个字符串,只有英文字符a-z,然后返回一个按键的顺序。假设虚拟键盘一行有8个字符,
a b c d e f g h
i j k l m n o p
q r s t u v w x
y z
cursor初始在a,例如输入是boy的话,那么返回"r x r r r r r d x l l l l l d d d x"
提示要考虑到最后一行只有两个按键,所以如果从其他行move到最后一行的话,需要先移动column,再移动row.反之,先移动row,在移动column。

评分

1

查看全部评分

dg7743 发表于 2016-5-5 11:22:45 | 显示全部楼层
yueliu2366 发表于 2016-5-5 04:55
感谢楼主分享面经。思路是遍历给定的字符串,分别处理相邻的两个char,直到字符串结束,如果有移动到y或者z ...

逻辑可以更精简一下:如果终点在起点的上方,我们就先垂直移动,反之我们就先水平移动。这样其实就可以避免用额外的逻辑来处理最后一行。
C++代码如下:

  1. #include <iostream>
  2. #include <string>

  3. using namespace std;

  4. class Solution {
  5. public:. visit 1point3acres.com for more.
  6.     string inputSequence(string in, char start) {  .1point3acres缃
  7.         string res = "";
  8.         for (const char& c : in) {. From 1point 3acres bbs
  9.             int pos_start = start - 'a';
  10.             int pos_end = c - 'a';
  11.             int horizontal_moves= pos_start % kNum - pos_end % kNum;
  12.             int vertical_moves = pos_end / kNum - pos_start / kNum;
  13.             
  14.             if (vertical_moves < 0) {
  15.                 //move vertically first
  16.                 vertical_moves = -vertical_moves;. from: 1point3acres.com/bbs
  17.                 for (int i = 0; i < vertical_moves; ++i) {
  18.                     res.push_back(kUp);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.                 }
  20.                 moveHorizontally(res, horizontal_moves);
  21.             } else {
  22.                 //move horizontally first. 1point 3acres 璁哄潧
  23.                 moveHorizontally(res, horizontal_moves);
  24.                 for (int i = 0; i < vertical_moves; ++i) {
  25.                     res.push_back(kDown);
  26.                 }
  27.             }. 鍥磋鎴戜滑@1point 3 acres
  28.             start = c;
  29.             res.push_back(kConfirm);
  30.         }
  31.         return res;
  32.     }
  33.    
  34. private:
  35.     const char kUp = 'u';
  36.     const char kDown = 'd';. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.     const char kLeft = 'l';
  38.     const char kRight = 'r';. from: 1point3acres.com/bbs
  39.     const char kConfirm = 'x';
  40.     const int kNum = 8;  . 1point 3acres 璁哄潧
  41.    
  42.     void moveHorizontally(string &res, int horizontal_moves) {
  43.         if (horizontal_moves < 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  44.             horizontal_moves = -horizontal_moves;
  45.             for (int i = 0; i < horizontal_moves; ++i) {
  46.                 res.push_back(kRight);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  47.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.         } else {
  49.             for (int i = 0; i < horizontal_moves; ++i) {
  50.                 res.push_back(kLeft);
  51.             }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  52.         }
  53.     }
  54. };

  55. int main()
  56. {
  57.     Solution s;
  58.     while(1) {
  59.         std::string input;
  60.         std::cout << "What is your input? ";
  61.         getline (std::cin, input);
  62.         std::cout << s.inputSequence(input, 'a') << "\n";
  63.     }
  64. }
复制代码

补充内容 (2016-5-5 11:36):.1point3acres缃
没有看到“提示要考虑到最后一行只有两个按键,所以如果从其他行move到最后一行的话,需要先移动column,再移动row.反之,先移动row,在移动column。”. From 1point 3acres bbs
如果这个提示是硬性规定的话,稍作修改即可。
回复 支持 1 反对 0

使用道具 举报

lpx1989 发表于 2016-5-5 03:47:18 | 显示全部楼层
原来还可以问这样的问题
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-5-5 03:55:46 | 显示全部楼层
楼主,我以后也想申请这个职位,请问你工作经验多少,是不是工作经验完全match,是ms还是phd?
还有期待你onsite 面经

补充内容 (2016-5-4 14:57):
还有,请问你embedded system怎么准备的?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
还有,你刷题用c吗?刷了多少遍?sd准备了吗?工作上的东西有没有准备?

补充内容 (2016-5-4 14:58):
最后一个问题,OS和architecture准备了吗?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-5 04:55:41 | 显示全部楼层
感谢楼主分享面经。思路是遍历给定的字符串,分别处理相邻的两个char,直到字符串结束,如果有移动到y或者z,以及从y或者z移出的要特殊处理一下。时间复杂度是O(n),空间是O(1).自己练习一下:. from: 1point3acres.com/bbs
public class Solution {
    public String printPath(String s, char[][] keyboard) {

        String ret = "";. more info on 1point3acres.com
        for(int i = 0; i < s.length(); i++) {
            if (i == 0) {
                ret += printPahtBetweenTwoPoints(0, s.charAt(i) - 'a'); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            } else {
                ret += printPahtBetweenTwoPoints(s.charAt(i - 1) - 'a', s.charAt(i) - 'a');
            }
               
        }
    }
    . 1point 3acres 璁哄潧
    String printPahtBetweenTwoPoints(int startCode, int endCode) {
        int start_i = startCode / keyboard[0].length;
        int start_j = startCode % keyboard[0].length;
        int end_i = endCode / keyboard[0].length;
        int end_j = endCode % keyboard[0].length;
        
        String ret = ""; . visit 1point3acres.com for more.
        if (start_i == 3 && end_i != 3) { // 起点在y或者z,而终点不是y或者z,先垂直移动,后横向移动
            for(int i = 0; i < 3 - end_i; i++) {
                ret += 'u';
            }
            ret += 'x';
            
            if (start_j == end_j) {return ret;}
            
            char dir = (start_j < end_j) ? 'r' : 'l';. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            for(int i = 0; i < Math.abs(start_j - end_j); i++) {
                ret += dir;
            }
            ret += 'x';
        } else if (start_i != 3 && end_i == 3) {// 起点不在y或者z,而终点在y或者z,先横向移动,后垂直移动
             if (start_j != end_j) { //只有start_j != end_j时,才需要横向移动
                char dir = (start_j < end_j) ? 'r' : 'l';
                for(int i = 0; i < Math.abs(start_j - end_j); i++) {
                    ret += dir;
                }
                ret += 'x';
             }
            
            for(int i = 0; i < 3 - start_i; i++) {
                ret += 'd';
            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
            ret += 'x';. 1point 3acres 璁哄潧
        } else { //起点既不在y或者x,终点也既不在y或者x,无所谓移动的顺序
            if (start_j != end_j) { //只有start_j != end_j时,才需要横向移动
                char dir = (start_j < end_j) ? 'r' : 'l';
                for(int i = 0; i < Math.abs(start_j - end_j); i++) {
                    ret += dir;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                ret += 'x';
             }
             . 鍥磋鎴戜滑@1point 3 acres
             if (start_i != end_i) { //只有start_i != end_i时,才需要纵向移动
                char dir = (start_i < end_i) ? 'd' : 'u';-google 1point3acres
                for(int i = 0; i < Math.abs(start_i - end_i); i++) {
                    ret += dir;
                }
                ret += 'x';
             }
        }
        return ret;
    }
}
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-5-5 05:06:58 | 显示全部楼层
lpx1989 发表于 2016-5-5 03:47
原来还可以问这样的问题

我猜,这个可能是他们工作中写过的一个小小的feature
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-5-5 05:12:31 | 显示全部楼层
lll_2013 发表于 2016-5-5 03:55
楼主,我以后也想申请这个职位,请问你工作经验多少,是不是工作经验完全match,是ms还是phd?
还有期待你 ...

在某芯片公司工作3年,应该是比较match的职位,MS.
Embedded system,以前上过课,然后跟工作相关,你可以去网上搜embedded system interview question.有很多,基本就是memory/pointer/deadlock/semaphore/mutex/OS都需要准备吧。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

其实我是想转码农的,leetcode用java/python刷过几遍。其实对这个职位也没有报太大希望
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-5-5 05:14:33 | 显示全部楼层
yueliu2366 发表于 2016-5-5 04:55
感谢楼主分享面经。思路是遍历给定的字符串,分别处理相邻的两个char,直到字符串结束,如果有移动到y或者z ...

嗯,不错!
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-5-5 05:53:07 | 显示全部楼层
lfzh123 发表于 2016-5-4 16:12
在某芯片公司工作3年,应该是比较match的职位,MS.
Embedded system,以前上过课,然后跟工作相关,你可 ...

恩恩,谢谢啦。
回复 支持 反对

使用道具 举报

最初的梦想2013 发表于 2016-5-5 12:13:32 | 显示全部楼层
lfzh123 发表于 2016-5-5 05:12-google 1point3acres
在某芯片公司工作3年,应该是比较match的职位,MS.
Embedded system,以前上过课,然后跟工作相关,你可 ...

楼主工作3年了,公司都还没开始申绿吗?是不是想找家申绿的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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