Common Algo Problem Solutions | Hacker News Reader

Common Algo Problem Solutions

github.com

113 pointsJames9923 comments

Open articleView on HN

So are these just copied from leetcode? For example, leetcode's hamming distance versus yours:

LeetCode:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Yours:

1)Hamming Distance The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance.

Another one, LeetCode:

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Yours:

2)Single Number Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Yes, many problems are the same as leetcode problems. The purpose of this repo is just learning.

First this doesn't include any statements of the specifics of the algorithm problems, which can be extremely relevant. Second there are errors, for example the code the return all duplicates in array is just broken, and even if you fix the obvious errors like indexing and modifying the array you are examining, it will still not handle values of 0 or less.

I wonder if it makes sense for larger companies like Google to intentionally plant online unconventional solutions that seem plausible but have subtle errors. Better still if they point out the errors and give a plausible-sounding argument for why they don't apply, that the person then later repeats during the interview without disclosing that he's seen the problem before.

I wonder if there's a way to make money from cheaters caught in the act. The only thing I can think of is making reimbursement of travel expenses conditional on not cheating. Or encouraging them to somehow gamble money on the assumption their solution is correct.

Just using unconventional language to describe the solution could be a good signal: People learning something new often use the same words as the source material.

> I wonder if there's a way to make money from cheaters caught in the act

You would certainly save money.

Your argument reads a bit like a conspiracy theory to me, but it's definitely one of the more fun and reasonable ones I've read. :)

I was personally wondering why the "find duplicates" algorithm multiplied every number by -2. Maybe there is some reason, but I don't know what it could be.

I'd like to know how this is 'cheating'. The questions are quite simply memorization problems as the difficulty increases especially. You don't have to disclose you've seen a problem before. These types of interview questions are already terrible, and now you are expecting interviewees to intentionally make it harder for themselves.

I don't get this anti-worker attitude. However I'm not surprised to see it on HN

Algorithm problems are supposed to be solved by thinking, not memorization.

That's just plain wrong. What happens if you need for example ukonnens algorithm for creating a suffix tree? Good luck deriving that on your own. Similarly Fourier transforms. Memorizing what algorithms do and what types of problems they can solve is essential to being a programmer, and besides that it's simply faster.

I agree that memorizing algorithms is useful. That said, Google interview questions are usually much easier than deriving Ukkonen's algorithm or FFT on your own. They are more like "given a rotated sorted array, find a given value quickly". Well, a bit harder than that, but solvable in 40 min.

That's the theory.

In practice recent prior exposure to the problem and possible solutions makes answering such a question far easier, so the most prepared for the questions wins. They don't test thinking, they test preparation.

Not only that, but some worker may be well prepared without even noticing. And without any bad intentions to trick you.

This happened to myself (although in a non-interview situation):

In general, if you have solved many problems and looked at many solutions, you simply won't remember each specific problem. This effect may start as early as your first math olympiad, and will only get worse on university while you study math and/or computer science.

Some time ago I solved a math puzzle, where I got the right ideas relatively quickly, even though I was convinced this problem was new to me. Later I found out in my writings that I actually solved exactly that problem some years ago.

Even though I was unable to remember the exact solution, not even remembered I've seen it before, I seem to have internalized enough clues so I could rediscover the exact solution whenever I need it.

You are right, thinking logically is always better option than memorizing solutions. To have a good thinking ability, one needs practice. Solving many problems leads you to think different approaches, compute running time and space complexity of your solution before writing code to any problem. I think, this is one of the best ways to improve "thinking".

This is not really cheating, but it would help you weed out people who don't check the sources they learn from, which is also valuable.

>"I wonder if there's a way to make money from cheaters caught in the act."

Wait, practicing problem solving is somehow "cheating"?

So we have an industry where a handful of SV companies have found that algorithmic parlor games are an indication of good hire vs bad hire. The rest of the industry has simply decided to mimic this practice with reasoning that goes "if Google's doing it it must be the right thing to do.", with no thought that Google's reality has so very little to do with their own.

So now that algorithm challenges are the bog standard for interview it would stand to reason that you would best yourself by studying or practicing some example problems. B that somehow is considered "cheating." So you are either born with these skills or you are not is that correct?

That is patently absurd.

So to weed out those who obviously did some studying we should seed the internet with misinformation in order to catch these "cheaters"? Is the thinking - if you weren't born with the skills to write a function to "search for the missing integer in a matrix that has been rotated by k elements" you probably aren't a good programmer?

Thank you for your comment, I added all problem statements. Find Duplicates are correct and tested against 100 test cases. Problem statement is not what u thought I think. Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array.

The link to hard interview questions is broken, the first letter of the file name is actually capital

i fixed the link, thanks (y)

Most of these don't include any commentary about the intuition behind the solutions which is just as important as code. A few do but most of these don't.

Agreed. This is a terrible source.

For example, the rotate array is much better handles with a deque; you get amortized constant time rotations.

Right, Deque is also another option, which has the same amortized time complexity and but extra O(n) space is required for Queue. In the given solution, O(n) time complexity and O(1) space is used

more like here's another list of algorithms I need to know that's been featured here on hacker news a gazillion times

Thought this was about Algo VPN. [1]

1. https://github.com/trailofbits/algo

Is there a decent algorithm book series that will go in detail the logic behind each question?

Reply on news.ycombinator.com