问:
Complexity analysis: Finding common members of unsorted arrays
I've been going over previous tech interviews I've had (got another one coming up).

The problem

Anyway, one question I had was...

Given 2 unsorted arrays how would you find all of the common objects between them?

Say I have array A and B. Worst case A and B are both of size n.

Initial thought

Initially my thought was to iterate A and do a linear search through B.

The complexity for this is O(n) * O(n) = O(n^2).

Sorting first

However, I was wondering if it would be better to sort B first.

Using a quick sort (or merge sort) on B is O(n log(n)). This is done once.

Now you can iterate A O(n) and do a  binary search on B O(log(n)) for each A.

So the complexity is (sort) O(n log(n)) + (iterate A) O(n) * (search B) O(log(n)) which simplifies down to O(n log(n)).

My question is. Am I right with this? I am very new to complexity analysis so wanted to check that I'm not doing anything stupid.

Best solution

Is the best solution then to sort one array first before iterating the other? You could sort both arrays and then iterate but you're not improving O(n log(n).

Is there another better way of approaching this?

答:
Why not use a Hash Set? Most implementations of the add() method, which is used to inject items in the set return a boolean indicating if an item was inserted or not. Insertion will return false if the item was already there. So your code would look like:

```<code>HashSet<int> set = {}
Array<int> items1 = ...
Array<int> items2 = ...

foreach (item in items1)
    set.add(item)

foreach(item in items2)
    if(set.add(item) == false)
        out >> item is duplicate
</code>```

This would yield a time complexity of 2n, since hash sets have a constant O(1) fetch time.

If I remember correctly, O(2n) (which reduces to O(n)) would be less than O(n log(n)). This assumes that you do not need to optimize in terms of space.

Body:
Why not use a Hash Set? Most implementations of the add() method, which is used to inject items in the set return a boolean indicating if an item was inserted or not. Insertion will return false if the item was already there. So your code would look like:

HashSet<int> set = {}
Array<int> items1 = ...
Array<int> items2 = ...

foreach (item in items1)
    set.add(item)

foreach(item in items2)
    if(set.add(item) == false)
        out >> item is duplicate

This would yield a time complexity of 2n, since hash sets have a constant O(1) fetch time.

If I remember correctly, O(2n) (which reduces to O(n)) would be less than O(n log(n)). This assumes that you do not need to optimize in terms of space.


答:
You can't possibly do better than O(n), since you have to examine each element at least once to ensure there is a match or not.  My first choice would be to convert the arrays to sets, which is O(n), then take their intersection, which is O(n) on the smallest set.  In python:

```<code>set(array1) & set(array2)
</code>```

If you have to do it in place, which is sometimes a restriction in these sorts of exercises, your solution is pretty good.

ContentLicense: CC BY-SA 3.0

Title: Complexity analysis: Finding common members of unsorted arrays

Body:
I've been going over previous tech interviews I've had (got another one coming up).

The problem

Anyway, one question I had was...

Given 2 unsorted arrays how would you find all of the common objects between them?

Say I have array A and B. Worst case A and B are both of size n.

Initial thought

Initially my thought was to iterate A and do a linear search through B.

The complexity for this is O(n) * O(n) = O(n^2).

Sorting first

However, I was wondering if it would be better to sort B first.

Using a quick sort (or merge sort) on B is O(n log(n)). This is done once.

Now you can iterate A O(n) and do a  binary search on B O(log(n)) for each A.

So the complexity is (sort) O(n log(n)) + (iterate A) O(n) * (search B) O(log(n)) which simplifies down to O(n log(n)).

My question is. Am I right with this? I am very new to complexity analysis so wanted to check that I'm not doing anything stupid.

Best solution

Is the best solution then to sort one array first before iterating the other? You could sort both arrays and then iterate but you're not improving O(n log(n).

Is there another better way of approaching this?

Body:
You can't possibly do better than O(n), since you have to examine each element at least once to ensure there is a match or not.  My first choice would be to convert the arrays to sets, which is O(n), then take their intersection, which is O(n) on the smallest set.  In python:

set(array1) & set(array2)

If you have to do it in place, which is sometimes a restriction in these sorts of exercises, your solution is pretty good.


答:
I don't think that there's a better answer for worst case complexity in the general case. You could probably only improve specific cases in which the input is somehow limited (say numbers between 1 and N). In that case you could use something like a Radix sort.

Karl Bielefeldt's idea of converting the arrays to sets doesn't solve the problem, it only hides it since intersecting sets (in the general case) is done in O(n^2). For instance, here's Java's retainAll() implementation:

```<code>public boolean retainAll(Collection<?> paramCollection) {
        int i = 0;
        Iterator localIterator = iterator();
        while (localIterator.hasNext()) {
            if (!(paramCollection.contains(localIterator.next())))
                ;
            localIterator.remove();
            i = 1;
        }

        return i;
    }
</code>```

Note the iteration on the incoming collection. For each element, the method calls contains, which iterates over the elements of the current set:

```<code>public boolean contains(Object paramObject) {
        Iterator localIterator = iterator();
        if (paramObject == null)
            while (true) {
                if (!(localIterator.hasNext()))
                    break label53;
                if (localIterator.next() == null)
                    return true;
            }
        while (localIterator.hasNext()) {
            if (paramObject.equals(localIterator.next()))
                return true;
        }
        label53: return false;
    }
</code>```

npinti's solution of using a HashSet is equally problematic. A HashSet doesn't guarantee O(1) fetch time in the worst case. In fact, if the hashes of all N elements collide, you're looking at O(n) fetches/inserts. This brings us back to O(n^2) worst case time.

Body:
I don't think that there's a better answer for worst case complexity in the general case. You could probably only improve specific cases in which the input is somehow limited (say numbers between 1 and N). In that case you could use something like a Radix sort.

Karl Bielefeldt's idea of converting the arrays to sets doesn't solve the problem, it only hides it since intersecting sets (in the general case) is done in O(n^2). For instance, here's Java's retainAll() implementation:

public boolean retainAll(Collection<?> paramCollection) {
        int i = 0;
        Iterator localIterator = iterator();
        while (localIterator.hasNext()) {
            if (!(paramCollection.contains(localIterator.next())))
                ;
            localIterator.remove();
            i = 1;
        }

        return i;
    }

Note the iteration on the incoming collection. For each element, the method calls contains, which iterates over the elements of the current set:

public boolean contains(Object paramObject) {
        Iterator localIterator = iterator();
        if (paramObject == null)
            while (true) {
                if (!(localIterator.hasNext()))
                    break label53;
                if (localIterator.next() == null)
                    return true;
            }
        while (localIterator.hasNext()) {
            if (paramObject.equals(localIterator.next()))
                return true;
        }
        label53: return false;
    }

npinti's solution of using a HashSet is equally problematic. A HashSet doesn't guarantee O(1) fetch time in the worst case. In fact, if the hashes of all N elements collide, you're looking at O(n) fetches/inserts. This brings us back to O(n^2) worst case time.


问:
Question on RC4 algorithm
I started reading RC4 from a book and was not able to understand some phrases correctly.

The RC4 algorithm is remarkably simple and easy to understand. A variable length key of from 1 to 256 bytes is used to initialize a 256-byte state vector S. At all times S contains a permutation of all 8-bit numbers from 0 to 255.

From the above my interpretation is that if suppose we use Java as our programming language

Each character is 2 bytes and the key length can be from 1 till 128(256/2)length long.

A vector/extendable-array is created array is created. But what is the length of the array? Is the size of array is 256?

At all times array S contains a permutation of all the 8-bit numbers from 0 to 255? Could someone explain this to me.

Kindly help me as I am feeling lost in my first chapter to study cryptography.

答:
RC4 is applied bytewise, regardless how long a simple character is. There were times where a character was one byte, but today those (old) characters mean bytes. To be consistent with current implementations and in case of ASCII-characters (those whose ordinal number is less than 128) you should chop the (upper) byte containing the zero. "password" has a length of 8 and will be applied 32 times in the initial permutation step. Otherwise the permutation-array will contain artifacts, if only every "second" byte is effectively used for permutation.

the KSA of RC4

```<code>for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor
</code>```

If you use 2 bytes per ascii char, one of the bytes will contain a "0" for every second byte. For every second password byte the key-schedule-algorithm will reduce to:

```<code>for i from 0 to 255
    j := (j + S[i] + 0) mod 256
    swap values of S[i] and S[j]
endfor
</code>```

Wich makes the permutation of S and the inner state exploitabe. If the first password byte is null, then S[0] is swapped with S[0], which is no swap at all. I suggest you make some experiments on that - it could be interesting for you - S[0] may later been exchanged but maybe not. And it may also be exchanged with one of those other unlucky bytes. Which may lead to a more or less constant permutation values on certain values of S[i].

The security of this algorithm is dependend on the secrecy of the permutation of S. But if you can guess some of the bytes of S by knowing some of password properties, you can effectively reduce uncertaincy as an attacker.

The streamcipher itself is applied byte wise. The RC4 pseudorandom stream is a stream of bytes and your data to encrypt is a stream of bytes.

"At all times array S contains a permutation of all the 8-bit numbers from 0 to 255"

The array S has a length of 256 bytes, it contains every possible byte (8bit => 2^8) exactly once. At the start S is ordered in that way, that S[0]=0 .. and S[255]=255. Each Password byte will exchange two elements with each other. All the elements from 0 to 255 are still there, but not at the position as before. S is the internal state after applying of the password (this state is hidden/secret and not known to anyone but you). Your password is the key, how to create this special and hopefully unique permutation.

hth. please ask if i missed to explain something.

Title: Question on RC4 algorithm

Body:
RC4 is applied bytewise, regardless how long a simple character is. There were times where a character was one byte, but today those (old) characters mean bytes. To be consistent with current implementations and in case of ASCII-characters (those whose ordinal number is less than 128) you should chop the (upper) byte containing the zero. "password" has a length of 8 and will be applied 32 times in the initial permutation step. Otherwise the permutation-array will contain artifacts, if only every "second" byte is effectively used for permutation.

the KSA of RC4

for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

If you use 2 bytes per ascii char, one of the bytes will contain a "0" for every second byte. For every second password byte the key-schedule-algorithm will reduce to:

for i from 0 to 255
    j := (j + S[i] + 0) mod 256
    swap values of S[i] and S[j]
endfor

Wich makes the permutation of S and the inner state exploitabe. If the first password byte is null, then S[0] is swapped with S[0], which is no swap at all. I suggest you make some experiments on that - it could be interesting for you - S[0] may later been exchanged but maybe not. And it may also be exchanged with one of those other unlucky bytes. Which may lead to a more or less constant permutation values on certain values of S[i].

The security of this algorithm is dependend on the secrecy of the permutation of S. But if you can guess some of the bytes of S by knowing some of password properties, you can effectively reduce uncertaincy as an attacker.

The streamcipher itself is applied byte wise. The RC4 pseudorandom stream is a stream of bytes and your data to encrypt is a stream of bytes.

"At all times array S contains a permutation of all the 8-bit numbers from 0 to 255"

The array S has a length of 256 bytes, it contains every possible byte (8bit => 2^8) exactly once. At the start S is ordered in that way, that S[0]=0 .. and S[255]=255. Each Password byte will exchange two elements with each other. All the elements from 0 to 255 are still there, but not at the position as before. S is the internal state after applying of the password (this state is hidden/secret and not known to anyone but you). Your password is the key, how to create this special and hopefully unique permutation.

hth. please ask if i missed to explain something.


问:
Open Source license that prevents from bundling with adware?
I wrote a small tool I published on my blog. I did not even think about the license, just put the binaries there for everyone to download. Now I am thinking about making it open source (BSD or GPL) but have already seen that my tool was available for download on other sites that bundle it with their own installer which also installs Browser-Addons aka. Adware. (we all know this crap)

Is there an open source license that forbids this but still allows the usage as open source? If not? May the GPL be modified to fit these conditions?

答:
There's no such major license, as

FOSS licenses' primary goal is to maintain the "four freedoms" (or a part thereof for permissive licenses). Any restrictions on possible future functionality (even the odious DRM that Stallman asserts to have no place in the future1) are seen as highly undesirable and are gonna condemn a license as "incompatible"

in licenses that allow relicensing, such a provision is pointless as it can easily be removed with the entire license. In licenses that require to provide source code, it's pointless as well since, if the software ever gets contaminated with adware, any user can remove it with relative ease.

Regarding bundles, e.g. GPLv3 specifically requires that

"the compilation and its resulting copyright are not used to limit the
  access or legal rights of the compilation's users beyond what the
  individual works permit"

(otherwise, the work isn't considered an "aggregate" so GPLv3 applies to the entire thing, meaning the author immediately infringes it).

@c561302:

I believe that forcing a user to perform an installation (that they might not even be able to do in their environment) to access the source code does "limit the access or legal rights of the compilation's users beyond what the individual works permit".

Even in the remote case it doesn't, this provision from section 6 still limits the opportunity for "drive-by installs":

Corresponding Source conveyed... must be in a format that is publicly documented (and with an implementation available to the public in source code form), and must require no special password or key for unpacking, reading or copying.

by requiring that the (installation) package containing the source code must be publicly documented and have an "implementation available to the public in source code form" (the latter, I believe, means an unpacker in this case as the clause applies to the ability to "unpack, read or copy"). I.e. it effectively treats an installation package as a compound file.

1GPLv3 section 3 bans software covered by it from having legal rights associated with DRM regarding its circumvention. Which means, it doesn't limit functionality per se even in this case

OwnerDisplayName: Ole Albers


问:
Where can I find design exercises to work on?
I feel it's important to continue practicing my problem-solving skills. Writing my own mini-projects is one way, but another is to try and solve problems posted online. It's easy to find interesting programming quizzes online that require applying clever algorithms to solve - Project Euler is one well-known example.

However, in a lot of real-life projects the design of the software - especially in the initial phases - has a large impact and at later stages it cannot be tweaked as easily as plain algorithms. In order to improve these skills, I'm looking for any collection of design problems.

When I say "design", I mean the abstract design of a software solution - for example what modules will there be and what are the dependencies between them, how data will flow in the program, what sort of data needs to be saved in the database, etc. Design problems are those problems that are critical to solve in the early stages of any project, but their solution is a whiteboard diagram without a single line of code.

Of course these sort of problems do not have a single correct solution, but I'll be especially happy with any place that also displays pros and cons of the typical solutions that might be used to approach the problem.

答:
Start with the classic design problem: KWIC.

David Parnas used KWIC as an example in his classic paper on modularity: On the Criteria To Be Used in Decomposing Systems into Modules, which everyone should probably read every 10 years.

KWIC, for key-word in context, is a simple indexing and sorting problem where you read in lines of text, and then rotate each line based on keywords (e.g., excluding "the", "with"), adding each shift to a list you then sort. The idea is that using KWIC would be useful for generating an index for a book. At the time of his classic paper, Parnas said that an experienced programmer could solve it in one to two weeks, but Yannis's Law states that it can now be done in one to two hours. [Operating systems and standard libraries have gotten much better.]

Read through Parnas's paper, and as soon as you can grok what the KWIC program is supposed to do, go and write your own as a design exercise. Then, read the rest of the paper, which discusses two different designs: Both are modular, but one achieves information hiding while the other does not.

After knowing the KWIC example, you'll be able to appreciate other software design papers that use it. For example, Michael VanHilst's paper Decoupling Change from Design uses it to show a really interesting design technique using C++ templates. And, so long as we are talking about C++ templates and design, read Czarnecki and Eisenecker's Synthesizing Objects paper.

Moving on from KWIC are other classic examples, such as the Spacewar example, which has been ported/redesigned in several languages, such as Python and AspectJ.

Of course, any program can be used as a design exercise, but KWIC and Spacewar are examples where you can look at several alternatives.

ContentLicense: CC BY-SA 2.5


问:
How can I team up two MVC frameworks without having them fight each other?
I'm creating a CRUD-based web project, and am thinking about using a server side MVC framework (such as CodeIgniter or Laravel) in tandem with a client side MVC framework (such as AngularJS). Is this a fairly common approach? After all, it's clear that I need something on the server, and that doing MVC on the client as well can enhance my application. But I feel that two MVC frameworks on the same project would just get in the way of each other and lead to disproportionate complexity and repetition.

What kind of approach or architecture would help me get the best out of both MVC frameworks when using one on the client, the other on the server?

答:
You can use angularjs for the front-end and codeigniter or another php framework for the back-end without any issues.  You just have to keep in mind that both are MVC (Model-View-Controller).

Why use similar concepts but with different structures? Because angularjs works with template HTML and  all views are HTML (not including the header and footer).  As an example,  with a form contact you just have to specify on the template HTML the div for ng-view (to load the views angularjs).  And on the nav for the application you have to specify the controller and source view and on the app.js have you code for provider the router wich template have to load each time.

For codeigneter you have to create the controller and model to create the interaction with the database if you need it.  But keep in mind that codeigneter can define routes more easily.  You just have to load the views with an extension of .php where that views will have only the HTML like angular views.

You can work with multiple frameworks like CSS + angularjs + codeigneter or other MVC framework.

For forms validation, you can use the forms validation from the framework CSS and not use the angularjs.  And just use angularjs to communicate with the framework MVC and to send the data using JSON.

I don't know if you follow my idea but in technology you can integrate everything to create a robust and strong app.  But sometimes you will take only a part of each framework and not use all 100% of it.


问:
How to offer money to an open source project?
There's an open source project on GitHub that is very useful, but doesn't have a feature I want and which a fair number of other users have been clamoring for in the issues.

There's already an advanced discussion of the issue, and I get the impression that good_enough is pretty feasible, it's just stalled because perfect is complicated, and good_enough !== perfect.

The Right™ way to go would be to to absorb the discussion, add the feature, present a pull request, address the critiques and polish it for contribution. In this case it's outside my core focus.

It's a utility library, developed for actual work not just for games, so an alternative way might be to offer to sponsor that feature with money. But that doesn't seem like the done thing, can't find any examples. Could try hiring this out but the best people for it seem like those already thinking about it.

What's a polite way to proceed?  Or just wait and see if the feature gets added organically?

答:
Personally I believe the best option would be to out-source the work (perhaps on Freelancer or something along those lines) so that you personally have the features you desire.

Thereafter you can offer the patch back to the community, and it'll be their decision whether or not to adopt it. At the end of the day, this solution will be functional for you as an individual.


问:
MJRTY - A Fast Majority Vote Algorithm isn't work
The MJRTY algorithm sets out to solve the problem of finding the majority element in a stream (an element comprising more than 50% of the stream). Moore proposed to solve this by using only 2 pieces of information and a single scan of the data.
Imagine you have a stream of names (“matt”, “timon”, “matt”, “matt”, “rob”, “ben”, …) and you wanted to know if any name appeared in more than half the stream. Boyer and Moore proposed the following:

```<code>count = 0
majority = ""

for val in stream:
    if count == 0:
        majority = val
        count = 1
    elif val == majority:
        count += 1
    else:
        count -= 1
print majority if count > 0 else "no majority!"
</code>```

if stream = A A A A B B B B C => result = C, but it isn't truth.

step by step

```<code>step    val majority    count
0   A   A   1
1   A   A   2
2   A   A   3
3   A   A   4
4   B   A   3
5   B   A   2
6   B   A   1
7   B   A   0
8   C   C   1
</code>```

About this algotithm: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

答:
```<code>Input          count          majority
A                1              A
A                2              A
A                3              A
A                4              A
B                3              A
B                2              A
B                1              A
B                0              A
C                1              C
</code>```

Count is not greater than 0.  "no majority!"

Body:
Input          count          majority
A                1              A
A                2              A
A                3              A
A                4              A
B                3              A
B                2              A
B                1              A
B                0              A
C                1              C

Count is not greater than 0.  "no majority!"


答:
The Boyle-Moore algorithm only works if there is a majority, indeed. It is useful if you can assume that there is a majority, for instance when processing binary strings composed of 0 or 1: if the length of the string is odd, then you must have a majority.

The sequence A A A A B B B B C has 9 elements, so you need at least 5 occurences of an element to have a majority, and you don't have it. The result is therefore not significant.

Title: MJRTY - A Fast Majority Vote Algorithm isn't work

Body:
The MJRTY algorithm sets out to solve the problem of finding the majority element in a stream (an element comprising more than 50% of the stream). Moore proposed to solve this by using only 2 pieces of information and a single scan of the data.
Imagine you have a stream of names (“matt”, “timon”, “matt”, “matt”, “rob”, “ben”, …) and you wanted to know if any name appeared in more than half the stream. Boyer and Moore proposed the following:

```<code>count = 0
majority = ""

for val in stream:
    if count == 0:
        majority = val
        count = 1
    elif val == majority:
        count += 1
    else:
        count -= 1
print majority if count > 0 else "no majority!"
</code>```

if stream = A A A A B B B B C => result = C, but it isn't truth.

step by step

```<code>step    val majority    count
0   A   A   1
1   A   A   2
2   A   A   3
3   A   A   4
4   B   A   3
5   B   A   2
6   B   A   1
7   B   A   0
8   C   C   1
</code>```

About this algotithm: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/


问:
Is it wise for a high level developer to spend time studying assembly?
It is clear that the knowledge of low level stuff is very important in our work.

But in a situation where you're already developing commercial software on a high level, and when you already have a chosen direction but don't have any assembly skill, isn't it more reasonable to focus on studying stuff related to your direction? Or is there a reason you should spend some time to learn the low-level basics anyway?

When is it too late, and when it is not? And if it is not too late, then how would one go about learning optimally (in the sense of not spending excessive time to get some depth and understanding)?

答:
You will always benefit from peaking under the covers and understanding a bit more about the what sits beneath the abstraction you are standing on top of.  As a college professor of mine stated once "All good programmers understand the hardware" -- you don't have to be able to create and manipulate circuits, but you should have some grasp of whats going on down there -- it will only make you better.

Try Computer Organization and Design


问:
Mixing BSD + GPL, and dual licensing
I am the sole author of a piece of C++ software which so far I have kept under the GPL license. For uninteresting reasons, I am considering a switch to a MIT/BSD style license. As far as I have understood, this would prevent, in the future, to use any kind of GPL component (library, header, plugin, etc.) in my MIT/BSD licensed software.

Would it make any sense then to dual-license the software under both BSD and GPL? I would add a switch in the build system to enable/disable the component of my software that relies on GPLed 3rd party code and document that, if the user builds the software with that option enabled, then she must choose the GPL license. Otherwise, she is able to choose whichever license she likes.

Would that be a suitable course of action? How should I word this in a README file?

答:
I am not a lawyer and this isn't legal advice.

If I really had to do what you're asking, I would release two separate versions, one licensed GPL with the GPL'd component, and one licensed BSD without the GPL'd component.  I don't think it would work to have one distribution with both "versions" in it because GPL is triggered by distribution, so since you're distributing something that has a GPL'd component in it, you have to release it under the GPL.  This is a case where I'd want to keep it separate to avoid any ambiguity, and your users would like to avoid ambiguity too.

When I was looking at the Qt framework a few years ago, they had dual license options, but from what I remember you had to choose one license or the other, and for some reason they said you weren't allowed to change your mind later (if you started developing your application under the GPL, you weren't then allowed to change to a different license).  My memory is vague, but it's an indication that you have to be careful.

Title: Mixing BSD + GPL, and dual licensing


问:
Caveats of using String.hashCode() on a switch on java < 1.7
There are several cases when I want to switch over a String input. I decided for implementing something like:

```<code>public Object doStuff(String param) {
    switch (param.hashCode()) {
    case 1234546:
         break;
    case -18754956:
         break;
    default:
         whatever();
    }
}
</code>```

It works as intended, but there is this feeling that something can go awry.

What are the possible pitfalls of using that implementation? I am bound to use java 1.5 or 1.6 because corporate dictates so (therefore I cannot upgrade to 1.7 or later).

Is there some better implementation of a switch over Strings other than a monstruous chain of if-then-else (for the purpose of this question, lets assume I cannot do if-then-else over every possible String value of the input)?

related: What is the benefit of switching on Strings in Java 7? but I am asking pre-1.7

答:
When you compare two strings using their hash codes:

If two hash codes are different, it means that strings are different,

If two hash codes are identical, this doesn't mean anything. The original strings may be identical, or different.

In the same way, a different string length indicates that two strings are different, but if you have the same length, it doesn't mean that two strings are equal.

This is why if you need to perform an action based on the user input, you should use the original string, not its hash code. Having a switch based on the string itself is one way to go. Another alternative you should consider is a map.

The benefit of a map is that you can change it at run time, for instance by defining the different inputs and their corresponding actions in a configuration file. This can also be useful if you are switching over long strings which would be weird hadcoded within a switch statement.


答:
Hash codes are not unique. There are numerous strings which hash to, say, 1234546. If you want to check for the string "foo" and the unrelated, meaningless string "bar" has the same hash, your code will falsely treat "bar" the same as "foo" rather than rejecting it/going to default.

Fixing this is generally possible (check whether the value really equals the intended string in each case), but it's quite a bit of extra code, especially if there is a default case (since you have to transfer control out of the "wrong" case and to the default case). This is how the switch-over-string feature proposal desugars it. It's not pretty.

Hash codes are not meaningful. Someone has to find out the hash code and hard-code them, and the code has more meaningless magic numbers. You can and should of course write the string in a comment next to the integer literal, but it's still a maintenance burden.

Technically, the hash algorithm might also change when the JVM is updated or when the deployment environment is changed, etc. — depending on the JVM, maybe even when the JVM is restarted! And then the code would be silently wrong. This probably won't actually happen (I think the implementation of Java 7 switch-over-string depends on the compiler being able to predict the hashCode value of string literals).

Title: Caveats of using String.hashCode() on a switch on java < 1.7

Body:
There are several cases when I want to switch over a String input. I decided for implementing something like:

```<code>public Object doStuff(String param) {
    switch (param.hashCode()) {
    case 1234546:
         break;
    case -18754956:
         break;
    default:
         whatever();
    }
}
</code>```

It works as intended, but there is this feeling that something can go awry.

What are the possible pitfalls of using that implementation? I am bound to use java 1.5 or 1.6 because corporate dictates so (therefore I cannot upgrade to 1.7 or later).

Is there some better implementation of a switch over Strings other than a monstruous chain of if-then-else (for the purpose of this question, lets assume I cannot do if-then-else over every possible String value of the input)?

related: What is the benefit of switching on Strings in Java 7? but I am asking pre-1.7


问:
Is this pattern RESTful? Or something else?
I'm working on a new project that will create a web-based API to perform CRUD operations on a relational database.

Originally, I was going to create the API as http-based, and make it RESTful so that - for example - operations on a person record might look like:

```<code>PUT /api/person/create/Sally/Smith/ssmith@acmeco.com
</code>```

or

```<code>GET /api/person/findByEmail/ssmith@acmeco.com
</code>```

For Create and Read.

However, I've since swapped out the http layer (node/express) for an http/ websockets layer (node/express.io). I've created realtime routes so that now, once a client has an open socket connection, they could perform the same actions as above with:

```<code>socket.emit('person:create', {firstname: 'Sally', lastname: 'Smith', email: 'ssmith@acmeco.com'});
</code>```

and

```<code>socket.emit('person:select', {email: 'ssmith@acmeco.com'});
</code>```

In one sense, this kinda sorta meets the constraints of REST (it is client/server, it is "stateless" in that no request relies on a prior request, etc.) but it feels like calling this pattern "RESTful" is wrong.

Is it? If it's not REST, what is it?

答:
There are a few things that make this API not very RESTful:

REST API URLs identify resources, not actions. First, actions should not be part of the URL path. The actions are the different HTTP methods. Instead of doing something like GET /api/person/findByEmail/ssmith@acmeco.com, you should remove findByEmail and use query parameters to convey that you're searching by email, e.g. GET /api/people?email=ssmith@acmeco.com. Notice that I also changed from person to people, since collections should generally be noted as plurals of the resources they contain. This resource reads as 'People who have the email address ssmith@acmeco.com', and with the GET method your request becomes 'Get me the people who have the email address ssmith@acmeco.com'.

Second, PUT should always be idempotent, and the way you're using it is not. In other words, if the PUT method accidentally gets called more times than it was meant to, it won't really matter.

When to use PUT: When you are placing a resource at a specific location, e.g. if you want to put a song resource at /api/playlists/5/tracks/1. If this gets called more than once, it won't really have a different outcome. Note, placing something might even mean placing something that wasn't previously in the system. PUT can create a resource on the back-end or in the persistence layer somewhere if it doesn't already exist before placing it at the specified location. The key point here is you're not saying 'create a user and give me a URL to reference said user', you're saying 'create a user that looks like this and put said user at this URL'. This request could read as 'Put the following song as the first track in playlist 5'

When to use POST: When you are creating a resource, and it's up to the server to create a URL for the resource. An example would be creating a user, much like you're trying to do, which could be done as so: POST /api/people?firstName=Sally&lastName=Smith&email=ssmith@acmeco.com. Another way to do this would simply be to use POST /api/people and pass in as the body of the request a person object containing those details, e.g.:

```<code>{
    firstName: "Sally",
    lastName: "Smith",
    email: "ssmith@acmeco.com"
}
</code>```

The response would have a Location : api/people/1 header indicating that the person resource lives at that URL. If you called it a second time, it might give you Location : api/people/2. Each subsequent POST should give you a new URL for the newly created resource because you're creating a new one each time it's called. Note that by nature, POST requests are generally not idempotent.

So whatever it is, I wouldn't call it REST. As far as what you can call it, I would say that's up to you. I guess you should ask yourself if it actually matters what you call it, and if there's anything wrong with just calling it a 'websockets API'.

Body:
There are a few things that make this API not very RESTful:

REST API URLs identify resources, not actions. First, actions should not be part of the URL path. The actions are the different HTTP methods. Instead of doing something like GET /api/person/findByEmail/ssmith@acmeco.com, you should remove findByEmail and use query parameters to convey that you're searching by email, e.g. GET /api/people?email=ssmith@acmeco.com. Notice that I also changed from person to people, since collections should generally be noted as plurals of the resources they contain. This resource reads as 'People who have the email address ssmith@acmeco.com', and with the GET method your request becomes 'Get me the people who have the email address ssmith@acmeco.com'.

Second, PUT should always be idempotent, and the way you're using it is not. In other words, if the PUT method accidentally gets called more times than it was meant to, it won't really matter.

When to use PUT: When you are placing a resource at a specific location, e.g. if you want to put a song resource at /api/playlists/5/tracks/1. If this gets called more than once, it won't really have a different outcome. Note, placing something might even mean placing something that wasn't previously in the system. PUT can create a resource on the back-end or in the persistence layer somewhere if it doesn't already exist before placing it at the specified location. The key point here is you're not saying 'create a user and give me a URL to reference said user', you're saying 'create a user that looks like this and put said user at this URL'. This request could read as 'Put the following song as the first track in playlist 5'

When to use POST: When you are creating a resource, and it's up to the server to create a URL for the resource. An example would be creating a user, much like you're trying to do, which could be done as so: POST /api/people?firstName=Sally&lastName=Smith&email=ssmith@acmeco.com. Another way to do this would simply be to use POST /api/people and pass in as the body of the request a person object containing those details, e.g.:

{
    firstName: "Sally",
    lastName: "Smith",
    email: "ssmith@acmeco.com"
}

The response would have a Location : api/people/1 header indicating that the person resource lives at that URL. If you called it a second time, it might give you Location : api/people/2. Each subsequent POST should give you a new URL for the newly created resource because you're creating a new one each time it's called. Note that by nature, POST requests are generally not idempotent.

So whatever it is, I wouldn't call it REST. As far as what you can call it, I would say that's up to you. I guess you should ask yourself if it actually matters what you call it, and if there's anything wrong with just calling it a 'websockets API'.


问:
Reproducing a bug in production that happens with a large database
We are running Oracle 12c and a custom application written in Java/JDBC (Java 8). Our production system is running a 5TB database and runs into deadlocks. However we have been unable to reproduce this in our test environment which is considerably smaller. Unfortunately we don't have a test system that can handle 5TB. We don't know why database size should matter when it comes to database deadlocks. Any suggestions?</p>

答: I would recommend you to use Thread profiler to identify the real root cause of your production environment. Most of the time, it might be due to heavy traffic. If you really wants to make a copy of your production db(at least a part of it as a QA db) use slony to replicate data from the production to some other database. </p>


问:
Micro-services and data replication
I am building a new application and was reading about micro-services architecture. The architecture itself makes lot of sense from a development, deployment and life cycle management point of view. However, one issue that came up was with regards to how to handle master data.

For example, I have 2 apps: say Sales app and a Ticketing app. Assume that both of these apps are built as independent micro-services. However both of these apps, when deployed (assuming that they are deployed separately say Sales uses MongoDB and Ticketing uses MariaDB), would need to have access to the same master data instances e.g. Accounts, Products. This would mean that there would be an owner app for a given master data entity (e.g. for Accounts it might be the Sales app) and an interested party (e.g. Ticketing app would need to have information about Accounts).

There are multiple ways in which this can be achieved:

Data replication from master to interested party

Synchronous read from interested party to master (sync dependency is not recommended by the micro-services architecture paradigm)

Own centralized repository

Also even within Accounts, there can be a core part which is common for both Sales and Ticketing (e.g. account name, address etc.). However some aspects of the Account might ONLY be relevant for Sales and others ONLY relevant for Ticketing.

Any thoughts / best-practices / opinions regarding any of the above mentioned options ?

答:
I was part of a team that successfully built a microservices architecture using a service bus.

Initially, we believed that microservices and an event driven architecture would enable us to fix the underlying shared data ball-of-mud database.

What we learned was that microservices and an event driven architecture required us to get rid of the underlying shared data ball-of-mud database.

I believe that shared data is incredibly hard to do well with microservices - for me it is prohibitively hard.  I recommend not allowing services to see each others data.  If you can't query it, you can't accidentally introduce a dependency.

If you do share data, certainly only one service can ever OWN a record; it is the only service that writes to the record, and any other users of the same data should have read only access.

Unfortunately, even this small managed amount of sharing introduces significant coupling between your services.  What if one service doesn't want the data in that shape?  Perhaps it wants an aggregation.  Do you get your "owner/write" service to write aggregate data for the benefit of another service?  I'd advise not.

What if the owner wants to persist the data in a different shape?  Then every reader service needs to be updated.  That's a maintenance nightmare.

The best solution we had was a significant duplication and denormalisation of our data.  Micro services maintained their own copies of data they cared about.

Messages were often published with enough accompanying data to process them.

For example, you might imagine that a postal despatch service might need to keep track of changes to a customer address, in case it needs to post something.  But if your "item ready for despatch" message includes the destination address as part of the message data, then the despatch service no longer needs to track changing addresses related to customers at all; just point-in-time addresses related to items as they are despatched.

I can't suggest how to architect solutions with synchronised data.  Our data solutions were built around the idea of "eventual consistency".

So when a customer updates their address, the Address service processes the initial command from the UI.  Once its data is correct, it publishes an event to notify all other interested services "Customer Address Updated" - with the complete address attached as data.  Those services will update their own data stores with the parts of the data that they care about.

The idea is that any time a service has to take an important action, it should have a copy of the information up-to-date-enough to act correctly, either tracked independently, or as part of the message it is responding to.

ContentLicense: CC BY-SA 4.0

Title: Micro-services and data replication


答:
Shared data storage would go against the microservice architecture. The point is if there are Accounts, there should be a service to handle them and there should be no other way of interacting with these Account than thorough the service. Your microservices would not be independent if they shared common storage and any change to the storage mechanism, validation or other constraints would need to be implemented in both services. In practice this never happens and soon leads to both applications being prevented from any serious changes.

So, use a service as the only way of accessing your data, e.g. Accounts. It may happen that implementing a feature in some other service requires a change to the Accounts service, and that's OK. Just remember that logic specific to any service should be in that service and as little specific stuff as possible should go into the Accounts microservice.

Title: Micro-services and data replication

Body:
I am building a new application and was reading about micro-services architecture. The architecture itself makes lot of sense from a development, deployment and life cycle management point of view. However, one issue that came up was with regards to how to handle master data.

For example, I have 2 apps: say Sales app and a Ticketing app. Assume that both of these apps are built as independent micro-services. However both of these apps, when deployed (assuming that they are deployed separately say Sales uses MongoDB and Ticketing uses MariaDB), would need to have access to the same master data instances e.g. Accounts, Products. This would mean that there would be an owner app for a given master data entity (e.g. for Accounts it might be the Sales app) and an interested party (e.g. Ticketing app would need to have information about Accounts).

There are multiple ways in which this can be achieved:

Data replication from master to interested party

Synchronous read from interested party to master (sync dependency is not recommended by the micro-services architecture paradigm)

Own centralized repository

Also even within Accounts, there can be a core part which is common for both Sales and Ticketing (e.g. account name, address etc.). However some aspects of the Account might ONLY be relevant for Sales and others ONLY relevant for Ticketing.

Any thoughts / best-practices / opinions regarding any of the above mentioned options ?


问:
Returning reference type passed to method
I'm asking this from .NET (C#) point-of-view, however, I'd preferire language agnostic answer.

Is it better to return the reference type when some value is changed in method or not? I'm mostly  concerned about readability, but I'd like to here others pros & cons if there are any.

For Example, we have the following structure

```<code>struct PersonInformation
{
    internal string name;
    internal int year;
}
</code>```

Example 1:

```<code>private void Caller()
{
    var person = new PersonInformation;
    person = GetPersonInfo(person);
}

private PersonalInformation GetPersonInfo(PersonalInformation person)
{
     person.name = "Mike";
     person.year = 19;
     return person;
}
</code>```

Example 2:

```<code>private void Caller()
{
    var person = new PersonInformation;
    GetPersonName(person);
}

private void GetPersonInfo(PersonalInformation person)
{
        person.name = "Mike";
        person.year = 19;

}
</code>```

答:
I generally prefer to follow the Command-Query Separation Principle. The principle states that if you change information it is a Command, and then it returns nothing.

If the method call is a Query, it basically retrieves information and it should return with the correct type.

If you are retrieving the information of the person, the getPersonInfo() name is ok, but maybe you should pass the details of what person are you getting. For example

db.getPersonInfoByName("Mike");

Following the CQS, the signature of getPersonInfoByname should return PersonInformation.

In the case you would like to change the age of the person, you would have a method which returns void because it changes information.

void setBirthDate(date birthDate)

TL;DR

Is it better to return the reference type when some value is changed
  in method or not?

When changing values no reference type should be returned according to the Command-Query Separation Principle. If a function has side-effects, return void.

This allows a programmer to immediately recognize which functions contains side-effect and which does not.


问:
Are there memory-memory instructions?
From Tanenbaum's Structured Computer Organization,

Most instructions can be divided into one of two categories: register-memory or register-register.

Register-memory instructions allow memory words to be fetched into registers, where, for example, they can be used as ALU inputs
      in subsequent instructions. (‘‘Words’’ are the units of data moved
      between memory and registers. A word might be an integer. We will
      discuss memory organization later in this chapter.) Other
      register-memory instructions allow registers to be stored back into
      memory.

A typical register-register instruction fetches two operands from the registers, brings them to the ALU input registers, performs
      some operation on them (such as addition or Boolean AND), and stores
      the result back in one of the registers. The process of running two
      operands through the ALU and storing the result is called the data
      path cycle and is the heart of most CPUs. To a considerable extent,
      it defines what the machine can do. Modern computers have multiple
      ALUs operating in parallel and specialized for different functions.
      The faster the data path cycle is, the faster the machine runs.

Are there memory-memory instructions?

Or is a memory-memory "operation" implemented as two register-memory instructions (one for read and the other for write)?
Isn't this inefficient than moving data directly between two places in the same memory without going via a register?

答:
The Motorola 68000 ("68K") architecture had an orthogonal instruction set, and both operands could specify absolute memory addresses.  You could also do things like directly incremement / decrement the value at a specific memory location, whereas with a more RISC-like architecture you'd still be required to load memory to register, increment register, write (store) register back to memory.

The ColdFire architecture is the heir/successor to the 68K, and I think they might have trimmed away some of the more exotic instructions and addressing modes.

Title: Are there memory-memory instructions?


问:
Connected components of undirected graph
Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation.

For every time moment I have as input some subset of vertices that are "active" at this moment. And I need to find all connected components in this subset of vertices for that time moment.

Right now I've implemented this using union-find data structure like this:

```<code>initialize sets for every active vertex so that every vertex has itself as "representative" (also called "parent")

for every active vertex v
   for all neighbours of v in G v_neighbour
      if v_neighbour is active
          union set of v and set of v_neighbour
</code>```

It should work OK, but I want to know if there is a more optimal approach? And what is the running time of that algorithm? O(N*M)?

答:
The right answer in practice may depend on the rough proportion of vertices that are active. If most vertices are active, I would modify the graph structure by stripping out all links to inactive vertices (trivial in adjacency matrix form, very parallelizable in adjacency list form) and then run a standard weakly-connected-components algorithm (which should be O(V+E)). If the number of active vertices is very small, then mutilating the graph might not be worth the time, and just expanding out from the active vertices as you suggested could be better.

As always, our intuitions about these things should be experimentally checked if performance is a key concern.


问:
What is the (craziest, stupidest, silliest) thing a client/boss asked you to do?
See title, but I am asking from a technical perspective, not

Take my 40 year old virgin niece on a date or you're fired.

答: Wear khakis and a polo shirt.</p>

Body: Wear khakis and a polo shirt.

OwnerDisplayName: Casey


问:
Distributing Libraries
How are libraries typically distributed?  Because they have to be compiled with the same compiler under the same settings as the project using it, distributing the .dll, .lib, etc. seems  impractical.  Is the source code just made available for download?

答: You can distribute the .dll, there's nothing wrong with that. In .NET, when you reference a library it doesn't need to be recompiled, you can just use it as is. Plenty of projects distribute their binaries but not their source.</p>

Title: Distributing Libraries


问:
What about LISP, if anything, makes it easier to implement macro systems?
I'm learning Scheme from the SICP and I'm getting the impression that a big part of what makes Scheme and, even more so, LISP special is the macro system. But, since macros are expanded at compile-time, why don't people make equivalent macro systems for C/Python/Java/whatever? For example, one could bind the python command to expand-macros | python or whatever. The code would still be portable to people who don't use the macro system, one would just expand the macros before publishing code. But I don't know of anything like that except templates in C++/Haskell, which I gather aren't really the same. What about LISP, if anything, makes it easier to implement macro systems?

答:
I'm learning Scheme from the SICP and I'm getting the impression that a big part of what makes Scheme and, even more so, LISP special is the macro system.

How so? All the code in SICP is written in macro-free style. There are no macros in SICP. Only in a footnote on page 373 are macros ever mentioned.

But, since macros are expanded at compile-time

They aren't necessarily. Lisp provides macros in both interpreters and compilers. Thus there might not be a compile-time. If you have a Lisp interpreter, macros are expanded at execution time. Since many Lisp systems have a compiler on board, one can generate code and compile it at runtime.

Let's test that using SBCL, a Common Lisp implementation.

Let's switch SBCL to the Interpreter:

```<code>* (setf sb-ext:*evaluator-mode* :interpret)

:INTERPRET
</code>```

Now we define a macro. The macro prints something when it is called for code expanded. The generated code does not print.

```<code>* (defmacro my-and (a b)
    (print "macro my-and used")
    `(if ,a
         (if ,b t nil)
         nil))
</code>```

Now let's use the macro:

```<code>MY-AND
* (defun foo (a b) (my-and a b))

FOO
</code>```

See. In above case Lisp does nothing. The macro is not expanded at definition time.

```<code>* (foo t nil)

"macro my-and used"
NIL
</code>```

But at runtime, when the code is used, the macro is expanded.

```<code>* (foo t t)

"macro my-and used"
T
</code>```

Again, at runtime, when the code is used, the macro is expanded.

Note that SBCL would expand only once when using a compiler. But various Lisp implementations also provide interpreters - like SBCL.

Why are macros easy in Lisp? Well, they aren't really easy. Only in Lisps, and there are many, which have macro support built in. Since many Lisps come with extensive machinery for macros, it looks like it is easy. But macro mechanisms can be extremely complicated.

Body:
I'm learning Scheme from the SICP and I'm getting the impression that a big part of what makes Scheme and, even more so, LISP special is the macro system.

How so? All the code in SICP is written in macro-free style. There are no macros in SICP. Only in a footnote on page 373 are macros ever mentioned.

But, since macros are expanded at compile-time

They aren't necessarily. Lisp provides macros in both interpreters and compilers. Thus there might not be a compile-time. If you have a Lisp interpreter, macros are expanded at execution time. Since many Lisp systems have a compiler on board, one can generate code and compile it at runtime.

Let's test that using SBCL, a Common Lisp implementation.

Let's switch SBCL to the Interpreter:

* (setf sb-ext:*evaluator-mode* :interpret)

:INTERPRET

Now we define a macro. The macro prints something when it is called for code expanded. The generated code does not print.

* (defmacro my-and (a b)
    (print "macro my-and used")
    `(if ,a
         (if ,b t nil)
         nil))

Now let's use the macro:

MY-AND
* (defun foo (a b) (my-and a b))

FOO

See. In above case Lisp does nothing. The macro is not expanded at definition time.

* (foo t nil)

"macro my-and used"
NIL

But at runtime, when the code is used, the macro is expanded.

* (foo t t)

"macro my-and used"
T

Again, at runtime, when the code is used, the macro is expanded.

Note that SBCL would expand only once when using a compiler. But various Lisp implementations also provide interpreters - like SBCL.

Why are macros easy in Lisp? Well, they aren't really easy. Only in Lisps, and there are many, which have macro support built in. Since many Lisps come with extensive machinery for macros, it looks like it is easy. But macro mechanisms can be extremely complicated.


问:
How to respond to a rude bug report?
I just received a quite rude bug report. The user basically says that we're doing it all wrong using capital letters here and there, although he's in fact just pointing at one bug.

On one hand, I care a lot about our users and want to maintain a good relationship and a good rating of our app. On the other I'd feel like a complete sell out if I would reply overly polite.

What's a decent way of responding? What should I keep in mind? What mindset should I have?

It should be added that the user seems to be a 24 year old CS student, and our product is an Android app that we're giving away free of charge.

答:
It sounds like you really try to please your users and care about your software, which is good!

Some people just don't know how to express themselves in a healthy manner, I'm sure the user felt much better after releasing that anger - though it sucks to be the unwarranted target.

You can't change other people, and likely the person knows that they responded unprofessionally. Take it for what it really is at the core, just a bug report. I get the feeling you also want to express that they don't need to be rude, because you care about your product and you appreciate helpful feedback. If you'd like to respond to the user in some way, I would focus on that, and not their rude behavior.

You should be able to recognize that your user is trying to help, in his own way - so whether what he says is true or not, the best thing to do going forward is to continue doing your best and recognize that some users will always think there are better ways to do it, and may never be happy with your hard work.

Title: How to respond to a rude bug report?


答:
Is it better to return the reference type when some value is changed in method or not?

To expand on Doval's comment, it's far better to not cause side effects at all. Side effects make your code harder to reason about. They make your code harder to reuse. They make your code harder to test. They make it way harder to use concurrently.

These examples have their own problems. If your function is named GetPersonInfo why is it not returning anything - I mean to get something, you necessarily need to return it. For the other signature, why are you calling GetPersonInfo when you already have a person info? Both of these signatures are uncommon in C# (and other languages) because they don't follow the principle of least surprise. Programmers cannot simply look at the signature and reasonably guess what is going on. That leads to slowness writing code and it leads to bugs.

No, a better option would be to pass in some data to find the person you want and return (an ideally immutable) instance of person info.

Title: Returning reference type passed to method

Body:
I'm asking this from .NET (C#) point-of-view, however, I'd preferire language agnostic answer.

Is it better to return the reference type when some value is changed in method or not? I'm mostly  concerned about readability, but I'd like to here others pros & cons if there are any.

For Example, we have the following structure

```<code>struct PersonInformation
{
    internal string name;
    internal int year;
}
</code>```

Example 1:

```<code>private void Caller()
{
    var person = new PersonInformation;
    person = GetPersonInfo(person);
}

private PersonalInformation GetPersonInfo(PersonalInformation person)
{
     person.name = "Mike";
     person.year = 19;
     return person;
}
</code>```

Example 2:

```<code>private void Caller()
{
    var person = new PersonInformation;
    GetPersonName(person);
}

private void GetPersonInfo(PersonalInformation person)
{
        person.name = "Mike";
        person.year = 19;

}
</code>```


问:
Are deadlines Agile?
For clarity, a deadline is:

A time limit or deadline is a narrow field of time, or particular point in time, by which an objective or task must be accomplished.

From wikipedia

My whole software development career I have been doing "Agile" which everywhere has seemed to mean at least the following practices were adhered to:

Weekly or Bi-Weekly sprints

Retrospectives Sprint planning

A product owner

Scrum

User Stories

However, every project I have ever been on has insisted on setting a deadline. Given that Agile attempts to focus on adaptive planning, flexibility and change; are deadlines Agile?

My own opinion is that they are not, as I see deadlines leading to a lack of flexibility and lack of quality. Instead, I think it provides more value to focus on Sprints and early deliveries. It seems however, in every circle I have been in, this is not the case, and deadlines are viewed to go hand in hand with Agile development.

答:
Deadlines are a reality. Most times you have to have something by a certain date. It's unavoidable. Without deadlines, even agile projects can succumb to Parkinson's Law:

Work expands so as to fill the time available for its completion.

In other words, if your project can go on forever, it will.

In relation to deadlines, Agile tries to do a few things:

Ensure that everybody can always see how much work will get done by the deadline

Ensure that the most important features are completed first

Ensure that the completed features are usable, in the sense that they don't depend on features that haven't yet been completed

Ensure that development continues at a sustainable pace

That way, when the inevitable day comes, you don't have a useless pile of code, but a working, tested product with, hopefully, only the least important stuff unfinished. And nobody is surprised by the finished product.

So yes. "Agile" and "deadlines" can be perfectly compatible.

Title: Are deadlines Agile?


问:
Why the practice of writing unit tests in a different language isn't that popular?
When Microsoft released Visual Studio 2008, there was a thing they were talking a lot about at the conferences and in their online tutorials: the idea of writing the actual code in one language, and the unit tests in a different language. For instance, unit tests for C# code can be written in Visual Basic.

Six years later, I don't know any open source project which uses this practice and no proprietary project I've seen uses it. The subject is not discussed any longer at Microsoft's conferences, blogs or tutorials.

The benefit of this practice is that doing the same type of error in two different languages is more difficult. For instance, if I don't know that in C#, 10/3 equals 3 and expect it to be 3.333..., a unit test written in Python or JavaScript will fail and lead me to the discovery in integer division.

.NET Framework, specifically, makes it possible to use any .NET-enabled language to test another one. While testing C# code with Visual Basic tests doesn't look particularly interesting, given the similarity of both languages, I would imagine that, for example, testing F# code with unit tests written in C# could be useful for people who are not that familiar with functional programming.

Personally, I have no experience writing unit tests in a different language. Therefore, I don't know if there are actual drawbacks in this technique. I often write system and acceptance tests in a different language (for instance in Python for a Node.js web app, because Python's Requests library is so great), but this doesn't count, since those tests are truly language-agnostic: they just do black box testing through HTTP: I can rewrite an app from Node.js to ASP.NET MVC, and the tests won't even notice the change.

So what could be the drawbacks, and why is this practice not that popular?

答:
Unit tests are white-box tests and usually written by the developers of the thing being tested. The first means that you need first-class interaction with the APIs and objects and values of the language the actual product is written in, which rules out almost all combinations of languages. In fact, I think the CLR is the only agglomeration of languages that each can call into each other perfectly. And as you say, most CLR languages are so similar that none of the advantages you suggest apply.

That leaves pretty much only the combination of F# and C#/VB.NET. I can imagine several reasons this hasn't taken off:

F# doesn't have that big of a community. Conversely, most C# developers don't know enough F# to even consider this.

The people who do know F# are either busy writing both unit tests and actual code in F#, or in a team where they can't use F# at all because nobody else knows it (well). As mentioned before, unit tests are usually not written by a separate team, so people who write C# unit tests for F# code probably still have to know F#. Plus the whole white-box thing: If you don't know a thing about functional programming, even the data structures and APIs exposed by (idiomatic) F# will be unnatural for you once you delve deeper than very simple libraries of the form "put in a URL here, receive IEnumerable<UrlParameter>.

There's no benefit (or people don't believe the benefit), but quite possibly some very real friction from switching languages constantly.


答:
Some deadlines must be met. Contractual obligations, conventions, regulatory requirements. Some are imposed by managers who want to be able to put software development in the same chart as manufacturing on their spreadsheet. Whatever the cause, most people can't get away from them.

If you are working in a functioning team then communication between the developers and management/stakeholders means that the people who need to make a decision are well informed to decide if missing the deadline or continuing with development is more important.

Even if you are delivering completed user stories once a week, or twice a month you will still probably have deadlines. When one is coming up, make sure your stakeholders know what you think will fit in by the deadline and set expectations.

If you are constantly building the best software you can with the requirements you currently have at every stage, then a deadline at the end of any sprint should theoretically not be a problem. Practically, this isn't normally the case, but then neither are deadlines that appear out of thin air. Most important deadlines I've ever been given were communicated to me long before, it was the expectation of the quality and the features that were the issue. All the deadlines I can think of that have come out of nowhere are because of lies. Either sales told a customer the feature was there or could be added without consulting and sometimes without even informing engineering, or someone told their boss it had already been done.

Title: Are deadlines Agile?

Body:
For clarity, a deadline is:

A time limit or deadline is a narrow field of time, or particular point in time, by which an objective or task must be accomplished.

From wikipedia

My whole software development career I have been doing "Agile" which everywhere has seemed to mean at least the following practices were adhered to:

Weekly or Bi-Weekly sprints

Retrospectives Sprint planning

A product owner

Scrum

User Stories

However, every project I have ever been on has insisted on setting a deadline. Given that Agile attempts to focus on adaptive planning, flexibility and change; are deadlines Agile?

My own opinion is that they are not, as I see deadlines leading to a lack of flexibility and lack of quality. Instead, I think it provides more value to focus on Sprints and early deliveries. It seems however, in every circle I have been in, this is not the case, and deadlines are viewed to go hand in hand with Agile development.


答:
Think of deadlines as commitment. The fact that the project is agile doesn't mean you shouldn't commit to deliver given features for a given date.

What agility brings is what happens in between. Instead of having a strict software requirements specification document which defines that you should deliver feature A composed of sub-features B, C, D and E for a given date, you commit to deliver the feature A for a given date, given that at the early stage, neither you nor your customer knows what the feature will look like, or would it have sub-features B, C, D and E or maybe B and C, or a dozen of other sub-features.

Imagine a company which previously delivered goods to small companies only and have just signed a contract with a large corporation. This large corporation uses EDIFACT, and it appears that the current accounting software used by your company doesn't handle EDIFACT. You're requested to create a plugin which does that, given that contractually, your company should be ready for April 15th.

The agility would mean that intermediary steps will be delivered progressively, and be based on regular feedback. Basically, you'll show your progress to the accountants, and they will tell you what they think about it, what are the possible issues, etc. This also means that maybe originally, accountants had a great idea which, they thought, could improve substantially the user experience. Three weeks later, it appeared that not only it doesn't improve it that much, but it will also result in one month of additional development. Thanks to Agile, you can then redirect your efforts from this feature to something else, making sure to deliver on time.

You should also understand the point of view of the customer:

Often, businesses need a specific delivery date. For instance, you can't deliver the Olympic games online streaming service after the end of Olympic games. Business-wise, this is simply a failure, with huge negative consequences.

Without having a commitment, it is tempting for a developer or a subcontractor to either be perfectionist or make the project low priority. While the regularity of the sprints help, it doesn't totally prevent this risk.

I'm not fond of deadlines for that, especially since deadline slips happen very easily, but I still understand why many companies do that. It is not always easy to see that the project is behind the schedule by looking only at the sprints: a missed deadline, in this context, may be a clear reminder that something goes out of control and should be dealt with, right now.

Title: Are deadlines Agile?


问:
Where can I find design exercises to work on?
I feel it's important to continue practicing my problem-solving skills. Writing my own mini-projects is one way, but another is to try and solve problems posted online. It's easy to find interesting programming quizzes online that require applying clever algorithms to solve - Project Euler is one well-known example.

However, in a lot of real-life projects the design of the software - especially in the initial phases - has a large impact and at later stages it cannot be tweaked as easily as plain algorithms. In order to improve these skills, I'm looking for any collection of design problems.

When I say "design", I mean the abstract design of a software solution - for example what modules will there be and what are the dependencies between them, how data will flow in the program, what sort of data needs to be saved in the database, etc. Design problems are those problems that are critical to solve in the early stages of any project, but their solution is a whiteboard diagram without a single line of code.

Of course these sort of problems do not have a single correct solution, but I'll be especially happy with any place that also displays pros and cons of the typical solutions that might be used to approach the problem.

答:
I agree Katas and Euler are nice for designing algorithms and practicing coding -- perhaps you can expand on them, and be a little creative and design a system around one of the problems.

For instance, I am working on not just solving the problems of Euler to find the quickest, shortest answer, but solving them in a distributed way -- I want to set up a series of Erlang nodes in order to tackle one of the problems.  Of course, this means I have to figure out how to separate out the problem into discrete chunks and have them report back on their progress and aggregate the results together (all within a Functional Language that I'm not an expert in).

Perhaps you can design a system around solving one of these problems as a business solution -- how can you make it so that multiple "customers" could have access to your problem at one time, you can go through designing a client and service layer interactions, etc.

It's all about being creative and having fun.


问:
What layer generates commands for dependent services?
Our business works with truck drivers making pickups/deliveries of containers. The location of containers needs to be tracked.

The drivers use mobile devices to generate a "DriverReport" (a log of their trip locations, times, container pickup/drop-offs, etc.). This is currently working with a mostly CRUD design.

We wanted to maintain good SoC so we built two services:

DriverService

InventoryService

We've had the DriverService take a dependency on the InventoryService. When a new DriverReport was inserted, it would generate DTO's (based off the reports data) that could be sent to the InventoryService.

We're not using CQRS yet, but we're considering transitioning to it.

I'm struggling to understand the relationship between the services, commands and BLL. I seem to have lots of questions.

Who would be responsible for calling the inventory service?

Would it be good design for a NewTripCommandHandler to generate and send an UpdateContainerInventory command?

Or, would updating inventory for a new Trip be considered business logic? If yes, should a a domain entity for Trip generate and send an UpdateContainer command?

Or, should the mobile client generate both trip and inventory specific commands to send to the appropriate service?

Would it make more sense to take the parts specific to DriverReport inventory and merge it into the DriverService (so the dependency is broken)? Is that still good SoC? If we did this, at what layer might we start to think about the inventory? Would updating the inventory simply become a DB repository concern, or should there still be inventory specific commands and/or business logic?

I'm getting lost in the details, and it seems the more I read on the topics, the more confused I get.

答:
My advice is to stop thinking about services, commands and fancy terms in OO design.

I would strongly recommend modelling your business logic without thinking about service oriented architecture, how the data will be transferred from clients to the service, etc.

You have an application. Your application clearly has two modules:

Module for processing a driver's report. I really don't care how this report gets generated and where the data comes from at this stage.

Module for updating inventory. Now I would not create a dependency between driver's report and inventory processing. Instead I would create a component that would extract relevant data from the driver's report and then pass it into the inventory processing module.

Once all this is in place I would start thinking about services (boundaries). I'd be asking questions like "Does it really make sense to create an inventory service? Will I have a client application that will call it directly?"

Finally, I would question having any business logic in the client application. I normally model and unit test all my business requirements in the domain layer. Once that's done, I start working on the client application. This way my client application is pretty dumb, all it does is aggregate some data, pass it to the domain layer, lets domain layer work out what to do with the data, and then finally display result back to the user.

Update 1
So instead of:

```<code>var driverReport = new DriverReport();
var inventoryCoordinator = new InventoryCoordinator();
inventoryCoordinator.Process(driverReport);
</code>```

I would have:

```<code>var driverReport = new DriverReport();
var inventoryUpdate = InventoryUpdateFactory.Create(driverReport);

var inventoryCoordinator = new InventoryCoordinator();
inventoryCoordinator.Process(inventoryUpdate);
</code>```

In first example the inventory coordinator has a direct dependency on drivers' report.

In second example, we extract relevant information from the drivers' report and then pass that into inventory coordinator for further processing.

Body:
My advice is to stop thinking about services, commands and fancy terms in OO design.

I would strongly recommend modelling your business logic without thinking about service oriented architecture, how the data will be transferred from clients to the service, etc.

You have an application. Your application clearly has two modules:

Module for processing a driver's report. I really don't care how this report gets generated and where the data comes from at this stage.

Module for updating inventory. Now I would not create a dependency between driver's report and inventory processing. Instead I would create a component that would extract relevant data from the driver's report and then pass it into the inventory processing module.

Once all this is in place I would start thinking about services (boundaries). I'd be asking questions like "Does it really make sense to create an inventory service? Will I have a client application that will call it directly?"

Finally, I would question having any business logic in the client application. I normally model and unit test all my business requirements in the domain layer. Once that's done, I start working on the client application. This way my client application is pretty dumb, all it does is aggregate some data, pass it to the domain layer, lets domain layer work out what to do with the data, and then finally display result back to the user.

Update 1
So instead of:

var driverReport = new DriverReport();
var inventoryCoordinator = new InventoryCoordinator();
inventoryCoordinator.Process(driverReport);

I would have:

var driverReport = new DriverReport();
var inventoryUpdate = InventoryUpdateFactory.Create(driverReport);

var inventoryCoordinator = new InventoryCoordinator();
inventoryCoordinator.Process(inventoryUpdate);

In first example the inventory coordinator has a direct dependency on drivers' report.

In second example, we extract relevant information from the drivers' report and then pass that into inventory coordinator for further processing.


答: I think that having a void (mutator) method that starts with "Get" is a code smell on its own. Method names must be clear, descriptive and trustworthy. Your first example is better than the second one, however, I would not call it a good method. </p>


答:
If someone wants to set a deadline then that is fine and the deadline can be fixed, but what they must understand is that if the deadline is fixed, then the scope must remain flexible.

tl;dr

In an ideal world we wouldn't have deadlines and just deliver things when they are ready. The reality though is that people paying for things usually want to know when they are done. Agile methodologies do recognise this but also recognise that not everything can be tied down.

This ensures that you can keep quality of delivery at the level that is right for the product. If you fix a deadline and scope (and budget) then things get rushed and you end up back in the old waterfall world with a crazy crunch time at the end of the project. Increasing the budget usually isn't the answer, because adding more developers and testers doesn't solve a problem faster. It's a well-known view (and I agree with it from experience), that the more people you add (each with their own foibles) the more time it takes.

Now, typically (unless they really understand Agile methods) the person paying for the software doesn't like being told, we can meet your deadline but we can't do everything you want. This can be managed by prioritising the features that make up the software. Your prioritisation discussion might go like:

Dev Team (D): "Please can you prioritise the features you want delivered, with most important first?"

Customer (C): "Everything is priority 1 - I want them all done by the end of next month."

D: "That may be possible, but that may not be possible if requirements change or we discover issues we didn't expect while going through development."

C: "Well what if I give you more money?"

D: "sigh...even with more resource it's going to take them one month to really get going; so if you're not sure how to prioritise the features just tell us which ones you want done first."

C: "Ok I want the big button but make it really big, and then ...etc"

Now you can start working through the features in priority order. It does help to also look ahead with your team to those items lower in the priority order and make some early estimates, knowing you may change them when you get to development when you have more information. This can be used to redefine or create your roadmap if you don't have one yet. This then forms the basis of your release plan. The roadmap can be discussed with the customer acknowledging that scope may change but you do have an order of things to be delivered.

One of the great advantages of Agile is that it acknowledges that things change as you go through development and you adjust as they do. Contrary to more traditional approaches, this principle, in conjunction with the regular sprint deliverables and ongoing communication with the customer, mean that you are naturally forced to be more transparent about progress, which is a good thing.

Sometimes the customer doesn't like that they will not get what they want by a certain date BUT they will understand why and what they do get will be of good quality. And 6 months after features are delivered the customer won't care or remember that you delivered by a certain date, they'll remember the quality of the product that they are still using.

Title: Are deadlines Agile?


答:
Deadlines are a fact of life. There are things that have a very firm date.

We need the software by Comdex

or

The games must be on store shelves by Black Friday

and the like. One cannot postpone Comdex or Black Friday - the rest of the world doesn't work that way.

The goal that Agile has is that things that won't meet the deadline fail faster (and that is a good thing), or the scope is able to be re-examined sooner so that the resources can be focused on the correct ROI in a more timely manner.

The deadline is a hard date that is set down firmly. Agile is a tool that allows one to realize earlier in the cycle that the software is going to take twice as long to develop as originally hoped. It is important for project managers to be able to realize these issues earlier than later so that either more resources can be added, the scope changed, the deadline adjusted (in the situation where it is a firm rather than rock solid deadline) or the project canceled.

The transparency that Agile seeks is that of showing the problems and progress earlier in the cycle. The classic waterfall delivery failure is one were you've spent months behind closed doors and deliver the product a week before the deadline and are told you're doing it all wrong and you've wasted months (and now have completely blown the deadline). The other classic waterfall failure is finding out a week before the deadline you've still got months to go.  Agile seeks to make these issues known early in the process.

The other part that Agile seeks to do in the context of a deadline is that even if only part of the agreed upon features are complete (for whatever reason), the current version of the software is useful and deployable.

Ok, we missed having everything we want for the tax software to be deployed on April 15th, but we've got 75% and what we do have works and has been working since we started last November.  We've known we are not going to be able to deploy the full feature set since mid December and refocused our efforts on the 80% of the customer base.

Title: Are deadlines Agile?


答:
The degree of agility required in one's work is inversely proportional to how high their position is on the organization chart.

"Agile" is good, for what it is.  "Agile" sorta means "open-minded coupled with sufficient competence."  It's the grunts at the bottom that have to be the most agile.

If, at management levels, the pointy-haired boss was agile enough to understand that pushing a deadline back a week will make for a better product, or will make for cleaner, more bug-free, and more leverageable code so that the company (or the division) saves two weeks in the future, that's an agile deadline.

But like enlightened self-interest, it doesn't really exist.

Title: Are deadlines Agile?


答:
The purpose of software development methods, when understood correctly, is to make us more productive by focusing our thoughts, and to provide a common language for typical situations. It's about inspiration and enabling, not about mind control and guilt.

Following a software development method literally with no compromises whatsoever corresponds to what is called radicalism or fundamentalism in other contexts. The pure form of this aberration is rarely seen in practice because it typically leads to rapid failure in the market. But of course when developers compete in the hard task of implementing a specific method, overshooting the mark is a natural occurrence.

The problem is exacerbated by the fact that missionaries and evangelists primarily target those who still need convincing to use the method at all; and even if they do preach moderation, human nature ensures that it gets less attention.

Title: Are deadlines Agile?


答:
I would say that delivery each sprint is non-negotiable. You assess the work, you put card sizes on it, and you load up enough to keep your team busy until the sprint ends (and the sprint should be small -- anything from a week to a month). "Delivery deadlines" should be based on historical trend of completed work against anticipated work. Agile adds/removes nothing from the old "cost/time/scope" constraint idea, it simply uses scope as the preferred method of managing slippage on the basis that better prioritization against scope is generally preferable to spending more money or time.

Some people seem to confuse agile for "wild west".  Agile doesn't mean anything goes.  Agile means that we stop lying to ourselves about how well a reasonable person can estimate.  Basically we can estimate software development about 2 - 4 weeks into the future.  Beyond that, it's all varying degrees of swags and guesses.  Worse yet, the cost of providing estimates for things further and further out into the future approaches the cost of just doing the work.  For whatever reason, Project Managers have historically been unwilling to admit these absolute truths to customers.  Agile simply adjusts that thinking by asserting that there is a limit to how well we can predict the future in software engineering, and makes a subtle switch to "evidence based estimation" for long term forecasting.  By giving dead certain delivery in small chunks, and evidence based delivery for long term stuff, we get something close to the best of both worlds -- we get to be truthful about what we actually are capable of estimating, and we can provide fairly reasonable estimates of long term future delivery based on what we've been delivering so far.

Title: Are deadlines Agile?


答:
Deadlines are not agile, they are:

1)Waterfall, and
2)Wrong.

Software and deadlines do not work well together and never have. In many ways, the Agile methods are a reaction to the massive problem of missed deadlines or software which was abandoned when it became clear that the deadline could not be met (as well as budget issues, too).

Agile attempts to inject reality into the situation by saying "You know the deadline or the features are going to slip and/or change, we know it, so let's get off on the right foot and not even pretend".

The key is that the deadline becomes simply a release date for the first version of the software. That might still be written in stone - say, the software is for academic use and MUST be usable by the start of term - but what you will deliver is not. You have a minimum viable product that everyone is very sure can be delivered by then, and you have a load of "would like to haves". Instead of everyone throwing up their hands when it turns out that the entire list isn't going to be delivered by the "deadline", you make sure you get the MVP out the door and as many of the "would like to haves" as possible and then assess the cost/benefit of the remainder at that point.

Anyone who's played computer games for any length of time knows exactly how this works! If the first release is up to beta standards many gamers are happy, so low are the expectations of what "firm, real deadlines" mean in real life.

So deadlines are not agile, they are holdovers from the days when people thought that software could be treated like hardware and steel engineering. We've learnt that this is neither possible nor desirable, since it throws away the greatest advantage software has over hardware: it is soft.

Agile tries to exploit this softness by allowing goals to develop and change over the course of the project in a way that a bridge design never could.

Title: Are deadlines Agile?


答:
Deadlines are traditionally based upon the business lifecycle. Tax software needs to be in by April 15th. Reporting for the next fiscal year might need to be done by July.

The Agile manifesto states:

Individuals and interactions over Processes and tools

Working software over Comprehensive documentation

Customer collaboration over Contract negotiation

Responding to change over Following a plan

Deadlines are a contract. They are a plan. They do not respond to your team's velocity. They do not change if you lose your three best developers.

Deadlines are not Agile, but Agile can give us feedback on deadlines. Agile let's us know if our velocity will not let us make a deadline without a feature being cut. It also let's us know if we need to hire to make a deadline. And in some cases, it let's us know that a deadline is impossible, when there are no features left to cut.

The best thing an Agile team can do, is let their velocity and prioritized backlog drive the deadlines. This will give estimated delivery dates. If those fall outside the deadline, then its time for a serious talk with the client and determine if the deadline is even doable.

Title: Are deadlines Agile?


问:
Enemy AI for classic game Bubble Bobble
I am building a similar game to Bubble Bobble. This is the scenario:

where E represents enemies, and P represents the player. If a user falls through the lower hole, it reappears through the superior one.

Assume that players can fall and jump.

Also, even though I said I based it on "Bubble Bobble", the characters can jump "through" platforms to go up. They have to find the proper corners.

My problem here is that I have to program the AI of the enemies, to find and search the player.

What would be the best algorithm to find the shortest path to meet the player?

答:
"The best algorithm to achieve this"?  Define "best".  A simple A* algorithm will generate the most efficient possible path for an enemy to take to reach the player, but would you really want to play against a perfect computer?  That's a recipe for frustration right there.

The Pac-Man "AI" was actually 4 very simple algorithms that told the 4 ghosts where to move towards, which gave each one a distinct "personality" and hunting style.  If they acted intelligently and worked together, they could hunt Pac-Man down, corner him, and kill him consistently, and it would suck to play the game.  Instead, the developer came up with a system that is challenging but fun.  For something like this, I'd advise a similar tactic: come up with a handful of different simplistic algorithms and test them to see what version(s) are the most fun, individually and together.

Title: Enemy AI for classic game Bubble Bobble