What You Have Now:

You code is simple and concise. That in and of itself can be a desirable quality. I think we can make the code a little bit more concise while gaining some runtime efficiency.

Some changes I would make:

Change srand((unsigned) time(0)); to srand(time(NULL));

While both are correct, this is how I have seen seeds set more often, hence it is the idiomatic approach

Change return 0 to return EXIT_SUCCESS

Exit codes are included in stdlib, since you already using that library, you should also use the provided exit codes.

Change rand()%2 to rand()&1

The modulo operator (%) can be very inefficient on some architectures. Since you are only using rand() to get binary values, we can much more efficiently use the bitwise and operator (&) to get a 1 if the number is odd and a 0 if the number is even.

Change your while loop to remove intermediate variables:

while(1) {
 if(rand() & 1)
   printf("%d ", rand() & 1);
 else
   printf(" %d", rand() & 1);
}

All together I think you could simplify your code to this:

#include<stdlib.h>
#include<stdio.h>
int main() {
srand(time(NULL));
system("color 0a");

while(1) {
  if(rand() & 1)
    printf("%d ", rand() & 1);
  else
    printf(" %d", rand() & 1);
}

return EXIT_SUCCESS;
}

This is a pretty small and eloquent code for generating a matrix style output. If your happy with this you can stop right here.

However, it should be pointed out that printf is a little heavy handed for just printing spaces, ones, and zeros. You could utilize putchar which will, unsurprisingly, put a character to STDOUT.

while(1) {
  if(rand() & 1) {
    putchar(48 + (rand()&1))
    putchar(' ');
  }
  else {
    putchar(' ')
    putchar(48 + (rand()&1));
  }
}

Note that now we have a Magic Number 48 in out code, that is no good! Let's let the preprocessor help us make the code a little bit more readable:

#define ASCII_NUMBER_OFFSET 48
while(1) {
  if(rand() & 1) {
    putchar(ASCII_NUMBER_OFFSET + (rand()&1));
    putchar(' ');
  }
  else {
    putchar(' ');
    putchar(ASCII_NUMBER_OFFSET + (rand()&1));
  }
}

Next is a matter of personal preference. I personally don't like 2 line if statements. If the if statement has 3 lines, it should probably be abstracted into a separate method, if it has one line, that’s perfect, but if we have 2 lines... that's murky water.

We could use the comma operator to clean up the line a little:

#define ASCII_NUMBER_OFFSET 48
while(1) {
  if(rand() & 1)
    putchar(ASCII_NUMBER_OFFSET + (rand()&2)), putchar(' ');
  else
    putchar(' '), putchar(ASCII_NUMBER_OFFSET + (rand()&1));
}

Using the comma operator is a matter of preference. I think that there are times that it is perfectly clear & reasonable to use it, others say the comma operator should never be used because it is too opaque. While that code is more compact, I don't think it helps readability or efficiency.

Lets try abstraction that into a method instead and see how that looks:

while(1) {
  if(rand() & 1)
    printLeft();
  else
    printRight();
}
.
.
.
#define ASCII_NUMBER_OFFSET 48
void printLeft() {
   putchar(' ');
   putchar(ASCII_NUMBER_OFFSET + (rand()&1));
}

void printRight() {
   putchar(ASCII_NUMBER_OFFSET + (rand()&1));
   putchar(' ');
}

That makes the while loop look better but the methods might incur some performance cost. Since your tag Optimization implies that you care most about runtime efficiency and not readability/maintainability lets try something else.

You will notice in your all the code examples above, there is some repetition in the while loop. In all the cases we have 2 statements printing the one or zero. Repetition is often a good thing to focus on because it can alert you to things that can be improved. There is a mantra of Don't Repeat Yourself (DRY) in programming which is designed to help programmers locate inefficiencies and refactor their code for better readability & efficency.

Consider this loop:

int b;
while(1) {
  if(b = rand() & 1)
    putchar(' ');
  putchar(ASCII_NUMBER_OFFSET + (rand() & 1));
  if(!b)
    putchar(' ');
}

Here we have a single binary number printing statement but conditionally print a space before or after the number. From a runtime efficiency perspective this is probably optimal (though I have not done any benchmarking).

If we put this all together we have the following:

#include<stdlib.h>
#include<stdio.h>
#define ASCII_NUMBER_OFFSET 48

int main() {
int b;
srand(time(NULL));
system("color 0a");

while(1) {
  if(b = (rand() & 1))
    putchar(' ');
  putchar(ASCII_NUMBER_OFFSET + (rand() & 1));
  if(!b)
    putchar(' ');
}

return EXIT_SUCCESS;
}

I hope this has given you a lot of different angles to view you code from and given you the tools to decide what you value when improving this code, readability or runtime efficiency.


I completely changed the approach which resulted in faster downloads, and improved functionality. The overall approach of the initial version works well for a generic solution looking for adding concurrency to independent jobs.

Removed zypper list-updates. This format is easier for machine consumption, but it's not intended for Tumbleweed. Replaced with zypper dup/inr/in --details;
Removed background jobs and waits. Replaced with aria2 which handles the maximum number of concurrent connections;
It pays off learning more about awk capabilities, in order to replace sequences of grep/awk/tr with a single awk;
The main job of the script became building a plain text file with URIs and target directory for each .rpm file

aria2 is really great tool. Superb quality. curl is not reliable in its native concurrent download capabilities.


The biggest problem with this code is that is not manageable at all. This setup is inefficient and will make it very hard to add features and also bug fix if things start going wrong.

there's no success or error handling on your AJAX request.
There's no way of knowing if getNumber() worked on not, which could end up spewing errors onto the page.
Callbacks are your friend.

Here is a more manageable setup for you.

// jQuery will wait until the DOM is ready. Then in the callback you can define all your listeners.
$('body').on('ready', function(){
    // This is the listener for the button click. $.on() should always be used from jQuery 1.7+.
    $('button').on('click', function(){
        $('.receiver').load('number.html .giver', function(response, status, xhr){
            // This is just a very basic error check. At least is there is an error you'll know.
            if (status == "error") {
                $('.receiver').html("Sorry there was an error: " + xhr.statusText);
            }
        });
    });
});

I would always advise strongly against having timed events in your code. They tend to break easily and are hard to fix. However if you really want them, use the Javascript setTimeout() function after DOM load. setTimeout() is just a bit easier to read and maintain. Instead of timing events, I would advise using callbacks to fire events. This solution allows any number of DOM listeners to be easily added to your page now without hassle.

I would make one more note here: in my experience it never ends well trying to drag AJAX responses through functions unless you have rock solid scopes set up. I would personally always say it is best practice, with adding dynamic content, to always create the AJAX request in the same scope/function that you are going to use it in. So:

// Don't do this.
var ajaxRetrieve = function(){
    $.ajax({
        url: '/gimmeAllOfThat',
        method: 'POST',
        success: function(responseData){
            return responseData;
        },
        error: function(responseData){
            alert('Check yourself');
        }
    });
}

$('button').on('click', function(){
    // This is very bad.
    var data = ajaxRetrieve();
    $('#div').html(data);
});

This config means that you will still have to use whatever you get returned from your function, even if the AJAX request fails. Which could mean you'll have to check for errors twice, instead of just once and using the data as an event in the AJAX request. Also something to note is: that AJAX return will fail so badly, as it won't get returned into the parent function scope, only the success function scope.

TL;DR: use callbacks:

// Do this.
$('body').on('ready', function(){
    var ajaxRetrieve = function(callback){
        $.ajax({
            url: '/gimmeAllOfThat',
            method: 'POST',
            success: function(responseData){
                callback(responseData);
            },
            error: function(responseData){
                alert('Check yourself');
            }
        });
    }

    $('button').on('click', function(){
        ajaxRetrieve(function(data){
            $('#div').html(data);
        });
    });
});

This setup means that that function can be reused for a number of different things, and you can just change the callback function each time you call it. It also means you get out of 'Returning Hell', trying to return data here, there and everywhere.


Python: Find pairs of numeric palindromes that sum up to another palindrome

Two opportunities for optimization that suggest themselves to me:

Seems like you should be able to produce an exhaustive list of 4-digit palindromes by taking every 2-digit number and then appending its mirror to it, rather than having to iterate through every 4-digit number and throw most of them out.  That would let you build your palindrome list in about one-hundredth the time (you'll be iterating over 90 two-digit numbers instead of 9000 four-digit numbers in that first loop).
A lot of the sums you're checking will be too small (i.e. they'll be 4 digits); none will be too big (9999+9999=19998).  You can minimize the work you do on those sums by iterating from largest to smallest and breaking the inner loop once the sum gets too small.

An alternative to the nested for loops would be using one of the itertools functions to generate all the combinations as a set of tuples, but I don't think that'd get you any performance wins.


Avoiding redundant code in MVC view page

Most of your code is duplicated, what I did is extract the logic to the first code block, and left only the placeholders in the HTML.

@{
    bool savingHtml = (Request.QueryString["savehtml"] == "1");
    string activeTab = Request.QueryString["from"];
    string tabContent = Html.Partial("~/Views/Shared.MultiQuery/_resultset.cshtml", Model);
    string heatClass, tableClass;
    string tableId = "table";
    string heatId = "heat";
    string heatTabContent, tableTabConten;

    if (savingHtml && activeTab.ToLower() != "index") {
        heatClass = "active";
        heatTabContent = tabContent;
        tableId += "2";
        heatId += "2";
    } else {
        tableClass = "active";
        tableTabContent = tabContent;
        if (savingHtml) {
            tableId += "1";
            heatId += "1";
        }
    }
}

Heat Map

Table

        @tableTabContent

        @heatTabContent

Note: I have no experience with ASP.Net, so I apologize if the code is not as clean as possible, or has any syntax errors... The gist of the matter is still that if you extract the logic, you get shorter and cleaner code, with much less copy+paste...


I don't know what the possible rest of your code looks like, so my opinion might be wrong. What I don't understand is why a lot of people use jQuery for the slightest bits nowadays. The display of the array could be done like this:

var table = document.getElementById("displayTable"); //give this ID to your table

for (var i = 0; i < game_name.length; i++) {
    var row = table.insertRow(i);
    var cell = row.insertCell(0);
    cell.innerHTML = game_name[i].ItemName;
}

Update:

If you insist on using jQuery, cache the selector in a variable and re-use the variable. Overusing selectors can result in poor performance and since you're using the selector inside a loop this can easily occur.

var table = $('#displayTable');

for (var i = 0; i < game_name.length; i++) {
    table.append("
" + game_name[i].ItemName + "
");
}

Furthermore, give useful names to variables. Names like tr or game_name are not meaningful, try tableRow and gameNames instead. I updated the JSFiddle working example.


Prepending a string to alternate elements in a Python tuple

There may be other ways to do it, but none that I can think of that stands out as being better than what you wrote.  You could tighten up the code by adhering to PEP 8 naming conventions (use lower_case_with_underscores) and eliminating the variable t.

All I can offer is my condolences for being stuck with this stupid interface.  Note that the first thing that webpy does, as you might expect, is split up the tuple into pairs, using their own utils.group() function.

class application:
    def __init__(self, mapping=(), fvars={}, autoreload=None):
        if autoreload is None:
            autoreload = web.config.get('debug', False)
        self.init_mapping(mapping)
        …

 def init_mapping(self, mapping):
    self.mapping = list(utils.group(mapping, 2))


To find the kth smallest/largest value you do not need to sort all values! Simply keep track of the k smallest/largest encountered values in a (sorted) buffer. This will take your run time from O(nlog(n)) to O(nlog(k)). And will also avoid the unnecessary copy and iteration, simply keep the index with k.

The following pseudocode illustrates the algorithm

template<typename It>
It min_k(It first, It last, int k){
   auto cmp_it_values = [](It lt, It rt){ return *lt < *rt;};
   auto max_copy = std::min<long>(k, std::distance(first, last));
   auto start_it = first;
   std::advance(start_it, max_copy);

    k++; // k == 0 has to return smallest one element.
    std::vector<It> k_smallest;
    k_smallest.reserve(k+1);
    for(auto it = first; it != start_it; ++it){
        k_smallest.push_back(it);
    }
    std::sort(k_smallest.begin(), k_smallest.end(), cmp_it_values);

    for(auto it = start_it; it != last; ++it){
        if(k_smallest.empty() || *it < *k_smallest.back()){
            auto insertion_point = std::lower_bound(k_smallest.begin(), k_smallest.end(),
                                                    it, cmp_it_values);
            k_smallest.insert(insertion_point, it);
            if(k_smallest.size() > k){
                k_smallest.pop_back(); // Remove the largest value
            }
        }
    }
    return k_smallest.back(); // The iterator to the min(k, n) smallest value
}

The above has O(nklog(k)) worst case and O(n + log(k)) best case behaviour. You can improve the worst case by using a max heap for k_smallest instead of a vector. This would have the promised O(nlog(k)) run time. I leave that as an exercise to the reader ;)

And you should read this using namespace std; is bad practice.

You can see from the benchmark here: https://ideone.com/B81Hs4 that the code above is twice as fast as your original code for the given values (you need to test with typical values for your application to verify) and the heap version is even faster.


pointer = (T*)calloc(len, sizeof(T));

Say what?  I’m used to getting people to stop using “naked new”, but this is C memory management!  Why would you do that?  You are not initialing any of the T objects you allocated room for.  That may work for ints and other primitive types, but in general you are looking at a boom when you subsequently access an element.

unsigned short

Why use this for the size type?  At the very least, abstract it as a member type, normally called size_type.  The usual default type for this is std::size_t but there is a movement to switch to signed types for new containers.

   if (index > length) throw;

Throw what?  This will crash since throw by itself is only allowed when there is a current exception being handled.

Your insert and remove take (signed) shorts, which conflicts with your use of unsigned for indexes.  Besides not being able to represent all the values, you will have problems comparing them, which is exactly what you do in the first line.

To provide for the negative number indexing feature, either use the same approach as Eric Neibler (end - 5 rather than -5) or use the signed type for your length, as suggested earlier.

Your insert is re-allocating memory, which is not what I’m expecting.  You are implementing a vector class, not an array class (which is fixed length).  So why?  What’s wrong with std::vector?

LinearSearch, BinarySearch:  Don’t write these members.  Instead, allow std::find etc. (as well as all other algorithms) to work with your container.

You re-allocate upon inserting, but not when deleting.  But you don’t keep track of how much slack space you have.


public Node findSmallest(Node start) {
    //This is so in the main method, I can call findSmallest and pass in
    //null to search the whole tree. Because in main, I won't have reference
    //to the root. I have the start parameter so I can specifiy where to
    //start the search, because of the way I am dealing with deleting
    //a node with 2 children. See above.
    Node smallest = start == null ? root : start;

    while(smallest.getLeftNode() != null) {
        smallest = smallest.getLeftNode();
    }
    return smallest;
}

I would break this into two methods:

public Node findSmallest() {
    return findSmallest(root);
}

private Node findSmallest(Node candidate) {
    // I have the start parameter so I can specify where to
    // start the search, because of the way I am dealing with deleting
    // a node with 2 children. See above.
    while (candidate.getLeftNode != null) {
        candidate = candidate.getLeftNode();
    }

    return candidate;
}

Now your external caller isn't asked to pass information that it doesn't have.  And you don't have to check whether the method is being called internally or externally on every call.

I prefer the name candidate to smallest for accuracy's sake.  Until the last iteration, it's not the smallest.  It's a candidate to be the smallest on every iteration.

    }
    //Case 3: If node to be deleted has 2 children.
    else {

I'm not a fan of the half-cuddled else in the first place, but if you have to use it, please use it without separation.  It's bad enough that C-style languages (e.g. Java) do not explicitly end their if/then blocks.  Adding arbitrary content between the then block and the else just makes this worse.

    }
    else {
        // Case 3: If node to be deleted has 2 children.

Now I can easily see that there is an else.  I don't have to scroll down to the next statement to see if it might be an else.

Also, there are four cases, not three.  Your case 2 is two cases:  a null left child or a null right.

    while(data != current.getData() && current != null) {

This is a bug.  Create a test case where the data is not found and you'll see.


Hackerrank Insertion Sort Algorithm 1 (creating duplicates to show shifting)

A few points specifically for C#.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    // Method name should be in Pascal case.
    public static void PrintArray(int[] array)
    {
        // If it is known that x is an int, x.ToString() is more readable.
        // Also, rather than calling it 'b', you could give a more readable name.
        var strArray = array.Select((x) => x.ToString() + " ").Cast<string>();
        Console.WriteLine(String.Concat(strArray));
    }

    public static void InsertionSort(int[] unsortedArray)
    {
        // Why use Count() and Length in two lines?
        // You could choose the one you prefer and use it everywhere.
        // Also, if you are using var in PrintArray, you should be consistent in its use.
        var unsortedElement = unsortedArray[unsortedArray.Length];
        var i = unsortedArray.Length - 1;
        // I would prefer to keep it i >= 0, as it defines a valid range, rather than a single point.
        // There is no real difference, but it is more resilient against mistakes like having i-- statements twice.
        while (i >= 0)
        {
            // As pointed by others, i != 0 would be more readable.
            if (i > 0)
            {
                // Shift the element to right if it is bigger than unsorted element.
                if (unsortedArray[i - 1] > unsortedElement)
                {
                    unsortedArray[i] = unsortedArray[i - 1];
                    PrintArray(unsortedArray);
                }
                // Insert the element if the element at i - 1 is smaller or EQUAL to it.
                else
                {
                    unsortedArray[i] = unsortedElement;
                    PrintArray(unsortedArray);

                    break;
                }
            }
            // I prefer to keep a comment with else statements.
            // When i = 0, i.e. for the first element.
            else
            {
                unsortedArray[i] = unsortedElement;
                PrintArray(unsortedArray);

                break;
            }

            i--;
        }
    }
}


To get this code to compile I had to add the Sort namespace definition:

namespace Sort
{
    template <typename RandomIt, typename Compare = std::less_equal<>>
    void QuickSort(RandomIt first, RandomIt last, Compare compare = Compare());

    template <typename RandomIt, typename Compare>
    RandomIt Partition(RandomIt first, RandomIt last, Compare compare);

    template <typename RandomIt, typename Compare>
    RandomIt MedianOf3(RandomIt first, RandomIt last, Compare compare);
}

And I had to remove the default argument from the redeclaration of Sort::QuickSort:

template <typename RandomIt, typename Compare = std::less_equal<>>
void Sort::QuickSort(RandomIt first, RandomIt last, Compare compare)

Review requests should have issues like that already accounted for.

The performance of the Partition() function can be improved by doing fewer swaps.  The current loop swaps when *j < *pivot, without considering whether *i is less or greater than *pivot.  Instead, we can use two iterators, and advance them towards each other, swapping only when the ascending iterator points to an item greater than pivot and the descending iterator points to one smaller than pivot.  The tricky bit is to avoid the iterators passing each other without terminating.


Well your code is all broken.
But we will get to that as we answer your questions:
Answers to Questions

How do you keep track of includes? Even in this short example I now have includes that are not needed anymore.

Only include a header file if you need the class definition.
Forward declare everything else

Using this rule it is easy to only include files you need. In your header files only include other header files if you need them. You only need them if the object you are defining has a member of that type or is derived from that type (or takes a parameter to a method by value).
In all other situations forward declare.
This reduces the header count considerably.
In the source file you include all the header files of object you use to implement your code (that your header files have not included).
#ifndef BASE_H
#define BASE_H

#include <string>  // There is no need for this.
                   // There are no members that use string
                   // You are not deriving from string (who would)
                   // You are not passing a string as a parameter
                   // Remove this.

#include "IVisitable.h"

class Base : public IVisitable {
public:
    void acceptvisitor(Visitor v);  // By the way this is probably wrong.
                                    // You are passing by value and thus will
                                    // Make a copy.
                                    // Here you (if you really
                                    // wanted to pass by value) you should have
                                    // include "Visitor.h".
                                    //
                                    // But you don't want to pass by value you want
                                    // to pass by reference. So you just need to
                                    // forward declare.
};

#endif

Is this #ifndef treatment of header files still normal? I picked it up somewhere but have never actually seen anybody else do it.

Yes you should always place include guards around header files to protect from multiple inclusion.

Is there any way to treat an object as a superclass without a pointer? I.e. can I do something like this: Base d = Derived();

Well actually what you have written will compile:
Unfortunately it does not do what you expect. Here you have object slicing. The Base part of the object you created is sliced out and copied into d. What you need is a pointer (or a reference).
It looks like you are used to languages like Java. Where all objects are dynamically allocated. C++ has a much superior mechanism that allows us to accurately control the lifetime of the object. The disadvantage is that it adds complexity to the language.
What is called a pointer in C/C++ (to distinguish it from C++ references) would in most other languages be called a reference. C++ has both local objects (automatic storage duration object) and dynamically allocated objects (dynamic storage duration objects) thus we need a convention that allows access to both types of object, hence we use * to refer to objects that are dynamically allocated (to distinguish them from local objects).
BUT it is unusual to use pointers directly in C++ (unless you are implementing some real low level stuff). Most of the time when you dynamically allocate objects you will use a smart pointer that defines the lifespan of the object (much like other languages with garbage collection (but better)). std::shared_ptr<T> would be the equivalent of T in Java.
std::shared_ptr<Base>   d = new Derived();  // dynamically allocated object
                                            // That will be correctly destroyed
                                            // when there are no more references.

When can I use a forward declaration like "class Visitor;" and when do I need to include the actual header file. Or when should I?

As described above.
In the header file (were there is only declaration) only include another header if the header file defines a type that is a member or is used as a parent or used to pass a parameter by value (parameters are infrequent as they are normally passed by reference). In all other cases in a header file you should use forward declaration. In the source file include the header files that define types that you use (ie call methods on).
Note: You only need a forward declaration for objects that are pointers or references.

Should I make implementations of abstract functions virtual? It seems not to matter.

Only virtual methods can be abstract.
If you forget to define a method the compiler will not complain (as you may define it in another compilation unit). The linker will only complain if somebody tries to call the method and can't find a definition. So if you don't call it then there will be no error (but if you don't call it then it does not matter).
When you implement a virtual function in a derived class it is probably best to mark it as virtual to show a subsequent maintainer that it is virtual function (but it is not required by the language).
You should also note that C++11 introduces they keyword override. Which is an indicator that this method overrides a virtual method in a base class. If there is not such method in the base class it is a compilation error.
Other Notes
Your code passes all parameters by value. This is probably not what you want (as a copy will be made). If it is a derived type the base parameter type will be sliced out and passed to the method. So pass by reference.
class IVisitable {
    virtual void acceptvisitor(Visitor& v) = 0;
};                          //       ^^^   pass by reference

Also note that you can have more than one class defined in a file. Thus personally I would have put the IVisitable and Visitor patterns in the same file (they are tightly coupled anyway).


If you want only the numbers 0..9 to be matched by the Regex and you don't care about for instance some Eastern Arabic numerals like ´٠١٢٣٤٥٦٧٨٩, then you should use an expression like [0-9]+.
because by using either the d+ or [0-9]+ expression you already made sure that the var key is a number. Because this number has at the maximum 7 digits, you can simply call Parse() instead of TryParse() which eleminates the usage of the int num.
please add always braces {} although they might be optional. This will make your code less error prone.
the return statement

return "TG" + new string('0', 7 - newNum.Length) + newNum;

can be simplified by using the PadLeft() method like so

return "TG" +  newNum.PadLeft(7,'0');

personally I would just have a if clase for checking the highest number instead of the List<int> together with the call to Max().

Putting this all together leads to

static string GenerateKey()
{
    int max = int.MinValue;
    var keys = allKeys.Where(k => k.StartsWith("TG"));
    foreach (var key in keys.Select(str => Regex.Match(str, @"[0-9]+").Value))
    {
        int num = int.Parse(key);
        if (num > max)
        {
            max = num;
        }
    }

    return "TG" + (max + 1).ToString().PadLeft(7, '0');
}


My first thought was that there wasn't much that you could do.  However, it does occur to me that you don't need to have both the vector and map variables.

private std::map<int,int> count_for;

protected void count_factors(int &n, int factor) {
    // if factor is not actually a factor of n, nothing to do
    if ( n % factor != 0 ) {
        return;
    }

    // initialization only needs to be done once,
    // so do it before the loop
    // we already checked that this is a factor and should be in the map
    count_for[factor] = 0;
    do {
        count_for[factor]++;
        n /= factor;
    } while ( n % factor == 0 );
}

public void generate_factors(int n) {
    // handle the only even prime separately
    count_factors(n, 2);

    // note that if a particular value of i is not prime,
    // then it won't divide n evenly
    // as we will have removed all its factors from n already
    for ( int i = 3; i <= n; i += 2 ) {
        count_factors(n, i);
    }
}

public ostream & display(ostream &out) {
    for ( const auto &p : count_for ) {
        out << p.first << "^" << p.second << " ";
    }
    out << endl;
}

I don't have a C++ compiler at the moment, so I haven't tested any of this.

Some other comments.  Note that I put those functions in a class.  That gets us away from the global variables of the original program and puts the code in a more sustainable location.  We can reuse the code in other programs easily.

When doing comparisons in a loop, you want to minimize the number of operations.  Thus, i <= n is better than i < n + 1.  Similarly, try to avoid making function calls as in i < factors.size().  If the result won't change during the loop, do the function call in the loop initialization, like so

for ( int i = 0, m = factors.size(); i < m; i++ )

When doing a modulus operation, there's one special result 0.  I don't know that there's a way to get a negative result, but if there is, you don't want one.  So write it as you mean it n % i == 0 not n % i < 1.  Note that this would be different if you were doing something like

for ( int i = n; i >= 0; i-- ) {
    // do stuff with i
}

Then you'd want to guard against i changing in addition to the decrement, so you use the inequality.

        factormap.insert(std::pair<int,int>(factors[i],std::count(factors.begin(), factors.end(), factors[i])));

That's an awful lot of things happening in one line.  It's often easier to read something like that if you assign the results of the function calls to variables rather than chaining them like that.  Also, some errors won't do a good job of identifying what prompted them, but they'll usually tell you the right line.

If you're using a C++11 compiler, then you can use range-based for loops.  If not, then stick with your original iterator approach.

The printf function comes from C.  While it will work in C++, the C++ way is to use std::cout.  I used a display function, but you could also overload the << operator to similar but more flexible effect.


Debug merge sort and validate comparison counters

Here's some suggestions on what you can do differently to get a better result (both performance counters and code style).

The MergeSortRun class breaks many rules for naming conventions in Java.... well, actually the class name is OK (MergeSortRun), but the method (also called MergeSortRun) is very confusing, because only the constructor (which you don't have coded up) is supposed to have that name.

Rename the MergeSortRun method to something simple like 'sort'.

Additionally, the variables 'counterOne' and 'displaylist' are not necessary... if it were me, I would have 'counterOne' returned from the sort method, and the displaylist variable is completely dead anyway. Doing this will allow you to make the sort method static, of the form:

public static final int sort(int array[], int lo, int n) {...}

The 'int' return value is the number of comparisons you want to count.

Now, you have to question what your counter should be. There are two key items that tend to impact performance of sorts. The one is comparisons, and the other is data-moves (or swaps).

Since your input data is an int[] array, the comparisons between values are just as expensive as any other int based comparison. Thus, I think you should potentially be counting much more. The easiest way to do it is to show you what I think it should look like:

public int sort(int array[], int lo, int n) {
    int low = lo;
    int high = n;
    int compares = 1;
    if (low >= high) {
        return compares;  // NOTE - 1 comparison (low >= high)
    }
    int middle = (low + high) / 2; // technically should be: (low + high) >>> 1
    compares += sort(array, low, middle);
    compares += sort(array, middle + 1, high);
    int end_low = middle;
    int start_high = middle + 1;
    while ((lo <= end_low) && (start_high <= high)) {
        compares += 3; // two in 'while' loop above, and one in 'if' below.
        if (array[low] < array[start_high]) {
            low++;
        } else {
            int Temp = array[start_high];
            compares++; // entry in to the for loop
            for (int k = start_high - 1; k >= low; k--) {
                array[k + 1] = array[k];
                compares++; // exit from the for loop
            }
            array[low] = Temp;
            low++;
            end_low++;
            start_high++;
        }
    }
    return compares;
}


I don't see anything ugly about your Cast module. If it was .Net I would use a Static (Shared) type class, and a standard *.bas module is roughly equivalent in VB6. It seems to have been the right move to me.

What I do question is the usefulness of defaulting to the object's pointer as a string representation of it. Since VB6 supports default properties, I would take advantage of it. It's not exactly pretty, but perhaps a more useful representation of an object.

Private Function TryCastToString(x As Variant) As String
    On Error GoTo ErrHandler

    TryCastToString = CStr(x)

    Exit Function

ErrHandler:
    Const MethodNotSupportedError As Integer = 438

    If Err.Number = MethodNotSupportedError Then
        TryCastToString = "&" & ObjPtr(x)
    Else
        Err.Raise Err.Number, Err.Source, Err.Description, Err.HelpFile, Err.HelpContext
    End If
End Function

Which would change this function:

Private Function DefaultObjectToString(ByVal x As Object) As String

    DefaultObjectToString = ObjectToString(x, cast.CArray(Array("&" & ObjPtr(x))))

End Function

Into this:

Private Function DefaultObjectToString(ByVal x As Object) As String

    DefaultObjectToString = ObjectToString(x, cast.CArray(Array(TryCastToString(x))))

End Function

This provides a much nicer string back. Consider a workbook with a value of "Hello!" in cell A1 and the following code.

Public Sub test()
    Debug.Print Cast.ToString(ThisWorkbook)
    Debug.Print Cast.ToString(Range("A1"))
End Sub

This would result in the following:

Workbook(&2349672)
Range(Hello!)


Consider using Arrays.asList("", ...) to create lists in-line.
Why are colors and models Lists while cars is an Array? It seems like you can use Arrays for all of this.
Consider using "anonymous arrays" (terrible name) to create Arrays in-line.
Consider first building the "true" data structure as int[][] car_counts = new int[7][7], a zero-indexed 2D array of counts. Then treat the task of printing it as shown in the image as a separate problem.
Your while loop at the end appears to be incorrectly indented.
That while loop should be building a data-structure that you can neatly read the file into: a list of pairs of strings. (or even a list of pairs of ints, representing indexes into models and colors.)


Unnecessary code

This function is puzzling to me:

static void clearAndCopy(char *destination, const char *source, unsigned size) {
    memset(destination, 0, size);
    memcpy(destination, source, size);
}

Why do you need to clear the destination buffer when you are going to copy over it immediately afterwards?  All calls to this function could simply be replaced by calls to memcpy instead.

Memory leak

In split_free(), you forgot to free (*s)->tokens.

Allocation strategy

There are two things I would do differently with respect to how you allocate your tokens:

Instead of using realloc to dynamically resize your token array, I would prescan the input and determine how many tokens there will be, and just allocate once.  This avoids a possible \$O(n^2)\$ reallocation time.
Instead of allocating a buffer for each token and copying the token to it, I would make a single copy of the input string, and then have s->tokens[i] be pointers to the tokens within the single copy.


Is this an efficient implementation of the Roman Numeral Converter?

See link above in comments for some more elegant solutions. So I am not going to focus on algorithm, which I think can certainly be improved.

Some thoughts on your code itself:

Comments don't seem to make sense or add value.
No need for all the if-else stuff. Would be much clearer with just if conditions and breaks, IMO.
I don't understand why you build digitArray the way you do. How about something like num.toString().split('').map(function(t){return parseInt(t)}) or Array.from(num.toString()).map(Number) (ES6)?
Your spacing around conditional and flow-control structures (or really, lack thereof) makes your code hard to read.
Indentation is inconsistent.
Seems to be odd use of vertical whitespace.


Replacing files with symlinks to other files

#!/usr/bin/env python -tt

"""Xcode4 installs and expects to find a git installation at /usr/bin.
This is a pain if you want to control your own installation of git that
might be installed elsewhere. This script replaces the git files in
/usr/bin with symlinks to the preferred installation.

Update the 'src_directory' to the location of your preferred git installation.
"""
import sys
import os

#- Configuration  -----------------------------------------------------------------
src_directory = '/usr/local/git/bin/' # preferred installation
#----------------------------------------------------------------------------------

dest_directory = '/usr/bin/'
files = ('git','git-cvsserver','git-receive-pack','git-shell','git-upload-archive','git-upload-pack','gitk')

The official python style guide recommends using ALL_CAPS to name global constants. Additionally, some of these constants might be better as command line arguments to the script. That way you don't need to modify the script to install to a different location.

def main():
    if os.getuid():

I suggest using if os.getuid() != 0 because I think its better to be explicit. The code will run the same, but this way I think its clearer that you are checking for zero rather then an actual boolean value.

        print "This script needs to be run as 'sudo python update_git.py'"
        sys.exit(1)

    for a_file in files:

a_file is kinda ugly. I'm guessing you are using it to avoid replace the builtin file. I suggest filename.

        src_file = os.path.join(src_directory, a_file)
        dest_file = os.path.join(dest_directory, a_file)

        if os.path.exists(dest_file):
            os.remove(dest_file)

What if someone deletes the file between your script checking if it exists and deleting it? Also checking if the file exists duplicates effort that remove will have to do. You could rewrite the code to try remove, and then catching the doesn't exist exception. I wouldn't bother here though.

        os.symlink(src_file, dest_file)

if __name__ == '__main__':
    main()

You don't catch any exceptions. In a script this simple that might be okay. But it might be a good idea to try/catch IOError/OSError and print them out for the user hopefully with enough detail that the user can tell whats going wrong. If you don't the exception will be dumped, but the user will also see a stack trace which might be scary.


This seems quite reasonable as a baseline for CSRF protection. Critically, you must ensure that you do not set the Access-Control-Allow-Origin (CORS) header to a wildcard, otherwise an attacker can just perform an Ajax request to your site and gain access to the CSRF token.

A criticism of single global CSRF tokens is that that exposing the CSRF token allows re-use across different requests, which can be avoided. The upside of the single global token model is that it is very simple to implement and therefore has less chance of bugs. Additionally, it is unlikely that an attacker will gain read-access to only one page and not others, particularly as XSS would allow Ajax requests to other pages on the same origin (same domain).

If you wish to generate tokens that are locked to their initial purpose (i.e. a particular form target URI), a fairly sensible approach is to use HMAC-SHA256 to generate each token. Generate a global CSRF key as part of your session data, then for each token you need to generate compute a HMAC-SHA256 digest of the target URI using the CSRF key as the HMAC key, then inject that digest as the CSRF token in the form. For validation, take the request URI and hash it using the CSRF key, then compare that to the CSRF token provided as part of the request.

If you're building any kind of framework to handle MVC or MVVM then I would implement the CSRF protection as a by-default for all requests in the parent view or controller class, then have a way to opt-out of CSRF validation explicitly. CodeIgniter 3.x handles this quite nicely, so you should check out their code as an example.

One thing I would probably add is logging of cases where CSRF validation fails, although the way you do that is very much down to your platform.


Naming:

Like the previous answer stated, your classnames are far from following conventions. The should be PascalCase and not camelCase. Also a name like dxRpt12MonthsItemPurchaseAnalysisByAmount is definitly not meaningful, not for you, not for others who read your code. Try names like FirstReportForm, FirstFilterForm or FilterForm1, ReportForm1 and so on.

Tip: Names of Classes, Structs, and Interfaces

Braces:

Microsoft doesn't have any conventions on the formatting of your braces. This means you can chose between following:

if (isValid) {
    DoSomething();
}

and

if (isValid)
{
    DoSomething();
}

But it's best practice to stick with one and not to mix the two up in your code. (I prefer the second use of braces.)

Logical use of variables:

In both click event handlers you instantiate a new filter. Whether or not document is null, you call CreateWindows with again a new instance of that filter-class. Just re-use the instance you created before. You didn't manipulate it in any way.

Generic method:

First of all, the following code is written out of my head and not tested as I have little information what all your classes are/mean. But here's an attempt to make it generic:

private void HandleButtonClick<T>(Form filterForm) where T : Form, new()
{
    var document = FindDocument<T>();

    if(document == null)
    {
        CreateWindows(filterForm, new T(), sender, e);
    }
    else
    {
        tabbedView1.Controller.Activate(document);
        if (this.ActiveMdiChild is T)
        {
            filterForm.Focus();
        }
    }
}

And the usage of the method:

private void button1_ItemClick(object sender, ItemClickEventArgs e)
{
    HandleButtonClick<ReportForm1>(new FilterForm1());
}

private void button2_ItemClick(object sender, ItemClickEventArgs e)
{
    HandleButtonClick<ReportForm2>(new FilterForm2());
}

Notes:

T is the type of the report form
The new() constraint is set on the method, check tip for more info
I reversed the null check for readability, this might be personal choice

Tip: new Constraint (C# Reference)

I cannot reproduce your code and therefore cannot test the method. Please let me know if you got it to work using this method. Hope this helps!


GCD calculation - A cross of the Euclidean and the Binary algorithm

Introduction

Rabindranath Tagore said:

  "যদি তোর ডাক শুনে কেউ না আসে তবে একলা চলো রে..."
  Translated: "If no one responds to your call, then go your own way alone..." 1

After waiting for two whole days in vain, I've decided to answer my own question. In these two days, I've tried several methods and made certain interesting observations. Here, I shall present them in a logical order.

First, the Euclidean algorithm

Here is the implementation of the "Modern Euclidean Algorithm" (Algorithm A, TAOCP Vol - 2, Pg - 337, Section - 4.5.2) in Java:

/**
 * Returns the GCD (Greatest Common Divisor, also known as the GCF -
 * Greatest Common Factor, or the HCF - Highest Common Factor) of the two
 * (signed, long) integers given.
 *

 * It calculates the GCD using the Euclidean GCD algorithm.
 *
 * @param u The first integer (preferably the larger one).
 * @param v The second integer (preferably the smaller one).
 * @return The GCD (or GCF or HCF) of {@code u} and {@code v}.
 */
public static long euclideanGCD(long u, long v) {
    // Corner cases
    if (u < 0) u = -u;
    if (v < 0) v = -v;
    if (u == 0) return v;
    if (v == 0) return u;
    // Correction
    if (u < v) {
        long t = u;
        u = v;
        v = t;
    }
    // A1
    while (v != 0) {
        // A2
        long r = u % v;
        u = v;
        v = r;
    }
    return u;
}

In order to test it, I wrote this class:

class Test {
    public static void main(String[] args) {
        // Warm-up
        int g = 0;
        while (++g > 0)
            Math.sqrt(g);
        // Timing starts
        long time = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 20000; i++) {
            for (int j = 0; j < i; j++) {
                sum += GCD.euclideanGCD(i, j);  // Over here
            }
        }
        time = System.nanoTime() - time;
        System.out.println("sum  = " + sum);
        System.out.println("time = " + time);
    }
}

Here is its output:

sum  = 1352820356
time = 35306053968

So, it took 35.3 seconds on my Windows 7 Laptop with a 2.1 Gz Intel Pentium processor. (If we run the test again, the time will of course be different, but it will be in the range: 34-36 seconds). We shall use this time as the reference point (and the sum to test the correctness of the other methods). Now, let's try and improve upon this. Here are a few points to note:

This method is horribly slow because of the divisions (modulo operations) that it has to perform. We can improve upon this by making every effort to make the divisors smaller.
It also has so many (rather unnecessary) assignment operations. This is also a factor that reduces the speed.

Keeping these points in mind, I wrote the method that I had provided in the question. For convenience, here it is again (now well documented):

The "Better" Euclidean algorithm

/**
 * Returns the GCD (Greatest Common Divisor, also known as the GCF -
 * Greatest Common Factor, or the HCF - Highest Common Factor) of the two
 * (signed, long) integers given.
 *

 * It calculates the GCD using a modified form of the Euclidean GCD algorithm.
 *
 * @param u The first integer.
 * @param v The second integer.
 * @return The GCD (or GCF or HCF) of {@code u} and {@code v}.
 */
public static long euclideanGCD2(long u, long v) {
    // Corner cases
    if (u < 0) u = -u;
    if (v < 0) v = -v;
    int a0 = Long.numberOfTrailingZeros(u);
    int b0 = Long.numberOfTrailingZeros(v);
    // Make both of them odd.
    u >>>= a0;
    v >>>= b0;
    // t is the common power of 2 (may be 0)
    int t = a0 < b0 ? a0 : b0;
    while ((u & v) != 0) {  // i.e. both are non-zero
        if (u > v) {
            u %= v;
            u >>>= Long.numberOfTrailingZeros(u);
        } else {
            v %= u;
            v >>>= Long.numberOfTrailingZeros(v);
        }
    }
    return (u | v) << t;    // {the non-zero value of the two} * 2^t
}

We test again by changing the line marked withe the comment to sum += GCD.euclideanGCD2(i, j);

Here is the output:

sum  = 1352820356
time = 26400006940

This is a definite improvement (of around 25.2%), and this is about as far as we can go without any other help. But can go further if we use the Binary GCD algorithm. So here it is:

The binary GCD algorithm

/**
 * Returns the GCD (Greatest Common Divisor, also known as the GCF -
 * Greatest Common Factor, or the HCF - Highest Common Factor) of the two
 * (signed, long) integers given.
 *

 * This uses the Binary GCD algorithm.
 *
 * @param a The first integer.
 * @param b The second integer.
 * @return The GCD (or GCF or HCF) of {@code a} and {@code b}.
 */
public static long binaryGCD(long a, long b) {
    // Corner cases
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (a == 0) return b;
    if (b == 0) return a;
    int a0 = Long.numberOfTrailingZeros(a);
    int b0 = Long.numberOfTrailingZeros(b);
    int t = a0 < b0 ? a0 : b0;
    a >>>= a0;
    b >>>= b0;
    while (a != b) {
        if (a > b) {
            a -= b;
            a >>>= Long.numberOfTrailingZeros(a);
        } else {
            b -= a;
            b >>>= Long.numberOfTrailingZeros(b);
        }
    }
    return a << t;
}

The output is:

sum  = 1352820356
time = 13381525510

So, the improvement is quite dramatic (around 60% compared to the original). Now, we know that this algorithm slows down when \$u\$ and \$v\$ have very different bit lengths. So, let's try and improve this:

The "Hybrid" GCD algorithm

/**
 * Returns the GCD (Greatest Common Divisor, also known as the GCF -
 * Greatest Common Factor, or the HCF - Highest Common Factor) of the two
 * (signed, long) integers given.
 *

 * It uses a hybrid of Euclidean and the binary GCD algorithm.
 *
 * @param a The first integer.
 * @param b The second integer.
 * @return The GCD (or GCF or HCF) of {@code a} and {@code b}.
 */
public static long hybridGCD(long a, long b) {
    // Corner cases
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (a == 0) return b;
    if (b == 0) return a;
    int a0 = Long.numberOfTrailingZeros(a);
    int b0 = Long.numberOfTrailingZeros(b);
    int t = a0 < b0 ? a0 : b0;
    a >>>= a0;
    b >>>= b0;
    while ((a & b) != 0) {
        // if 'a' and 'b' have almost same bit length
        if (Math.abs(Long.numberOfLeadingZeros(a)
                - Long.numberOfLeadingZeros(b)) < 2) {
            return binaryGCD(a, b) << t;
        }
        // use Euclidean algorithm
        if (a > b) {
            a %= b;
            a >>>= Long.numberOfTrailingZeros(a);
        } else {
            b %= a;
            b >>>= Long.numberOfTrailingZeros(b);
        }
    }
    return (a | b) << t;
}

The output is:

sum  = 1352820356
time = 19178926693

Well, that's interesting! :-) It seems that our "optimized" algorithm is actually slower than the un-optimized version of the binary algorithm. This occurs because the difference in bit-length is not such a big factor in case of the binary algorithm(i.e. 64 bits max in case of long). Sure enough, if we change the length-checking value from 2 to 4, we see that the running time is ~16 seconds.

Conclusion

Here, we have seen that:

Division-based algorithms should generally be avoided.
Premature optimization seldom pays off.
Shifts, additions and subtractions are the way to go in a binary environment.

Hence, the answers are:

Yes, but there can be more.
Many, many improvements... For starters, try reducing the absolute values of the remainders.
If the library supports integers which can have huge differences in bit-length. Otherwise, I'd use the Binary GCD algorithm for long.

1 See this article for more info on the song.


Finding whether there exists a pair of numbers in a set having a given product

The algorithm description is good, but the implementation of find is \$ O(n) \$, so the overall runtime is actually \$ O(n^2) \$.

Detailed review follows:

There are no docstrings. What does each function do? How do I call it? What does it return? Are there any constraints on the parameters, for example do the inputs have to be sorted? or do they have to be free of duplicates?
It's not necessary in Python to have parentheses around the condition of if statement, and it's best to omit them.
According to the analysis, find needs to be \$ O(\log n) \$, but the actual implementation is \$ O(n) \$. Here's a demonstration:

>>> from timeit import timeit
>>> for p in range(2, 8):
...     items = list(range(10**p))
...     '{:f}'.format(timeit(lambda:find(0, items), number=1))
...
0.000012
0.000022
0.000077
0.001386
0.038858
0.417670

The reason for this is the copying in the recursive calls. In Python, the list slice items[mid:] has to be copied, and the time taken to do this is proportional to the number of items in the copy. See the time complexity page on the Python wiki.
In order to avoid copying in find, it's best to keep indexes into the part of the sequence which might contain the item we're looking for:

def find(x, items):
    """Return True if x is an element of the sequence items, assuming
    items is sorted.

    """
    lo = 0
    hi = len(items)
    while lo < hi:
        mid = (lo + hi) // 2
        if x == items[mid]: return True
        elif x < items[mid]: hi = mid
        else: lo = mid + 1
    return False

Python has a built-in module bisect for binary search of sorted sequences, and using this module it's possible to write find like this:

from bisect import bisect_left

def find(x, items):
    """Return True if x is an element of the sequence items, assuming
    items is sorted.

    """
    i = bisect_left(items, x)
    return i < len(items) and items[i] == x

The corrected version of find locates an element in a sorted list in time \$ O(\log n) \$. But it's possible to do better than that using a set. Set lookup has average complexity \$ O(1) \$.
The implementation of merge goes into an infinite loop if list1 and list2 have a common item. This was easy for me to spot because there is an if … elif with no else at the end. When code has a sequence of conditions like this, it's always worth asking, "what happens if none of the conditions apply?"
Python has a built-in function heapq.merge for merging sorted iterables into a single sorted iterator, and a built-in function sorted for sorting an iterable (using a variant of mergesort, as it happens). These are fast and well-tested implementations, and (except as an exercise) they should be used in preference to writing your own.
In findIfProdExists the division x/item is computed twice in some cases.
It would be better to compute it once and remember the value.
In findIfProdExists the cheap test item!=x/item is computed after the expensive test find(x/item,items). It's usually best to compute cheap cases first so that if they fail the expensive test can be avoided altogether.

Putting all this together, I'd implement the algorithm like this:

def product_pair(x, items):
    """Return True if there is a pair of distinct elements in the iterable
    items whose product is x. Return False otherwise.

    """
    items = set(items)
    for item in items:
        if item != 0 and x % item == 0:
            y = x / item
            if y != item and y in items:
                return True
    return False


In production Java code, you would never reverse a string using recursion, primarily due to efficiency concerns, and also because new StringBuilder(str).reverse().toString() is better.  Therefore, this question should be treated as an academic exercise — a quick test to weed out candidates who don't understand recursion at all.  I don't think that an optimal solution is required.

Basically, your solution is good enough.  That said…

I prefer your reverse() to reverseRecursively(), since I consider the recursion to be an implementation detail that doesn't need to be reflected in the name.
str is a more appropriate parameter name, since the function doesn't care whether the string is a word or not.
The way you sliced the string is less elegant than in the second solution.
I find your brace style slightly irksome.  (Normally I wouldn't say anything about it, but given how little code I have been given to evaluate, I'm judging you on that.)  Try to stick to the obsolete official Java style guide or Google's Java style guide, which is a close derivative of it.


Faster Django CSV generation for several million database entries

1. Introduction

By coincidence, I'm working on a similar problem right now, so here's a chance for me to write up an experiment I ran today, in the hope that it might prove useful. However, the solution presented below is far from ideal (see section 3).

2. The idea

Processing your query results through Django's ORM and then through csv.writer is time-consuming. You can speed things up by getting the database to write the query output directly to a file and then serving that file.

First, your database user needs to have FILE privilege in order to be able to write files:

mysql> GRANT FILE ON *.* TO 'user'@'host';

Then you need to run your query with MySQL's INTO OUTFILE clause. You can get the query you need from Django by calling .query.sql_with_params():

from django.db.models import Q
s101 = Q(fwy='101', dir='S', abs_pm__gte=420.80, abs_pm__lte=431.63)
s280 = Q(fwy='280', dir='S', abs_pm__gte=41.16, abs_pm__lte=56.49)
sql, params = Station.objects.filter(s101|s280).query.sql_with_params()

Add the INTO OUTFILE clause:

sql += ''' INTO OUTFILE %s
           FIELDS TERMINATED BY ','
           OPTIONALLY ENCLOSED BY '"'
           LINES TERMINATED BY '\n' '''

Pick a place to put the CSV:

import os.path
csv_path = os.path.join(csv_directory, csv_filename)

Run the query:

from django.db import connection
cursor = connection.cursor()
cursor.execute(sql, params + (csv_path,))

Send the file (using StreamingHttpResponse which is new in Django 1.5):

from django.http import StreamingHttpResponse
response = StreamingHttpResponse(open(csv_path), content_type='text/csv')
response['Content-Disposition'] = 'attachment; filename=' + csv_filename
return response

3. Analysis

In my test cases (about a million records) this is around ten times as fast as processing the data through csv.writer in Python.

But there are several problems, mostly related to security:

This depends on the MySQL server being on the same machine as the Django web server. You can imagine working around this by some kind of reverse proxying but it all gets rather complicated.
Granting FILE access to your MySQL user is dangerous because it means that a SQL injection attacker can read and write files on your disk. You might want to create a separate MySQL user just to generate these CSV files, and you'll definitely want to set MySQL's secure_file_priv variable.
Even if the attacker can't inject SQL, they may be able to cause your disk to fill up with these temporary files. You need a plan for how they are going to be deleted. (Maybe using the request_finished signal?)
You need to find somewhere safe to put them (a directory to which the MySQL database user has write access).

4. Update

I did some more timing experiments today, trying out five different ways of generating and downloading the CSV, summarized in the table below:

+------+-----------------------+-------+
|      |     through Django    |Direct |
|      |Streaming|Not streaming|from DB|
+------+---------+-------------+-------+
|ORM   |      630|          370|    N/A|
+------+---------+-------------+-------+
|No ORM|      190|          125|     58|
+------+---------+-------------+-------+

Notes on the table:

Times are in seconds.
This is for a query with a million rows that generates 150 MiB of CSV.
"ORM" means that I passed the query results through Django's object-relational mapping system before generating the CSV.
"No ORM" means that I avoided this by running a custom SQL query.
"Streaming" means that I used a StreamingHttpResponse and generated the CSV one line at a time using a technique I'll describe below.
"Not streaming" means that I used the technique described in the Django documentation to generate the CSV. (This involves reading the entire CSV output into memory, which is a bit painful for other processes running on the server.)
"Direct" is the technique described in section 2 above, using MySQL's INTO OUTFILE clause.

Clearly Django's ORM and Python's csv.writer are both significant bottlenecks. If only the INTO OUTFILE approach weren't so painful!

So I would still be interested to see other suggestions for speeding up this operation.

5. Appendix: streaming CSV download

Python's csv module doesn't provide an easy way to generate one record at a time, but you can coerce it into doing so like this, using io.BytesIO to capture the output:

from io import BytesIO

def writerow(row):
    """Format row in CSV format and return it as a byte string."""
    bio = BytesIO()
    csv.writer(bio).writerow([unicode(r).encode('utf-8') for r in row])
    return bio.getvalue()


If you don't care about the origin list, we can use the head of it as the iterator, You should return the new head after reverse, or the new list will lost.

#include <stdio.h>

struct Node
{
    int data;
    Node* next;
    Node(int value, Node* ptr):data(value), next(ptr){}
};

// Reverse list and return the new head
Node* reverse_list(Node* head)
{
    Node* p = NULL;
    Node* q = head;
    while(q)
    {
        Node* t = q->next;
        q->next = p;
        p = q;
        q = t;
    }

    return p; // new head
}

void print_list(Node* head)
{
    Node* t = head;
    while(t)
    {
        printf("%d\n", t->data);
        t = t->next;
    }
}

void main()
{
    Node* head = new Node(1, NULL);
    Node* p = head;
    for(int i = 2; i < 10; ++i)
    {
        p->next = new Node(i, NULL);
        p = p->next;
    }
    print_list(head);

    Node* newHead = reverse_list(head);
    print_list(newHead);

    getchar();
}


Having graphics resize in line with the Frame in Swing

Naming and Initialization

It's very hard to read when many variables are initialized on a single line.

numN naming pattern is also confusing. Since they correspond to coordinates, why not name them like this?

final int topLeftX = getWidth()/4
final int topLeftY = getHeight()/4
final int bottomRightX = ...

The 4 number may also be extracted into a vairable.

Draw a Rectangle

If I'm not mistaken, with drawLine(args) you are trying to draw a rectangle. It may be replaced with the respective method call, thus reducing the stuff to a single line:

g.drawRect(topLeftX, topLeftY, width, height);


Find All Numbers Disappeared in an Array

You have created a good solution, just a few style points that can reduce code size.

Why null rather than false or even 0 in arr[x - 1] = null;

Why not use commas to remove need for return. Eg .reduce((arr, x) => {arr[x - 1] = null; return arr; } becomes .reduce((arr, x) => (arr[x - 1] = null, arr))

To create an array of indexes you could have used the shorter forms, Array.from(nums, (item, i) => i + 1)) or nums.map((item,i) => i + 1)

Rewrites
function findMissing(arr) {
  return arr
    .reduce((a, i) => (a[i - 1] = 0, a), arr.map((item, i) => i + 1))
    .filter(Boolean);
}

or
const findMissing = arr => arr
  .reduce((a, i) => (a[i - 1] = 0, a), arr.map((item, i) => i + 1))
  .filter(Boolean);

You could also have solved it with a set as follows
function findMissing(arr) {
    const s = new Set(arr), res = [];
    var i = arr.length;
    while (i) { s.has(i--) || res.push(i + 1) }
    return res;
}


I don't think I completely know what is going on in your code.

but there is one thing that I think you are doing wrong.

you are creating a connection over the web and trying to force it to stay open.

your web application should

Connect
Send or receive the information that it needs
Disconnect

you should never leave a connection open for extended periods of time.

every time you need something from the server, open a new connection, when you are finished close the connection.

I may be way out of line, but that struck me as off about the way you explained that part of your application


Find The One Element In An Array That is Different From The Others

This is a similar idea to the other answers here, but the implementation is a bit different.

First of all, we can assume that the array's length is at least 3, since it needs to have at least two of the same values and one different value.

Let's start by handling the case where the stray value is not in the first element. We could simply write:

a.find(v => v != a[0])

That is, find an element that's different from the first element. But what if the stray element comes first in the array? We can check if the first two elements differ. If they do, then the stray is either in the first or second position, so the third element is not a stray. In this case, we can check against the third element instead of the first; otherwise we check against the first element as before, thus:

a.find(v => a[0] != a[1] ? v != a[2] : v != a[0])

This is a bit code-golfey and not very readable, so I wouldn't recommend it in production, but it may be of some interest as a curiosity.

It may be worth noting that this solution appears to perform quite well, and can be further optimized by doing the inequality check on the first two elements before invoking find, and by using the third parameter to find to access the array, making the callback a pure function and eliminating the need to reference the array via the closed-over variable, for example:

a.find(a[0] != a[1] ?
    (v, i, a) => v != a[2] :
    (v, i, a) => v != a[0])


Some comments:

&& modelList.size() > 1

this check is redundant, in fact

if (prevList.size() > 1 && modelList.size() > 1 && prevList.size() == modelList.size()) {

this whole check doesn't depend on the for variable, and can be hoisted outside the for.

The big if that starts at the first line can be inverted to reduce nesting.


First, let me ungolf and simplify your code slightly, so it will be easier for me to read:

import System.Random

pick :: Int -> [a] -> (a,[a])
pick 0 (x:xs) = (x, xs)
pick i (x:xs) = let (y,ys) = pick (i-1) xs
                in (y, x:ys)
pick _ []     = error "pick: Invalid index"

shuffle :: [a] -> IO [a]
shuffle lst = runner (length lst) lst
  where
    runner :: Int -> [a] -> IO [a]
    runner 0 xs = return xs
    runner i xs = do
      r <- randomRIO (0, i-1)
      let (y,ys) = pick r xs
      (y:) <$> runner (i-1) ys

Every call to pick is O(i), since you need to iterate through on average half of the array to extract the value and move it to the front. In when calling pick, i is on average equal to n/2 (where n is the length of the list). runner is called recursively n times.

So in conclusion, pick has time complexity O(n) and shuffle has time complexity O(n^2), which is indeed much worse than linear, but not quite exponential as you feared. There are also some minor issues with your functions not being tail recursive, but that should only affect constant factors and memory usage, not complexity.

This also matches your measurements, since 0.57 * 10^2 ≈ 6.81

If you compare it to the modern method which you linked, that code instead uses a swap operation which is O(1), which gives you the promised O(n) complexity.

On a side-note, your javascript version of the algorithm has the same problem, since Array.splice is an O(n) operation.

So, to your questions:

Can we improve the time complexity while using the list type?

No. Not unless we change the algorithm to something different, which in a way you have already done in both your implementations by not using the swap operation. An O(1) swap operation for lists is not available, since all random access costs O(n). You can however easily fix it in your js-version (see here).

If you do want to use a different algorithm, there are O(n*log n) algorithms that works on lists, which is not quite linear, but it's the best we can get for lists. You could also use the same algorithm with a Map, which has O(log n) swap operations.
Unboxed types and similar gimmicks will only only help with constant factors, not algorithmic complexity. However, what would help a lot is to use a mutable array or vector. They do have an O(1) swap operation. They come in both an IO version and an ST version which can be used from pure functions.

There are a number of different implementations of a random shuffle function on this page, including Fisher-Yates with both a Map (O(n*log n)) and a mutable Array (O(n)).


Summing two objects without altering either

Since you're using ES2015 destructuring assignments you can use Set and spread:

function mashObj(a, b) {
    var sum = {};
    new Set([...Object.keys(a), ...Object.keys(b)])
        .forEach(k => sum[k] = Math.round(a[k]||0) + Math.round(b[k]||0));
    return sum;
}


Parsing and formatting a time two ways (perfectionistic approach)

In the 2nd version, the if acts as a guard: it prevents invalid states to get through it. Many people prefer it this way, for example in this related post:
Should I return from a function early or use an if statement?

Which way you choose, is a matter of taste. There's nothing wrong with either one.

If you do go with the 2nd one, it can be improved a little bit:

public override void OnEventTimeChanged()
{
    TimeSpan eventTime;
    if (!TimeSpan.TryParse(EventTime, out eventTime))
    {
        return;
    }

    DateTime eventDateWithTime = EventDate.Date + eventTime;
    CultureInfo cultureInfo = Thread.CurrentThread.CurrentUICulture;
    string eventTimeString = String.Format(cultureInfo, "{0:HH:mm}", eventDateWithTime);

    EndTime = eventTimeString;
    EndDate = eventDateWithTime;
}

That is:

cultureInfo is not needed in the if, so declare and initialize it later. Even more precisely, declare and initialize it right before you really need it.
It's recommended to use braces with if statements always, even if only one line will go inside the block. Remember this bug: https://www.imperialviolet.org/2014/02/22/applebug.html


1. Review

The bfs function relies on a global variable distance. This make it hard to test (you have to remember to set up the distance list before you call bfs) and means that it can't be used from multiple threads. It would be better if bfs constructed all its own data structures.
The path variable is a tuple of all the vertices that have been visited so far. Adding a new element to the path, as in path = path + (u,), requires copying out the old path. This makes the overall runtime \$\Omega(n^2)\$. But path is not actually used for anything, so you could just remove it.
queue.Queue is a thread-safe data structure intended for use by multi-threaded programs. It has to take and release a lock for every operation, so it is overkill to use this in a single-threaded program. It is more than ten times faster to use collections.deque instead.
The code handles the exceptional situation (no path is found) by returning an exceptional value (−1). This is an error-prone design because it would be very easy for the caller to forget to check for the exceptional value. It would be easy to write code like this:

dist = bfs(graph, start, end)
if dist <= goal:
    print("reachable in {} steps or fewer".format(goal))

which would go wrong when dist is -1. It's better to handle an exceptional situation by raising an exception.
The code checks to see whether a vertex is equal to end after removing it from the queue. But it would be better to do this check before adding a vertex to the queue — that way you wouldn't have to wait for the vertex to move all the way up the queue before you spot that the search is done.

This optimization works for this problem because all the edges have the same length and so breadth-first search adds vertices to the queue in order by their distance from the start. This means that as soon as you've found a path to end you know that more searching cannot find a shorter path.
The value distance[u] + 1 is computed again for every child. It would be better to compute it once and remember it.

2. Revised code

from collections import deque

class NotFound(Exception):
    """Exception raised when no path is found."""

def bfs(graph, start, end):
    """Return the shortest distance from start to end in graph, which is
    represented as a mapping from a vertex to a list of adjacent
    vertices. If there is no path from start to end, raise NotFound.
    """
    # Mapping from v to shortest distance from start to v.
    distance = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        d = distance[u] + 1
        for neighbour in graph[u]:
            if neighbour not in distance:
                if neighbour == end:
                    return d
                distance[neighbour] = d
                queue.append(neighbour)
    else:
        raise NotFound()


Display Object as a node tree in HTML with clickable trace back to root node

It's always hard to guess, what the interviewer actually wanted. However, here are some thoughts mostly on style and markup.

Arrow function

You're using an arrow function in global scope, where it doesn't add value by binding this:

tree = (lvl, parent = 0, node, data) => {}

I would stick with a normal function here. It is also more readable. There's a discussion on SO – When should I use Arrow functions in ECMAScript 6? – which also explain why and where arrow functions are beneficial.

Readability

Here are some parts, that are hard to read:

arrNodeParent[node] = parent==0?0:parent-1;
n = node+=1;
(data.children.length)&&data.children.forEach(e=>tree(lvl+1, node, n, e));

Especially the last line. While it makes use of JavaScript's way to handle logical expressions, I would say: This is not Code Golf but production code. So readability and quick understanding of the code, even tomorrow, is more important then saving a few bytes by creating one-liners.

Inconsistent use of keywords

Sometimes you declare variables using let, often you don't. Sometimes const could be used instead. Also, think twice before using var and check whether globals are really necessary for your function.

Indentation

Your Indentation is inconsistent. Sometimes it's two, sometimes it's four characters. Some lines are totally off, like here:

    complete = false;
        currNode = $(this);
  while(!complete){

HTML

Semantics/nesting

  It should reflect parent-child relationship by appropriate element nesting and indentation.

A div and also span are the elements with no semantic meaning, which make them not the first choice for a relationship like that. You also don't nest the elements to reflect that, you simply list them:

Earth

Australia

Sydney

Adding a class like level-n does not add semantics to HTML.

You can change the markup to a nested list for example:

        Earth

                Australia

Sydney

Invalid markup

You add two attributes node and parent to each element. These aren't valid HTML attributes. If you want to use your own custom ones, use data-*-attributes, like:

Earth

jQuery

Yes, the task says, you can use any open source library you need. But it also says they like simplicity. So adding 87 kB of JavaScript to simply attach an event handler and to select/create a few HTML elements seems like a huge overhead to me. If the library doesn't help building the actual tree, I would stick to vanilla JavaScript in this case.


Several things to mention:

1. Use a for loop.

Semantically speaking, a for loop is way more suited in your case than a while loop. for usually means "repeat this for a specified number of steps" while while means "repeat this as long as a given condition is true". Given, you can ALWAYS replace a for with a while from a technical point of view and exactly this is the reason why you need to decide which one to use based on semantics

2. No need to use explicit array initialization.

When you assign the result of explode to your array object the interpretor will take care of the object type. There is no reason in this case to make it explicit so it is better to delete that line.

3. Naming

Not sure if this is part of the exercise or not, but consider using proper names for your objects. What do you explode? What does the array contains? Is a list of houses? Are those candies? Users? deliveryoutcode does not have too much meaning.

If you really don't have any real objects to work on, invent some and use those. It creates good habits for your programming journey.


First off streams and specifically the stream operators >> and << are designed for robustness not speed. They make the code harder to write incorrectly (and provide some local specific conversions) that make expensive in terms of using (consider changing to C fscanf() if speed is paramount).

So if speed is you objective streams is not the best choice.

Assuming we are staying with streams (Ask another question about how to write this in C for speed):

Dead Code

Second delete dead code (it confuses a review) and costs in creation.

    std::string new_line;

Small Inefficiencies

There is no need to create the cell object each time through the loop create it once outside the loop. (Personally I would leave it in the loop, but if you are going for speed then this is an obvious simple save).

When scanning the date you are making a copy of the value:

    std::string my_date = my_str_vec[0];

No need just make a reference (you  can even use a const reference for safety):

    std::string const&   my_date = my_str_vec[0];
          //    ^^^^^^

Use Reserve

Building the string character by character may not be the most efficient way of getting the date (as the string processed_date may be resized on each insert).

    for(my_iter = my_date.begin(); my_iter != my_date.end(); ++my_iter) {
        if(std::isalnum(*my_iter) || *my_iter == ' ')
            processed_date.append(1,(*my_iter));
    }

Use reserve so you know that it is not re-sized internally, then use a standard algorithm for optimal looping:

processed_date.reserve(my_date.size());  // Note: not resize()
std::remove_copy(my_date.begin(), my_date.end(),
                 std::back_inserter(processed_date),
                 [](char const& my_char) {return !(std::isalnum(*my_char) || *my_char == ' ');}
                );
// Note if you don't have C++0x then lamda is easily replaced by a functor.

Standard algorithms.

Your code will be optimal when you use the standard algorithms. Its worth learning what is available.

http://www.sgi.com/tech/stl/table_of_contents.html
See section 5

I showed you how to copy all but the characters you want. But there is one to remove all elements in-place. I'll let you experiment.


I'd use a decision table here:

GameState[,] decisionTable = new GameState[2,2];
decisionTable[0,0] = GameState.Ok;
decisionTable[0,1] = GameState.Stalemate;
decisionTable[1,0] = GameState.Check;
decisionTable[1,1] = GameState.Mate;
return decisionTable[Convert.ToInt32(isCheck), Convert.ToInt32(isStuck)];

From Code Complete 2nd Edition, Chapter 19: General Control Issues, page 431:

  Use decision tables to replace complicated conditions

  Sometimes you have a complicated test involving several variables. It can be helpful to use a decision table to perform the test rather than using ifs or cases. A decision-table lookup is easier to code initially, having only a couple of lines of code and no tricky control structures. This minimization of complexity minimizes the opportunity for mistakes. If your data changes, you can change a decision table without changing the code; you only need to update the contents of the data structure.


Bash script to download sequentially numbered images

I would write it this way:

#!/bin/bash

url_template="http://150.216.68.252:8080/adore-djatoka/resolver?url_ver=Z39.88-2004&svc_id=info:lanl-repo/svc/getRegion&svc_val_fmt=info:ofi/fmt:kev:mtx:jpeg2000&svc.format=image/jpeg&svc.level=6&rft_id=http://150.216.68.252/ncgre000/00000012/00011462/00011462_ac_%04d.jp2"

for i in {1..584}; do
    wget -O $(printf '%03d.jpeg' $i) "$(printf "$url_template" $i)"
done

Specifically,

At first glance, I thought that $urlFirst and $urlSecond were two URLs, until I figured out what was happening.
If there is another leading 0, then %04d is more appropriate than %03d.
The web server isn't going to care about the order of the parameters in the query string.  For the benefit of humans, though, it would be nicer to put the parameter that changes either first or last.
Fewer variables is nice.  I do everything by interpolation.  You can get a feel for what the wget command does, without tracing which variable came from where.


Programming challenge “Greatest Odd Divisor”

You should not be using doubles to perform integer arithmetic. Stick to int or long.

This is a brute-force search that follows the instructions very literally.  That is the wrong approach. Similar to Project Euler Problem 3, the fast way to find the largest factor is by finding the smallest factors. Just divide by 2 as many times as possible.

Example:

$$360 = 2^3 \cdot 45$$

The largest odd divisor is therefore 45.


Execute edit in a stored procedure based on database value

Create PROCEDURE [dbo].[spChanger]

AS
BEGIN

Execute ('UPDATE [TblActions] SET Complete = 2 WHERE DateToComplete < Date.Now.AddDays(14) AND Complete = 3' )

END

Your casing is inconsistent. If you prefer UPPERCASE keywords, stick to uppercase :)

CREATE PROCEDURE [dbo].[spChanger]

AS
BEGIN

EXECUTE ('UPDATE [TblActions] SET Complete = 2 WHERE DateToComplete < Date.Now.AddDays(14) AND Complete = 3' )

END

The name of the procedure is potentially problematic. "Changer" says nothing about what's changing, and as your database grows you'll certainly end up wondering why you didn't call it something along the lines of spUpdateTblActionsCompleteStatusCode.

Why are you executing a string? Why not just do this?

CREATE PROCEDURE [dbo].[spChanger]

AS
BEGIN

    UPDATE TblActions
      SET Complete = 2
    WHERE DateToComplete < Date.Now.AddDays(14)
      AND Complete = 3

END

Now you get IntelliSense in SSMS (assuming SQL Server) and it's much harder to make a typo on a column name.

I don't think this CREATE PROCEDURE script can run though. Date.Now.AddDays(14) isn't valid T-SQL.

That said I think you're missing opportunity for some parameters. I'd do it like this:

CREATE PROCEDURE [dbo].[spUpdateTblActionsCompleteStatusCode]
    @completeStatusValue INT = 2,
    @daysDiff INT = 14,
    @completeStatusFilter INT = 3
AS
BEGIN

    UPDATE TblActions
      SET Complete = @completeStatusValue
    WHERE DATEDIFF(d, DateToComplete, DATEADD(d, @daysDiff, GETDATE())) < @daysDiff
      AND Complete = @completeStatusFilter

END

When your code runs this stored procedure, if no parameters are passed it will just use the default values, and you have the flexibility to pass different parameters if/when you need to.

Also I'd recommend scripting your T-SQL as a DROP+CREATE, so the full script would look like this:

USE [DB]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[spUpdateTblActionsCompleteStatusCode]') AND type IN (N'P', N'PC'))
DROP PROCEDURE [dbo].[spUpdateTblActionsCompleteStatusCode]
GO

CREATE PROCEDURE [dbo].[spUpdateTblActionsCompleteStatusCode]
    @completeStatusValue INT = 2,
    @daysDiff INT = 14,
    @completeStatusFilter INT = 3
AS
BEGIN

    UPDATE TblActions
      SET Complete = @completeStatusValue
    WHERE DATEDIFF(d, DateToComplete, DATEADD(d, @daysDiff, GETDATE())) < @daysDiff
      AND Complete = @completeStatusFilter

END


RECURSIVE SOLUTION:
NOTE: it assumes that the input strings is already sorted. You could sort this at every call of the function, but this seems like unnecessary overhead.

def recursiveMerge(strings=[], current_line='', line_length=40, result=[]):
    """ Gather groups of strings into a line length of approx. 40 """

    # base case
    if not strings:
        result.append(current_line)
        return result

    else:
        next_line = strings.pop(0)

        # if current_line + next_line < line_length, add them
        # otherwise append current_line to result
        if len(current_line + next_line) < line_length:
            current_line = '    '.join([current_line, next_line]).lstrip(' ')
        else:
            result.append(current_line)
            current_line = next_line

        # recursively call function
        return recursiveMerge(strings, current_line = current_line, result=result)

ITERATIVE SOLUTION:

def myMerge(strings, line_length=40, res=[]):
    """ Gather groups of strings into a line length of approx. 40 """

    # sort the list of string by len
    strings = sorted(strings, key=len, reverse=True)

    # loop through the group of strings, until all have been used
    current_line = strings.pop(0)
    while strings:
        next_line = strings.pop(0)

        # if current_line + next_line shorter than line_length, add them
        # otherwise, append current_line to the result

        if len(current_line + next_line) < line_length:
            current_line = '    '.join([current_line, next_line])
        else:
            res.append(current_line)
            current_line = next_line

    # add any remaining lines to result
    res.append(current_line)

    return res


Delete companies with the least number of flights

If you can with MySQL 8.0, use the WITH Common Table Expression to simplify this query.
https://dev.mysql.com/doc/refman/8.0/en/with.html
The idea is to extract out the nested queries into ones in the WITH statement before the main query and then use them just like tables in the main query.


Prefer to use move rather than copy semantics

If your object is an int then it makes no difference. But some objects are more expensive to copy (such as std::string). If you can move rather than copy you will get much better performance with more complex objects.

*out = *first1++;

// Just add a call to std::move
*out = std::move(*first1++);

Too many lines of parameters

This is bit difficult to say this is required or perfect and you can make arguments both ways. But one parameter per line seems a bit over verbose. I prefer to group my parameters into logical groups (tools don't like this as they can't apply logical as it is situation specific).

But I personally think that for readability it makes sense to put parameters in logical groups.

(see below)

Member types names

Technically this is illegal:

typedef std::iterator_traits<BidirIt>::difference_type dt;

The compiler can not tell if difference_type is a type or a member variable until it knows the type of BidirIt. So you need to tell it that it is a typename.

typedef typename std::iterator_traits<BidirIt>::difference_type dt;
 //     ^^^^^^^^  required for standards conformance

Type names

Types are important in C++. Try and use names that help identify the type (be a bit verbose). But also it is a sort of convention that user defined types have an initial upper case letter (so that they can be easily spotted from objects).

typedef std::iterator_traits<BidirIt>::difference_type dt;

// Here I did not like the short name:
typedef typename std::iterator_traits<BidirIt>::difference_type DiffType;

Don't pass comparator to merge by value

The merge operation is not supposed to be done in isolation. It is always called from the sort_merge() function. So there is no need to create a comparator for each call to merge() just create it once in sort_merge() and pass by const reference to all calls to merge():

void merge(InputIt1 first1, InputIt1 last1,
           InputIt2 first2, InputIt2 last2,
           OutputIt out,
           Comparator const& cmp)

Non optimal implementation

while (first1 != last1 || first2 != last2)
{
    if (first2 == last2 || first1 != last1 && cmp(*first1, *first2))
    {
        *out = *first1++;
    }
    else
    {
        *out = *first2++;
    }
    ++out;
}

Better to write as this:

// Test your constraints here.
while (first1 != last1 && first2 != last2)
{
    // The comparison test then becomes much simpler.
    *out = std::move(cmp(*first1, *first2)
                         ? *first1++
                         : *first2++);
    ++out;
}
// Then the final optimized copy
// Only one of these loops will execute.
std::move(first1, last1, out);
std::move(first2, last2, out);

Space optimization

Creating the copy in sort_merge()

    std::vector<vt> left(first, middle);
    std::vector<vt> right(middle, last);

Means that you use more memory because you have a copy in this iteration then make a copy in each recursive call below this one and they are all active at the same time.

If you do the recursive sort_merge() in place. Then in the merge() call perform the copy then you get a much better space usage (as you only have one copy at the current iteration active).

Result

You will notice I have slightly altered the merge. We can make several assumptions about the inputs (because it is only called from sort_merge()):

There is only one type of input iterator.

Because we know we are sorting two halves of the same container.

There is no output iterator

as the merge is done in place.

The comparator does not need a default type.

this is done as part of the sort_merge template.

I don't pass two ranges.

I use begin/mid/end

Code: merge

template<typename I, typename Comparator>
void merge(I first, I mid, I last, Comparator const& cmp)
{
    typedef typename std::iterator_traits<I>::difference_type DiffType;
    typedef typename std::iterator_traits<I>::value_type      ValueType;

    DiffType                size1 = std::distance(first, mid);
    DiffType                size2 = std::distance(mid, last);

    std::vector<ValueType>  hold1;
    std::vector<ValueType>  hold2;
    hold1.reserve(size1);
    hold2.reserve(size2);

    std::move(first, mid,  std::back_inserter(hold1));
    std::move(mid,   last, std::back_inserter(hold2));

    auto first1 = std::begin(hold1);
    auto last1  = std::end(hold1);
    auto first2 = std::begin(hold2);
    auto last2  = std::end(hold2);
    auto out    = first;

    while (first1 != last1 && first2 != last2)
    {
        *out = std::move(cmp(*first1, *first2)
                             ? *first1++
                             : *first2++);
        ++out;
    }
    std::move(first1, last1, out);
    std::move(first2, last2, out);
}

Code: sort_merge

template<typename I,
         typename Comparator = std::less<typename std::iterator_traits<I>::value_type>>
void sort_merge(I first,
                I last,
                Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type DiffType;

    DiffType size = std::distance(first, last);
    if (size > DiffType(1))
    {
        auto middle = first + size / 2;
        auto midIter = begin;
        std::advance(midIter, middle);

        sort_merge(first, midIter, cmp);
        sort_merge(midIter, last,  cmp);

        merge(first, midIter, end, cmp);
    }
}


Python 2.7 Tower of Hanoi game with ASCII graphics

Hi thanks for sharing your code,

You should stick to Python naming conventions, check out the PEP8 style guide.

https://www.python.org/dev/peps/pep-0008/

Based off of this, your rod class should be class Rod: and movepiece should be move_piece

For your global variables, you could fix this by having a Game or Hanoi class.

class Hanoi:

    def __init__(self, rod1, rod2, rod3):
        self.rod1 = rod1
        self.rod2 = rod2
        self.rod3 = rod3
        ...

Watch out for using eval. There are lots of reasons not to use eval, but the one I want to talk about is that here you're relying on the user to know variable names. Variable names should never matter. But here if you were to change a variable name, your program would not function as intended.

If the goal is to call a method on a Rod object based on user input, just do a standard if/elif block

if source == 1:
    piece = self.rod1.top()
elif some_condition:
    ...

If you're using eval to call methods like this, just call the methods instead.

list(range(1,level+1)) if you look at the documentation for the range function, it already returns a list, you can just use range(1,level+1)

There seem to be some unnecessary offsets throughout your code, why use range(1, level + 1) and not just range(level) you can just take the user input value and subtract 1 from it in one place, in Python counting starts from 0 :)

def __init__(self,n): n is a very poor name for a variable, use something like num or number instead, anything to improve readability goes a long way.

in your movepiece() function, you call movepiece again inside, I don't think there's any real benefit to using recursion here, I think it would be simpler to understand a simple loop instead, and it would also be simpler to reason about and leave less room for error.

while !game_over:
    # game loop

This way you don't need to worry about maximum recursion depth exceeded either, not that that would really be a problem here anyway.

This while loop rod2.state!=list(range(1,level+1)) and rod3.state!=list(range(1,level+1) could be a lot simpler.

Try breaking it down into multiple well named boolean values instead.

meaningful_name_for_this = rod2.state!=list(range(1,level+1))
meaningful_name_for_that = rod3.state!=list(range(1,level+1)
while meaningful_name_for_this and meaningful_name_for_that:
    # do your loop code

Make your code as self documenting as possible.

destination=int(move.split(" ")[1])

Avoid magic numbers where possible, whenever you need specific values like this, make them a well named constant instead.

destination=int(move.split(" ")[DESTINATION_INDEX])

especially if you reuse them throughout your code base.

Hopefully some of this was useful to you!

Edit:

Here's an example of what your move_piece method could look like
Here it's a method of some Hanoi or Game object.

def move_piece(self):
    move = INVALID_VALUE  # some constant
    while not self._is_move_valid(move):  # method that checks if a move is okay or not
        move = self._prompt_for_move() # reads user input

    # if we're here, we know that the move is definitely valid
    self._perform_movement(move)  # does the work on the Rod objects

I've made up some methods here, in your code you have the logic to do these actions, so I'll let you fill in those!

Notice now how short this method is, the shorter the method the better, even though it's made up of many calls to other methods, by giving them all good clear names, you should be able to see what the method is doing without looking at the bodies of these other methods.


Coin tossing simulation to get x heads in a row, ten times - timely at higher amount of heads

Fails if they don't enter an integer
You are doing integer math on the average
I would prefer ++; over += 1;
I would rather see a foreach
Odd but rnd.Next(2) is faster
Need to get into the millions for a decent sample

public static void CoinToss()
{
    int sample = 1000000;
    Debug.WriteLine($"Enter a head streak to achieve. This will be executed {sample.ToString("N0")} times to generate an average.");
    int desiredStreak = 10;
    int grandTotalAttempts = 0;
    int currentStreak;
    int totalAttempts;
    Random rnd = new Random();
    for (int i = 0; i < sample; i++)
    {
        currentStreak = 0;
        totalAttempts = 0;
        while (currentStreak != desiredStreak)
        {
            if (rnd.Next(2) == 0)
            {
                currentStreak ++;
            }
            else
            {
                currentStreak = 0;
            }
            totalAttempts ++;
        }
        if ((i + 1) % (sample / 20) == 0)
        {
            Debug.WriteLine($"Attempt Number: {(i + 1).ToString("N0")}");
            Debug.WriteLine($"Total Attempts: {totalAttempts.ToString("N0")}");
            Debug.WriteLine("");
        }
        grandTotalAttempts += totalAttempts;
    }
    Debug.WriteLine($"Average Attempts: {((decimal)grandTotalAttempts / sample).ToString("N2")}");
}