Binary expression tree node with two possible states I am building out a binary expression tree and shown below is an implementation of the tree's node.

The node can be either a leaf or non-leaf, with leaves having Integer type values and non-leaves having ExpressionTreeNodeOperands type values. Leaves may have neither left nor right child nodes, and non-leaves must have both left and right child nodes.

I feel like this could be solved more appropriately using inheritance but can't seem to wrap my head around the generic Object member.

public class ExpressionTreeNode {

    private Object value;
    private ExpressionTreeNode leftNode;
    private ExpressionTreeNode rightNode;

    public ExpressionTreeNode(Object value) {
        this(value, null, null);
    }

    public ExpressionTreeNode(Object value, ExpressionTreeNode leftNode, ExpressionTreeNode rightNode) {

        if (value == null || (!(value instanceof Integer) && !(value instanceof ExpressionTreeNodeOperands))) {
            throw new IllegalArgumentException("Illegal argument: value must be non-null with a type of Integer or ExpressionTreeNodeOperand");
        }

        if (leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
            throw new IllegalStateException("Illegal state: leftNode and rightNode should both be null or non-null alike");
        }

        if ((value instanceof Integer) && (leftNode != null && rightNode != null)) {
            throw new IllegalStateException("Illegal state: non-operand non-leaf node");
        }

        if (!(value instanceof Integer) && leftNode == null && rightNode == null) {
            throw new IllegalStateException("Illegal state: non-integer leaf node");
        }

        this.value = value;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public boolean isLeafNode() {
        return (leftNode == null) && (rightNode == null);
    }

    public Object getValue() {
        return value;
    }

    public ExpressionTreeNode getLeftNode() {
        return leftNode;
    }

    public ExpressionTreeNode getRightNode() {
        return rightNode;
    }
}

This is a perfect situation to introduce an interface. What you want to model is a tree-like structure, with nodes having a left and right subtree and leaf containing an integer value.

Your current code models this by having a single ExpressionTreeNode class, handling both cases of having a node with a left and right operand, and a leaf. What shows that this class has too much responsibility is the overhead you need to have to ensure its consistency:

if (value == null || (!(value instanceof Integer) && !(value instanceof ExpressionTreeNodeOperands))) {
    throw new IllegalArgumentException("Illegal argument: value must be non-null with a type of Integer or ExpressionTreeNodeOperand");
}

if (leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
    throw new IllegalStateException("Illegal state: leftNode and rightNode should both be null or non-null alike");
}

if ((value instanceof Integer) && (leftNode != null && rightNode != null)) {
    throw new IllegalStateException("Illegal state: non-operand non-leaf node");
}

if (!(value instanceof Integer) && leftNode == null && rightNode == null) {
    throw new IllegalStateException("Illegal state: non-integer leaf node");
}

That is a lot of code to make sure that the node has a proper state after its construction. It also makes assumptions on the given arguments (namely, that you cannot pass a value that isn't an Integer or a ExpressionTreeNodeOperands): this is reasonable when well-documented but such constraints, if possible, would be preferable to ensure at compile-time.

For example, it will also compile if the caller gives an integer value along with a node, only to fail at run-time because it is incorrect.

The model you want to have here shows that, in fact, 3 classes need to be introduced:

an ExpressionTree interface, that represents the tree-like structure.
an ExpressionTreeNodeOperands class that would represent a node in the tree. A node would have 2 members: a left and a right subtree, represented as two members of type ExpressionTree.
a Leaf class that would represent a leaf in the tree. This class would just have one member of type int.

A sample code would be the following:

interface ExpressionTree {
    boolean isLeaf();
}

class ExpressionTreeNodeOperands implements ExpressionTree {

    private ExpressionTree left;
    private ExpressionTree right;

    public ExpressionTreeNodeOperands(ExpressionTree left, ExpressionTree right) {
        this.left = Objects.requireNonNull(left);
        this.right = Objects.requireNonNull(right);
    }

    @Override
    public boolean isLeaf() {
        return false;
    }

}

class Leaf implements ExpressionTree {

    private int value;

    public Leaf(int value) {
        this.value = value;
    }

    @Override
    public boolean isLeaf() {
        return true;
    }

}

Notice a couple of things:

Leaf is now constructed directly with an int and you cannot construct it without one. Also, it is not a boxed Integer: null values were not permitted before and are simply not possible now.
ExpressionTreeNodeOperands is constructed with two arguments: the left and right sub-tree, which could be another ExpressionTreeNodeOperands, or a Leaf. It also calls requireNonNull to make sure that the given arguments are non-null.

The concern are now clearly separated: the node handles only its sub-trees, and the leaf handles only its value.

With this base, you can add convenience methods, like isLeaf, that would always return false for a node, and always return true for a leaf.

Then, depending on your actual usage, you may not even need a getLeft() and getRight() getters to retrieve the left and right node sub-trees. Let's take an example usage where we want to perform an infix traversal. You could add a String infix(); method inside the interface ExpressionTree, that would return a String representation:

@Override
public String infix() {
    return "(" + left.infix() + "," + right.infix() + ")";
}

for a node, and

@Override
public String infix() {
    return String.valueOf(value);
}

for a leaf. And then you can have:

ExpressionTree tree = new ExpressionTreeNodeOperands(new ExpressionTreeNodeOperands(new Leaf(2), new Leaf(1)), new Leaf(3));
System.out.println(tree.infix()); // prints ((2,1),3)


Using Python to get data from a Star Wars API I am learning Python (about 6 months in, sporadically) and today I decided to write a script to download JSON information from an API.

To start, I wrote a one-page script with a few functions.

The script does the following:

The user enters the script on the terminal with a search value.
The script gets the response information from the Star Wars API (https://swapi.co). This is an open API, so I don't need any keys or tokens.
If the API returns one value, the information is displayed immediately.
If the API returns several values, the script prompts the user to make a choice. Then the information is displayed.

Right now, the script only works for people in the SWAPI (e.g., Luke Skywalker).

Any feedback on my code would be helpful.

#!/usr/bin/python3

'''Script to get information from https://swapi.co/'''

import requests
import json
import sys

#TODO: Print useful information such as movie titles or names of worlds instead of showing links
#Break up URL to allow for more dynamic searching in the future. Right now, script only handles the people parameter when getting info from the API.

UNDERLINE_LEN = 30

def show(data, index=0):
    '''
        Displays an individual Swapi object.
        data = data retrieved from api
        index = which entry to select. Default is 0 for single item lists.
    '''
    info = data['results'][index]
    print()
    print('-' * UNDERLINE_LEN)
    print("Name : {0}\n{1}".format(data['results'][index]['name'], '-' * UNDERLINE_LEN))
    for k, v in info.items():
        if type(v) is list:
            counter = 0
            print(k, ':')
            for j in v:
                print("\t{0}".format(v[counter]))
                counter += 1
        else:
            if k != 'name':
                print(k, ':', v)

def show_choices(data):
    '''Shows a list of Swapi objects and prompts users to select an object [integer]'''
    info = data['results']
    counter = 0
    for i in info:
        print("[{0}] {1}".format(counter + 1, data['results'][counter]['name']))
        counter += 1
    print()
    choice = int(input("Which item would you like to view? "))
    try:
        show(data, choice - 1)
    except IndexError as ie:
        print(ie)

def grab():
    '''Main function.'''
    try:
        search = sys.argv[1]
        url = 'https://swapi.co/api/people/?search={0}'.format(search)      #need to divide url to make search process more dynamic
        r = requests.get(url)
        data = json.loads(r.text)
        if data is not None:
            numResults = int(data['count'])
            txt = "results"
            if numResults == 1:
                txt = "result"
            resText = "{0} {1} found for search parameter '{2}'".format(numResults, txt, search)
            print(resText)
            if numResults == 1:
                show(data)
            else:
                show_choices(data)
    except Exception as e:
        print(e)

grab()

You should never compose URLs using this technique!

search = sys.argv[1]
url = 'https://swapi.co/api/people/?search={0}'.format(search)      #need to divide url to make search process more dynamic
r = requests.get(url)

Query string parameters need to be percent-encoded.  The Python Requests library provides a correct way to do it:

search = sys.argv[1]
url = 'https://swapi.co/api/people/'
r = requests.get(url, params={'search': search})

Going further, I would caution you to never concatenate any user-supplied string to form another string that will be interpreted by some computer system.  You must first considering the escaping mechanism.  SQL injections, cross-site scripting, LDAP injection, etc. — they're all vulnerabilities that result from this same kind of carelessness.


Take a list of nums and return max and min Exercise 6: Rewrite the program that prompts the user for a list of numbers and prints out the maximum and minimum of the numbers at the end when the user enters “done”. Write the program to store the numbers the user enters in a list and use the max() and min() functions to compute the maximum and minimum numbers after the loop completes.

num_list = []

num = input('Please enter a number: ')

while num != 'done' and num != 'DONE':
    try:
        num_list.append(int(num))
        num = input('Please enter a number: ')
    except:
        num = input("Not a number. Please enter a number Or 'done' to finish: ")

try:
    print('Maximum number: ', max(num_list))
    print('Minimum number: ', min(num_list))
except:
    print('NO INPUT!')

Avoid repeating yourself: use a single input call; it isn't much here, but it is easily error-prone if your "initialization" phase is several steps long. The usual idiom in such case is to use a while True loop and test the condition after the initialization to break if necessary.
Please avoid bare except, this is a bad habit to get into. This will catch all exceptions, including the ones you're not expecting (such as KeyboardInterrupt if the user hits Ctrl+C) and, thus, not ready to handle. In both cases, you’re expecting ValueErrors here.
Use functions, this will make your code much more reusable:

def ask_user_number_list():
    num_list = []
    while True:
        num = input('Please enter a number or 'done' to finish: ')
        if num.lower() == 'done':
            break

        try:
            number = int(num)
        except ValueError:
            print('Invalid input')
        else:
            num_list.append(number)

    return num_list

def search_min_and_max(lst):
    try:
        return min(lst), max(lst)
    except ValueError:
        return None

if __name__ == '__main__':
    bounds = search_min_and_max(ask_user_number_list())
    if bounds is None:
        print('NO INPUT!')
    else:
        print('Maximum number: ', bounds[-1])
        print('Minimum number: ', bounds[0])


Getting device type from user agent in Python - is explicit better than implicit? I'm debating with my colleagues which code is better:
user_agent is a class instance. The class itself comes from a third-party library so we don't have any control over it.

1.

def _get_ua_device_type(user_agent):
    property_to_type = {'is_mobile': 'mobile', 'is_tablet': 'tablet', 'is_pc': 'pc', 'is_bot': 'bot'}
    for prop, type in property_to_type.items():
        if get_attr(user_agent, prop) is True:
            return type
    return 'unknown'

2.

def _get_ua_device_type(user_agent):
    for type in ('mobile', 'tablet', 'pc', 'bot'):
        if get_attr(user_agent, f'is_{type}') is True:
            return type
    return 'unknown'

3.

def _get_ua_device_type(user_agent):
    if user_agent.is_mobile:
        return 'mobile'
    if user_agent.is_tablet:
        return 'tablet'
    if user_agent.is_pc:
        return 'pc'
    if user_agent.is_bot:
        return 'bot'
    return 'unknown'

Things we discussed:

Static code is easier to understand than dynamic.
Static code is easier to test.
Dynamic code is declarative and more idiomatic than metameric ifs.
Dynamic code will be as hard/easy to understand regardless of the number of choices.
It's hard to anticipate the number of choices up-front so why start with a more complex dynamic form?
Assuming that predicate names are derived from type names is bad.
Where is the line when code is spaghetti-like and should be rewritten in a more dynamic way?
What about Zen of Python (“Explicit is better than implicit.“, “Flat is better than nested.“, “Readability counts.”, “Simple is better than complex.”)

Do you have your own thoughts/suggestions?

Equivalence considerations

1 is not the same as 2 or 3 for older versions of Python. In 2 and 3, you have an ordered execution sequence that determines the priority of returned variables. In 1, you have a dictionary whose order is inherently unknown. This might be OK for you, or it might not. If it isn't, a workaround is to use an OrderedDict.

For newer versions of Python (3.6+) this should not be an issue.

Drop boolean redundancy

No matter what you do, you should probably stop writing is True if you know that the target variable is already boolean. If the variable can have mixed type (i.e. integer or boolean), which is bad but sadly often possible in Python, and if you care about this, then you need to keep is True.

Ownership

Do you control the design of user_agent? If so, then you can enforce a stable interface, and my favourite of your options is 2, simply because it's more concise. If not, then only (3) would work well with static analysis to catch a changing interface.

Other options

try:
    return next(type for type in ('mobile', 'tablet', 'pc', 'bot')
                if get_attr(user_agent, f'is_{type}'))
except StopIteration:
    return 'unknown'

The bigger problem

is that you're representing an idea of a type with multiple booleans when it should be a single enum-style variable. If you can change your user agent to do this, do this. If not, you may want to consider writing a multivariate-boolean-to-single-enum shim class to sanitize the rest of your business logic.


Logical Predicate Class For a while now I've been playing around with various ways of passing a logical predicate E.G. >= someValue as an argument to a function. (see: If ComparisonIsTrue(thisPost, ComparisonOperator.NotEqualTo, goodCode) Then Me.Answer and a global enum for comparison operators)

In the end, I've decided to build a CLS_Comparison_Predicate class with Operator and RightValue properties, with a Compare() function that takes a LeftValue as an argument.

Thoughts?

Example Usage:

Dim predicate As CLS_Comparison_Predicate
Set predicate = New CLS_Comparison_Predicate

predicate.Operator = GreaterThan
predicate.RightValue = 9000

If predicate.Compare(inputValue) Then
    MsgBox "It's over 9,000!"
End If

Enum:

Public Enum ComparisonOperator
    NotEqualTo = 0
    LessThan = 1
    LessThanOrEqualTo = 2
    EqualTo = 3
    GreaterThanOrEqualTo = 4
    GreaterThan = 5
End Enum

Code:

Option Explicit

Private pOperator As ComparisonOperator
Private pRightValue As Variant

Private Const NULL_ERROR_TEXT As String = "Invalid Compare input. Cannot compare against Null"
Private Const OBJECT_ERROR_TEXT As String = "Invalid compare input. Input must be a value, not an object"

Public Property Let Operator(ByVal inputOperator As ComparisonOperator)
    pOperator = inputOperator
End Property

Public Property Let RightValue(ByVal inputValue As Variant)
    If IsNull(inputValue) Then
        PrintErrorMessage NULL_ERROR_TEXT
        Stop
    ElseIf IsObject(inputValue) Then
        PrintErrorMessage OBJECT_ERROR_TEXT
        Stop
    End If

    pRightValue = inputValue
End Property

Public Function Compare(ByVal leftValue As Variant) As Boolean

    If IsNull(leftValue) Then
        PrintErrorMessage NULL_ERROR_TEXT
        Stop
    ElseIf IsObject(leftValue) Then
        PrintErrorMessage OBJECT_ERROR_TEXT
        Stop
    End If

    Dim isTrue As Boolean
    Select Case pOperator
        Case NotEqualTo
            isTrue = (leftValue <> pRightValue)

        Case LessThan
            isTrue = (leftValue < pRightValue)

        Case LessThanOrEqualTo
            isTrue = (leftValue <= pRightValue)

        Case EqualTo
            isTrue = (leftValue = pRightValue)

        Case GreaterThanOrEqualTo
            isTrue = (leftValue >= pRightValue)

        Case GreaterThan
            isTrue = (leftValue > pRightValue)

        Case Else
            '/ TODO: Error Handling
            Stop
    End Select

    Compare = isTrue

End Function

Stop

This instruction is outright dangerous in any production code (assuming that code could be used in anything that ends up in the hands of users that don't understand what's happening when the VBE pops up). And because it's easy to forget about it and remove every instance of it everywhere, I usually reserve it for debugging only - for example:

CleanFail:
    Stop
    Resume CleanExit
    Resume
End Sub

When debugging, execution breaks at the Stop keyword, and then I can drag the yellow "next instruction" arrow to Resume and jump back at the error-causing line.

If you're going to be outputting an error message and stop execution, you might as well raise an error to do so. Runtime error 5 "Invalid procedure call or argument" is more or less analoguous to .NET's ArgumentException, which seems to be the most accurate existing error to throw/raise here - I'd do it like this:

Err.Raise 5, TypeName(Me), NULL_ERROR_TEXT

That will only PrintErrorMessage if the caller handles the runtime error though, which changes the way your code works. But it's more semantically correct I find.

Same here:

    Case Else
        '/ TODO: Error Handling
        Stop

The function received an invalid argument; there's an existing runtime error specifically for this: just use it!

Public Enum ComparisonOperator
    NotEqualTo = 0
    LessThan = 1
    LessThanOrEqualTo = 2
    EqualTo = 3
    GreaterThanOrEqualTo = 4
    GreaterThan = 5
End Enum

Every single enum value here has the same value is would have if an explicit value wasn't specified, and the values themselves are meaningless. Better leave 'em out and only specify explicit values when these values mean something or can be combined (and then they would be valued with powers of 2).

Objects are indeed not comparable. But not because they're objects - because in and by themselves, they don't specify how they should be compared. The .NET framework solved this problem by introducing a fairly simple interface, IComparable:

Option Explicit

Public Function CompareTo(ByVal other As Variant) As Integer
End Function

Given an object that implements this interface, your code would be able to evaluate all operators, assuming both operands are of the same type; so instead of systematically refusing to compare objects, you could instead raise an error that says something like "Both objects must be the same type and implement IComparable".

Private pOperator As ComparisonOperator
Private pRightValue As Variant

I've seen p used to mean "parameter". Not sure what it stands for here, as typically the Hungarian prefix would be m_ for module-scope variables.

I like to solve this problem like this:

Private Type TComparer
    Operator As ComparisonOperator
    RightValue As Variant
End Type
Private this As TComparer

And then you don't need prefixes anymore:

Public Property Let Operator(ByVal value As ComparisonOperator)
    this.Operator = value
End Property

Notice I'm using a general-purpose value parameter in property setters (let/set); this makes properties read consistently, and pretty much identical to modern VB.

Public Property Let RightValue(ByVal value As Variant)
    If IsNull(value) Then
        PrintErrorMessage NULL_ERROR_TEXT
        Stop
    ElseIf IsObject(value) Then
        PrintErrorMessage OBJECT_ERROR_TEXT
        Stop
    End If

    this.RightValue = value
End Property

Are you sure IsNull is doing what you're using it for here?

  The Null value indicates that the Variant contains no valid data. Null is not the same as Empty, which indicates that a variable has not yet been initialized. It is also not the same as a zero-length string (""), which is sometimes referred to as a null string.

  https://msdn.microsoft.com/en-us/library/office/gg278616.aspx

It's actually pretty hard to supply a Null value by accident to a required Variant parameter. I'm not saying the check isn't needed, just that it's rather uncommon in VBA code. I'm not even sure how one would manage to actually pass a null in there without explicitly specifying Null.

It's good that you're checking for Null. But then, why stop there? Why not check for vbEmpty? If one can pass Null, they could also pass vbEmpty... and how would you compare against vbEmpty?


getDerivedStateFromProps Starting from React 16.3 there are some new lifecycle methods introduced. One of them is the static getDerivedStateFromProps(props,state) method. This method essentially synchronizes properties and state.

The props and state of a react component aren't always a one-on-one match. But for simple components often a couple of props do match exactly on the state.

It's not strictly necessary to have this getDerivedStateFromProps(...) method actually. If your component doesn't really have an internal state, then there is no need to worry about it.

Anyway, in a case where there is an exact match of props and state I am trying to find the most elegant way to write this code.

The following is rather verbose:

static getDerivedStateFromProps(props, state) {
  // these 3 properties can change over time.
  const activeBaseNode = props.activeBaseNode;
  const filterOID = props.filterOID;
  const quickFilterRequest = props.quickFilterRequest;

  // compare them to the state
  if ((state.filterOID !== filterOID) ||
    (state.activeBaseNode !== activeBaseNode) ||
    (state.quickFilterRequest !== quickFilterRequest)) {

    // updates the state
    return ({ activeBaseNode, filterOID, quickFilterRequest });
  }

  // no changes --> no updates
  return null;
}

Ted's answer is quite readable to me.

You could use some to detect if you need to submit changes as that is semantically closer to what you are doing:

if (['activeBaseNode', 'filterOID', 'quickFilterRequest']
    .some(prop => state[prop] !== props[prop])

It's perhaps nicer to reverse the logic with every and early exit, then extract all the properties only when you need them. Here I'm doing it with a function, avoiding defining three consts:

static getDerivedStateFromProps(props, state) {
  if (['activeBaseNode', 'filterOID', 'quickFilterRequest']
    .every(prop => state[prop] === props[prop]) return null

  return (({activeBaseNode, filterOID, quickFilterRequest}) =>
         ( {activeBaseNode, filterOID, quickFilterRequest}))(props)

That's cryptic and short approach.

I don't really like that the names of the properties are repeated three times in all the solutions. To avoid that, a reduce can be used to build the properties that need to be updated:

const toUpdate = ['activeBaseNode', 'filterOID', 'quickFilterRequest']
  .find(prop => state[prop] !== props[prop])
  .reduce((m,k) => m[k] = props[k], {})
return Object.keys(toUpdate).length == 0 ? null : toUpdate

Once you get used to it, I think that's the clearest. It's got the essence of the problem and nothing more: the names of the properties, that the state != the props, and that you return null if nothing is changing.


Form data to object to HTML I have a form. When I click the save button, I want to create an object from the data and pass that info to HTML elements on the same page (div.form_content).

I decided, instead of creating a variable for each HTML element to create an array of HTML elements.  I know the first HTML element is going to contain the first object property, the second html element will contain the second obj property, and so on...

What I have done below seems a little repetitive and not very DRY, and I was wondering if someone could recommend a better way.  For example, if my form has to grow to 12 input fields, what I am doing now would be pretty clunky.  I tried running a loop to prevent the line-by-line assignments, but couldn't figure it out. (By the way, I needed to create an object from the form data because I will need to stringify it to JSON notation to pass to the server, but I got that part.)

$('#save').click(function() {

    var form_Array = $('form').serializeArray();

    // Create an Array of HTML elements
    var el_Array = $('div.form_content').children();

    // create empty object
    var obj = {};

    // loop through serialized form object and assign new object keys from this.name and their values from this.value
    $.each(form_Array, function() {
        obj[this.name] = this.value;
    });

    // populate the html elements with contents of the newly created object
    $(el_Array[0]).html(obj.fname);
    $(el_Array[1]).html(obj.lname);
    $(el_Array[2]).html(obj.phone);
    $(el_Array[3]).html(obj.fax);

});

I'd say give your "output" elements a data-* attribute that matches the name of the form value it should contain. For instance:

Then, you can do something like:

$('#save').click(function() {
  var values = $('form').serializeArray(),
      output = $('#values');

  $.each(values, function() {
    output.children("[data-key='" + this.name + "']").text(this.value);
  });
});

Here's a demo


Interview task to efficiently find compact representation of nodes in tree and find big O time I recently had an interview problem where I was asked to find a compact representation of nodes in a tree.

As an example, consider the following tree:

                      A
                   /  |  \
                  B   C   D
                / | \     | \
               E  F  G    H  I
              /\
              J K

The task was, given a list of node values, find a compact list of node values that completely describes the list given. A node value being in the list implictly means that all it's children are in the list as well and viceversa.

As a few examples, for the tree given:

compact([A]) = [A]
compact([B, C, D, J]) = [A]
compact([J, K]) = [E]
compact([J, K, F, G]) = [B]
compact([E, F, G, H]) = [B, H]
compact([H, I, D]) = [D]

This was my recursive attempt in python (from memory so may be some mistakes/syntax errors), which would be called with the root of the tree first. I was told:

I don't need to check for empty trees
I can assume that each node has basic tree methods (so can check it's value, if it's a leaf node etc).
The non-compact list of nodes values is passed in through node_list and I was told that there would be no duplicates in this list and that each value in it would correspond to a node in the tree

def compacted_tree(node, node_list):

    compact_list = []

    if node.value in node_list:
        #if this node is in the list then it is it's own consise representation
        return [node.value]

    allChildrenInCompactList = True

    for child in node.get_children():
        compact_list.extend(compacted_tree(child, node_list))

        if (allChildrenInCompactList):
            #only keep checking this if it's still true
            allChildrenInCompactList = child.value in compact_list

    if (allChildrenInCompactList and !node.isleaf()):
        #all my children are in the list so the compact list should just be me
        return [node.value]

    return compact_list

I said that this would run with complexity \$O(n^2)\$ (with n=number of nodes in the tree) as in the worst case, every node needs to be visited and, in the worst case, every node needs to check all it's children against the node_list which is an \$O(n)\$ operation too. I said the space complexity should be \$O(n)\$ as in the worst case you may have to add all your nodes to the compact_list before it can simplify.

It was hard to get a good read of how I went from the interview but I'm yet to get a call back. The interviewer hinted that the task could have been done with better complexity but I fail to see how. He also said that my time complexity should have been not just in terms of the number of nodes in the tree but also the length of the node_list.

Is anyone able to tell me how I should've approached this problem/analysis better?

This is, strictly speaking, off-topic for Code Review, because it's a question of algorithm design, not one of implementation. But I'll try to explain how I would approach it.

1. Notation

In order to describe an algorithm and its performance, we need some notation. So:

\$n\$ is the number of nodes in the tree;
\$M\$ is the set of nodes we want to compact;
\$m = |M|\$, the initial number of nodes in \$M\$;
\$C(x)\$ is the set of children of the node \$x\$ in the tree.
\$P(x)\$ is the parent of the node \$x\$ in the tree.

I'm going to assume that I can test for membership in a set in amortized time \$O(1)\$ and add or remove an element from a set in amortized time \$O(1)\$. This means we need to use Python's set data structure.

2. Eliminate redundancies

The set \$M\$ might be redundant: namely it might contain nodes \$x\$ and \$y\$ such that \$y\$ is an ancestor of \$x\$ (that is, \$y = P(x)\$ or \$y = P(P(x))\$ or ...). All such \$x\$ need to be removed from \$M\$. For example, the set \$\{B, C, D, J\}\$ is redundant because \$B = P(P(J))\$ and so \$J\$ can be removed.

This can be done in one depth-first traversal over the tree:

Initialize \$k\$ to 0.
On entering a node \$x ∈ M\$: if \$k = 0\$, set \$k = 1\$, otherwise remove \$x\$ from \$M\$.
On leaving a node \$x ∈ M\$: set \$k = 0\$.

This visits each node once and so takes time \$O(n)\$.

3. The naïve algorithm

Any algorithm for this problem is going to have to find nodes all of whose children are in the set of nodes to be compacted (that is, to find nodes \$x\$ where \$C(x) ⊆ M\$), and update the set of nodes accordingly.

So the first algorithm that springs to mind is the simple one in which we repeatedly search the whole tree for a node \$x\$ matching that condition, stopping when we can't find any more such nodes. Formally:

Eliminate redundancies from \$M\$ as described above.
For each non-leaf node \$x\$ in the tree:
  If \$C(x) ⊆ M\$ then:
    Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
    Go to step 2.

What's the complexity of this algorithm? Step 1 takes time \$O(n)\$. Step 3 takes \$O(m)\$ (since \$M\$ stays the same or gets smaller as the algorithm progresses) and so does step 4 (for the same reason), so each loop 2–5 over the nodes in the tree takes time \$O(mn)\$, and we run that loop \$O(n)\$ times. The overall complexity is thus \$O(mn^2)\$.

4. Looking at the nodes in the right order

How can we improve this algorithm? It would be nice not to have to restart the loop over the nodes in the tree each time we update \$M\$. The reason we restart the loop is because updating \$M\$ might make a compaction available that we already considered and rejected. So we have to start over from the beginning so that we don't miss any compactions.

But if we looked at the nodes in the right order: that is, if we always looked at the children of \$x\$ before looking at \$x\$, then this couldn't happen. This order of traversing a tree is known as post-order.

So the revised algorithm looks like this:

Eliminate redundancies from \$M\$.
For each non-leaf node \$x\$ in post-order:
  If \$C(x) ⊆ M\$ then:
    Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$

Here the loop 2–4 takes \$O(mn)\$ as before, but we only execute it once, for an overall complexity of \$O(mn)\$.

5. Speeding up the subset test

The step that is contributing the most to the overall complexity is the subset test \$C(x) ⊆ M\$, which is executed \$O(n)\$ times and costs \$O(m)\$. How could we speed this up? The insight here is that all we need to know is the number of items in \$C(x) ∩ M\$, because when \$|C(x) ∩ M| = |C(x)|\$ then \$C(x) ⊆ M\$. So we can maintain a count for each node, of the number of its children that are in \$M\$, and just compare the counts. This results in the following algorithm:

Eliminate redundancies from \$M\$.
Initialize a map \$K\$ from nodes to non-negative integers such that \$K(x) = |C(x) ∩ M|\$, the number of children of \$x\$ that are in the set of nodes to be compacted.
For each non-leaf node \$x\$ in post-order:
  If \$K(x) = |C(x)|\$ then:
    Update \$M\$ to \$(M \setminus C(x)) ∪ \{x\}\$
    Update \$K(P(x))\$ to \$K(P(x)) + 1\$

Here step 1 takes \$O(n)\$, step 2 takes \$O(m)\$, the loop 3–6 is executed \$O(n)\$ times, steps 4 and 6 take \$O(1)\$ each time they are executed, so \$O(n)\$ overall, and step 5 takes \$O(n)\$ overall since each node can be removed from \$M\$ at most once and added to \$M\$ at most once. So the overall complexity is \$O(n)\$.


Get Next Working Date, skip weekends and holidays The object is to be able to pass some dates (start date, holiday) and the number of days you want to skip. We only want to skip working days, not weekends and holidays.

Just let me know what you'd do different than what I have. The code works, but I was told there are issues with it, but not told what issues they are.

function getWDays($startDate,$holiday,$wDays){

$d = new DateTime( $startDate );
$t = $d->getTimestamp();
$h = strtotime($holiday);

// loop for $wDays days
for($i=0; $i<$wDays; $i++){

    // 1 day = 86400 seconds
    $addDay = 86400;

    $nextDay = date('w', ($t+$addDay));
    if($nextDay == 0 || $nextDay == 6) {
        $i--;
    }
    $t = $t+$addDay;
    if ($t == $h) {
        // lets make sure the holiday isn't one of our weekends
        if(!$nextDay == 0 || !$nextDay == 6) {
            $t = $t+$addDay;
        }
    }
}

$d->setTimestamp($t);

return $d->format( 'Y-m-d' );

}

echo getWDays("2013-08-29","2013-09-02", 3)

Here is another way of doing the same thing

<?php

function getWDays($startDate,$holiday,$wDays) {

    // using + weekdays excludes weekends
    $new_date = date('Y-m-d', strtotime("{$startDate} +{$wDays} weekdays"));

    $holiday_ts = strtotime($holiday);

    // if holiday falls between start date and new date, then account for it
    if ($holiday_ts >= strtotime($startDate) && $holiday_ts <= strtotime($new_date)) {

        // check if the holiday falls on a working day
        $h = date('w', $holiday_ts);
            if ($h != 0 && $h != 6 ) {
            // holiday falls on a working day, add an extra working day
            $new_date = date('Y-m-d', strtotime("{$new_date} + 1 weekdays"));
        }
    }

    return $new_date;
}

// here is an example
$start = "2013-08-29";
$holiday = "2013-09-02";
$wDays = 3;

echo "Start: ",date("Y-m-d D", strtotime($start)),"
";
echo "Holiday: ",date("Y-m-d D", strtotime($holiday)),"
";
echo "WDays: $wDays
";

echo getWDays($start, $holiday, $wDays);


Plotting a graph of survey answers in Laravel I'm using PHP (Laravel) to iterate over the survey_answers table and build datasets which I can show in a graph. I'm just wondering if this is the way to go.

ChartFactory.php

public static function buildFromSurvey($survey)
{
    $chart = new Chart($survey->name);

    foreach($survey->answers as $answer) {

        if($chart->hasDataset($answer->user_id)) {
            $dataset = $chart->getDataset($answer->user_id);
        } else {
            $dataset = new Dataset();
            $dataset->setTitle($answer->user->name);
            $dataset->setColor(config('assessment.chart_colors_survey')[0]);
            $dataset->setOwner($answer->user);
            $chart->addDataSet($dataset);
        }

        // Create the category if not exists in this dataset
        if ($dataset->hasDataItem($answer->question->category->name)) {
            $category = $dataset->getDataItem($answer->question->category->name);
            $category->addScore($answer->score);
        } else {
            $category = new Category();
            $category->setName($answer->question->category->name);
            $category->addScore($answer->score);

            $dataset->addDataItem($category);
            $chart->addLabel($answer->question->category->name);
        }
    }

    return $chart;
}

I think my main criticism of this code would be that it is asymmetric in terms of where ownership of instantiating your different object dependencies lives.

For example, in the first conditional around whether Dataset exists on the Chart, why does this code need to own the logic to create and attach a new Dataset?  If the Chart object "owns" the datasets, I would think that perhaps all this code would do is call a Chart::createNewDataset() or similar method to handle the work building a new dataset and setting it on the Chart.

This same concern exists for me with regards to creating Category objects.

I would also strongly recommend using type hinting for the parameter to enforce that you are getting passed a valid survey object.


Database schema for a products and bugs aggregator As an exercise in learning, I'm creating a bugs/issues tracking and "aggregator" web application. A simple app consisting of products, issues, reviews and links related to it. The links will be urls pointing to issues/reviews already created on external sites (bugzillas, stackoverflow, etc). Here is my initial effort towards creating the database schema of the app:

CREATE TABLE PRODUCT (
    ID INTEGER PRIMARY KEY,
    NAME VARCHAR(255), --Samsung Galaxy, Apple iphone, Dell Inspiron, GNOME Desktop, etc.
    VERSION VARCHAR(255), --S5, v3.14, etc.
    IMAGE VARCHAR(255), --PATH TO UPLOADED IMAGE FILE
    CATEGORIES VARCHAR(255),
    TAGS VARCHAR(255),
    CREATOR VARCHAR(255) --EMAIL ADDRESS OF PRODUCT UPLOADER
);

CREATE TABLE REVIEWS (
    ID INTEGER PRIMARY KEY,
    PRODUCT_ID INTEGER,
    CREATOR VARCHAR(255), --EMAIL ADD. OF REVIEWER
);

CREATE TABLE ISSUES(
    ID INTEGER PRIMARY KEY,
    PRODUCT_ID INTE GER,
    CREATOR VARCHAR(255), --EMAIL ADDRESS
    DESCN VARCHAR(255), --DESCRIPTION
    LINKS VARCHAR(255)
);

CREATE TABLE LINKS(
    ID INTEGER PRIMARY KEY,
    PRODUCT_ID INTEGER,
    LINK_TYPE VARCHAR(255), --ISSUE OR REVIEW OR OTHER (STACKOVERFLOW/REDDIT/HN CONTENT)
    DESCN VARCHAR(255), --A SHORT PREVIEW OF LINKED CONTENT
    URL VARCHAR(255),
    LAST_UPDATED DATETIME, --CRAWLER TIMESTAMP
);

CREATE TABLE LINK_VOTES(
    ID INTEGER PRIMARY KEY,
    LINK_ID INTEGER,
    VOTER VARCHAR(255), --EMAIL ADD. OF THE VOTER
    VOTE INTEGER, --1==UP, 0==DOWN
);

Appreciate if you can provide me suggestions, improvements, etc.

CATEGORIES VARCHAR(255),
TAGS VARCHAR(255),

Take care with plural named fields. It's very, very likely that any plural field is secretly a multi-valued field. You might want to extract a "Category" and "Tag" table out of this, so searching for them is easier.

PRODUCT_ID INTE GER,

You've got a space there. Not sure if SQL is okay with that.

Lastly, I think you should put some NOT NULL in there - are you sure every field except the primaries can be NULL? You also seem to be missing foreign keys from one table to another.


1st questions with answers within X hours I recently challenged @Hosch520 with writing a query as such:

  Find first questions with answers posted within 24 hours

And he did great. I figured I would have a go at it too. Turns out I learned valuable things about data subsets, so here I am seeking review.

I did not specify whether to return only the first answer within 24 hours, or all answers within 24 hours, so we went about it a bit differently. The remarks at the top of my query give more details.

In any case, mine returns all answers posted to a new user's first question within 24 hours.

Link to query on SEDE.

/*
 * Author: @Phrancis
 * Title: 1st questions with answers within X hours
 * Date: 2015-04-16
 * Purpose:
 *   To query a new user's first question under the condition that
 *   the question received one or more answers within a certain number of
 *   hours (default 24), as well as all qualifying answers, and both users'
 *   name and current reputation. It also calculates the interval between
 *   question and answers.
*/

DECLARE @HoursElapsed AS INT;
SET @HoursElapsed = ##NumberOfHours:float?24##;
-- NumberOfHours: Hours elapsed between OP 1st question and answers following it "Decimals are allowed"

DECLARE @QuestionType INT;
DECLARE @AnswerType INT;
SET @QuestionType = 1;
SET @AnswerType = 2;

WITH AllFirstQuestions AS (
  SELECT
      OwnerUserId
    , Id
  FROM Posts
  WHERE CreationDate IN (SELECT MIN(CreationDate) FROM Posts GROUP BY OwnerUserId)
  AND PostTypeId = @QuestionType
)

SELECT
    qUser.Id AS [User Link]
  , qUser.Reputation AS [Q OP Rep]
  , firstQ.Id AS [Post Link]
  , q.CreationDate AS [Q Date]
  , CONVERT( DECIMAL(10,2), DATEDIFF(MINUTE, q.CreationDate, a.CreationDate) /60.0 ) AS [Hours Elapsed]
  , aUser.Id AS [User Link]
  , aUser.Reputation AS [A OP Rep]
  , a.Id AS [Post Link]
  , a.CreationDate AS [A Date]

FROM Posts AS q
INNER JOIN AllFirstQuestions AS firstQ
  ON q.Id = firstQ.Id
INNER JOIN Posts AS a
  ON q.Id = a.ParentId
  AND q.PostTypeId = @QuestionType
  AND a.PostTypeId = @AnswerType
INNER JOIN Users qUser
  ON q.OwnerUserId = qUser.Id
 AND q.OwnerUserId IS NOT NULL
INNER JOIN Users aUser
  ON a.OwnerUserId = aUser.Id
 AND a.OwnerUserId IS NOT NULL

 WHERE a.CreationDate <= (DATEADD(HOUR, @HoursElapsed, a.CreationDate))
  AND DATEDIFF(HOUR, q.CreationDate, a.CreationDate) <= @HoursElapsed
/* This condition is needed because some "fluke" questions
 * have an answer creation time that is before the question's.
 * Usually due to complicated migrations.
 */
  AND DATEDIFF(HOUR, q.CreationDate, a.CreationDate) >= 0

ORDER BY
    q.CreationDate DESC
  , aUser.Reputation DESC;

I'm looking to see if this can be improved. Maybe mine is too much? I personally feel it is reasonable, and it executes pretty fast:

  14662 rows returned in 194 ms

I scanned through the output for a while to make sure I did not have multiple first questions by the same user, and AFAIK, I do not. I'm open to any criticism to make this better!

a.CreationDate <= (DATEADD(HOUR, @HoursElapsed, a.CreationDate))

This first condition of your WHERE clause either needs to be removed or needs some explanation.

For any non-negative value of @HoursElapsed, this will always return true.  Perhaps, the intent was to use q.CreationDate as the third argument of the DATEADD function?

Otherwise, this condition just says:

x <= x + y

The <= can return true for any non-negative y value.  No matter the value of x, x plus some non-negative y will always be some number larger than (or in the case of y=0, equal to) x.

I don't like your indention style.  Specifically, in your CTE, I don't like that the AND in your WHERE clause gets the same indention level as the rest of the query.  In your main query, I don't like that your INNER JOIN have the same indention level as the rest of the query (and the WHERE appears to have a space in front of it.

Importantly, any SQL query has up to eight primary clauses.  WITH, SELECT, INTO, FROM, WHERE, GROUP BY, HAVING, and ORDER BY.  Everything else is a part of one of these clauses.  These 8 clauses should have zero indentation relative to the query as a whole, and everything else should be indented by at least one level (and I personally prefer four spaces, but I know SEDE default is two spaces).

Our major offender here is the massive list of INNER JOIN subclauses (helper elves?) within the FROM clause.

Keeping in mind the comments I already made about the first part of your WHERE clause, we could simplify the entire WHERE clause into simply just this:

WHERE a.CreationDate BETWEEN q.CreationDate AND DATEADD(HOUR,@HoursElapsed,q.CreationDate)

Our FROM can be massively simplified.

First, there's no reason our CTE can't include the CreationDate.  That completely eliminates the need for us to have the Posts table we labeled q.  And that can clean up some other nastiness, like q.PostTypeId = @QuestionType (our CTE already narrows that dataset down to just questions).

Bearing in mind the recommended change to the CTE (just add CreationDate to the select list), I recommend a FROM that looks more like this:

FROM AllFirstQuestions q
    INNER JOIN Posts as a ON a.PostTypeId = @AnswerType AND a.ParentId = q.Id
    INNER JOIN Users qUser ON qUser.Id = q.OwnerUserId
    INNER JOIN Users aUser ON aUser.Id = a.OwnerUserId

I'm guessing that a.PostTypeId = @AnswerType is probably unnecessary, but I don't know enough about SEDE.

I'm going to wager though that the Id column of the Users table is an indexed, auto-incrementing, non-null primary key.  We don't have to include a AND alias.OwnerUserId IS NOT NULL on joining it.  Any post with a NULL owner user id will be eliminated by virtue of the fact that there are no NULLs in the Id column of the Users table (and even if there were, null wouldn't join to null... I don't believe).

Finally, this is SEDE specific, but it doesn't make sense to allow the user to enter a decimal number for hours elapsed.  You're saving it as an INT, so it's immediately converted to an INT and the decimal part is lost before you even do anything with it.  Moreover, SQL's DATEADD (one place you use @HoursElapsed) takes an INT, so it doesn't make sense to even think about passing anything else here, and SQL's DATEDIFF (you compare result of this to @HoursElapsed) returns an INT, so it also doesn't make a whole lot of sense to compare to a floating point number here.  I think you just need to not allow the user to enter decimal places, since they're 100% ignored no matter what.  Allowing the user to enter decimal places gives the false impression that your query is doing something it's not.


Search for ways in OpenStreetMap extract What does it do ?

Looks in big XML files (1-3 GB) for given parameters that I need in my project, appends them to lists and finally exports both of them to the CSV files.

My XML scheme

I need to get child named 'v', which is  value of specific child 'k' nested in tag named 'tag' which is nested within parent 'way'.

What I tried

IBM's take on big xml files

Plus various scripts from StackExchange.

Performance

My function needs 50% less time to parse XML than above method, any other I tried or I was able to try, because with some I was unable to figure things out and given up on them.

My goal

To get some tips on my code, hopefully find way to speed it up.
I need to parse about 20 - 30 GB of XML files (as mentioned before single file is 1-3 GB), whole procedure is really time consuming - It takes about 12 hours up to 2 days of non stop parsing.

Variables description:

xml - path to xml file
list_agis - list of IDs, list which length is number between 5k - 1 kk
parent - way
child - tag
child_atribitute - k
child_value_1 - highway
child_value_2 - track
name_id, name_atribute, name_file, path_csv, part_name - variables needed to create csv file name

My code

def save_to_csv(
        list_1, list_2, name_1,
        name_2, csv_name, catalogue,
        part_name):
    """
    Saves to CSV, based on 2 lists.
    """
    raw_data = {name_1: list_1,
                name_2: list_2}
    df = pd.DataFrame(raw_data, columns=[name_1, name_2])
    df.to_csv(
        '{0}\{1}_{2}.csv'.format(catalogue, part_name, csv_name),
        index=False, header=True, encoding = 'CP1250')

def xml_parser(
        xml, lista_agis, parent,
        atribiute_parent, child, child_atribiute,
        child_value_1, child_value_2, name_file,
        sciezka_csv, name_id, name_atribiute,
        part_name):
    """
    Function to pick from xml files tag values.
    Firstly it creates tree of xml file and then
    goes each level town and when final condtion is fullfiled
    id and value from xml file is appended to list in the end of
    xml file list is saved to CSV.

    """
    rootElement = ET.parse(xml).getroot()
    list_id = []
    list_value = []
    for subelement in rootElement:
        if subelement.tag == parent:
            if subelement.get(atribiute_parent) in lista_agis:
                for sselement in subelement:
                    if sselement.tag == child:
                        if sselement.attrib[child_atribiute] == child_value_1:
                            list_id.append(
                                subelement.get(atribiute_parent))
                            list_value.append(
                                sselement.get(child_value_2))

    save_to_csv(
        list_id, list_value, name_id,
        name_atribiute, name_file,
        sciezka_csv, part_name)

Introduction

Unfortunately imposm is just for Python 2, my project is in Python 3. I think lxml library looks promising. I wrote simple code to test it, right now it is based on just 2 nodes.

Picture of nodes

I attach picture from XML file so one can see what I am dealing with.

How it works

It is iterating over l_id (which is list of ids) using etree.parse and findall.

First inner loop gathers dictionary where given id is.

Second inner loop gathers dictionary where chosen value is.

Loop for dict_ids_all appends to new list only ids from dictionary.

Loop for dict_ids_all appends to new list only value from dictionary.

My code

tree = lxml.etree.parse(r'path to xml')
l_dict_ids_all = []
l_dict_values_all= []
l_only_id =[]
l_only_values = []
l_id = ['"35121262"', '"35121263"']
name = '"name"'

for id in l_id:
    for tag in tree.findall('//node[@id={0}]'.format(id)):
        l_dict_ids_all.append(tag.attrib)

    for tag in tree.findall('//node[@id={0}]//tag[@k={1}]'.format(id,name)):
        l_dict_values_all.append(tag.attrib)

#printing is only for review purpose

print('Full id dict')
print(l_dict_ids_all)

print('Full Value dict')
print(l_dict_values_all)

print('Only ID list')
for element in l_dict_ids_all:
    l_only_id.append(element['id'])
print(l_only_id)

print('Only Value list')
for element in l_dict_values_all:
    l_only_values.append(element['k'])
print(l_only_values)

Output

  Full id dict

  [{'id': '35121262', 'visible': 'true', 'version': '17',
  'changeset': '41419943', 'timestamp': '2016-08-12T22:24:23Z', 'user':
  'kocio', 'uid': '52087', 'lat': '52.1560439', 'lon': '21.0346808'},
  {'id': '35121263', 'visible': 'true', 'version': '16', 'changeset':
  '41419943', 'timestamp': '2016-08-12T22:24:20Z', 'user': 'kocio',
  'uid': '52087', 'lat': '52.1492285', 'lon': '21.0461042'}]

  Full Value dict [{'k': 'name', 'v': 'Stokłosy'}, {'k': 'name', 'v': 'Imielin'}]

  Only ID list  ['35121262', '35121263']

  Only Value list  ['name', 'name']

What I tried

I am aware that creating list and using it to append items to new list is wrong, but whenever I tried something like this:

l_dict_ids_all.append(tag.attrib[0]['id'])

Received an error :

  TypeError Traceback (most recent call)

  ipython-input-91-8b0a49bc5f35 in ()
        7 for id in l_id:
        8     for tag in tree.findall('//node[@id={0}]'.format(id)):
  ----> 9         l_dict_ids_all.append(tag.attrib[0]['id'])
       10
  src/lxml/etree.pyx in lxml.etree._Attrib.getitem()

  src/lxml/apihelpers.pxi in lxml.etree._getAttributeValue()

  src/lxml/apihelpers.pxi in lxml.etree._getNodeAttributeValue()

  src/lxml/apihelpers.pxi in lxml.etree._getNsTag()

  src/lxml/apihelpers.pxi in lxml.etree.__getNsTag()

  src/lxml/apihelpers.pxi in lxml.etree._utf8()

  TypeError: Argument must be bytes or unicode, got 'int'

My goal/problem

Code is working, but I want to make it better.
I need to get rid of 2 out 4 lists which I create at the begging.


Convert numbers from base X to base Y I recently wrote a piece of code to convert between two bases of X, (Where 26 > X > 0). I was mighty proud that I did this. And then I started wondering, am I using modern coding conventions/practices?

The code can be found here.

And some sample outputs are shown:

// syntax: convertBase(input, inputBase, outputBase)
convertBase("10", 10, 11) // "a"
convertBase("3", 10, 3)   // "10"
convertBase("4", 10, 3)   // "11"

The full code is here:

function convertBase(inNumber, inBase, outputBase) {
  var result = [];
  if (typeof inNumber !== "number" && typeof inNumber !== "string") {
    throw new Error("You input is not a number or a string.");
  }
  var encodings = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
  if (typeof inNumber === "number") {
    inNumber = JSON.stringify(inNumber);
  }
  if (inBase === outputBase) {
    return inNumber;
  }
  inNumber = inNumber.toLowerCase();
  inNumber = inNumber.split("").map(function(item) {
    return encodings.indexOf(item);
  });
  inNumber = inNumber.reverse();
  inNumber = inNumber.map(function(item, index) {
    return item * Math.pow(inBase, index);
  });
  var res = 0;
  inNumber.forEach(function(item) {
    res += item;
    return;
  });
  var ones = res % outputBase;
  var remainder = (res - res % outputBase) / outputBase;
  result.unshift(ones);
  var left = remainder > 1;
  while (left) {
    var ones = remainder;
    var remainder = (remainder - remainder % outputBase) / outputBase;
    result.unshift(ones);
    var left = remainder > 1;
  }
  return result.map(function(item) {
    return encodings[item];
  }).join("");
}
;

Bug

I tried converting "10' from base 10 to base 2 (i.e. binary) and the output was 250, which is invalid for a base 2 number.

Also, when I ran convertBase("3", 10, 3) the output was 0, not "10"

Your Question

  am I using modern coding conventions/practices?

Originally, before I added the javascript tag, this question only had the ecmascript-6 tag. I don't see many features of es-6 in your code, like let and const, arrow functions, default parameters, etc. So judging from an ecmascript-6 point-of-view, I would say No. See the rewrite below which utilizes those features.

const convertBase = (inNumber, inBase = 10, outputBase = 10) => {
  let result = [];
  if (typeof inNumber !== "number" && typeof inNumber !== "string") {
    throw new Error("You input is not a number or a string.");
  }
  const encodings = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
  if (typeof inNumber === "number") {
    inNumber = JSON.stringify(inNumber);
  }
  if (inBase === outputBase) {
    return inNumber;
  }
  inNumber = inNumber.toLowerCase();
  inNumber = inNumber.split("").map(item => encodings.indexOf(item));
  inNumber = inNumber.reverse();
  inNumber = inNumber.map((item, index)  => item * Math.pow(inBase, index));
  let res = 0;
  inNumber.forEach(item => res += item);
  let ones = res % outputBase;
  let remainder = (res - res % outputBase) / outputBase;
  result.unshift(ones);
  let left = remainder > 1;
  while (left) {
    ones = remainder;
    remainder = (remainder - remainder % outputBase) / outputBase;
    result.unshift(ones);
    left = remainder > 1;
  }
  return result.map(item => encodings[item]).join("");
};
console.log('convertBase("10", 10, 11):',convertBase("10", 10, 11))

Re-declarations

The code inside the while loop contains variable declarations for variables declared outside the loop:

var ones = res % outputBase;
var remainder = (res - res % outputBase) / outputBase;
result.unshift(ones);
var left = remainder > 1;
while (left) {
  var ones = remainder;
  var remainder = (remainder - remainder % outputBase) / outputBase;
  result.unshift(ones);
  var left = remainder > 1;
}

While the Javascript engine won't "chuck a wobbly1"2 (though somebody who has to update your code might), those assignment statements inside the while loop could exist without the var keyword, and for the sake of readability, probably should not have var at the beginning.

Simplification

The first versions of Ecmascript (i.e. 1 and 5) have had parseInt() and Number.prototype.toString(), which should be enough to implement the desired functionality (though note that the supported base values are 2-36, not 0-26).

const convertBase = (inputNumber, inputBase = 10, outputBase = 10) =>
  parseInt(inputNumber, inputBase).toString(outputBase);

console.log('convertBase("10", 10, 11):', convertBase("10", 10, 11)); // "a"
console.log('convertBase("3", 10, 3):', convertBase("3", 10, 3)); // "10"
console.log('convertBase("4", 10, 3):', convertBase("4", 10, 3)); // "11"
console.log('convertBase(10, 10, 2):', convertBase(10, 10, 2)); // "1010"

1http://spencertipping.com/js-in-ten-minutes/js-in-ten-minutes.pdf
2https://english.stackexchange.com/a/129277/213844


HackerRank - Left Rotation in JavaScript I'm looking to learn more about data structures, time complexity, and efficient algorithms. I have solved the Left Rotation Problem
on HackerRank using JavaScript. I am looking to see ways to optimize the time complexity. I feel like I have a lot to learn, as don't grok Big O.

function main() {
    const nd = readLine().split(' ')
    const numbers = parseInt(nd[0], 10)
    const rotations = parseInt(nd[1], 10)
    const arr = readLine().split(' ').map(aTemp => parseInt(aTemp, 10))
    const front = arr.slice(0, rotations)
    const back = arr.slice(rotations, numbers)
    const new_arr = back.concat(front)
    console.log(new_arr.join(' '))
}

I feel like this likely has bad time complexity, as under the hood, I believe the slice function uses a loop and has a time complexity of \$O(n)\$. In addition, I'm unsure of how JavaScript implements the merge from the concat method under the hood.

Review

Since you are building the array yourself, as opposed to you get a source array from a consumer of your method, I don't think you should create a new array, but rather just adapt the source array. This way, you could avoid slice and concat altogether.
The number of rotations is an integer. However, reading the description behind the link tells use it's clamped between 1 <= rotations <= nd. There is a slight optimization here. If rotations = nd you don't have to do anything, since a rotation is circular. An elegant way to check this is to normalize rotations as rotations = rotations % nd; assuming you have already checked rotations againsts the clamped range. if rotations = 0, don't rotate.
There's another optimization if nd < 2, then any rotation is the source itself.


32-bit checksum of a file I have implemented a function to produce a 32-bit checksum of a file using the following method: checksum = word_1 + word_2 + ... + word_n, where word_i is the 32-bit words the file consists of.

Here are several questions I'm very interested about:

Is the way I read file word by word correct or there is a better way? (I aim not to read the whole file at once because it can be very large.)
Are there any problems with chosen data types such as uint32_t, unsigned and so on?
Have I got the right way to handle a file that isn't N*4 bytes in size? For example, for 7 bytes file I'm just setting 0-8 bits into 0 to avoid using an accidental value. Or I should set 24-31 bits into 0?

Here is the code I have so far:

void execute(std::ifstream& file)
{
    const size_t WORD_SIZE = sizeof(uint32_t);

    file.seekg(0, ios::end);
    auto sizeInBytes = file.tellg();

    file.seekg(0);
    uint32_t checksum = 0U; // ???
    if(auto sizeInEntireWords = sizeInBytes / WORD_SIZE)
    {
        for(int i = 0; i < sizeInEntireWords; i++)
        {
            uint32_t word;
            file.read(reinterpret_cast<char*>(&word), WORD_SIZE); // ???
            checksum += word;
        }
    }

    if(auto additionalSizeInBytes = sizeInBytes % WORD_SIZE)
    {
        uint32_t word;
        file.read(reinterpret_cast<char*>(&word), WORD_SIZE);
        word &= (~0U << (WORD_SIZE - additionalSizeInBytes * 8)); // ???
        checksum += word;
    }

    cout << checksum << endl;
}

First of all, your checksum function should probably be named checksum and actually return the checksum, rather than simply printing it.

Now, you're not taking advantage of what the std::basic_ifstream API actually gives you. First, read() returns a basic_istream&, which is convertible to bool. That bool tells you if the complete read succeeded or not. So all you have to do is:

uint32_t checksum(std::ifstream& file)
{
    uint32_t sum = 0;

    uint32_t word = 0;
    while (file.read(reinterpret_cast<char*>(&word), sizeof(word))) {
        sum += word;
    }

    // ??

Now, when read() fails, that means our file has run out (assuming we had a valid file to begin with). But, we have other information. There is also gcount() which

  Returns the number of characters extracted by the last unformatted input operation.

If the read partially succeeded, we can mask off the other bytes and add the remainder. Thus, the full solution might be:

uint32_t checksum(std::ifstream& file)
{
    uint32_t sum = 0;

    uint32_t word = 0;
    while (file.read(reinterpret_cast<char*>(&word), sizeof(word))) {
        sum += word;
    }

    if (file.gcount()) {
        word &= (~0U >> ((sizeof(uint32_t) - file.gcount()) * 8));
        sum += word;
    }

    return sum;
}

Doing the masking looks kind of terrible though, so instead we could simply zero out word every time so we can just add the result:

uint32_t checksum(std::ifstream& file)
{
    uint32_t sum = 0;

    uint32_t word = 0;
    while (file.read(reinterpret_cast<char*>(&word), sizeof(word))) {
        sum += word;
        word = 0;
    }

    sum += word; // add the last word, could be 0
                 // if the file size is divisible by 4

    return sum;
}


Linked stack implementation in C++ Please feel free to be as harsh as possible.

Implementation file:

#include "Stack.h"
#include <iostream>
using namespace std;

// Initializes an empty Stack.
Stack::Stack() {
    this->head = new node();
    this->num_elements = 0;

    // set default values for head
    this->head->next = 0;
    this->head->value = 0;
}

// Cleans up memory before the Stack's destruction.
Stack::~Stack() {
    while (this->head->next != 0) {
        pop();
    }
    delete this->head;
}

// Pushes value onto the top of the stack.
void Stack::push(int value) {
    node* newTopNode = new node();
    newTopNode->value = value;

    // currentTopNode may be null if stack is empty
    node* currentTopNode = this->head->next;

    this->head->next = newTopNode;
    newTopNode->next = currentTopNode;

    this->num_elements++;
}

// Pops the top-most value off the stack and returns its value.
int Stack::pop() {
    if (this->head->next == NULL) {
        cout << "\nIllegal State Exception: You cannot pop an empty stack." << endl;
        return 0;
    } else {
        node* topNodeToRemove = this->head->next;

        // save the value of the node before deleting it
        int topNodeValue = topNodeToRemove->value;

        this->head->next = this->head->next->next;

        delete topNodeToRemove;
        this->num_elements--;

        return topNodeValue;
    }
}

// Returns the value at the top of the stack.  Works similarly to pop(), but
// retains the internal structure of the stack.  That is, it does not remove
// the top-most element.
int Stack::getTopElement() const {
    if (this->head->next == NULL) {
        cout << "\nIllegal State Exception: You cannot get the top element of an empty stack." << endl;
        return 0;
    } else {
        return this->head->next->value;
    }
}

// Returns the number of elements currently in the stack.
int Stack::size() const {
    return this->num_elements;
}

Header file:

#ifndef STACK_H_
#define STACK_H_

class Stack {
public:
    Stack();
    ~Stack();
    void push(int);
    int pop();
    int getTopElement() const;
    int size() const;

private:
    struct node {
        int value;
        node* next;
    };

    node* head;
    int num_elements;
};

#endif // STACK_H_

Do not use using namespace std.
In the constructor and push(), it looks like you're calling new on a function.  It should be node.
Prefer nullptr to NULL and 0 for the node pointers if you're using C++11.  Otherwise, you should choose either NULL or 0 for node pointers and keep it consistent.
You don't need this-> everywhere as the code already has the current object in scope.
It's needless to call pop() in the destructor.  For one thing, pop() returns a value.  You should just be using delete.

Instead, have head point to the first element, loop through the stack (stopping when NULL is hit) and call delete on each node.  With this, you won't need to delete head at the end.
pop() and getTopElement() might be best as void.  Here, a 0 is returned if the list is empty.  Sure, no errors happening there.  But then the calling code will take it as an element 0, never knowing whether or not the stack is empty.  If you make them void, you can simply return if the stack is empty.  As for retrieving an element, that's why you have getTopElement().  Once you get the value with getTopElement(), call pop() after that.

Regarding checking for an empty stack, you could make a public empty() function for calling code.  The two functions above should still check for an empty stack, but containers like this usually utilizes such a function.  This could go in the header:

bool empty() const { return num_elements == 0; }

You could make your class more useful by using templates.  This will allow you to populate the stack with any type instead of just ints.


Reading numbers from a file using map I want to read a list of IDs (as integers) from a file in Python3. The file has a single ID per line and no blank lines.

with open(file_eval_id) as f:
    eval_ids = [list(map(int, line.split()))[0] for line in f]

Is there a cleaner way of doing it? I have doubts about referencing the list(...)[0] as the best way.

You can use something like the following:

with open(file_eval_id) as f:
    eval_ids = [int(line) for line in f]

The code assumes, that ID is the only thing in the line.


FSA (finite state automaton) in Scala I'm a beginning Scala programmer with a strong background in functional programming (ML, Haskell, Scheme) and I've just written my first Scala program. It is an implementation of a FSA (finite state automaton). Below is a simplified version that has 3 events/actions/labels (E0, E1, E2) and four states (S0, S1, S2, S3).

 sealed abstract class Event

 case object E0 extends Event
 case object E1 extends Event
 case object E2 extends Event

 abstract class State { def event ( e : Event ) : State }

 object S0 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S1 }
       case E1 => { S0 }
       case E2 => { S2 } } } }

 object S1 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S1 }
       case E1 => { S2 }
       case E2 => { S0 } } } }

 object S2 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S2 }
       case E1 => { S0 }
       case E2 => { S3 } } } }

 object S3 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S0 }
       case E1 => { S3 }
       case E2 => { S3 } } } }

 class Fsa {
   private var state : State = S0
   def event ( e : Event ) : Unit = { state = state.event ( e ) } }

A typical use of Fsa objects would be like this:

val fsa = new Fsa
while ( true ) {
   fsa.event ( ... nextEvent () ) }

I'd be interested to know if you think this is a good, or at least reasonable way
of implmenting FSAs in Scala, and if not, why. I'm particularly interested in the memory consumption of solutions like this.

Following suggestions from Landei above, and this article on recursive type declarations in Scala, I've come up with a slightly different solution where states are directly modelled as state transitions.

trait StateFunc [ T ] extends PartialFunction [ T, StateFunc [ T ] ]

sealed abstract class Event

case object E0 extends Event
case object E1 extends Event
case object E2 extends Event

class FSA {
  private type State = StateFunc [ Event ]

  private def transitions [ T ] ( pf : PartialFunction [ T, StateFunc [ T ] ] ) = new StateFunc [ T ] {
    def apply( event : T ) = pf ( event )
    def isDefinedAt ( event : T ) = pf.isDefinedAt ( event ) }

  private val ( s0 : State ) = transitions { case E0 => s1; case E1 => s2; case E2 => s0 }
  private val ( s1 : State ) = transitions { case E0 => s3; case E1 => s0; case E2 => s1 }
  private val ( s2 : State ) = transitions { case E0 => s2; case E1 => s1; case E2 => s0 }
  private val ( s3 : State ) = transitions { case E0 => s3; case E1 => s3; case E2 => s1 }

  private var state = s0

  def handle ( e : Event ) { state = state ( e ) } }

I'm not saying that this is better than the other solutions proposed, but I wonder about memory usage. Clearly, as this is a highly recursive construct, if the compiler doesn't do tail-call optimisation, this solution will run out of memory eventually. I have no understanding of the Scala compiler, but I would imagine that in this simple case the tail calls are optimised to ensure constant stack space usage. But what if the transition functions do something more complicated (e.g. possibly throwing exceptions)? Can constant space usage still be guaranteed?

As an aside, is it really necessary to go through so many hoops to define a recursive type? Why can I not simply write e.g. type T = Map [ Int, T ]?

Edit 9.9.2011: I added @tailrec annotations to the program above with the following results: The compiler accepts @tailrec on s0, ..., s3 just fine. But it balks when I annotate the private definition of transitions, which is not surprising. What that means in practise for stack-space usage of this form of implementing FSAs I don't know.


Intentional performance degradation through cache and branch-prediction misses I am experimenting with performance evaluation. From the hardware architecture point of view, two main factors are cache misses and incorrect prediction of conditional branches which can degrade the performance of an application.

I have considered a small application for each case:

Cache Misses:

In this application, I intentionally want to write such a piece of code that would cause a worst case scenario w.r.t. cache (i.e., induce cache misses). A cache miss can be a read miss or a write miss, so I have written the code for both.

Read Misses:

     int n = 32767;
     int arr[n];

     for (int i = 0; i < n ; i++) {
         int ri = rand() % n;
         int var=arr[ri];
     }

Write Misses:

     int n = 32767;
     int arr[n];

     for (int i = 0; i < n ; i++) {
         int ri = rand() % n;
         arr[ri] = ri;
     }

Branch Incorrect Predictions:

Here, I intentionally want to write such a piece of code that would cause a worst case scenario w.r.t. branch prediction (i.e., induce incorrect predictions). So, it will make the branch predictor fail badly. The code is as following: Source

    const unsigned arraySize = 1024;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c){
        data[c] = std::rand() % 256;
    }
    long sum = 0;
    for (int i = 0; i < 1024; ++i) {
         // Primary loop
         for (int c = 0; c < arraySize; ++c) {
             if (data[c] >= 128)
                 sum += data[c];
         }
    }

My question:

  Can I make any improvements to these source codes?

(Since a flaw left at this level can make all my experimental results flawed.)

  What are other possible codes that would have similar behavior(cache misses and branch incorrect predictions)?

(Maybe, a couple of other possible ways to do the same thing but with different apparent code.)

  Last but not least; Is there any other potential factor (other than cache misses and branch incorrect predictions) that can cause such a huge performance degradation?

An example source code to demonstrate its effect on the performance.

Note: With regard to the third question, I can name factors e.g., interrupts, context switches etc., however, I am considering real-time paradigm where such events would presumably be controlled.

P.S. I know three different question should be asked in three different posts, nonetheless, the second question is an addendum to the first question and the third question alone will be dubious without the whole context.

Thanks.

EDIT: I am using gem5-simulator in my experiments. Just out of my mind, based on my previous studies and experiences, a brief description of the simulator is: It is a cycle-accurate simulator with the facility to configure customized platforms. The execution traces provided by this simulator does include the exact counts on most of the expected statistics (e.g., cache misses, branch incorrect predicted etc). The generation of these traces does not cause overhead on the actual execution of an application. It also provides overhead free instrumentation facility to added further counters in the traces as per user needs.

Nevertheless, @vnp: Adjoining thanks, I am getting the counts and considering the cache configurations.

I don't think the test results will be convincing. Should I be in this situation, I would be interested in not just performance figures, but the miss counts as well. And I would need the latter to be controlled - random access patterns are not enough.

Also, I'd need to know more about cache: line size, ways and associativity, tag width all affect the test setup (e.g., what is the significance of 32767?) and reliability of results.

The guaranteed way to get worst case cache performance is to disable the cache completely. Configure it as writearound, and you'd have a miss on any write or read. To get more granularity (or if writearound is not available on your CPU), play with writethrough and readthrough modes.

I have no say on branch prediction, however I'd insist on more controllable test setup.

As for question 3: it depends on the underlying architecture. If it has virtual memory, page misses are extremely expensive.


Finding the maximum sum of any 2 elements in an array of integers this no-brainer came up to me in a technical interview. I played it safe and wrote this.

 public class Main {

  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    System.out.println("enter size of the array: ");

    if (!in.hasNextInt()) {
      System.out.println("put an integer! ");
    }
    int size = in.nextInt();

    System.out.println("enter numbers for array");

    int[] array = new int[size];

    for (int i = 0; i < array.length; i++) {
      array[i] = in.nextInt();
    }

    maxSum(array);

    System.out.println(maxSum(array));
  }

  private static int maxSum(int[] array) {

    int max = array[0];

    for (int i = 0; i < array.length; i++) {
      for (int j = i + 1; j < array.length; j++) {

        int currentMax = array[i] + array[j];

        if (currentMax > max) {
          max = currentMax;
        }
      }
    }

    return max;
  }
}

obviously O(n^2) is not the best approach but I just wanted to finish the question without spending to much time, what do you think?

Your code tries all \$ n (n+1)/2 \$ combinations of array elements to find the
combination with the largest sum, so the complexity is \$ O(n^2) \$.

A better solution would be to find the two largest elements in the
array, since adding those obviously gives the largest sum.

Possible approaches are:

Sort the array elements in increasing order and add the last two
elements. Efficient sorting algorithms (such as Quicksort) have an
average complexity of \$ O(n \log(n)) \$.
Traverse the array once and keep track of the largest and second
largest element encountered so far. Then add those elements.
The complexity is \$ O(n) \$.

Other remarks:

Your main program computes maxSum(array) twice,
which is not necessary.
You should check if the user entered at least 2 elements, otherwise
the problem is ill-defined.
The if (!in.hasNextInt()) check is not really helpful. If the user
enters a non-integer, "put an integer! " is printed, but then in.nextInt() fails with an exception. You could for example
skip the entire input line until a valid integer is entered:

while (!in.hasNextInt()) {
    System.out.println("Enter an integer! ");
    in.nextLine();
}
int size = in.nextInt();


Disjoint-set data structure in Python 3 Inspired by this question, I decided to implement a Disjoint-set data structure in Python 3. I mainly followed this description for understanding the algorithm (but did not do the optimizations for path compression, union by rank etc. -- so mine is a "naive" implementation).
Here is the Wikipedia article for reference.

In short, the data structure can hold n disjoint sets, and do two operations on them:

merge any two sets into a single one
for any element, tell to which set it belongs

My implementation is as follows:

#!/usr/bin/python

class Disjoint:

    def __init__(self):
        self.sets = []

    def createSet(self, repr):
        self.sets.append([repr])

    def mergeSets(self, repr1, repr2):
        set1 = self.findSet(repr1);
        set2 = self.findSet(repr2);
        if set1 != set2:
            set1.extend(set2);
            self.sets.remove(set2);

    def findSet(self, repr1):
        for oneSet in self.sets:
            if repr1 in oneSet:
                return oneSet

    def getSets(self):
        return self.sets;

The test class:

import unittest
import disjoint

class TestSequenceFunctions(unittest.TestCase):

    def setUp(self):
        pass;

    def test_empty(self):
        dis = disjoint.Disjoint();
        self.assertEqual([], dis.getSets())
        self.assertEqual(None, dis.findSet(1))

    def test_init(self):
        dis = disjoint.Disjoint();
        for i in range(1, 6):
            dis.createSet(i);
        for i in range(1, 6):
            found = dis.findSet(i);
            self.assertEqual(1, len(found))
            self.assertEqual(i, found[0])
        expected = [[i] for i in range(1, 6)]
        self.assertEqual(expected, dis.getSets())

    def test_simple(self):
        dis = disjoint.Disjoint();
        for i in range(1, 6):
            dis.createSet(i);
        pairs = [[1, 2], [2, 4], [4, 5]]
        for p in pairs:
            p1 = p[0];
            p2 = p[1];

            if dis.findSet(p1) != dis.findSet(p2):
                dis.mergeSets(p1, p2);

        expetctedSets = [[1, 2, 4, 5], [3]];
        self.assertEqual(expetctedSets, dis.getSets())

if __name__ == '__main__':
    unittest.main()

Any suggestion for improvement is welcome, but in particular, I'm interested in the following:

Do you see any problem in the (naive) implementation of the algorithm?
Can the code be improved in any way to have similar functionality, but either be more elegant or more efficient in Python? (I'm thinking of things like using list comprehensions instead of for-itertions, etc.)
Is there any other test case that would be worth adding?

N.B.: For now, I'm not interested in how to implement the optimizations suggested in the linked source (that will be the next step, also using any new unit tests suggested here).

There's a couple of points that are a possible C or Java background leaking through:

You end a lot of lines with an unnecessarry semicolon
You've named your methods and some variables using camelCase, whereas the prefered convention in Python is usually lowercase_with_underscores (the unittest module is an anomaly here, being one of a very few isolated stdlib modules using camelCase)
The getSets method is unnecessarry. Python convention is to expose attributes directly because if the implementation changes later, you can just make it a property. If you really don't want to do that, then you should rename self.sets to self._sets to emphasise that it isn't part of the documented API

I have a feeling that the following line:

self.sets.append([repr])

isn't actually doing what you want. It looks like you mean self.sets.append(repr), otherwise self.sets is full of single-length lists whose only item is a collection of some kind whereas it would make more sense for those collections to be in self.sets directly. You would then make a corresponding change down in findSet so that the test there reads:

if repr1 == oneSet:

Also think about what should happen if findSet fails to find the set. As written, it will fall off the end and impliiclty return None, which will almost certaintly lead to errors in short order. Instead, you should probably immediately raise ValueError with an appropriate error message. You may also want to use list.find to help with this.

You could then add that case to your unit tests.

repr is the name of a builtin function, so calling your arguments by that name shadows it. A better name might be subset, for example. You may also want to document whether it should be a set, a list or a tuple, especially if that ends up mattering to any of the optimisations you write later.

In test_simple, this looks like a typo:

expetctedSets = [[1, 2, 4, 5], [3]];

should be 'expected'.

Finally, you say that this class models disjoint sets, but you never enforce that. Indeed, this would work:

ds = Disjoint()
subset = {1,2,3}
ds.add(subset)
ds.add(subset)
ds.add(subset)

If you are assuming clients won't do things like that, that is OK (although it may make your class less useful), but you should document that. In fact, some docstrings in general wouldn't go astray.


Basic cryptography algorithm I wrote 2 classes in order to implement some basic cryptography algorithm. I tried to use some object-oriented concepts of C++. I'm a beginner, so any comment or suggestion is welcome.

First class: Message

The header:

#ifndef MESSAGE_H
#define MESSAGE_H

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

class Message
{
   public:
       friend class Chiffre;
       typedef std::vector<char> cryptoContainer;
       // constructors
       Message();
        Message(const std::string&);
        Message(const cryptoContainer&);
        Message(const std::string&, const int&);
        // templates for writing original and crypted messages
        template<typename T>
        int writeOriginalMessage(T& stream) const // return original message in an output stream
        {
            for (auto it = m_originalContent.begin(); it != m_originalContent.end(); it++) stream << *it;
            stream.flush();
            return 0;
        }
        template<typename T>
        int writeCryptedMessage(T& stream) const // return crypted message in an output stream
        {
            if (m_cryptedContent.empty()) return 1;
            for (auto it = m_cryptedContent.begin(); it != m_cryptedContent.end(); it++) stream << *it;
            stream.flush();
            return 0;
        }
        // getters
        cryptoContainer getOriginalMessage(void) const;
        cryptoContainer getCryptedMessage(void) const;
        // destructor
        virtual ~Message();
    protected:
        //protected setter
        void setOriginalMessage(cryptoContainer&);
        void setCryptedMessage(cryptoContainer&);
        //attributes
        int m_key;
        cryptoContainer m_originalContent;
        cryptoContainer m_cryptedContent;
};

#endif // MESSAGE_H

The .cpp file:

#include "Message.h"

Message::Message(const std::string& texte):
    m_key(0),
    m_originalContent(texte.begin(),texte.end())
{

}

Message::Message(const Message::cryptoContainer& texte):
    m_key(0), // default key is 0
    m_originalContent(texte)
{

}

Message::Message(const std::string& texte, const int& clef):
    m_key(clef),
    m_originalContent(texte.begin(),texte.end())
{

}

Message::~Message()
{

}

Message::cryptoContainer Message::getOriginalMessage(void) const
{
    return m_originalContent;
}

Message::cryptoContainer Message::getCryptedMessage(void) const
{
    return m_cryptedContent;
}

void Message::setOriginalMessage(Message::cryptoContainer& msg)
{
    m_originalContent = msg;
    return;
}

void Message::setCryptedMessage(Message::cryptoContainer& msg)
{
    m_cryptedContent = msg;
    return;
}

second class: Chiffre (will implement crypto algorithms)

The header:

#ifndef CHIFFRE_H
#define CHIFFRE_H

#include <vector>
#include "Message.h"

class Chiffre
{
public:
        Chiffre();
        virtual ~Chiffre() = 0;

        static void cesar(Message&, const int&);   // décale un caractère à partir d'une clef (algorithme de César)

};

#endif // CHIFFRE_H

The .cpp file:

#include "Chiffre.h"

Chiffre::Chiffre()
{
}

Chiffre::~Chiffre()
{
}

void Chiffre::cesar(Message& msg, const int& clef)
{
    Message::cryptoContainer res;
    Message::cryptoContainer orig = msg.getOriginalMessage();
    for (auto it = orig.begin(); it != orig.end(); it++) res.push_back(*it + clef);
    msg.Message::setCryptedMessage(res);
    return;
}

I'm no cryptography guru, so my comments will aim at the code in itself, not the algorithms.

Message.h / Message.cpp:

There doesn't seem to be a need to include <iostream> nor <fstream> in the header file. Avoid importing dependencies that you don't use. The cost of an include is in compile-time. One too many big projects suffer with long compile times due to poor management of include files.
Keep your parameter names in function/method prototypes. This will self document your code. Take this constructor for instance:

Message(const std::string&, const int&);

Impossible to tell which parameter is doing what without consulting the implementation.
cryptoContainer is a "type alias", nevertheless, it names a type. Your naming convention for types is PascalCase, so CryptoContainer would be more self-consistent.
writeOriginalMessage is currently returning a meaningless integer value (always zero). It could very well return nothing (void). If there is a possibility of failure, then return a boolean true or false.
Still talking about writeOriginalMessage and writeCryptedMessage, both have a quite similar loop inside:

for (auto it = m_originalContent.begin(); it != m_originalContent.end(); it++)

You can significantly shorten them by using a range based foreach loop:

for (const auto & item : container)
{
    stream << item;
}

Notice the reference &. Care should be taken to avoid copying things in this style of iteration since the default in C++ is always a copy.
Writing void in the parameter list of a C++ function that takes no parameters (as in getOriginalMessage(void)) is a C-ish style. C++ does not require that; () is just as good. So avoid the unnecessary verbosity.
virtual destructors are only necessary when your class is meant to be inherited from. In this particular code, that doesn't seem to be the case with Message. If you did that to allow users of your code to inherit from the class, I would advise against, since Composition is usually much more elegant and with less coupling. You should remove virtual from the destructor declaration and perhaps even mark your class final. While your are at it, them make the protected section private and throw the destructor away, since it is empty.
I see that you have a couple places with names not in English, while the bigger whole is all in that language. It would be better to keep things uniform, so replace things like texte and clef with the proper English terms.
In functions/methods that return void, no need to explicitly return at the end. E.g.: setOriginalMessage and setCryptedMessage.
Careful with noisy/meaningless comments. // constructors and // destructor are self evident.

Chiffre.h / Chiffre.cpp:

Again, unnecessary includes: you don't need <vector> in the header file.
Also, the reasons for Chiffre having a virtual destructor are not clear. If you don't have inheritance, you shouldn't be making it virtual.
The empty constructor is also unnecessary. Leave it out if you have no manual initialization to perform.


Efficiently index rows of numpy array by exclusion I need a function that takes a numpy array and a row number as inputs and returns the array (or copy of the array) excluding the given row. I want to do this as efficiently as possible.

# Test array
x = np.repeat(range(10),2).reshape([10,2])

Indexing by slices is very fast in numpy, but as far as I can tell this can only be used to get a contiguous set of rows. For instance, I know I can use slicing to exclude the first row

def index_rows_by_exclusion_firstrow(arr):
    """
    Return slice of arr excluding first row using slice-based indexing
    """
    return arr[1:]

%timeit index_rows_by_exclusion_firstrow(x)

#The slowest run took 33.84 times longer than the fastest. This could mean that an intermediate result is being cached
#1000000 loops, best of 3: 204 ns per loop

There is a numpy function, numpy.delete, that does the operation that I'm looking for, but it creates a new array and is therefore very slow.

def index_rows_by_exclusion_npdel(arr, i):
    """
    Return copy of arr excluding single row of position i using
    numpy delete function
    """
    return np.delete(arr, i, 0)

%timeit index_rows_by_exclusion_npdel(x, 1)
#The slowest run took 5.51 times longer than the fastest. This could mean that an intermediate result is being cached
#100000 loops, best of 3: 9.65 µs per loop

The best I have come up with is indexing by a list, which is about twice as fast as the numpy.delete version of the function, but still ~30 times as slow as slicing

def index_rows_by_exclusion_list(arr, i):
    """
    Return slice of arr excluding single row of position i using
    list-based indexing
    """
    return arr[[ x for x in range(arr.shape[0]) if x != i]]

%timeit index_rows_by_exclusion_list(x,1)
#The slowest run took 12.54 times longer than the fastest. This could mean that an intermediate result is being cached
#100000 loops, best of 3: 5.82 µs per loop

My question is: is there any faster way to index a numpy array like this? Is there any way to use slicing to index all but one row in an array?

One additional note: the code I'm writing has to be compatible with Cython, which means I can't use boolean masking arrays because Numpy in Cython does not support boolean arrays (this is what I was doing before I realized that boolean arrays don't work in Cython).

Since the result's buffer will have a gap, compared to the original, it will have to be a copy.  I believe delete takes different approaches depending on the inputs.

One approach is a boolean index, e.g.

ind = np.ones((10,), bool)
ind[n] = False
A1 = A[ind,:]

Another is to do the equivalent with index values

ind = range(n) + range(n+1:A.shape[0]] # using list concatenate
A1 = A[ind,:]

And as you note, using that index with take may be faster than direct indexing.  I doubt if the difference is big, but I haven't timed it recently.

ind could also made by concatenation of 1d arrays.  Alternatively, index the two parts, and concatenate them:

 np.concatenate([A[:n,:],A[n+1:],axis=0)

The inputs to concatenate are slices, but result is a copy.

 np.r_[0:n, n+1:A.shape[0]]

is a convenient way of generating the integer index list - but not necessarily a speed solution.

Why is the difference time difference between a view and a copy significant?  If you do it a few times in the program, it shouldn't matter.  If you do this deletion repeatedly, I'd question the larger program design.  Could, you for example, accumulate the deletion indices, and perform the deletion step just once?

A few timings:

In [17]: arr=np.arange(1000)

In [18]: timeit arr[np.r_[:500,501:1000]].shape
10000 loops, best of 3: 55.7 us per loop

In [19]: timeit arr.take(np.r_[:500,501:1000]).shape
10000 loops, best of 3: 44.2 us per loop

In [20]: timeit np.r_[:500,501:1000]
10000 loops, best of 3: 36.3 us per loop

In [23]: timeit ind=np.ones(arr.shape[0],bool);ind[500]=False;arr[ind].shape
100000 loops, best of 3: 12.8 us per loop

Oops, the boolean index is faster in this test case.

Best yet:

In [26]: timeit np.concatenate((arr[:500],arr[501:])).shape
100000 loops, best of 3: 4.61 us per loop


Refactoring RadioGroup setter code? I am setting different RadioGroup like this:

fragment.setT1RadioGroup((RadioGroup)fragView.findViewById(rowids[0]).findViewById(R.id.t1_radiogroup));
fragment.setT2RadioGroup((RadioGroup)fragView.findViewById(rowids[1]).findViewById(R.id.t1_radiogroup));
fragment.setT3RadioGroup((RadioGroup)fragView.findViewById(rowids[2]).findViewById(R.id.t1_radiogroup));
fragment.setT4RadioGroup((RadioGroup)fragView.findViewById(rowids[3]).findViewById(R.id.t1_radiogroup));
fragment.setT5RadioGroup((RadioGroup)fragView.findViewById(rowids[4]).findViewById(R.id.t1_radiogroup));
fragment.setT6RadioGroup((RadioGroup)fragView.findViewById(rowids[5]).findViewById(R.id.t1_radiogroup));
fragment.setT7RadioGroup((RadioGroup)fragView.findViewById(rowids[6]).findViewById(R.id.t1_radiogroup));
fragment.setT8RadioGroup((RadioGroup)fragView.findViewById(rowids[7]).findViewById(R.id.t1_radiogroup));
fragment.setT9RadioGroup((RadioGroup)fragView.findViewById(rowids[8]).findViewById(R.id.t1_radiogroup));
fragment.setT10RadioGroup((RadioGroup)fragView.findViewById(rowids[9]).findViewById(R.id.t1_radiogroup));

For refactoring purpose could I reduce the size of this code? How?

Assuming that setT5RadioGroup only sets a variable within the fragment:

In your fragment, use RadioGroup[] radioGroups = new RadioGroup[10];

setTRadioGroup(int number, RadioGroup grp) {
   this.radioGroups[number] = grp;
}

In your activity, or whatever it is:

for (int i = 0; i < rowids.length; i++) { // assuming rowids.length is 10
    RadioGroup grp = (RadioGroup)fragView.findViewById(rowids[i]).findViewById(R.id.t1_radiogroup);
    fragment.setTRadioGroup(i, grp);
}

Whenever you find yourself using multiple numbered methods that does very similar things, think: Array!! (or possibly List<ElementType> if you want to be able to add/remove dynamically)


Merge sort implementation in Python def mergesort( array ):
    # array is a list

    #base casee
    if len(array) <= 1:
        return array
    else:
        split = int(len(array)/2)
        #left and right will be sorted arrays
        left = mergesort(array[:split])
        right = mergesort(array[split:])

        sortedArray  = [0]*len(array)

        #sorted array "pointers"
        l = 0
        r = 0

        #merge routine
        for i in range(len(array)):

            try:
                #Fails if l or r excede the length of the array
                if left[l] < right[r]:
                    sortedArray[i] = left[l]
                    l = l+1
                else:
                    sortedArray[i] = right[r]
                    r = r+1
            except:
                if r < len(right):
                    #sortedArray[i] = right[r]
                    #r = r+1
                    for j in range(len(array) - r-l):
                        sortedArray[i+j] = right[r+j]
                    break
                else:
                    #sortedArray[i] = left[l]
                    #l = l+1
                    for j in range( len(array) - r-l):
                        sortedArray[i+j] = left[l+j]
                    break

        return sortedArray

First of all, the code suffers a very typical problem. The single most important feature of merge sort is stability: it preserves the order of the items which compare equal. As coded,

            if left[l] < right[r]:
                sortedArray[i] = left[l]
                l = l+1
            else:
                sortedArray[i] = right[r]
                r = r+1

of two equals the right one is merged first, and the stability is lost. The fix is simple:

            if left[l] <= right[r]:

(or if right[i] < left[i]: if you prefer).

I don't think that try/except on each iteration is a way to go. Consider

        try:
            while i in range(len(array)):
                ....
        except:
            ....

Of course here i is not known in the except clause. Again, the fix is simple. Notice that the loop is never terminated by condition: either left or right is exhausted before i reaches limit. It means that testing the condition is pointless, and i is an index on the same rights as l and r:

        l = 0
        r = 0
        i = 0
        try:
            while True:
                ....
        except:
            ....

Naked except are to be avoided. Do except IndexError: explicitly.