<
查看: 4545|回复: 9
收起左侧

Google Embedded Software Position电面

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (84)
 
 
0% (0)    👎

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

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

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

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
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
如果从其他行move到最后一行的话,需要先移动column,再移动row.反之,先移动row,在移动column。

评分

参与人数 1大米 +30 收起 理由
candy_shmily + 30

查看全部评分


上一篇:Pure Storage 两次电面面经
下一篇:Zillow 前端 (FrontEnd) 电话面试 (无算法)
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (36)
 
 
2% (1)    👎
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:
  6.     string inputSequence(string in, char start) {  
  7.         string res = "";
  8.         for (const char& c : in) {
  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;
  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
  23.                 moveHorizontally(res, horizontal_moves);
  24.                 for (int i = 0; i < vertical_moves; ++i) {
  25.                     res.push_back(kDown);
  26.                 }
  27.             }
  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';
  39.     const char kConfirm = 'x';
  40.     const int kNum = 8;  
  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.             }
  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):
没有看到“提示要考虑到最后一行只有两个按键,所以如果从其他行move到最后一行的话,需要先移动column,再移动row.反之,先移动row,在移动column。”
如果这个提示是硬性规定的话,稍作修改即可。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (156)
 
 
17% (34)    👎
原来还可以问这样的问题
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
感谢楼主分享面经。思路是遍历给定的字符串,分别处理相邻的两个char,直到字符串结束,如果有移动到y或者z,以及从y或者z移出的要特殊处理一下。时间复杂度是O(n),空间是O(1).自己练习一下:
public class Solution {
    public String printPath(String s, char[][] keyboard) {

        String ret = "";
        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');
            }
               
        }
    }
   
    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 = "";
        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';
        } 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';
             }
            
             if (start_i != end_i) { //只有start_i != end_i时,才需要纵向移动
                char dir = (start_i < end_i) ? 'd' : 'u';
                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 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (84)
 
 
0% (0)    👎
lpx1989 发表于 2016-5-5 03:47
原来还可以问这样的问题

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

使用道具 举报

 楼主| lfzh123 2016-5-5 05:12:31 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (84)
 
 
0% (0)    👎
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 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (84)
 
 
0% (0)    👎
yueliu2366 发表于 2016-5-5 04:55
感谢楼主分享面经。思路是遍历给定的字符串,分别处理相邻的两个char,直到字符串结束,如果有移动到y或者z ...

嗯,不错!
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (468)
 
 
10% (57)    👎
lfzh123 发表于 2016-5-5 05:12
在某芯片公司工作3年,应该是比较match的职位,MS.
Embedded system,以前上过课,然后跟工作相关,你可 ...

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

使用道具 举报

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

本版积分规则

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