Generating letter combinations It's about two months since I posted this question on CodeReview. I've been working hard to improve the code posted there and came up with the following.

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

typedef unsigned long long ull;

int main(void) {

    ull start=1, stop=100,cnt;
    register int t,len;
    char *str=calloc(33,sizeof(char));
    char *Alpha="abcdefghijklmnopqrstuvwxyz", *p1, *p2;
    int a_len=(int)strlen(Alpha);

    for (;start<=stop;++start) {

        cnt=start;

        /*
            This is used to construct a string from given alphabet.
            The generated string must be reversed
        */
        for (t = 0, len = 0; cnt; cnt = (cnt-1)/a_len, ++str, ++len, ++t)
            *str = Alpha[(cnt-1) % a_len];

        /*
            A bit odd but working (and important!) part of this code.
            As the str pointer was incremented during string generation,
            we need to 'reverse' it.
        */
        while ( t-- ) str--;

        /*
            This is used to reverse a string instead of strrev
        */
        for (p1 = str, p2 = str+len-1; p2>p1; ++p1, --p2) {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
        }

        printf("%llu --- %s\n",start,str);
    }

    free(str);

    return 0;
}

As you could have already guessed, this code generates letter combinations. The 'reversing' of a pointer (I'm not quite sure how to call this properly) is necessary because if one doesn't do that, he'll get a SegmentationFault as he'll be trying to access unallocated memory.

Example output

1 --- a
2 --- b
3 --- c
4 --- d
5 --- e
6 --- f
7 --- g
8 --- h
9 --- i
10 --- j

< omitted >

91 --- cm
92 --- cn
93 --- co
94 --- cp
95 --- cq
96 --- cr
97 --- cs
98 --- ct
99 --- cu
100 --- cv

This works quite well but I was wondering if it is possible to do the same thing even faster, if it is possible to omit the 'pointer revering' business.

Note: this code is different from the one I linked this question to because it doesn't use a function, thus, the technique and the algorithm are very different.

Do you really need this:

typedef unsigned long long ull;

Will a long or an int not just work (1 .. 100) fit nicely in these types.

One variable declaration per line.
You are not helping the compiler by making less lines of code (it will work just as well with more). But humans who have to read this will work better with cleaner more readable code.

ull start=1, stop=100,cnt;

A register declaration. Wow. I have not seen one of those in a while (20 years). The optimizer is much better than you at deciding what fits in a register let it do its job. I would even bet this keyword is ignored nowadays.

register int t,len;

Do you realy need to cast the result here?

int a_len=(int)strlen(Alpha);

That could would look a lot clearer without the cast. I would only keep it if the compiler is generating a warning. (but then I may change the type of a_len to be the correct type (but I am a C++ programmer and correct types is important to me).

This seems like a complicated way

 while ( t-- ) str--;

of saying:

 // Or
 str -= t;
 t    = 0;

WTF!!!!

        *p1 ^= *p2;
        *p2 ^= *p1;
        *p1 ^= *p2;

Why O Why do you use this. Its a obfuscated way of swapping two values. Just swap the two values using a temporary. The compiler will use any tricks it has internally to do this as fast as possible (probably using a register and two memory accesses rather than 3 memory accesses (which will be slower)).

Seems to me like you are trying to manually do peephole optimizations that the compiler is already doing for you. The compiler is better than you at these optimizations so the only thing you are doing is screwing with the compilers ability to perform these optimizations probably resulting in slower code.

Humans are bad at this, compilers are very very very good. Humans are good at algorithmic optimizations compilers are bad at this. Do what humans do best and let the compiler to what it is good at.


Getting the HTTP client's IP Can you please tell me whether this is a good way to get the user's IP (IPv4 or IPv6)? Does someone have a better way to do this? Please take a look at the entire code, the server_params order and the comments.

/* We are looking for ip in server params */
$server_params = array('HTTP_CLIENT_IP', 'HTTP_X_FORWARDED_FOR', 'REMOTE_ADDR');

foreach($server_params as $server_param)
{
    /* If server param exists and his value is a real ip */
    if(isset($_SERVER[$server_param]) && filter_var($_SERVER[$server_param], FILTER_VALIDATE_IP))
    {
        /* If we are here, then means that the ip is whether IPV4 or IPV6 */
        /* This means that we can set user_ip as binary - We will insert this ip into an mysql column - VARBINARY (16) */
        define('user_ip',inet_pton($_SERVER[$server_param]));
        break;
    }
}

/* If the user_ip is not defined or the inet_pton failed (can inet_pton fail if is defined ?) */
if(!defined('user_ip') || user_ip === false) { echo 'Error. Your ip is not valid'; exit(); }

Here's what I would change :

The answer to the question (see 200_success comment) states that the only thing that is hard to spoof is REMOTE_ADDR, so you should put this value first in your array.
I'm not a big fan of your double test (isset and filter_var). I would like to trust that the implementation of filter_var is a good one and that it does test the emptyness of your variable before going any futher, but I'm not sure. Anyway, I'll just keep the test with filter_var .
Not a big fan of your define either, why do you want to use a constant ? I would initialize a variable userIP before the foreach to false, so there's only one test to do after the loop.

One thing that worries me a bit is the existence of a case where filter_var would succeed but inet_pton would fail (for the same value). It should not exist, but if it does, you might exit your loop with userIP equal to false, while there is one valid IP in one of the following server variables. So just to be sure, I would add a test on inet_pton before breaking out of the loop.


Wireframe animation on canvas is slow I'm recently working on a project that involves animation in the background. It works well on desktop but performance drops drastically on mobile. I'm using Paper.js to import a svg and animate it. This is the demo.

paper.project.importSVG(svg, function(item) {
          var moveSpeed = 70;
          var movementRadius = 15;
          var boundingRec = item.bounds;
          var lines = [];
          var circles = [];
          /*
            Arrange lines and circles into different array
          */
          $.each(item.getItems({
            recursive: true,
          }), function(index, item) {
            if (item instanceof paper.Shape && item.type == 'circle') {
              item.data.connectedSegments = [];
              item.data.originalPosition = item.position;
              circles.push(item);
            }
            if (item instanceof paper.Path) {
              lines.push(item);
            }
          });

          /*
            Loop through all paths
            Checks if any segment points is within circles
            Anchors the point to the circle if within
          */
          $.each(lines, function(pathIndex, path) {
            $.each(path.segments, function(segmentIndex, segment) {
              $.each(circles, function(circleIndex, circle) {
                if (circle.contains(segment.point)) {
                  circle.data.connectedSegments.push( segment.point );
                  return false;
                }
              });
            });
          });

          /*
            Animate the circles
          */
          $.each(circles, function(circleIndex, circle) {
            var originalPosition = circle.data.originalPosition;
            var radius = circle.radius * movementRadius;

            var destination = originalPosition.add( paper.Point.random().multiply(radius) );

            circle.onFrame = function() {
              while (!destination.isInside(boundingRec)) {
                destination = originalPosition.add( paper.Point.random().multiply(radius) );
              }

              var vector = destination.subtract(circle.position);
              circle.position = circle.position.add(vector.divide(moveSpeed));
              // move connected segments based on circle

              for (var i = 0; i < circle.data.connectedSegments.length; i++) {
                circle.data.connectedSegments[i].set({
                    x: circle.position.x,
                    y: circle.position.y,
                });
              }

              if (vector.length < 5) {
                destination = originalPosition.add( paper.Point.random().multiply(radius) );
              }
            }
          });
        });

A single SVG animation alone is causing the CPU usage to go up to 90% on mid-tier mobile devices and it go to the point that the interface becomes unusable. Any advice or help is much appreciated.

This might be a small improvement but there is no need to check that destination is inside boundingRec on each frame, you just need to check it when creating a new destination.

Here is a modified codepen in which destination creation is done in a separated function, removing the unneeded check:

function createNewDestination(originalPosition, radius) {
    var destination = null;
    while (!destination || !destination.isInside(boundingRec)) {
        destination = originalPosition.add(paper.Point.random().multiply(radius));
    }
    return destination;
}


Rotating 3D wireframe This code consumes a lot of CPU. Could you tell me where it is possible to improve the code or change the way rendering?

Or it is possible to reduce the overhead of calculations? If you are using only 1 point when drawing the load on the CPU is not changed! Load 50-60%

Ubuntu 15.04 / intel® Core ™ i5-3230M CPU @ 2.60GHz × 4

Run the code without rendering lines - 20-30% load. So they are quite costly...

Demo: http://codepen.io/jonfint/full/VLYMMW

var canvas = document.getElementById("canvas"),
    ctx = canvas.getContext('2d'),
    points = [],
    r = 0;

var a = 50; // количество точек
var b = 1; // скорость поворота
var d = 20; // увеличение радиуса*
var minDist = 200; // ??
var dist; // ??

canvas.width = 500;    // Originally window.innerWidth, changed for Stack Snippet
canvas.height = 600;   // Originally window.innerHeight, changed for Stack Snippet

for (var i = 0; i < a; i++) {
    var rand = Math.random() * canvas.height;

    points.push({
        cy: rand,
        cx: rand * 0.3 + 300,
        r: 360 / a * i,
        p: {x: null, y: null},
        d: Math.random() * (d + 5) + 50,
        s: (Math.random() - 0.5) * 0.7,
        size: Math.random() * 3 + 1,
    })
}

function render(){
    ctx.clearRect(0, 0, canvas.width, canvas.height);

    ctx.fillStyle = '#202020';
    for (var i=0, len = points.length; i < len; i++) {
        var p = points[i];

        for (var j = i + 1; j < points.length; j++) {
            var p2 = points[j];
            distance(p.p.x, p.p.y, p2.p.x, p2.p.y);
        }

        p.r += p.s;

        var vel = {
            x: p.d * Math.cos(p.r * Math.PI / 180),
            y: p.d * Math.sin(p.r * Math.PI / 180) / 2
        };

        var centx, centy;
        centx = p.p.x - p.size * 0.5;
        centy = p.p.y - p.size * 0.5;
        ctx.beginPath();
        ctx.rect(centx, centy, p.size, p.size);
        ctx.fill();
        ctx.closePath();

        p.p.x = p.cx + vel.x;
        p.p.y = p.cy + vel.y;
    }
}

function distance(p1x, p1y, p2x, p2y) {
    var dx = p1x - p2x;
    var dy = p1y - p2y;
    dist = Math.sqrt(dx*dx + dy*dy);
      // Нарисовать линию, если расстояние меньше, чем minDistance
    if (dist <= minDist) {
        ctx.beginPath();
        ctx.strokeStyle = 'rgba(200, 200, 200,'+ (1.0-dist/minDist) +')';
        ctx.moveTo(p1x, p1y);
        ctx.lineTo(p2x, p2y);
        ctx.lineWidth = 1;
        ctx.stroke();
        ctx.closePath();
    }
}

window.requestAnimFrame = (function(){
    return  window.requestAnimationFrame   ||
        window.webkitRequestAnimationFrame ||
        window.mozRequestAnimationFrame    ||
        window.oRequestAnimationFrame      ||
        window.msRequestAnimationFrame     ||
    function(callback) {
        window.setTimeout(callback, 1000 / 30);
    };
})();

(function animloop() {
    requestAnimFrame(animloop);
    render();
})();
<canvas id="canvas"></canvas>

I profiled your code and calling your render function takes 3.1-4.2 ms on my machine (i7 2.1 ghz running chrome/linux). I managed to cut that to only 0.6 ms by removing what is AFAIK the performance killer in this type of drawings using the canvas API. Check it out for yourself http://codepen.io/anon/pen/QbwQmo

The performance killer that I'm talking about is that you're drawing a million separate paths instead of batching them all in a single .beginPath ... .stroke. The catch is however that you can't have multiple colors (alpha levels) in the same path - so changing the color for every segment is not possible anymore. You could instead bucketize the paths - choose 10 shades of grey and add segments to these buckets; then call .stroke for each bucket (that'll amount to max 10 calls - way better than (50*50 which is what you can have)). The only way to overcome this limitation of the canvas API is to not use it in the first place :). Instead use a WebGL renderer (pixi.js, goo.js, three.js).

There's another thing which you can do to increase performance especially if you'll want more than 50 points. Right now you're checking every point against every other point. The number of calls to distance (not the best name btw) grows quadratically with the number of points. You can reduce the number of checks by discarding points that are too far - and you achieve this by splitting the whole space ([0...600] x [0...600]) into smaller buckets of 100 x 100 or something. You'd have to update the buckets every frame such that they contain the points that lie within their bounds. The upside is that you only need to check points in nearby buckets and not in the whole space.

(Disclaimer: I am a dev of goo.js)


Finding an item name starting or ending with from a list I have written this helper function. I want to know if there is an even better approach, considering that I do not want to add a dependency to any additional module.

def _isobjectInList(lst, name, criteria='startswith'):
    """ Find item in the list  starting or ending with name passed.

        :param lst: list of items/ objects
        :type lst: list

        :param name: name starting or ending with.
        :param name: string

        :param criteria: function of string obect whether startswith or endswith
        :param criteria: built-in method of str object
    """
    return [itemfound for itemfound in lst if getattr(itemfound, criteria)(name)]

Use first class functions, not hardcoded strings:

def _isobjectInList(lst, name, criteria=str.startswith):
    """
    >>> _isobjectInList(['foobaz','null'],'foo')
    ['foobaz']
    """
    return [i for i in lst if criteria(i, name)]

also give it a better name


Playing card game method Is there a better, more elegant solution to the following method?

Boolean[] spades = new Boolean[10]; // 40 cards deck

foreach (Card card in m_Cards.Where(card => (card.Suit == Suit.Spades)))
    spades[(Int32)card.Rank] = true; // Rank goes from Ace (0) to King (10)

if (spades[0] && spades[1] && spades[2])
{
    points += 3;

    for (Int32 i = 3; i < spades.Length; ++i)
    {
        if (spades[i])
            ++points;
        else
            break;
    }
}

In fact, the function awards 3 points to the player only if he owns Ace, Two and Three... and, always if this condition is satisfied, it awards him a point for every card that extends the sequence. Examples:

Ace + Three + Five = 0 Points
Ace + Two + Three = 3 Points
Ace + Two + Three + Five = 3 Points
Ace + Two + Three + Four + Five + Six = 6 Points

Every kind of better solution is accepted, such as Linq and enumerable extensions.

We can use the fact that in the ordered sequence of cards the cards that match your requirement will be located at the beginning of sequence, and their rank will match their position:

var count = _cards.Where(card => card.Suit == Suit.Spades)
    .Select(card => (int)card.Rank) //we only need the rank
    .Distinct() //ignoring multiple cards with the same rank
    .OrderBy(rank => rank) //sorting by rank
    .TakeWhile((rank, index) => rank == index) //taking all initial cards with index matching their rank
    .Count();

return count < 3 ? 0 : count;

Note that your code will perform better than this one (you'll notice that only if you run it thousands times a second) since you're using the fact that there are only 10 sequential values present in Rank.


Project Euler #5 - Smallest multiple using Factor Table This is a problem from Project Euler and on Hackerrank (here)-

  2520 is the smallest number that can be divided by each of the numbers
  from 1 to  10 without any remainder.

  What is the smallest positive number that is evenly divisible
  (divisible with no remainder) by all of the numbers from 1 to N?

  Input Format First line contains  that denotes the number of test cases. This is followed by  lines, each containing an integer, .

  Output Format  Print the required answer for each test case.

  Constraints

    1 <= T <= 10
    1 <= N <= 40

  Sample Input

    2
    3
    10

  Sample Output

    6
    2520

Here is the code I wrote. My approach was to first create a table of prime factors and use them to generate a number that is divisible by all numbers below N. Is there a better approach? Is there something that I am doing here that is very sub-optimal?

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int T,N,i,j,k,q,M[40],p;
    scanf("%d",&T);
    M[0]=1;
    M[1]=2;
    M[2]=3;
    for (i=3;i<40;i++){
        q=i+1;
        for (j=1;j<i;j++){
            if (q%M[j]==0){
                q/=M[j];
            }
        }
        M[i]=q;
    }
    for (i=0;i<T;i++){
        scanf("%d",&N);
        p=1;
        for (j=0;j<N;j++){
            p*=M[j];
        }
        printf("%d\n",p);
    }
    return 0;
}

Truly choose your language

Although a C compiler won't accept the program as a whole (due to the using directive and choice of headers) the actual code here is all really C. I'd make up my mind and either write C in a way that's acceptable to a C compiler, or else write C++ that makes good use of the language. The combination you've used is (IMO) pretty much a pit of despair.

For the remainder of this review, I'm going to go with the tag, and assume you really wanted to write good C++.

Avoid C's variadic I/O functions

Although some parts of the C library are fine, C's variadic I/O functions such as scanf and printf are quite problematic in one respect: they provide essentially no type safety. As shown by dozens (probably hundreds, if you looked carefully) of questions on Stack Overflow, mismatches between the formatting argument and the other arguments frequently cause problems. There are a few cases where you're reading or writing highly formatted data that it might be worth at least considering using these functions anyway, but the I/O format specified here doesn't provide any such justification.

Use the right types

In C++, there's rarely much reason to use a built in array such as your M. You're usually better off with a std::array or std::vector instead.

Likewise, the values we need for inputs up to 40 can exceed the range of a 32-bit number. We probably want to use unsigned long long (or something on the same general order) to support the specified range.

Names

As @NullException hinted at in the comments, most of the variable names in this code border on meaningless. I consider it perfectly acceptable to use a name like i for a subscript in a loop, but for longer-lived things like your M, a more meaningful name would be extremely helpful.

Consider a more recognizable algorithm

When you get down to it, what we're dealing with here is computing the least common multiple (LCM) of some numbers. There's a well-known method of computing the LCM of numbers: LCM(a, b) = a * b / gcd(a, b). This can be extended to three or more numbers quite easily:

LCM(a, b, c) =
    L = lcm(a, b);
    result = L * c / gcd(L,c)

Since this defines the LCM of three numbers in terms of the LCM of two numbers, we can extend it indefinitely.

Define functions where suitable

In this case, our definition of LCM depends on the GCD. Computing the GCD of two inputs is a well-defined operation that should probably be defined as a function.

Consider a greedy algorithm

In this case, we have only 40 possible inputs. We also have an algorithm for computing LCMs, where each result depends on the previous result. It's probably easiest to start by computing the LCM for every possible input from 1 to 40, then read the actual inputs, and just print out the result for each.

Result

Putting those suggestions together, we might get code something like this:

#include <map>
#include <vector>
#include <iostream>

template <class T>
T GCD(T u, T v) {
    while (v != 0) {
        T r = u % v;
        u = v;
        v = r;
    }
    return u;
}

int main() {
    using T = unsigned long long;

    std::vector<T> LCMs{ 1 }; // The LCM of 1 is 1

    // Compute succeeding LCMs based on existing one(s)
    for (T i = 2; i < 40; i++) {
        auto prev = LCMs.back();
        LCMs.push_back(prev * i / GCD(prev, i));
    }

    int test_count;
    std::cin >> test_count;

    for (int n = 0; n < test_count; n++) {
        int input;
        std::cin >> input;

        std::cout << LCMs[input-1] << "\n";
    }
}


Pairwise swap elements of a given linked list by changing links GeeksForGeeks challenge:

  Given a singly linked list, write a function to swap nodes pairwise.

  For example :

  if the linked list is 1->2->3->4->5->6->7 then the function should
  change it to 2->1->4->3->6->5->7, and if the linked list is
  1->2->3->4->5->6 then the function should change it to
  2->1->4->3->6->5

#include <iostream>

// structure of a Node in the linked list
struct Node {
    int data;
    Node *next;
};

// append data to end of linked list
Node *append(Node *head, int data) {
    auto newNode = new Node{data, nullptr};
    if (head == nullptr)
        return newNode;

    auto temp{head};
    while (temp->next)
        temp = temp->next;
    temp->next = newNode;

    return head;
}

//  display the list

void display(Node *head) {
    std::cout << "The list : \t";
    while (head != nullptr) {
        std::cout << head->data << " ";
        head = head->next;
    }
    std::cout << std::endl ;
}

//  pairwise swap of the elements in the given linked lists
void pairwiseSwap(Node **head_ref) {

    if(((*head_ref) == nullptr) || ((*head_ref)->next == nullptr))
        return ;

    Node *temp1 = nullptr, *temp2 = nullptr ;
    Node *prev = nullptr, *curr =(*head_ref) ;

    while(curr != nullptr) {

        //  temp1 : first element of the pair
        //  temp2 : second element of the pair
        temp1 = curr;
        temp2 = curr->next;

        //  if the the 2nd element in the pair is nullptr, then exit the loop
        if(temp2 == nullptr){
            break ;
        }
//      curr = curr->next->next ;

        //  if the current element is head, then previous one must be nullptr
        //  In either case swapping the nodes
        if(prev == nullptr){
            prev = temp1;
            temp1->next = temp2->next;
            temp2->next = temp1;
            (*head_ref) = temp2 ;
        }
        else {
            temp1->next = temp2->next;
            temp2->next = temp1;
            prev->next = temp2;
            prev = temp1;
        }

        //  moving to the next pair of nodes
        curr = temp1->next ;
    }
}

//  Driver function
int main() {
    Node *a = nullptr ;

    // for odd number of nodes
    a = append(a, 15);
    a = append(a, 10);
    a = append(a, 5);
    a = append(a, 20);
    a = append(a, 3);
//  a = append(a, 2);

    pairwiseSwap(&a);

    display(a);

   // for even number of nodes
    a = append(a, 15);
    a = append(a, 10);
    a = append(a, 5);
    a = append(a, 20);
    a = append(a, 3);
    a = append(a, 2);

    pairwiseSwap(&a);

    display(a);
}

It's weird that you picked append as your primitive for building test cases, when prepend would be so much simpler and faster — O(1) instead of O(n).

auto newNode = new Node{data, nullptr};

This is a very "modern" way of writing what would be more idiomatically written as

Node *newNode = new Node(data, nullptr);

I would weakly recommend the latter. And I would strongly recommend, if you do nothing else, at least calling out explicitly when you're working with raw (non-owning) pointers:

auto *newNode = new Node{data, nullptr};  // the asterisk means watch out!

auto temp{head};

Again, I'd write simply

Node *temp = head;

or at least

auto *temp = head;

The * signals the reader to watch out for pointer pitfalls (aliasing, memory leaks); the = signals the reader that an initialization is happening here. You might be surprised how easy it is to glance over auto temp{head}; surrounded by other lines of code and not even recognize that it's introducing the name temp!

//  pairwise swap of the elements in the given linked lists
void pairwiseSwap(Node **head_ref) {

Some coding guidelines tell you to pass the inout parameter head_ref by pointer here, instead of by reference. I'm going to assume you're following one of those guidelines.

return ;

is an unidiomatic whitespace style; most programmers would write

return;

You actually put an extra space before a lot of semicolons in this function (but not consistently). Are you French? ;)

You should definitely factor out the "swap two nodes" functionality into a named function. I somewhat suspect that this would do, but you'd have to draw it out on paper...

void swap_two_nodes(Node *&p, Node *&q) {
    assert(p->next == q);
    std::swap(p, q);
}

Alternatively — and since I've confused myself ;) — you could just write a recursive version of the whole thing:

Node *pairwise_swap(Node *head) {
    if (head && head->next) {
        Node *first = head->next;
        Node *second = head;
        Node *tail = pairwise_swap(head->next->next);
        head = first;
        first->next = second;
        second->next = tail;
    }
    return head;
}

Turning this into tail-recursion is left as an (easy) exercise for the reader.

// for even number of nodes
a = append(a, 15);

Appending an even number of nodes to an odd-length list does not result in an even-length list. Did you try running your test code? Did you look at the output and verify that it was correct? You should have!


Checking if two time intervals overlap I have two time intervals i1 and i2, each defined by two values, begin and end (epoch time). I need to write a function returning a boolean value indicating whether the intervals overlap.

According to my understanding, an overlap can occur in four following cases:

while the last case (where the i2 is fully included within i1 is already covered by first two cases so can be dismissed.

The remaining three cases lead me to the following logic:

private static boolean isThereOverlap(Interval t1, Interval t2) {

        return t1.begin.isAfter(t2.begin) && t1.begin.isBefore(t2.end) ||
                t1.end.isAfter(t2.begin) && t1.end.isBefore(t2.end) ||
                t1.begin.isBefore(t2.begin) && t1.end.isAfter(t2.end);
}

where:

t1 and t2 represent i1 and i2 accordingly.

I wonder whether there's a more concise way to identify the overlap or a
way to simplify the code?

EDIT1:

Including the Interval class which is utilizing java.time:

import java.time.Instant;

private class Interval {
        private Instant begin;
        private Instant end;

        private Interval(long begin, long end) {
            this.begin = Instant.ofEpochMilli(begin);
            this.end = Instant.ofEpochMilli(end);
        }
    }

The code looks well presented, and it's clear how it maps to the problem statement.

The one thing that's not well defined is how we deal with exact equality of times.  I'm assuming that intervals are always half-open (i.e. including the start time, but excluding the end time); it would be wise to add suitable comments to ensure that all readers agree on what's expected.

It's possible to simplify considerably, because in all cases we want (and none we don't), t1 ends after t2 begins and t2 ends after t1 begins, giving us a simpler expression:

t1.begin.isBefore(t2.end) && t2.begin.isBefore(t1.end)

If the Interval class is under your control, consider making this method a public instance method of that class.  You might also want to check that the parameters are not null, if users might use that to indicate an empty interval:

if (t1 == null || t2 == null)
    return false;

(this latter is an argument against using an instance method, as then the caller would need to check t1 isn't null).


Aggregate cidrs up to a limit I have this algorithm which aggregates a list of cidrs up to a provided limit based on the distance between them. It finds the closest ones and calculates the subnet to join them. The loop repeats until the limit is reached. I think there's room to improve it but I'm stuck at the moment. Any advice?

Input

limit: 9
cidrs (10):

52.1.0.0/16
52.2.0.0/16
52.3.0.0/16
52.4.0.0/16
52.5.0.0/16
52.6.0.0/16
52.7.0.0/16
52.8.0.0/16
52.9.0.0/16
52.10.0.0/16

Output

cidrs (9):

52.1.0.0/16
5̶2̶.̶2̶.̶0̶.̶0̶/̶1̶6̶
5̶2̶.̶3̶.̶0̶.̶0̶/̶1̶6̶
52.4.0.0/16
52.5.0.0/16
52.6.0.0/16
52.7.0.0/16
52.8.0.0/16
52.9.0.0/16
52.10.0.0/16
**52.2.0.0/15**

Code

public static IEnumerable<string> Aggregate(List<string> cidrs, int limit)
{
    var parsedCidrs = cidrs.Select(IPNetwork.Parse).ToArray();

    var cidr1 = parsedCidrs[0];
    var cidr2 = parsedCidrs[1];
    var minWideSubnet = IPNetwork.WideSubnet(new[] { cidr1, cidr2 });

    while (parsedCidrs.Count > limit)
    {
        foreach (var cidrA in parsedCidrs)
        {
            foreach (var cidrB in parsedCidrs)
            {
                if (cidrA != cidrB)
                {
                    var wideSubnet = IPNetwork.WideSubnet(new[] {cidrA, cidrB});

                    if (wideSubnet.Usable < minWideSubnet.Usable)
                    {
                        minWideSubnet = wideSubnet;
                        cidr1 = cidrA;
                        cidr2 = cidrB;
                    }
                }
            }
        }
        // update array
        cidrs.Remove(cidr1.ToString());
        cidrs.Remove(cidr2.ToString());
        var end = minWideSubnet.ToString();
        cidrs.Add(end);
    }

    return cidrs;
}

First just a small cosmetic improvement: I'd call the method MergeSimilarIps or something like this (you know better what name would make more sense). Aggregate suggests you would get a sigle result.

    foreach (var cidrA in parsedCidrs)
    {
        foreach (var cidrB in parsedCidrs)
        {
            if (cidrA != cidrB)
            {

I thnink you can speed the merge a little bit by using for loops and starting the second one at i + 1 of the first loop. This way you check x == y only once because y == x is the same an you already checked it so there is no need that you do it again plus the + 1 will skip x == x.

Compare these two loops. The first one works like in your solution:

var nums = new [] { 1, 2, 3 };

foreach (var x in nums)
{
    foreach (var y in nums)
    {
        Console.WriteLine($"({x}, {y})");
    }
}

its result is:

(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)

The second one works without repetitions.

for (var x = 0; x < nums.Length; x++)
{
    for (var y = x + 1; y < nums.Length; y++)
    {
        Console.WriteLine($"({nums[x]}, {nums[y]})");
    }
}

It produces only 1/3 of this list above:

(1, 2)
(1, 3)
(2, 3)

This means you get only unique combinations without repetitions.


Writing a function to add or modify an existing object inside an array I have an array of objects. Each object has two properties, id and quantity.

I wrote a function to add an object to the array. But the function must check if the object already exists within the array. If it does exist the function must increment the quantity property. Otherwise it must add a new object.

Is there an idiomatic way to achieve the same result? I feel that looping over the array to compare the id of the object at index against the id passed as argument is not the right approach.

I am also suspicious of the found = false temporary variable.

Finally, in Ruby we are encouraged to break down long methods into smaller ones. I am aware that JavaScript is not the same, but I feel that this could be further refactored.

addItem = function(id, items) {
  var found, i;
  found = false;
  i = 0;
  while (i < items.length) {
    if (id === items[i].id) {
      items[i].quantity++;
      found = true;
      break;
    }
    i++;
  }
  if (!found) {
    return items.push({
      id: id,
      quantity: 1
    });
  }
};

Why are you using an array to do the job of a map? Use the right data structures....

... instead, use a hashmap (associative array) of [id, quantity]. If id exists in hashmap, then increment up the value at hashmap[id].


Form the largest number by swapping one pair of digits You are given a number. You are given the opportunity to swap only once to produce the largest number.

My approach was to use buckets whose values were their indexes and their locations were their values.

I walked the array checking if the largest value was greater than the current value.

If the current value was smaller I would decrement the largest value. Checking if it existed and that, that bucket was in a location greater than the current location in the iteration.

At which point I would know the bucket's location and that it contained the largest value outside a successive set and the nearest lowest value it would replace, to produce the largest number.

Analysis:

Creating Buckets: O(n) time and O(n) space
Walking Values Space and Time: O(1) +  finding the lowest high and swapping: O(1)
Total: O(n)

const maximumSwap = function(array) {
  array = array.toString().split('');
  const buckets = []
  for (let location = 0; location < array.length; location++) {
    buckets[array[location]] = location
  }
  let largest = buckets.length - 1
  for (let current_location = 0; current_location < array.length; current_location++) {
    let current_val = array[current_location]
    for (; largest > current_val; largest--) {
      if (buckets[largest] > current_location) {
        array[current_location] = [array[buckets[largest]], array[buckets[largest]] = array[current_location]][0]
        return +array.join('')
      }
    }
  }
  return +array.join('')
};

console.log(maximumSwap(99739))
console.log(maximumSwap(9273))
console.log(maximumSwap(9732))

Style critique

Either terminate your statements consistently with semicolons, or not at all.

If you're going to use const to define the function, then I suggest using the arrow notation as well, instead of the function keyword.

The variable names could be improved:

Why is the function's parameter called array?  It's clearly supposed to be a number.
After splitting the digits, what does array mean, and what does it contain?  I'd rename it to digits.
What are the buckets?  I suggest renaming it to lastIndex.
Instead of location and current_location, I'd just use i, which is a conventional variable name to use for an array index.  (Also, the underscore is unconventional in JavaScript.)
largest doesn't remain the largest digit of the number.  Perhaps wantDigit would be a better name, since it's the digit that we would like to put at the current index, if possible.

The nastiest line of code is the one where you perform the swap:

array[current_location] = [array[buckets[largest]], array[buckets[largest]] = array[current_location]][0]

A better way to do parallel assignment would be to use destructuring assignment:

let array = ['a', 'b', 'c'];
[array[0], array[2]] = [array[2], array[0]];
console.log(array);

But here, you don't even need to do parallel assignments, because you have already stored the values to be swapped in other variables:

array[buckets[largest]], as an rvalue, is just largest.  (With the renamings I proposed above, it would have been digits[lastIndex[wantDigit]], which might make it more obvious that it's actually just wantDigit.)
array[current_location], as an rvalue, is just current_val.

So, just write two simple and clear assignment statements instead.

If no swap occurred, then you can just return the original number.

const maximumSwap = (number) => {
    let digits = number.toString().split('');
    let lastIndex = [];
    for (let i = 0; i < digits.length; i++) {
        lastIndex[digits[i]] = i;
    }
    let wantDigit = lastIndex.length - 1;
    for (let i = 0; i < digits.length; i++) {
        for (let iDigit = digits[i]; iDigit < wantDigit; wantDigit--) {
            if (i < lastIndex[wantDigit]) {
                digits[i] = wantDigit;
                digits[lastIndex[wantDigit]] = iDigit;
                return +digits.join('');
            }
        }
    }
    return number;
};

console.log(maximumSwap(99739));
console.log(maximumSwap(9273));
console.log(maximumSwap(9732));

Complexity analysis

Your algorithm is pretty efficient, and I couldn't find any significant optimizations to make.

Be careful to specify what you mean by "n".  You probably used it to mean the length of the input number.  (If I had to choose my conventions, I'd say instead that the input number itself is n, and its length is d = log10 n.)

Creating the buckets takes O(n) time, because location loops up to array.length.  But I would say that it takes O(1) space, since the length of buckets will not exceed 10.

Walking the values clearly takes more than O(1) time, because the outer loop is O(n): current_location iterates up to array.length.  The inner loop, which executes at most 10 times, can be said to take O(1) time.

Altogether, then, the algorithm takes O(n) time and O(1) space.


Save/Load GridView layout using SettingsService I am able to save my GridView layout by storing a string representation of the items in the ItemsSource. I then load that string representation from the SettingsService and set the index of the items accordingly.

The layout is changed by drag/dropping items in the GridView. Here is the code-behind:

private void MainGridView_OnDrop(object sender, DragEventArgs e)
{
    var grid = e.OriginalSource as GridView;
    var items = grid?.ItemsSource as ObservableCollection<AppPage>;

    if (items != null)
    {
        var layout = "";

        // save settings
        foreach (var p in items)
        {
            p.PageIndex = items.IndexOf(p);
            // serialize pagename and pageindex
            layout += $"{p.PageName},{p.PageIndex}|";
        }
        _settings.MainMenuLayout = layout;
    }
}

Then when I load the application, I check for the MainMenuLayout setting and parse it out like so:

public void LoadMainMenu()
{
    var pages = new ObservableCollection<AppPage>
    {
        new AppPage("Payees", "ms-appx:///Assets/payee-180.png", typeof(Views.PayeesPage)),
        new AppPage("Bills", "ms-appx:///Assets/invoice-180.png", typeof(Views.InvoicesPage)),
        new AppPage("Payments", "ms-appx:///Assets/envelope-180.png", typeof(Views.PaymentsPage)),
        new AppPage("Checkbook", "ms-appx:///Assets/checkbook-180.png", typeof(Views.CheckbookPage)),
        new AppPage("Receipts", "ms-appx:///Assets/receipt-180.png", null),
        new AppPage("Categories", "ms-appx:///Assets/categories-180.png", typeof(Views.CategoriesPage)),
        new AppPage("Accounts", "ms-appx:///Assets/bank-180.png", typeof(Views.AccountsPage)),
        new AppPage("Budget", "ms-appx:///Assets/budget-180.png", null),
        new AppPage("Contacts", "ms-appx:///Assets/contacts-180.png", typeof(Views.ContactsPage)),
        new AppPage("Reports", "ms-appx:///Assets/charts-180.png", typeof(Views.ReportsPage)),
        new AppPage("Test", "ms-appx:///Assets/beaker-180.png", typeof(Views.TestPage)),
    };

    var layout = _settings.MainMenuLayout;
    if (!string.IsNullOrEmpty(layout))
    {
        // split on |
        var pagesSplit = layout.Split('|');

        foreach (var p in pagesSplit)
        {
            // then split on ,
            if (p.Contains(","))
            {
                var pageInfo = p.Split(',');
                var cur = pages.First(page => page.PageName == pageInfo[0]);
                cur.PageIndex = int.Parse(pageInfo[1]);
            }
        }
    }

    // sort based on index
    AppPages = new ObservableCollection<AppPage>(pages.OrderBy(p => p.PageIndex));
}

Is there a better way to serialize/deserialize the layout? I don't want to store the entire AppPage objects for every item, as there are additional properties that are unrelated to the layout.

At the recommendation of @svick, I decided to serialize the objects themselves. Rather than creating a custom object/stub, I just added [JsonIgnore] attribute to the properties that I did not want to serialize.

Here is the new code for saving the layout:

private void MainGridView_OnDrop(object sender, DragEventArgs e)
{
    var grid = e.OriginalSource as GridView;
    var items = grid?.ItemsSource as ObservableCollection<AppPage>;

    if (items != null)
    {
        foreach (var p in items)
        {
            p.PageIndex = items.IndexOf(p);
        }
        // serialize items
        var layout = JsonConvert.SerializeObject(items);
        _settings.MainMenuLayout = layout;
    }
}

Then I was able to simplify reading the layout from settings like so:

var layout = _settings.MainMenuLayout;
if (!string.IsNullOrEmpty(layout))
{
    var pageStubs = JsonConvert.DeserializeObject<ObservableCollection<AppPage>>(layout);

    foreach (var p in pageStubs)
    {
        var cur = pages.First(page => page.PageName == p.PageName);
        cur.PageIndex = p.PageIndex;
    }
    // sort based on index
    AppPages = new ObservableCollection<AppPage>(pages.OrderBy(p => p.PageIndex));
}
else
{
    AppPages = pages;
}

The only properties of AppPage that get serialized are the PageName and PageIndex, which are the only properties used for this process.

Any further improvements are always welcome!


Using deque for composing a string from 2 alternating stacks We have 2 strings, say "JACK" and "DANIELS". We create two stacks from these strings, and then loop over them comparing first elements: whichever of the 2 goes first in lexicographic order gets popped from its stack and added to a string (the second value is left alone). So it goes, until we end up with a string containing all the elements from both stacks. In this example it would be "DAJACKNIELS"

My solution takes advantage of the fact that min function, when applied to deque() objects, returns the one whose first element goes lexicographically first. As it happens, it works well enough for small testcases, but fails large ones, for it takes all the memory it can get and then some.

Perhaps, something can be improved in my code, or there's a better solution altogether (like, without a while loop).

def morgan(a, b):
    string = ""
    stack_a = deque()
    stack_b = deque()

    stack_a.extend(a)
    stack_b.extend(b)
    while True:
        if len(stack_a) != 0 and len(stack_b) != 0:
            if stack_a == min(stack_a, stack_b):
                string += stack_a.popleft()
            else:
                string += stack_b.popleft()
        elif len(stack_a) == 0 and len(stack_b) == 0:
            break
        elif len(stack_a) == 0:
            string += stack_b.popleft()
        elif len(stack_b) == 0:
            string += stack_a.popleft()
    return(string)

Example of a large testcase:

string a: https://pastebin.com/raw/pebMbcA6
string b: https://pastebin.com/raw/bwNEqJcr

There is no need to read the whole string into a deque. Just iterate over the strings using iterators. The only gotcha is handling the fact that either of the strings can be empty at the beginning and that one can be exhausted before the other.

def _morgan(a, b):
    a, b = iter(a), iter(b)
    try:
        x = next(a)
    except StopIteration:
        yield from b
        return
    try:
        y = next(b)
    except StopIteration:
        yield x
        yield from a
        return
    while True:
        if x <= y:  # `<=` because that's what `min` does
            yield x
            try:
                x = next(a)
            except StopIteration:
                yield y
                yield from b
                return
        else:
            yield y
            try:
                y = next(b)
            except StopIteration:
                yield x
                yield from a
                return

def morgan(a, b):
    return "".join(_morgan(a, b))

Note that both the original strings and the resulting string still need to fit into memory for this to work. If you only need to iterate over the resulting string, use only the private function. In that case the original strings still need to fit into memory, unless you also have them as generators (e.g. by streaming the contents from the URLs):

import requests

def stream(url, chunk_size=1000):
    with requests.get(url, stream=True) as r:
        for chunk in r.iter_content(chunk_size=chunk_size, decode_unicode=True):
            yield from iter(chunk)

if __name__ == "__main__":
    a = stream("https://pastebin.com/raw/pebMbcA6")
    b = stream("https://pastebin.com/raw/bwNEqJcr")
    c = _morgan(a, b)
    while (chunk := "".join(islice(c, 1000))):
        print(chunk, end='')
    print()

This works on my machine with the given strings, but so does the morgan function I defined above.

Note that you need Python 3.8+ for the walrus operator :=. With earlier Python versions it is slightly more verbose:

 if __name__ == "__main__":
    a = stream("https://pastebin.com/raw/pebMbcA6")
    b = stream("https://pastebin.com/raw/bwNEqJcr")
    c = _morgan(a, b)
    chunk = "".join(islice(c, 1000))
    while chunk:
        print(chunk, end='')
        chunk = "".join(islice(c, 1000))
    print()


Implementing a Trie in Python using lists alone I've been working on implementing a Trie in Python for educational purposes. I tried implementing one using dictionaries and I was successful.

The structure of a trie with the words in, inn, inner, innerr would be as follows:

[['i', [['n', [['n', [['e', [['r', [['r', [], 'end']], 'end']]]], 'end']], 'end']]]]

where end indicates the end of a word.

class TrieException(Exception):
    pass

def add_word(word, trie):
    END = "end"
    if word == '':
        raise TrieException("word empty")

    prev = None
    branch = trie

    for i, c in enumerate(word):
        found = False
        for each in branch:
            if each[0] == c:
                if i == len(word)-1:
                    if len(each) > 2:
                        raise TrieException("Word already present")
                    else:
                        each.append(END)
                prev = branch
                branch = each[1]
                found = True
                break
        if not found:
            nb = []
            if i == len(word)-1:
                branch.append([c, nb, END])
            else:
                branch.append([c, nb])
            branch = nb

def search_word(word, trie):
    if word == '':
        raise TrieException("empty word")

    branch = trie
    for i, c in enumerate(word):
        found = False
        for each in branch:
            if each[0] == c:
                found = True
                branch = each[1]
                if i == len(word)-1:
                    if len(each) <= 2:
                        raise TrieException("Word not found")
                break
        if not found:
            raise TrieException("Word not found")

Do you have any suggestions on how I can do this in a cleaner fashion?

Exceptions are for exceptional (read 'rare','unexpected') edge cases

You are using exceptions as the default behaviour, this is not nice, instead functions should return values, remove TrieException("word not find") from search_word(word, trie) and instead return True if you find the word and False if you do not find it.

Confusing alias

branch = trie

You just confuse the reader, each thing should have one name only.


String calculator in F# This is some of my first real F# code ever. I have done a bit of reading and watched a few videos however. I chose to do a code kata for string calculator to try it out.

The kata I was working on is here by Roy Osherove, though I may have strayed a bit.

I am pretty happy with this, but wonder if there are things that could be better, or more idiomatic F#.  I am specifically wondering if there is a better option to having the overloaded Add members.  I'm also curious about the last test and exception handling best practices.

module Tests
open Xunit
open System

type Calculator() =
    let delimiters = ",\n"
    member x.Add (m:int, n:int list) =
        match n with
        |[] -> m
        |y::ys ->
            if y < 0 then failwith "No Negative Numbers"
            x.Add((m+y),ys)
    member x.Add (y:string) =
        let numList = List.map (fun x -> x.ToString() |> Convert.ToInt32) (delimiters.ToCharArray() |> y.Split |> Seq.toList)
        x.Add(0,numList)

[<Fact>]
let ReturnsNotNull() =
    let calc = new Calculator()
    Assert.NotNull (calc.Add "0,0")

[<Fact>]
let ReturnsZeroWhenZeros() =
    let calc = new Calculator()
    Assert.Equal(0,(calc.Add "0,0"))

[<Fact>]
let ReturnsOneWhenShouldBeOneOnLeft() =
    let calc = new Calculator()
    Assert.Equal(1,(calc.Add "1,0"))
[<Fact>]
let ReturnsOneWhenShouldBeOneOnRight() =
    let calc = new Calculator()
    Assert.Equal(1,(calc.Add "0,1"))
[<Fact>]
let ReturnsElevenWithStringOfNumbersThatTotalEleven() =
    let calc = new Calculator()
    Assert.Equal(11,(calc.Add "0,1,1,1,1,1,6"))
[<Fact>]
let ReturnsElevenWithStringOfNumbersThatTotalElevenDelimitedByNewLine() =
    let calc = new Calculator()
    Assert.Equal(11,(calc.Add "0,1,1\n1,2\n6"))
[<Fact>]
let ReturnsElevenWithStringOfNumbersThatTotalElevenDelimitedByNewLineNoNegativeNumbers() =
    let calc = new Calculator()
    try
        calc.Add("0,1,-1\n1,2\n6") |> ignore
        Assert.False true
    with
        | _ -> Assert.True true

Is there a specific reason you want to accept a string? You could pass a list and get by with one overload.

type Calculator() =
  member x.Add(nums: int list) = List.sum nums

let calc = Calculator()

calc.Add([0; 0])
calc.Add([1; 2; 3; 4])
calc.Add(List.init 10 id)

EDIT

I'm sorry, I misunderstood the point of the exercise. There are a few changes I would make.

According to the kata, you only need one method taking a string and returning an int.
There's an overload of String.Split accepting a char array, so you can store your delimiters as such and avoid the call to ToCharArray.
You can use the built-in int function instead of Convert.ToInt32.
There's no need to roll your own "sum" function. It's already built into the various collection modules.

The following code satisfies steps 1-3.

type Calculator() =

  let delimiters = [|','; '\n'|]

  member x.Add(nums) =
    match nums with
    | null -> nullArg "nums"
    | "" -> 0
    | _ ->
      nums.Split(delimiters)
      |> Array.map int
      |> Array.sum


Strongly-connected component for a graph I implemented a strongly connected graph code in C++.

matrix_graph.h

#pragma once
#include "stdafx.h"

class matrix_graph
{
private:
    int** v;
    int vertexes;
public:
    matrix_graph(int**, int);
    ~matrix_graph(void);
    void reverse();
    int get_max_vertexes();
    bool is_connected(int i,int j);
};

matrix_graph.cpp

#include "stdafx.h"
#include <iostream>
#include "matrix_graph.h"

using namespace std;

matrix_graph::matrix_graph(int** g, int N)
{
    v = g;
    vertexes = N;
}

matrix_graph::~matrix_graph(void)
{}

void matrix_graph::reverse()
{
    for(int i=0;i<vertexes;i++)
        for(int j=0;j<vertexes;j++)
        {
            if(v[i][j] == 1 && v[j][i]==0){
                v[j][i] = -1;
                v[i][j] = 0;
            }
        }

    for(int i=0;i<vertexes;i++)
        for(int j=0;j<vertexes;j++)
        {
            if(v[i][j] == -1 )
                v[i][j] = 1;
        }
}

int matrix_graph::get_max_vertexes()
{
    return vertexes;
}

bool matrix_graph::is_connected(int i,int j)
{
        return (v[i][j]==1);
}

Main code:

enum Color {WHITE,GREY,BLACK};

void matrix_dfs_visit(matrix_graph m , int i , std::list<int>& q , Color* c)
{
    int N = m.get_max_vertexes();
    c[i] = GREY;
    for(int j=0;j<N;j++){
        if(i!=j){
            if( m.is_connected(i,j))
                if(c[j] == WHITE)
                  matrix_dfs_visit(m,j,q,c);
        }
    }
    c[i] = BLACK;
    q.push_front(i);
}

void dfs(matrix_graph m, std::list<int>& visited_vertexes_in_order )
{
    int N = m.get_max_vertexes();
    Color* c = new Color[N];
    for(int i=0;i<N;i++)
        c[i] = WHITE;
    for(int i=0;i<N;i++)
        if(c[i] == WHITE)
            matrix_dfs_visit(m,i,visited_vertexes_in_order ,c);
}

void dfs_transpose(matrix_graph &m , std::list<int> &visited_vertexes_in_order)
{
    int N = m.get_max_vertexes();

    Color* c = new Color[N];
    for(int i=0;i<N;i++)
        c[i] = WHITE;

    for(list<int>::iterator iter = visited_vertexes_in_order.begin();iter != visited_vertexes_in_order.end();iter++){
        int scc_head = *iter;
        if(c[scc_head] == WHITE){
            list<int> scc;
            matrix_dfs_visit(m,scc_head ,scc,c);
            print_scc(scc);
        }
    }
}

void print_scc(list<int> & l){
    cout << "Strongly Connected Component:";
    for(list<int>::iterator iter=l.begin(); iter !=l.end();iter++)
        cout<< " "<<*iter;
    cout<<"\n";
}

void get_strongly_connected_component(matrix_graph &m)
{
    list<int> visited_vertexes_in_order;
    dfs(m,visited_vertexes_in_order);
    m.reverse();
    dfs_transpose(m,visited_vertexes_in_order);
}

void process()
{

    int v[7][7] = {
        {0,1,0,0,0,0,0},
        {0,0,1,1,0,0,0},
        {1,0,0,0,0,0,0},
        {0,0,0,0,1,0,0},
        {0,0,0,0,0,1,0},
        {0,0,0,1,0,0,1},
        {0,0,0,0,0,0,0}
    };

    int* v_ptr[7] = {v[0],v[1],v[2],v[3],v[4],v[5],v[6]};
    matrix_graph m(&v_ptr[0],7);
    get_strongly_connected_component(m);
}

Please give any reviews, especially on the reverse function and the whole design. Naming convention here is also pretty weak I think.

Firstly, I think you class name can be improved somewhat. Sure, it tells you the underlying data structure that the graph will use (sort of, anyway), but it doesn't tell you anything about what kind of graph it is. Unless you read the source, you won't know that this is supposed to represent a directed graph - so why not put that in the name: directed_matrix_graph.

Speaking of underlying data structure, simply taking an int** that you don't copy, but simply use as-is, is generally not good practice. Most users of a class like this will assume that it manages its own memory. This puts the onus on the user to make sure everything used in your class remains within scope. I'd recommend replacing this with a std::vector<std::vector<int>> which manages its own memory. This should probably have a constructor which it initializes from a template; something like:

class matrix_graph
{
private:
    std::vector<std::vector<int>> vertexes;

public:
    template <typename Iterator>
    matrix_graph(Iterator begin, Iterator end)
    {
        std::vector<int> v(begin, end);
        for(std::size_t i = 0; i < v.size(); ++i) {
            vertexes.push_back(v);
        }
    }

...
};

Destructors shouldn't take parameters (even void), and you shouldn't declare one if it isn't going to do anything: the compiler generated one will suffice in this case.

Both  int get_max_vertexes() and bool is_connected(int i,int j) should be const methods, as these don't change the underlying matrix_graph:

int get-max_vertexes() const;
bool is_connected(int i, int j) const;

On to the main code: your dfs has a memory leak: you declare new Color[N] but never delete[] it. Again, using a std::vector will make these sorts of problems go away. It will also simplify the code:

void dfs(matrix_graph m, std::list<int>& visited_vertexes_in_order )
{
    std::vector<Color> c(m.get_max_vertexes(), WHITE);
    for(int i = 0;i < N; i++)
        if(c[i] == WHITE)
            matrix_dfs_visit(m, i, visited_vertexes_in_order, c);
}

In matrix_dfs_visit and dfs, you pass your matrix_graph by value and call it recursively. If you were actually storing graph vertexes in your class, this would get very slow very quickly. You aren't modifying the underlying matrix_graph here, so you should pass it by const-reference instead: const matrix_graph& m.

You have another memory leak in dfs_transpose, same solution applies as above. You pass your matrix_graph here by reference, but it is never changed. Since bool is_connected(int i, int j) should be const (if you change it per the advice given above), you can now pass by const matrix_graph&.

Similar complaint for void print_scc(list<int> & l), should be const list<int>& l. Anything that doesn't change should always be passed by const, this will make sure that the underlying object isn't changed (well, as long as people don't start const_casting things, but you have bigger problems in that case).

The algorithms themselves look like they come straight from CLRS so I won't bother going over them.

Some other general comments:

Use whitespace in loops: for(int i=0;i<vertexes;i++) is so much harder to read than for(int i = 0; i < vertexes; i++).
Avoid using namespace std as much as possible, even in .cpp files. In fact, you don't even use any standard library components in your matrix_graph.cpp file, so it doesn't even need to be there in the first place. Even if you did, the absolutely tiny time savings you get by not having to type out std:: in a few places is not worth the potential name clashes.
Put your code in a namespace, it's generally good practice.
In general, be careful of memory leaks. Use new as little as possible. Prefer std::vector to manually dealing with arrays: they stop memory leaks and offer much better exception safety.


Count total set bits Im am solving Count total set bits:

  Find the sum of all bits from numbers 1 to N.

  Input:

  The first line of input contains an integer T denoting the number of
  test cases. The first line of each test case is N.

  Output:

  Print the sum of all bits.

  Constraints:

  1 ≤ T ≤ 100
  1 ≤ N ≤ 1000

  Example:

  Input:
  2
  4
  17

  Output:
  5
  35

  Explanation:
  An easy way to look at it is to consider the number, n =
  4:
  0 0 0 = 0
  0 0 1 = 1
  0 1 0 = 1
  0 1 1 = 2
  1 0 0 = 1
  Therefore , the total number of bits is 5.

My approach:

/*package whatever //do not write package name here */

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

class GFG {
    private static int noOfBits (int N)
        {
            int sum = 0;
            for (int i = 1; i <= N; i++)
                {
                    if ((i & i-1) == 0)
                        {
                            sum += 1;
                        }
                    else
                        {
                            sum += numBits(i);
                        }
                }
            return sum;
        }

    private static int numBits (int num)
        {
            int sum = 0;
            int rem;
            while (num != 0)
                {
                   rem = num%2;
                   num /= 2;
                   sum += rem;
                }
            return sum;
        }

    public static void main (String[] args) throws IOException {
        //code
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        String line = br.readLine();
        int T = Integer.parseInt(line);
        String line2;
        int N;

        for (int i = 0; i < T; i++)
            {
                line2 = br.readLine();
                N = Integer.parseInt(line2);
                System.out.println(noOfBits(N));
            }
    }
}

I have the following questions with regards to the above code:

How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?

Your way of indenting and placing braces is consistent, which is good.
I prefer the K&R style, which
is also recommended in the (historical) Java Code Conventions from
Sun Microsystems, or the Google Style Guides:

  Open brace “{” appears at the end of the same line as the declaration statement
  Closing brace “}” starts a line by itself indented to match its corresponding opening statement, ...

You have separated the I/O from the actual computation, which is again
good, as it keeps the main method short, and allows to add unit tests
more easily.
Reading the input can be simplified slightly by using Scanner.
Short (nondescriptive) variable names T and N are usually not recommended.
In this case it might be acceptable, since those names correspond directly
to the identifiers used in the programming challenge description.

However, it is not immediately apparent what the method names noOfBits
and numBits stand for, and what distinguished them. A better choice could
be totalSetBits (corresponding to the challenge description), and
countBits, plus short explaining comments.
I am not sure if the special treatment of powers of 2 in if ((i & i-1) == 0)
is worth the additional code, as it applies only to few numbers in the range
1...N. In any case, it should be part of the numBits() method.
The separate variable int rem in numBits() is not needed.

Summarizing the suggestions so far, the code would look like this:

import java.io.IOException;
import java.util.Scanner;

class GFG {

    // Total count of all 1 bits in the binary representation of the
    // numbers 1 ... N.
    private static int totalSetBits(int N) {
        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += countBits(i);
        }
        return sum;
    }

    // Number of 1 bits in the binary representation of n.
    private static int countBits(int n) {
        if ((n & n-1) == 0) {
            return 1; // n is a power of 2.
        }
        int count = 0;
        while (n != 0) {
            count += n % 2;
            n /= 2;
        }
        return count;
    }

    public static void main (String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 1; i <= T; i++) {
            int N = scanner.nextInt();
            int bits = totalSetBits(N);
            System.out.println(bits);
        }
    }
}

How can we make this faster? One approach would be
to make countBits() faster, and you'll find various methods to count
the number of set bits in an integer at
Bit Twiddling Hacks.

But perhaps we can compute totalSetBits(N) better than
adding countBits(n) for all numbers n from 1 to N? This is the real
challenge here, and I don't want to deprive you from the satisfaction of
figuring out the solution yourself, so here are some hints only:

First have a look at some special values:

0
1  --> totalSetBits(1) = 1

00
01
10
11 --> totalSetBits(3) = 2 * 2 = 4

000
001
...
110
111 -> totalSetBits(7) = 3 * 4 = 12

Can you spot the general pattern?

Then try compute totalSetBits(N) for arbitrary N by using
those “special values.” This should lead to a \$ O(\log N) \$ solution
instead of the current \$ O( N) \$ solution.

And of course – when not in an interview – you can “cheat:” Compute totalSetBits(N) for the first
(e.g.) 40 values of N, and look up the resulting sequence in the
On-Line Encyclopedia of Integer Sequences®. For many
programming challenges, this leads to useful information and insights into
the problem.


Inverse cascade challenge - Recursion Print the following pattern, when you invoke inverse_cascade(1234)

1
12
123
1234
123
12
1

Solution:

def inverse_cascade(n):
    def grow(n):
        if n < 10:
            print(n)
        else:
            grow(n // 10)
            print(n)
    def shrink(n):
        if n < 10:
            print(n)
        else:
            print(n)
            shrink(n // 10)
    grow(n // 10)
    print(n)
    shrink(n // 10)

Using a recursion approach, how can I improve this code without using higher order functions?

Note: No data models have to be used.

Separate grow and shrink functions are not necessary. Instead you can have a single function that prints, recurses and prints again the same value when the recursion returns.

For example like this:

def inverse_cascade(n, digits=1):
    n = str(n)
    print(n[:digits])
    if digits < len(n):
        inverse_cascade(n, digits+1)
        print(n[:digits])


Filter a Linked List in Place in C I have created the following function which filters a linked list in place
(here it removes all instances of the element k), but it could easily be modified to take a function pointer as an argument and filter on something else.
Any ideas on how to improve the code?
typedef struct list_integer {
    type value;
    struct list_integer *next;
} list_integer;

list_integer *removeKFromList(list_integer * l, int k)
{

    if (!l)
    return l;
    while (l && l->value == k)
    l = l->next;
    if (!l)
    return l;

    list_integer *p = l;
    list_integer *q = l->next;

  scan_in:
    if (q) {
    if (q->value != k) {
        list_integer *t = q;
        q = q->next;
        p = t;
        goto scan_in;
    } else {
        goto scan_out;
    }
    }

  scan_out:
    if (q) {
    if (q->value != k) {
        p->next = q;
        p = q;
        q = q->next;
        goto scan_in;
    } else {
        q = q->next;
        goto scan_out;
    }
    } else {
    p->next = q;
    }
    return l;

}

Table of contents (in no particular order)
Indent your code properly!
Don't use goto for something so routine. Unless you're writing a c compiler and intend to compete with gcc or clang or you're Andrei Alexandrescu... don't use goto at all!
while loop/for loop can be used to accomplish what you need instead of goto.
Fix memory leaks. If you're in place modifying a linked list, the nodes that are removed from the list have to have their memory free'd. (In general, this is the assumption going off solely your function prototype. It's possible that all the nodes are statically allocated and it's not this function's responsibility to free them but I'm assuming the more usual case.)
Use comments to explain what you're doing. Although this isn't super complicated, since it's pretty low level, comments are a good idea.
Checking for NULL, IMO it's better to do an explicit check with == NULL rather than !l. Although it is the same and is a popular choice among C programmers (I used to do it too, it made me feel smart)... it's hard to read and is not a good idea. Personally, I only use !l to check for bool's. Others may disagree.
Better variable names. This can cut down on the amount of stuff that has to be explained in comments. Renamed p to previous and q to current. (If you really don't wanna type so much -- prev and cur)
typedef struct list_integer {
    type value;
    struct list_integer *next;
} list_integer;

list_integer *removeKFromList(list_integer * l, int k)
{

    if (l == NULL) return NULL; // empty list becomes empty list

    // remove the occurrences of k at the beginning
    while (l != NULL && l->value == k) {
        list_integer* temp = l;
        l = l->next;
        free(temp); // deallocate memory
    }

    if (l == NULL) return NULL; // list of only k's becomes empty list

    // already checked in the while loop. l->value != k
    list_integer *previous = l;
    list_integer *current = l->next;

    while (current != NULL) {
        if (current->value != k) {
            previous = current;
            current = current->next;
        } else {
            while (l != NULL && l->value == k) { // remove continuous occurrences of k
                list_integer* temp = current;
                current = current->next;
                free(temp); // deallocate memory
            }
            previous->next = current;
            if(current != NULL) {
                previous = current;
                current = current->next;
            }
        }
    }

    return l;
}

The version above keep's the OP's optimisation of not modifying the next pointer (ie p->next) multiple times if there are multiple continuous k's.
Version without this optimisation is a bit simpler
typedef struct list_integer {
    type value;
    struct list_integer *next;
} list_integer;

list_integer *removeKFromList(list_integer * l, int k)
{

    if (l == NULL) return NULL; // empty list becomes empty list

    // remove the occurrences of k at the beginning
    while (l != NULL && l->value == k) {
        list_integer* temp = l;
        l = l->next;
        free(temp); // deallocate memory
    }

    if (l == NULL) return NULL; // list of only k's becomes empty list

    // already checked in the while loop. l->value != k
    list_integer *previous = l;
    list_integer *current = l->next;

    while (current != NULL) {
        if (current->value != k) {
            previous = current;
            current = current->next;
        } else {
            list_integer* temp = current;
            current = current->next;
            previous->next = current;
            free(temp); // deallocate memory
        }
    }

    return l;
}
```


Additional model validation public HttpResponseMessage Post(LongUrlModel model)
{
    if (ModelState.IsValid)
    {
        var baseAddress = Request.RequestUri.ToString().TrimEnd('/');
        if (model.LongUrl.StartsWith(baseAddress))
        {
            ModelState.AddModelError("", "You cant shorten a URL that belongs to this domain");
            return Request.CreateErrorResponse(HttpStatusCode.BadRequest, ModelState);
        }

        *snip*
    }
    return Request.CreateErrorResponse(HttpStatusCode.BadRequest, ModelState);
}

I am not at all fond of the conditional logic here, it can be quite hard to follow. How can I refactor the additional model validation logic so that it will co-exist with the standard model validation nicely?

I feel as though there could be a way to refactor this code so that  Request.CreateErrorResponse only occurs in the code once, but I cannot see how at the moment.

In regards to your question:

  I feel as though there could be a way to refactor this code so that
  Request.CreateErrorResponse only occurs in the code once, but I cannot
  see how at the moment.

I would consider reducing the nesting (Arrow code) of the If statements and perform follow the return early mantra.

public HttpResponseMessage Post(LongUrlModel model)
{
    if (!ModelState.IsValid)
    {
        return BadRequest();
    }

    var baseAddress = Request.RequestUri.ToString().TrimEnd('/');
    if (model.LongUrl.StartsWith(baseAddress))
    {
        ModelState.AddModelError("", "You cant shorten a URL that belongs to this domain");
        return BadRequest();
    }

    // Perform the valid code logic here
}

private HttpResponseMessage BadRequest()
{
    return Request.CreateErrorResponse(HttpStatusCode.BadRequest, ModelState);
}

In regards to your other question

  I am not at all fond of the conditional logic here

There's a few things I can think of you could try.

Create a custom validation attribute and decorate the LongUrl property.

  public class UrlLengthAttribute: ValidationAttribute
  {
      public UrlLengthAttribute()
      {
      }

      protected override ValidationResult IsValid(object value, ValidationContext validationContext)
      {
        var httpContext = new HttpContextWrapper(HttpContext.Current);
        var url = value as string;

        if(string.isNullOrWhiteSpace())
        {
          return base.IsValid(value, validationContext);
        }

        // I'm not 100% on this code but you get the general idea
        var baseAddress = httpContext.RequestUri.ToString().TrimEnd('/');

        if(url.StartsWith(baseAddress))
        {
          return new ValidationResult(this.FormatErrorMessage(validationContext.DisplayName));
        }

        return null;
      }
  }

You can then use this to decorate your model:

    public class LongUrlModel
    {
        [UrlLength(ErrorMessage = "You cant shorten a URL that belongs to this   domain")]
        public string LongUrl { get; set; }
    }

You could the extract the model validation out into a separate Validator class and use that in the controller instead.  At the very least it might be moving towards the lines of creating a unit testable module.

  public class LongUrlModelValidator
  {
     public LongUrlModelValidator(HttpContextBase httpContext)
     {
      // store and use
     }

     public bool Validate(LongUrlModel model)
     {
      // perform validation logic here
     }
  }


Transaction.atomic with continuations I have a view that looks like this:

@transaction.commit_on_success
def view(request):
    do_stuff(...)
    if condition(...):
        result = do_other_stuff(...)
        transaction.commit()
        send_email(result)
    return HttpResponse(...)

Assume everything with (...) can touch the database.

There are currently two main cases:

condition is true, do_stuff() and do_other_stuff() are done in transaction 1, the transaction is saved, then the e-mail is sent and HttpResponse is done in transaction 2
condition is false, everything happens in transaction 2

I want to rewrite this with transaction.atomic. The important requirement is: the e-mail should only be sent if do_other_stuff() really gets saved.

Obviously I can't use @atomic around the whole view, because I wouldn't be able to commit, so my first shot looks something like:

def view(request):
    should_send_email = False
    with transaction.atomic:
        do_stuff(...)
        if condition(...):
            result = do_other_stuff(...)
            should_send_email = True
        response = HttpResponse(...)
    if should_send_email:
        should_send_email(result)
    return response

It's kind of acceptable, but it clobbers the control flow. How to rewrite it better?

I was thinking about something like:

def view(request):
    with AtomicWithContinuation as a:  # new context manager
        do_stuff(...)
        if condition(...):
            result = do_other_stuff(...)
            a.after_commit(lambda: send_email(result))
        return HttpResponse(...)

which looks easier on the eyes, so I've rolled up a context manager like:

class AtomicWithContinuation(object):

    def __init__(self, *args, **kwargs):
        self.atomic = transaction.atomic(*args, **kwargs)
        self._after_commit = []
        self._after_rollback = []

    def after_commit(self, cb):
        self._after_commit.append(cb)

    def after_rollback(self, cb):
        self._after_rollback.append(cb)

    def __enter__(self):
        self.atomic.__enter__()
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        try:
            self.atomic.__exit__(exc_type, exc_val, exc_tb)
        except Exception:
            # atomic.__exit__ itself threw an exception
            # - assume a rollback has been done
            for cb in self._after_rollback:
                cb()
            raise
        if exc_val is not None:
            # Wrapped block raised an exception,
            # so atomic had to do a rollback
            for cb in self._after_rollback:
                cb()
        else:
            for cb in self._after_commit:
                cb()

Does this implementation make sense? Is this a good approach to take? Also, can I trust my assumptions in __exit__?

I don't think there's anything wrong with the should_send_email version of the code. But I can see that in more complex cases there would be a readability benefit in keeping the after-commit logic next to the condition.
There's no documentation. How do I use the AtomicWithContinuation class? What methods does it have? What guarantees does it provide about which callbacks will be called, when, and in what order?
The name could be improved: callbacks are not the same as continuations.
It would make sense for the after_commit and after_rollback methods to take *args and **kwargs to be passed to the callback:

def after_commit(self, cb, *args, **kwargs):
    """Call cb, passing *args and **kwargs, when this transction commits."""
    self._after_commit.append((cb, args, kwargs))

That would allow you to omit the lambda:

a.after_commit(send_email, result)

There's repeated code for calling all the callbacks in a list. This could be made into a function:

def run_callbacks(callbacks):
    """Run the callbacks in the iterable."""
    for cb, args, kwargs in callbacks:
        cb(*args, **kwargs)

You ask, "can I trust my assumptions in __exit__?" Well, there seem to be three assumptions:

If atomic.__exit__ is called with exc_val=None, it commits the transaction.
If atomic.__exit__ is called with any other value of exc_val, it rolls back the transaction.
If atomic.__exit__ raises an exception, then the transaction was rolled back.

Assumptions 1 and 2 are guaranteed by the docstring for the Atomic class, which says:

  __exit__ commits the transaction or releases the savepoint on normal exit, and rolls back the transaction or to the savepoint on exceptions.

It would be worth adding a comment to your __exit__ method quoting or linking to this guarantee.

Assumption 3 is not guaranteed anywhere I can find, and a look at the source for the Atomic.__exit__ method shows that it tries to roll back the transaction, but this might fail, possibly ending up with the connection being closed, or the needs_rollback flag being set.


Find char which appears maximal number of times I had 15 minutes to code the following question:

Given a file name return the char which appears maximal number of times.

please do not take into account the unit test.
Please look at the final foreach loop, I could have also used a for loop, I have doubts what is the best way to implement finding a max value and get the key from the dictionary.

Also please comment about code style.
Thanks

using System.Collections.Generic;
using System.IO;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{

    [TestClass]
    public class GetMostRepeatedCharQuestion
    {
        [TestMethod]
        public void TestForAasMax()
        {
            char result = GetMaxCharHelper.GetMaxReaptedCharFromFile("MaxA.txt");
            Assert.AreEqual('A', result);
        }
    }

    public class GetMaxCharHelper
    {
        public static char GetMaxReaptedCharFromFile(string fileName)
        {
            Dictionary<char, int> charToCount = new Dictionary<char, int>();
            using (var streamReader = new StreamReader(fileName))
            {
                string line = streamReader.ReadLine();
                while (line != null)
                {
                    char[] charArray = line.ToCharArray();
                    foreach (var currentChar in charArray)
                    {
                        if (charToCount.ContainsKey(currentChar))
                        {
                            charToCount[currentChar]++;
                        }
                        else
                        {
                            charToCount.Add(currentChar, 1);
                        }
                    }
                    //don't forget to get next line when reading from a file
                    line = streamReader.ReadLine();

                }

                int maxCount = 0;
                char maxChar = '\0';
                foreach (var current in charToCount)
                {
                    if (current.Value > maxCount)
                    {
                        maxCount = current.Value;
                        maxChar = current.Key;
                    }
                }
                return maxChar;
            }
        }
    }
}

According to a modern C# and LINQ you could try to "shock" interviewer with solving in a row:

var res = File.ReadAllText(path)
            .Where(ch => char.IsLetter(ch))
            .GroupBy(x => x)
            .OrderByDescending(x => x.Count())
            .First()
            .Key;


Java design for dimensions and units I created this abstract class:

public abstract class MeasurementType {
  protected String name;
  protected String[] units;

  public MeasurementType() {}

  public MeasurementType(String name) {
    this.name = name;
  }

  protected void setName(String name) {
    this.name = name;
  }

  protected String getName() {
    return name;
  }

  protected void setUnits(String[] values) {
    this.units = values;
  }
}

Then I thought to create to other classes that were its subtypes:

public class Acceleration extends MeasurementType {
  private String name;

  public Acceleration () {
    super();
  }

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

public class Density extends MeasurementType {
  private String name;

  public Density() {
    super();
  }

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

Plenty to choose from but these were the first two types that cam to my mind, the first question might be what the need for the subtypes are since there isn't anything in those classes that differentiates them apart enough (at least in my implementations) to give them the right to exist as their own entities, but for the sake of the example, lets say they had their own arrays containing units for each distinct type, so density would have kilograms, grams etc.. and acceleration would have mph, kmph etc..

Finally, I have this run class which I quickly made up:

public class run {

  public run() {}

  public static MeasurementType testType() {
    Acceleration a = new Acceleration("meters per second");
    return (MeasurementType) a;
  }

  public static void main(String[] args) {
    MeasurementType mt = testType();
    System.out.println(mt.getClass().toString());
    System.out.println(mt.getClass().getName());

    String type = "acceleration";
    String[] units = new String[8];

    Object mType;
    if(type.equals("acceleration")) {
      mType = new Acceleration();
    } else if(type.equals("density")) {
      mType = new Density();
    } else {
      mType = new Object();
    }

    System.out.println(mType.getName());
  }
}

This is where I encountered the problem that I was thinking about. I was using strings to determine the type that I would instantiate, but the problem is, by default right at the end of the conditional statements I instantiate Object because otherwise the compiler would complain that the mType variable wouldn't have been initialised. I can't create a MeasurementType object since it is an abstract class.

I guess this is more of a design question, but is there a better way of determining the class to instantiate? Please assume that the String type = "acceleration" came from a drop down or somewhere from some user interface, I have just hard coded it in because it isn't really necessary for the question.

Could someone please shed some light on this design fault as I see it please?

Using strings in themselves to determine the MeasurementType isn't the biggest problem, but you really don't need to create classes and subclasses and stuff for this.

Instead, use an enum!

public enum MeasurementType {
    DENSITY, ACCELERATION;
}

In this case you can use this code to grab the MeasurementType:

String type = ...;
MeasurementType mType = MeasurementType.valueOf(type.toLowerCase());

Note however that this will throw an exception if the type is not found. So instead, you might want to consider using a Map<String, MeasurementType> where you add all known MeasurementTypes (preferably in a static initializer block), or you can loop through MeasurementType.values() and scan for the one with the right name.

Also remember that enums can have methods, implement interfaces, override methods, and contain fields.

As I'm not sure what your ultimate goal is, here's an example of what an enum can do:

public enum MeasurementType {
    DENSITY("test"),
    ACCELERATION("test2") {
        @Override
        public int transform(int value) {
            return 0;
        }
    },
    SOMETHING_ELSE("test3")
    ;

    private final String test;

    private MeasurementType(String test) {
        this.test = test;
    }

    public int transform(int value) {
        return value;
    }
}


Context manager for SMTP connections My code right now look like this

@contextmanager
def smtp_connection(host, user=None, passwd=None, timeout=5):
    conn = None # smell here
    try:
        conn = SMTP(host=host, timeout=timeout)
        conn.ehlo_or_helo_if_needed()
        if user and passwd:
            conn.login(user=user, password=passwd)
        logger.debug('SMTP connected')
        yield conn
    except Exception as e:
        raise e
    finally:
        if conn: # and here
            conn.quit()

In recipes for ExitStack there is a suggestion to replace try-finally and flag variables with this

with ExitStack() as stack:
    stack.callback(cleanup_resources)
    result = perform_operation()
    if result:
        stack.pop_all()

But this doesn't use result in cleanup_resources. So in my case it still would be

with ExitStack() as stack:
    result = None
    stack.callback(lambda conn: conn.quit())
    result = POP3() # code from above here
    if result:
        stack.pop_all()

except Exception as e:
    raise e

First, you could simplify this to

except Exception:
    raise

Second, since you only re-raise it, you are not prepared to handle any Exception that could appear either with your code or the code managing the connection returned by your context manager. Thus you don't need that except clause.

Now the only thing left to manage is the state of the connection. Since there is no exception handling performed by your code, you are free to create the connection out of the try … finally and use that mechanism to only close the connection whatever happened:

@contextmanager
def smtp_connection(host, user=None, passwd=None, timeout=5):
    conn = SMTP(host=host, timeout=timeout)
    try:
        conn.ehlo_or_helo_if_needed()
        if user and passwd:
            conn.login(user=user, password=passwd)
        logger.debug('SMTP connected')
        yield conn
    finally:
        conn.quit()

You could also simplify the design by separating concerns. As it stand, your function does two things:

manage the connection;
perform some initial setup.

By delegating to a second context manager, you could separate these two behaviors into reusable bits:

@contextmanager
def smtp_connection(host, timeout):
    connection = SMTP(host=host, timeout=timeout)
    try:
        yield connection
    finally:
        connection.quit()

@contextmanager
def smtp_setup(host, user=None, passwd=None, timeout=5):
    with smtp_connection(host, timeout) as conn:
        conn.ehlo_or_helo_if_needed()
        if user and passwd:
            conn.login(user=user, password=passwd)
        logger.debug('SMTP connected')
        yield conn

But, looking at the second context manager, there is nothing to manage anymore since there is no teardown/cleanup anymore. Thus it is best to provide it as an independant function:

@contextmanager
def smtp_connection(host, timeout=5):
    connection = SMTP(host=host, timeout=timeout)
    try:
        yield connection
    finally:
        connection.quit()

def smtp_setup(conn, user=None, passwd=None):
    conn.ehlo_or_helo_if_needed()
    if user and passwd:
        conn.login(user=user, password=passwd)
    logger.debug('SMTP connected')

You would then need to change your calling code from

with smtp_connection(h, u, p, t) as conn:
    # do stuff

to

with smtp_connection(h, t) as conn:
    smtp_setup(conn, u, p)
    # do stuff

In the end, I personally don't like to have to manage the try ... finally inside the context manager. I don't find that natural as I preffer to write an explicit class using __enter__ and __exit__:

class smtp_connection:
    def __init__(self, host, timeout):
        self.smtp = SMTP(host=host, timeout=timeout)
    def __enter__(self):
        return self.smtp
    def __exit__(self, exc_type, exc_value, exc_trace):
        self.smtp.quit()

Using a class could also let you wrap this thing around SMTP directly:

class smtp_connection(SMTP):
    def __init__(self, host, timeout):
        super().__init__(host=host, timeout=timeout)
    def __enter__(self):
        return self
    def __exit__(self, exc_type, exc_value, exc_trace):
        self.quit()
    def setup(self, user=None, password=None):
        self.ehlo_or_helo_if_needed()
        if user and passwd:
            self.login(user=user, password=passwd)
        logger.debug('SMTP connected')

Use it like:

with smtp_connection(h, t) as conn:
    conn.setup(u, p)
    # do stuff


How to get a centered mean (excluding max and min value) of a list in Python? I'm learning Python & practising from this site and here is the particular problem at hand:

Return the "centered" average of an array of ints, which we'll say is the mean average of the values, except ignoring the largest and smallest values in the array. If there are multiple copies of the smallest value, ignore just one copy, and likewise for the largest value. Use int division to produce the final average. You may assume that the array is length 3 or more.
centered_average([1, 2, 3, 4, 100]) → 3
centered_average([1, 1, 5, 5, 10, 8, 7]) → 5
centered_average([-10, -4, -2, -4, -2, 0]) → -3

My solution is as follows:
def centered_average(nums):
  items = len(nums)
  total = 0
  high = max(nums)
  low = min(nums)
  for num in nums:
    total += num
  aveg = (total -high-low) / (items-2)
  return aveg

The above code works fine. I want to ask more experienced programmers if this could be done in a better manner - or is this solution fine?

This code can be written more concisely in a couple of ways:

You can use the sum function rather than an explicit loop:

(sum(nums) - max(nums) - min(nums)) / (len(nums) - 2)

You could also use sorting and slicing to remove the extreme values, which is more concise but less efficient:

sum(sorted(nums)[1:-1]) / (len(nums) - 2)

The slice notation [1:-1] takes the elements of a list starting with the second element (index 1) and finishing with the last-but-one element (index -1, i.e. indexing from the end of the list rather than the start)

If you are using Python 3.4+ you can use the statistics module, which has a mean function:

from statistics import mean

mean(sorted(nums)[1:-1])


Find line of best fit This is an update of Test thousands of combinations quickly.

I have a physical robot which has a function, turn(degrees). For different robots, there will be small differences in the accuracy of the turn. I have fine turning variables, multiplier and adder. The degrees are multiplied by the multiplier, and then adder is added on.

The data set will be manually created by someone requesting a turn, and recording what the actual turn was. This means the data set will usually be around 4 to 8 results long.

The PRECISION is how accurate we want the result to be. Ideally it would be as precise as possible, but since the robot has a fair amount of unpredictability, 2 d.p is fine.

The Code:

from numpy import arange

# list of actual test results in the form
# (requested turn degrees, actual turn degrees)
REAL_RESULTS = (
    (90, 101),
    (100, 112),
    (110, 123),
    (120, 134),
    (130, 145),
)
# how accurate a multiplier you want
PRECISION = 0.001
# multiplier will be less than this
# and more than negative this
MULTIPLIER_BOUNDS = 10
# number of results to print
PRINT_TOP_RESULTS = 3

def calculateLine(multiplier, test_cases):
    """Calculates the absolute error and adder."""
    # calculate the error with no adder
    error_no_adder = 0
    for test in test_cases:
        error_no_adder -= test[0] * multiplier - test[1]
    # the adder is the average error
    adder = error_no_adder / len(REAL_RESULTS)

    # calculate error with the adder
    error = 0
    for test in test_cases:
        error += abs((test[1] - adder) / multiplier - test[0])

    return error, adder, multiplier

if __name__ == "__main__":
    # calculate results for every multiplier
    results = [calculateLine(multiplier, REAL_RESULTS) for multiplier in
               arange(-MULTIPLIER_BOUNDS, MULTIPLIER_BOUNDS, PRECISION)]
    # sort from lowest error to highest error
    results.sort()

    printed_num = 0
    i = -1
    last_multiplier = 999
    # print the top (least error) x results
    while printed_num < PRINT_TOP_RESULTS:
        i += 1
        # don't print results with very similar precision
        if abs(results[i][2] - last_multiplier) < PRECISION * 20:
            continue
        printed_num += 1
        last_multiplier = results[i][2]
        # print average error, the adder and multiplier
        print("Average error: {:.3f}\nAdder: {:.3f}\nMultiplier: {:.3f}\n"
              .format(*results[i]))

Have I followed standard coding conventions? pep8online says that it is fine.

Is it "better" - performance or conventions - to map the results or use list comprehension? I had previously used map and the calculate function used the global variable REAL_RESULTS, but I changed this because it defeats the purpose of reusable modules if a function relies on predefined global variables.

Are there any areas where performance could be improved? Performance isn't really an issue anymore because it has been hugely improved from my original code, but it's still nice to know if it could be better. Also this code could theoretically be used with a much larger data set where performance could matter.

PEP-8 issue: Function names should be lowercase_with_underscores.