Subscriptable/Indexable generator I'm not a Python developper, but I enjoy programming with it, and for a project I wanted to have generators that I can easily index. Using python's slice model is obviously the way to go, and here's the solution I've come up with.

class _SubscriptableGenerator():
    def __init__(self, generator, *args):
        self.gen = generator(*args)

    def __getitem__(self, key):
        try:
            if isinstance(key, int):
                self.ignore(key)
                yield next(self.gen)
            else:
                step = key.step if key.step else 1
                start = key.start if key.start else 0

                i = start
                self.ignore(start)

                while i < key.stop:
                    yield next(self.gen)
                    i = i + step
                    self.ignore(step-1)
        except Exception:
            self.raiseInvalidSlice(key)

    def raiseInvalidSlice(self, key):
        raise KeyError("{0} is not a valid key (only int and [x:y:z] slices are implemented.".format(key))

    def ignore(self, n):
        for i in range(n):
            next(self.gen)

It is not intended to be called by the user of the module, that's internal code. I for example define my generators like so

def _myGen(arg1, arg2):
    while 1:
        yield something

and provide them wrapped in my class

def myGen(*args):
    return _SubscriptableGenerator(_myGen, *args)

I'd like to know what a more pythonic solution would be, if there are things to fix, etc. I am not sure about the way to handle exceptions on the key.

The most Pythonic solution would be to use itertools.islice from the standard library. For example, like this:

from itertools import islice

class Sliceable(object):
    """Sliceable(iterable) is an object that wraps 'iterable' and
    generates items from 'iterable' when subscripted. For example:

        >>> from itertools import count, cycle
        >>> s = Sliceable(count())
        >>> list(s[3:10:2])
        [3, 5, 7, 9]
        >>> list(s[3:6])
        [13, 14, 15]
        >>> next(Sliceable(cycle(range(7)))[11])
        4
        >>> s['string']
        Traceback (most recent call last):
            ...
        KeyError: 'Key must be non-negative integer or slice, not string'

    """
    def __init__(self, iterable):
        self.iterable = iterable

    def __getitem__(self, key):
        if isinstance(key, int) and key >= 0:
            return islice(self.iterable, key, key + 1)
        elif isinstance(key, slice):
            return islice(self.iterable, key.start, key.stop, key.step)
        else:
            raise KeyError("Key must be non-negative integer or slice, not {}"
                           .format(key))

Note that I've given the class a better name, written a docstring, and provided some doctests.


Console-based game in Java to demonstrate Solid principles and abstractions I've written a console-based demo while learning about the Solid principles. Along the way, I've become exceedingly paranoid about whether I'm writing good code or not.

Here is the code I have so far:

public class Entity {  //Base template for all game entities...

private String name;

public Entity(String name)
{
    this.name = name;
    displayEntityName();
}

public String getName()
{
    return name;
}

public void setName(String newName)
{
    name = newName;
}

private void displayEntityName()
{
    System.out.println(name + " entity created...");
}

public class Player extends Entity {

private String[] inventory; //Player will have an inventory.
private int itemsInInventory;
private static final Random RAND = new Random();

public Player(String name) {
    super(name);
    inventory = new String[25]; //Default inventory size.
}

public void attack(Enemy enemy) //Player can attack all enemy types.
{
    System.out.println(super.getName() + " attacked the enemy...");
}

public void findLegendaryWeapon()
{
    inventory[0] = WeaponConstants.LEGENDARY_WEAPONS
    [RAND.nextInt(WeaponConstants.LEGENDARY_WEAPONS.length)];
    itemsInInventory++;
}

public void equiptWeapon()
{
    System.out.println(super.getName() + " equipted a weapon...");
}

public void searchChest()
{
    System.out.println(super.getName() + " searched the chest and found nothing...");
}

}

public enum WeaponConstants{ //Legendary weapon constants.

BOW_OF_THE_MAJOR_ARCHER(), BLOOD_LETTER,
DAWNFANG, FROZEN_TOUCH;

public static final String[] LEGENDARY_WEAPONS = {DAWNFANG.name(),
        BLOOD_LETTER.name(), FROZEN_TOUCH.name(), BOW_OF_THE_MAJOR_ARCHER.name()};

}

public interface Enemy { //Enemy interface...
    void attack(Player player);
}

public class Ghoul extends Entity implements Enemy { //An example of a standard enemy class.

    public Ghoul(String name) {
        super(name);
    }

    @Override
    public void attack(Player player) {
        System.out.println(super.getName() + " attacked " + player.getName());
    }
}

As mentioned above, I mainly want to know if I'm violating any of the Solid principles. My main concern is with my player class. I have quite a few methods in the class that do different types of things but they are all related to the player. Is this in any way violating the SRP principle?

Also, I wanted to know if my abstractions are correct and well-designed. Does this represent good coding style when used to develop more serious apps? I only have one year of experience, so I'm trying to solidify good practices early on. All input would be appreciated.

thanks for sharing your code

I know that this isn't a huge amount of code, but I'm going to look at it assuming that we will want to be able to add additional features and expand upon the code that's already here.

Redundant Comments

comments should say why you're doing something, not what you're doing.
This line

private String[] inventory; //Player will have an inventory.

is an example of a particularly bad offender. If I have a Player class, and it has an inventory member variable. We know that a Player will have an inventory, you don't need to write a comment saying what the code is already telling us.

Let's take a look at your Entity class. If we look in the constructor, we can see that the constructor is causing some side effects. In this case, it's printing to the console. In general, when I construct an object, I assume there will be no side effects or other unexpected behaviour. It's perfectly reasonable to provide a method to do this (in your case displayEntityName) but I would not include this in the constructor.

Consider making your classes immutable where possible

Unless you need to provide getter and setter methods for an instance variable, you should just leave them out entirely and make the variable final. I think here name is a good candidate, a getter seems reasonable, but I don't think you'd ever really need a setter. In a standard RPG or game, the player or enemy names don't change. They can be marked final.

private final String name;

see this question https://stackoverflow.com/questions/565095/are-getters-and-setters-poor-design-contradictory-advice-seen

have a look at the arguments for and against using getters and setters. I won't also recommend reading up on the benefits (and drawbacks) of writing immutable classes.

Avoid using Strings to represent more complex Objects

You're currently representing your inventory as an array of Strings. I would argue that an Item is far more than just a String. I would rather see an Item class. This could be a super class or interface that all items in your game could derive from / implement.

Some class that come to mind could be, Weapon, Armour, Accessory etc. If all of these things are represented as a single String, you're restricting what you can do. Additionally, I would not use an array for this situation. How about an Inventory class.

public class Inventory {
    private final List<Item> items = new ArrayList<>();

    public void addItem(Item item){ // can be weapon, armour etc.
        items.add(item);
    }

    public int numItems(){
        return items.size();
    }
    ...
}

Now, this Inventory class has the single responsibility of representing and maintaining this list of items.

and your Player class can just have an Inventory

private final Inventory inventory;

Or even just put it in the Entity class. This way an Enemy can have an inventory too.

Notice how I used a List instead of an array. This can be resized and already has a list.size() method to tell you how many elements are in it. No need to keep track of that stuff yourself!

This Inventory can now become a lot more useful than just an array of Strings.

Your current Player class has two responsibilities that jump out. One is providing Player behaviour, but it's also maintaining the inventory by keeping track of it's size. Now the Inventory class is in charge of this.

This method signature

public void searchChest()

At the moment this method simply prints that the Player is searching a chest, why not provide the option to search any Chest object.

public void searchChest(Chest chest)

and a Chest could look like

public class Chest {
    private final List<Item> contents;

    ...

    public List<Item> open(){
        return new ArrayList<>(contents);
    }
}

Then in the searchChest method, the Items from the Chest can be added to the Inventory.

Similarly to the Chest method, this method

public void equiptWeapon()

firstly, there's a typo here. It should be

public void equipWeapon()

Secondly, why not be able to provide a weapon

public void equipWeapon(Weapon weapon)

At the moment in your Enemy interface you have this method.

void attack(Player player);

What if you want to have Enemies fight each other, different factions etc.
There's no need to limit the potential targets, how about

void attack(Entity entity);

Some final points to consider.

When you attack another entity, you could get the currently equipped Weapon and the other entity's currently equipped Armour and do some simple math based on their Stats

instead of a displayEntityName method, you could just override toString and then print the Entity directly in the calling code.

Before you start coding anything, think about what Objects could be involved in your System/Game in real world terms, then start thinking about how these could be implemented as Objects in your code.

Instead of WeaponConstants, why not just make a Collection of Weapon objects.

Hopefully this review was useful for you.

Keep it up!


OOP PDO Database Connection I'm currently learning about PDO, and trying to connect to the database and CRUD in OOP way, this is a simple code that I use.

index.php

include_once("connection.php");
include_once("model.php");

$con    = new Connection();
$model  = new Model();

$model->insert();
$con->closeConnection();

connection.php

class Connection {

    protected $host = "localhost";
    protected $dbname = "pdo";
    protected $user = "root";
    protected $pass = "";
    protected $DBH;

    function __construct() {

        try {

            $this->DBH = new PDO("mysql:host=$this->host;dbname=$this->dbname", $this->user, $this->pass);
        }
        catch (PDOException $e) {

            echo $e->getMessage();
        }
    }

    public function closeConnection() {

        $this->DBH = null;
    }
}

model.php

class Model extends Connection {

    public function insert() {

        $STH = $this->DBH->prepare("INSERT INTO people (name) VALUES ('Yeaaap')");
        $STH->execute();
    }
}

Am I doing it in the right way?

Besides the already mentioned things I like to add a few of my own:

Connection charset
You should set the charset of the connection the be the same of your php files (and  definition when you use html):

Simply add , array(PDO::MYSQL_ATTR_INIT_COMMAND => "SET NAMES 'utf8'") after $this->pass

Coding Style

The naming of class variables shouldn't be all uppercase, so rename $DBH to $dbh.

Additionally I'd advice you the read the Coding Style Guide from the PHP Framework Interop Group which many php framework developers pay attention to lately.
http://www.php-fig.org/psr/psr-2/

There it says in Chapter 4.3 that you should put the opening curly brace of function on a new line.

User Input

As soon as some user input gets into your sql statement you should use parameterized queries, for example:

$stmt = $this->dbh->prepare("SELECT * FROM user WHERE passwort_hash = :passwort_hash");

$stmt->bindParam(":passwort_hash",md5($_POST['passwort']));
$stmt->execute();
...

This protects you against SQL-Injections.


Largest Prime Factor I'm trying to learn Python by working my way through problems on the Project Euler website. I managed to solve problem #3, which is

  What is the largest prime factor of the number 600851475143 ?

However, my code looks horrible. I'd really appreciate some advice from experienced Python programmers.

import math
import unittest

def largestPrime(n, factor):
    """
    Find the largest prime factor of n
    """

    def divide(m, factor):
        """
        Divide an integer by a factor as many times as possible
        """
        if m % factor is 0 :
            return divide(m / factor, factor)
        else :
            return m

    def isPrime(m):
        """
        Determine whether an integer is prime
        """
        if m is 2 :
            return True
        else :
            for i in range(2, int(math.floor(math.sqrt(m))) + 1):
                if m % i is 0 :
                    return False
            return True

    # Because there is at most one prime factor greater than sqrt(n),
    # make this an upper limit for the search
    limit = math.floor(math.sqrt(n))

    if factor <= int(limit):
        if isPrime(factor) and n % factor is 0:
            n = divide(n, factor)
            if n is 1:
                return factor
            else:
                return largestPrime(n, factor + 2)
        else:
            return largestPrime(n, factor + 2)
    return n

Some thoughts:

Divide function has been implemented recursively. In general, recursive implementations provide clarity of thought despite being inefficient. But in this case, it just makes the code cumbersome.

while m % factor == 0:
    m /= factor
return m

should do the job.

A lot of computational work is done by isPrime which is unnecessary. Eg: when factor 15 is being considered, the original n would've been already Divided by 3 and 5. So, if factor is not a prime then n%factor will not be 0.

So, the following should do:

import math
def largestPF(n):
    limit = int(math.sqrt(n)) + 1
    for factor in xrange(2, limit+1):
        while n % factor == 0:
            n /= factor
        if n == 1:
            return factor
    return n

You can of course, include the 'run through factors in steps of 2' heuristic if you want.

PS: Be careful with the is statement for verifying equality. It might lead to unexpected behaviour. Check out https://stackoverflow.com/questions/1504717/python-vs-is-comparing-strings-is-fails-sometimes-why


How to overcome static referencing errors in Java/basic programming? Someone posted a question on http://math.stackexchange.com earlier because their program to tranpose a matrix wasn't working. I copied the code they posted (which was just the transpose method) and added the code necessary to check if it worked on their example matrix and it does, so there's obviously a problem elsewhere in their code. I've posted my code below.

I don't have much programming experience and I suspect my style is unconventional. I implement most of the main program in the constructor, because every time I try to do it in the main method, I get lots of errors because I'm referencing non-static variables and methods from a static context. Maybe there are good reasons for using the static keyword, but I just wanted to write quickly a program to check whether the other person's method was correct and it seemed like the fact that the main method was static was getting in the way, so I just transferred most of the program to the constructor. I have 9 questions (question 8 is actually 2 questions), but question 8 is the most important:

Is my program ok?
Could it be better and if so, why?
What would be the conventional way to write the program?
How would the program be written with the main method in the main method rather than the constructor?
How does having the main method static help?
Someone wrote 'It is good to move code into on or more classes instead of having everything in the main method!'. If I do this, it seems like I get lot of errors because I'm referencing a static variable from a non-static context (since I must at least instantiate one class in the static main method). How would I best overcome this?
Someone else suggested changing everything to static, but that can't be normal, can it?
I know that's a lot of questions. I think the following 2 questions could pin down what I want to find out: where would printMatrix() be in a conventional program (presumably not in the constructor like it is in mine)? If there wouldn't even be such a method in a conventional program, how would the printing of the matrix and its transpose be implemented?

public class Matrix {
    double[][] M = new double[3][3];
    static int mat_size=3;
    public Matrix() {
        M[0][0]=1;
        M[0][1]=0;
        M[0][2]=0;
        M[1][0]=5;
        M[1][1]=1;
        M[1][2]=0;
        M[2][0]=6;
        M[2][1]=5;
        M[2][2]=1;
        System.out.println("M");
        printMatrix();
        transpose();
        System.out.println("M'");
        printMatrix();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new Matrix();
    }

    public void transpose() {

        System.out.println();

        for(int i = 0; i < mat_size; ++i) {
            for(int j = 0; j < i ; ++j) {
                double tmpJI = get(j, i);
                put(j, i, get(i, j));
                put(i, j, tmpJI);
            }
        }
    }

    public void printMatrix() {
        System.out.println();

        for(int i = 0; i < mat_size; ++i) {
            for(int j = 0; j < mat_size ; ++j) {
                System.out.print((int)get(i,j)+" ");
            }
            System.out.println();
        }

    }

    private void put(int i, int j, double d) {
        // TODO Auto-generated method stub
        M[i][j]=d;
    }

    private double get(int i, int j) {
        // TODO Auto-generated method stub
        return M[i][j];
    }
}

Is my program ok?

Well, I guess it works. However, it can be structured far better.

Basic Object Oriented Programming in Java

In Java (and all of this is also true for C#), every object has a type which is represented by a so-called class. We can define operations on each type, which we call methods. Some methods operate on an individual instance of a type. Other operations are not inherently bound to instances, and operate on the whole class. We call this second kind of operations static methods.

Likewise, data can either belong to a specific instance, or is shared across all instances, in which case it's called static. Every method (static and non-static) can refer to static data, because that is shared. However, static methods cannot reference instance data, because a static method can't tell from which instance you'd like the data – and sometimes, no instance may exist at all. Static methods are mostly useful for general helpers.

It is really important to grok the difference between static and non-static methods in order to use Java effectively (the same holds for any other class-based programming language).

Meaning of the main

What is the main and why do we need it? The main originated as a feature of the C programming language. It defines an entry point into the program. At startup, your classes are initialized and then the main methods gets called with the command line arguments in an array as parameter. The main method doesn't return a value (it is void), because returning from it aborts the process.

The main is static because it's a helper method to get your control flow going – it is not coupled to any instance. It is therefore common in a main to create an instance of the surrounding class, and work with that.

Constructors

A constructor is a special method used to initialize a fresh instance. All it usually does is assigning its arguments to the corrects data fields of the instance. It isn't recommended to do the actual work here – put that into another method.

In your code, everything after the initialization can be moved into the main method where it belongs. Note that methods are invoked on a specific instance with the dot operator. The main now looks like:

public static void main(String[] args) {
    Matrix matrix = new Matrix();

    System.out.println("M");
    matrix.printMatrix();

    matrix.transpose();

    System.out.println("M'");
    matrix.printMatrix();
}

Now we are already getting into the code review zone of this answer.

Design spotlights

A method should do one thing only and – no “and”!

Every method should do one thing only. Exaggerated: While a description of your method uses the word “and”, it is doing to much. Split the functionality into more methods. For example, your transpose method does this: “It prints an empty line and swaps columns with rows of the matrix”. Is printing an empty line really necessary in a method called “transpose”?

The same goes for your version of the constructor: “It initialized the matrix and prints it out and transposes it and prints it out again” – but we already cleaned that up above.

Composability

An advantage of having each method doing one concept only makes it easier to compose them in a different way to do new things. There are a few important things that can make this easier:

Don't hardcode stuff – parameterize it

Don't hardcode things that aren't universal constants. Actually, don't hardcode things at all. For example, you assign static int mat_size = 3 – but what if I want to use a 5×5 matrix? You don't provide any functionality that actually depends on the number three. Instead, the size is a property of each instance. Therefore, we'll remove the static modifier, and initialize it in the constructor.

The constructor is another example of hardcoding: The whole test matrix is specified there. It would be better to move that data out of the constructor, and have the constructor take an array as argument instead. I'd rather initialize a new matrix like:

// array literals :) – however, I'm unsure about the exact syntax
double[3][3] testData = { { 1, 0, 0 },
                          { 5, 1, 0 },
                          { 6, 5, 1 } };
Matrix matrix = new Matrix(3, testData);

We can now initialize a matrix with arbitrary other values, not only that specific data set.

Immutability

When objects don't change their internal state over time, programs often get a bit simpler. Mathematics does this as well: When we transpose a matrix M, the M still has its old values. The transposition produces a new and distinct matrix, which we can call M' (you even do this in your printout). There is no reason our transpose method shouldn't return a new matrix either. Now we get something along the lines of:

public Matrix transpose() {
    double[size][size] newData = new double[size][size];

    for(int i = 0; i < size; i++) {
        for(int j = 0; j < i ; j++) {
            newData[i][j] = get(j, i);
            newData[j][i] = get(i, j);
        }
        newData[i][i] = get(i, i);
    }

    return new Matrix(size, newData);
}

This changes our main:

public static void main(String[] args) {
    Matrix matrix = new Matrix();

    System.out.println("M");
    matrix.printMatrix();

    Matrix transposed = matrix.transpose();

    System.out.println("M'");
    transposed.printMatrix();
}

No side effects

When a method has any effect except returning some data, it has side effects. Such effects might be changing the state of some object (thus voiding the point about immutability), or printing out some data. These side effects make it more difficult to combine these methods in a new way.

Specifically, printMatrix is an offender here. Also because it can't be changed to print to anything other than System.out. What happens when I want a string representation to display on a GUI? I can't simply use your awesome Matrix class :(

Here, it would be better to implement the toString() function, which returns a string representation of your object. There is already a default implementation for every object, but we can override it. Then, our main will look like:

public static void main(String[] args) {
    Matrix matrix = new Matrix();

    System.out.println("M");
    System.out.println(matrix.toString());

    Matrix transposed = matrix.transpose();

    System.out.println("M'");
    System.out.println(transposed.toString());
}

That is more ugliness here, but massively clears up the rest of your code. The toString might be:

public String toString() {
    StrinBuilder sb = new StringBuilder();
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size ; j++) {
            sb.append(" " + (int) get(i, j));
        }
        sb.append("\n");
    }
    return sb.toString();
}
// apologies if I mixed up the StringBuilder API

A closing note on naming things

In Java, names are written in camelCase. Class names are capitalized. Any other names start with a lowercase letter: Matrix refers to a class, while matrix is a local variable, field, or method. As an exception, constants are written all-uppercase and seperated by underscores. Because for normal names the parts of a word are distinguished by capitalization, no underscores are ever used.

It is advisable to use meaningful names like matrix or transformedMatrix, not shortcuts like m or t or m_. Choosing longer names makes it easier to read a piece of code for someone who isn't used to your shortcut notation.


Simple concurrency implemented in Python Purpose of the question: learn more about ways to implement concurrency in Python / experimenting.

Context: I want to count all of the words in all of the files that match a particular pattern. The idea is that I can invoke the function count_words('/foo/bar/*.txt') and all of the words (i.e., strings separated by one or more whitespace characters) will be counted.

In the implementation I am looking for ways to implement count_words using concurrency. So far I managed to use multiprocessing and asyncio.

What do you think of these two approaches?
Do you see alternative approaches to do the same task?
What about the code style, should I implement a dedicated class for each approach?

I did not use threading as I noticed the performance improvement was not that impressive due to the limitation of the Python GIL.

import asyncio
import multiprocessing
import time
from pathlib import Path
from pprint import pprint

def count_words(file):
    with open(file) as f:
        return sum(len(line.split()) for line in f)

async def count_words_for_file(file):
    with open(file) as f:
        return sum(len(line.split()) for line in f)

def async_count_words(path, glob_pattern):
    event_loop = asyncio.get_event_loop()
    try:
        print("Entering event loop")
        for file in list(path.glob(glob_pattern)):
            result = event_loop.run_until_complete(count_words_for_file(file))
            print(result)
    finally:
        event_loop.close()

def multiprocess_count_words(path, glob_pattern):
    with multiprocessing.Pool(processes=8) as pool:
        results = pool.map(count_words, list(path.glob(glob_pattern)))
        pprint(results)

def sequential_count_words(path, glob_pattern):
    for file in list(path.glob(glob_pattern)):
        print(count_words(file))

if __name__ == '__main__':
    benchmark = []
    path = Path("../data/gutenberg/")
    # no need for benchmark on sequential_count_words, it is very slow!
    # sequential_count_words(path, "*.txt")

    start = time.time()
    async_count_words(path, "*.txt")
    benchmark.append(("async version", time.time() - start))

    start = time.time()
    multiprocess_count_words(path, "*.txt")
    benchmark.append(("multiprocess version", time.time() - start))

    print(*benchmark)

For simulating large quantity of files, I downloaded some books from Project Gutenberg (https://gutenberg.org/) and used the following command to create several duplicates of the same file.

for i in {000..99}; do cp 56943-0.txt $(openssl rand -base64 12)-$i.txt; done

async def count_words_for_file(file):
    with open(file) as f:
        return sum(len(line.split()) for line in f)

Just making this function async won't bring you any benefit. asyncio can improve performance only if you're running multiple operations that can be parallelized. Usual case is when you're running multiple downloads: asyncio will do some job instead of idle waiting answer from network and through that bring you benefit.

In your case almost everything faces CPU (splitting lines) and disk I/O (reading files). For can be parallelized throught processes only (due to GIL), for second you can use threads (since GIL doesn't affect disk I/O). In both cases you can use asyncio to rule the process with run_in_executor.

Read this link for general explanation and few examples.


Adding time to struct tm Simply put, is this function a correct and safe way to add and/or subtract time to a tm struct (from <time.h>)?

void AddTime(int seconds, tm *date)
{
    date->tm_sec += seconds;
    mktime(date);
}

seconds could be any value, supposedly larger than 60 (or smaller than -60). I'm using mktime to readjust the other values in tm, but I don't know if that's right.

I'm also not taking into account going below 1970 or above 3001 for the year, which I think are the default bounds for mktime to operate. I can check for that elsewhere.

I would add a sanity check on the pointer as well:

void AddTime(int seconds, tm* date) {
    if (date == NULL) return;
    date->tm_sec += seconds;
    mktime(date);
}

But other than that it looks correct.

Reading some documentation on mktime, this appears to be what it was meant for.


Find K biggest numbers in the array I was trying to implement method number 2, from this article.

  Method 2 (Use temporary array) K largest elements from arr[0..n-1]

  Store the first k elements in a temporary array temp[0..k-1].
  Find the smallest element in temp[], let the smallest element be min.
  For each element x in arr[k] to arr[n-1] If x is greater than the
  min then remove min from temp[] and insert x.
  Print final k elements of temp[]

  Time Complexity: O((n-k)*k). If we want the output sorted then
  O((n-k)*k + klogk)

Please comment on the complexity and runtime speed. Can I improve my implementation in that sense? I was trying to get O((n-k)*k).

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{

    //Design an algorithm to find K biggest numbers in the array.
    [TestClass]
    public class KBiggestNumbers
    {
        [TestMethod]
        public void FindKBiggestNumbersTest()
        {
            int[] testArray = new[] { 7, 2, 4, 4, 3, 6, 1, 8, 9, 10, 11 };
            int k = 5;
            int[] result = FindKBiggestNumbers(testArray, k);
            int[] expectedResult = new[] { 7,8,9,10,11 };
            CollectionAssert.AreEqual(expectedResult, result);
        }

        private int[] FindKBiggestNumbers(int[] testArray, int k)
        {
            int[] result = new int[k];
            for (int i = 0; i < testArray.Length; i++)
            {
                //if bigger than the smallest node
                if (testArray[i] <= result[0])
                {
                    continue;
                }
                else
                {
                    //if bigger than all?
                    if (testArray[i] > result[k - 1])
                    {
                        for (int l = 0; l < k - 1; l++)
                        {
                            result[l] = result[l + 1];
                        }
                        result[k - 1] = testArray[i];
                    }
                    else
                    {

                        //Naive way
                        //for (int j = 0; j < k-1; j++)
                        //{
                        //    if (testArray[i] > result[j] && testArray[i] <= result[j + 1])
                        //    {
                        //        for (int l = 0; l < j; l++)
                        //        {
                        //            result[l] = result[l + 1];
                        //        }
                        //        result[j] = testArray[i];
                        //        break;
                        //    }
                        //}

                        //binary search
                        int indexLeft = 0;
                        int indexRight = k-1;

                        int currIndex = 0;
                        //10 20 30 40 50 - > place 33
                        while (indexRight- indexLeft >1)
                        {
                            currIndex = (indexRight + indexLeft)/2;
                            if (testArray[i] >= result[currIndex])
                            {
                                indexLeft = currIndex;
                            }
                            else
                            {
                                indexRight = currIndex;
                            }

                        }

                        for (int l = 0; l < currIndex; l++)
                        {
                            result[l] = result[l + 1];
                        }
                        result[currIndex] = testArray[i];
                    }
                }
            }
            return result;
        }
    }
}

Store the first k elements in a temporary array temp[0..k-1]

You are not doing that

  Find the smallest element in temp[], let the smallest element be min

You are not doing that

  For each element x in arr[k] to arr[n-1]...

You are starting on 0 because you skipped step 1

Nothing in there about a binary search
Not less operations the with the shifts

This

if (testArray[i] <= result[0])
{
    continue;
}
else
{

Can be

if (testArray[i] > result[0])
{

Other than that looks good

Just following what I think are the instructions
It is \$\mathcal{O}(n \times k)\$ as the first k elements are not free

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
    int[] result = new int[k];
    int indexMin = 0;
    result[indexMin] = testArray[0];
    int min = result[indexMin];

    for (int i = 1; i < testArray.Length; i++)
    {
        if(i < k)
        {
            result[i] = testArray[i];
            if (result[i] < min)
            {
                min = result[i];
                indexMin = i;
            }
        }
        else if (testArray[i] > min)
        {
            min = testArray[i];
            result[indexMin] = min;
            for (int r = 0; r < k; r++)
            {
                if (result[r] < min)
                {
                    min = result[r];
                    indexMin = r;
                }
            }
        }
    }
    return result;
}


Second largest element of a large array Given an array which contains integers (may contain thousands of elements), you have to write a program to find the second largest element of the group.

int secondmax(int array[],int n)
{
 int max;
 int secondmax;
 assert(n>1);
 max=array[0]>array[1] ? array[0] : array[1];
 secondmax=array[0]>array[1] ? array[1] : array[0];
 for(j=2;j<n;j++)
 {
  if(array[j]> max) { secondmax=max;max=array[j];}
  else if (array[j] > secondmax) { secondmax=array[j];}
 }
 return secondmax;
}

Is code correct?
Is usage of assert okay or should it be avoided?

There's no need to check if array[0] > array[1] twice.

if (array[0] > array[1]) {
    max = array[0];
    secondmax = array[1];
} else {
    secondmax = array[0];
    max = array[1];
}

But if you really want to use the ternary operator here (? :), at least move them to the declarations, and move the assertion above.

It's a micro-optimization, but I would assign array[j] to a temporary variable inside the loop since it may potentially be accessed four times. Plus it is more readable

for(j=2;j<n;j++)
{
    int candidate = array[j];
    if (candidate > max) {
        secondmax = max;
        max = candidate;
    }
    else if (candidate > secondmax) {
        secondmax = candidate;
    }
}

Gotta say that I'm not a big fan of a single space for indentation or putting multiple statements on a single line. I've worked at a company where we used two before, and that was confusing. One is asking for trouble. And with 24+ inch monitors common, there's no need to be so frugal with your vertical screen real estate! :)

The assertion seems like a good choice, though you might consider returning a signaling value instead. It really depends on what callers will expect, and make sure you document your choice.


Employer registration I have two registration paths in my app. They are very similar and I am curious if I should simplify 4 associated actions down into two actions that handle the same amount of work.

Here are my controller actions:

def employer_registration
  @employer_signup = EmployerSignup.new
end

def employee_registration
  @employee_signup = EmployeeSignup.new
end

def create_employee
  @employee_signup = EmployeeSignup.new(params[:employee_signup])

  if @employee_signup.save
    sign_in @employee_signup.user
    redirect_to root_path, notice: 'You signed up successfully'
  else
    render action: :employee_registration
  end
end

def create_employer
  @employer_signup = EmployerSignup.new(params[:employer_signup])

  if @employer_signup.save
    sign_in @employer_signup.user
    redirect_to root_path, notice: 'You signed up successfully.'
  else
    render action: :employer_registration
  end
end

As you can see, the only difference between the two registration paths are the form object that's being used, EmployeeSignup and EmployerSignup respectively.  As you would expect, views are actually very similar too, they just display a form that's appropriate to each form object.

I have full test suits for each of these registration paths and it seems like an exceptionally large amount of duplication.

Each path handles something different, one handles employees registering, the other handles employers - so I'm tempted to leave them separate.  But, if thought of another way, they both handle one idea: User Registration.  In that case I feel it would be wiser to reconcile the different paths into one path and have a simple parameter control which form object is being used depending on the desired path.

Is my code acceptable as is or would it be more reasonable to refactor it down into one 'new' action and one 'create' action?

Your setup is going to eventually be working around Rails configurations, which are built for the canonical index, new, create, show, edit, update, delete.

Rails does resource routing for this very reason (read more in the Rails Guide on Routing). It's also very in-line with HTTP verb standards and will make turning this into a JSON API trivial, should you need one.

Since your Employer and Employee are separate domain objects, I would make them separate controllers. This leaves some nice future options for other actions when you need them like edit and destroy.

class EmployerController < ApplicationController
  def new
    @employer_signup = EmployerSignup.new
  end

  def create
    @employer_signup = EmployerSignup.new(params[:employer_signup])

    if @employer_signup.save
      sign_in @employer_signup.user
      redirect_to root_path, notice: 'You signed up successfully.'
    else
      render action: :employer_registration
    end
  end
end

class EmployeeController < ApplicationController
  def new
    @employee_signup = EmployeeSignup.new
  end

  def create
    @employee_signup = EmployeeSignup.new(params[:employee_signup])

    if @employee_signup.save
      sign_in @employee_signup.user
      redirect_to root_path, notice: 'You signed up successfully'
    else
      render action: :employee_registration
    end
  end
end


Monadic list for a more functional approach to C# I am learning about monadic structures and have created a sort of monad list that implements the map and binding "operators" (or technically methods) in C#.

I understand that Linq already exists and would solve many of the problems that my solution solves (I am in fact already using linq to help in parts of my code) and that lists are technically already monads. However this is still a learning experience for me and so I want to make sure I have the right idea.

class ListMonad<T> : IEnumerable<T>
{
    private readonly List<T> items;
    private List<T> Items => items;

    public ListMonad(List<T> value)
    {
        this.items = new List<T>(value);
    }

    public ListMonad()
    {
        items = new List<T> { };
    }

    public ListMonad<TO> Bind<TO>(Func<T, ListMonad<TO>> func)
    {
        var lists = new List<ListMonad<TO>>();
        foreach(var el in Items)
            lists.Add(func(el));

        return new ListMonad<TO>(lists.SelectMany(x => x.Items).ToList());
    }

    public ListMonad<TO> Map<TO>(Func<T, TO> func)
    {
        var result = new ListMonad<TO>();
        foreach(var item in Items)
            result.Items.Add(func(item));

        return result;
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        foreach(var item in Items)
            yield return item;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<T>)this).GetEnumerator();
    }

    public T this[int index] => Items[index];
}

Use:

class Program
{
    static void Main(string[] args)
    {
        var listMonad = new ListMonad<int>(new List<int> { 1, 2, 3, 4, 5, 6, 7 });

        var doubledAndSquared = Compose((int x) => x * x, (int x) => x * 2);
        Func<int, ListMonad<int>> zeroSeparated = x => new ListMonad<int>(new List<int> { x, 0 });

        listMonad = listMonad
            .Bind(zeroSeparated)
            .Map(doubledAndSquared);

        foreach(var item in listMonad)
            Console.Write(item + ", ");
    }

    static Func<V, U> Compose<T, U, V>(Func<T, U> func1, Func<V, T> func2) =>
        (V x) => func1(func2(x));
}

Just a few points that I've noticed:

Readonly property can be declared directly like this:

private List<T> Items { get; }

It is not clear if this class is intended to be immutable. The Items is not exposed directly, and its backing field is marked with readonly. However, the indexer is exposed. In case it is, you should use ReadOnlyCollection<T> as the container. If not, an T[] would allow you to mutate its element, but prevents you from adding/removing item.
ctor argument value should pluralized.
An overload of ctor that takes params T[] values would be a nice addition, enabling this type of code: new ListMonad<int>(1, 2, 3)
Another ctor overload that support IEnumerable<T> would be great too, which will allow you to write this:

// this likely defeats the purpose of this class?
public ListMonad<TO> Map<TO>(Func<T, TO> func) => new ListMonad<TO>(this.Select(func));
public ListMonad<TO> Bind<TO>(Func<T, ListMonad<TO>> func) => new ListMonad<TO>(this.SelectMany(func));

In the Bind method, you can use AddRange to avoid creating a nested list:

public ListMonad<TO> Bind<TO>(Func<T, ListMonad<TO>> func)
{
    var results = new List<TO>();
    foreach (var element in this)
        results.AddRange(func(element));

    return new ListMonad<TO>(results);
}

The argument order of Compose method seems weird, although it may just be my personal preferences. I would suggest to put the inner-most selector first, and moving toward outside, since this is how we normally solves equations:

public static Func<TInput, TResult> Compose<TInput, T2, TResult>(Func<TInput, T2> func1, Func<T2, TResult> func2)
{
    return x => func2(func1(x));
}

Compose can also be placed in a generic-ally typed static class to avoid having to explicitly mentioning the generic type multiple times:

public static class FuncHelper<T>
{
    // usage: FuncHelper<int>.Compose(x => x * 2, x => x * x)
    public static Func<T, TResult> Compose<T2, TResult>(Func<T, T2> func1, Func<T2, TResult> func2)
    {
        return x => func2(func1(x));
    }
    // and, you can chain even more function
    public static Func<T, TResult> Compose<T2, T3, TResult>(Func<T, T2> func1, Func<T2, T3> func2, Func<T3, TResult> func3)
    {
        return x => func3(func2(func1(x)));
    }
    // and, so on ...

    // or, you can chain as long as you want, if the input, intermediate and result types are all the same
    // usage: FuncHelper<int>.Compose(x => x + 1, x => x * 2, x => x + 3, x => x * 4, ...)
    public static Func<T, T> Compose(params Func<T, T>[] funcs)
    {
        return x => funcs.Aggregate(x, (y, f) => f(y));
    }
}


Representing a queue as a procedure with local state From SICP:

  Exercise 3.22.  Instead of
  representing a queue as a pair of
  pointers, we can build a queue as a
  procedure with local state. The local
  state will consist of pointers to the
  beginning and the end of an ordinary
  list. Thus, the make-queue procedure
  will have the form

(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <definitions of internal procedures>
    (define (dispatch m) ...)
    dispatch))

  Complete the definition of make-queue
  and provide implementations of the
  queue operations using this
  representation.

I wrote the following solution:

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (set-front-ptr! ptr) (set! front-ptr ptr))
    (define (set-rear-ptr! ptr) (set! rear-ptr ptr))
    (define (empty?) (null? front-ptr))
    (define (front-queue)
      (if (empty?)
          (error "FRONT called with an empty queue" front-ptr)
          (car front-ptr)))
    (define (insert! item)
      (let ((new-pair (cons item '())))
        (cond ((empty?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair)
               dispatch)
              (else
               (set-cdr! rear-ptr new-pair)
               (set-rear-ptr! new-pair)
               dispatch))))
    (define (delete!)
      (cond ((empty?)
             (error "DELETE! called with an empty queue" first-ptr))
            (else
             (set-front-ptr! (cdr front-ptr))))
      dispatch)
    (define (print) front-ptr)
    (define (dispatch m)
      (cond ((eq? m 'insert!) insert!)
            ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'empty?) empty?)
            ((eq? m 'delete!) delete!)
            ((eq? m 'print) print)
            (else (error "No such procedure: dispatch" m))))
    dispatch))

(define q1 (make-queue))
((((q1 'insert!) 'a) 'print))
((((q1 'insert!) 'b) 'print))
((((q1 'delete!)) 'print))
((((q1 'delete!)) 'print))

How can it be improved?

You did not provide implementations of the queue operations using this representation. In SICP this usually refers to syntactic sugar to make working with a data structure less awkward, e.g.
(define (queue-insert! q item)
    ((q 'insert!) item) )

Also I would prefer different operation names, e.g.
append! instead of insert!
front instead of front-ptr
...


A simple Java class for implementing code stop watches (The next iteration: A simple Java class for implementing code stop watches - follow-up)

Here is my attempt at more convenient benchmarking (yes, this time I am aware of JVM warmup, etc.), and it looks like this:

package net.coderodde.stopwatch;

public final class StopWatch {

    private long earliestMillis = Long.MAX_VALUE;

    public StopWatch() {
        this(System.currentTimeMillis());
    }

    public StopWatch(long earliestMillis) {
        this.earliestMillis = earliestMillis;
    }

    public void push(long earliestMillis) {
        if (earliestMillis < this.earliestMillis) {
            throw new IllegalArgumentException("Cannot go back in time.");
        }

        this.earliestMillis = earliestMillis;
    }

    public long pop() {
        return System.currentTimeMillis() - earliestMillis;
    }

    public long popAndPush() {
        long ret = pop();
        this.earliestMillis = System.currentTimeMillis();
        return ret;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("(")
                     .append(System.currentTimeMillis() - earliestMillis)
                     .append(" starting from ")
                     .append(earliestMillis)
                     .append(" ms -> ")
                     .append(System.currentTimeMillis())
                     .append(")");

        return stringBuilder.toString();
    }

    public static void main(String[] args) throws InterruptedException {
        StopWatch sw = new StopWatch();

        Thread.sleep(3_000L);
        System.out.println(sw.pop());
        System.out.println(sw);

        Thread.sleep(2_000L);
        System.out.println(sw.pop());

        sw.popAndPush();
        Thread.sleep(1_230L);
        System.out.println(sw);
    }
}

Is there more reasonable/extensive approach to this?

public final class StopWatch {

    private long earliestMillis = Long.MAX_VALUE;

There is no reason to initialize this field at this point. Both constructors will overwrite it immediately.

    public StopWatch() {
        this(System.currentTimeMillis());
    }

    public StopWatch(long earliestMillis) {
        this.earliestMillis = earliestMillis;
    }

There should be no reason for the user to provide their own initial start time. The only reason could be to use an entirely different clock for testing this code. For that case, you should use a MillisProvider instead of calling System.currentTimeMillis directly. As of now, you have a wild mixture of calling currentTimeMillis and accepting caller-provided timestamps, which can easily lead to confusion.

    public void push(long earliestMillis) {

Again, I don't see any reason not to hard-code System.currentTimeMillis here.

        if (earliestMillis < this.earliestMillis) {
            throw new IllegalArgumentException("Cannot go back in time.");
        }

When you measure code for performance, you usually don't expect additional exceptions to be thrown. Changing the system clock backwards should not happen anyway, but still this code should deal a little softer with this situation by just ignoring it.

        this.earliestMillis = earliestMillis;
    }

    public long pop() {
        return System.currentTimeMillis() - earliestMillis;
    }

    public long popAndPush() {
        long ret = pop();
        this.earliestMillis = System.currentTimeMillis();
        return ret;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("(")
                     .append(System.currentTimeMillis() - earliestMillis)
                     .append(" starting from ")
                     .append(earliestMillis)
                     .append(" ms -> ")
                     .append(System.currentTimeMillis())
                     .append(")");

        return stringBuilder.toString();
    }

Using a StringBuilder here is unnecessary. It is only needed if you have some parts that are added conditionally to the string. Just use plain string concatenation, which is far easier to read. Alternatively, since the toString method is probably not called in the performance-critial part, it's probably ok to use String.format here, to separate the general format of the message from the parameters.

Oh, I just saw that toString calls currentTimeMillis. That's wrong. It's even wronger to call it twice in a row (and expecting both calls to return the same timestamp). Measuring the time should be as fast and light-weight as possible. Building a nice presentation out of the raw measurement values should be clearly separated from the measurement.

To increase the precision of the measurement, you should determine how long it takes to call currentTimeMillis and subtract that from the reported durations.

    public static void main(String[] args) throws InterruptedException {
        StopWatch sw = new StopWatch();

        Thread.sleep(3_000L);
        System.out.println(sw.pop());
        System.out.println(sw);

        Thread.sleep(2_000L);
        System.out.println(sw.pop());

        sw.popAndPush();
        Thread.sleep(1_230L);
        System.out.println(sw);
    }
}

As danielspaniol already said in a comment, having a stopwatch with buttons labelled "push" and "pop" feels strange. Looking at Wikipedia, the second image, your methods should rather be called start, stop, reset, lap, split, recall, pause.


Asynchronous lightweight JSON API I am writing a lightweight JSON API, and I come from a PHP background, so I have some questions/reviews about async node.js code.

This is my code so far:

main.js

var http = require('http');
var api = require('./api.js');

api.addRoute({
    'method': 'POST',
    'url': '/users',
    'input': {
        'fullName': {
            type: String,
            required: true,
            min: 2,
            max: 64
        },
        'email': {
            type: String,
            required: true,
            match: /^(.*)@(.*).(.*)$/,
            min: 2,
            max: 64
        },
        'password': {
            type: String,
            required: true,
            min: 2,
            max: 64
        }
    },
    'description': 'Create an user account.'
});

var server = http.createServer(api.handleRequest).listen(3000);

api.js

var api = exports;
var routes = [];

var postMaxSize = 1000;
var postTotalReceived = 0;

function getInput(req, res, callback){
    if(req.method === 'POST' || req.method === 'PUT'){
        var queryString = require('querystring');
        var inputData = '';

        req.on('data', function(data){
            if(data.length < postMaxSize && postTotalReceived < postMaxSize){
                inputData += data;
                postTotalReceived += data.length;
            } else {
                res.statusCode = 413;
                res.end('max-size');
            }
        });

        req.on('end', function(){
            callback(queryString.parse(inputData));
        });
    } else {
        callback(false);
    }
};

api.addRoute = function(route){
    routes.push(route);
}

function getRoute(req, res, callback){
    for(var i = 0; i < routes.length; i++){
        if(routes[i]['method'] === req.method){ // If the request method matches.
            if(typeof(routes[i]['url'] === 'string') && routes[i]['url'] === req.url){
                callback(routes[i]);
            }
        } else {
            var matches = req.url.match(routes[i]['url']);

            if(matches){
                req.urlParameters = [];

                for(var j = 1; j < matches.length; j++){ // Skip the first match, which is the url.
                    req.urlParameters.push(matches[j]);
                }

                callback(routes[i]);
            }
        }
    }
};

api.handleRequest = function(req, res){
    res.setHeader('Content-Type', 'application/json'); // Always return JSON since this is a rest JSON api.

    getInput(req, res, function(inputData){
        getRoute(req, res, function(route){
            if(route){

                // Do something.

                res.end();
            } else {
                res.statusCode = 404;
                res.end('not-found');
            }
        });
    });
};

I am just wondering, Node.js sells itself with "Non-blocking", but if on each request I have to do a regex to match the route for example:

/^\/users\/(.*)\//$ -> /users/mike

The regex has to be executed since Node.js is single threaded.  How does it do Regex non blocking? The CPU has to execute the Regex, right?

About the code, my idea was:

I don't want to use any framework like express, since routing etc. can be done
much more lightweight and I can customize everything, full control etc.
Each route has automatic input validation, which can be combined with auto generating documentation, for example if a user would request 'GET /' he would get a list of all the routes fully documented with required parameters, optional parameters, description, authentication requirements etc.

Please take a look at the api.handleRequest function.  Am I correctly using callbacks at getInput and getRoute? Or should I only use callbacks at I/O, db calls etc?

The API I am about the build is basically a simple wrapper around Amazon Web Services, MongoDb and maybe later Redis or some other message queue.

From a once over:

Not sure why you are not parsing the querystring for GET requests? It seems wrong
if(data.length < postMaxSize && postTotalReceived < postMaxSize) could be if(data.length + postTotalReceived < postMaxSize)
Not sure what happens in your code after setting the 413, it seems you have some loose ends there. You could consider redefining callback to function(){}
I would not store the routes as an array, the lookup time is too slow in my mind, instead I would store the routes in an object like this:

api.addRoute = function(route){
  routes[route.method][route.url] = route;
}

I read your code several times, it seems as if even if the method of a route does not match you will still execute the route if the url matches through a regex. If so, then that is completely wrong.


An implementation of parallel workers in Ruby Much in the spirit of this question, I have implemented a simple class for parallel workers and wanted to get some feedback on it. Can I make the code even more concise or readable? Are there any hidden problems that I should be aware of?

Worker class

class Worker

    def initialize queue
        @queue = queue

        # Set the "idle state" (returned by the idle? method)
        # and a mutex for accessing it
        @idle_state = false
        @idle_mutex = Mutex.new

        # Set the "exit state" (returned by the done? method)
        # and a mutex for accessing it
        @exit_state = false
        @exit_mutex = Mutex.new

        poll
    end

    # Poll a queue for Proc objects to process
    def poll
        @thread = Thread.new do
            loop do
                while @queue.empty?
                    set_idle true
                    exit 0 if done?
                    sleep 1
                end
                set_idle false
                job = @queue.pop
                job.call
            end
        end
    end

    def done?
        @exit_mutex.synchronize { @exit_state }
    end

    def shut_down
        @exit_mutex.synchronize { @exit_state = true }
        @thread.join
    end

    def idle?
        @idle_mutex.synchronize { @idle_state }
    end

    def set_idle state
        @idle_mutex.synchronize { @idle_state = state }
    end

end

Usage

# Set up a job queue
queue = Queue.new

# Spin up a few workers
workers = []
(1..5).each do
    workers << Worker.new(queue)
end

# Add some jobs to the queue
(1..50).each do |i|
    queue << Proc.new { $stdout.print "Job ##{i}\n" }
end

# Shut down each of the workers once the queue is empty
sleep 0.1 until queue.empty?
workers.each { |worker| worker.shut_down }

References:

Correctness of a minimal parallel workers queue in Ruby

Where not to lock
I'm not sure why you decided to lock on @exit_state and @idle_state, as they don't seem to have any potential to cause any race condition (except for maybe when the manager calls thread.shut_down, and even then - all that would happen is that you will 'lose' a round of one second - hardly catastrophic).

Where to lock
When you want to concurrently work on a queue - you should synchronize your work with the queue (in this case @queue.empty? and @queue.pop), which you don't do...

How to lock
You should also note the @queue.pop is implicitly @queue.pop(false) which means that if the queue is empty, it will block until a new message arrives, which is probably not what you want, since you can't be sure that it is not empty (between while @queue.empty? to job = @queue.pop another worker might have 'hijacked' your message).

Since Queue is thread-safe, you could write your worker like this:

class Worker

  def initialize(queue)
    @thread = Thread.new { poll(queue) }
  end

  def poll(queue)
    until done?
      begin
        queue.pop(true).call
      rescue ThreadError
        # queue was empty
        sleep 1
      end
    end
    exit 0
  end

  def done?
    @done
  end

  def shut_down
    @done = true
  end
end


Typelist with extractor The purpose of the code is to store arbitrary number of types. The type can be extracted from it using Extract template, which uses template recursion to get the needed type. There will be compilation error if user will try to get out of bounds. I think it supports both fully defined types and only declared types.

In which ways the code below can be improved?

#ifndef TYPELIST_H
#define TYPELIST_H

#include <cstddef>

struct NullType;

template <typename Head, typename ... Tail>
struct TypeList
{
    using head = Head;
    using tail = typename TypeList<Tail...>;
};

template <typename Single>
struct TypeList <Single>
{
    using head = Single;
    using tail = NullType;
};

template <size_t index, typename typelist>
struct Extract
{
    using result = typename Extract<index - 1, typename typelist::tail>::result;
};

template <typename typelist>
struct Extract <0, typelist>
{
    using result = typename typelist::head;
};

#endif

I doubted about whether or not make NullType declaration only. In my opinion, leaving definition better says "don't use this" than empty definition.

I was thinking about SFINAE on out of range indexes, but thought the behavior will be surprising.

My another concern was creating objects of such classes. I couldn't figure out the way to restrict users from creating the objects. The only thing that came to mind is deleting all constructors, but it is strange, thus I decided to refrain from deleting constructors.

Example usage:

#include "typelist.h"
#include <typeinfo>
#include <iostream>

int main()
{
    using MyList = TypeList<int, char, bool>;
    using extracted = Extract<2, MyList>::result;

    std::cout << (typeid(extracted) == typeid(bool));
}

Naming

Templates depend on a consistent naming scheme for static polymorphism.

We can observe such consistent naming throughout the type traits offered by the standard library (from std::aligned_storage to std::add_pointer); the two most common names being:

A type alias member when the type trait produces a type result.
A value static data member to represent constexpr values.

This means that naming your extracted type alias as result is non-standard and breaks with any templates that assume the same naming convention from the standard library.

What is a type list?

There doesn't seem to be a specific purpose for having a type list that is defined in terms of a head and tail when variadic templates can easily represent what a type list is. Thus, we can simply define a type list as:

template <class... Types>
class type_list {};

What is extracting from a type list?

We can define a more general extraction template to extract from a variadic template.

template <std::size_t idx, class... Types>
class extract
{
    static_assert( idx < sizeof...( Types ), "index out of bounds" );

    template <std::size_t i, std::size_t n, class... Rest>
    struct extract_impl;

    template <std::size_t i, std::size_t n, class T, class... Rest>
    struct extract_impl<i, n, T, Rest...>
    {
        using type = typename extract_impl<i + 1, n, Rest...>::type;
    };

    template <std::size_t n, class T, class... Rest>
    struct extract_impl<n, n, T, Rest...>
    {
        using type = T;
    };

public:
    using type = typename extract_impl<0, idx, Types...>::type;
};

Now that we have that, extracting from our type list is a simple subset operation based on the generalized template for extraction:

template <std::size_t idx, class TypeList>
struct type_list_extract;

template <std::size_t idx, template <class...> class TypeList, class... Types>
struct type_list_extract<idx, TypeList<Types...>>
{
    using type = typename extract<idx, Types...>::type;
};

For which we can provide a convenience alias:

template <std::size_t idx, class TypeList>
using type_list_extract_t = typename type_list_extract<idx, TypeList>::type;

That we can now use as follows:

int main()
{
    using list_t = type_list<char, bool, void>;

    static_assert( std::is_same<char, type_list_extract_t<0, list_t>>::value, "!" );
    static_assert( std::is_same<bool, type_list_extract_t<1, list_t>>::value, "!" );
    static_assert( std::is_same<void, type_list_extract_t<2, list_t>>::value, "!" );
    //type_list_extract_t<3, list_t>; // static_assert fails: index out of bounds
}

Final words

There are non-recursive ways to implement extraction (among other operations); they will most likely (possibly definitely!) require integer/index sequences. You can have a look at my answer for this question to see a non-recursive integer sequence implementation.

There are many more cool tricks to do with templates. Look on this very site or Stack Overflow!


Concatenate several CSV files in a single dataframe I have currently 600 CSV files (and this number will grow) of 50K lines each i would like to put in one single dataframe.
I did this, it works well and it takes 3 minutes :
colNames = ['COLUMN_A', 'COLUMN_B',...,'COLUMN_Z']
folder = 'PATH_TO_FOLDER'

# Dictionnary of type for each column of the csv which is not string
dictTypes = {'COLUMN_B' : bool,'COLUMN_D' :int, ... ,'COLUMN_Y':float}

try:
   # Get all the column names, if it's not in the dict of type, it's a string and we add it to the dict
   dictTypes.update({col: str for col in colNames if col not in dictTypes})
except:
    print('Problem with the column names.')

# Function allowing to parse the dates from string to date, we put in the read_csv method
cache = {}
def cached_date_parser(s):
    if s in cache:
        return cache[s]
    dt = pd.to_datetime(s, format='%Y-%m-%d', errors="coerce")
    cache[s] = dt
    return dt

# Concatenate each df in finalData
allFiles = glob.glob(os.path.join(folder, "*.csv"))
finalData = pd.DataFrame()
finalData = pd.concat([pd.read_csv(file, index_col=False, dtype=dictTypes, parse_dates=[6,14],
                    date_parser=cached_date_parser) for file in allFiles ], ignore_index=True)

It takes one minute less without the parsing date thing. So i was wondering if i could improve the speed or it was a standard amount of time regarding the number of files. Thanks !

Here is my untested feedback on your code. Some remarks:

Encapsulate the functionality as a named function. I assumed folder_path as the main "variant" your calling code might want to vary, but your use case might "call" for a different first argument.
Use PEP8 recommandations for variable names.
Comb/separate the different concerns within the function:

gather input files
handle column types
read CSVs and parse dates

Depending on how much each of those concerns grows in size over time, multiple separate functions could organically grow out of these separate paragraphs, ultimately leading to a whole utility package or class (depending on how much "instance" configuration you would need to preserve, moving the column_names and dtypes parameters to object attributes of a class XyzCsvReader's __init__ method.)
Concerning the date parsing: probably the bottleneck is not caused by caching or not, but how often you invoke the heavy machinery behind pd.to_datetime. My guess is that only calling it once in the end, but with infer_datetime_format enabled will be much faster than calling it once per row (even with your manual cache).

import glob
import os
import pandas as pd

def read_xyz_csv_folder(
        folder_path,
        column_names=None,
        dtypes=None):
    all_files = glob.glob(os.path.join(folder_path, "*.csv"))

    if column_names is None:
        column_names = [
            'COLUMN_A',
            'COLUMN_B',  # ...
            'COLUMN_Z']
    if dtypes is None:
        dtypes = {
            'COLUMN_B': bool,
            'COLUMN_D': int,
            'COLUMN_Y': float}
    dtypes.update({col: str for col in column_names
                   if col not in dtypes})

    result =  pd.concat((
            pd.read_csv(file, index_col=False, dtype=dtypes)
            for file in all_files),
        ignore_index=True)

    # untested pseudo-code, but idea: call to_datetime only once
    result['date'] = pd.to_datetime(
        result[[6, 14]],
        infer_datetime_format=True,
        errors='coerce')

    return result

# use as
read_xyz_csv_folder('PATH_TO_FOLDER')

Edit: as suggested by user FMc in their comment, switch from a list comprehension to a generator expression within pd.concat to not create an unneeded list.


Finding unique triplets adding up to 0 I am working on a problem "3Sum", in which, given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0. I must find all unique triplets in the array which gives the sum of zero.

I wrote my naive implementation which was \$O(n^3)\$ since it was checking for every possible combination:

public List<List<Integer>> threeSum(int[] num) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();

        if(num.length<3) return res;

       Arrays.sort(num);

        for(int i=0;i<num.length;i++)
        {
         if(num[i]>0) break;
            for(int j=i+1;j<num.length;j++)
            {
                if(num[i]+num[j]>0 && num[j]>0) break;
                for(int k=j+1;k<num.length;k++)
                {
                    if(num[i]+num[j]+num[k]==0)
                      {
                          List<Integer> curr=new ArrayList<Integer>();
                          curr.add(num[i]);
                          curr.add(num[j]);
                          curr.add(num[k]);
                          res.add(curr);
                      }
                      while(k+1<num.length && num[k]==num[k+1]) k++;
                }
                 while(j+1<num.length && num[j]==num[j+1]) j++;
            }
            while(i+1<num.length && num[i]==num[i+1]) i++;
        }
        return res;

}

However, I am looking for a solution which is better than \$O(n^2)\$. Rather, is there a way I can bring the time complexity of my solution to \$O(n^2)\$ by removing any of the loops?

I don't have a solution better than yours (you can google for java 3Sum O(n^2) to find some examples), but I have some small comments on your code:

While loops

I would remove all the while loops. They make your code harder to read and don't really speed it up (in my tests, they actually slowed it down).

Minor performance improvements

array access costs time, if you save num[i], etc in local variables, it will slightly speed your code up.
move quicker checks to the beginning: nj > 0 && ni + nj > 0 instead of ni + nj > 0 && nj > 0 should be quicker, but only marginally so.

Style

use correct indentation
in Java, the opening curly bracket commonly goes on the same line
use curly brackets, even for one-line statements
use more spaces (for example while(k+1<num.length && num[k]==num[k+1]) would be while (k + 1 < num.length && num[k] == num[k + 1])


Saving User Preferences I have the following given code after some refactoring:

public static void storePreferences() {
    try {
        Preferences.userRoot().exportSubtree(new FileOutputStream(ReleaseInfo.getAppFolder() + File.separator + SETTINGSFILENAME));
    } catch (IOException e) {
        e.printStackTrace();
    } catch (BackingStoreException e) {
        e.printStackTrace();
    }
}

Now I wonder - should I explicitly close the FileOutputStream or the JVM takes care for doing so? I have looked at this question on the same topic, where it is said that it is not a good practice to rely on the garbage collector, but still I need a bit more confirmation (therefore this question). I have changed the above code to:

public static void storePreferences() {
    FileOutputStream fos = null;

    try {
        fos = new FileOutputStream(ReleaseInfo.getAppFolder() + File.separator + SETTINGSFILENAME);
        Preferences.userRoot().exportSubtree(fos);
    } catch (IOException | BackingStoreException e) {
        e.printStackTrace();
    } finally {
        try {
            fos.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Here I close the stream manually, so which would be the better alternative and do the performed changes really bring something to the table?

Any other remarks?

The better alternative is the second alternative, because the first alternative may only write the data to disk when the Garbage Collector clears up the stream. The file will remain open for all that time too, leading to long holds on file handles in the OS.

i.e. the first one may produce unexpected results.

The second alternative is an improvement, but you should consider using a "try with resources" block, which has been around for the past 6 years in Java 7 and 8... The try-with-resources is a far more elegant way to approach this problem, and it makes the exception handling "trivial"...

public static void storePreferences() {
    File prefs = new File(new File(ReleaseInfo.getAppFolder()), SETTINGSFILENAME);
    try (OutputStream fos = new FileOutputStream(prefs)) {
        Preferences.userRoot().exportSubtree(fos);
    } catch (IOException | BackingStoreException e) {
        e.printStackTrace();
    }
}

Note that I used the more convenient 2-argument File constructor instead of the constant File.separator

Further, I would suggest getting a better-performing new NIO2 functions, and wrap the resulting OutputStream with a buffer:

public static void storePreferences() {
    Path prefs = Paths.get(ReleaseInfo.getAppFolder(), SETTINGSFILENAME);
    try (OutputStream fos = new BufferedOutputStream(Files.newOutputStream(prefs))) {
        Preferences.userRoot().exportSubtree(fos);
    } catch (IOException | BackingStoreException e) {
        e.printStackTrace();
    }
}


Adding to an index of authors I'm new to SQLite but have programmed in BASIC (and other languages) for pushing 50 years.

Given the sample code extract, please offer suggestions for improvement:

    Sub addAuthor(ByVal authorlnf As String, ByVal authorfnf As String)
        Dim objConn As SQLiteConnection
        Dim objCommand As SQLiteCommand
        objConn = New SQLiteConnection(CONNECTION_STR)
        objConn.Open()
        objCommand = objConn.CreateCommand()
        objCommand.CommandText = "INSERT INTO [author] ([authorlnf], [authorfnf]) VALUES ('" & authorlnf & "', '" & authorfnf & "');"
        Try
            objCommand.ExecuteNonQuery()
        Catch ex As InvalidOperationException
            MessageBox.Show("An error has occurred: " & ex.Message)
        Catch ex As SQLiteException
            MessageBox.Show("An error has occurred: " & ex.Message)
        End Try

        If Not IsNothing(objConn) Then objConn.Close()

End Sub

This is an index of book authors and this routine will be called several thousand times. I'm replacing VB dictionaries as memory is becoming a limiting factor.

I have never used SQLite either, but something is jumping at me in your code: the addAuthor() procedure owns the connection, which means if you're calling it 10,000 times in a loop you're going to be opening and closing 10,000 connections, which is ..well to be honest, nuts.

Looking at the method's signature:

Sub addAuthor(ByVal authorlnf As String, ByVal authorfnf As String)

Naming nitpicks

I believe PascalCasing is the convention for naming just about everything in VB, but what really matters is consistency. Try to be consistent with the language you're using - the VB API uses PascalCasing for methods.
Names authorlnf and authorfnf could just as well be named authorwtf - they tell the reader it's something about an author, but to find out what exactly, one has to dig deeper than the method's signature. Avoid disemvoweling at all costs - it ruins reading even the best-written code base.
well now that I think of it I'd say authorlnf would be author's last name and authorfnf would be author's first name.. still scratching my head as for what the last f is standing for...

Serious stuff

What happens when authorlnf contains the value "Robert'); DROP TABLE author;--"?

credits: xkcd/Randall Munroe

Your insert fails and the author table gets dropped (if your user has the permissions and there's no FK constraint involved, but that's not the point). This is called SQL Injection and, depending on where, how and by whom your code is being used, it may or may not be a concern - nevertheless, it's a flaw in your design.

You could write yourself some parameter-cleansing function and think you're protected, but that would leave you the burden of proving that your cleansing function is undeniably safe. And you must never forget to call it!

Or you could use parameters, that take the value of the user input. That's much harder to mess with!

Connection ownership

I think the AddAuthor() method shouldn't create (/own) the connection it's using. Consider this:

Sub AddAuthor(ByVal connection As SQLiteConnection, ByVal authorlnf As String, ByVal authorfnf As String)

All of a sudden, opening, closing and disposing the connection is no longer a concern here: you put that burden on the caller, where you're looping 10,000 times - so you open up the connection, create and execute 10,000 commands inside AddAuthor(), and then close the connection. That puts the lite in SQLite, no?

I'll only add that you're catching known & relevant exceptions and letting unknown ones bubble up, and that's excellent. The only thing is, as @Malachi correctly pointed out, you should be closing the connection in a Finally block, but if your method doesn't own the connection, that's moot. However I believe a Command would implement IDisposable, so it should be .Dispose()'d.


A traits class for (compound) pointers - beyond what std::pointer_traits offers This is a percolation of ideas which originated this SO question:

Compound pointer traits class with method generalizing make_shared and make_unique?

The std::pointer_traits class offers the following traits, basically:

Types: pointer, element_type, difference_type, and rebind (given a pointer-like type for pointing to T, get a pointer-like type for pointing to U)

Static methods:

to_address - get the plain vanilla T* from some fancy pointer-to-T-like class, if possible
pointer_to - opposite of to_address. This is a fishy method, since it's not clear what it means with respect to resource ownership.

I think it's useful to add at least two methods - for creating a pointer to a new object / array of objects, a-la std::make_shared and std::make_unique, and one for releasing ownership + getting the raw address. Here's my implementation:

#pragma once
#ifndef EXTRA_POINTER_TRAITS_HPP_
#define EXTRA_POINTER_TRAITS_HPP_

#include <memory>

template <typename Ptr>
struct extra_pointer_traits;

template <typename T>
struct extra_pointer_traits<T*>
{
    using ptr_type = T*;
    using element_type = T;

    static ptr_type make(size_t count) { return new T[count]; }
    static ptr_type make()             { return new T;        }
};

template <typename T>
struct extra_pointer_traits<T[]>
{
    using ptr_type = T[];
    using element_type = T;

    static T* make(size_t count) { return new T[count]; }
    static T* make()             { return new T;        }
};

template <typename T, class Deleter>
struct extra_pointer_traits<std::unique_ptr<T[], Deleter>>
{
    using ptr_type = std::unique_ptr<T[], Deleter>;
    using element_type = T;

    static T* release(ptr_type& ptr) { return ptr.release(); }
    static std::unique_ptr<T[], Deleter> make(size_t count)
    {
        return std::make_unique<T[]>(count);
    }
};

template <typename T, class Deleter>
struct extra_pointer_traits<std::unique_ptr<T, Deleter>>
{
    using ptr_type = std::unique_ptr<T, Deleter>;
    using element_type = T;

    static T* release(ptr_type& ptr) { return ptr.release(); }
    static std::unique_ptr<T, Deleter> make()
    {
        return std::make_unique<T>();
    }
};

template <typename T>
struct extra_pointer_traits<std::shared_ptr<T>>
{
    using ptr_type = std::shared_ptr<T>;
    using element_type = typename std::pointer_traits<ptr_type>::element_type;

    // No release()
    static std::shared_ptr<element_type[]> make(size_t count)
    {
        return std::make_shared<element_type[]>(count);
    }
    static std::shared_ptr<element_type> make()
    {
        return std::make_shared<element_type>();
    }
};

#endif // EXTRA_POINTER_TRAITS_HPP_

I'm considering suggesting something like this as an addition to the existing traits class the standards committe, but for now I've implemented it as a separate class.

Note: To clarify - these are not all possible template specializations for pointer-like classes in the standard library, there would be a few more.

First, size_t should be std::size_t everywhere.

Why don't the raw pointer/array cases have release()? Granted, it won't really change any ownership in reality, but it could conceptually.

static ptr_type make(size_t count) { return new T[count]; }
static ptr_type make()             { return new T;        }

I'm not sure this interface is a good idea as is. This only supports Ts with default constructors. What about constructor arguments:

template <typename... Args>
static ptr_type make(Args&&... args)
{
    return new T{std::forward<Args>(args)...};
}

But of course, if you do that, it conflicts with the make(std::size_t) overload. So you'd need a different name for that, like make_n() or something, maybe with an interface like:

template <typename... Args>
static ptr_type make_n(std::size_t count, Args&&... args)
{
    return new T[count]{std::forward<Args>(args)...};
}

However, what about the difference between T{...} and T(...)? Now you need overloads for those cases, too.

Now, as for the overall idea, I'm not a committee member, but I can tell you with absolute certainty that this will never be accepted.

First, what actual problem in use is this supposed to solve? What is an actual use case where this is necessary and offers a significant improvement? I can't think of any situation where this will be useful. Certainly not one that's generalizable, which is mandatory for a standard library addition.

Generally speaking, memory management should be handled by containers, and containers use allocators, and this has no allocator support whatsoever.

Even worse, it hides the allocation method from client code... which is disastrous because you need to know how something was allocated to know how to DEallocate it. As it is, your interface offers a "handy" way to allocate memory, but no way to free it, and in fact goes out of its way to make code less safe by stripping ownership from smart pointers with the release() function.

In summary, I see no general gain from this, and plenty of dangerous drawbacks.


Managing PostgreSQL transactions for concurrency I have a situation where I need to use PostgreSQL's serializable isolation level for transactions.  This is for a table shared among multiple concurrent PHP processes.  If the database runs into any sort of data consistency issue PDO will throw an exception.  Makes sense since it's really up to the application to decide what to do.  In my case I effectively want to lock and wait for any other concurrent process to finish.  Based on the hints returned by PostgreSQL messages it's recommended to catch the errors and just try again.

My main concern is that I'm arbitrarily retrying 5 times and hoping for no more problems.  Is there a way to write this process more resilient to concurrency issues?

public function runInTransaction(callable $callable)
{
    $success = false;
    $count = 0;
    $this->beginTransaction($isolationLevel);
    $this->exec("SET TRANSACTION ISOLATION LEVEL SERIALIZABLE");
    try {
        while (!$success && $count < 5) {
            try {
                $callable();
                $success = $this->commit();
            } catch (\PDOException $e) {
                if ($e->getCode() == '40001') {
                    // Serialized transaction failure. Try again.
                } elseif ($e->getCode() == '25P02') {
                    // "In failed sql transaction." Rollback and try again.
                    $this->rollback();
                    $this->beginTransaction($isolationLevel);
                } else {
                    throw $e;
                }
            }
            $count++;
        }
    } catch (\Exception $e) {
        if ($this->inTransaction()) {
            $this->rollback();
        }
        throw $e;
    }
    if (!$success) {
        throw new \RuntimeException("Could not commit transaction");
    }
}

Taking Craig's suggestion, I've had the following running in a test environment for one week with no issues:

public function runInTransaction(callable $callable)
{
    $success = false;
    $count = 0;
    $this->beginTransaction($isolationLevel);
    $this->exec("SET TRANSACTION ISOLATION LEVEL SERIALIZABLE");
    try {
        while (!$success && $count < 5) {
            try {
                $callable();
                $success = $this->commit();
            } catch (\PDOException $e) {
                // Catch concurrency issues and retry after
                // random scaled back-off delay.
                if ($e->getCode() == '40001' || $e->getCode() == '40P01') {
                    // Serialized transaction failure or deadlock.
                    usleep(rand(100, 200) * ($count + 1));
                } elseif ($e->getCode() == '25P02') {
                    // "In failed sql transaction."
                    $this->rollback();
                    usleep(rand(100, 200) * ($count + 1));
                    $this->beginTransaction($isolationLevel);
                } else {
                    throw $e;
                }
            }
            $count++;
        }
    } catch (\Exception $e) {
        if ($this->inTransaction()) {
            $this->rollback();
        }
        throw $e;
    }
    if (!$success) {
        throw new \RuntimeException("Could not commit transaction");
    }
}


SPOJ - Alphacode, using dynamic programming I am currently trying out a programming problem, SPOJ Alphacode, that involves dynamic programming.  In an encoding system where A=1, B=2, …, Z=26, a message 25114 is ambiguous, and could be decoded in 6 ways (BEAN, BEAAD, YAAD, YAN, YKD, or BEKD).  The challenge is to count the number of ways each given input number can be decoded.

Since, this is my second DP problem I am trying out, my code doesn't seem to be optimised, resulting in a time limit exceed error.

Although I have noticed that I have used a lot of for loops, I am not sure how to get rid of them.

Can someone please help me optimise this code?  And also, can someone tell me tips on how to optimise codes so that in the future, I can fix Time Limit Exceeded errors by myself?

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> input;

int addProc(string a, string b)
{
  int n = stoi(a) * 10 + stoi(b);

  if(n > 26)
  {
    return 0;
  }
  else
  {
    return n;
  }
}

int dp(int i)
{
  vector<vector<string> > comb(1);
  comb[0].push_back(string(1, input[i].at(0)));

  for(int j = 1; j < input[i].length(); j++)
  {
    int l = comb.size();
    for(int k = 0; k < l; k++)
    {
      if(comb[k][comb[k].size() - 1] != "0")
      {
        if(input[i].at(j) == '0')
        {
          int n = addProc(comb[k][comb[k].size() - 1], "0");
          comb[k].push_back(to_string(n));
        }
        else
        {
          comb[k].push_back(string(1, input[i].at(j)));
          int n = addProc(comb[k][comb[k].size() - 2], string(1, input[i].at(j)));
          vector<string> temp(comb[k].begin(), comb[k].end() - 1);
          temp[temp.size() - 1] = to_string(n);
          comb.push_back(temp);
        }
      }
    }
  }

  int count = 0;
  for(int j = 0; j < comb.size(); j++)
  {
    if(comb[j][comb[j].size() - 1] != "0")
    {
      count++;
    }
  }

  return count;
}

int main()
{
  ios_base::sync_with_stdio(false);

  string a = "";
  while(true)
  {
    cin >> a;
    if(a != "0")
    {
      input.push_back(a);
    }
    else
    {
      break;
    }
  }

  for(int i = 0; i < input.size(); i++)
  {
    cout << dp(i) << "\n";
  }

  return 0;
}

First of all, I would simplify the driver loop in main(), like this:

int main() {
    std::string msg;
    while ((std::cin >> msg) && (msg != "0")) {
        std::cout << decodings(msg) << '\n';
    }
}

Observations:

The status of the >> operator is checked, so that an input error or EOF would cause the program to end.
a was a cryptic variable name.
There is no point in saving all of the input first.  Each message is an independent test case.  You can start computing the result for each line as you encounter it.  That potentially saves you some delay.  It also eliminates the input global variable.  Most importantly, it helps declutter the dp() function, which only cared about input[i] anyway.
dp(i) was a cryptic and unhelpful function name.  It's not obvious what it stood for, and even if you knew that it meant "dynamic programming", it didnt't say anything about what it computes.

Your algorithm seems very complicated.  It seems to use a 2D table of strings (which is like a 3D table of chars) for memoization.  There are no comments, so I couldn't figure out what you were trying to do.  I decided it would be easier to write a solution from scratch.

Suggested solution

#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>

/**
 * Checks whether the character 'a' could represent a letter (1 to 9).
 */
bool isletter(char a) {
    return '1' <= a && a <= '9';
}

/**
 * Checks whether the string "ab" could represent a letter (10 to 26).
 */
bool isletter(char a, char b) {
    return (a == '1' && ('0' <= b && b <= '9')) ||
           (a == '2' && ('0' <= b && b <= '6'));
}

/**
 * Counts the number of ways the message could be decoded.
 */
std::int64_t decodings(const std::string& msg) {
    std::string::size_type len = msg.length();
    if (len == 0) return 1;

    std::int64_t prev_count = 1,
                 curr_count = isletter(msg[0]);
    for (int i = 1; i < len; ++i) {
        // Try decoding the last two characters as a letter, and
        // try decoding the final character as a letter.
        std::int64_t new_count = prev_count * isletter(msg[i - 1], msg[i]) +
                                 curr_count * isletter(msg[i]);
        prev_count = curr_count;
        curr_count = new_count;
    }

    return curr_count;
}

int main() {
    assert(decodings("25114") == 6);
    assert(decodings("1111111111") == 89);
    assert(decodings("3333333333") == 1);

    std::string msg;
    while ((std::cin >> msg) && (msg != "0")) {
        std::cout << decodings(msg) << '\n';
    }
}

Observations:

decodings() is obviously O(L) in time and O(1) in space, so it's hard to beat.
I've used std::int64_t, since that is what the challenge specifies.
For good measure, I've added assertions for the three provided test cases.


Take postcodes and get the Lat long information from them I had an interview task which was the final stage, however, the feedback I got back for my solution was that it lacked effort and structure. I would be grateful to know how my solution could be improved. I used postcode.io to get the latitude and longitude from the post codes.
Here is the Description:

Brief: Create a server application that allows a user to input one or more postcodes, and then returns location-specific information
based on the postcode entered.
Requirements: At least one of the external APIs made available to you should be used to retrieve the information that your API returns.
You are not limited to using only one, and are free to use as many of
them as you like (inc. any other external resources) in order to
provide useful data.

Based on the above I made the following program.
app.js
import * as express from "express";
import * as axios from "axios";

const app = express();
app.use(express.json());

app.get("/", (req, res) => {
  res.send("Server is up and running ");
});

app.get("/postcode/:postcode", async (req, res) => {
  const postcode = req.params.postcode;
  await getLatlonFromPostcode(postcode).then((data) => {
    res.send(data);
  });
});

app.post("/postcodes", async (req, res) => {
  const postCodes = req.body.postcodes;
  const result = await getAdressForMultiplePostCodes(postCodes).then(
    (response) => {
      return returnLatLonObj(response.result);
    }
  );
  res.json(result);
});

//Return the lat and lon for a single postcode
export async function getLatlonFromPostcode(postcode) {
  try {
    const res = await axios
      .get(`https://api.postcodes.io/postcodes/${postcode}`)
      .then((response) => {
        const lat = response.data.result.latitude.toString();
        const lon = response.data.result.longitude.toString();
        return `${lat}, ${lon}`;
      });
    return res;
  } catch (error) {
    console.error(error);
  }
}

//Return array of addresses from Postcode array
export async function getAdressForMultiplePostCodes(postcodes) {
  try {
    const res = await axios
      .post("https://api.postcodes.io/postcodes", {
        postcodes,
      })
      .then((response) => {
        return response.data;
      });
    return res;
  } catch (error) {
    console.error(error);
  }
}

//Grab Latitude and Longitude and convert Array to object
function returnLatLonObj(arr) {
  return arr.reduce((prev, curr) => {
    prev[curr.result.latitude] = curr.result.longitude;
    return prev;
  }, {});
}

export default app;

This is my index.js
import app from "./app";

app.listen(3000, () => {
    console.log("server listening on port 3000");
})

This was my test file, which I used jest for.
import { getLatlonFromPostcode } from "../app";

describe("getLatlonFromPostcode", () => {
  test("it should return latlon for given postcode", async () => {
    const latlon = await getLatlonFromPostcode("ox495nu");
    expect(latlon).toEqual("51.655929, -1.069752");
  });
});

describe("getLatlonFromPostcode in uppercase", () => {
  test("it should return latlon for given postcode", async () => {
    const latlon = await getLatlonFromPostcode("OX49 5NU");
    expect(latlon).toEqual("51.655929, -1.069752");
  });
});

describe("getLatlonFromPostcode with spaces between the postcode", () => {
  test("it should return latlon for given postcode", async () => {
    const latlon = await getLatlonFromPostcode("OX49 5NU");
    expect(latlon).toEqual("51.655929, -1.069752");
  });
});

Test case structure
It doesn't seem like the code totally "lacked effort and structure" but the structure, at least of the test cases, could be better. Since all three describe() blocks contain a test that calls getLatlonFromPostcode so there could be a single describe() block with three it() blocks to test the various aspects of how the function should handle given postcodes.
Utilizing await
One of the main benefits of using await is to eliminate the need for callbacks to .then(). Some code utilizes this benefit e.g. the test functions but the methods in app.js do not - e.g.

await getLatlonFromPostcode(postcode).then((data) => {
  res.send(data);
});

Ideally, the res.send() call would be on a sequential line instead of in a .then() callback function:
const data = await getLatlonFromPostcode(postcode);
res.send(data);

Or even simpler:
res.send(await getLatlonFromPostcode(postcode));

Error handling
As an interviewer I would be checking to see how well the code handles edge cases. Obviously with promises comes rejection. The first couple methods don't appear to handle rejected promises at all.
Import Star
The two import statements import everything from the modules being imported. In the Airbnb style guide, it recommends no wildcards:

Why? This makes sure you have a single default export.1

The import for axios could be simplified using destructuring assignment:
import { get, post} from "axios";

That way the code can call get() and post() without needing to reference axios, and the other items exported from axios that are not needed are not imported.