C++ Dijkstra's shortest path implementation I have created a c++ function that searches for the shortest path between two points with dijkstra's shortest path algorithmus. I'm using it right now in combination with a program that solves mazes and it works quite well on up to 15K * 15K mazes (I ran short of RAM there). But I have problems solving an 2K * 2k Braid maze (one with lots of paths and loops). Tell me what I can improve.

The function itself:

    bool dijkstra::GetShortestPath(std::deque<CNode> &vGraph, CNode *mStart, CNode *mEnd, std::deque<CNode*> *vPath)
{
    if(mStart == 0 || mEnd == 0 || vPath == 0)
        return false;

    std::vector<CNode*> vUnvisited;     //Priority Queue
    auto mCompare = [&](CNode *lhs, CNode *rhs){return (lhs->DistanceTo > rhs->DistanceTo);};

    //Set distance to start node to 0
    mStart->DistanceTo = 0;

    //Init Queue
    vUnvisited.reserve(vGraph.size());
    vUnvisited.push_back(mStart);   //At the beginning the queue is empty, besides the startnode
    //Dijkstra loop
    {CNode *mTopNode = 0;
    do{
        std::pop_heap(vUnvisited.begin(), vUnvisited.end(), mCompare);
        mTopNode = vUnvisited.back();               //Get nearest, not completed node
        vUnvisited.pop_back();                      //Remove it, it will be completed next iteration
        for(auto &it : mTopNode->Connections())     //Look at all connections
        {
            if(it.To->DistanceTo > (mTopNode->DistanceTo + it.Distance))        //If a shorter path to a node is found, overwrite DistanceTo & PreviousNode
            {
                it.To->DistanceTo = (mTopNode->DistanceTo + it.Distance);
                it.To->PreviousNode = mTopNode;
                std::make_heap(vUnvisited.begin(), vUnvisited.end(), mCompare); //Completely sort the queue
            }
            if(it.To->Completed == false)       //If an unvisited node has been found, add it to the queue and sort it in
            {
                vUnvisited.push_back(it.To->Addr());
                std::push_heap(vUnvisited.begin(), vUnvisited.end(), mCompare);
            }
            mTopNode->Completed = true; //The current node is now completed
        }
    }while(!(mEnd->Completed == true || vUnvisited.size() == 0 || mTopNode->DistanceTo == std::numeric_limits<unsigned int>::max()));}

    //Push path into array
    {CNode *mCurrentNode;
    mCurrentNode = mEnd;
    while(mCurrentNode != 0)
    {
        vPath->push_front(mCurrentNode);
        mCurrentNode = mCurrentNode->PreviousNode;  //Follow the PreviousNode pointers
    }}
    return true;
}

The CNode class:

struct SConnection
{
    SConnection(CNode *To, unsigned int Distance);
    CNode *To;
    unsigned int Distance;
};

class CNode
{
public:
    CNode();

    std::vector<SConnection> Connections()const;

    bool AddConnection(CNode *mTo, unsigned int nDistance);
    bool AddConnection(const SConnection &mConnection);
    bool RemoveConnection(CNode *mTo);

    bool operator >  (const CNode &rhs)const;
    bool operator <  (const CNode &rhs)const;
    bool operator == (const CNode &rhs)const;

    CNode* Addr();

    bool Completed = false;
    unsigned int DistanceTo = std::numeric_limits<unsigned int>::max();
    CNode *PreviousNode = 0;
    unsigned int XPos = 0;
    unsigned int YPos = 0;

private:
    std::vector<SConnection> m_vConnections;
};

OK this does not implement dijkstra exactly (its close).

Dijkstra looks more like this:

PriorityQueue<{Node,cost}>   frontierList;
List<Node>                   alreadyVisited;

frontierList.push({start,0});

while(!frontierList.empty())
{
    node, cost = frontierList.pop();
    if (node == end) {
        return cost;
    }
    if (alreadyVisited.find(node) != alreadyVisited.end()) {
        continue;
    }
    alreadyVisited.push(node);
    for(connect: node.connections) {
        if (alreadyVisited.find(connect.node) == alreadyVisited.end()) {
            frontierList.push({connect.node, cost + connect.cost});;
        }
    }
}
return -1; // No  path found.

Notice we keep the cost in the priority list (not in the node). Otherwise you may have nodes in the list with a higher cost that need to be expunged.

You get more efficiency by using an already visited list because you don't have to expand all its connections (if you already found it then you already have the shortest path to that node).

Note: You can't put the test for alreadyUsed inside the connections loop because by the time you get to them the priority loop may have found a better way to the node.

For more details see:

https://stackoverflow.com/a/3448361/14065
https://stackoverflow.com/a/3765889/14065
https://codereview.stackexchange.com/a/126688/507
A generic implementation of Dijkstra
https://codereview.stackexchange.com/a/103896/507
https://codereview.stackexchange.com/a/69024/507
https://codereview.stackexchange.com/a/77256/507

Code Review

Passing by pointer should be avoided.

bool dijkstra::GetShortestPath(std::deque<CNode> &vGraph, CNode *mStart, CNode *mEnd, std::deque<CNode*> *vPath)
{
    if(mStart == 0 || mEnd == 0 || vPath == 0)
        return false;

If you pass these value by reference then you don't need to make this check.

This is doggy:

    //Set distance to start node to 0
    mStart->DistanceTo = 0;

It assumes that in all your nodes. You have set Completed and DistanceTo and PreviousNode to their default values. That means the algorithm is intrusive into the graph. This means the algorithm only works with this specific type of graph and can not be applied to a generic graph type.

It also assume that you go through a manual reset of the graph before you can call this function.

Don't particularly like your do {} while(); loop I think this falls more into the while() {} category.

OK this is gets a bit hard. I was sure this was broken. But as it turns out that it works fine (just inefficient).

            if(it.To->DistanceTo > (mTopNode->DistanceTo + it.Distance))        //If a shorter path to a node is found, overwrite DistanceTo & PreviousNode
            {
                it.To->DistanceTo = (mTopNode->DistanceTo + it.Distance);
                it.To->PreviousNode = mTopNode;
                std::make_heap(vUnvisited.begin(), vUnvisited.end(), mCompare); //Completely sort the queue
            }

Every time you encounter a path to a destination node you update the destination node with the shortest distance. But this also means you have to re-sort your whole priority queue each time you change the distance.

This is not very efficient. This is why the destination node and distance are supposed to be stored together in the priority queue (sorted by distance). Then you will always find the shortest distance to a node first. Then duplicates will be quickly removed by the Already Found List.

Checking the ->Completed flag here is an optimization that I don't have in my example (that can be added). But putting it here is not enough. You also need to check the ->completed flag before you start processing the current node mTopNode Otherwise each copy on the frontier list will push all its children on the frontier list thus growing it exponentially.

            if(it.To->Completed == false)       //If an unvisited node has been found, add it to the queue and sort it in
            {
                vUnvisited.push_back(it.To->Addr());
                std::push_heap(vUnvisited.begin(), vUnvisited.end(), mCompare);
            }

This line does not need to be in the loop.

            mTopNode->Completed = true;


Harmonic partial sum calculator with multithreading I wrote a program which computes the harmonic partial sum to N terms with multithreading capability. I've been working on this to sharpen my C++ skills for the upcoming semester. Just wondering if there's anything that doesn't follow the C++ standard and/or glaringly wrong. Also wondering if I can make any further optimizations.

Basically I have my program set up to only use threads if the input is divisible by 4, since I am using 4 threads due to my quad core CPU. I want this to be more flexible but I haven't thought of a better solution yet. If anyone has a suggestions, that'd be appreciated.

#include <iostream>
#include <cstdio>
#include <thread>
#include <ctime>
#include <cassert>

using namespace std;

const int NUM_THREADS = 4;

// H(N) is defined to be the harmonic partial sum to N terms.
// calculateHarmonic(): function given to threads to compute H(N).
// unsigned long start: starting point for the loop; different for each thread.
// unsigned long N: amount of terms to compute; different for each thread; divided evenly by # of threads.
// double *sum: pointer to a double which holds a thread's individual sum for H(N).
void calculateHarmonic(long long start, long long N, double *sum)
{
    for(; start <= N; start++)
    {
        *sum += 1.0/start;
    }
}

void executeWithThreads(long long N)
{
    thread t[NUM_THREADS];  // using four threads
    double sum[NUM_THREADS] = {0.0};    // array of each sum calculated by each thread
    double finalSum = 0.0;
    clock_t start = clock();

    // Assign threads their task.
    for(int i = 0; i < NUM_THREADS; i++)
    {
        // thread([name of function], [starting point], [N], [address of individual element in sum array])
        t[i] = thread(calculateHarmonic, (((N/4)*i)+1), ((N/4)*(i+1)), &(sum[i]));
    }

    // Join threads to terminate and sum up all individual sums into finalSum.
    for(int i = 0; i < NUM_THREADS; i++)
    {
        t[i].join();
        finalSum += sum[i];
    }

    clock_t end = clock();
    printf("Harmonic sum of %lld is %1.18lf\n", N, finalSum);
    printf("Calculation took %1.18lf seconds.\n", (((double)(end-start)/CLOCKS_PER_SEC))/NUM_THREADS);
}

void executeNoThreads(long long N)
{
    double sum = 0.0;
    clock_t start = clock();
    for(int i = 1; i <= N; i++)
    {
        sum += 1.0/i;
    }
    clock_t end = clock();
    printf("Harmonic sum of %lld is %1.18lf\n", N, sum);
    printf("Calculation took %1.18lf seconds.\n", (((double)(end-start)/CLOCKS_PER_SEC))/NUM_THREADS);
}

int main()
{
    long long N;

    cout << "Enter the amount of terms to calculate the Harmonic sum to: ";
    cin >> N;
    assert(N > 0 && "N must be a nonzero positive integer.");
    cout << endl;

    if(N > NUM_THREADS && N % 4 == 0)
    {
        cout << "Calculating with threads..." << endl;
        executeWithThreads(N);
    }
    else if(N > NUM_THREADS && N % 4 != 0)
    {
        cout << "Calculating without threads..." << endl;
        executeNoThreads(N);
    }
    else
    {
        cout << "Calculating without threads due to small N..." << endl;
        executeNoThreads(N);
    }

    return 0;
}

Compiled with:

g++ -std=c++11 -pthread -Ofast harm_sum.cpp -o harm.out ; ./harm.out

Try not to use using namespace std in global scope.  If you must use it, keep it in local scope, such as in a function.  More info about that here.
I don't need any need to use printf() over std::cout here.  You are also using C-style casting and no std:: for clock_t, so some of this code still looks C-like.

If you're using printf() because you're having trouble with formatting, then take a look at the <iomanip> library for something useful.
Unless you're debugging, assert may be unnecessary.  You can easily output an error message to std::cerr and return EXIT_FAILURE from main().
The value 4 used in main() appears to be a magic number and should be a constant.
Each use of std::endl flushes the buffer and takes extra time. Luckily, you're not using it in the timed section.  It's still not needed in most cases and you can also output a newline with "\n", which doesn't do a flush as well.  More info about that here.


Validating a string under few conditions Following code validates NIC number of a person (National Identity Card, no like SSN)
Requirements are...

Length should be 10 digits or characters
All should be digits except the last one
Last one would be x or v in simple letters

Currently I'm using following method and its working. I just want to know that could this be make better or simplified?

    private bool ValidateNIC(string nic)
    {
        if (!string.IsNullOrEmpty(nic))
        {
            char[] letter = nic.ToCharArray();
            if (letter.Length == 10)
            {
                if (letter[9] == 'v' | letter[9] == 'x')
                {
                    for (int i = 0; i <= (letter.Length - 2); i++)
                    {
                        if (char.IsNumber(letter[i]) == false)
                        {
                            MessageBox.Show(string.Format("letter {0 } is not allowed, all Should be numbers except the last one.", letter[i]));
                            return false;
                        }
                    }
                    return true;
                }
                else
                {
                    MessageBox.Show("Last letter should be x or v in simple letters");
                    return false;
                }
            }
            else
            {
                MessageBox.Show("Length should be 10 ");
                return false;
            }
        }
        else
        {
            MessageBox.Show("NIC is null");
            return false;
        }
    }

As I think George Howarth was suggesting in his answer you can reduce nesting and avoid the Arrow code effect by returning early from the
method.  This helps with code flow as well as readability.
As already mentioned if you can remove constant literals from your code that is good. One way to do this is to move these to
private static or const variables or even supply them to the method.

private const int RequiredLength = 10;
private readonly char[] _acceptedLastCharacters = { 'x','v' };

I like to try and remove dependecies from the view especially in business logic which validation can often be.  So in this case
I would consider returning a result class and let your caller determine how to handle it.  This would also mean creating unit tests
would be so much easier which I think in this case would be ideal.

internal class ValidationResult
{
  public bool IsValid { get { return string.IsNullOrEmpty(ErrorMessage); } }
  public string ErrorMessage { get; private set; }

  private ValidationResult(string errorMessage)
  {
      ErrorMessage = errorMessage;
  }

  public static ValidationResult Success()
  {
      return new ValidationResult(string.Empty);
  }

  public static ValidationResult Failure(string errorMessage)
  {
      return new ValidationResult(errorMessage);
  }

}
A great thing about writing unit tests is that it can sometimes ensure you think about your requirements before you even code and so
help cover everything.  In this case I was writing some unit tests for the method and it occured to me that the code might not cover the case
of empty strings.  I created the test and hello, it had worked.  That was great.  Now I also have a test!  And not only that, doing a couple
of other tests showed some flaws in my code which meant I identified problems with tests.  Awesome!

Here is an example of the entire re-factored code:

internal class ValidationResult
{
    public bool IsValid { get { return string.IsNullOrEmpty(ErrorMessage); } }
    public string ErrorMessage { get; private set; }

    private ValidationResult(string errorMessage)
    {
        ErrorMessage = errorMessage;
    }

    public static ValidationResult Success()
    {
        return new ValidationResult(string.Empty);
    }

    public static ValidationResult Failure(string errorMessage)
    {
        return new ValidationResult(errorMessage);
    }
}

class NicValidator
{
    private const int RequiredLength = 10;
    private readonly char[] _acceptedLastCharacters = { 'x','v' };

    public ValidationResult ValidateNic(string nic)
    {
        var trimmedNic = nic.Trim();

        if (trimmedNic.Length != RequiredLength)
        {
            return Failed("NIC cannot be empty and is not of required length " + RequiredLength);
        }

        if (!_acceptedLastCharacters.Contains(trimmedNic.Last()))
        {
            return Failed(string.Format("Last letter is not supported and should be one of [{0}]", string.Join(",", _acceptedLastCharacters)));
        }

        // Ignore last character as that is handled in earlier check
        var illegalCharacters = trimmedNic
            .Take(trimmedNic.Length - 1)
            .Where(p => !char.IsNumber(p))
            .ToList();

        if (illegalCharacters.Any())
        {
            string errorMessage = string.Format("letters {0} are not allowed, all Should be numbers except the last one.",
                string.Join(",", illegalCharacters));

            return Failed(errorMessage);
        }

        return ValidationResult.Success();
    }

    private ValidationResult Failed(string errorMessage)
    {
        return ValidationResult.Failure(errorMessage);
    }
}

With some unit tests (I didn't do all, just enough to test base functionality).  Note.  I started these tests before I
even started re-factoring the code so that I had them passing first.  Then during re-factoring I could confidently know
whether what I did was still returning the correct results.

[TestMethod]
public void StringIsOfRequiredLength()
{
    // arrange
    var validator = new NicValidator();
    const string nic = "123456789x";

    // assert
    var result = validator.ValidateNic(nic);

    // act
    Assert.IsTrue(result.IsValid, result.ErrorMessage);
}

[TestMethod]
public void StringIsNotOfRequiredLength()
{
    // arrange
    var validator = new NicValidator();
    const string nic = "12345678x";

    // assert
    var result = validator.ValidateNic(nic);

    // act
    Assert.IsFalse(result.IsValid, result.ErrorMessage);
}

[TestMethod]
public void NicIsNotAllSpaces()
{
    // arrange
    var validator = new NicValidator();
    const string nic = "          ";

    // assert
    var result = validator.ValidateNic(nic);

    // act
    Assert.IsFalse(result.IsValid, result.ErrorMessage);
}


Cracking the Coding Interview — 1.5 One Away I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one character from the longer string is equal to add one character to the shorter one.

Description

  One away : There are three types of edits that can be performed on
  strings: insert a character, remove a character and replace a
  character. Given two strings, write a function to check if they are
  one edit (or zero edits) away.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int helper_one_way(const char *str1, const char * str2,
                          size_t len1, size_t flag) {
    size_t nchars = 0;
    size_t i, j;

    for (i = 0, j = 0; i < len1; ++i, ++j) {
        if (str1[i] != str2[j]) {
            if (++nchars > 1) return 0;
            if (flag && i) --i;
        }
    }
    return 1;
}

/* check if str1 can be obtained from string2 adding, deleting, replacing
 * at last one char */
int one_way(const char *str1, const char *str2) {
    size_t len1 = strlen(str1), len2 = strlen(str2);
    size_t diff = abs(len1 - len2);

    if (diff > 1) return 0;
    if (!diff) return helper_one_way(str1, str2, len1, 0);
    if (len1 > len2) return helper_one_way(str2, str1, len2, 1);
    return helper_one_way(str1, str2, len1, 1);
}

int main(void) {
    printf("%d\n", one_way("pale", "ple"));
    printf("%d\n", one_way("pales", "pale"));
    printf("%d\n", one_way("pale", "bale"));
    printf("%d\n", one_way("pale", "bake"));
    return 0;
}

Generally nice code: easy to read, good use of const char* for the string arguments.

It's great that we have unit tests; we can improve them by making them self-checking:
/* return number of test failures (0 or 1) */
int test_one_away(const char *str1, const char *str2, int expected)
{
    const int actual = one_way(str1, str2);
    if (actual == expected)
        return 0;
    fprintf(stderr, "one_way \"%s\", \"%s\" expected %d but got %d\n",
            str1, str2, expected, actual);
    return 1;
}

int main(void)
{
    return
        + test_one_away("pale", "ple", 1)
        + test_one_away("pales", "pale", 1)
        + test_one_away("pale", "bale", 1)
        + test_one_away("pale", "bake", 0);
}

We should add some more tests.  When I start writing tests (usually before the production code) I usually write the very simplest tests first, probably passing NULL to exercise the error recovery.  I'm going to assume that the code won't be testing for null pointers, but would certainly start with the next simplest case: are two empty strings within one change:
        + test_one_away("" "", 1)

Then compare one- and two-character strings against the empty string, and for strings that differ by one or two deletions at the beginning, middle and end.  A good guideline for testing functions that return a boolean value is to identify the boundaries where the result should change between false and true (e.g. remove one character from the front ⇒ true; remove two characters from front ⇒ false) and write one test for each side of that transition.
Here's a test that exposes a bug in the code:
        + test_one_away("pale", "ale", 1)

This is because we don't accept deletion of the first character:

        if (flag && i) --i;

The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):
        if (flag) --i;

I'm not sure why flag needs to be a size_t;  a simple int should be sufficient.  If/when we have access to a C99 compiler (which should be soon; it's around 20 years old now), we could include <stdbool.h> and make it a bool.  It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).

The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:
/* check if str1 can be obtained from string2 adding, deleting, removing
 * at last one char */
bool one_way(const char *str1, const char *str2)
{

    size_t len1 = strlen(str1);
    size_t len2 = strlen(str2);

    switch (len2 - len1) {
    case (size_t)-1: return helper_one_way(str2, str1, len2, true);
    case 0:          return helper_one_way(str1, str2, len1, false);
    case 1:          return helper_one_way(str1, str2, len2, true);
    default:         return false;
    }
}

We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:
    for (i = 0, j = 0;  str1[i];  ++i, ++j) {

Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):
static bool helper_one_way(const char *a, const char *b,
                           bool allow_deletion)
{
    size_t nchars = 0;
    while (*a) {
        if (*a++ != *b++) {
            if (++nchars > 1) return false;
            if (allow_deletion) --b;
        }
    }
    return true;
}

Finally: the name - should one_way be spelt one_away?

Modified code
Applying the above suggestions, we get:
#include <stdbool.h>
#include <string.h>

static bool helper_one_away(const char *a, const char *b,
                           bool allow_deletion)
{
    size_t nchars = 0;
    while (*a) {
        if (*a++ != *b++) {
            if (++nchars > 1) return false;
            if (allow_deletion) --b;
        }
    }
    return true;
}

/* Return true if a can be obtained from string2 by adding,
   deleting, or removing at most one character */
bool one_away(const char *a, const char *b)
{
    switch (strlen(a) - strlen(b)) {
    case (size_t)-1: return helper_one_away(b, a, true);
    case 0:          return helper_one_away(a, b, false);
    case 1:          return helper_one_away(a, b, true);
    default:         return false;
    }
}

/* Test code */

#include <stdio.h>

/* return number of test failures (0 or 1) */
static int test_one_away(const char *a, const char *b,
                         bool expected)
{
    const int actual = one_away(a, b);
    if (actual == expected)
        return 0;
    fprintf(stderr, "one_away \"%s\", \"%s\" expected %d but got %d\n",
            a, b, expected, actual);
    return 1;
}

int main(void)
{
    return
        + test_one_away("", "", true)
        + test_one_away("", "a", true)
        + test_one_away("pale", "", false)
        + test_one_away("pale", "le", false)
        + test_one_away("pale", "ale", true)
        + test_one_away("pale", "pale", true)
        + test_one_away("pale", "pal", true)
        + test_one_away("pale", "pa", false)
        + test_one_away("pale", "ple", true)
        + test_one_away("ple", "pale", true)
        + test_one_away("pales", "pale", true)
        + test_one_away("pale", "bale", true)
        + test_one_away("pale", "bake", false);
}


To LINQ or not to LINQ As a fairly new C# programmer I am a unsure about when and how to best make use of LINQ (and also when to choose the expression method syntax vs. the query syntax). This question often comes up for me at work, because I heavily lean toward making full use of new language features and a functional style, while my colleagues seem to prefer a more conservative style. This means I have to think a lot about when using LINQ is actually worth it.

Now here is where the review part comes in. This is an anonymized piece of code that this question came up for, once coded in a LINQ style and once in imperative style. Which version do you believe is preferable from a readability / maintainability viewpoint?

void updateItems()
{
    Items.Clear();
    Items.AddRange(Widget.GetDetectedWidgets()
        .Intersect(GetRelevantWidgets())
        .Select(widget => readSerialNr(widget))
        .Where(serial => serial != null)
        .DefaultIfEmpty("No relevant widgets found.")
        .ToArray());
}

void updateItems()
{
    Items.Clear();
    List<string> relevantWidgets = GetRelevantWidgets().ToList();
    foreach(string widget in Widget.GetDetectedWidgets())
    {
        if(relevantWidgets.Contains(widget))
        {
            string serial = readSerialNr(widget);
            if(serial != null)
                Items.Add(serial);
        }
    }
    if(Items.Count == 0)
        Items.Add("No relevant widgets found.");
}

Some notes:

I think the LINQ version would be more readable if you extracted a variable for the collection. Something like:

var serials = /* the whole LINQ query here */

Items.Clear();
Items.AddRange(serials);

The LINQ version might be more efficient if there were lots of widgets, because Intersect() uses hashing to achieve O(n+m) time complexity, while your imperative code is O(n·m).
You don't need ToArray() in your LINQ version. (Assuming Items is List<string>.)
I really don't think the string "No relevant widgets found." should be the default value if the list is empty. List of widget serial numbers should contain widget serial numbers, nothing else. And you should separate your business logic and presentation.

With the mentioned changes, I think the LINQ version will be more readable, primarily because Intersect() explains what you want to do better.

Also don't forget that you don't have to use only LINQ or only imperative code, you can combine the two in a single method (e.g. improve the imperative approach by using Intersect()).


multiple threaded program vb.net i have this code that is suppose to work with at starting the minimum number of threads, say 5. when it starts the first five threads, it automatically replaces any thread that is finished  making sure that there is always five threads working.

the problem here is that, am finding it difficult to manage where am suppose perform locks

Private Sub StartProcess()
        intNextItemIndex = intMaxThreadCount
        ' start the first five threads
        For i = 0 To intMaxThreadCount
            If i < ListWorkItems.Count Then
                StartNextItem(i)
            End If
        Next
        ' update running threads
    End Sub

    Private Sub StartNextItem(ByVal index As Integer)
        Dim tt As New ThreadTask
        If index < ListWorkItems.Count Then

            ' start parsing thread
            Dim t As New Thread(AddressOf DoWork)
            With tt
                .Index = index
                .Task = "count"
                .Data = CStr(index * index)
            End With
            With t
                .IsBackground = True
                .Name = "Thread " & index
                .Start(tt)
            End With
            Thread.Sleep(100)
        End If
    End Sub

    Private Sub DoWork(ByVal data As Object)
        Dim tt As ThreadTask = CType(data, ThreadTask)
        Dim sTemp As String = Nothing
        Dim objLock As Object = New Object()
        Dim t As Double = 0
        myWatch = New Stopwatch
        Try
            Debug.Print("Incoming index: " & CInt(tt.Index))
            myWatch.Start()

                    SyncLock (objLock)
                        sTemp = PerformWork(ListWorkItems(CInt(tt.Index)).ToString)
                        'sTemp = CountTo()
                    End SyncLock

            myWatch.Stop()
            t = myWatch.ElapsedMilliseconds / 1000
            AddItem(tt.Index, t.ToString & " = " & sTemp)
            'AddItem(index, t.ToString)
        Catch ex As Exception
            ' catch error
            Debug.Print( ex.Message)
        End Try
 end sub

Public Sub AddItem(ByVal index As Integer, ByVal item As String)

    If Me.InvokeRequired Then
        Me.Invoke(New AddItemDelegate(AddressOf AddItem), index, item)
    Else
        Dim objLock As Object = New Object()
        Dim lvItem As New ListViewItem

        SyncLock (objLock)
            count += 1
            intNextItemIndex += 1
        End SyncLock

        With lvItem
            .Text = index.ToString
            .SubItems.Add(ListWorkItems(index).ToString)
            If item.Length < 100 Then
                .SubItems.Add(item.ToString)
            Else
                .SubItems.Add(item.Length.ToString)
            End If
        End With
        listView1.Items.Add(lvItem)

        If count = ListWorkItems.Count Then
            Button1.Enabled = True
            tsslStatus.Text = "Finished!!"
            Debug.Print("Finished: " & index.ToString)
        Else
            tsslStatus.Text = "Processing item (" & count + 1 & ")"
        End If

        StartNextItem(intNextItemIndex)
    End If

End Sub

can someone help me review it and tell me whats wrong with it?

Are the loks ok?

Is this way of doing it ok?

What possible improvements can i make

thanks all

Unfortunately, the whole approach is broken. You should make your parallel tasks explicit in the code so that you don’t need cross-thread communication any more. Secondly, you are writing your own thread scheduler here. – Don’t. Schedulers already exist, take advantage of that.

Have a look at the Task Parallel Library, in particular the Task and TaskScheduler classes.

Better yet, try to model your algorithm to benefit from data parallelism and eschew explicit threading completely in favour of the automatically parallelised computations.


Secure way of uploading php images and GIF I am creating a social network and I want to know if this is a secure way of uploading pics/gifs and videos.
if(isset($_POST['post'])) {

    $uploadOk = 1;
    $imageName = $_FILES['postToUpload']['name'];
    $errorMessage = "";
    $picdate = date('Y-m-d_H-i-s');

    if($imageName != "") {
        $targetDir = "assets/images/posts/";
        $imageName = $targetDir . uniqid() . basename($imageName);
        $imageFileType = pathinfo($imageName, PATHINFO_EXTENSION);

        if($_FILES['postToUpload']['size'] > 10971520) {
            $errorMessage = "Your file is to large";
            $uploadOk = 0;
        }

        if (strtolower($imageFileType) != "jpeg" && strtolower($imageFileType) != "png" &&
            strtolower($imageFileType) != "jpg" && strtolower($imageFileType) != "gif"
            && strtolower($imageFileType) != "mp4"&& strtolower($imageFileType) != "Ogg"
            && strtolower($imageFileType) != "WebM"){

            $errorMessage = "File type not allowed.";
            $uploadOk = 0;
        }

        if($uploadOk){
            if(move_uploaded_file($_FILES['postToUpload']['tmp_name'], $imageName)) {
                // image uploaded

            } else{
                // image did not upload
                $uploadOk = 0;
            }
        }
    }

    if($uploadOk) {

    $post = new Post($con, $userLoggedIn);

    $post->submitPost(trim(strip_tags(filter_var($_POST['post_text'], FILTER_SANITIZE_STRING))),
        'none', $imageName);

    } else {

        echo "<div class='alert alert-danger'>
                $errorMessage
            </div>";
    }
}

Your code is insecure because:

It only relies on the file extension, so attackers can upload any backdoors.
It accesses variable $_FILES['postToUpload']['name'] without checking if it is defined and this may lead to Full Path Disclosure.
It uses function uniqid() without any arguments, so uniqueness is not guaranteed and the files that are uploaded simultaneously and have the same file name will be overwritten.
It stores the filename provided by user without removing potentially dangerous characters and this may lead to unexpected results.

Some recommendations to improve your code:

Get rid of the $uploadOk variable. You already have and handle the $errorMessage variable and this is enough to check if the file was uploaded successfully.
You should define $imageFileType as lowercase, instead of calling strtolower() for each extension.
You should define all accepted file extensions as lowercase, otherwise users won't able to upload some files (in your case WebM and Ogg, because strtolower($imageFileType) != "Ogg" and strtolower($imageFileType) != "WebM" will always be FALSE).


JavaScript Image Preloading Script I wrote an infinite scrolling scrolling plugin for an app I'm developing. When requesting the second 'page' from the server, I loop through each image, and give it a very basic onload function.

// I will have the result in a variable called data
// Fetch each image from result
$images = $( data.content ).find('img');
// Cache length for use in for loop
imagesLength = $images.length;

for ( var i = 0; i < imagesLength; i++ ) {
    // Create new Image object
    img = new Image();
    // Match src of image in the result
    img.src = ( $images[i].src );
    // Add onload listener
    img.onload = function () {
        // Increment iterator, and check if we've loaded all the images
        if( ++imageLoadingIterator == images.length)
            _continue(); // Run _continue() if this is the case
    }
}

I feel like this isn't the best way to do this. Is there a way I can improve this function to run faster? For example: I'm thinking maybe creating a new Image object for each img tag is too much overhead.

Not really about performance, but this is more about clarity of the code.

Attach onload handlers first, for readability. Appending the src starts the loading process. If you saw code that loaded something, expect to do something, but haven't found the handler to do it makes it a bit confusing.
Declare one handler function in a persistent scope and have the onload refer to it, rather than create one handler for each onload, or creating the function everytime the whole routine executes.
Instead of find(), use jQuery function's second parameter, context. With this, jQuery finds the elements with the given selector under the jQuery object that is on the second parameter.
If the images are children of data.content, use children() instead of find() to avoid deep DOM traversal. Also, the lower you are in the DOM, the less deep find() has to dive and find your elements.
Use strict comparison as much as possible.
Don't forget to declare the variables and use var. You'd be declaring globals if you didn't.

And so:

var $images = $('img', data.content),
  imagesLength = $images.length,
  imageLoadingIterator = 0,
  img, i;

function onImageLoad() {
  if (++imageLoadingIterator === images.length) _continue();
}

for (i = 0; i < imagesLength; i++) {
  img = new Image();
  img.onload = onImageLoad;
  img.src = $images[i].src;
}

However, these advices might have a very negligible gain in performance, and might be unnecessary since the compiler might be optimizing them in some way.


Quick sort a list of integers in place This code is meant to sort a list of integers in place using quick sort.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def quicksort(l):
    quicksort_helper(l, 0, len(l)-1)

def quicksort_helper(l, lo, hi):
    if lo >= hi:
        return

    pivot_ind = partition(l, lo, hi)
    quicksort_helper(l, lo, pivot_ind-1)
    quicksort_helper(l, pivot_ind+1, hi)

def partition(l, lo, hi):
    pivot = l[hi]
    left = lo

    for right in range(lo, hi):
        if l[right] <= pivot:
            swap(l, left, right)
            left += 1
    swap(l, left, hi)

    pivot_ind = left
    return pivot_ind

def swap(l, i, j):
    temp = l[i]
    l[i] = l[j]
    l[j] = temp

Swapping

def swap(l, i, j):
    temp = l[i]
    l[i] = l[j]
    l[j] = temp

Just do:

l[i], l[j] = l[j], l[i] # (a)

You could abstract this into a swap function like you have done, but I probably wouldn't in this case. Matter of taste. Nevertheless, if you do swap the body definition should consist of (a).

Unnecessary variables.

pivot_ind = left
return pivot_ind

Just return left. Write a comment explaining what left is if you need to.


Testing an unsafe counter I made this studying my Java book about concurrency. It's just to test. I feel it works ok but I'm not so sure about my Java. I worry maybe my code style is strange. I really didn't want that exception. It bothers me that I have to catch it.

I'd love to hear your input on the Java style used here. Any suggestion for how to do something better is welcome! Is it ok to make the array of threads like this?

package com.katie;

// Demonstration of a counter that is not thread-safe.
class Counter {
    private int myCounter = 0;
    public void increment() { myCounter++; }
    public int getCounter() { return myCounter; }
}

class BadIdea implements Runnable {
    private Counter myTarget;
    private int myStabs;
    BadIdea(Counter victim, int stabs) {
        myTarget = victim;
        myStabs = stabs;
    }
    public void run() {
        for (int i = 0; i < myStabs; i++) {
            myTarget.increment();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Counter guineaPig = new Counter();
        final int stabCount = 1000;
        final int threadCount = 3;

        // make multiple threads and use them to break the guineaPig
        // because she is not thread safe!

        Thread[] threads = new Thread[threadCount];
        for (int i = 0; i < threadCount; i++) {
            threads[i] = new Thread(new BadIdea(guineaPig, stabCount));
        }
        for (Thread t : threads) {
            t.start();
        }
        for (Thread t : threads) {
            try {
                t.join();
            } catch (InterruptedException e) {
                // i dont care!!
            }
        }

        // These will be different sometimes.

        System.out.println(guineaPig.getCounter());
        System.out.println(threadCount * stabCount);
    }
}

In general, your code looks fine to me. You could make myTarget and myStabs in BadIdea final. Also, you don't have to create three separate BadIdea objects in main(String[]). Instead, it would suffice to create only one BadIdea from guineaPig and stabCount and pass that object to the threads you start, because the BadIdea objects themselves will never change, only the Counter the point to, and since they all point to the same Counter (which is guineaPig), creating a separate BadIdea for each thread is redundant.

And about that InterruptedException: I can't envision a scenario in which an InterruptedException could ever be thrown in your program, but your comment "i dont care!!" implies that you think by merely swallowing the exception, you let the flow of your program be unaffected by it. However, this is not what would happen if an InterruptedException were actually thrown. If your code actually caught an InterruptedException, then it would no longer wait for t to die, but instead, the for-each loop would move on to the next thread, if there is one. So theoretically, it could happen that, if an InterruptedException is thrown, by the time you call System.out.println(guineaPig.getCounter()), not all 3 threads (or however many you start) are dead yet and the guinea pig is secretly still being tortured.

To prevent this from happening, you could rewrite the code to look something like this:

for (Thread t : threads) {
    while (t.isAlive()) {
        try {
            t.join();
        } catch (InterruptedException e) {
            // i really dont care!!
        }
    }
}


Read files from a directory using Promises Using javascript functions and the old way of doing things I wrote a piece of code to copy the first file in a directory to a file Test.

console.log("Copy First File");
var fs = require('fs');
fs.readdir(".", function(err, files) {
    if (err) {console.log(err);process.exit(1);}

    fs.exists(files[0], function(exits) {
        fs.readFile(files[0], function(err, data) {
            if (err) {console.log(err);process.exit(1);}

            fs.writeFile('Test', data, function(err) {
                if (err) {console.log(err);process.exit(1);}

                console.log("Data Copied");
            });

        })
    });
});

After reading about Promises (and several failed attempts). I managed to convert the above to use Promise and .then() chaining.

function getAListOfFiles() {
    return new Promise(function(resolve, reject) {
        fs.readdir(".", function(err, files) {
            if (err) {
                reject(err);
            }
            else {
                resolve(files);
            }
        });
    });
}
function checkFirstFileExists(files) {
    return new Promise(function(resolve, reject) {
        fs.exists(files[0], function(exists) {
            if (!exists) {
                reject("No File");
            }
            else {
                resolve(files[0]);
            }
        });
    });
}
function readFileData(file) {
    return new Promise(function(resolve, reject) {
        fs.readFile(file, function(err, data) {
            if (err) {
                reject(err);
            }
            else {
                resolve(data);
            }
        });
    });
}
function writeFileData(data) {
    return new Promise(function(resolve, reject) {
        fs.writeFile('Test', data, function(err) {
            if (err) {
                reject(err);
            }
            else {
                resolve("A-OK");
            }
        });
    });
}

console.log("Copy First File");
var fs = require('fs');

new Promise(function(resolve, reject) {
    resolve(1);
})
.then(getAListOfFiles)
.then(checkFirstFileExists)
.then(readFileData)
.then(writeFileData)
.then(function(comment) {
    console.log("Data Copied " + comment);
})
.catch(function(err) {
    console.log("Error: " + err);
});

I want to know is my use of Promise and chaining idiomatic? What can I do better? It seems much longer than the original and thus slightly harder to read.

Particularly interested if:

new Promise(function(resolve, reject) {
    resolve(1);
})
.then(getAListOfFiles)
.then(...

Is more idiomatic than

getAListOfFiles()
.then(...

For the most part, your use of promises is idiomatic. Good work! Most people new to promises fail to chain them and end up with a similar pyramid to your original code.

fs.exists is deprecated, you should either use fs.stat, fs.access, or just catch the exception when trying to read it. Additionally, the use of fs.exists introduces a race condition where the file could be deleted between the exists call and the read call.
If the first file turns out to be very large, you may run into memory issues since you first read the file into memory and then write it out to another file. Thankfully, you can use fs.copyFile to resolve this, and also reduce the amount of code you have to write. If you are stuck with a version of Node older than 8.5.0, you can use fs.createReadStream and fs.createWriteStream to copy the file without the memory issues.
As elclanrs mentioned in the comments, you can use util.promisify to automatically wrap some functions in a promise based api. It was added in 8.0.0, but is fairly simple to implement.
You should not construct a promise to just return a value.

new Promise(function(resolve, reject) {
    resolve(1);
})

is equivalent to

Promise.resolve(1)

In your case, since you don't actually use the return value, it is better to just begin the promise chain with getAListOfFiles(), and even if you did use the return value, you should just start with getAListOfFiles(1).

Here's how I would write this script with promises:

const { promisify } = require('util');
const fs = require('fs');

const readdir = promisify(fs.readdir);
const copy = promisify(fs.copyFile);

readdir('.')
.then(files => copy(files[0], 'Test'))
.then(() => console.log('Data copied!'))
.catch(console.error);

Bonus: It's a really good idea to understand how promises work before using async / await, but once you do, async functions can help make the logic look more synchronous. In this case, there isn't really a benefit, but for more complex situations, it can help immensely.

const { promisify } = require('util');
const fs = require('fs');

const readdir = promisify(fs.readdir);
const copy = promisify(fs.copyFile);

async function main() {
    try {
        const files = await readdir('.');
        await copy(files[0], 'Test');
        console.log('Data copied!');
    } catch (err) {
        console.error(err);
    }
}

main();


Preferred implementation of `Array::operator=(const Array & rhs)` I have a custom template class Array<T>, and am currently implementing the assignment operator.

However, I've come across a design decision: When assigning two arrays, must I require them to have the same size, or adjust the LHS Array size to the RHS?

Pros and Cons of Requiring Equal Size

Pro

Most of the time, the array is often thought of as a static container (there are std::vector, etc. for dynamic containers).
It's more efficient, because I do not have to reallocate; rather, I overwrite each element of the LHS.

Con

It's a hassle for the user to do the work himself if he does intend to have a variable-length Array, plus it would be inefficient.

Code

Here are the implementations of the two versions I'm considering.

Equal Size

template <typename T>
bool JKArray<T>::operator=(const JKArray<T> & rhs)
{
    if (this == *rhs) { return true; }
    else
    {
        if (size_ != rhs.size_) { return false; }
        else
        {
            for (int i = 0; i < size_; i++) { array_[i] = rhs.array_[i]; }
        }
    }
}

Unequal Size

template <typename T>
void JKArray<T>::operator=(const JKArray<T> & rhs)
{
    if (this == *rhs) { }
    else
    {
        if (size_ != rhs.size_)
        {
            delete [] array_;
            size_ = rhs.size_;
            array_ = new T[size_];
        }
        for (int i = 0; i < size_; i++) { array_[i] = rhs.array_[i]; }
    }
}

Note

Regarding the implementation of Equal Size: I return false if the size is not equal, and true otherwise. Of course, I could use exceptions, however this is satisfactory for now.

I'm leaning towards making operator= fail* if RHS is a different length than LHS.

I'd like to know what other's have done, and what the prefer. To avoid closing this on the basis of opinion-based, please give explanations as to why one might be preferred over the other.

*See 'Note' under 'Code'.

template <typename T>
bool JKArray<T>::operator=(const JKArray<T> & rhs)

template <typename T>
void JKArray<T>::operator=(const JKArray<T> & rhs)

Neither of them have the correct signature for a copy assignment. The correct signature for that operator is class_name & class_name :: operator= ( const class_name & ).

That already rules out abusing the return value to signal success or failure. If you want runtime errors, you got to do it with exceptions.

If you violate that signature, it makes common patterns such as chained assignment (a = b = c = {...};) impossible. This may break other templated libraries depending on your datatypes to adhere to the standards.

Especially returning a bool may cause rather unexpected side effects.

  Pro

  Most of the time, the array is often thought of as a static container (there are std::vector, etc. for dynamic containers).
  It's more efficient, because I do not have to reallocate; rather, I overwrite each element of the LHS.

  Con

  It's a hassle for the user to do the work himself if he does intend to have a variable-length Array, plus it would be inefficient.

That list is by no means complete. There are more aspects to cover:

Iterator invalidation

When you have to re-allocate the backing data structure, it would be trivial to keep all existing iterators valid for same-size copies, while the same feat is problematic for different sizes.
Heap vs stack allocation

For fixed size arrays, it's not even necessary to allocate them on the heap, sufficiently small arrays may as well be allocated straight on the stack. This is obviously impossible to do with the dynamically sized ones.
Array or Vector?

While you call it Array, if you make it re-sizable it behaves more like an std::vector rather than an std::array.
Size as part of the type?

As @Olzhas mentioned, it's an option to include the size of the backing array as a template parameter. This provides compile time checks for compatible or incompatible sizes. Whereby compile time checks - if applicable - are obviously to be preferred.

This would actually be how std::array does it.


Optimizing bubble sort code Please help me optimize this bubble sort code. It's working fine otherwise.

int[] randomIntegers = {2,3,1,1,4,5,8,-2,0};

for(int i=0;i<randomIntegers.length;i++){
  for(int j=i;j<(randomIntegers.length-1);j++){
    if(randomIntegers[i]>randomIntegers[j+1]){
      randomIntegers[i] += randomIntegers[j+1];
      randomIntegers[j+1] = randomIntegers[i] - randomIntegers[j+1];
      randomIntegers[i] = randomIntegers[i] - randomIntegers[j+1];
    }
  }
}
for(int i:randomIntegers){
  System.out.print(i+",");
}

If you need to optimize bubble sort, you're doing it wrong. It's not really worth optimizing something that's inherently slow. You should just use a better sorting algorithm.


Implementation of insertion sort in Ruby, code correctness To implement an insertion sort that sorts an array with optional block to determine sorting order, how can I improve this code?  (Seeking best practices and code correctness)

def custom_insertion_sort(arr)
  for i in (1..arr.length-1)
    curr = arr[i]
    compare = i-1
    if block_given?
      sorted = yield arr, compare, curr
    else
      sorted = arr[compare] < curr
    end
   while compare >= 0 && sorted
      arr[compare+1] = arr[compare]
      compare -= 1
      if block_given?
        sorted = yield arr, compare, curr
      else
        sorted = arr[compare] < curr
      end
    end
    arr[compare+1] = curr
  end
  arr
end

Your block usage yield arr, compare, curr is rather weird:

custom_insertion_sort(array){ |_, i, j| _[i].abs > j.abs }

I would do yield arr[compare], curr:

naki_insert_sort(array){ |i, j| i.abs > j.abs }

You may use ...n syntax instead of ..n-1
You are sorting inplace, operating with an array like with a memory pointer, so you don't have to return arr from the function.
Instead of writing comparision code twice you can either define lambda or put it just inside while condition.

And after a bit more golf I've got this:

def naki_insert_sort arr
    for i in (1...arr.length)
        curr = arr[compare = i]
        while 0 <= (compare -= 1) && ( block_given? ?
            yield(arr[compare], curr) :
            arr[compare] < curr
        )
            arr[compare + 1] = arr[compare]
        end
        arr[compare + 1] = curr
    end
end

But looks like Insertion sort and Ruby don't actually suit each other, because using indexes isn't functional.


Updating geo coordinates An error in a live environment was detected when trying to convert string geo coordinates into a double.

The current culture (hu-HU) uses comma instead of point for the decimals and that produced an exception when trying to parse Double.Parse(47,545874)
That's why I'm using CultureInfo.InvariantCulture and the reason to wrap the conversion up in a try/catch statement.

Is there a better way to handle these exceptions?

public void UpdateJobGeoCoordinates(Job job)
{
    var address = _kernel.GetKernel();

    var gpsCoordinate = _locator.GetGpsCoordinates(address);

    try
    {
        job.Lat = Double.Parse(gpsCoordinate.Item1, CultureInfo.InvariantCulture);
        job.Lng = Double.Parse(gpsCoordinate.Item2, CultureInfo.InvariantCulture);
    }
    catch (FormatException)
    {
        ResetCoordinates(job);
        Logger.Warn("Geo location issue for Job [{0}] , Format error when convert '{1}', '{2}' to a Double.", job.ERPServiceOrderId, gpsCoordinate.Item1, gpsCoordinate.Item2);
    }
    catch (OverflowException)
    {
        ResetCoordinates(job);
        Logger.Warn("Geo location issue for Job [{0}] , Overflow when convert '{1}', '{2}' to a Double.", job.ERPServiceOrderId, gpsCoordinate.Item1, gpsCoordinate.Item2);
    }
    catch (Exception ex)
    {
        ResetCoordinates(job);
        Logger.Warn("Geo location issue for Job [{0}] , Exception message: {1}", job.ERPServiceOrderId, ex.Message);
    }
}

For what it's worth I think you've over complicated this. It seems to me that you care if you succeed or not and then want to pass as much information on to someone who can figure out what went wrong. The only 2 lines that are in the try block are parsing to doubles so just catch Exception and beef up the information included.

public void UpdateJobGeoCoordinates(Job job)
{
    var address = _kernel.GetKernel();

    var gpsCoordinate = _locator.GetGpsCoordinates(address);

    try
    {
        job.Lat = Double.Parse(gpsCoordinate.Item1, CultureInfo.InvariantCulture);
        job.Lng = Double.Parse(gpsCoordinate.Item2, CultureInfo.InvariantCulture);
    }
    catch (Exception ex)
    {
        ResetCoordinates(job);
        Logger.Warn("Geo location issue for Job [{0}] , Exception details: {1}", job.ERPServiceOrderId, ex);
    }
}

Note that Exception.ToString() is so much more useful than just the message.

You'll get the type of the exception, the message and the stack trace.


xkcd comics data provider Please help me improving this code(golang), thanks!

Why I need built a API for xkcd

Can't get the data provided by xkcd directly in front-end(CORS).
So we can package the data to 10 comics per request. Instead of 1 request match one comic.

main.go

package main

import (
    "encoding/json"
    "fmt"
    "log"
    "net/http"
    "strconv"
    "strings"
)

type comicInfo struct {
    Number int    `json:"num"`
    Img    string `json:"img"`
    Title  string `json:"title"`
    Alt    string `json:"alt"`
}

var comicInfoMap = make(map[int]comicInfo)
var newestComic comicInfo

func fetch(url string, ch chan<- comicInfo) {
    if res, err := http.Get(url); err == nil {
        if res.StatusCode == http.StatusOK {
            newComic := comicInfo{}
            if err := json.NewDecoder(res.Body).Decode(&newComic); err == nil {
                fmt.Println(newComic)
                ch <- newComic
            }
        }
    }
}

func init() {
    ch := make(chan comicInfo)
    if res, err := http.Get("http://xkcd.com/info.0.json"); err == nil {
        if res.StatusCode == http.StatusOK {
            newComic := comicInfo{}
            if err := json.NewDecoder(res.Body).Decode(&newComic); err == nil {
                newestComic = newComic
                comicInfoMap[newestComic.Number] = newestComic
                for j := 0; j < 10; j++ {
                    addtion := 100 * j
                    for i := addtion + 1; i < addtion+101; i++ {
                        indexStr := strconv.Itoa(newComic.Number - i)
                        url := "http://xkcd.com/" + indexStr + "/info.0.json"
                        go fetch(url, ch)
                    }
                    for i := addtion + 1; i < addtion+101; i++ {
                        newComic := <-ch
                        comicInfoMap[newComic.Number] = newComic
                    }
                }
            }
        }
    }
}

func main() {
    http.HandleFunc("/", handler)
    log.Fatal(http.ListenAndServe(":9020", nil))
}

func handler(w http.ResponseWriter, r *http.Request) {
    w.Header().Set("Access-Control-Allow-Origin", "*")
    w.Header().Set("Access-Control-Allow-Methods", "GET, OPTIONS")
    w.Header().Set("Access-Control-Allow-Headers",
        "Origin, X-Requested-With, Content-Type, Accept")

    var encoder = json.NewEncoder(w)
    if r.URL.Path == "/" {
        encoder.Encode(newestComic)
    } else {
        res := strings.Split(r.URL.Path, "/")
        r.Body.Close()
        path, err := strconv.Atoi(res[1])
        if err != nil {
            return
        }
        if path < 100 {
            number := path
            newComicInfoSlice := []comicInfo{}
            for i := 0; i < 10; i++ {
                index := newestComic.Number - i - 10*number
                newComicInfoSlice = append(newComicInfoSlice, comicInfoMap[index])
            }
            encoder.Encode(newComicInfoSlice)
        }
    }
}

Being inspired by recent xkcd comic I will review this particular piece of code:

res := strings.Split(r.URL.Path, "/")
path, err := strconv.Atoi(res[1])

As far as I understand it converts path string "/123" to int 123.

I see several issues here:

this code creates unnecessary (and possibly large) slice,
assumes that res[1] is always there,
parses negative numbers,
and allows input /123/whatever/goes/here/.

Split

Use strings.SplitN when you know how many parts of the slice you need. On /a/b/c/d/ input strings.Split will create slice with six items, but you need only res[1].

..

url.URL documentation states, that relative paths may omit leading slash. So on .. or . input access to res[1] will trigger panic with "runtime error: index out of range" message.

Malicious HTTP request may contain lots of crap similar ../.. so is crucial to validate this.

I suggest you to check that the path begins with a slash or test the length of res.

stronv.ParseUint

strconv.Atoi allows negative numbers. You can use strconv.ParseUint instead.

Path from HTTP request is same thing as any other form of user input. Proper handling of it is full of gotchas.

I suggest you to check that path begins with a slash and use strings.TrimSuffix to remove one possible trailing slash:

// Check that r.URL.Path begins with "/",
if (r.URL.Path[0] == "/") {
    // skip leading slash and trim one(!) possible trailing shash.
    num := strings.TrimSuffix(r.URL.Path[1:], "/")
    // Try to parse non negative number,
    tmp, err := strconv.ParseUint(num, 10, 32)
    if err != nil {
        // and return 404 if there is no one.
    }
    // Convert uint to int.
    index := int(tmp)

    // function body continues...
}


Python Line continuation dictionary I have a function that needs to return the call to another function that have some parameters. Let's say, for example, the following:

def some_func():
   iss = do_something()
   example = do_something_else()

   return some_long_name('maybe long string', {'this': iss, 'an': example, 'dictionary': 'wich is very long'})

I want to adjust it so it will comply with PEP 8. I tried:

def some_func():
   iss = do_something()
   example = do_something_else()

   return some_long_name('maybe long string', {'this': iss,
                                               'an': example,
                                               'dictionary': 'wich is very long'})

But it still goes way beyond 80 characters. So I did a two step 'line continuation', but don't know if it's how it's done.

def some_func():
   iss = do_something()
   example = do_something_else()

   return some_long_name('maybe long string',
                         {
                             'this': iss,
                             'an': example,
                             'dictionary': 'wich is very long'
                         })

Or should it be something like:

def some_func():
   iss = do_something()
   example = do_something_else()

   return some_long_name('maybe long string',
                         {'this': iss,
                          'an': example,
                          'dictionary': 'wich is very long'})

I would appreciate some insight so I can maintain a better code because PEP8 doesn't explain it very well.

In my opinion, use Explaining Variables or Summary Variables express the dict. I like this coding style as follows.

keyword = {
    'this': iss,
    'an': example,
    'dictionary': 'wich is very long',
}
return some_long_name('maybe long string', keyword)


User authentication SQL injection Is this authentication mechanism vulnerable to SQL injection?
If so, how could one exploit it, and what is the most effective way to mitigate this?

if (isset($_POST['userid']) && isset($_POST['password'])){

$username = $_POST['userid'];
$password = crypt($_POST['password'],'34l5kj');

    $query = "SELECT * FROM users WHERE name =:username and pass=:password";
$db->query($query);
$db->bind(':username', $username);
$db->bind(':password', $password);
$db->execute();
$data = $db->single();

            $_SESSION['valid_user'] = $username;
            $_SESSION['user_id'] = $data['id'];
            $_SESSION['pwd']=$_POST['password'];

First, regarding your initial question: the code you have right here is definitely safe against SQL injection.  Using prepared queries (which you are doing) will protect you from the majority of SQL injection vulnerabilities.  It's worth doing some reading on SQL injection in general, but otherwise the biggest concern you have is for those queries that cannot use prepared queries.  This is typically the case if you need a column name to change based on user input, in which case you need to apply a white-list.  However, that isn't an issue here, so no need to over complicate things.  So while you are immediately protected against SQL injection, there are still some potential concerns here, and some general room for improvement:

You store the raw user data in the session.  In particular, the username is stored without any filtering.  This can result in a second-order SQL injection vulnerability.  In effect, you are using prepared queries here, but unsanitized data is being stored in the session.  Later on when that data is retrieved from the session and used (for instance, to verify the user when they return to the site), you can't see that it is dirty data and may forget to use proper prepared queries.  As a result, you may accidentally introduce an SQL injection vulnerability that is hard to see.  So remember to abide by two very important rules: 1) Always clean user input before storing and 2) Always use prepared queries.  The latter could very well be true already, but make sure and do #1 as well.
In this particular case though it is better not to worry about cleaning the username so much as halting all processing if you find invalid input.  In an ideal situation this would be part of a check_login function and you would return false as soon as you determined that the login was invalid.  So before you even do anything with the username you first check if it is valid (probably by making sure it doesn't contain any special characters) and return false if you find any problems.  This way there is no chance of getting dangerous input into the session in the first place.  It is much easier if people login with an email instead of a username, because you can use filter_var to make sure an actual email address was given, and return false if not.  Email addresses, of course, cannot be used for SQL injection.
Don't use crypt.  Use password_hash, and let it pick the salt for you.
Don't compare the password in the database.  Password hash comparisons are actually difficult to do right, and (while difficult to execute), a direct comparison like you are doing can leave your application vulnerable to timing attacks and other subtle weaknesses.  Select the hashed password out of the database and use password_verify to check if it matches the user input.
It is probably a bit to soon for you yet, but if you are just learning then now is a good time to start reading about and learning about dependency injection and test automation.  Those two will substantially improve the quality of your code in the long run, but obviously aren't being used here.
Your spacing is very inconsistent.  Following good coding conventions is a surprisingly important way of minimizing bugs in the long run and making maintenance easier.  Pick a coding convention and stick to it.  PSR is the standard in the PHP world, but sticking to any standard is better than being inconsistent.

Code organization is also very important to keep bugs at a minimum in the long run, but since only part of your code is posted here, there isn't much I can say about that at the moment.

Edit to add more about input filtering

I think it is worth a few more minutes to expand upon my discussion about input filtering.  The issue is that there are more vulnerabilities to be concerned about than just SQL Injection.  When you store user input directly in the application (i.e. $_SESSION['valid_user'] = $_POST['userid']) you leave a lot of room for security holes to leak in.  In this case, because you are checking that the username exists in the database, you are effectively checking the username against a whitelist.  Validating against a white-list is the typically the best approach to security, and in this particular case it is unlikely to cause you any specific trouble, but most security vulnerabilities are the more subtle kind that come from failures to properly validate user input at every step of the process.

The concept you want to go for is defense-in-depth.  In this case your login code is implicitly relying upon the fact that the registration form performs proper user-input validation.  As a result, a simple failure in validation logic on the registration page can potentially open up additional avenues for attack when the login page doesn't do any validation of its own.  When each area of the system practices proper security for all data relevant to itself, it becomes much more difficult for an attacker to find an exploitable security bug.  As a result, the most secure way to handle user input is:

Validate user input as strictly as you can, and reject any requests with invalid data
Always use prepared queries


Portably generate uniformly random floats from mt19937 output My goal is to generate a sequence of random float from a seeded random generator. The sequence should be the same on any machine / any compiler -- this rules out the use of std::uniform_real_distribution since it doesn't make that guarantee. Instead we have to create our own version of this, which we will be able to guarantee is portable / uses the same implementation on all platforms.

We can assume I'm starting from std::mt19937 since the C++ standard does mandate its implementation, so the goal becomes, how can I convert a uniformly random uint32_t to a uniformly random float in the range [0.0f, 1.0f]. The main things I'm concerned about are:

Efficiency
Loss of precision

I threw something together which looks like this:

template <typename RNG>
float uniform_float(RNG & rng) {
  static_assert(std::is_same<std::uint32_t, typename RNG::result_type>::value, "Expected to be used with RNG whose result type is uint32_t, like mt19937");

  float result = static_cast<float>(rng());

  for (int i = 0; i < 32; ++i) {
    result /= 2;
  }
  return result;
}

In preliminary tests it seems to be outputting floats in the range [0.0f, 1.0f].

I did also try looking around in the libstdc++ headers to see where they are doing the equivalent thing, but it looked like it was going to take some digging to actually find it.

Here are some natural questions in my mind:

When static casting uint32_t to float, the value is never outside the representable range, so the behavior is not undefined. Typically it will not be representable exactly though, since both types have 32 bits, and float has to have some overhead. The standard says it is implementation-defined whether I get the next highest or next lowest representable number in this case. I assume that it doesn't matter since I'm going to divide by two anyways many times after this, and then many of these values will collide anyways?
Is it better (faster) to divide by the uint32_t max value, rather than by 2^32? I assume not.
Does dividing by two repeatedly cause a subtle bias as the least significant bits are repeatedly discarded? If they are only being discarded then I would expect not, but possibly there is some rounding that takes place and could cause problems?

An alternative strategy would be, start with 2^{-32} as a float, and then multiply it up by a random integer into the range 0.0f, 1.0f. However it's harder for me to understand in terms of the standard exactly what will happen if I do that -- what if 2^{-32} is not exactly representable? If I simply write it as a multiplication, then the int will be promoted to a float first anyways, right? Is it better to do some kind hand-rolled operation for int * float, using a bit-by-bit doubling routine etc.?

At least in my opinion, the efficiency question you've raised (repeated division by 2 vs. division by 232 vs. multiplication by 2-32) is best answered by profiling.

I, however, would take issue with making a blind assumption that the generator's maximum is 232-1 at all. Instead, I'd rather use the generator's own specification of the maximum value it can return, so the code would look something like this:

return (float)rng() / (float)RNG::max();

Here again, pre-inverting and multiplying might (possibly) improve speed:

static const float factor = 1.0f / RNG::max();

return rng() * factor;

I also tend to wonder whether it might make sense to make the result type generic. With this, we're no longer restricted to a generator that produces a 32-bit result, but we probably do want to assure that the result type is floating point.

template <typename Result, typename RNG>
Result uniform_dist(RNG & rng) {
    static_assert(std::is_floating_point<Result>::value, "Result must be a floating point type");

    static const Result factor = Result(1) / static_cast<Result>(RNG::max());

    return rng() * factor;
}

Then we'd specify the result type as a template parameter:

std::mt19937 rng { std::random_device()() };

std::cout << uniform_dist<float>(rng) << "\n";

std::cout << uniform_dist<double>(rng) << "\n";


Synchronising data in C# We use a third party dll which has an object called CServer and was provided by one of our software vendors to act as an API between our applications and their applications.

CServer has the following method:

bool SynchroniseData() which can be called if we want to fetch data from server which is very important for our application. This call signifies to the DLL our intention that we want to fetch the data. It does not fetch the data. Instead it returns true, if the request was successfully send to their application.

When data are actually fetched in the CServer object, CServer fires the event onDataFetched. We listen to that event and process the data. The CServer always has the latest data, since it continuously synchronises the data with our Vendor's servers.

However, there are many times at which the event onDataSynchronisationStopped is called. This signifies that the CServer object will stop data synchronisation with the server. This event is fired when the network is momentarily down, or if the server has some minor delays and so on.

We always want to have that data, and thus we try to fetch them again.

We currently do it like this:

private void OnDataFetchedHandler(object sender, EventArgs eventArgs){

            try{
                bool dataHaveBeenFetched;
                do{
                    dataHaveBeenFetched = TrytoFetchData((CServer) sender);
                    Thread.Sleep(1000);
                } while (!dataHaveBeenFetched);
            }
            catch (Exception ex){
                Log.ErrorFormat(ex.Message, ex);
            }
        }

        private bool TrytoFetchData(CServer sender){
            sender.SynchroniseData();
            ManualResetEvent manualResetEvent = new ManualResetEvent(false);
            EventHandler manualResetEventSethandler = (s, e) => manualResetEvent.Set();
            sender.OnDataFetched += manualResetEventSethandler;

            bool dataHaveBeenFetched = manualResetEvent.WaitOne(new TimeSpan(0, 0, 3, 0));
            sender.OnDataFetched -= manualResetEventSethandler;

            return dataHaveBeenFetched;
        }

Is there any cleaner way of doing this?

Instead of do ... while loop you can use SpinWait.SpinUntil:

bool dataHaveBeenFetched = SpinWait.SpinUntil(() => TrytoFetchData((CServer)sender))

And as @t3chb0t noted it seems strange to sleep 1 second between TrytoFetchData calls.


Slow execution time of search algorithm I have solved a problem of a game named 'Set'.
The full problem is detailed on it's website: https://www.urionlinejudge.com.br/judge/en/problems/view/1090

However my code for the search algorithm is too slow, I'd like to achieve something around \$O(n)\$. How can I make SetGameManager::CountSet() better?

This is not the full code, it's just so that you have an idea of what's going on:

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>

enum TYPE{
    SQUARE,
    CIRCLE,
    TRIANGLE,
};

struct _card
{
    TYPE type;
    int amount;
    _card( int a, TYPE t) { type = t; amount = a;};
};

inline bool canMatch(_card a, _card b)
{
    return((a.type == b.type && a.amount != b.amount) || (a.type == b.type && a.amount == b.amount) );
}

inline bool canMatch3(_card a, _card b, _card c)
{
    return((a.type == b.type && a.type == c.type)
           && ((a.amount != b.amount && b.amount != c.amount && a.amount != c.amount) ||
               ( a.amount == b.amount && a.amount == c.amount )));
}

inline bool cannotMatch(_card a, _card b)
{
    return(a.type != b.type && a.amount != b.amount);
}

inline bool cannotMatch3(_card a, _card b, _card c)
{
    return((a.type != b.type && b.type != c.type && a.type != c.type) &&
           (a.amount != b.amount && b.amount != c.amount && a.amount != c.amount));
}

class SetGameManager {
public:
    std::vector<_card> gameCards;
}

inline unsigned int SetGameManager::CountSet()
{
    unsigned int SetMatches = 0;

    unsigned int i1 = 0;

    std::sort(this->gameCards.begin(), this->gameCards.end());

    while(gameCards.size() > 2)
    {
        auto continue_outer_loop(true);
        for(unsigned int i2=1; continue_outer_loop && (i2<gameCards.size()); i2++)
        {
            if(i2 == 2) continue;
            auto const p_match_3_func
            (
                cannotMatch(gameCards.at(i1), gameCards.at(i2))
                ?
                &cannotMatch3
                :
                &canMatch3
            );
            for(unsigned int i3=2; i3<gameCards.size(); i3++)
            {
                if((*p_match_3_func)(gameCards.at(i1), gameCards.at(i2), gameCards.at(i3)))
                {
                    SetMatches++;
                    gameCards.erase(gameCards.begin()+i3);
                            gameCards.erase(gameCards.begin()+i2);
                    continue_outer_loop = false;
                    break;
                }
            }
        }
        gameCards.erase(gameCards.begin());
    }

    return SetMatches;
}

I think in this case the answer is to count rather than sort and search. I would create a struct that simply keeps count of how many cards of each type. Something like this:

struct cardCounts {
    unsigned long numOneCircles;
    unsigned long numTwoCircles;
    unsigned long numThreeCircles;
    unsigned long numOneSquares;
    unsigned long numTwoSquares;
    unsigned long numThreeSquares;
    unsigned long numOneTriangles;
    unsigned long numTwoTriangles;
    unsigned long numThreeTriangles;
};

You can initialize them all to 0, then increment each one as you read a card of that type from the input.

Once you've read all the cards, you can make combinations from them. For example, you can figure out how many sets containing 3 cards of 1 circle are possible by simply dividing numOneCircles by 3. Then the same for each other member of the struct.

Next, you can find combinations where 1 property is the same and the other are all different. So either the shape is the same but the counts are different, or the counts are the same and the shapes are different. You can take the minimum of numOneCircles, numTwoCircles, and numThreeCircles, and that's how many sets you can make with 1 card from each stack. Do the same for squares then triangles. Then switch it so the number stays the same but the shapes are different - so across numOneCircles, numOneSquares, and numOneTriangles.

Finally, find all combinations where both the shape and the number are different. This one is a little trickier, but not too bad. Check for one circle, two squares, three triangles. (Again, taking the min of those 3 as the result.) Then one circle, two triangles, three squares. There are 9 combinations you have to cover (I think?).

This should be O(n) in time and O(1) in space, as you'll only read through the data once when counting up the amounts, and you'll only ever use the 9 elements to store the sums.


First quicksort algorithm The program is separated in main.cpp, quicksort.cpp, partition.cpp and swap.cpp. There is also a header file to each .cpp file. The idea is from this site.

As you can see, I tried to be very modular. I think instead of having swap.cpp I could've simply used std::swap, right?

But the more important thing is, that I'd like to know how I can improve this quicksort algorithm or how to improve my program in general (not only the algorithm itself).

My three .hpp files are looking like this:

#ifndef __qs__name__
#define __qs__name__

#include <vector>

//protype

#endif

partition.cpp:

#include "partition.hpp"
#include "swap.hpp"

int partition(std::vector<int>& v, int ileft, int iright, int ipivot)
{
  int i = ileft, j = iright;

  while (i <= j)
  {
    while (v[i] < ipivot)
      i++;

    while (v[j] > ipivot)
      j--;

    if (i <= j)
    {
      swap(v, i, j);
      i++;
      j--;
    }
  }

  return j;
}

quicksort.cpp:

#include "quicksort.hpp"
#include "partition.hpp"

void quicksort(std::vector<int>& v, int ileft, int iright)
{
  int p, ipivot = v[iright]; // v[(ileft + iright) / 2];

  p = partition(v, ileft, iright, ipivot);

  if(ileft < p)
    quicksort(v, ileft, p);

  if((p + 1) < iright)
    quicksort(v, p + 1, iright);
}

swap.cpp:

#include "swap.hpp"

void swap(std::vector<int>& v, int i, int j)
{
  int temp = v[i];

  v[i] = v[j];
  v[j] = temp;
}

main.cpp:

#include <vector>

#include "partition.hpp"
#include "quicksort.hpp"
#include "swap.hpp"

int main()
{
  std::vector<int> v;
  v.push_back(7);
  v.push_back(10);
  v.push_back(11);
  v.push_back(1);
  /*v.push_back(-4543);
  v.push_back(88);
  v.push_back(5);
  v.push_back(3);
  v.push_back(31);
  v.push_back(34);
  v.push_back(7);*/

  for (int i = 0; i < v.size(); i++)
    std::cout << v[i] << std::endl;

  quicksort(v, 0, v.size()-1);
  std::cout << "\n";

  for (int i = 0; i < v.size(); i++)
    std::cout << v[i] << std::endl;

  return 0;
}

Any identifier with two underscores is reserved for the implementation. Using such an identifier yields undefined behaviour. Change your include guard. Something along QUICKSORT_GAMDSCHIEE_H is perfectly fine.

The user interface of quicksort should only take a std::vector. That way one cannot use size() by accident:

void quicksort(std::vector<int> & v) {
    quicksort_impl(v, 0, v.size() - 1);
}

Make it hard to use your code in a wrong way.

You can return immediately in both partition and quicksort if ileft == iright and spare yourself some other if.

  I think instead of having swap.cpp I could've simply used std::swap, right?

Exactly, or at least re-use it:

void swap(std::vector<int> & v, int i, int j) {
    std::swap(v[i], v[j]);
}

Instead of int we should use std::vector<int>::size_type (which will be size_t usually).

There's no reason to limit your quicksort to std::vector<int> it works fine for any std::vector<T> as long as T provides operator<.

To your "faster quicksort algorithm" question: you can find a std::vector where quicksort will take \$\mathcal O(n^2)\$ instead of \$\mathcal O(n \log n)\$. It's average time complexity is \$\mathcal O(n \log n)\$. Mergesort on the other hand is always \$\mathcal \Theta(n \log n)\$ time complexity.

Usually std::sort will be fast enough for all your use cases.


Is this the rigth way to write power and factorial functions with nasm? I wrote factorial and power functions with nasm but I don't know if it is the right to write assembly code. For example, by executing the functions I make some changes in the registers and I don't know if I have to revert them to their original value a the end with push and pop.

To write the factorial function, I first wrote it in C, compiled it with gcc and disassembled it with gdb. It gave me inspiration to write the code. Then I followed the same way of coding for my power function.

I use 64 bits registers.

Here is my code :

; Factorial function n!
; Argument from rsi and return in rax
factorial:
  push rbp
  mov rbp, rsp

  sub rsp, 0x10 ; Allocate 2 bytes on the stack
  mov DWORD [rbp-4], esi ; Put the parameter on the stack
  cmp DWORD [rbp-4], 1 ; if ==1 there is nothing to do
  jne factorial_rec
  mov eax, 1 ; return 1
  jmp fin_factorial
factorial_rec:
  mov eax, DWORD [rbp-4] ; Move the parameter in eax
  sub eax, 1
  mov esi, eax
  call factorial ;Call factorial recursively with eax-1
  imul eax, DWORD [rbp-4] ; multiply eax by the parameter
fin_factorial:
  leave
  ret

; Power function x^n
; Argument from rsi and rdi return in rax
; rsi at the power rdi
power:
  push rbp
  mov rbp, rsp

  cmp rdi, 0 ; if == 0
  jne power_init
  mov eax, 1 ; Return 1 (x^0=1)
  jmp power_end
power_init:
  sub rsp, 0x10 ; Allocate 2 bytes on the stack
  mov DWORD [rbp-4], esi ; Put the parameter on the stack
  mov eax, esi ; first power
power_loop:
  dec edi
  cmp edi, 0
  je power_end
  imul eax,DWORD[rbp-4] ; Multiply eax by the parameter until edi == 0
  jmp power_loop
power_end:
  leave
  ret

Thank you for your comments.

sub rsp, 0x10 ; Allocate 2 bytes on the stack

The comment is not correct! 0x10 is an hexadecimal number equal to 16 in decimal.

cmp rdi, 0 ; if == 0
jne power_init

If you need to compare with zero, it's usually better to test the register to itself:

test rdi, rdi
jnz  power_init

dec edi
cmp edi, 0
je power_end

The cmp edi, 0 instruction is redundant since the dec edi instruction already provides the necessary zero condition status.

  For example, by executing the functions I make some changes in the registers and I don't know if I have to revert them to their original value a the end with push and pop.

If you write these functions and your program uses these functions, then it's up to you to decide if you deem it useful to preserve any or all of the registers. If someone else will be using your functions your comments should make it absolutely clear what registers get clobbered!

The recursive factorial function can do without the prologue/epilogue code and is a bit complicated.

; IN (esi) OUT (eax) MOD ()
; Calculate eax = esi!
Factorial:
    mov  eax, 1
    cmp  esi, eax
    je   .return       ; esi was 1 -> eax = 1
    push esi           ; (1)
    dec  esi
    call Factorial     ; -> EAX
    pop  esi           ; (1)
    imul eax, esi
.return:
    ret

The power function can do without the prologue/epilogue code. There's no need to put ESI on the stack. If you want you could preserve the EDI register, but that's up to you to decide.

; IN (esi,edi) OUT (eax) MOD (edi)
; Calculate eax = esi ^ edi
Power:
                      ; push edi
    mov  eax, 1
    sub  edi, eax
    jb   .return      ; edi was 0 -> eax = esi^0 = 1
    mov  eax, esi
    jz   .return      ; edi was 1 -> eax = esi^1 = esi
.more:
    imul eax, esi
    dec  edi
    jnz  .more
.return
                      ; pop edi
    ret


Sending templatized e-mail to a million contacts This code runs fine without a bug, I need to optimize this code for following interview requirement.

Lets say i need to send it to 1 million contacts and emailBody is ~100Kb.

What code optimization do you recommend to make it faster ?
Write code or algorithm to explain the optimization you think will make this code faster, let's say 10x, 100x ?

public String sendEmail(String emailBody, Email email) {
      Hashtable<String, String> dataHash = new Hashtable<String, String>();

      dataHash.put("{{USER_EMAIL}}", email.getEmail());
      dataHash.put("{{USER_NAME}}", email.getName());
      dataHash.put("{{USER_PHONE}}", email.getPhone());
      dataHash.put("{{LOGIN_URL}}", email.getLoginUrl());

      Enumeration<String> tagList = dataHash.keys();

      while (tagList.hasMoreElements()) {
          String tag = tagList.nextElement();
          while (emailBody.indexOf(tag) != -1) {
              int indexOf = emailBody.toLowerCase()
                      .indexOf(tag.toLowerCase());

              String part1 = emailBody.substring(0, indexOf);
              String part2 = emailBody.substring(indexOf + tag.length(),
                      emailBody.length());

              emailBody = part1 + (String) dataHash.get(tag) + part2;
          }
      }
      return emailBody;
  }

My version is:

public String sendEmailUsingStringBuilder(String emailBody, Email email) {

        HashMap<String, String> dataHash = new HashMap<String, String>();
        dataHash.put("{{USER_EMAIL}}", email.getEmail());
        dataHash.put("{{USER_NAME}}", email.getName());
        dataHash.put("{{USER_PHONE}}", email.getPhone());
        dataHash.put("{{LOGIN_URL}}", email.getLoginUrl());

        StringBuilder strBuilder = new StringBuilder(emailBody);
        for ( String tag : dataHash.keySet() ) {
            int tagIndex;
            while ((tagIndex = strBuilder.indexOf(tag)) != -1) {
                strBuilder.replace(tagIndex, tagIndex + tag.length(),
                        (String) dataHash.get(tag));
                tagIndex = strBuilder.indexOf(tag);
            }
        }
        return strBuilder.toString();
    }

The big picture

First of all, consider the possibility that this is a trick question.  When sending bulk e-mail, the performance bottleneck is likely to be with the Mail Transfer Agent or the database query that fetches the contacts rather than with the text generation.  I would raise a concern with the interviewer that perhaps we should gather some evidence before making a premature effort to optimize the wrong part of the process.  Optimizing the code in this question (which takes about 2 seconds to run) will not make any noticeable difference to the time necessary to conduct the e-mail campaign.

Review

That said, if you had to optimize the text generation process, your changes would be a mild improvement.  The HashMap is more lightweight than the synchronized Hashtable, and the StringBuilder does save a bit of copying, though not by as much as you think, since you are still making four global substitution passes through the entire emailBody.

Strictly speaking, both the original code and your version of it are buggy.  Because string substitution is being done in multiple passes, it is possible that the output from one round of substitution could introduce a string that looks like a placeholder that ends up being inappropriately substituted in a subsequent round.  (Another example of this class of bug.)  Here, it's unlikely to be a problem unless someone decided to deliberately exploit the bug.

Alternative approach

If I really had to optimize this code, I would take a different approach entirely.  The same emailBody template is likely to used for a million emails.  Therefore, it would make sense to "pre-compile" the template…

Dear {{USER_NAME}},

According to our records, your phone number is {{USER_PHONE}} and
your e-mail address is {{USER_EMAIL}}.  If this is incorrect, please
go to {{LOGIN_URL}} and update your contact information.

… into code that looks like this:

public class C implements Template {
    public void write(Writer out, Map<String, String> params) throws IOException {
        out.write("Dear ");
        out.write(params.get("USER_NAME"));
        out.write("\n\nAccording to our records, your phone number is ");
        out.write(params.get("USER_PHONE"));
        out.write(" and \nyour e-mail address is ");
        out.write(params.get("USER_EMAIL"));
        out.write(".  If this is incorrect, please \ngo to ");
        out.write(params.get("LOGIN_URL"));
        out.write(" and update your contact information.\n");
        out.flush();
    }
}

The performance is likely to be unbeatable, since there is no longer any string substitution going on.  This is, in fact, very similar to the code that a JSP engine generates, and you could try to integrate a JSP implementation instead of reinventing the wheel.

As a bonus, you can stack layers of writers.  For example, you might pass it a subclass of FilterWriter that performs Format=Flowed line wrapping as per RFC 2646 to keep line lengths to a reasonable length as required by SMTP.  You could also stack that directly on top of a Writer that feeds the text directly to an SMTP socket.  Or, to obtain the resulting text as a string as in the original code, just use a StringWriter.

When I tried generating a million messages with a pre-compiled template, it completed the task in half the time of your code.  If you include the time to compile the template into executable form, it's still better than break-even for one million messages.  For a hundred million messages, it's about four times faster, compilation overhead included.


Validation/error handling of user input values This is a tiny learning program that lead to an interesting question: how can I best/most elegantly handle user entered numbers? This method works, fails cleanly, and reads well. It doesn't apply to types other than build in ones (as far as I know), but for floats and integers it's a nice feature. But it doesn't scale well, and seems cumbersome. Thoughts?

  Read two numbers (a,b) then increment (a) by one if ( a > b ) and (a >
  0)  otherwise decrement (a) by one. Print (a).

  Sample Input:
  27
  36

  Sample Output:
  26

#include <iostream>
#include <stdexcept>

int main() {
    int a, b;

    try {
        std::cin >> a;
        if (std::cin.fail()) throw std::runtime_error("Input is not an integer\n");
        std::cin >> b;
        if (std::cin.fail()) throw std::runtime_error("Input is not an integer\n");

    } catch (const std::runtime_error& e) {
        std::cout << e.what();
        return 1;
    }

    if (a > b && a > 0) {
        ++a;
    } else {
        --a;
    }

    std::cout << a;

    return 0;
}

I question your use of exceptions to catch the invalid input. Exceptions are supposed to be used for exceptional situations. Validating user input is part of the normal functionality of the program, not an exceptional situation. It's on the lazy side to use exceptions here; you're basically treating it as a goto.

When you do use exceptions, you should probably create a new class that's derived from one of the standard exception classes, and throw/catch that instead of the one from <stdexcept>.

I also think that when you fail, you should inform the user of that, reset the input stream, and give them another chance, rather than just exiting.

Also, sure this is just a toy, but in a real program you should separate the business logic of your program from the input and output. You might want to plug the business logic into adapters that get input from a different place and/or send the output to a different place.