LeetCode on Longest Palindromic Substring in Python This is a programming question from LeetCode:

Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Below is my code that fails the following input because of "Time Limit Exceeded":

"glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt"

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0:
            return None
        if len(s) == 1:
            return s

        P = [[False]*len(s) for i in range(len(s))]

        for i in range(len(s)):
            P[i][i]   = True

        for i in range(len(s)-1):
            P[i][i+1] = (s[i]==s[i+1])

        for s_len in range(3,len(s)+1):
            for i in range(len(s)+1-s_len):
                P[i][i+s_len-1] = P[i+1][i+s_len-2] and (s[i]==s[i+s_len-1])

        ip = 0
        jp = 0
        max_len = 1

        for i in range(len(s)):
            for j in range(len(s)):
                if P[i][j] and j+1-i > max_len:
                    max_len = j+1-i
                    ip = i
                    jp = j
                    continue

        return s[ip:jp+1]

I was trying to follow the following approach described in the site solution. Could anyone help to see how to make my code more efficient?

Disclaimer: Not a Code Reviewer
Here are some short comments though:

You're looping though twice.
That'd make it brute force.
Brute force does usually fail for some medium and hard questions on LeetCode.

Alternative Solution

Here we'd loop through once:

class Solution:
    def longestPalindrome(self, s):
        if len(s) < 1:
            return s

        def isPalindrome(left, right):
            return s[left:right] == s[left:right][::-1]

        left, right = 0, 1
        for index in range(1, len(s)):
            if index - right > 0 and isPalindrome(index - right - 1, index + 1):
                left, right = index - right - 1, right + 2
            if index - right >= 0 and isPalindrome(index - right, index + 1):
                left, right = index - right, right + 1
        return s[left: left + right]

Your Solution

I just tested your solution (marginally passes):

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 1:
            return s

        P = [[False] * len(s) for i in range(len(s))]

        for i in range(len(s)):
            P[i][i] = True

        for i in range(len(s) - 1):
            P[i][i + 1] = (s[i] == s[i + 1])

        for s_len in range(3, len(s) + 1):
            for i in range(len(s) + 1 - s_len):
                P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])

        ip = 0
        jp = 0
        max_len = 1

        for i in range(len(s)):
            for j in range(len(s)):
                if P[i][j] and j + 1 - i > max_len:
                    max_len = j + 1 - i
                    ip = i
                    jp = j
                    continue

        return s[ip:jp + 1]

Since the runtimes is high, it's possible that it would fail sometimes.

I guess LeetCode has a time limit for each problem, maybe 10 seconds would be the limit for this specific problem.

Probably based on the geolocation/time, the runtime would be different also.

Just a bit more optimization:

Please see this line for j in range(i + 1, len(s))::

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 1:
            return s

        P = [[False] * len(s) for _ in range(len(s))]

        for i in range(len(s)):
            P[i][i] = True

        for i in range(len(s) - 1):
            P[i][i + 1] = (s[i] == s[i + 1])

        for s_len in range(3, len(s) + 1):
            for i in range(len(s) + 1 - s_len):
                P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])

        ip = 0
        jp = 0
        max_len = 1

        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                if P[i][j] and j + 1 - i > max_len:
                    max_len = j + 1 - i
                    ip = i
                    jp = j
                    continue

        return s[ip:jp + 1]

It reduces about 1 second but still not good.

I'm sure there are more ways to optimize.

Wait a bit! There are good Python reviewers here. Would likely help you out.

With some comments:
class Solution:
    def longestPalindrome(self, s):
        if len(s) < 1:
            return s

        def isPalindrome(left, right):
            return s[left:right] == s[left:right][::-1]

        # We set the left pointer on the first index
        # We set the right pointer on the second index
        # That's the minimum true palindrome
        left, right = 0, 1

        # We visit the alphabets from the second index forward once
        for index in range(1, len(s)):
            # Here we move the right pointer twice and once checking for palindromeness
            # We boundary check using index - right, to remain positive
            if index - right > 0 and isPalindrome(index - right - 1, index + 1):
                print(f"Step {index - 1}: Left pointer is at {index - right - 1} and Right pointer is at {index + 1}")
                print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
                print(f"Window length: {right}")
                print(f"Before: Left is {left} and Right is {left + right}")
                left, right = index - right - 1, right + 2
                print(f"After: Left is {left} and Right is {left + right}")
                print(f"String: {s[left: left + right]}")
                print('#' * 50)
            if index - right >= 0 and isPalindrome(index - right, index + 1):
                print(f"Step {index - 1}: Left pointer is at {index - right} and Right pointer is at {index + 1}")
                print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
                print(f"Window length: {right + 1}")
                print(f"Before: Left is {left} and Right is {left + right}")
                left, right = index - right, right + 1
                print(f"After: Left is {left} and Right is {left + right}")
                print(f"String: {s[left: left + right]}")
                print('#' * 50)
        return s[left: left + right]

Solution().longestPalindrome("glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt")

Prints:
Step 18: Left pointer is at 18 and Right pointer is at 20
Palindromeness start: 17 - Palindromeness end: 20
Window length: 2
Before: Left is 0 and Right is 1
After: Left is 18 and Right is 20
String: xx
##################################################
Step 25: Left pointer is at 24 and Right pointer is at 27
Palindromeness start: 23 - Palindromeness end: 27
Window length: 3
Before: Left is 18 and Right is 20
After: Left is 24 and Right is 27
String: ibi
##################################################
Step 462: Left pointer is at 460 and Right pointer is at 464
Palindromeness start: 459 - Palindromeness end: 464
Window length: 4
Before: Left is 24 and Right is 27
After: Left is 460 and Right is 464
String: pppp
##################################################

Happy Coding! ( ˆ_ˆ )


UnitOfWork, removing abstraction of abstraction (Repository) I'm creating a small project, but in the past I've used a Repository pattern for it, and it just seemed too bloated. I ended up having repo classes with huge amounts of queries. I'm trying to move away from that. I invite you to critique/help/guide me on my journey to less abstraction:

Note: I like the syntax style of Simple.Data and "Fluentness" of FluentApi. So my naming/style is inspired by them.

I start off with an IUnitOfWork Interface:

public interface IUnitOfWork : IDisposable
{
    void Save();
    IDbSet<T> Set<T>() where T : class;
}

My DB Context (pretty standard):

public partial class MyDbContext : DbContext, IUnitOfWork
{
    public MyDbContext() : base("DBConnection") { }

    public new IDbSet<T> Set<T>() where T : class
    {
        return base.Set<T>();
    }
    protected override void OnModelCreating(DbModelBuilder modelBuilder)
    {
        modelBuilder.Configurations.Add(new UsersMap());
    }
    public void Save()
    {
        SaveChanges();
    }
}

A Query object/service:

public class UserService : IService
{
    private readonly IUnitOfWork unitOfWork;

    public UserService(IUnitOfWork _u)
    {
        this.unitOfWork = _u;
    }
    public string GetUserName(string Name)
    {
        return unitOfWork.Set<User>().Single(s => s.Name == Name).UserName;
    }

}

Here's my Database Class (name inspired by Simple.Data):

public sealed partial class Database
{
    private readonly IUnitOfWork context;

    public Database(IUnitOfWork _context = null)
    {
        if (_context == null)
            this.context = new MyDbContext();
        else
            this.context = _context;
    }

    public static Database Open()
    {
        return new Database();
    }

    // I may move these into a separate file:
    public UserService Users { get { return new UserService(context); } }
}

Usage:

var userName = Database.Open().Users.GetUserName("John");
Console.WriteLine(userName);

This is all fine and good for simple tasks. But let's say I want to do multiple things whilst the Database connection is open. I could move Database.Open() to a separate variable then use it like this:

var database = Database.Open();
var userName = database.Users.GetUserName("John");
var userFirstName = database.Users.GetFirstName("john123");

So my question is, am I doing it wrong? Obviously, my main concern is to not open multiple connections to the Database, and use it like a UnitOfWork.

My other question is about how to handle CRUD. I have IService there (currently empty) because I was thinking of putting Insert/Update/Delete in there and adding methods to each Service class - BUT, this turns into a type "Repository" which I was trying to avoid. I don't think it's right for me to expose the DbSet<TEntity>() so I can .Add()/.Attach() - so what should I do here?

I'm still at the planning stage of this, so any changes/recommendations are welcome.

I realize you said

  my naming/style is inspired by them.

But I would still point out some of your naming conventions which don't align with C#s.

Method/Function level variables should be camelCase instead of PascalCase

public string GetUserName(string Name)
public string GetUserName(string name)

Same as before, and as a note _underscores should only be used for class level variables.

public UserService(IUnitOfWork _u)
public UserService(IUnitOfWork u)

Not required, but a common practice is also that you do indeed use underscores for class level variables

private readonly IUnitOfWork unitOfWork;
private readonly IUnitOfWork _unitOfWork;

Make sure you are disposing(closing) your database object. I presume by the way you have your class setup that when your database object is disposed it will close, in which case I would recommend using the using keyword. Which would make your above code look more like this in practice.

using(var database = Database.Open())
{
    var userName = database.Users.GetUserName("John");
    var userFirstName = database.Users.GetFirstName("john123");
}

This ensures that you are always closing your connection in the end.

Be careful when debugging your code, and remember (depending on your db setup) if you pause the debug in your code while the connection is open, you wont be able to use the database. Also if you have any plans to do mulithreading with this you'll want to use locks.


PANDAS DataFrame operations to analyze top Server Fault tags I am working on learning how to do frequency analysis of Server Fault question tags to see if there is any useful data that I can glean from them. I'm storing the raw data in Bitbucket for global access, so this code will use the same dataset I am using, it's about 30Mb.

import pandas as pd

debiandf = pd.read_csv("https://bitbucket.org/lloydm/dataviz/raw/e84b9f9a7941d255483a81af98248b4fec8a36a8/data/LinuxSFPopularity/DebianQuestions.csv")
debiandf["CreationDate"] = pd.to_datetime(debiandf["CreationDate"], format="%Y-%m-%d %H:%M:%S")
debiandf = debiandf.set_index(["CreationDate"])

tag_df = pd.DataFrame(index=debiandf.index, data=debiandf["Tags"])
tag_df = tag_df.reset_index().drop_duplicates(subset='CreationDate', keep='last').set_index('CreationDate')
x = tag_df["Tags"].str.extractall(r'\<(.*?)\>').unstack()
x.columns = x.columns.droplevel(0)
# column names signify the index location of the tag when extracted.
# i.e. with <ubuntu><networking><tag3> you would have [ubuntu,networking,tag3]
x.rename(columns={0: 1, 1: 2, 2: 3, 3: 4, 4: 5}, inplace=True)

x1 = x.groupby(x.index.year)[1].apply(lambda grp: grp.value_counts().head(5))
x2 = x.groupby(x.index.year)[2].apply(lambda grp: grp.value_counts().head(5))
x3 = x.groupby(x.index.year)[3].apply(lambda grp: grp.value_counts().head(5))
x4 = x.groupby(x.index.year)[4].apply(lambda grp: grp.value_counts().head(5))
x5 = x.groupby(x.index.year)[5].apply(lambda grp: grp.value_counts().head(5))

x6 = pd.concat([x1,x2,x3], axis=1)
x6 = x6.reset_index()
x6.rename(columns={"level_0": "Year", "level_1": "Tag"}, inplace=True)
print x6

I'm new to using pandas and I'm learning how to do data analysis on my own so I can produce original content for reddit. How can I simplify my x.groupby lines so I can get the top 5 value counts from every column in my x DataFrame?

I'm new to pandas, so if you could explain why it would be done that way, that would be really helpful.

The easiest way to go about this problem is to separate the tags, unstack them then stack them back in a way that doesn't lose creationDate values, this is done through concat, group the data then use pivote_table to rearrange the data where the periods are the columns and the tags are the index

To group the data take one of two approaches;

The first approach is to keep the creation date as a string and extract the year through str.split, then group the data by year and tag

import pandas as pd

# top n tags for each year will be displayed
n = 10
debiandf = pd.read_csv("filename")
debiandf = debiandf.reset_index().set_index(['index', "CreationDate"])
df = debiandf["Tags"].str.extractall(r'\<(.*?)\>').unstack()
df.columns = df.columns.droplevel(0)

# take all columns in df, convert each column to a df with
# columns Year(CreationDate) and tag and stack them on top of eachother
# the resulting x will be a 2 column dataframe
x = pd.concat(
    [pd.DataFrame(df[x], columns=['tag']).reset_index(
    ).rename(columns={'CreationDate': 'Period'}
             ) for x in df.columns.tolist()]).drop('index', axis=1)

# change the value of year from "%Y-%m-%d %H:%M:%S" to "%Y" using split
x['Period'] = x['Period'].apply(lambda x: x.split('-')[0])

# group values of x according to year and tag that will produce a 3 column
# ['Period','tag','count']
x6 = x.groupby(['Period', 'tag'])['tag'].agg({'count': len}).reset_index(
    # use pivote_table to reorganize the data
).pivot_table(index=['tag'], columns='Period').xs(
    # the resulting df will have the tags as index and the years as columns
    'count', axis=1, drop_level=True)

topn = pd.concat([pd.DataFrame(x6[col].nlargest(n)).astype(
    int).reset_index().rename(columns={
        col: 'count'}) for col in x6.columns],
    keys=x6.columns, axis=1)
print(topn[topn.columns[-6:]])

The second approach involves the use of pd.tseries.resample.TimeGrouper, to resample the date creation yearly A while grouping the data by year and tag

import pandas as pd

n = 10
debiandf = pd.read_csv("filename")
debiandf = debiandf.reset_index()
debiandf["CreationDate"] = pd.to_datetime(
    debiandf["CreationDate"], format="%Y-%m-%d %H:%M:%S")
debiandf.set_index(['index', 'CreationDate'], inplace=True)
df = debiandf["Tags"].str.extractall(r'\<(.*?)\>').unstack()
df.columns = df.columns.droplevel(0)

# take all columns in df, convert each column to a df with
# columns Year(CreationDate) and tag and stack them on top of eachother
# the resulting x will be a 2 column dataframe
x = pd.concat(
    [pd.DataFrame(df[x], columns=['tag']).reset_index(
    ).rename(columns={'CreationDate': 'Period'}
             ) for x in df.columns.tolist()]).drop(
    'index', axis=1).set_index('Period')
# group the data by the tags and the creationDate resampled to yearly
x6 = x.groupby([pd.tseries.resample.TimeGrouper('A'), 'tag']
               )['tag'].agg({'count': len}).rename(
    index=lambda x: str(
        x.year) if type(x) != str else x).reset_index().pivot_table(
    index=['tag'], columns='Period').xs('count', axis=1, drop_level=True)
topn = pd.concat([pd.DataFrame(x6[col].nlargest(n)).astype(
    int).reset_index().rename(columns={
        col: 'count'}) for col in x6.columns],
    keys=x6.columns, axis=1)
print(topn[topn.columns[-6:]])

Note that the second approach is more flexible and if you decide to look at a resample rate, i.e. look at quarterly data rather than yearly, all you have to change will be the resample rates and the format of the period columns.

A sample output for both snippets is shown below, the output contains the top 10 tags for each year:

Period                2014                2015                2016
                       tag count           tag count           tag count
0                   ubuntu   957        ubuntu   854        ubuntu  1010
1                    linux   428         linux   419         linux   409
2                   debian   318        debian   343        debian   339
3               apache-2.2   195    apache-2.2   120  ubuntu-14.04    91
4             ubuntu-12.04    70  ubuntu-14.04    50    apache-2.2    76
5                    nginx    59         nginx    41         nginx    67
6                    mysql    38           ssh    38    apache-2.4    46
7               networking    36    networking    37    networking    44
8                      ssh    33         mysql    29         mysql    31
9       domain-name-system    16    apache-2.4    28           ssh    27


Generic sort function I'm building a functional React component that allows a list of products to be sorted by various properties. The properties could be top-level or nested properties. And I'd also like a sort order to be defined. As a secondary sort, I'd like a name property to be used.
I have left out the React parts to boil it down to the plain JS.
Here's my first take on it:
sort = [one-of-the-cases]
ascending = [true||false]

const sortFunc = (a, b) => {
  let aParam = null
  let bParam = null
  switch (sort) {
    case 'brand':
      aParam = a.brand.title
      bParam = b.brand.title
      break
    case 'weight':
      aParam = a.metadata.weight
      bParam = b.metadata.weight
      break
    case 'price':
      aParam = a.price.unit_amount
      bParam = b.price.unit_amount
      break
    case 'style':
      aParam = a.metadata.style
      bParam = b.metadata.style
      break
    case 'arrival':
      aParam = b.created
      bParam = a.created
      break
    default:
      aParam = a.brand.title
      bParam = b.brand.title
      break
  }

  // Sort by property, ascending or descending
  if (aParam < bParam) {
    return ascending ? -1 : 1
  }
  if (aParam > bParam) {
    return ascending ? 1 : -1
  }

  // Sort by name
  if (a.name < b.name) {
    return -1
  }
  if (a.name > b.name) {
    return 1
  }

  return 0
}

products.sort(sortFunc)

This seems overly complicated. One idea I have is to flatten the object to eliminate the nested properties, which would make it possible to store the sort param as a variable, and use bracket notation to reference the object property. This would eliminate the switch statement.
Any other ideas for simplifying this complicated sort?

From a short review;

ascending should probably be a parameter in the sortFunc
sort (sortKey) should probably be a parameter in the sortFunc
I feel things should be Spartan (1 char) or spelled out

sortFunc -> sortFunction -> sorter?

I would strongly consider the closure concept (example ion proposal)
I would harmonize the sort values with the object fields,or create a map
There is no need to initialize aParam and bParam with null, the default undefined should do
You probably want to add a comment as to why you compare name at the end
I prefer the if/else if approach even when if performs a return, it's one line less and increases readability

This is my counter-proposal;

const sortAscending = true;
const sortDescending = false;

function createSortFunction(key, ascending){

  const keyMap = {
    brand : 'brand.title',
    weight: 'metadata.weight',
    price: 'price.unit_amount',
    style: 'metadata.style',
    arrival: 'created'
  }

  key = keyMap[key]? keyMap[key] : 'brand.title';

  return (function sortFunction(a, b){

    //Minor magic, derive the property from a the dot notation string
    key.split('.').forEach(part=>{a = a[part], b = b[part];});

    // Sort by property, ascending or descending
    if (a < b) {
      return ascending ? -1 : 1
    }else if (b > a) {
      return ascending ? 1 : -1
    }

    // Sort by name if the properties are same
    if (a.name < b.name) {
      return -1
    } else if (a.name > b.name) {
      return 1
    }
    //a and b are equal
    return 0;
  });
}

products = [
 { name : 'Bob',   metadata: { weight: 160, style: 'sage'}, price: { unit_amount: 145}, created : '19750421', brand : { title: 'Sir' } },
 { name : 'Skeet', metadata: { weight: 130, style: 'ninja'}, price: { unit_amount: 160}, created : '20010611', brand : { title: 'Bro' } }
]

products.sort(createSortFunction('weight', sortAscending));
console.log(products);


Bash - Automating creation of test files I'm in the process of understanding shell scripting - this is my simple code for adding test files for python unittest
I'm looking for best practice pointers, variable naming, and of course comments on structure and readability.
EDIT: Script is called by, for example
./create_tests.sh math tensor_add

dir_name="$1"
file_name="$2"
test_dir="test/${dir_name}"
file_in_dir="${test_dir}/${file_name}.py"

addFile() {
    if [[ -f "${file_in_dir}" ]]
    then
        echo "File already exists in directory, exiting."
        exit 0
    else
        touch "${file_in_dir}"
    fi
}

if [[ -d "${test_dir}" ]]
then
    echo "Directory already exists, adding the file to this directory."
    addFile
else
    echo "Directory and __init__.py created."
    mkdir "${test_dir}"
    touch "${test_dir}/__init__.py"
    addFile
fi

Add a shebang.
Keep naming consistent, I personally prefer and follow Google's style guide; you may use a different guide if available.
Try to make your script POSIX compliant, for a wider target reach (no need to rely on [[ expression from bash)
Define a function to create the test directory.
Use shellcheck.
The echo "Directory and __init__.py created." should happen after the creation has happened.
Use mkdir -p to allow for nested directories to also be created (if needed).
Let script throw error and stop as early as possible on errors. This is achieved with set -e.

Together:
#!/bin/sh

set -e

dir_name="$1"
file_name="$2"
test_dir="test/${dir_name}"
file_in_dir="${test_dir}/${file_name}.py"

add_file() {
    if test -f "${file_in_dir}"
    then
        echo "File already exists in directory, exiting."
        exit 0
    else
        touch "${file_in_dir}"
    fi
}

create_dir() {
    mkdir -p "${test_dir}"
    touch "${test_dir}/__init__.py"
    echo "Directory and __init__.py created."
}

[ ! -d "${test_dir}" ] && create_dir "${test_dir}"

add_file

The chunk of variable declarations (dir_name, file_name etc.) could also be localised to functions.


Count number of previous elements greater than its element at present index Suppose I have a vector containing n elements. I want to find out the number of previous elements greater than its element at present index i. I want to find A[i] > A[j] && i < j for all elements of the vector.

Constraints:

1 <= t <= 1000
1 <= n <= 10^5
1 <= A[i] <=10^5

My code:

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;

    while(t--) {
        int n,a,i,j;
        cin >> n;

        vector<int>v1;

        for(i=0;i<n;i++) {
            cin >> a;
            v1.push_back(a);
        }
        int cnt=0,sum=0;

        for(i=0;i<n;i++) {
            if( i!=0) {
                for(j=0;j<i;j++) {
                    if(v1[i]<v1[j]) {
                        cnt++;
                    }
                }
            }
            //  cout << cnt << " ";
            sum=sum+cnt;
            cnt=0;
        }

        cout << sum << '\n';
    }
}

This code is running fine for all the test cases except only one. It is showing the Time limit exceeded for one of the test cases. Can anyone help me?

I don't think there is a logic error in what you have posted. And even though there are details that would make it nicer (the cycle can for example run from i=1, questionable use of bits/stdc++.h header, long variable scopes and similar), it should do its job.

I suggest to think about time complexity of the algorithm. Your brute force approach will have quadratic complexity and may be too slow when the input is large.

There are different approaches that you can try. For example, I see you tagged your post with binary-search tag. Why? You could for example keep your vector sorted as the user enters the values. When adding a new number, find where it belongs (you can do it by bisection - with logarithmic complexity). All numbers to the left are smaller, the ones on the right are larger. Then insert the number and repeat. How to do it exactly is up to you, if you're allowed to use C++ algorithms, std::lower_bound and std::vector::insert will do the hard work for you.

You can of course craft some tree structure of your own to do something along those lines.


Determining if a product is taxable or imported This should tell me whether the product is taxable or imported. Name should indicate if the product is imported or certain keywords should tell that the product is non-taxable (chocolates, book, pills).

Could you please review the following class products?

class Product
  NON_TAXABLE = [/chocolates/, /book/, /pills/]

  def initialize(product_name)
    @product_name = product_name
  end

  def is_taxable?
    taxable = false
    NON_TAXABLE.each { |x| taxable = x.match(@product_name) if taxable }
    !taxable
  end

  def is_imported?
    /imported/.match(@product_name)
  end
end

Your is_taxable? function code does not seem to work. The issue is that taxable is never going to be true, so you'll never assign a new value. You want to write if !taxable instead. Your code becomes:

def is_taxable?
    taxable = false
    NON_TAXABLE.each { |x| taxable = x.match(@product_name) if !taxable }
    !taxable
end

It's still possible to make it simpler using Ruby functions on arrays.

def is_taxable?
  NON_TAXABLE.none? { |x| x.match(@product_name) }
end

This means: if my product is not among the tax-free products, then it is taxable.


More efficient way than creating scanner of .txt file twice I am working on a simple personal project to build a Hoffman Tree. In my constructor, shown below, I am reading in a file, creating HoffmanNodes that represent each char in the file then I got through the file to encode it. I need to create a Scanner to go through the file once to find all the chars and their frequency, then I recreate the scanner of the same file and go through it again to encode it.

I have tried to do some research to find a more efficient way to do this, and I am coming up short. Is there an easier way to do this?

public HoffmanCoding(File inFile) {

    Scanner in = createScanner(inFile);
    //Check empty file
    if (in.hasNextLine() == false) {
        throw new IllegalArgumentException("Can not encode an empty file");
    }

    //Create a HashMap that holds all the HoffmanNodes in the HoffmanTree
    nodeHashMap = buildNodeHashMap(in);
    //Use the HashMap to create a Priority Que that I then can use to make the tree
    PriorityQueue<HoffmanTreeNode> allNodes = new PriorityQueue<>(nodeHashMap.values());
    //Build the HoffmanTree
    this.rootOfHoffmanTree = buildHoffmanTree(allNodes);
    //Assign a code to all the nodes based on their position in the tree.
    assignCode(this.rootOfHoffmanTree, "");

    // Recreate scanner reset it to the begging of the file
    in = createScanner(inFile);
    //Encode and Decode the message.
    this.encodedMessage = encodeMessage(in);
    in.close();
    this.decodedMessage = decodeMessage(this.encodedMessage);
}

I'd be very skeptical about making any changes to the current code you have when it comes to creating the scanners. However, I do want to indicate that reopening a file while it is still open is probably not a good idea. So I'd use a try-with-resources when you create the Scanner instances. I don't think reopening a file is so resource intensive that it needs to be avoided.

However, file access is commonly performed using a file pointer, and that file pointer can be reset. The question is then how to make a FileInputStream aware of that. This can be done by asking for the file channel (introduced with Java NIO2) and then setting the position on that.

So if we read the documentation of FileInputStream#getChannel() we get:

  Reading bytes from this stream will increment the channel's position. Changing the channel's position, either explicitly or by reading, will change this stream's file position.

Ah! Right what we are after, so here is code that leaves the file open:

try (FileInputStream fis = new FileInputStream(inFile)) {
    Scanner scanner1 = new Scanner(fis);
    System.out.println(scanner1.nextLine());

    fis.getChannel().position(0L);

    Scanner scanner2 = new Scanner(fis);
    // prints the same line!
    System.out.println(scanner2.nextLine());

    // the underlying file stream will be closed anyway, but yeah...
    scanner2.close();
    scanner1.close();
}

Reusing a scanner itself doesn't work. The reason is that Scanner instances cache data, which means that that data is not present anymore in any underlying stream. This is why no such functionality is supplied. Scanner is not a very heavy-weight component to instantiate, so I guess that's all right.

The above code is pretty ugly because how Java handles close(). Any call to Scanner.close() - implicit or explicit - will also close the underlying FileInputStream. That's of course not very useful in this scenario.

An ugly hack is to create a FilterInputStream-based decorator that simply forwards everything and then simply doesn't call close on the underlying stream. That way you can close the scanners without closing the underlying FileInputStream. But yeah, just as yucky as above code.

The fact that it is possible to re-read the file without re-opening it is not sufficient reason to use tricks like above. If you close the file then the file handle is released and when reopening the file is probably still cached.

I don't know enough about your application to know if rewriting your code to use Java NIO directly makes sense. Scanner was added to Java to make it easy to parse simple input, it was not meant to parse complex files, as the first line of documentation shows:

  A simple text scanner which can parse primitive types and strings using regular expressions.

Your code looks OK-ish. I'm very worried about the number and use of fields though. Generally a lot of fields is a red flag when it comes to class design. The fact that all the processing is performed in the constructor is not a good sign either. The separate part of encoding should take place in a separate method, which would make above solution even harder to apply.


Decimal to Roman numeral conversion algorithm I have written a program to convert a decimal to a Roman numeral. I am wondering if my algorithm is okay or not. If it's not okay, I want suggestions on improving my code. This code only works for inputs up to 5000. I found this question in a code cracker competition at my college.

#include <iostream>
using namespace std;
int main()
{
    int num=0;
    int user;
    int temp=0;
    string ans[4];
    int mod=10;
    int n[5];
    string r1[]={"0","I","II","III","VI","V","VI","VII","VIII","IX" };
    string r2[]={"x","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
    string r3[]={"C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
    string r4[]={"M","MM","MMM","MMMM"};

    cout<<"Enter Number"<<endl;
    cin>>user;

    for(int i=0;i<4;i++)
{
    num=user%mod;
    user=user-num;
    n[3-i]=num;
    mod=mod*10;
}

for(int i=0;i<4;i++)
{
    if(n[i]>999)
    {
        temp=n[i]/1000;
        ans[i]=r4[temp-1];
    }
    if(n[i]>99 && n[i]<1000)
    {
        temp=n[i]/100;
    ans[i]=r3[temp-1];
    }
    if(n[i]>9&& n[i]<100)
    {
    temp=n[i]/10;
    ans[i]=r2[temp-1];
    }
        if(n[i]>0 && n[i]<10)
    {
    temp=n[i];
    ans[i]=r1[temp];
    }
    }
    for(int i=0;i<4;i++)
    {
    cout<<ans[i];
    }
    return 0;
    }

This code has a bug as 14 and 16 give the same output, while the Roman representation for them should surely be different:

14 -> XVI
16 -> XVI


HackerRank Binary search tree validation From here:

def checkBST(root):
    prev_val = -1
    for node in in_order_sort(root):
        if node.data <= prev_val:
            return False
        prev_val = node.data
    return True

def in_order_sort(node):
    if node.left:
        yield from in_order_sort(node.left)
    yield node
    if node.right:
        yield from in_order_sort(node.right)

Looking for any suggestions on improving this. It's pretty concise.

The input data is constrained between \$0\$ and \$10^4\$ so I can "get away" with setting the initial value to -1. The input func name checkBST is also predefined.

It seems that short of knowing you can validate a binary tree via an in-order traversal this would get complicated, but knowing that makes it straightforward?

The prev_val handling is slightly clumsy.  I would personally prefer using the pairwise() recipe from itertools.  You could then replace the loop altogether with all(…), which more clearly expresses your intentions.

I would also prefer to see the generator yield node.data instead of yield node.

from itertools import tee

def checkBST(root):
    a_iter, b_iter = tee(in_order_traversal(root))
    next(b_iter, None)
    return all(a <= b for a, b in zip(a_iter, b_iter))

def in_order_traversal(node):
    if node.left:
        yield from in_order_sort(node.left)
    yield node.data
    if node.right:
        yield from in_order_sort(node.right)


JavaScript Array Comparison (aka Set Comparison) I want to compare the values in two arrays. The order of the values doesn't matter. Basically they are two Sets. This function returns true if the values are the same in both arrays, or false otherwise.

function compareSets(a1, a2) {
    if (a1.length !== a2.length) {
        return false;
    }

    var len = a1.length;
    var a1Set = {};

    // Convert a1 into a Set
    for (var i = 0; i < len; i++) {
        var value1 = a1[i];
        a1Set[value1] = true;
    }

    // Compare a2 values to a1 values
    for (var i = 0; i < len; i++) {
        var value2 = a2[i];
        if (!(value2 in a1Set)) {
            return false;
        }
    }

    return true;
}

This is an \$O(n)\$ solution which is better than the naive \$O(n^2)\$. I think it is always safe to say that if the lengths are different, the arrays are not the same.

Is there any way I can make this more concise?

In JavaScript objects, keys are always strings, or converted into strings.  Therefore, all the elements of a1 and a2 will be compared as if they were stringified.  For example, compareSets(['true'], [true]) returns true.  I consider that to be unexpected behaviour that either needs to be fixed or documented.


Variable creation and returning Boolean values Out of a challenge for myself, I created this little program in which you can create "variables", test those "variable" values, test regular values, or clear all the "variables".

from operator import *

oper = {
    "==": eq,
    ">": gt,
    "<": lt,
    "<=": le,
    ">=": ge,
    "!=": one,}

var = []

def println(stringint):
    print stringint

def clearvars():
    del var[:]

def createvar(value):
    var.append(value)

def returnbool(value1, testvalue, value2):
    print testvalue(value1, value2)

Here's an example of an interpreter session. If you're curious, pcl is the filename.

>>> import pcl
>>> pcl.createvar(1)
>>> pcl.createvar(3)
>>> pcl.println(pcl.var)
[1, 3]
>>> pcl.returnbool(pcl.var[0], pcl.oper["!="], pcl.var[1])
True
>>> pcl.clearvars()
>>> pcl.println(pcl.var)
[]

All I'm really looking for are places where I could improve on, and how I can make this compatible with Python2 & Python3.

The code is sufficiently trivial that it's hard to see where improvements could be made. The only element that isn't already compatible with Python 3 is println (print is a function in 3.x), which seems useless anyway - why would you do:

pcl.println(pcl.var)

rather than

print pcl.var

If you're determined to keep it,

def println(stringint):
    print(stringint)

will work in 2.x and 3.x.

One step up would be to go for a class:

from operator import ne, ... # avoid 'from xyz import *'

class PCL(object):

    OPERATORS = {"!=": ne, ...}

    def __init__(self, vars=None): # provide initial variables (defaults to empty list)
        if vars is None:
            vars = []
        self.vars = vars

    def clear_vars(self): # create new list rather than deleting old one
        self.vars = []

    def create_var(self, value):
        self.vars.append(value)

    def return_bool(self, var1_index, op, var2_index):
        return self.OPERATORS[op](self.vars[var1_index],
                                  self.vars[var2_index])

This allows you to have multiple "sessions" alongside each other, with separate variable lists. It also removes the reliance on scoping for variable access, which will make testing easier as this grows in complexity.

I have also altered return_bool to take the indices and operator as arguments directly, simplifying the syntax:

>>> from pcl import PCL
>>> pcl1 = PCL()
>>> pcl1.create_var(1)
>>> pcl1.create_var(3)
>>> pcl1.return_bool(0, "!=", 1)
True

This may or may not be desirable.


Gaussian Elimination with Pivots I'm pretty new to python, and coding in general.  For practice, I've written the following code, which uses Gaussian reduction to solve a system of linear equations.

import numpy as np

def gaussian_reduce(matrix, b):

    '''
    Solve a system of linear equations matrix*X = b using
    Gaussian elimination.
    ---
    Inputs:
    matrix -> an nxn numpy array of the linear equation coefficients
    b -> an nx1 numpy array of the linear equation constants
    ---
    Output:
    a numpy array giving the solution to the system of equations
    ---
    Example:
    http://web.mit.edu/10.001/Web/Course_Notes/GaussElimPivoting.html
     '''

    if(matrix.shape[0] != matrix.shape[1]):
        raise Exception("Matrix should be square")

    matrix = np.append(matrix, b, axis=1)
    matrix = to_row_echelon(matrix)
    if all(matrix[-1,:] == 0):
        raise Exception("System of equations is inconsistent")
    b = matrix[:,-1].copy()
    matrix = np.delete(matrix, -1, axis =1)
    b = backsolve(matrix, b)

    return np.array([b])

def to_row_echelon(matrix):
    '''
    Loops over the input matrix to reduce the matrix to row echelon
    form
    '''
    for i in range(matrix.shape[0] -1):
        matrix[i:, i:] = pivot(matrix[i:, i:])

    return matrix

def pivot(matrix):
    '''
    Finds the max element of the first column, switches this row to be
    the first row of the matrix, then adds linear multiples of this row
    to set all other elements of the first row to be zero.
    '''
    idx_of_max = np.argmax(list(map(abs, matrix.T[0])))
    if idx_of_max != 0:
        swap_rows(matrix, 0, idx_of_max)

    matrix[1:,] = np.apply_along_axis(subtract_rows, 1, matrix[1:], matrix[0])

    return matrix

def subtract_rows(row, top_row):
    '''
    Subtracts a linear multiple of top_row from row such as to
    set the first element of row to zeros
    '''

    return row - (row[0]/top_row[0])*top_row

def backsolve(matrix, b):
    '''
    Backsolves a set of linear equations matrix*X = b, where
    matrix is in row echelon form
    '''
    b[-1] = b[-1]/matrix[-1,-1]
    for i in range(len(matrix) - 2, -1, -1):
        b[i] = (b[i] - (b[i+1:]*matrix[i, i+1:]).sum())/matrix[i,i]

    return b

def swap_rows(matrix, a, b):
    '''
    Swaps row a and b in a numpy array
    '''
    t = matrix[a].copy()
    matrix[a] = matrix[b]
    matrix[b] = t

I suppose my observations would be:

a) I wrote this as a number of different functions, which I hoped would make the code more readable - however, I think this might in fact have made it less so?

b) Ideally, I would have done most of the operations without having to reassign the matrix a number of times - however, I couldn't find a way to easily do the subtract rows step in place.  Would this make it much less efficient?

For some inputs where there is no solution, gaussian_reduce returns an array of NaNs:

>>> gaussian_reduce(np.zeros((2, 2)), np.ones((2, 1)))
__main__:63: RuntimeWarning: invalid value encountered in double_scalars
array([[nan, nan]])

A better way to handle an exceptional situation is to raise an exception, like np.linalg.solve:

>>> np.linalg.solve(np.zeros((2, 2)), np.ones((2, 1)))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "numpy/linalg/linalg.py", line 390, in solve
    r = gufunc(a, b, signature=signature, extobj=extobj)
  File "numpy/linalg/linalg.py", line 89, in _raise_linalgerror_singular
    raise LinAlgError("Singular matrix")
numpy.linalg.linalg.LinAlgError: Singular matrix

It looks as though you attempted to do this:

matrix = np.append(matrix, b, axis=1)
matrix = to_row_echelon(matrix)
if all(matrix[-1,:] == 0):
    raise Exception("System of equations is inconsistent")

but it doesn't work, because in this case (a zero matrix) the last row gets filled with NaNs rather than zeros:

>>> m = np.append(np.zeros((2, 2)), np.ones((2, 1)), axis=1)
>>> to_row_echelon(m)
array([[ 0.,  0.,  1.],
       [nan, nan, nan]])

The NaNs result from the division in subtract_rows:

return row - (row[0]/top_row[0])*top_row

This division needs to be skipped if top_row[0] is zero. For example, in pivot you would have:

if matrix[0, 0]:

before the call to np.apply_along_axis. (But see below for further improvements here.)
In mathematical code, you should be on the lookout for division by zero. Every division operation is suspicious: what if the divisor is zero? There are some more division operations in backsolve which lead to this kind of incorrect result:

>>> gaussian_reduce(np.ones((2, 2)), np.array([[2], [3]]))
__main__:70: RuntimeWarning: divide by zero encountered in double_scalars
array([[-inf, inf]])

In this case you need to raise an appropriate exception, again like  np.linalg.solve:

>>> np.linalg.solve(np.ones((2, 2)), np.array([[2], [3]]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "numpy/linalg/linalg.py", line 390, in solve
    r = gufunc(a, b, signature=signature, extobj=extobj)
  File "numpy/linalg/linalg.py", line 89, in _raise_linalgerror_singular
    raise LinAlgError("Singular matrix")
numpy.linalg.linalg.LinAlgError: Singular matrix

gaussian_reduce returns the result as a row vector (an array with one row):

>>> A = np.diag((1., 2.))
>>> b = np.array([[4.], [5.]])
>>> gaussian_reduce(A, b)
array([[4. , 2.5]])

But in the equation \$Ax = b\$ the solution \$x\$ is a column vector (an array with one column). And this is what np.linalg.solve returns:

>>> np.linalg.solve(A, b)
array([[4. ],
       [2.5]])

Returning a column vector means that we can verify the solution by multiplying:

>>> A @ np.linalg.solve(A, b)
array([[4.],
       [5.]])

which is equal to b as required. Whereas in the gaussian_reduce case, it doesn't work:

>>> A @ gaussian_reduce(A, b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: shapes (2,2) and (1,2) not aligned: 2 (dim 1) != 1 (dim 0)

The name gaussian_reduce could be improved. It's better to name a function based on what it computes, not after the algorithm it uses to compute it. For example, if you want to find the strongly connected components of a graph, you'd rather have a function named strongly_connected_components than one named tarjans_algorithm (Robert Tarjan invented many algorithms). Naming a function after its result rather than its method also allows you to change the method if you find a better one.

Since gaussian_reduce is a function that returns a solution to a system of linear equations, a name like linear_system_solution (or some suitable abbreviation) would be clearer.
When writing NumPy code, it's a good idea to be clear about when you are modifying arrays in-place and when you are returning new arrays. If you don't keep this distinction clear, then you are at risk of either (i) modifying an array that you didn't mean to, for example one passed by the caller; or (ii) making an unnecessary copy of an array when you could have just modified the original.

There are a couple of things you can do to keep this distinction clear. First, distinguish between functions that construct new arrays and functions that modify their input arrays, by having the former return the new array, and the latter return nothing (consider the difference between Python's built-in sorted, which returns a new list, and list.sort, which returns nothing). In this case, since to_row_echelon modifies its input, it should return nothing.

Second, avoid reusing a variable name to refer to a newly constructed array, because this will lead to confusion about whether it is safe to modify the array. For example, in gaussian_reduce you have:

matrix = np.append(matrix, b, axis=1)

The function np.append always constructs a new array, and so the original matrix and b are unchanged. This means that the copy and the deletion are unnecessary in the following lines:

b = matrix[:,-1].copy()
matrix = np.delete(matrix, -1, axis =1)
b = backsolve(matrix, b)

So to improve this code I would give the full matrix a new variable name to avoid confusion:

augmented_matrix = np.append(matrix, b, axis=1)

Then since to_row_echelon modifies its input, it should not return a result:

to_row_echelon(augmented_matrix)

Then the copy and deletion are unnecessary, because I can just index into augmented_matrix:

solution = backsolve(augmented_matrix[:,:-1], augmented_matrix[:, -1])

Note the use of the new variable name solution to avoid confusion with b.

Finally, instead of constructing yet another array:

return np.array([b])

we could reshape the array we already have:

return solution.reshape(1, -1)

but in fact as discussed above we should return a column vector here, not a row vector, so we actually need:

return solution.reshape(-1, 1)

Similarly, pivot modifies the input and so should not also return it.
The docstring for pivot says:

... to set all other elements of the first row to be zero

but this should say "column", not "row".
pivot needs to find the row with the largest absolute value in the first column, which it does like this:

idx_of_max = np.argmax(list(map(abs, matrix.T[0])))

It is clearer, I think, to get the first column of the matrix using matrix[:, 0] instead of transposing. Then you can just call abs(matrix[:, 0]), which returns a new array containing absolute values element-wise. This avoids the need for map and list.
Instead of calling subtract_rows for each row:

matrix[1:,] = np.apply_along_axis(subtract_rows, 1, matrix[1:], matrix[0])

do all the subtractions in one go, avoiding the need for subtract_rows:

matrix[1:] -= (matrix[0] / matrix[0, 0]) * matrix[1:, 0]

But to avoid division by zero you will need to guard this, as discussed above:

pivot_value = matrix[0, 0]
if pivot_value:
    matrix[1:] -= (matrix[0] / pivot_value) * matrix[1:, 0]

In swap_rows, it is misleading to name the arguments a and b, since elsewhere in the code you are using b for a column vector, but here b needs to be an index. It helps the reader to follow the code if you are consistent about the use of variable names. In this case I would use the names i and j.
swap_rows can be implemented more simply like this, using NumPy's "fancy indexing":

def swap_rows(a, i, j):
    "Swap rows i and j in the array a."
    a[[i, j]] = a[[j, i]]

This is now so simple that you would probably want to inline it at its single point of use.


Perform n mongodb updates at a time using SemaphoreSlim I have a queue of jobs, and I want to process 20 at a time using asynchronous concurrency.

When processing a job, some updates in MongoDb are made an a file gets uploaded to a server, that's up to 1GB and would take about 40 seconds.

What do you think?

Program.cs

 public static void Main(string[] args)
{
    MainAsync(args).Wait();
}

 public static async Task MainAsync(string[] args)
    {
        var serviceCollection = new ServiceCollection();
        ConfigureServices(serviceCollection);

        var serviceProvider = serviceCollection
            .AddLogging()
            .AddAutoMapper(typeof(Program))
            .BuildServiceProvider();

        await serviceProvider.GetService<App>().Run(20);
    }

App.cs

public class App
{
    private readonly IQueueService _queueService;
    private readonly IUploadService _uploadService;
    private SemaphoreSlim _throttle;

    public App(IQueueService queueService, IUploadService uploadService)
    {
        _queueService = queueService;
        _uploadService = uploadService;
    }

    public async Task Run(int initialCount = 3)
    {
        _throttle = new SemaphoreSlim(initialCount);

        var jobs = await _queueService.GetQueue();

        var tasks = jobs.Select(ProcessJob);
        await Task.WhenAll(tasks);

        Console.WriteLine("Upload finished...");
        Console.ReadKey();
    }

    private async Task ProcessJob(JobDto JobDto)
    {
        await _throttle.WaitAsync();
        try
        {
            // Process file
            Guid.TryParse(JobDto.JobName, out var jobId);
            var isUploaded = await _uploadService.Upload(JobDto.CreatedBy, jobId);

            // Update collection
            await _queueService.DeleteJobQueue(JobDto.Id);
        }
        finally
        {
            _throttle.Release();
        }
    }
}

I see two issues with the provided code:

You are using a queue, however I only see a single call to retrieve items from the queue, when you start the application. Does this mean all the jobs are there when Run() is called?
You want to process 20 jobs at a time, but can _uploadService.Upload actually handle unlimited simultaneous requests? Or does it silently peak at something like 2 * number of cores or the size of the thread pool?


Perl DBI Sample with MySQL DDL I've been experimenting with Perl and MySql and wrote this code for connecting and writing to a database:

#   MySQL DDL to create database used by code
#
#   CREATE DATABASE sampledb;
#
#   USE sampledb;
#
#   CREATE TABLE `dbtable` (
#     `id`  int(11) NOT NULL AUTO_INCREMENT,
#     `demo` longtext,
#     PRIMARY KEY  (`id`)
#   ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

# PERL MODULES
use strict;
use warnings;
use DBI; #http://dbi.perl.org

# CONFIG VARIABLES
my $platform = "mysql";
my $database = "sampledb";
my $host = "localhost";
my $port = "3306";
my $username = "root";
my $password = "password";

# DATA SOURCE NAME
my $dsn = "dbi:$platform:$database:$host:$port";

# PERL DBI CONNECT
my $connect = DBI->connect($dsn, $username, $password);

# VARS for Examples
my $query;
my $query_handle;
my $id;
my $demo;

# Example 1 using prepare() and execute() INSERT

    # SAMPLE VARIABLE AND VALUES TO PASS INTO SQL STATEMENT
    $id = 1;
    $demo = "test";

    # INSERT
    $query = "INSERT INTO dbtable (id, demo) VALUES ('$id', '$demo')";
    $query_handle = $connect->prepare($query);
    $query_handle->execute();
    undef $query;

# Example 2 using do() UPDATE

    # SAMPLE VARIABLE AND VALUES TO PASS INTO SQL STATEMENT
    $id = 1;
    $demo = "test 2";

    # UPDATE
    $query = "UPDATE dbtable SET demo = '$demo' WHERE id = $id";
    $query_handle = $connect->do($query);
    undef $query;

Is this the correct/idiomatic way to access a database in Perl? Are there any other improvements I could make?

Couple of things I noticed:

When you connect to the database, you don't check that the connection succeeded. The most common way I've seen to do this in Perl is:

my $connect = DBI->connect($dsn, $username, $password)
   or die "Connection Error:  DBI::errstr\n";

If the connection fails, the program will then display the connection failure message so you can see what's going on.

I see that you use two different ways of accessing the database. It would be better to pick one and use it for all your inserts/updates unless there is a compelling reason not to - it keeps future readers from trying to figure out why you did it differently. In this case I'd reccomend using execute since it allows you to execute multiple times:

$query_handle = $connect->prepare("INSERT INTO dbtable (id, demo) VALUES (?, ?)");
$query_handle->execute($id, $demo);
$id = 2;
$demo = "test2";
$query_handle->execute($id, $demo);

Also don't forget to disconnect:

$connect->disconnect;


Given two Binary trees, find whether the second is a sub tree of the first Given two binary trees, you have to find whether the second is a sub tree of the first.

First attempt (brute force):

int issubtree(tree *tree1p, tree * tree2p)
{
    if (tree2p == NULL)
        return 1;

    if (tree1p == NULL)
        return 0;

    if (tree1p->data == tree2p->data)
        return (issubtree(tree1p->leftp,tree2p->leftp)
                && (issubtree(tree1p->leftp,tree2p->leftp));
    else
        return (issubtree(tree1p->leftp,tree2p) || (issubtree(tree1p->rightp,tree2p));
}

Please give feedback on correctness more efficient code.

Firstly, what's will all the p's? I guess they mean pointer? They are silly, get rid of them.

Consider these trees:

     [A]                     [A]
    /   \                   /  \
  [B]   [C]               [D]   [C]
 /
[D]

Your code will claim that the second tree is a subtree of the first. The problem is that you cannot check the left/right matching using issubtree because they need to be exact matches not subtrees. You need to seperate the subtree search from the matching:

int matches(tree * tree1, tree * tree2)
{
    if(tree1 == tree2) return 1;
    if(tree1 == NULL || tree2 == NULL) return 0;
    if(tree1->data != tree2->data) return 0;
    return matches(tree1->left, tree2->left) && matches(tree1->right, tree2->right);
}

int issubtree(tree *haystack, tree * needle)
{
    if(tree1 == haystack) return 0;
    if( matches(haystack, needle) ) return 1;
    return issubtree(haystack->left, tree2) || issubtree(haystack->right, needle);
}

For increased efficiency, we can look at the problem in another way. We can express a tree by its pre-order traversal. So for the first tree above we have:

A,B,D,(NULL),(NULL),(NULL),C,(NULL), (NULL)

We can reconstruct the original tree from this sequence. Additionally, a subtree will show up as a substring of this sequence. This means that we can view the subtree problem as the same as the substring search problem. That's a well studied problem and you can view various algorithms for it here: http://en.wikipedia.org/wiki/String_searching_algorithm


Finding the horse number you will get I got this question from the interviewbit site test.

There are n horses and you are the kth person in the line to ride on the horse. All the persons in the queue will go with the lowest numbered horse available i.e if horse no.1 and horse no.2 are present , the person will choose horse no.1 .All the horses have their own riding time and after their riding time ends they are free for next round. If there are no horses available the person will wait for the horse to come and will go on with it. We have to find that on which horse number we will be riding.

Input:- T - no. of test cases, n - no. of horses, k - your number in queue,ride time(M) - n numbers which will denote the riding time of the horses

constraints:- 1 <= T <= 100, 1 <= N <= 1000, 1 <= K <= 10^9, 1 <= M(i) <= 100000

output :- you have to tell the horse number which you will get.

Ex. 1

3 8

4 2 1

output:-
1

Here there are 3 horses with running time 4, 2, 1 and i am 8th in the queue.
so first three persons will go with horse#1 , horse#2 and horse#3. After this
there will be no horse so the fourth person will have to wait. horse#3 will
come first so he will go with it. fifth will go with horse#2 and sixth with
horse#3, seventh will go with horse#3 and eight will go with horse #1. so the
output is 1.
Below is my code :-

Its time complexity is O(N*K). Is there a better way to solve it.

#include<iostream>
using namespace std;

int main(){

    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int hrs[n], ans;
        for(int i = 0;i < n;i++)
        cin>>hrs[i];

        if(n >= k){
            cout<<k<<endl;
        }else{
            int tt = 0,p = n;
            int B[n];
            for(int j = 0;j < n;j++)
            B[j] = hrs[j];

            while(p != k){
                tt++;
                for(int m = 0;m < n;m++){
                    if(tt == hrs[m]){
                        p++;
                        hrs[m] += B[m];
                        if(p == k){
                         ans = m;
                         break;
                        }
                    }
                }

            }
            cout<<ans+1<<endl;
        }

      }

    return 0;
}

Use portable constructs

Variable-length arrays are not standard C++.  Using such non-standard extensions hampers your code because you can't easily use different compilers (this can possibly even exclude entire target platforms).

Avoid importing all of std into the global namespace

Namespaces provide us with an important service, separating the large and growing set of identifiers in std from those of our own code.  It's actively harmful to reverse that benefit with using namespace std.

Always test for errors when reading

Formatted input such as std::cin >> n >> k should always test the state of the stream before using the read values.

Use clearer names

We don't have to use names like t just because that's what the question uses to describe the number of test cases.  Similarly, hrs took me much longer to comprehend than would horse - and that's not going to push your line lengths.

Know your standard library

What we have is a priority queue of horses, ordered by the time they next return, with the horse's number as tie-breaker.  We have std::priority_queue with insertion/removal times that scale as O(log n), so iterating over the k previous riders to find which horse we get will scale as O(k log n).

The algorithm is pretty simple - for each member of the queue in front of us, take the next horse from the stable (a std::priority_queue), add its running time to its next-available time, and insert it back into the stable.  The horse at the front of the stable after k-1 iterations will be ours.


Sorting a list based on date and time I have a class that is used to basically store samples from data being read from a system. Within that class is a property that I use to store the date and time of that sample:

public class ReadingValue
{
    public DateTime DateTimeOfReading { get; set; }
    public float Reading { get; set; }
}

I need to sort a list of ReadingValue based on the DateTimeOfReading property.

This is what I've come up with:

public IEnumerable<ReadingValue> Hourly(IList<ReadingValue> readings)
{
    var sortedReadings = readings.OrderBy(x => x.DateTimeOfReading.TimeOfDay)
        .OrderBy(x => x.DateTimeOfReading.Date)
        .OrderBy(x => x.DateTimeOfReading.Year);

    return sortedReadings;
}

The code seems to work, when I pass in a list of ReadingValue's it returns the list in sorted order. Is there anything I've overlooked or should do differently? I know time and date programming can be a tricky topic with things like timezones, daylight savings etc. but sorting dates and times shouldn't involve any of that, I don't think.

You should first do OrderBy and then you should do ThenBy instead of doing another OrderBy. What you are currently doing is that you are re-ordering everything after your first OrderBy.

public IEnumerable<ReadingValue> Hourly(IList<ReadingValue> readings)
{
    var sortedReadings = readings.OrderBy(x => x.DateTimeOfReading.TimeOfDay)
        .ThenBy(x => x.DateTimeOfReading.Date)
        .ThenBy(x => x.DateTimeOfReading.Year);

    return sortedReadings;
}


What's better: return null or handle the Exception? I'm in doubts what approach to take here, please have a look on the code below:

private void processBarCodeResponse(String decodedQrCode) {
        JSONObject jsonObject = JsonUtil.composeJsonObject(decodedQrCode);
        SalePoint salePoint = parseSalePoint(jsonObject);
        if (salePoint == null) return; // handle null value here
        saveSalePoint(salePoint);
    }

private SalePoint parseSalePoint(JSONObject jsonObject) {
        SalePoint salePoint = new SalePoint();
        try {
            salePoint.type = jsonObject.getString("type");
            salePoint.url = jsonObject.getString("url");
            salePoint.salePointId = jsonObject.getString("salePointId");
        } catch (JSONException e) {
            Logger.logError(TAG, "jsonObject " + jsonObject.toString() + " wasn't parsed " +
                    "correctly");
            return null; // point of concern
        }

        return salePoint;
    }

For the sake of readability I moved the try/catch block to the parseSalePoint() method, but then if parsing fails I'm enforced to return null from the method and check for null value in processBarCodeResponse() method. Wouldn't it be right to just handle the JSONException in processBarCodeResponse() method and stop its execution once it is thrown?

A possibly useful pattern here can be the Null Object-pattern.

Instead of returning null, return a "null SalePoint". Perhaps something like new SalePoint();, or new SalePoint("some special url");. Then make your saveSalePoint method do nothing if the SalePoint has a special url indicating that it's null.

Another option is to return null from your parseSalePoint method as you are currently doing and then simply return from the saveSalePoint method if the argument is null which will remove the null check from processBarCodeResponse.

Honestly, I can't tell you which option you should use or not. I can only present you with alternatives. Personally I like Null Object pattern a lot, but it doesn't always makes much sense to use that pattern.

By the way, why isn't SalePoint immutable? Instead of first creating a SalePoint object and then setting it's values one by one, read the values into variables and call a constructor which takes type, url, salePointId as arguments and get rid of the accessible properties (make them private, and also get rid of the setter-methods if you have any)


Personal Project for managing Bookmarks - View Part The code is the view part of my bookmarker - project for managing bookmarks by categories. It uses Python 3.4/Django 1.6. I have also included models.py for reference.

The code does the following

Providing relevant autocomplete JSON data
Providing details of categories/bookmarks (both are DB models of my project)
Open website stored in bookmark

I am mainly concerned with the quality of the abstractions. Other reviews are also welcome but I am mainly concerned with the structure of the code.

views.py

from django.http import HttpResponse
from django.shortcuts import render

from BookMarker.models import BookMark, Category

import json
import webbrowser

###########################
##       Auxiliary       ##
###########################
def _get_objects_by_params(request, param_name, object_class):
    ids_string = request.GET.get(param_name, '')
    if ids_string == '':
        return []
    ids = ids_string.split(',')
    return [object_class.objects.get(pk=_id) for _id in ids]

class Autocomplete():
    @staticmethod
    def _get_json(cur_objects, func):
        results = []
        for cur_object in cur_objects:
            results.append(func(cur_object))
        return json.dumps(results)

    @staticmethod
    def autocomplete(request, class_name, attr_name):
        term = request.GET.get('term', '')
        objects = class_name.objects.filter(**{
            attr_name + '__icontains': term
        })

        exclude_value = request.GET.get("excludes", "")
        if exclude_value != "":
            objects = objects.exclude(id__in=[int(i) for i in exclude_value.split(",")])

        data = Autocomplete._get_json(
            objects,
            lambda x: getattr(x, attr_name)
        )
        return HttpResponse(data, 'application/json')

class GetBookMarks:
    @staticmethod
    def get_bookmarks_by_categories(categories):
        bookmarks = set()
        for category in categories:
            bookmarks.update(category.bookmark_set.all())
        return bookmarks

    @staticmethod
    def get_bookmark_by_name(bookmark_name):
        return BookMark.objects.filter(name=bookmark_name)[0]

class GetCategories:
    @staticmethod
    def get_categories_by_bookmark(bookmark):
        return bookmark.category.all()

###########################
##         Services      ##
###########################
def category_autocomplete(request):
    return Autocomplete.autocomplete(request, Category, 'name')

def bookmark_autocomplete(request):
    return Autocomplete.autocomplete(request, BookMark, 'name')

def website_open(request):
    cur_url = _get_objects_by_params(request, 'id', BookMark)[0].url_content
    webbrowser.open(cur_url)
    return HttpResponse('success', 'text/html')

def get_bookmarks(request):
    categories = _get_objects_by_params(request, 'value', Category)
    bookmarks = GetBookMarks.get_bookmarks_by_categories(categories)
    return render(request, 'BookMarker/partials/bookmarks.html', {
        'bookmarks': bookmarks,
    })

#TODO Need to check the name
def get_bookmark_by_name(request):
    bookmark = GetBookMarks.get_bookmark_by_name(request.GET.get("name", ""))
    categories = GetCategories.get_categories_by_bookmark(bookmark)
    result = [category.name for category in categories]
    return HttpResponse(json.dumps(result), 'application/json')

def get_category(request):
    category = Category.objects.get(name=request.GET.get('value', ''))
    return render(request, 'BookMarker/partials/category.html', {
        'category': category,
    })

models.py

from django.db import models

class Category(models.Model):
    name = models.CharField(max_length=50)

    def __str__(self):
        return self.name

class BookMark(models.Model):
    name = models.CharField(max_length=50)
    url_content = models.CharField(max_length=500)
    category = models.ManyToManyField(Category)

    def __str__(self):
        return self.name

Overall, this is pretty nicely written.

Abstractions and code structure

  I am mainly concerned with the quality of the abstractions. Other reviews are also welcome but I am mainly concerned with the structure of the code.

The models are nice and simple, no comments there.

The classes in the views file are not great.
Since they only have static methods,
they are essentially utility classes.
As such, the methods don't really need to be in a class at all,
they could be simply top-level functions.
For example, these kind of calls are a bit awkward:

    return Autocomplete.autocomplete(request, Category, 'name')

Normally a class should help you avoid repeating terms.
For example a Person class would have a get_name method instead of get_person_name. Since Person is already implied by the class,
methods in it don't need to repeat the term "person".
The presence of calls like Autocomplete.autocomplete is a symptom of a problem with the class structure.

Possibly you created a class for Autocomplete to hide the private method _get_json.
That's not a bad idea.
However, since that method is only called from autocomplete itself,
it could just as well be inside autocomplete itself.
Also note that another way to group methods is to put them in a separate file.

Overall, I think classes with only static methods are not great.
They would be better converted to regular functions at the top level,
or in their dedicated file.
The same goes for GetBookmarks and GetCategories too.
And this is especially true for classes that only contain one public method.

Going back to your main question:
such classes don't represent useful abstractions,
they are simple groupings of related methods.
Utility classes are useful,
but if you only have a single method in them,
then they are a bit of an overkill and might not help all that much.

Coding practices

A couple of things are not very Pythonic or can be improved.

Instead of this:

    if ids_string == '':
        return []

It's more Pythonic to write this way:

    if not ids_string:
        return []

Instead of this:

    def _get_json(cur_objects, func):
        results = []
        for cur_object in cur_objects:
            results.append(func(cur_object))
        return json.dumps(results)

The common approach is to use a list comprehension, which makes it more compact and Pythonic:

    def _get_json(cur_objects, func):
        return json.dumps([func(cur_object) for cur_object in cur_objects])

Similar to earlier:

        if exclude_value != "":
            # ...

The Pythonic way would be:

        if exclude_value:
            # ...

This is more complicated than it needs to be:

        data = Autocomplete._get_json(
            objects,
            lambda x: getattr(x, attr_name)
        )

Since the _get_json function will simply call the lambda on the elements,
it would be more natural to use a simple list comprehension here,
and pass a list to _get_json without needing a lambda at all:

        data = Autocomplete._get_json([getattr(x, attr_name) for x in objects])

And since we know just how simple is _get_json,
we could simply bypass it entirely:

        data = json.dumps([getattr(x, attr_name) for x in objects])


Counter GUI in Swing, updating the count in the background I made a simple counter GUI for practice. The user presses a button to start the counter. The button click executes a SwingWorker task that updates a JLabel with the count. The update occurs in the doInBackground method.

Is this a bad idea? Even for something as simple as this, I should still update the component from a method that runs on the event dispatch thread, such as process?

If so, why would it be a bad practice for something as simple as this?

Main.java:

package counter;

import javax.swing.SwingUtilities;

public class Main {
    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                CounterView view = new CounterView();
                view.activate();
            }
        });
    }
}

ProgressBar.java:

package counter;

import java.awt.BorderLayout;
import javax.swing.*;
import javax.swing.JFrame;
import javax.swing.JButton;
import javax.swing.JLabel;
import javax.swing.SwingWorker;
import javax.swing.SwingConstants;
import java.awt.event.*;

public class CounterView {
    private JFrame frame;
    private JPanel gui;
    private JButton button;
    private JLabel count;

    public CounterView() {
        customizeFrame();
        createMainPanel();
        createCountText();
        createButton();
        addComponentsToFrame();
    }

    private void customizeFrame() {
        frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }

    private void createMainPanel() {
        gui = new JPanel();
        gui.setLayout(new BorderLayout());
    }

    private void createCountText() {
        count = new JLabel("0");
        count.setHorizontalAlignment(SwingConstants.CENTER);
    }

    private void createButton()  {
        button = new JButton("Start counter");
        button.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                // Create the worker
                SwingWorker<Void, Void> worker = new SwingWorker<Void, Void>() {

                    @Override
                    protected Void doInBackground() throws Exception {
                        for (int i = 0; i <= 50; i++) {
                            Thread.sleep(100);
                            System.out.println(i);
                            text.setText(Integer.toString(i));
                        }

                        return null;
                    }
                };

                // Start the worker
                worker.execute();
            }
        });
    }

    private void addComponentsToFrame() {
        gui.add(count, BorderLayout.CENTER);
        gui.add(button, BorderLayout.SOUTH);
        frame.add(gui);
        frame.pack();
    }

    public void activate() {
        frame.setVisible(true);
    }
}

To answer your question:

  Q. Is this a bad idea?

A. No, it's fine in your case, but creating a new Thread is easier, like this:

private void createButton() {
    button = new JButton("Start counter");
    button.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            button.setEnabled(false); // can't click while counter is running
            Thread background = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int i = 0; i <= 50; i++) {
                        try {
                            Thread.sleep(100);
                        } catch(InterruptedException e) {
                            e.printStackTrace();
                        }
                        System.out.println(i);
                        count.setText(Integer.toString(i));
                    }
                    button.setEnabled(true); //click-able after the counter ends
                }
            });
            background.start();
        }
    });
}

There are some things you can fix in your code to improve it:

Use of throws Exception in your doInBackGround method. throwing Exception is not good to use because it is vague, and unnecessary in your case. Just throw InterruptedException instead.

@Override
protected Void doInBackground() throws InterruptedException {
    //...
}

Error. This line: text.setText(Integer.toString(i)); throws an Error: "text cannot be resolved." I believe you meant to do: count.setText(Integer.toString(i));
activate() method. Make your life easier by cutting down a few lines: Just set the frame visible in your constructor, like this:

public CounterView() {
    customizeFrame();
    createMainPanel();
    createCountText();
    createButton();
    addComponentsToFrame();
    frame.setVisible(true);
}

This removes the need for your activate method completely.
Notice that if you click the button twice, then 2 counters start? I don't think you want that. disable the button after it is clicked to avoid this. Example:

private void createButton() {
    button = new JButton("Start counter");
    button.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            button.setEnabled(false); //added this line
            //...

Other than those, your code looks good. good indentation, variable names, method names, etc.


Pulling Docker Machine IP I am working with MongoDB through Docker, and I have a terrible bash command to pull the Docker Machine IP so I can sanely connect locally.

export dockerip="$(docker-machine ls | awk '{print $5}' | sed -n '2p' | sed 's/tcp:\/\///' | sed 's/\:2376//')"
mongo --host "$dockerip" --port 27017

How can I optimise the docker-machine line?

docker-machine provides a simple way to get the IP of the host machine

mongo --host `docker-machine ip default` --port 27017

I'm using default here, since that's the name of the machine I'm using.


Callback class to callback member (virtual) functions After looking at a post on CR I found that pointers to member functions are incredibly hard to use, especially as callbacks. The current solution doesn't solve the problem mentioned in the linked post, but tries to get rid of the type erasure (i.e. std::function<>) by making the target type explicit. I tried to solve lifetime/ownership issue with something else than std::shared_ptr<>, but found that it is impossible without relying on programmer to take care of that. So, I ended up with std::shared_ptr<> as a solution.

So, here is the code:

#pragma once
#include <memory>
#include <utility>

template <typename T, typename Func>
class member_callback;

template <typename T, typename R, typename ... ArgTypes>
class member_callback<T, R(ArgTypes...)>
{
    std::shared_ptr<T> object;
    R(T::* callback)(ArgTypes ...);
public:
    using function_pointer = R(T::*)(ArgTypes ...);

    member_callback(const std::shared_ptr<T>& ptr, R(T::* function)(ArgTypes...)) :
        object(ptr),
        callback(function)
    {}

    member_callback(std::shared_ptr<T>&& ptr, R(T::* function)(ArgTypes...)) :
        object(std::move(ptr)),
        callback(function)
    {}

    R operator()(ArgTypes&& ... args)
    {
        return ((*object).*callback)(std::forward<ArgTypes>(args)...);
    }

    std::shared_ptr<T> get()
    {
        return object;
    }

    function_pointer get_function()
    {
        return callback;
    }
};

It does one tradeoff though, you can't make a vector of them and call member functions of completely unrelated classes. Nevertheless, you'll still be able to invoke virtual functions, and they will work as expected according to this answer.

From the first glance it might look useless. But it is not! It becomes extremely useful when you're making a menu (1. ... 2. ... 3. ...) and want to invoke a function on the single object. So, here is the example:

#include "member_callback.hpp"
#include <iostream>
#include <vector>

class integer
{
    int x;
public:
    integer():
            x(0)
    {}

    integer& operator++()
    {
        ++x;
        return *this;
    }

    integer& operator--()
    {
        --x;
        return *this;
    }

    friend std::ostream& operator<<(std::ostream& os, const integer& i);
};

std::ostream& operator<<(std::ostream& os, const integer& i)
{
    os << "Currently number is: " << i.x << '\n';
}

void print_menu()
{
    static auto message = "Type the specified number to invoke the command.\n";
    static auto menu = "0. Increment\n1. Decrement\nAnything else to exit\n";

    std::cout << message << menu;
}

int main()
{
    auto object = std::make_shared<integer>();

    std::vector<member_callback<integer, integer&()>> actions{{object, &integer::operator++},
                                                              {object, &integer::operator--}};

    std::cout << "Welcome to dummy program!\n";
    std::cout << *object;

    unsigned int response =  -1;
    print_menu();
    std::cin >> response;
    while (response < 2)
    {
        actions[response]();
        std::cout << *object;
        print_menu();
        std::cin >> response;
    }

    std::cout << "Goodbye!\n";
}

If code will ever get changed you can find it here.

I would like a review to focus on the easy of use. Also, does the code provide fine grained control? It will require dealing with std::shared_ptr<>, but I think it is mostly ok. Any other review points are welcome!

Overall, the design looks reasonable.  However, I can't shake the feeling that Lambda expressions are a good (maybe even better) fit here.

For example, instead of

member_callback(object, &integer::--);

you could use a Lambda expression:

[&] () { return object--; }

This is almost as short, and has some additional advantages:

You aren't effectively "reinventing the wheel".  Although I wouldn't say your member_callback class is precisely the same as a lambda, it's pretty close.
I'm not qualified to say whether your code conforms to the C++ 11 specification.  But assuming it does, you are relying on relatively obscure portions of the specification.  This has some practical problems:

Others might have a hard time understanding and verifying your code.
Compilers often don't conform as strictly to the spec as we would like.  So you might find that your code is not portable, even if it does conform the the spec.

You noted that one of the drawbacks of your approach is that you cannot mix functions to different types of objects.  With lambdas, you can combine functions that work on different types of objects.  You aren't just limited to objects of a single (base) type (in your case, integer).  Likewise, you can define functions that operate on more than one object, or even none at all (e.g., produce a constant value).  Or, you could combine functions.
Lambdas open the door to higher-order approaches.  For example, if you Curry the member_callback function, you can partially instantiate a callback:

With the order you have (object, function), you can construct a factory for working on a single object.  For example (eliding types for brevity):

factory = member_callback_curried(object);

// Sometime later, perhaps in a different scope
dec = factory([] (integer& obj) { return obj--; });
inc = factory([] (integer& obj) { return obj++; });

Reversing the order to (function, object), you can construct a factory for working with the specified function:

factory = callback_member_curried([&] (integer& obj) { return obj-- });

// Sometime later, perhaps in a different scope
dec_o1 = factory(obj1); // function that decrements obj1
dec_o2 = factory(obj2); // function that decrements obj2


Is there simplier than this one in PHP? I want to refactor my code but I can't find and much simplier one. Can you please suggest on how to refactor the code below without using a loop? maybe using only array functions? TIA

<?php
$week_no = array(2,3,4);
$days = array('TU', 'WE', 'TH');

foreach ($week_no as $n) {
  foreach ($days as $d) {
   $out[] = $n . $d;
  }
}

var_dump($out); // array('2TU', '2WE', '2TH','3TU', '3WE', '3TH, '4TU', '4WE', '4TH)
?>

How about this for some madness:

function weekday($a, $b){global $days; return "$a $b".join(" $b", $days);};
$out = explode(' ', trim(array_reduce($week_no, 'weekday')));

(Urm, yes well maybe not...)

Sometimes to attain elegance you have to change the way your code is working, i.e. what are your reasons behind generating such an odd array? From my experience something like this would be more useful:

$out = array_fill(reset($week_no),count($week_no),$days);

Which generates the following:

Array
(
    [2] => Array
        (
            [0] => TU
            [1] => WE
            [2] => TH
        )

    [3] => Array
        (
            [0] => TU
            [1] => WE
            [2] => TH
        )

    [4] => Array
        (
            [0] => TU
            [1] => WE
            [2] => TH
        )

)

The above would be much easier to traverse and would be more extendable.

In sticking with your question however the foreach method is by far the best as stated in the comments... but it was fun trying odd work arounds ;) Am surprised that there is no php function to directly prepend or append array items with another set of array items... probably because it's quite easy and fast to do so with a few foreachs.


Discrete random number generator in Python Description: I am given a list of possible values, each of which have an associated probability of occurrence.

How could I improve the algorithm that randomly generates a value based on the given distribution? I want to let the number of possible values grow very large. I essentially use the cumulative probabilities in my solution.

import numpy as np, numpy.random

N = 100
possible_values = [x for x in range(N)]
probabilities = np.random.dirichlet(np.ones(N),size=1).tolist()[0]

def sampleValue(possible_values, probabilities):
    U = random.random()
    cum_probs= np.cumsum(probabilities).tolist()
    for i, c in enumerate(cum_probs):
        if U < c:
            return possible_values[i]

testValues = [sampleValue(possible_values, probabilities) for x in range(100000)]

#testing

print('Sample test')
print('Theoretical', probabilities[10])
print('Simulated', testValues.count(10) / 100000)

Is there a reason why you start off with numpy, then switch to lists and a for loop?

If you are given lists, you could convert them to numpy arrays and refactor your sampleValue() function to be done entirely in numpy. Otherwise, keep your generated values as numpy arrays instead of converting them to list and refactor your sampleValue() function to be done with numpy anyway.

probabilities = np.array(np.random.dirichlet(np.ones(N),size=1).tolist()[0])

def sampleValue2(possible_values, probabilities):
    U = random.random()
    return possible_values[np.argmax(np.cumsum(probabilities)>U)]

This reduces function simulation time from

1.18 s ± 9.87 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

to

486 ms ± 8.59 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Then if you know how many random #s you want you can ditch the list comprehension by creating a probability matrix:

cum_probs = np.tile(np.cumsum(probabilities),(num_test,1))

Apply the function we rewrote over the entire matrix instead of by row:

indices = np.argmax(U<cum_probs,axis=1)
return np.array(possible_values)[indices]

to write a new function:

def sampleValue3(possible_values, probabilities):
    U = np.random.random(size=(num_test,1))
    cum_probs = np.tile(np.cumsum(probabilities),(num_test,1))
    indices = np.argmax(U<cum_probs,axis=1)
    return np.array(possible_values)[indices]

And that gives me a simulation time of:

65.9 ms ± 502 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Since you are just doing a lot of numeric operations, your algorithm could be sped up a lot just by keeping everything within numpy arrays/matrices.

Alternatively, from your problem definition, I don't see any reason why you can't just use numpy's random choice:

def sampleValue5(possible_values, probabilities):
    return np.random.choice(possible_values,p=probabilities,size=100000)

which is the fastest of these at:

36.8 ms ± 315 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


Largest palindrome in the string There are a lot similar questions out there. However, I wanted to get comments on my code. My implementation (as I believe) is simpler than the other complex ones as mine is \$O(n^2)\$.

My approach is simple:

Start with the biggest size of string
Check that string if its palindrome
Reduce the string size by 1 and check each string of that size in the given string if its palindrome

I am not doing any null/size checks since I just wanted to see if my code works.

I used test data:

HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

and it gives the correct output of:

12345678987654321

Please let me know if you have any suggestions or comments.

public static String findLargestPalindrome(String str) {
    for (int palindromeSize = str.length(); palindromeSize > 0; palindromeSize--) {
        for (int i = 0; i + palindromeSize <= str.length(); i++) {
            int substr = i + palindromeSize;
            String test;
            if (substr > str.length()) {
                test = str.substring(i);
            } else {
                test = str.substring(i, substr);
            }
            if (isPalindrome(test)) {
                return test;
            }

        }
    }
    return null;
}

public static boolean isPalindrome(String str) {
    if (str == null || str.trim().equals("")) {
        return false;
    } else if (str.length() == 1) {
        return true;
    }

    for (int i = 0, j = str.length() - 1; i <= j; i++, j--) {
        if (str.charAt(i) != str.charAt(j)) {
            return false;
        }
    }
    return true;
}

I thought about this approach by myself without looking at any of existing solutions. I haven't even read any solution except for Manacher which solves this problem in \$O(n)\$.

Time complexity

  It has \$O(n^2)\$ complexity.

It actually has \$O(n^3)\$ complexity.  As @Cadoiz noted, isPalindrome isn't \$O(1)\$ but \$O(n)\$.

Note that Manacher's algorithm isn't \$O(n)\$ but \$O(n^2)\$.  The outer for loop and the inner while loop both are \$O(n)\$.  Together that makes them \$O(n^2)\$.  In practice, it will do better than that, as the worst case is when every character is the same.  You could also write this as \$O(m\cdot n)\$, where \$m\$ is the length of the longest palindrome substring.  It's only linear if you neglect \$m\$, which is itself \$O(n)\$ in the worst case.

Manacher's is linear in space, but your version can be constant in space (if you don't make extra substrings).

Unnecessary code

        for (int i = 0; i + palindromeSize <= str.length(); i++) {
            int substr = i + palindromeSize;
            String test;
            if (substr > str.length()) {
                test = str.substring(i);
            } else {
                test = str.substring(i, substr);
            }
            if (isPalindrome(test)) {
                return test;
            }

But substr can never be greater than the length of the string, as you you check for that in the for loop test.  So you can just say

         for (int i = 0; i + palindromeSize <= str.length(); i++) {
            int substr = i + palindromeSize;
            String test = str.substring(i, substr);

            if (isPalindrome(test)) {
                return test;
            }

Naming

I would generally expect something named substr to be a String, not an int.  I would call this end.  And to match, I'd change i to start.

I would call test something like candidate (it's not a test; it's the the thing to be tested), but I don't actually think that you need it.  Consider what happens if you use Cadoiz's suggestion instead and avoid taking the substring.

         for (int start = 0, end = palindromeSize - 1; end < str.length(); start++, end++) {
            if (isPalindrome(str, start, end)) {
                return str.substring(start, end + 1);
            }
         }

Although I wouldn't be surprised if the compiler optimizes out the duplicate strings anyway.

I also changed the parameters slightly.  Since we don't take the substring until we are ready to return, we don't need end to match substring.  This saves us a bunch of small math operations in isPalindrome.

Work with the right data structure

Rather than work with the String, I'd probably work with the underlying character array.

    public static boolean isPalindrome(char[] characters, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (characters[i] != characters[j]) {
                return false;
            }
        }

        return true;
    }

We lose the possibility of trimming the string, but you weren't using that.  It would be more efficient to do that work just once on the original string anyway.

As in your original, I assume that start and end will be reasonable values.  E.g. that end will be greater than or equal to start, and both will be in range for the array.  That's not hard

        if (start > end || start < 0 || end >= characters.length) {
            throw new IllegalArgumentException();
        }

but you don't have any exception handling anyway.  Also note that the last two of those cases will throw more specific exceptions if you let them go through.

    public static String findLargestPalindrome(String str) {
        char [] characters = str.toCharArray();

        // start with the whole string and work down to single characters
        for (int palindromeWidth = str.length() - 1; palindromeWidth >= 0; palindromeWidth--) {
            for (int start = 0, end = palindromeWidth; end < str.length(); start++, end++) {
                if (isPalindrome(characters, start, end)) {
                    return str.substring(start, end + 1);
                }
            }
        }

        return null;
    }

This version calls isPalindrome with the character array and the starting and ending indexes.

I'm renamed palindromeSize.  Note that I defined it slightly differently than you did.  Hopefully the name palindromeWidth is less confusing.  Perhaps a name like distance might be clearer.