狗家 匹村 现场面 面经

第一题是不是一个国人大叔。我也是。我觉得我的解法当时是对的。但是不知道会给我什么feedback

第四道题不是很easy，至少从代码量上来说

lz google只面算法吗，其他的会有吗，像ood, system design

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

如果是你这样的提议我感觉就是dp的解法，dp[i][0]代表着是从左边走到这一行的，dp[i][1]代表着从右边往下走到这一行的，转移方程也很容易写

论坛匿名用户 发表于 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;
        }

第三题union find

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

那如果选择原路返回是指不修吗？后面还得回来修？

为啥只有四道题目啊？

sweetwater 发表于 2018-9-26 02:27
那如果选择原路返回是指不修吗？后面还得回来修？

修啊，我觉得题目是这样的：
01000
10001
11000
10101
你走逆时针方向，修最近的1个或2个机器，共需要
第一行：修好后原路返回 2*2
第二行左半部：1*2
3: 2*2
4: 5步 不返回
接着修第2行右半部 1
共需要16步，不考虑返回原点和行间步数。
如果一行一行修 就需要5*4=20步

第一题暴力搜索可以。Dijakastra最短路径算法可以吗？！