# 2023資訊科技產業專案設計 作業二 ## 簡述同儕互評 ### 可改進之處 * 多數同儕英文口說流暢度非常有待改善 * 很多人都聽完題目就直接提出對應演算法, 我認為先分析題目架構再從中著手解釋應該怎麼解答, 最後再引出演算法會是比較合理的 ### 優點 * 多數能正確且流暢的解答面試官問題 * 能夠從原本的approach不斷以各面向優化演算法 ## 模擬面試 [影片](https://youtu.be/Xzotmq_A60Q) 👹 : interviewer 👾 : interviewee (Robber) ### 198. House robber 原題：[House Robber](https://leetcode.com/problems/house-robber/description/) 變形情境題目: You are a software developer working in a bustling office complex, and you have a list of adjacent offices represented by an array. Each office contains a certain amount of valuable equipment that you want to steal, but you cannot rob adjacent offices simultaneously as they are monitored by security cameras. Your goal is to maximize the stolen value without triggering any alarms. ### 測驗說明與問答 👹 : Hello Mr.Robber, welcome to our company's interview, let me describe the question for you really quick so you can understand better. 👹 : Imagine that you are a software engineer in our company, and we have many offices that list like an array. In each office, there's a certain amount of money or valuable objects that you want to stole. 👹 : But the problem is we have security systems, if you steal two adjacent offices the alarms will be triggered. 👹 : We want to know how to you steal from these offices and get the maximum amount of money? 👾 : Thanks for having me in your coding interview, I understand the question clearly, but what do I need to return as an answer? the amount of maximum money? 👹 : Yes you have to return the maximum amount of money you can still. Beside an array `office`, you'll be given the length of the array called `n`. 👾 : Let me describe my approach to you 👾 : Every time when I standing in front of an office, I'll have to decide whether to steal from it or not, I'll use an array called `gain[n]` 👾 : `gain[i]` means that the maximum amount of money I can get stealing from `office[0]~office[i]` 👾 : When I stand in front of `office[i]`, I'll face a decision whether to steal or not If I steal from it, the maximum amount of money I can have is `office[i] + gain[i-2]` If I don't steal it, the maximum amount of money I can have is `gain[i-1]` 👾 : Will I get empty array or an array contains only one office? 👹 : Yes you might have those kind of arrays 👾 : Ok so I should treat them as special cases 👾 : (Coding...) ```c int RobOffice (int *office, int n) { if ( n ==0 ) return 0; if ( n == 1) return office[0]; int gain[n]; gain[0] = office[0]; gain[1] = office[0] > office[1] ? office[0] : office[1]; for (int i=2; i<n; i++) { int stole = office[i] + gain[i-2]; int not_stole = gain[i-1]; gain[i] = stole > not_stole ? stole : not_stole; } return gain[n-1]; } ``` 👾 : Let me use the example `office = [1, 2, 3, 1]` to test my code 👾 : (testing...) 👹 : How about you calculate the time complexity of your algorithm? 👾 : The special cases part takes $O(1)$, the normal cases part takes $O(n)$, so the total time complexity is $O(n)$ 👹 : Hmm, can you imagine that `n` is super big, your array `gain[n]` will be super big, but only one element of them are used as result, 99% of the spaces are wasted, can you improve this situation? 👾 : I noticed that every time I only use 3 elements of my array and treat the rest as garbages, I think I can make my array into length 3 and treat it like a circular array ```c int RobOffice (int *office, int n) { if ( n ==0 ) return 0; if ( n == 1) return office[0]; int gain[3]; gain[0] = office[0]; gain[1] = office[0] > office[1] ? office[0] : office[1]; for (int i=2; i<n; i++) { int stole = office[i] + gain[(i-2) % 3]; int not_stole = gain[(i-1) % 3]; gain[i % 3] = stole > not_stole ? stole : not_stole; } return gain[(n-1) % 3]; } ``` 👾 : (Test example cases...) 👹 : Very well, thank you for attending our interview Mr.Robber.