狗家 匹村 现场面 面经

总共4轮，简历一个字没问，每个面试官都是上来就出题，题目其实都不难，但是楼主是菜鸡，求各位大神指点思路。顺便求加大米。

您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2018-9-22 05:19):
是visited的hashSet，之前写错了，不是数组。

补充内容 (2018-9-22 05:26):
补充下第一题是横着走的, 不考虑竖着走。真的求解答，怕下次还有类似的答不上就惨了。

补充内容 (2018-9-22 05:26):
补充下第一题是横着走的, 不考虑竖着走。真的求解答，怕下次还有类似的答不上就惨了。

补充内容 (2018-9-22 07:56):

补充里面不能贴图，第一题的解释请看9楼，如果哪位大神有思路，求贴一下大家看看~感谢!

补充内容 (2018-9-23 00:08):
找到了 第4题 刷题网 齐武巴 居然是道easy

论坛匿名用户 发表于 2018-9-23 04:50
修机器的人每次修一列的时候，只能走到最右边再往下，或是原路返回从最左边往下，这个是面试官的要求，在 ...

那这样的话就是bfs了， 当y == 0 的时候可以向右 或者向下， 当y == col-1的时候可以向左或者向下，
当0<y<col的时候，保持原有的方向，但是当修复了坏机器，这时可以选择转向或者继续前进，
我代码的问题是我没有找到好的保存状态的办法，我既要保存位置，还有已经修复的机器，还有前进的方向，
我自己都觉得写的代码很恶

public List<int[]> ShortestPathFixMachine(int row, int col, List<int[]> machines)
        {
            HashSet<int> machineSet = new HashSet<int>();
            foreach (int[] a in machines)
            {
                machineSet.Add(a[0] * col + a[1]);
            }

            int n = machines.Count;
            Queue<Tuple<int, string,int>> queue = new Queue<Tuple<int, string,int>>();
            HashSet<Tuple<int, string,int>> visited = new HashSet<Tuple<int, string,int>>();
            if (machineSet.Contains(0))
            {
                Tuple<int, string,int> t = new Tuple<int, string,int>(0, "0",1);
                queue.Enqueue(t);
                visited.Add(t);
            }
            else
            {
                Tuple<int, string,int> t = new Tuple<int, string,int>(0, "",1);
                queue.Enqueue(t);
                visited.Add(t);

            }
            
            while (queue.Count > 0)
            {               
                Tuple<int, string,int> cur = queue.Dequeue();
               
                string[] arr = cur.Item2.Split(',');
                if (arr.Length == n)
                {
                    List<int[]> res = new List<int[]>();
                    foreach (string s in arr)
                    {
                        int pos = Int32.Parse(s);
                        res.Add(new int[]{ pos / col, pos % col});
                    }
                    return res;
                }

                HashSet<string> curState = new HashSet<string>(arr);
                int x = cur.Item1 / col, y = cur.Item1 % col;
                string state = cur.Item2;
                if (machineSet.Contains(cur.Item1) && !curState.Contains(cur.Item1.ToString()))
                {
                    if (state.Length == 0)
                        state = cur.Item1.ToString();
                    else
                       state += "," + cur.Item1;
                }
                if (y == 0)
                {
                    //move right
                    Tuple<int, string,int> tright = new Tuple<int, string,int>(cur.Item1 + 1, state,1);
                    if (!visited.Contains(tright))
                        queue.Enqueue(tright);

                    if ((x + 1) * col + y >= row * col)
                        continue;

                    //move down
                    Tuple<int, string,int> tdown = new Tuple<int, string,int>((x + 1) * col + y, state,1);
                    if (!visited.Contains(tdown))
                    {
                        queue.Enqueue(tdown);
                        visited.Add(tdown);   
                    }

                }
                else if (y == col - 1)
                {
                    //move left
                    Tuple<int, string,int> tleft = new Tuple<int, string,int>(cur.Item1 - 1, state,-1);                    

                    if (!visited.Contains(tleft))
                        queue.Enqueue(tleft);


                    if ((x + 1) * col + y >= row * col)
                        continue;

                    //move down
                    Tuple<int, string,int> tdown = new Tuple<int, string,int>((x + 1) * col + y, state,-1);
                    if (!visited.Contains(tdown))
                    {
                        queue.Enqueue(tdown);
                        visited.Add(tdown);
                    }
                }
                else
                {
                    //either left or right
                    Tuple<int, string,int> tmove = new Tuple<int, string,int>(cur.Item1 + cur.Item3, state, cur.Item3);

                    if (!visited.Contains(tmove))
                    {
                        queue.Enqueue(tmove);
                        visited.Add(tmove);
                    }

                    //state change, can change direction
                    if (state != cur.Item2)
                    {
                        Tuple<int, string, int> tmove2 = new Tuple<int, string, int>(cur.Item1 - cur.Item3, state, -cur.Item3);

                        if (!visited.Contains(tmove2))
                        {
                            queue.Enqueue(tmove2);
                            visited.Add(tmove2);
                        }
                    }

                    
                }
            }

            return null;
        }

第一题：如果需要返回起点而且不用一行一行修的话，我的想法是：
如果某一行从开始走到最后一个坏机器然后返回（行内来回）的长度大于col长度话，就可以尝试着找到满足同样条件的另一行做一个来回，这样的总步长（不考虑上下）就是 2 * col, 且肯定小于 2个单行内来回的长度。对于不满足此条件的行，在行内来回就是最短。如果满足条件的行数为单数的话，就意味着有一行不能pair上，此时就找不满足条件但行内来回最长的一行 然后比较这两行是走一个圈好还是各自来回好。

如果需要回到起点这个解法才成立，因为就能保证即使跳行的话上下的从上下长度为row长的两倍。

如果有人能看懂的话，请鉴定

你第一题给的答案对吗？明显不是最短路径啊

不考虑竖着走是什么意思啊，不能竖着走怎么到下一行啊。。。

楼主可以说一下第一题不考虑竖着走是什么意思吗，没太明白题意

第一题是NP的，只能暴力

第一题是列数显著小于行数码？

楼主 第三题是要求实现areAllied(A,B) 和areAssociated(A,C)   方程嘛？

这句话没看懂 呀  什么事 多于10s内  如何输出Stdout print多于10s内间隔的String

deeper99 发表于 2018-9-22 05:40
不考虑竖着走是什么意思啊，不能竖着走怎么到下一行啊。。。

是我没讲清楚，因为technician被机器挡住，所以每次他要选择是原路返回，还是往前走，要么走到row的最右边往下，要么就做到row的最左边往下。要求返回的是修机器的顺序。

CHITYUEN 发表于 2018-9-22 05:50
楼主可以说一下第一题不考虑竖着走是什么意思吗，没太明白题意

详情请看9楼