So let’s move on.

因此，讓我們繼續(xù)前進(jìn)。

2. Is my algorithm doing Unnecessary work or Duplicated Work?

2.我的算法執(zhí)行不必要的工作還是重復(fù)的工作 ？

This is where we can make major gains on our solution.

這是我們可以從我們的解決方案中獲得重大收益的地方。

One thing we should change is that for every possible combination, we have to iterate through all the activities in the set to calculate the total XP and total time from that set of activities. This is duplicated work, because we’re adding up the same values over and over.

我們應(yīng)該改變的一件事是，對(duì)于每種可能的組合，我們都必須遍歷集合中的所有活動(dòng)，以計(jì)算出該組活動(dòng)的總XP和總時(shí)間 。 這是重復(fù)的工作 ，因?yàn)槲覀円槐橛忠槐榈乩奂酉嗤闹怠?

If we just saved the total XP and time of the combination in a variable, we could just add the XP and time of each new activity we add to to the total. This would take our solution from O(n! * n) to O(n!).

如果我們只是將組合的總XP和時(shí)間保存在一個(gè)變量中，則可以將添加到總計(jì)中的每個(gè)新活動(dòng)的XP和時(shí)間相加。 這將使我們的解從O(n！* n)變?yōu)镺(n！)。

This is helpful, but doesn’t fundamentally make our problem too much faster to run.

這很有用，但從根本上不會(huì)使我們的問(wèn)題運(yùn)行得太快。

What other optimization could we do?

我們還能做什么其他優(yōu)化？

We’re also calculating a lot of combinations that could not possibly lead to a valid solution. This is unnecessary work.

我們還計(jì)算了許多可能無(wú)法得出有效解決方案的組合。 這是不必要的工作 。

For reference here is the list of activities again:

作為參考，這里再次列出活動(dòng)：

Let’s say we have 8 hours total to prepare for our job search. How would our brute force algorithm check combinations?

假設(shè)我們總共有8個(gè)小時(shí)的時(shí)間為求職做準(zhǔn)備。 我們的蠻力算法將如何檢查組合？

Based on the order of the ACTIVITIES array, we would first consider a set just including the side-project object. There is no valid solution containing the side-project activity because it takes 10 hours to do and we only have 8 hours total.

根據(jù)ACTIVITIES數(shù)組的順序，我們首先考慮一個(gè)僅包含副項(xiàng)目對(duì)象的集合。 沒(méi)有有效的解決方案包含副項(xiàng)目活動(dòng)，因?yàn)檫@需要10個(gè)小時(shí)才能完成，而我們總共只有8個(gè)小時(shí)。

But our brute force algorithm (being brute force) doesn’t know that, and will then check every possible combination we can create with side-project.

但是我們的蠻力算法(即蠻力)不知道這一點(diǎn)，然后將檢查我們可以使用side-project創(chuàng)建的每種可能的組合。

So it will check if [side-project, algorithms] is a valid solution. It is not.

因此它將檢查[側(cè)項(xiàng)目，算法]是否是有效的解決方案。 它不是。

And it will check if [side-project, algorithms, networking] is valid. It is not.

并且它將檢查[副項(xiàng)目，算法，網(wǎng)絡(luò)]是否有效。 它不是。

And it will check if [side-project, algorithms, networking, exercise] is valid. It is not.

并且它將檢查[副項(xiàng)目，算法，網(wǎng)絡(luò)，練習(xí)]是否有效。 它不是。

See how much unnecessary work we’re doing?

看看我們正在做多少不必要的工作？

What if we could give our algorithm a little bit of intelligence, so it can check if our current state (the activities we currently have selected) can lead to a valid solution? If the activities we currently have selected can lead to a valid solution (specifically, if our selected set of activities takes less or equal time than the total time we have as a parameter to the function) then we keep selecting new activities and checking if they’re valid.

如果我們可以給我們的算法一點(diǎn)智慧，然后可以檢查我們當(dāng)前的狀態(tài)(我們當(dāng)前選擇的活動(dòng))是否可以導(dǎo)致有效的解決方案，那該怎么辦？ 如果我們當(dāng)前選擇的活動(dòng)可以導(dǎo)致有效的解決方案(特別是，如果我們選擇的活動(dòng)集所花費(fèi)的時(shí)間少于或等于我們作為該函數(shù)的參數(shù)所花費(fèi)的總時(shí)間)，那么我們將繼續(xù)選擇新的活動(dòng)并檢查是否有新活動(dòng)是有效的。

If not, we stop and unselect the last activity we selected.

如果沒(méi)有，我們將停止并取消選擇我們選擇的上一個(gè)活動(dòng)。

For example, if we have 8 hours total, we will first check to see if a combination containing just side-projects can possibly lead to a valid solution. As we determined before, it cannot, because it takes up more time than we currently have.

例如，如果我們總共有8個(gè)小時(shí)，我們將首先檢查看看僅包含側(cè)項(xiàng)目的組合是否可能導(dǎo)致有效的解決方案。 正如我們之前確定的那樣，它不能，因?yàn)樗痊F(xiàn)在占用了更多時(shí)間。

So we unselect side-projects, and try out different combinations starting with algorithms. By checking to see if our current selected activities could lead to a valid solution, we’re avoiding having to check any of the combinations containing side-projects, because they could not possible lead to a valid solution.

因此，我們?nèi)∠x擇副項(xiàng)目，并嘗試從算法開(kāi)始嘗試不同的組合。 通過(guò)檢查當(dāng)前選擇的活動(dòng)是否可以導(dǎo)致有效的解決方案，我們避免了必須檢查包含副項(xiàng)目的任何組合，因?yàn)樗鼈儾豢赡軐?dǎo)致有效的解決方案。

This approach is called backtracking. We check to see if where we are could lead to a valid solution, if not, we go back one step and try to make a different choice.

這種方法稱(chēng)為回溯。 我們檢查一下我們是否可以找到有效的解決方案，否則，我們將退后一步并嘗試做出其他選擇。

Here is the code:

這是代碼：

This solution implements the two optimizations that we discussed earlier:

該解決方案實(shí)現(xiàn)了我們前面討論的兩個(gè)優(yōu)化：

While backtracking saves a lot of work it doesn’t really reduce the overall runtime complexity of our algorithm. It’s still O(n!), because we’re still recursively checking most possible combinations.

回溯雖然節(jié)省了大量工作，但并沒(méi)有真正降低我們算法的整體運(yùn)行時(shí)復(fù)雜性。 它仍然是O(n！)，因?yàn)槲覀內(nèi)栽谶f歸檢查大多數(shù)可能的組合。

But implementing the backtracking algorithm has probably given you a clue on how to continue working on the problem. In the brute force solution, we had to assemble and check the entire combination for each possible combination. With backtracking, we get to check if the path we’re on will lead to a valid solution, before we assemble the entire combination.

但是實(shí)施回溯算法可能為您提供了如何繼續(xù)解決該問(wèn)題的線索。 在蠻力解決方案中，我們必須組裝并檢查每個(gè)可能組合的整個(gè)組合。 通過(guò)回溯，我們可以在組裝整個(gè)組合之前檢查所走的路徑是否會(huì)導(dǎo)致有效的解決方案。

Hmmmmm…..

嗯...

Is there a way to consider only whether or not we should add another activity to our set? This would be a much easier problem than trying to create the entire combination at once. It would allow us to break up our hard problem (finding the optimal combination) to a series of smaller problems (deciding whether or not to add a single activity).

有沒(méi)有辦法只考慮我們是否應(yīng)該向集合中添加另一個(gè)活動(dòng)？ 這比嘗試立即創(chuàng)建整個(gè)組合要容易得多。 這將使我們能夠?qū)㈦y題(找到最佳組合)分解為一系列較小的問(wèn)題(決定是否添加單個(gè)活動(dòng))。

動(dòng)態(tài)編程 (Dynamic Programming)

Dynamic programming is a method where we can divide our big optimization problem (what combination of activities should I choose?) into a series of manageable decision problems (should I include this activity in my optimal solution or not?). We divide and conquer.

動(dòng)態(tài)編程是一種方法，可以將大的優(yōu)化問(wèn)題(我應(yīng)該選擇哪種活動(dòng)組合？)劃分為一系列可管理的決策問(wèn)題(我應(yīng)該將此活動(dòng)包括在最優(yōu)解決方案中嗎？)。 我們分而治之。

Dynamic programming is a common way to solve NP-Hard problems like the Knapsack problem, and coincidentally also a good way to think about job search. It’s hard to determine what combination of activities will make you ready for job search. There’s no efficient way to find the optimal combination or to check if your current choice is optimal.

動(dòng)態(tài)編程是解決諸如背包問(wèn)題之類(lèi)的NP-Hard問(wèn)題的常用方法，同時(shí)也是思考求職問(wèn)題的一種好方法。 很難確定哪種活動(dòng)組合可以使您為求職做好準(zhǔn)備。 沒(méi)有找到最佳組合或檢查當(dāng)前選擇是否最佳的有效方法。

But it’s a lot easier to break your time period down into individual days and weeks, and try to figure out which activities you should be doing for each small period of time.

但是，將時(shí)間段分成幾天和幾周要容易得多，并嘗試找出在每個(gè)小時(shí)間段內(nèi)應(yīng)該執(zhí)行的活動(dòng)。

To solve our job search problem using dynamic programming, we break the problem up into a series of smaller problems (how do I optimize a smaller period of time?) and then take the solution from each of the smaller problems and combine them into a larger solution.

為了使用動(dòng)態(tài)編程解決我們的求職問(wèn)題，我們將問(wèn)題分解為一系列較小的問(wèn)題(如何優(yōu)化較短的時(shí)間段？)，然后從每個(gè)較小的問(wèn)題中獲取解決方案，并將它們組合為一個(gè)較大的問(wèn)題解。

Sounds confusing? Let’s walk through it:

聽(tīng)起來(lái)令人困惑？ 讓我們來(lái)看一下：

What’s the optimal solution if we have a total time of t=0 (zero) to prepare?

如果我們準(zhǔn)備的總時(shí)間為t = 0(零)，那是最佳解決方案？

If we have zero time, we can’t do any activities, so return an empty set, [].

如果我們的時(shí)間為零，那么我們將無(wú)法進(jìn)行任何活動(dòng)，因此請(qǐng)返回一個(gè)空集[] 。

Ok, now what’s the optimal solution is we have a total time of t=1?

好的，現(xiàn)在的最佳解決方案是總時(shí)間為t = 1？

First, let’s see what activities are possible to do: we can’t do a side-project (time t=10) or study algorithms (time t=3). The only thing we can do is networking (time t=1).

首先，讓我們看看可以進(jìn)行哪些活動(dòng)：我們無(wú)法進(jìn)行邊際項(xiàng)目(時(shí)間t = 10)或研究算法(時(shí)間t = 3)。 我們唯一能做的就是聯(lián)網(wǎng)(時(shí)間t = 1)。

So we need to decide if adding networking to the optimal solution for time t=0 will lead to an optimal solution.

因此，我們需要確定在時(shí)間t = 0時(shí)將網(wǎng)絡(luò)添加到最佳解決方案是否會(huì)導(dǎo)致最佳解決方案。

If we add networking, we come out with a total XP of 0.5, not bad.

如果添加網(wǎng)絡(luò)，則總XP為0.5，還不錯(cuò)。

If we don’t add networking, we can’t really do anything else, so we come out with a total XP of 0.

如果不添加網(wǎng)絡(luò)，那么我們將無(wú)能為力，因此我們得出的總XP為0。

0.5 is still better than 0, so if we only have a total time of t=1, we should do networking. The optimal solution for time t=1 is [networking]

0.5仍然比0好，因此，如果我們只有總時(shí)間t = 1，則應(yīng)該進(jìn)行聯(lián)網(wǎng)。 時(shí)間t = 1的最佳解決方案是[聯(lián)網(wǎng)]

What’s the optimal solution for time t=2?

時(shí)間t = 2的最佳解決方案是什么？

What activities are possible with time t=2, that we haven’t already considered? Just exercise.

我們尚未考慮的時(shí)間t = 2可能發(fā)生什么活動(dòng)？ 只是運(yùn)動(dòng)。

If we choose to add exercise, which takes time t=2, we no longer have any time to do anything else, so our solution is [exercise], which leads to 1.5 XP.

如果我們選擇增加運(yùn)動(dòng)，這需要花費(fèi)時(shí)間t = 2，那么我們將不再有時(shí)間做其他任何事情，因此我們的解決方案是[運(yùn)動(dòng)]，得出1.5 XP。

We compare the optimal solution including exercise (which leads to 1.5XP) and the optimal solution not including exercise (which leads to 0.5XP). Since the solution containing exercise is better, we choose that one (In real life, I also feel that with very limited time, some self-care is always more useful than more prep ?).

我們比較了包括運(yùn)動(dòng)的最佳解決方案(導(dǎo)致1.5XP)和不包括運(yùn)動(dòng)的最佳解決方案(導(dǎo)致0.5XP)。 因?yàn)榘\(yùn)動(dòng)的解決方案更好，所以我們選擇其中一種(在現(xiàn)實(shí)生活中，我也覺(jué)得在很有限的時(shí)間里，一些自我護(hù)理總是比準(zhǔn)備更有用？)。

Now here is where it gets really interesting: What’s the optimal solution for time t=3?

現(xiàn)在，這里是它得到真正有趣的： 什么是 時(shí)間t = 3的最佳解決方案？

Again, what activities are possible for time t=3?

同樣，在時(shí)間t = 3時(shí)可能進(jìn)行哪些活動(dòng)？

We have the option to choose from [algorithms, exercise, networking].

我們可以選擇[算法，練習(xí)，網(wǎng)絡(luò)]。

If we choose algorithms which takes time t=3, we have no time to do anything else, so one possible solution is [algorithms].

如果我們選擇需要時(shí)間t = 3的算法 ，那么我們就沒(méi)有時(shí)間做其他任何事情，因此[算法]是一種可能的解決方案。

If we choose exercise which takes time t=2, we have t=1 time left to do something else? How do we know what to choose for the remaining time?

如果我們選擇運(yùn)動(dòng)這需要時(shí)間t = 2，我們有T = 1周時(shí)間留給別人做一些事情？ 我們?nèi)绾沃朗Ｓ鄷r(shí)間要選擇什么？

We know the optimal solution for time t=1, is [networking], so we don’t have to calculate it again. We know we can’t do better than the optimal solution for time t=1.

我們知道時(shí)間t = 1的最佳解決方案是[網(wǎng)絡(luò)]， 因此我們無(wú)需再次計(jì)算。 我們知道，對(duì)于時(shí)間t = 1，我們不能做得比最優(yōu)解更好 。

So one possible solution is [exercise, networking].

因此，一種可能的解決方案是[運(yùn)動(dòng)，網(wǎng)絡(luò)]。

Again we compare all the possible solutions and see that the best we can do is [algorithms].

再次，我們比較了所有可能的解決方案，發(fā)現(xiàn)我們所能做的最好的就是[算法]。

This is the basic structure of a dynamic programming solution: at each amount of time, we test the decision of whether or not to add a specific activity. We compare all possible solutions, and figure out the optimal one.

這是動(dòng)態(tài)編程解決方案的基本結(jié)構(gòu)：在每個(gè)時(shí)間段，我們都會(huì)測(cè)試是否添加特定活動(dòng)的決策 。 我們比較所有可能的解決方案，并找出最佳解決方案。

Solutions for greater amounts of time build upon the optimal solutions for the same problem with a smaller amount of time. This allows us to call the dynamic programming function recursively.

較長(zhǎng)時(shí)間的解決方案以較少時(shí)間的相同問(wèn)題的最佳解決方案為基礎(chǔ)。 這使我們可以遞歸調(diào)用動(dòng)態(tài)編程函數(shù)。

For my example I chose to sort the array of activities by the time it takes to complete them (least to greatest). This allows us the quickly determine which items are possible in the given time because they are sorted by time.

在我的示例中，我選擇按完成活動(dòng)所需的時(shí)間對(duì)數(shù)組進(jìn)行排序(從最小到最大)。 這使我們能夠快速確定在給定時(shí)間內(nèi)哪些項(xiàng)目可行，因?yàn)樗鼈兪前磿r(shí)間排序的。

Below is the code:

下面是代碼：

Wooooo! If you made it through that example the first time, then you’re a way faster learner than I am. I hope it was an interesting in finding alternate ways to solve hard algorithmic questions!

！ 如果您是第一次完成該示例，那么您的學(xué)習(xí)速度將比我快。 我希望找到解決硬算法問(wèn)題的替代方法會(huì)很有趣！

Finally, what is the purpose of this series of three examples you might ask?

最后，您可能會(huì)問(wèn)這三個(gè)示例系列的目的是什么？

Not only did I stealthily give you some practice working on a question very similar to the ones you might be asked in technical interviews, I showed you the steps that I took to come to my mental framework.

我不僅偷偷地給了您一些練習(xí)，以解決與技術(shù)面試中可能會(huì)問(wèn)到的問(wèn)題非常類(lèi)似的問(wèn)題，而且還向您展示了我進(jìn)入心智框架所采取的步驟。

There are an almost infinite combinations of activities you could be doing, and there’s no efficient way to determine the optimal set of activities you should do. A lot of paths don’t lead to a valid solution, just like a lot of job applications and interviews won’t lead to a job.

您可能要進(jìn)行的活動(dòng)幾乎是無(wú)限的組合，并且沒(méi)有有效的方法來(lái)確定您應(yīng)該執(zhí)行的最佳活動(dòng)集。 許多途徑并不能帶來(lái)有效的解決方案，就像許多工作申請(qǐng)和面試不會(huì)帶來(lái)工作一樣。

You could try every possible combination of job search activities (brute force), but since we are human beings with finite time, this isn’t an efficient way to arrive at our goal.

您可以嘗試各種可能的求職活動(dòng)(蠻力)組合，但是由于我們是時(shí)間有限的人，因此這不是達(dá)成目標(biāo)的有效方法。

We could optimize our approach by evaluating at each step whether or not our approach will lead to our goal (backtracking). For example, if we are constantly reaching out to third-party recruiters to help us find job leads, and the recruiters haven’t been very helpful in generating interviews, maybe we should backtrack and consider a different activity.

我們可以通過(guò)在每個(gè)步驟中評(píng)估我們的方法是否會(huì)實(shí)現(xiàn)我們的目標(biāo)(回溯)來(lái)優(yōu)化我們的方法。 例如，如果我們一直在與第三方招聘人員聯(lián)系以幫助我們找到工作機(jī)會(huì)，而招聘人員在進(jìn)行面試方面并不是很有幫助，那么也許我們應(yīng)該回頭考慮其他活動(dòng)。

Lastly, since job search is not a one day affair, we could try to optimize each day and combine days together (dynamic programming). This way we have a manageable problem to deal with (should I study algorithms today?) versus a really hard one (what should I do for the next month to prepare myself for job search?).

最后，由于求職不是一日游，因此我們可以嘗試優(yōu)化每一天并結(jié)合在一起(動(dòng)態(tài)編程)。 這樣，我們就可以解決一個(gè)可管理的問(wèn)題(我今天應(yīng)該學(xué)習(xí)算法嗎？)，而不是一個(gè)非常困難的問(wèn)題(下個(gè)月我應(yīng)該怎么做才能為找工作做準(zhǔn)備？)。

Finally, I just want to point out that with all 3 approaches, even though they were not objectively efficient, we did eventually reach a solution. While in the middle of job search, it’s really important to remember that in the long term, you will achieve your goal, and to keep pushing forward each day.

最后，我只想指出，盡管這3種方法客觀上都不高效，但我們最終還是找到了解決方案。 在求職過(guò)程中，切記從長(zhǎng)遠(yuǎn)來(lái)看，您將實(shí)現(xiàn)自己的目標(biāo)，并每天不斷前進(jìn)，這一點(diǎn)非常重要。

我對(duì)處理您的開(kāi)發(fā)人員求職的建議 (My advice for handling your developer job search)

I’m going to succumb to my temptation to give you two pieces of advice from my experience.

我將屈從于我的誘惑，從我的經(jīng)驗(yàn)中給您兩個(gè)建議。

If you’re looking for your first programming job, I hope reading this was useful or at least inspirational for you — look, a talentless duffer like me found a great job! Good luck out there and I’d like to close by sharing the best piece of advice given to me during my job search:

如果您正在尋找自己的第一份編程工作，我希望閱讀這篇對(duì)您有用或至少鼓舞人心-看起來(lái)，像我這樣的無(wú)才干的傻瓜找到了一份好工作！ 祝你好運(yùn)，我想在求職時(shí)分享給我最好的建議，以結(jié)束我的生活：

“Don’t worry about whether you’re good enough, worry about whether you like programming and whether you’re willing to work hard enough. If you do those two things, you’ll make it.” — paraphrased from Edgar Pabon on the Breaking Into Startups podcast

“不必?fù)?dān)心您是否足夠出色，不必?fù)?dān)心您是否喜歡編程以及是否愿意努力工作。 如果您做這兩件事，就會(huì)成功。” —摘自Edgar Pabon在Breaking Into Startups播客中的演講

Thanks for reading, and good luck with your job search!

感謝您的閱讀，并祝您工作順利！

翻譯自: https://www.freecodecamp.org/news/a-dynamic-framework-for-finding-your-first-programming-job-b4eb0605b4f3/

snapchat

總結(jié)

以上是生活随笔為你收集整理的snapchat_我刚刚在Snapchat获得开发人员职位。的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。