crontab 最小间隔

by Marin Abernethy

通过Marin Abernethy

今天我间隔了：如何找到不在数组中的最小数字 (Today I Spaced: how to find the smallest number that is not in the array)

TIS在我的第一次技术采访中。 这是我学到的。 (TIS in my first technical interview. Here’s what I learned.)

Today I Spaced in my first technical interview, and could barely rememberhow to console.log()let alone find an optimal solution.

今天，我在第一次技术面试中就离开了，几乎不记得如何console.log()更不用说找到最佳解决方案了。

First, a one sentence summary of my software journey: for a couple of years after my BA, I worked for a small software consultancy as a full stack developer before getting my Masters in Software Engineering, which I finished this year.

首先，用一句话总结一下我的软件历程：在获得文学学士学位后的几年中，我在一家小型软件咨询公司担任全栈开发人员，然后获得了今年的软件工程硕士学位。

Woah, ok. Maybe that should have been two sentences. Point is, I used to feel confident in my engineering capabilities, but the pressure of interviews has caused that confidence to wane slightly.

好的，好的 也许应该是两个句子。 重点是，我以前对自己的工程能力充满信心，但是面试的压力使这种信心略有减弱。

I spaced in my first technical phone interview today while live coding, but Ihope my Today I Spaced (TIS) moment will turn into a Today I Learned (TIL) after a walkthrough of my interview. Here goes nothing…

我今天在进行现场编码时进行了第一次技术电话面试，但希望我的今天我间隔(TIS)的瞬间将在我的采访演练后变成今天的我学到的(TIL)。 这里什么都没有...

问题 (The problem)

The interviewer framed the question in the context of the product the company builds, but it boils down to this: Given an array of integers, write a function that finds the lowest integer that is not in the array.

面试官在公司生产的产品的上下文中提出了这个问题，但归结为：给定一个整数数组，编写一个函数来查找不在数组中的最低整数。

For example, given the array, [5, 2, 1, 4, 0, 2] , the function should return 3.

例如，给定数组[5, 2, 1, 4, 0, 2] ，该函数应返回3 。

Simple, right? Let the spacing commence.

简单吧？ 让间隔开始。

我哪里做错了 (Where I went wrong)

Hmm where do I start? As soon as the interviewer finished explaining the question, internal panic ensued. I couldn’t think.

嗯，我从哪里开始？ 面试官解释完该问题后，立即产生了内部恐慌。 我没想到

Inner monologue: THINK Marin, THINK. Why aren’t you even trying to think about the problem? Aha! Google always knows. Yo Google, tell me what to do… Oh, wait I am supposed to talk. All of the advice online says I should talk through my thought process. Ahhh ok ok ok. I can't read and talk at the same time. Fine, bye Google.

内心独白： 思索马林，思索。 您为什么甚至不考虑这个问题？ 啊哈！ Google一直都知道。 Google哟，告诉我该怎么做...哦，等等，我应该谈谈。 网上所有的建议都说我应该仔细考虑一下自己的想法。 啊，好，好，好。 我不能同时阅读和交谈。 很好，再见Google

Outer monologue: “Ummm, ah, well… let's see. Hmmm. Yeah so, hm.”

外面的独白 ：“嗯，嗯...让我们看看。 嗯 是的，嗯。”

After a few minutes of hemming and hawing, plus a minute or two ofsilence, I came up with this solution (in JavaScript):

经过几分钟的折边和牵引，再沉默一两分钟，我想到了这个解决方案(使用JavaScript)：

Remember how I said I couldn’t even recall how to console.log()? Well, after completing my first attempt, I was confused when Coderpad ran my function and nothing appeared on the screen. The interviewer had to remind me that it was, indeed, compiling properly, I just needed to console.log() if I wanted to see the output in the console. Doh. Cue face to palm.

还记得我怎么说我什至不记得如何console.log()吗？ 好吧，在完成第一次尝试之后，当Coderpad运行我的功能时，我很困惑，屏幕上什么也没有出现。 面试官不得不提醒我，的确是正确地编译，如果我想在控制台中查看输出， console.log()需要console.log()即可。 h 提示面对手掌。

So I updated it: console.log(count). And it returned the correct answer! Wahooo! …Can I go home now?

所以我更新了它： console.log(count) 。 它返回了正确的答案！ 哇！ …我现在可以回家吗？

“Alright, now what is the time complexity of this algorithm?” the interviewer asked. I had printed out a list of different complexities to help me if it came up. Turns out I can’t read when I am nervous.

“好的，现在这个算法的时间复杂度是多少？” 面试官问。 我打印出了各种复杂性的列表，以帮助我解决问题。 原来，当我紧张的时候我不会读书。

THINK, Marin. THINK. Well, my solution is just a single loop, right? Loop === Constant was scribbled on my printout. So I said “Constant, O(n) time”, without giving it much more thought.

想想，马林。 认为。 好吧，我的解决方案只是一个循环，对吗？ Loop === Constant在我的打印输出上写有Loop === Constant 。 所以我说“常数，O(n)时间”，而没有多加思考。

WRONG. Yes, I did write one while loop. However, I failed to recognize the JavaScript includes() function as anything other than magic. When pushed on this point by the interviewer, I realized that includes() is also iterating through the array each time. So really, its O(n²) time complexity. Cue face to palm round two.

错误 。 是的，我确实编写了一个while循环。 但是，我无法将JavaScript includes()函数识别为魔术以外的任何东西。 当面试官将这一点推到这一点时，我意识到includes()每次也在遍历数组。 确实，它的O(n²)时间复杂度。 提示面对掌第二轮。

For one brief moment, the wheels started turning. What data structures have I been reading about? Linked List? Doesn’t seem helpful. Stack? Nah. HashTable? Aha!

片刻之间，车轮开始转动。 我一直在阅读什么数据结构？ 链表？ 似乎没有帮助。 堆栈？ 没事 哈希表？ 啊哈！

寻求解决方案 (Towards a Solution)

Attempt number two:

尝试第二：

So I figured I could map each integer in the array to their frequency. Upon review of this solution post-interview, I realized it is unnecessary to keep track of how many times an integer appeared in the array. We just need to know whether it appeared at all, so the boolean true would have sufficed. Either way, this is O(n) time complexity.

所以我想可以将数组中的每个整数映射到它们的频率。 在面试后对该解决方案进行审查后，我意识到没有必要跟踪整数在数组中出现了多少次。 我们只需要知道它是否完全出现即可，因此布尔值true就足够了。 无论哪种方式，这都是O(n)时间复杂度。

Due to the limited remaining time, the interviewer asked me how I would solve this with only arrays. Ding! I said, “you could sort the array, and then iterate through it until there is a missing number”. Here is what I meant by that:

由于剩余时间有限，面试官问我如何仅使用数组来解决此问题。 ing！ 我说：“您可以对数组进行排序，然后对其进行迭代，直到缺少数字为止”。 这就是我的意思：

Looking back, I see that not only could I have given a clearer explanation, but I should also have discussed the tradeoffs between this and my hashmap solution. That is, because this solution is done in-place, the space complexity is O(1) which is superior to the hashmap solution with O(n). However, it is safe to assume the sorting algorithm is O(n log n) time complexity, which is less efficient than the previous solution.

回顾过去，我不仅可以给出更清晰的解释，而且还应该讨论此方法与我的哈希图解决方案之间的权衡。 也就是说，因为此解决方案是就地完成的 ，所以空间复杂度为O(1)，优于具有O(n)的哈希图解决方案。 但是，可以安全地假设排序算法的时间复杂度为O(n log n)，这比以前的解决方案效率低。

Sigh. More practice! More Interviews! Stay tuned.

感叹 。 多练！ 更多面试！ 敬请关注。

TL; DR (TL;DR)

My brain, given the choice of fight or flight, when faced with an intimidating technical interview, chose flight. Maybe with a little more practice, it will choose to fight next time.

面对激烈的技术面试时，考虑到战斗还是逃跑，我的大脑选择了逃跑。 也许再多练习一下，它将选择下次战斗。

Note to self:

注意自我：

• Talk through a solution before coding it up. This may help you discover a more efficient solution sooner (e.g. the interviewer can be more than a sounding board, they sometimes give hints)
  在编写解决方案之前先讨论一下解决方案。 这可以帮助您及早发现更有效的解决方案(例如，面试官可能不仅是一个共鸣板，有时还会提供提示)
• Yes, talking through your answer is important, but not to the detriment of your final solution. Take a beat to think, if necessary.
  是的，讨论您的答案很重要，但不会损害您的最终解决方案。 如有必要，请稍作思考。
• Internal JavaScript functions aren’t magic! They have time and space complexity too.
  内部JavaScript函数不是魔术！ 它们也具有时间和空间复杂性。

翻译自: https://www.freecodecamp.org/news/tis-find-the-smallest-integer-that-is-not-in-the-array-80479cec15e4/

crontab 最小间隔