Time and Space Complexity of Prime factorization I have written a function that prints all the prime factors for a given number. Here is my code

static void printPrimeFactorization(int number) {
    if (number <= 1 || isPrime(number)) { // If given number is already prime, no more factors for it
      System.out.println(number);
      return;
    }
    // check divisibility of given number starting from 2 to nextPrime(that is less than given number)
    for (int nextPrime = 2; nextPrime < number; nextPrime = getNextPrimeNumber(nextPrime)) {
      while (number % nextPrime == 0) { // check divisibility, until number is not divisible
        System.out.println(nextPrime);
        number = number / nextPrime;
        if (isPrime(number)) {
          System.out.println(number);
          return;
        }
      }
    }
  }

For brevity I am not writing the isPrime() and  getNextPrimeNumber() here

I am learning to calculate time complexity, and space complexity.
What is the exact time complexity of my code above starting from for loop having while loop in it

I guess Time complexity is O(log n) - Logarithmic time - as the total number of iterations is <= n/2 Correct me if my understanding is wrong
Space complexity is O(1) - constant time - As no extra space used other than simple variable assignments.

UPDATE:

static boolean isPrime(int number) {
    if (number == 0 || number == 1) {
      return false;
    }
    for (int i = 2; i <= Math.sqrt(number); i++) {
      if (number % i == 0) {
        return false;
      }
    }
    return true;
  }

static int getNextPrimeNumber(int number) {
    while (!isPrime(++number)) {
    }
    return number;
  }

isPrime()

Complexity

This function contains a simple loop that iterates up to Math.sqrt(number) times, so assuming Math.sqrt(...) can be computed in \$O(1)\$ time, the function has \$O(\sqrt N)\$ time complexity.

Review

This function is terribly inefficient. Math.sqrt(number) is computed \$\lfloor \sqrt N \rfloor\$ times, yet the value is a constant.  This should be moved out of the loop.

The function fails when given a negative number.  The square-root is returned as NaN, the for loop executes zero times, and true is returned.

2 is the only even prime number.  It can easily be called out as a special case (like you are doing for 0 and 1, allowing the for loop to consider only odd numbers starting at 3, which should cut the function time in half.

Main Function - Outer loop

Complexity

Consider this loop:

    for (int nextPrime = 2; nextPrime < number; nextPrime = getNextPrimeNumber(nextPrime)) {
        ...
    }

The getNextPrimeNumber(int number) is a simple function which increments a number by one, and tests whether or not it is prime.  These two can be combined into an equivalent simpler loop, which is easier to reason about:

    for (int nextPrime = 2; nextPrime < number; nextPrime++) {
        if (isPrime(nextPrime)) {
            ...
        }
    }

Now, we can see that this loop iterates number - 2 times, so isPrime(nextPrime) is called number - 2 times.  This gives us a time complexity of \$O(N^{3/2})\$ without considering the inner loop.

Inner Loop

Complexity

The inner statement (the while loop) is executed for each prime number the outer loop finds.  From the Prime Number Theorem, we know that the number of primes \$π(N)\$ is approximately \$\frac{N}{\log N}\$.

Since the while loop is dividing the number by a constant factor, p, the prime number from the outer loop, it will execute a maximum of \$log_{p} N\$ times.  After each division, isPrime(number) is called.  This means \$log N\$ executions of a \$O(\sqrt N)\$ algorithm, so the inner statement is \$O(\log N \sqrt N)\$.

Executed for each prime number, this gives \$O(\frac{N}{\log N} \log N \sqrt N)\$, or \$O(N^{3/2})\$.

Since both portions have \$O(N^{3/2})\$ complexity, the overall complexity is \$O(N^{3/2})\$.

Review

The trial division while(number % nextPrime == 0) loop will exit once all of the factors of nextPrime have been divided out of number.  isPrime(number) can't become true while more than one factor of nextPrime exist, and since isPrime() is an "expensive" \$O(\log N)\$ operation, it would be more efficient to remove as many multiples of nextPrime as possible, and only then checking if the resulting number is prime.  In short, when the while loop executes one or more iterations, the isPrime() should execute once, but if the while loop executes 0 times, isPrime() shouldn't be executed at all.

Overall

You've separated isPrime() out from determining the factors of number, but isPrime() determines whether a number is prime or not by doing trial divisions, and you need to do trial divisions to remove factors from number.  One function which does both operations would be more efficient:

divide out as many factors of 2 as possible
starting with a divisor of 3, and increasing by 2:

if number can be divided by the divisor:
repeat as many times as possible:

number /= divisor

stop, if number < divisor * divisor

if stopped, and number > 1:

number is last factor


Force attribute value on potentially non-existent or locked PyNode I am working in Maya using PyMEL (my goal is to leverage PyMEL to create more readable, object-oriented, Pythonic code than if I'd used maya.cmds). I need to set an attribute value on an arbitrary node. The attribute may not exist or, if it does exist, may be locked. I found that setAttr with force=True did not account for all these scenarios, so I made my own.

import pymel.core as core

def _maya_force_attribute(self, pynode, name, value, data_type="string", keyable=False, lock=False):

    if pynode.hasAttr(name):
        pynode.setAttr(name, lock=False)
        pynode.deleteAttr(name)

    pynode.addAttr(name, dataType=data_type)
    pynode.setAttr(name, value, keyable=keyable, lock=lock)

What I discovered (I think) is that when using set/add/deleteAttr, you can't often use multiple flags at the same time.

Is there a command sequence or a command/flag combo that achieves the same result more directly?

From the documentation link you provided:

  ‘force’ kwarg, which causes the attribute to be added if it does not exist.

So the force kwargs does not seem to allow you to set a new dataType.

Hence it seems that the only way to set a new dataType is to remove and recreate the attribute. From this case, it seems hard to further simplify your code.


Checking if IDs in array are not null and adding them into new array My view object:

{
    description: "2tik 2tags"
    id: 100
    portfolio: "TSLA"
    term_id_1: 260751
    term_id_2: 285493
    term_id_3: null
    ticker_1: "GOOG"
    ticker_2: "TSLA"
    ticker_3: ""
    timespan: "ld"
    top: ""
}

I need to grab the term_ids and stick them into a new array, but only if they are not null.

What I'm currently using:

function reSelectTags(view) {
    console.log('view',view);
    // Seperate term_ids:
    var term_ids = [];

    if (view.term_id_1 != null) {
        term_ids.push(view.term_id_1);
    }

    if (view.term_id_2 != null) {
        term_ids.push(view.term_id_2);
    }

    if (view.term_id_3 != null) {
        term_ids.push(view.term_id_3);
    }

    console.log('term_ids',term_ids);
}

This gets the job done, but I'm wondering if there is a better, cleaner way, perhaps on 1 or 2 lines that could accomplish this as well.

Since the property names are sequential, you can just put it into a for loop:

function reSelectTags(view) {
    var val, term_ids = [];
    for (var i = 1; i <= 3; i++) {
        val = view["term_id_" + i];
        if (val != null) {
            term_ids.push(val);
        }
    }
    console.log(term_ids);
}

You can also just put repeated code into a local function:

function reSelectTags(view) {
    var term_ids = [];

    function pushVal(name) {
        if (view[name] != null) {
            term_ids.push(view[name]);
        }
    }
    pushVal("term_id_1");
    pushVal("term_id_2");
    pushVal("term_id_3");
    console.log(term_ids);
}


Advent of Code 2017, Day 1: Sum of digits matching the next digit (circular list) I haven't used C++ for quite a while and wanted to practice a bit, so I decided to start simple and work through the Advent of Code 2017.

This is my solution to Part 1 of the Day 1 exercise "Inverse Captcha":

  The captcha requires you to review a sequence of digits (your puzzle
  input) and find the sum of all digits that match the next digit in the
  list. The list is circular, so the digit after the last digit is the
  first digit in the list.

  For example:

  1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth
  digit.
  1111 produces 4 because each digit (all 1) matches the next.
  1234 produces 0 because no digit matches the next.
  91212129 produces 9 because the only digit that matches the next one is the last digit, 9.

My program works as follows:

Read one line from stdin
Convert the line character-wise to a vector of decimal digits
Calculate the sum of matching digits
Write the result to stdout

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

// Convert the first line of the input stream to a vector of digits.
std::vector<int> read_digits(std::istream& input) {
    std::string line;
    std::getline(input, line);

    std::vector<int> digits(line.size());
    std::transform(
        std::cbegin(line), std::cend(line), std::begin(digits),
        [](char c) { return c - '0'; }
    );
    return digits;
}

// Return the sum of all digits in the list that match the next digit
// (the first digit is the "next" digit of the last digit).
int reverse_captcha(const std::vector<int>& digits) {
    int sum = 0;
    for (auto p = std::begin(digits); p != std::end(digits); p++) {
        auto next_p =
            (std::next(p) == std::end(digits)) ?
            std::begin(digits) : std::next(p);
        if (*p == *next_p) sum += *p;
    }
    return sum;
}

int main() {
    std::cout << reverse_captcha(read_digits(std::cin)) << '\n';
}

I'm compiling it with clang++-4.0 -std=c++14. I'm not sure if I actually use features of the newest standard, but I don't want to restrict myself to older versions.

Here are a few things I'm particularly curious about:

How can I separate iterating over the pairs of digits from calculating their sum if the pairs are equal? If I were using Python I would write one or two small generator functions, but I don't know yet if there is an equally simple way to do this in C++, or if this would become overkill.
Is there an elegant way to avoid the extra step of constructing a string line before creating the vector of digits?
Using - '0' for converting char → int feels like a hack to me, is there really no purpose-built function for this? (I'm used to int('5') → 5 from Python)

I think std::rotate can lead to a somewhat simpler approach:

get the input
create a copy
rotate the copy by one element
Accumulate the sum of elements that match between the two

Code might look something on this general order:

int sum_matching(std::vector<int> const &digits) {
    std::vector<int> copy{digits};

    std::rotate(copy.begin(), copy.begin()+1, copy.end());

    int sum = 0;
    for (int i=0; i<digits.size(); i++)
        if (digits[i] == copy[i])
            sum += digits[i];
    return sum;
}

I'm pretty sure you could hijack std::inner_product to do that final loop, but given its name, that would be misleading, so probably better avoided. On the other hand, if your compiler includes all the latest C++17 goodness, you could use std::transform_reduce though:

int main() {
    std::vector<int> inputs{1, 2, 3, 3, 1};

    std::vector<int> copy{inputs};
    std::rotate(copy.begin(), copy.begin()+1, copy.end());

    int result = std::transform_reduce(inputs.begin(), inputs.end(),
                    copy.begin(),
                    0,
                    [](int a, int b) { return a + b; },
                    [](int a, int b) { return a==b ? a : 0; });

    std::cout << result << "\n";
}

If you'd like to play with that using a (strictly prototype) implementation of transform_reduce, it's not terribly complex--something on this order:

template<class InputIterator1,
         class InputIterator2,
         class T,
         class BinaryOperation1,
         class BinaryOperation2>
T transform_reduce(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2,
                    T init,
                    BinaryOperation1 binary_op1,
                    BinaryOperation2 binary_op2)
{
    for ( ; first1 != last1; ++first1, ++first2) {
        init = binary_op1(init, binary_op2(*first1, *first2));
    }
    return init;
}

Note, however, that this is a purely serial implementation--part of the intent of transform_reduce is that it will support parallel implementation, which this doesn't (but that's mostly a restriction that binary_op1 and binary_op2 must be commutative and associative, not a requirement on the implementation). Note that the standard includes a number of overloads of std::transform_reduce--I've included an implementation of the one used in the preceding code.


Implemnting a Trie Data structures problem from HackerRank using Python3 I'm trying to write a better code in python. I don't know where to start checking. I want to make sure that I do write a best practice code.

This is the second problem in Hackerrank trie data structure:

  Given N strings. Each string contains only lowercase letters from (both inclusive). The set of  strings is said to be GOOD SET if no string is prefix of another string else, it is BAD SET. (If two strings are identical, they are considered prefixes of each other.)

  For example, aab, abcde, aabcd is BAD SET because aab is prefix of aabcd.

  Print GOOD SET if it satisfies the problem requirement.
  Else, print BAD SET and the first string for which the condition fails.

  Input Format

  First line contains , the number of strings in the set.
  Then next  lines follow, where  line contains  string.

  Output Format

  Output GOOD SET if the set is valid.
  Else, output BAD SET followed by the first string for which the condition fails.

  Sample Input00

7
aab
defgab
abcde
aabcde
cedaaa
bbbbbbbbbb
jabjjjad

  Sample Output00

BAD SET
aabcde

  Sample Input01

4
aab
aac
aacghgh
aabghgh

  Sample Output01

BAD SET
aacghgh

from sys import stdin

class Node:
    def __init__(self,char):
        self.character = char
        self.children = {}
        self.counter = 0
        self.end_word = False

class Trie:
    def __init__(self):
        self.root = Node('*')

    def add(self,word):
        current = self.root
        fail = False
        for char in word:
            if char not in current.children:
                new_node = Node(char)
                current.children[char] = new_node
                current = new_node
                new_node.counter += 1

            else:
                current = current.children[char]
                current.counter += 1
                if current.end_word:
                    fail = True

        current.end_word = True
        # first word > second word : second word is prefix of first word
        if current.counter >=2:
            fail = True

        return fail

if __name__ == "__main__":
    tree = Trie()
    n = stdin.readlines()
    for i in n[1:]:
        i = i.strip()
        add_check_string = tree.add(i)
        if add_check_string:
            print("BAD SET")
            print(i)
            break
    if not add_check_string:
        print("GOOD SET")

You could run autopep8 for minor style corrections (e.g. whitespaces).
Naming variables correctly is always extremely important, especially in a dynamic language, without indications about object type:

Your trie is a Trie, not just a tree.
n sounds like an integer. It could be called lines.
i also sounds like an integer. It could be line or word.

Using for/else syntax, you can refactor your main method without any flag.

if __name__ == "__main__":
    trie = Trie()
    _header, *lines = stdin.readlines()
    for line in lines:
        word = line.strip()
        if trie.add(word):
            print("BAD SET")
            print(word)
            break
    else:
        print("GOOD SET")

If you wish, you could replace the 3 last lines of add by return fail or current.counter >= 2


Get Date Taken from Image Is there a better way of doing this? I heard that BinaryReader and Exif parsing to get the property item is faster, but I have no idea how to do that, thanks for the help.
//we init this once so that if the function is repeatedly called
//it isn't stressing the garbage man
static Regex r = new Regex(":");

//retrieves the datetime WITHOUT loading the whole image
string[] GetDateTakenFromImage(string path)
{
    try
    {
        using (FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read))
        {
            using (Image myImage = Image.FromStream(fs, false, false))
            {
                PropertyItem propItem = myImage.GetPropertyItem(36867);
                string dateTaken = r.Replace(Encoding.UTF8.GetString(propItem.Value), "-", 2);
                if(string.IsNullOrEmpty(dateTaken))
                    return null;
                else
                    return DateTime.Parse(dateTaken).ToString("yyyy-MM-dd").Split('-');
            }
        }
    }
    catch
    {
        return null;
    }
}

//retrieves the datetime WITHOUT loading the whole image
string[] GetDateTakenFromImage(string path)

Function name and parameter are named well. You should use an XML-doc header to document the quirk that it doesn't need to load the entire image.
Overall I like that the method is concise: it mostly does only one thing, it's easy to read, and not needing to pre-load the whole image is a nice bonus.
It is strange to use string[] to denote a date. You should be returning a DateTime?.
Consider changing it to accept a Stream instead of a string path. Currently it's a bit burdensome to test your method because it requires a file path, even though all it's doing is getting a stream out of it anyway. By accepting a Stream instead, you can more easily put automated tests around it that use in-memory test data and avoid a whole litany of IO nonsense.

using (FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read))

fs is a poor name. Give it some more meaning, like imageStream. It can also be written a bit more concisely:
using (FileStream imageStream = File.OpenRead(path))

Likewise, myImage could just be named image.

PropertyItem propItem = myImage.GetPropertyItem(36867);

Avoid magic numbers -- that 36867 should be in a named constant somewhere:
const int ExifDateTimeOriginal = 0x9003;

Your error handling in general could be improved. If I was consuming this API, I would naturally expect exceptions relating to IO (file not found, file not accessible, not a valid image file, and so on) to propagate up. It's up to you whether you want to throw or return null in the case where everything is valid but the image simply doesn't have that tag.
You're returning null if anything goes wrong which makes this harder to test. Be aware that myImage.GetPropertyItem(36867); will throw if the tag is not present (which in my opinion is a totally non-exceptional circumstance), so if you do tweak your method to propagate other exceptions you will need to put that one line around a try-catch for that one exception.

The EXIF tag you're checking is encoded in ASCII according to the EXIF docs I've been able to find, so this should use Encoding.ASCII instead of Encoding.UTF8:
string dateTaken = r.Replace(Encoding.UTF8.GetString(propItem.Value), "-", 2);

You also don't need to do any string replacing. DateTime.ParseExact is handy for parsing dates encoded in custom formats:
string dateTaken = Encoding.ASCII.GetString(propItem.Value);
...
return DateTime.ParseExact(dateTaken.Trim('\0'), "yyyy:MM:dd HH:mm:ss", CultureInfo.InvariantCulture);

Lastly, if you want to really adhere to the letter of the spec then depending on how you decide to modify or keep your method contract you'll need to handle the case where the date and time are unknown and all non-colon characters are replaced with spaces.


Using RouteValueDictionary to convert anonymous type to query string I am trying to take advantage of the reflection built into RouteValueDictionary to add values to the query string of a URL. This is what I came up with. It seems to work, but I thought I would post it to see if anyone has any suggestions. It also uses the super-secret HttpValueCollection returned by ParseQueryString(), which automatically generates a URL-encoded query string.

So far the only negative is that it only works on URLs that can be parsed by UriBuilder (i.e. absolute URLs). So, relative URLs (i.e. "/Home/Index") will throw an exception. Maybe I should try the UriBuilder, and if that fails then try to extract/append the query string manually.

public static string AppendQueryValues(this string absoluteUrl, object queryValues)
{
    if (absoluteUrl == null)
        throw new ArgumentNullException("absoluteUrl");
    if (queryValues == null)
        throw new ArgumentNullException("queryValues");

    // Parse URL so we can modify the query string
    var uriBuilder = new UriBuilder(absoluteUrl);

    // Parse query string into an HttpValueCollection
    var queryItems = HttpUtility.ParseQueryString(uriBuilder.Query);

    // Parse & filter queryValues (using reflection) into key/value pairs
    var newQueryItems = new RouteValueDictionary(queryValues)
        .Where(x => !queryItems.AllKeys.Contains(x.Key));

    // Add new items to original collection
    foreach (var newQueryItem in newQueryItems)
    {
        queryItems.Add(newQueryItem.Key, newQueryItem.Value.ToString());
    }

    // Save new query string (HttpValueCollection automatically URL encodes)
    uriBuilder.Query = queryItems.ToString();

    return uriBuilder.Uri.AbsoluteUri;
}

Instead of catching an exception if the url is relative, use the System.Uri class to see if it is an absolute Uri.


Grading scores from 0.0 to 1.0 Write a program to prompt for a score between 0.0 and 1.0. If the score is out of range, print an error. If the score is between 0.0 and 1.0, print a grade using the following table:

Score  | Grade
-------+------
>= 0.9 | A
>= 0.8 | B
>= 0.7 | C
>= 0.6 | D
 < 0.6 | F

If the user enters a value out of range, print a suitable error message and exit. For the test, enter a score of 0.85.

try:
    inp = raw_input("Enter a number between 0.0 and 1.0: ")
    score = float(inp)
    if (score >= 1.0):
        print("You didn't follow instructions")
        exit()
    elif (score >= 0.9):
        print("A")
    elif (score >= 0.8):
        print("B")
    elif (score >= 0.7):
        print("C")
    elif (score >= 0.6):
        print("D")
    else:
        print("F")
except:
    print("Please enter numerical numbers")
    exit()

Yes, your code is correct, although I would recommend adding comments, and following the style guidelines of PEP8. Here are a few tips I have.

You should specify what type of error you want to except. If you just type except:, other errors could go un-noticed.
Typing exit() really isn't needed here. The program will terminate either way.
You don't need to put parentheses around conditionals in if statements.
It seems also that you're using Python2, so no parentheses are needed for print.
You could make this into a function that returns the grade.

Here's my re-factored version of the code.

def return_grade(user_input):
    """
    Return the user's grade based on the following table.
    Score  | Grade
    -------+------
    >= 0.9 | A
    >= 0.8 | B
    >= 0.7 | C
    >= 0.6 | D
    < 0.6 | F
    """
    try:
        user_score = float(user_input)
        if user_score > 1.0:
            return "Please enter a number between 0.0 and 1.0"

        elif user_score >= 0.9:
            return "Grade: A"

        elif user_score >= 0.8:
            return "Grade: B"

        elif user_score >= 0.7:
            return "Grade: C"

        elif user_score >= 0.6:
            return "Grade: D"

        elif user_score < 0.6 and user_score >= 0.0:
            return "Grade F"
    except ValueError:
        print("Please enter a number.")

print return_grade(raw_input("Enter a number between 0.0 and 1.0"))


Joining multiple functions data in one array This bit of code gathers data from two methods and puts it into an array. The code works fine but it doesn't look pretty and I feel like there is a better way of doing what I have done.

public static function RagUpdate()
{
    $MachineOnOffStatus = self::RagOnOffStatus();
    $ActiveMachine = array();
    foreach ($MachineOnOffStatus as $Key => $val) {
        if ($val['DateDifference'] < 360) {
            $ActiveMachine[$val['controllerID']]['controllerID'] = $val['controllerID'];
            $ActiveMachine[$val['controllerID']]["DateDiff"] = $val['DateDifference'];
        }
    }

    foreach (self::ActiveMachineCycleTime($ActiveMachine) as $Key => $val) {
        foreach ($ActiveMachine as $k => $v) {
            if ($val["controllerID"] == $v["controllerID"]) {
                $ActiveMachine[$v['controllerID']]["CycleTime"] = $val['ElaspedTime'];
            }
        }
    }
    return $ActiveMachine;
}

Output of this method:

array (size=5)
2 =>
array (size=3)
  'controllerID' => string '2' (length=1)
  'DateDiff' => string '136' (length=3)
  'CycleTime' => string '-61' (length=3)
28 =>
array (size=3)
  'controllerID' => string '28' (length=2)
  'DateDiff' => string '129' (length=3)
  'CycleTime' => string '-52' (length=3)
30 =>
array (size=3)
  'controllerID' => string '30' (length=2)
  'DateDiff' => string '96' (length=2)
  'CycleTime' => string '-45' (length=3)
37 =>
array (size=3)
  'controllerID' => string '37' (length=2)
  'DateDiff' => string '123' (length=3)
  'CycleTime' => string '-69' (length=3)
40 =>
array (size=3)
  'controllerID' => string '40' (length=2)
  'DateDiff' => string '89' (length=2)
  'CycleTime' => string '-75' (length=3)

I see some redundancy right off the bat:

$ActiveMachine[$val['controllerID']]['controllerID'] = $val['controllerID'];

If the key is the controllerID, do you need a separate controllerID underneath of it?  I would suspect not. You can use the $Key in place of $val['controllerID'] in the foreach below it.

As for the rest, do you have control over the output of the functions you are using?  Can the key of those arrays be used in a smarter way?  You are using $Key => $val, but you don't use $Key once.


Generate SQL query by loop I need to perform SQL query which will get products from database based on few dimensions which I will pass in URL.

import itertools

sql_where = ''
dimensions = ['a','b', 'c', 'd', 'e', 'f', 'f2', 'g']

for dimension in dimensions:
    for onetwo, direction in zip( range(1, 3), itertools.cycle('><') ):
        globals()[dimension+str(onetwo)] = str( request.GET.get( dimension+str(onetwo) ) )
        sql_where += " AND ( `{dimension}` {direction}= '{get_dimension}' OR '{get_dimension}' = ('None' OR '') )".format(dimension=dimension, direction=direction, get_dimension=globals()[dimension+str(onetwo)])

sql = """SELECT * FROM t_wishbone_dimensions WHERE 1=1""" + sql_where
print sql

Example output for /search?a1=34&a2=37&c1=50&c2=75

SELECT * FROM t_wishbone_dimensions
WHERE 1=1
AND ( `a` >= '34' OR '34' = ('None' OR '') )
AND ( `a` <= '37' OR '37' = ('None' OR '') )
AND ( `b` >= 'None' OR 'None' = ('None' OR '') )
AND ( `b` <= 'None' OR 'None' = ('None' OR '') )
AND ( `c` >= '50' OR '50' = ('None' OR '') )
AND ( `c` <= '75' OR '75' = ('None' OR '') )
AND ( `d` >= 'None' OR 'None' = ('None' OR '') )
AND ( `d` <= 'None' OR 'None' = ('None' OR '') )
AND ( `e` >= 'None' OR 'None' = ('None' OR '') )
AND ( `e` <= 'None' OR 'None' = ('None' OR '') )
AND ( `f` >= 'None' OR 'None' = ('None' OR '') )
AND ( `f` <= 'None' OR 'None' = ('None' OR '') )
AND ( `f2` >= 'None' OR 'None' = ('None' OR '') )
AND ( `f2` <= 'None' OR 'None' = ('None' OR '') )
AND ( `g` >= 'None' OR 'None' = ('None' OR '') )
AND ( `g` <= 'None' OR 'None' = ('None' OR '') )

What do you think about my solution?

Since I didn't want to setup a webserver for this, I added a bare class, which should behave in the same way as your request.GET:

class request:
    GET = dict(a1=34, a2=37, c1=50, c2=75)

You should avoid setting keys in globals(), it clutters the namespace too much. Instead just use the default keyword of the get method of a dictionary, which will give you the specified value if the key is not present.

get_dimension = request.GET.get(dim, 'None')

You can make your string formatting a bit easier to understand if you split it up a bit. I made the string itself a constant (avoiding having to allocate it multiple times) and used positional arguments, instead of keywords (which, admittedly, hurts the readability slightly).

Instead of doing a string addition every loop, it is better to append to a list and do one join at the end, because string addition means creating an intermediate new string, since strings are immutable.

sql = "SELECT * FROM t_wishbone_dimensions WHERE 1=1" + "\n".join(sql_where)

I would also use itertools.product to replace your double loop, so something like:

directions = {'1': '>', '2': '<'}
dimensions = ['a', 'b', 'c', 'd', 'e', 'f', 'f2', 'g']
for dimension, i in itertools.product(dimensions, ('1', '2')):
    direction = directions[i]
    ...

To improve readability you should separate the ANDs with a newline each (like you did in your example output).

Lastly, python has an official style guide, PEP8, which recommends having a blank after a comma in an argument list (in dimensions after 'a', one was missing), as well as not adding unnecessary whitespace (so usually no str( something ), but just str(something)).

Final code:

import itertools

class request:
    # should handle the same same as your `request.GET`
    GET = dict(a1=34, a2=37, c1=50, c2=75)

dimensions = ['a', 'b', 'c', 'd', 'e', 'f', 'f2', 'g']
DIRS = {'1': '>', '2': '<'}
AND_STR = "AND ( `{0}` {1}= '{2}' OR '{2}' = ('None' OR '') )"

sql_where = ['']
for dimension, i in itertools.product(dimensions, ('1', '2')):
    val = request.GET.get(dimension+i, 'None')
    sql_where.append(AND_STR.format(dimension, DIRS[i], val))
sql = "SELECT * FROM t_wishbone_dimensions WHERE 1=1" + "\n".join(sql_where)
print sql

Output:

SELECT * FROM t_wishbone_dimensions WHERE 1=1
AND ( `a` >= '34' OR '34' = ('None' OR '') )
AND ( `a` <= '37' OR '37' = ('None' OR '') )
AND ( `b` >= 'None' OR 'None' = ('None' OR '') )
AND ( `b` <= 'None' OR 'None' = ('None' OR '') )
AND ( `c` >= '50' OR '50' = ('None' OR '') )
AND ( `c` <= '75' OR '75' = ('None' OR '') )
AND ( `d` >= 'None' OR 'None' = ('None' OR '') )
AND ( `d` <= 'None' OR 'None' = ('None' OR '') )
AND ( `e` >= 'None' OR 'None' = ('None' OR '') )
AND ( `e` <= 'None' OR 'None' = ('None' OR '') )
AND ( `f` >= 'None' OR 'None' = ('None' OR '') )
AND ( `f` <= 'None' OR 'None' = ('None' OR '') )
AND ( `f2` >= 'None' OR 'None' = ('None' OR '') )
AND ( `f2` <= 'None' OR 'None' = ('None' OR '') )
AND ( `g` >= 'None' OR 'None' = ('None' OR '') )
AND ( `g` <= 'None' OR 'None' = ('None' OR '') )


Name-spaced JavaScript wrapped in self executing function Is there any point in wrapping this code in the self executing function declaring window and undefined? I've read that it improves performance etc... (NOTE I will be making use of the window at some point).

(function (window, undefined) { // THIS BIT HERE!
  var App = {
    init: (function () {
      $(document).ready(function () {
        App.alertMessage('Hello world');
      });
    })(),
    alertMessage: function (message) {
      alert(message);
    }
  }
})(window); // end closure

The IIFE/SEFE/closure/whatever

A quick discussion why we use "closures" for creating our code is that the purpose of the closure/IIFE/SEFE/whatever you want to call it, is to provide a scope where you are free to declare any variables for the internals to use, without polluting the global scope:

(function(ns){

  //I can declare tons of variables and functions here
  var a,b,c,d,e,f,g ...;

  //expose only foo to the namespace
  ns.foo = function(){
    //and foo can use them here
  }

}(this.myNS = this.myNS || {}));

//but out here, we call foo, use those variables
//but none of those variables are visible
myNS.foo();

//no a,b,c,d,e,f,g ... out here

window

Now, in the case of window, the idea that they are passed into the function is to have a local reference of whatever was pointed by them. It's because of the usage of that IIFE/SEFE/closure and how the compiler works.

//-3-found "a" here
var a = 1
(function(ns){
  //-2-no "a" here, going up
  ns.foo = function(){
    //-1-no "a" here, going up
    console.log(a);
  }
}(this.myNS = this.myNS || {}));

myNS.foo();

A quick trip into the how the compiler works is that when it tries to look for a variable/function, it searches through the local function scope first. If that variable/function is not found, it will look for it in the outer/containing scope. This goes on until the compiler finds that value or when you reach the global scope and declares it as non-existent.

In the code above, you crossed 2 scopes in order to find a. If a was declared lower into the scope, you could have minimized crossings. Now, wouldn't it be better if you provided window locally instead of having the compiler find it? YES, although:

performance gain is almost negligible
code structure might be more important than this minor optimization

undefined

For undefined, it's because undefined is mutable (it's not constant/final). Its value can be changed so that it would not be undefined anymore (but somewhat "pseudo-defined"). A quick code about that can be found here:

var a = {};
a.b === undefined; // true because property b is not set
undefined = 42;
a.b === undefined; // false, because undefined is something else

So what they did to overcome this "definable undefined" was to pass nothing into the function, and by default, passing nothing to the function and naming it something in the function gives it the value of "true undefined".

Personally, I don't pass in window and undefined into my closure for some reasons:

I don't check potentially undefined values against undefined. Since undefined values are falsy, loose comparison will tell if it is undefined or more like "unusable":

//instead of this:
if(potentiallyUndefined === undefined){...do stuff...}
if(typeof potentiallyUndefined === 'undefined'){...do stuff...}

//you can do this
if(potentiallyUndefined){...do stuff...}

Like I said, it's a minor/negligible performance gain, so I don't pass in window. Besides, how much of my code uses window anyway?


Storing user permissions to hierarchically structured data in SQL Server I'm developing a system that supports creating accounts and multiple users within every account that can each access a certain subset of data of their "parent" account.

The data is stored in a SQL Server database in the following tables:

Accounts: Id(guid, primary key), Title(nvarchar(200))
Users: Id(guid, primary key), Login(nvarchar), AccountId(guid, foreign key).

Now, I need to implement a concept of "Folders" and "Files" within accounts. Each account can have a number of files (an object with a name and a few other non significant properties) that can be arranged into folders (like a file system), and every user might have a permission to access a folder. "A user has permission to view a folder" means that this user can see all files within this folder and within all its subfolders. These folders/files also have to support a lot of moving around the hierarchy, renaming, editing, etc.

I have come up with the following table structure for this scenario:

Folders: Id(guid, primary key), Name(nvarchar(200)), AccountId(guid, foreign key)), ParentFolderId(guid, foreign key)
Files: Id(guid, primary key), Name(nvarchar(200)), FolderId(guid, foreign key),
UserFolderPermissions: Id(guid, primary key), FolderId(guid, foreign key), UserId(guid, foreign key)

This structure does the job of storing data correctly, but I also need to run some complex queries against it, like finding a complete path to a file or retrieving all files that current user has permissions to access. For that, I created a view that outputs all folders, files, and users who have permissions to access them:

WITH FolderWithPath AS
    (
        SELECT
            folder.Id,
            folder.Name,
            folder.AccountId,
            folder.ParentFolderId,
            CAST('/' + folder.Name + '/' AS NVARCHAR(4000)) AS Path
        FROM
            dbo.Folders folder
        WHERE
            (ParentFolderId IS NULL)

        UNION ALL

        SELECT
            self.Id,
            self.Name,
            self.AccountId,
            self.ParentFolderId,
            CAST(parent.Path + self.Name + '/' AS NVARCHAR(4000)) AS Path
        FROM
            dbo.Folders AS self
            INNER JOIN FolderWithPath AS parent ON self.ParentFolderId = parent.Id
    )

SELECT
    file.Id AS FileId,
    folder.AccountId,
    folder.Id AS FolderId,
    folder.Path AS Path,
    userFolderPathPermissions.UserId AS AuthorizedUserId
FROM
    FolderWithPath AS folder
    LEFT OUTER JOIN dbo.Files AS file ON file.FolderId = folder.Id
    LEFT OUTER JOIN
    (
        SELECT
            UserFolderPermissions.UserId,
            folder1.Path,
            folder1.AccountId
        FROM
            FolderWithPath folder1
            INNER JOIN UserFolderPermissions AS UserFolderPermissions ON folder1.Id = UserFolderPermissions.FolderId
    ) userFolderPathPermissions ON folder.AccountId = userFolderPathPermissions.AccountId AND folder.Path LIKE userFolderPathPermissions.Path +'%'

Now, this does seem to work, but I have certain performance concerns. Is it the best database structure to fit my needs? Is the query inside the view the optimal way to access the necessary data?

Due to different security issues, I am unable to test it in a real environment with millions of users performing hundreds of operations per second, so I would appreciate any advice regarding the code above.

I would only make minor adjustments to your SQL.

Refrain from using KEYWORDS or RESERVED words as column or table aliases. If you already have them as column names, enclose them in square brackets e.g. [Name], [Path]
I would put the commas in front to clearly define new columns. Versus code wrapped in multiple lines. It also makes trouble-shooting code easier.
If you put 1=1 at the top of a WHERE condition, it enables you to freely change the rest of the conditions when debugging a query. The SQL query engine will end up ignoring the 1=1 so it should have no performance impact.
I find it more convenient to see column alias's referenced from the left side
e.g.
, [Path] = CAST(pfdr.[Path] + fdr.[Name] + '/' AS NVARCHAR(4000))
Use a table expression instead of a correlated sub-query. It makes the select statement a bit more readable.
Check the Estimated Execution Plan Ctrl + L in Microsoft SQL Server Management Studio (SSMS) to check the performance of the query by pasting both SQL statements in a query window.

Here's an example.

Revised SQL

WITH
folder_paths
AS
(
    SELECT
          fdr.[Id]
        , fdr.[Name]
        , fdr.[AccountId]
        , f.[ParentFolderId]
        , [Path] = CAST('/' + fdr.[Name] + '/' AS NVARCHAR(4000))
    FROM
        dbo.[Folders] AS fdr
    WHERE
        1=1
        AND (fdr.[ParentFolderId] IS NULL)
    UNION ALL
    SELECT
          fdr.[Id]
        , fdr.[Name]
        , fdr.[AccountId]
        , fdr.[ParentFolderId]
        , [Path] = CAST(pfdr.[Path] + fdr.[Name] + '/' AS NVARCHAR(4000))
    FROM
        dbo.[Folders] AS fdr
        INNER JOIN folder_paths AS pfdr ON fdr.[ParentFolderId] = pfdr.[parent.Id]
)
,
user_folder_permissions
AS
(
    SELECT
          fprm.[UserId]
        , fdr.[Path]
        , fdr.[AccountId]
    FROM
        folder_paths AS fdr
        INNER JOIN dbo.[UserFolderPermissions] AS fprm ON fdr.[Id] = fprm.[FolderId]

)
SELECT
      [FileId] = fs.[Id]
    , fdr.[AccountId]
    , [FolderId] = fdr.[Id]
    , [Path] = fdr.[Path]
    , [AuthorizedUserId] = fprm.[UserId]
FROM
    folder_paths AS fdr
    LEFT JOIN dbo.Files AS fs ON fs.[FolderId] = fdr.[Id]
    LEFT JOIN user_folder_permissions AS fprm ON fdr.[AccountId] = fprm.[AccountId] AND fdr.[Path] LIKE fprm.[Path] + '%'


Merge two sorted lists of numbers Inputs are two sorted lists (of the same length) of numbers. I would like to return a new merged, sorted new list. I have written the following code, but most lines are used to deal with the end case. I am wondering if there is any better way to write it.

def merge(array1,array2):
    result = [0]*len(array1)*2

    i = 0 # left index
    j = 0 # right index

    for k in range(0,len(result)):
        # when none of the pointer is at the end of the list
        if i != len(array1)-1 and j != len(array2)-1:
            if array1[i] < array2[j]:
                result[k] = array1[i]
                i = i + 1
            elif array1[i] > array2[j]:
                result[k] = array2[j]
                j = j + 1
        # the following codes are used to deal with the end cases.
        # possible to write it more compactly?
        elif i == len(array1)-1:
            if j > len(array2)-1:
                result[-1] = array1[-1]
                return result
            elif array1[i] < array2[j]:
                result[k] = array1[i]
                result[k+1:] = array2[j:]
                return result
            else:
                result[k] = array2[j]
                j = j + 1
        elif j == len(array2)-1:
            if i > len(array1)-1:
                result[-1] = array2[-1]
            elif array2[j] < array1[i]:
                result[k] = array2[j]
                result[(k+1):] = array1[i:]
                return result
            else:
                result[k] = array1[i]
                i = i + 1

    return result

I'll answer your question by providing an alternative solution. IDK why you're over complicating this when everything that has to be done is to combine the two lists, then simply sort them:

def merge(array1, array2):
    array1.extend(array2)

    return sorted(array1)

print(merge([1, 3, 4, 7], [0, 2, 5, 6, 8, 9]))
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

The advantages of the above solution are:

there's less code so it's easier to maintain / read
it's using only two built-in functions (so assuming the lists are of a reasonable size, it should be quicker than implementing the sorting/merging in a loop)

There's also a one-liner which is even simpler than the above solution:

def merge(array1, array2):
    return sorted(array1 + array2)

print(merge([1, 3, 4, 7], [0, 2, 5, 6, 8, 9]))
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

You could also use the built-in heapq.merge for this.

Of course, if the lists are very large (like very large), merging two lists will totally make sense.

According to this SO answer unless len(array1 + array2) ~ 1000000 use:

L = array1 + array2
L.sort()

Those are just my 2-cents regarding the subject. I'll let somebody else comment on your code.

Extra: Even if practicing algorithms is a good idea, an even nicer aspect is knowing when / where to apply them.


Shopping List Application (Work in Progress) I'm new around here and want to involve myself with fellow developers and hopefully improve my skills here while attempting to help in any way I can with the knowledge I have so far. I'm a new Python programmer, been on and off it for years but have stuck to it recently officially.

I plan on making a career off of developing with it, whether it's data science, cyber security etc.

I plan on implementing some OOP in there instead of just straight functions:

import os

#create shopping list with automatic calculation

def display_help():
    print('''
    =======> Help <=======
    'HELP' to display this menu
    'START' to start creating your shopping list
    'SHOW' to display your current items
    'QUIT' to exit the program
    ''')
#create a list with the items needed
#

def clear_screen():
    os.system("cls" if os.name == "nt" else "clear")

#Create function to change values of current items or update price of items in the cart

def shopping_list():
    clear_screen()
    print('It\'s time to go shopping!')
    #Convert all floating point numbers to max digits of 2 after the decimal
    clear_screen()
    item_dict = {}
    print('Enter HELP at any moment if you need help or EXIT to return to the main menu')
    cart = 0
    def show_items():
        for key, value in item_dict.items():
            print(key + '-' * 5 + str(value))
        print('Current cart total: ',sum(item_dict.values()))
    while True:
        shop = input('Please enter an item: ')
        if shop.upper() == 'HELP':
            display_help()
            continue
        elif shop.upper() == 'EXIT':
           #Show total with taxes (or without taxes) with all the items in cronological order
           #start without taxes first
           print("Goodbye")
           break
        elif shop.upper() == 'SHOW':
            show_items()
            continue
        print(f'You have added {shop} to your list\n')
        try:
            cost = float(input(f'Price of {shop}: '))
            item_dict[shop] = cost
            cart = sum(item_dict.values())
            print(f'You entered {cost} as the price of {shop}\n')
            print(f'You now have {len(item_dict)} items in your list.\n')
            print(f'The total currently on your cart is {cart}')
            add_more_items = input('Would you like to add more items?(Y/N) ')
            if add_more_items == 'Y'.lower():
                continue
            else:
                print(f'Here\'s your cart and your total: \n')
                raise KeyboardInterrupt('Goodbye')
                continue
        except ValueError:
            print('Please enter a number')

def begin_attempt():
    print('Here\'s a list of possible commands: HELP, SHOP, EXIT')
    print('Welcome! What would you like to do?')
    while True:
        choose = input('> ')
        if choose.upper() == 'SHOP':
            print('Shopping has begun\n')
            shopping_list()
        elif choose.upper() == 'HELP':
            display_help()
            continue
        elif choose.upper() == 'EXIT':
            print("Goodbye")
            break

begin_attempt()

I still would like to add a lot more things, such as entering a specific state (or city in this case since I don't want to look up the taxes of every state) to calculate taxes, if there are discounts anywhere (I don't think I'll be adding that anytime soon or at all, but just an idea).

Welcome to Code Review SE!

I'll list some things I found while skimming over your code. This is unordered, and by no means exhaustive.

Most programming languages have a certain style guide associated with them. In the case of Python, it's PEP-8. It is in your best interest to comply with the points outlined there, as doing so will significantly improve readability.

Keep vertical whitespace to a minimum. Blank lines can aid in grouping related pieces of code together1, but in my opinion, you've gone a bit overboard. Having just two blank lines in between top-level function definitions is recommended.
Your function and variable names follow the PEP-8 naming conventions2. Good job, lots of people get this wrong at first.
Whenever you find yourself using an escaped quote character (\' or \"), you can simply surround the string with the other type of quotes.3 This makes the code more readable and reduces the chances of getting syntax errors. To take an example from the piece of code you wrote:

print('It\'s time to go shopping!')

... becomes:

print("It's time to go shopping!")

It's good practice to separate arguments to functions by a single space.4 An example from shopping_list():

print('Current cart total: ',sum(item_dict.values()))

... becomes:

print('Current cart total: ', sum(item_dict.values()))

Block comments should start with a space.5

It's nice that you added comments, but most of them are plain wrong. Never add comments that are simply a rewording of the code, and always assure your comments are up to date and correct. Let's go over your comments one by one.

Lines 3 through 6:

#create shopping list with automatic calculation

def display_help():

... not even close. I guess you reordered your functions at some point and forgot to update this comment.
Lines 14 through 17:

#create a list with the items needed
#

def clear_screen():

... the same goes for this comment. You don't create a list here. You don't do anything here.
Lines 22 through 26:

#Create function to change values of current items or update price of items in the cart

def shopping_list():

... finally, a comment that's in the right place. Unfortunately, this one falls under the 'documenting self-documenting code' category.6 Nitpick: you normally don't create a function, but define it.
...

I'm happy you found a way to avoid global variables, but nesting functions is rarely the right solution. show_items() should really be a top-level function, taking one argument.
By using f-strings, you're greatly limiting portability. I'd make a safe bet and use str.format() for now.
Let's see what happens when I exit the program:

Welcome! What would you like to do?
> EXIT
Goodbye

So far, so good. How about quitting from the 'SHOP' submenu?

Please enter an item: QUIT
You have added QUIT to your list

Price of QUIT:

Whoops, that's not what I was hoping to see. The help message clearly says:

'QUIT' to exit the program

Peculiar. Now that we're stuck with having to add a new item, let's go through with it and then exit.

Price of QUIT: 50
You entered 50.0 as the price of QUIT

You now have 1 items in your list.

The total currently on your cart is 50.0
Would you like to add more items?(Y/N) n
Here's your cart and your total:

Traceback (most recent call last):
File "ttt.py", line 86, in <module>
    begin_attempt()
File "ttt.py", line 78, in begin_attempt
    shopping_list()
File "ttt.py", line 64, in shopping_list
    raise KeyboardInterrupt('Goodbye')
KeyboardInterrupt: Goodbye

Oh my, that's ugly.

On a more serious note, there should only be one way to exit the program, and it should not be by means of an uncaught exception. You could do this a number of ways:

Put all of the prompts in a huge while-loop, then break from the loop when the user wants to exit. This gets messy very quickly. Avoid it.
Put all of the prompts in a huge while-loop, then call a function to exit. This is a much better alternative.

As an aside, it's almost never a good idea to raise a KeyboardInterrupt manually. Even a RuntimeError would be a better fit, but as I explained, cleanly exiting the script is ideal. The sys module provides sys.exit(), which is the best way of quitting Python scripts. Don't use exit(). It is a special function and should only be used in the Python REPL.
The main menu is broken:

    =======> Help <=======
    'HELP' to display this menu
    'START' to start creating your shopping list
    'SHOW' to display your current items
    'QUIT' to exit the program

> start
> show
> SHOW
> :(

try / except-constructs should capture the least amount of code possible. A clear violation of this principle, starting on line 52:

try:
    ... [12 lines skipped]
except ValueError:
    print('Please enter a number')

... the try-block only needs to encompass line 53, because that's the only line that could raise a ValueError.
On line 60, the input validation is off. The prompt suggests 'Y' and 'N' are valid inputs, but:

if add_more_items == 'Y'.lower():

... indicates it is not. If you want to do case-insensitive comparisons, call str.lower(), like you did in other instances. Alternatively, you could call str.casefold(), which also handles special characters like 'ß':

>>> "Straße".lower()
'straße'
>>> "Straße".casefold()
'strasse'

shopping_list is a bad function name. Function names are typically verbs. Maybe play_shopping_game?
String concatenation is in many ways inferior to string formatting. It's slower, harder to read, and less versatile: each argument needs to be casted to str if it is not already a string. Always prefer string formatting over concatenation.

References

1 PEP-8: Blank Lines

2 PEP-8: Naming Conventions

3 PEP-8: String Quotes

4 PEP-8: Whitespace in Expressions and Statements

5 PEP-8: Comments: Block Comments

6 Don't get me wrong, documenting functions is very important. The 'create a function' part is too verbose nevertheless. If you want to add formal documentation to functions, add docstrings! Docstrings are multiline strings placed below a function or class signature. For example:

def add(a, b):
    """Return `a` + `b`. Both arguments must be numbers."""
    return a + b

You can access the docstring as the object's __doc__ attribute:

>>> add.__doc__
'Return `a` + `b`. Both arguments must be numbers.'

... and in the Python REPL, you can use the built-in help():

add(a, b)
    Return `a` + `b`. Both arguments must be numbers.

There's also an official style guide for docstrings, called PEP-257.


Finding palindromes in C# This is my first foray into OOP, so I'd appreciate any kind of advice!

Here is the problem description:

  On the first line of the input, you will receive a number specifying
  how many lines of input to read. After that, the input consists of
  some number of lines of text that you will read and determine whether
  or not it is a palindrome.

  The only important factor in validating palindromes is whether or not
  a sequence of letters is the same backwards and forwards. All other
  types of characters (spaces, punctuation, newlines, etc.) should be
  ignored, and whether a character is lower-case or upper-case is
  irrelevant.

Here is my code:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("How many lines will you be entering? ");
        int numberOfLines = Int32.Parse(Console.ReadLine());
        string mergedLine = MergeMultipleLinesIntoOneLine(numberOfLines);
        bool isPalindrome = IsPalindrome(mergedLine);
        Console.WriteLine(isPalindrome ? "Palindrome" : "Not a palindrome");
    }

    public static string MergeMultipleLinesIntoOneLine(int numberOfLines)
    {
        int line = 1;
        var stringResult = new StringBuilder();
        do
        {
            Console.WriteLine("Please enter phrase #{0}: ", line);
            stringResult.Append(Console.ReadLine() + " ");
            line++;
        } while (line <= numberOfLines);

        return stringResult.ToString();
    }

    public static bool IsPalindrome(string someString)
    {
        string regexPattern = @"(?i)[^a-z]";
        string replacement = "";
        string amendedString = Regex.Replace(someString, regexPattern, replacement).ToLower();
        string reverseAmendedString = new string(amendedString.Reverse().ToArray());

        return amendedString.Equals(reverseAmendedString);
    }
}

Use a for loop where fit

public static string MergeMultipleLinesIntoOneLine(int numberOfLines)
{

    var stringResult = new StringBuilder();

    for (var line = 0; line < numberOfLines; line++)
    {
        Console.WriteLine("Please enter phrase #{0}: ", line);
        stringResult.Append(Console.ReadLine() + " ");
    }

    return stringResult.ToString();
}

MergeMultipleLinesIntoOneLine was very weird, when looping a fixed number of times, you should always use a for loop.

Refactor further

isPalindrome does two things:

It cleans the string.
It actually checks if it a palindrome.

These are two things, so we need two functions:

public static string clean(string s)
{
    string regexPattern = @"(?i)[^a-z]";
    string replacement = "";
    return Regex.Replace(s, regexPattern, replacement).ToLower();
}

and:

public static bool IsPalindrome(string someString)
{
    var amendedString = clean(someString);
    string reverseAmendedString = new string(amendedString.Reverse().ToArray());
    return amendedString.Equals(reverseAmendedString);
}

Do not put types into the name of the variables.

I am talking about regexPattern

Use constants

The cleaner Regex should be a class constant.

private const string cleaner = @"(?i)[^a-z]";

And replacement is unlikely to change, just use ""

clean is now simpler:

public static string clean(string s)
{
    return Regex.Replace(s, cleaner, "").ToLower();
}

Variables should be declared in the smallest possible scope, so putting the pattern inside the function is best. @Mat's Mug suggests inlining it, and I agree for such small a pattern.

Avoid unnecessary variables

bool isPalindrome = IsPalindrome(mergedLine);

Delete that line, just use:

Console.WriteLine(isPalindrome(mergedLine) ? "Palindrome" : "Not a palindrome");

Also isPalindrome can use less verbose names and be reduced to:

public static bool IsPalindrome(string someString)
{
    var cleaned = clean(someString);
    return cleaned.Equals(amendedString.Reverse().ToArray());
}

Seriously reducing noise.

Single responsibility system

@t3chb0t rightfully noted that isPalindrome still does two things, in fact, it is better to implement it like:

public static bool IsPalindrome(string text)
{
    return text.Equals(text.Reverse().ToArray());
}

And be careful to pass in cleaned strings.
Now it really does only one thing.


JSON schema validator I wrote a simple JSON schema validator.
The full code is over here on gist.github.com
However, the code without comment is...
validate = function(schema, instance) {
    var i;
    var errors = 0;

    var getType = function(attr) {
        return Object.prototype.toString.call(attr);
    }

    var addError = function(msg, attrs) {
        console.error(msg, attrs);
        errors += 1;
    }

    if(getType(schema) !== getType(instance)) {
        addError("Type Mismatch", [schema, instance]);
        return errors;
    }

    for(i in schema) {
        if(schema.hasOwnProperty(i)) {

            if(instance[i] == undefined) {
                addError("Property Not found", i);

            }
            //Special Handling for arrays
            else if( getType(schema[i]) === getType([]) ) {
                var zeroSchema = schema[i][0];
                var zeroInstance = instance[i][0];
                if(zeroInstance === undefined) {
                    continue;
                }
                for(var j=0;j<instance[i].length;j++) {
                    errors += validate(zeroSchema, instance[i][j]);
                }

            }
            //Special Handling for nested objects
            else if( getType(schema[i]) === getType({}) ) {
                errors += validate(schema[i], instance[i]);
            }

        }
    }
    return errors;

}

The code doesn't need the schema object to explicitly specify the type of object properties
unlike the official one
I'm fairly new to javascript. How do I improve the code?

I'd definitely change:

if(instance[i] == undefined) {
    addError("Property Not found", i);
}

to something more robust, e.g.

if (!instance.hasOwnProperty(i)) {
    addError("Property Not found", i);
}

Stylistically I'd change a few things as well:

Add a space between function names and (): function() to function ()
Add a space between if, for etc and (: for(i in schema) to for (i in schema)
Add in semi-colons after defining your functions:

var getType = function(attr) {
    return Object.prototype.toString.call(attr);
}; // <-- here.

Also, because JavaScript doesn't have block scope I like to define all my variables at the top of the function. e.g. you have:

validate = function (schema, instance) {

    // omitted code.

    for(var j=0; j<instance[i].length; j++) {
        errors += validate(zeroSchema, instance[i][j]);
    }

    // more code.
}

Whereas I would prefer j defined at the top of the function (as well as the extra spaces I've added).

Having said all of that, I wonder whether your solution is flexible enough - how would you specify an optional property? A property with a minimum and/or maximum value?


Multi-core OpenCV denoising I have ~40,000 JPEG images from the Kaggle melanoma classification competition. I created the following functions to denoise the images:
# Denoising functions
def denoise_single_image(img_path):
    img = cv2.imread(f'../data/jpeg/{img_path}')
    dst = cv2.fastNlMeansDenoising(img, 10,10,7,21)
    cv2.imwrite(f'../processed_data/jpeg/{img_path}', dst)
    print(f'{img_path} denoised.')

def denoise(data):
    img_list = os.listdir(f'../data/jpeg/{data}')
    with concurrent.futures.ProcessPoolExecutor() as executor:
        tqdm.tqdm(executor.map(denoise_single_image, (f'{data}/{img_path}' for img_path in img_list)))

The denoise function uses concurrent.futures to map the denoise_single_image() function over the full list of images.
ProcessPoolExecutor() was used based on the assumption of denoising as a CPU-heavy task, rather than an I/O-intensitve task.
As it stands now, this function takes hours to run. With a CUDA-configured Nvidia GPU and 6 GB VRAM, I'd like to optimize this further.
Is there any way to improve the speed of this function?
Multi-core processing documentation
OpenCV documentation

You may look at opencv Transparent API
#
imgUMat = cv2.UMat(img)
dst = cv2.fastNlMeansDenoising(imgUMat, 10,10,7,21)
#


Telling fibonaccis to the user Though this program tells the truth (unless you change the source code), it does tell Fibonacci numbers, depending on the user's input. Keeping in mind of all (or most) of the feedback given from previous questions, I wrote this program to see how well I have progressed.

def get_fibonacci_sequence(max):
    '''
    Returns the Fibonacci sequence from the
    first to the nth Fibonacci number.
    '''

    fib1 = 1
    fib2 = 1
    result = [fib1, fib2]
    for i in range(2, max):
        result.append(fib1 + fib2)
        fib1 = fib2
        fib2 = result[i]
    return result

def get_nth_fibonacci(n):
    '''Returns the nth Fibonacci number.'''

    return get_fibonacci_sequence(n)[n - 1]

def main():
    print("Would you like to have the sequence or the number?")
    print("Enter 's' for sequence, and anything else for the number.")
    seqOrNum = input("> ")
    if seqOrNum == 's':
        print("Up to which number would you like the sequence up to?")
        max = int(input("> "))
        print("The sequence up to the {}th Fibonacci number:".format(max))
        print(get_fibonacci_sequence(max))
    else:
        print("Which Fibonacci number would you like to get?")
        max = int(input("> "))
        print("The {}th Fibonacci number is:".format(max),
              get_nth_fibonacci(max))

if __name__ == "__main__":
    main()

Example Output:

Would you like to have the sequence or the number?
Enter 's' for sequence, and anything else for the number.
> s
Up to which number would you like the sequence up to?
> 10
The sequence up to the 10th Fibonacci number:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Concerns:

Are my docstrings well-used?
Does it follow conventions?

Generators, not lists

Rather than returning a list of Fibonacci numbers, it would be much more useful to simply return an infinite generator of them. That is, yield them. This way, you don't even need the max:

def get_fibonacci_numbers():
    '''
    Generator for all the fibonacci numbers
    '''
    fib1 = 1
    fib2 = 1
    yield fib1
    yield fib2
    while True:
        yield fib1 + fib2
        fib1 = fib2
        fib2 = fib1 + fib2

Note that double assigns are actually better done in one go for clarity:

def get_fibonacci_numbers():
    '''
    Generator for all the fibonacci numbers
    '''
    fib1, fib2 = 0, 1
    while True:
        yield fib2
        fib1, fib2 = fib2, fib1 + fib2

If you want the first n numbers, you can use itertools.islice.

Why a generator?

You can easily turn a generator into a list of specific size, so you're not losing any functionality this way. But there's simply so much you can do with a lightweight generator that you can't do with a list. Consider some simple problems - what's the first Fibonacci number over 1000?

>>> next(dropwhile(lambda x: x < 1000, get_fibonacci_numbers()))

Euler problem #2: find the sum of the even-valued fibonacci numbers under 4 million?

>>> sum(i for i in takewhile(lambda x: x < 4e6, get_fibonacci_numbers()) if i%2 == 0)

Can't do either with a list. At least, not unless you know where to stop up front.

If you want just the nth one, that's:

def get_nth_fibonacci(n):
    return next(itertools.islice(
        get_fibonacci_numbers(),
        n, None))


Simple ConsoleWorker This class updates the console's title so it can tell the person using it the programs uptime, which can be pretty useful. The class holds a timer and each time the timer executes it will call the function to update the title (interval is in config file).

How can I improve on this?

using Apple.Application.Base.Config;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Timers;

namespace Apple.Application.Base.Core
{
    class ConsoleWorker
    {
        /// <summary>
        /// Console timer
        /// </summary>
        private Timer _consoleTimer;

        /// <summary>
        /// ConsoleWorker
        /// </summary>
        /// <param name="config">Instance of AppleConfig</param>
        public ConsoleWorker(AppleConfig config)
        {
            _consoleTimer = new Timer(int.Parse(config.GetConfigElement("console.timer.interval")));
            _consoleTimer.Elapsed += new ElapsedEventHandler(OnElapsed);
            _consoleTimer.Enabled = true; // Enable it
        }

        public void OnElapsed(object sender, ElapsedEventArgs e)
        {
            DateTime Startup = Apple.ServerInformation.ServerStarted;
            TimeSpan Uptime = DateTime.Now - Startup;

            string days = Uptime.Days + " day" + (Uptime.Days != 1 ? "s" : "") + ", ";
            string hours = Uptime.Hours + " hour" + (Uptime.Hours != 1 ? "s" : "") + ", and ";
            string mins = Uptime.Minutes + " min" + (Uptime.Minutes != 1 ? "s" : "");
            string UptimeString = days + hours + mins;

            Console.Title = "Apple Server [" + UptimeString + "]";
        }
    }
}

I think for the given task, the code is fine.

If you want to do some architecting, here are some thoughts

I'd say the class does two things, timing and updating console
I'd create a worker class that would do the timer stuff
Inject (using dependency injection) an interface that can output stuff
Create an interface that defines "outputting stuff"
Create a console version of that interface
Feed it to the concrete one

It's just refactoring so that you can use the same stuff to write output to different places such as disk, web service etc..


Rsync script that does Daily, Weekly and Monthly backups with hard links I have not been able to find a good implementation of using rsync to do daily, weekly and monthly backups with hard links anywhere. So I wrote my own and I am now looking for critique before I set it live on an unRAID production server. Anything I should fix?

#!/bin/bash
#
# Daily/Weekly/Monthly Backup
#
PROG_NAME=DailyWeeklyMonthlyBackup
BACKUPPOINT=/mnt/user
MOUNTPOINT=/mnt/disks/REDBackup
DAYOFWEEK_NAME=$(date +"%a")
DAYOFWEEK_NUMERAL_WEEKLY=$(date +"%u")
DAYOFWEEK_NUMERAL_MONTHLY=$(date +"%d")

logger Started -t$PROG_NAME $(date "+%m-%d-%Y %r")

if [ -d $MOUNTPOINT ]
then

    # Daily Backup START
    ############################
    rsync -a -v --delete $BACKUPPOINT/ $MOUNTPOINT/Daily/ 2>&1
    logger Daily REDBackup Completed -t$PROG_NAME $(date "+%m-%d-%Y %r")
    /usr/local/emhttp/webGui/scripts/notify -e "unRAID Server Notice" -s "Server Backup" -d "Daily REDBackup completed" -i "normal"

    # Weekly Sunday Backup START
    ############################
    if [ $DAYOFWEEK_NUMERAL_WEEKLY == 7 ]
    then
        rsync -avH --delete --link-dest=$MOUNTPOINT/Daily/ $BACKUPPOINT/ $MOUNTPOINT/Weekly/ 2>&1
        logger Weekly REDBackup Completed -t$PROG_NAME $(date "+%m-%d-%Y %r")
        /usr/local/emhttp/webGui/scripts/notify -e "unRAID Server Notice" -s "Server Backup" -d "Weekly REDBackup completed" -i "normal"
    fi

    # Monthly Backup START
    ############################
    if [ $DAYOFWEEK_NUMERAL_MONTHLY == 1 ]
    then
        rsync -avH --delete --link-dest=$MOUNTPOINT/Daily/ $BACKUPPOINT/ $MOUNTPOINT/Monthly/ 2>&1
        logger Monthly REDBackup Completed -t$PROG_NAME $(date "+%m-%d-%Y %r")
        /usr/local/emhttp/webGui/scripts/notify -e "unRAID Server Notice" -s "Server Backup" -d "Monthly REDBackup completed" -i "normal"
    fi

else

    logger REDBackup Drive Not Mounted -t$PROG_NAME $(date "+%m-%d-%Y %r")
    /usr/local/emhttp/webGui/scripts/notify -e "unRAID Server Notice" -s "Server Backup" -d "Daily REDBackup failed" -i "alert"

fi

Error handling

Error handling is always important,
especially when working with something so important as backups.
In particular, the result of the rsync commands is not checked,
the script logs "backup completed" messages,
which doesn't say anything about success or failure.

I suggest to add a check on the exit status of all the rsync commands,
and to make the log message reflect the state of success/failure (or simply include the exit code directly).

Don't repeat yourself

There are some repeating elements in the code:

logger $period REDBackup $result -t$PROG_NAME $(date "+%m-%d-%Y %r")
/usr/local/emhttp/webGui/scripts/notify -e "unRAID Server Notice" -s "Server Backup" -d "$period REDBackup $result" -i "normal"

I replaced with $period and $result the parts that could be parameterized.
Extracting these commands to helper functions can greatly reduce duplicated logic, and improve readability.

A word on quoting

It's recommended to double-quote all variables used as command arguments.
For example instead of this:

rsync -a -v --delete $BACKUPPOINT/ $MOUNTPOINT/Daily/ 2>&1

It will be safer to write:

rsync -a -v --delete "$BACKUPPOINT"/ "$MOUNTPOINT"/Daily/ 2>&1

Maybe you know that these variables will always be safe.
But it's good to take this simple precaution anyway,
and make it a habit so it's automatic and you will never fall in a trap of unintended word splitting or globbing.


Navigational bar content built depending on login state I created a login service which holds a boolean based on if a user is logged in or not.

 angular.module('deafApp')

    .service('LoginService', function(){

        var $this = this;

        $this.loggedIn = false;

    });

Inside my login controller (LoginCtrl), I attach the LoginService to a local scope object and on the successful login callback function I turn the loggedIn value to true like so.

angular.module('deafApp')

.controller('LoginCtrl', ['Auth', '$scope', 'LoginService', function(Auth, $scope, LoginService) {

    $scope.Login = LoginService;

    $scope.loginUser = function() {

        Auth.$authWithPassword({
            email: $scope.email,
            password: $scope.password
        }).then(function(authData) {
            console.log("Logged in as:", authData.uid);
            /*
             WHERE I CHANGE THE VALUE TO TRUE
            */
            $scope.Login.loggedIn = true;
        }).catch(function(error) {
            console.error("Authentication failed:", error);
        });
    }

}]);

I wanted to change the navigation appearance based on a user logging in, so inside my navigation controller I've attached the LoginService to a local scope object again and created a function to return true or false like so.

angular.module('deafApp')

.controller('NavCtrl', [ 'LoginService',function(LoginService){
    var $this = this;

$this.Login = LoginService;

$this.isShowing = false;

$this.showToggle = function() {
    $this.isShowing = !$this.isShowing;
};

$this.goHome = function() {
    $this.isShowing = false;
};

 /*
    THIS FUNCTION RETURNS VALUE OF LOGGED IN
 */
    $this.userLoggedIn = function() {
        return $this.Login.loggedIn;
    }

$this.navLinks = [
    {name: 'About-us', ref:'about', title: 'About DeafandHoh Page'},
    {name: 'Facts', ref: 'facts', title: 'Facts & Deaf Empowerment Page'},
    {name: 'News', ref: 'news', title: 'News Page'},
    {name: 'Products', ref: 'products', title: 'Products Page'},
    {name: 'Directory', ref: 'directory', title: 'Directory Listings Page'},
    {name: 'Resources', ref: 'resources', title: 'Resources Page'},
    {name: 'Login / Register', ref: 'login', title: 'Login & Register Page', hide: 'nav.userLoggedIn()'},
    {name: 'Profile', ref: 'profile', title: 'User Profile Page', show: 'nav.userLoggedIn()'},
    {name: 'Chatroom', ref: 'chatroom', title: 'Come Chat!', show: 'nav.userLoggedIn()'},
    {name: 'Logout', ref: 'logout', title: 'Logout', show: 'nav.userLoggedIn()'}
];

}]);

I then attached it a hide and show property to several of the navLinks which get repeated that I want to either hide when truthy and show when truthy.

{name: 'Login / Register', ref: 'login', title: 'Login & Register Page', hide: 'nav.userLoggedIn()'},
{name: 'Profile', ref: 'profile', title: 'User Profile Page', show: 'nav.userLoggedIn()'},
{name: 'Chatroom', ref: 'chatroom', title: 'Come Chat!', show: 'nav.userLoggedIn()'},
{name: 'Logout', ref: 'login', title: 'Login & Register Page', show: 'nav.userLoggedIn()'}

The HTML looks like this:

Essentially, the purpose is for a login/register nav link to disappear when a user logs in and some more unique features in the navigation to appear for logged in users.

I discovered that inside of ng-repeat directive expressions aren't evaluated which is why the function wasn't affecting the navigation state. to make the navigation state change I created another array of objects inside my navigation controller like this:

  $this.loggedInLinks = [
    {name: 'About-us', ref:'about', title: 'About DeafandHoh Page'},
    {name: 'Facts', ref: 'facts', title: 'Facts & Deaf Empowerment Page'},
    {name: 'News', ref: 'news', title: 'News Page'},
    {name: 'Products', ref: 'products', title: 'Products Page'},
    {name: 'Directory', ref: 'directory', title: 'Directory Listings Page'},
    {name: 'Resources', ref: 'resources', title: 'Resources Page'},
    {name: 'Profile', ref: 'profile', title: 'User Profile Page'},
    {name: 'Chatroom', ref: 'chatroom', title: 'Come Chat!'},
    {name: 'Logout', ref: 'logout', title: 'Login & Register Page'}
];

and to allow the state to change when the user logged in I attached a ng-hide to the default HTML navigation bar like so

And Replicated that in another HTML section but instead with ng-show for when the LoginService.loggedIn state changed to truthy

Now when a user logs in the navigation bar changes appropriately.


File-encryption utility application I made a simple file-encryption utility application for a little school project.
I'm really interested in cryptography, and tried my best while making it.
Can you see it, and give me feedback?

The input is always a FileInputStream (wrapped by a BufferedInputStream), and the output is a ByteBufferOutputStream, which will be written to the output file.

 public class Cryptography {

    private final Cipher c;
    private final MessageDigest md5;
    private final String AES_CBC_PKCS5 = "AES/CBC/PKCS5Padding";
    private final String MD5 = "MD5";
    private final int BLOCK_SIZE = 16;
    private final byte[] bytesIV = new byte[BLOCK_SIZE];

    public Cryptography() throws NoSuchAlgorithmException, NoSuchPaddingException {
        c = Cipher.getInstance(AES_CBC_PKCS5);
        md5 = MessageDigest.getInstance(MD5);
    }

    public void initIV() {
        new SecureRandom().nextBytes(bytesIV);
    }

    public void encryptStream(InputStream in, OutputStream out, byte[] key) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, InvalidAlgorithmParameterException, IllegalBlockSizeException, BadPaddingException, IOException {
        out.write(bytesIV);
        out.flush();
        c.init(Cipher.ENCRYPT_MODE, new SecretKeySpec(key, "AES"), new IvParameterSpec(bytesIV));
        out = new CipherOutputStream(out, c);
        byte[] buf = new byte[1024];
        int numRead = 0;
        while ((numRead = in.read(buf)) >= 0) {
            out.write(buf, 0, numRead);
        }
        out.close();
    }

    public void decryptStream(InputStream in, OutputStream out, byte[] key) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, InvalidAlgorithmParameterException, IllegalBlockSizeException, BadPaddingException, IOException {
        in.read(bytesIV);
        c.init(Cipher.DECRYPT_MODE, new SecretKeySpec(key, "AES"), new IvParameterSpec(bytesIV));
        in = new CipherInputStream(in, c);
        byte[] buf = new byte[1024];
        int numRead = 0;
        while ((numRead = in.read(buf)) >= 0) {
            out.write(buf, 0, numRead);
        }
        out.close();

    }

    public byte[] hash(byte[] key) {
        return md5.digest(key);
    }

    public byte[] getIV() {
        byte[] temp = new byte[BLOCK_SIZE];
        System.arraycopy(bytesIV, 0, temp, 0, BLOCK_SIZE);
        return temp;
    }
}

Exposing the IV only leaves room for errors. Simply generate it at the start of encryption.
There is no point in having a completely unrelated hash method on this class.
There is not integrity protection, so an attacker who can modify the ciphertext you decrypt will likely be able to pull off a padding-oracle attack. Unfortunately it's not trivial to combine streaming decryption with integrity protection, since you must ensure that you don't release any plaintext you haven't authenticated.
Once you eliminate the IV storage, as recommended above, you have no state to preserve across calls, which means you don't need any instance fields anymore. They only make your class thread-unsafe without any benefit.
Closing out seems pretty weird, I wouldn't expect that behaviour. On the other hand you don't close in.
If you decide to dispose resources, use try...finally (or try-with-resources) to do so reliably.
I'd make the class immutable and threadsafe, storing only the key (and algorithm if it's not hardcoded) in it.


Binary Search in Haskell I have been trying to pick Haskell back up so I decided to try to implement binary search as practice. I am aware that binary search in Haskell in inefficient because Haskell's lists are implemented as linked lists, but I wanted to try it anyway. I would love to know how I could improve this or how it could be more idiomatic, thanks!

search :: (Ord a) => a -> [a] -> Maybe Int
search _ [] = Nothing
search n h
  | elem == n = Just index
  | elem < n = (+index) . (+1) <$> (search n $ drop (index+1) h)
  | otherwise = search n $ take index h
  where index = length h `quot` 2
        elem = h !! index

Since there is already a function called elem, I wouldn't call the element the same. There's no way that those two can get mistaken though, since their types differ. So you're safe at that point. However, you will still get a warning on -Wall.

Next, you call your list h. Lists are usually called xs (one x, may xses), which makes it a little bit harder to catch than it needs to be. We can also split the list into the three parts at the same time:

search :: (Ord a) => a -> [a] -> Maybe Int
search _ [] = Nothing
search n xs
  | elem == n = Just index
  | elem < n  = (+index) . (+1) <$> search n bs
  | otherwise = search n as
  where index = length xs `quot` 2
        (as,elem:bs) = splitAt index xs

This removes the need to traverse the list again just to get the correct init/tail, however it's harder to read, so it's up to you. Also, I really like to have the compiler yell at me if I forgot a case in my guards. For example, GHC will happily accept

search :: (Ord a) => a -> [a] -> Maybe Int
search _ [] = Nothing
search n xs
  | elem == n = Just index
  | elem < n  = (+index) . (+1) <$> search n bs
  where ...

even with warnings. With compare elem n, we get warnings:

search n xs = case elem `compare` n of
    EQ -> Just index
    LT -> (+index) . (+1) <$> search n bs
    -- third missing, GHC warns us
  where ...

But that's more or less a personal preference. A major nitpick though is that you take the length of the list in every iteration. You can get rid of that if you write another function:

search :: (Ord a) => a -> [a] -> Maybe Int
search n ys = go (length ys) ys
  where
    go _ [] = Nothing
    go l xs = ...


Checking balanced parenthesis string I recently wrote a code in online recruitment test. It was very good.

With each question, there were associated space and time limits check. If our code executed correctly within both limits, only then we were given full marks otherwise 0.

Input: String consisting of ASCII characters.

Output: True if the string is balanced parenthesis wise and false otherwise.

I wrote the following code for the problem, but the problem is I got 0 marks because it said limits crossed, Optimization required.

import java.util.*;
import java.io.*;
class Prths
{
 private static Stack<Boolean> st=new Stack<Boolean>();
 public static void main(String []args)throws IOException
 {
     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
     String s=br.readLine();
     boolean result=check(s);
     System.out.println(result);
 }
 public static boolean check(String s)
 {
     int i=0;
     while(i<s.length())
     {
         if(s.charAt(i)==')'&&st.isEmpty())
          return false;
         else if(s.charAt(i)==')')
          st.pop();
         else if(s.charAt(i)=='(')
          st.push(true);
         ++i;
     }
     if(st.isEmpty())
      return true;
     else return false;
 }
}

if(st.isEmpty())
  return true;
 else return false;

This can be simplified to return st.isEmpty();... Wait, that's not the right advice.

Why do you even need a Stack when you can simply count?

public static boolean check(String s) {
    int counter = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            counter++;
        } else if (s.charAt(i) == ')') {
            if (counter == 0) {
                return false;
            }
            counter--;
        }
    }
    return counter == 0;
}

Other issues (which may or may not be picked up by the automatic assessment):

If this is assessed using Java 7, using try-with-resources is recommended for the BufferedReader instance.
You can inline the printing of the results, i.e. System.out.println(check(input));.
Please use braces consistently... that tends to improve code readability for human programmers.

edit: OK, second stab at a Java 8 stream-based solution...

// Using better-suited visibility modifier and method name
private static boolean balanced(String input) {
    return input.chars().mapToDouble(i -> i == '(' ? 1 : i == ')' ? -1 : 0).reduce(0,
            (a, b) -> a == 0 && b == -1 ? Double.NaN : a + b) == 0;
}

mapToDouble() is used here just so that Double.NaN can be used as a special placeholder to effectively ignore further computations when a ) is encountered without a matching (. It doesn't look as streamlined as I hoped it would be though, and I think for most intent and purposes the non-stream-based way works and reads just a little better.


Justify text from a file using a LaTeX method I wrote a bit of code that takes a file, justifies the text and writes to another file.

It uses a DP approach to minimise a badness metric, which is the amount of undershoot of the line length, cubed (see my answer below, the badness function isn't quite right if there is an overshoot, the badness should be inf - I believe this is how LaTeX justifies its text).

I encapsulated it in a class (which is the bit I'm least confident about). Be careful running it on big files, because I think it's got a pretty nasty complexity (\$O(n^2)\$ maybe).

class justifyText:
    def __init__(self, inFileName, outFileName, pageWidth):
        with open(inFileName, "r") as fp:
            self.words = [word for line in fp for word in line.split()]
        self.outFileName = outFileName
        self.pageWidth = pageWidth
        self.memo = {}
        self.breakPointTrack = {}
        self.n = len(self.words)

    def badness(self, i, j):
        totalWidth = 0;
        for word in self.words[i:j]:
            totalWidth += len(word)
        return abs((self.pageWidth - totalWidth)**3)

    def minBadness(self, i):
        if i in self.memo:
            return self.memo[i]
        if i == self.n:
            f = 0
            j_min = self.n
        else:
            f = None
            for j in range(i + 1, self.n + 1):
                temp = self.minBadness(j) + self.badness(i, j)
                if (f is None) or (temp < f):
                    f = temp
                    j_min = j
        self.memo[i] = f
        self.breakPointTrack[i] = j_min
        return f

    def justify(self):
        self.minBadness(0)
        fOut = open(self.outFileName, "w")
        brk = 0
        while brk < self.n:
            start = brk
            brk = self.breakPointTrack[brk]
            line = " ".join(self.words[start:brk]) + "\n"
            fOut.write(line)
        fOut.close()

test = justifyText("test.txt", "out.txt", 80)
test.justify()

Is this a standard way to implement a DP program? I know that global variables are evil, so I was mainly trying to avoid my memo etc. being that.

You should have a look at Python's official style-guide, PEP8. One of its recommendations is to use PascalCase for class names and lower_case for function and variable names.

Since you read all words into memory anyway, you can just write:

with open(in_file_name) as fp:
    self.words = fp.read().split()

This is because split splits by default on all whitespace (so both space and newlines). Also note that the default behaviour of open is to open a file in read mode, so "r" is also not needed here.

Caching (or memoization) of a functions return value is best done with a decorator. This way you avoid interleaving the actual implementation of the function with the caching. One example could be:

import functools

def memoize_method(func):
    cache = func.cache = {}

    @functools.wraps(func)
    def wrapper(self, n):
        if n not in cache:
            cache[n] = func(self, n)
        return cache[n]
    return wrapper

class JustifyText:
    ...
    @memoize_method
    def min_badness(self, i):
        if i == self.n:
            f, j_min = 0, self.n
        else:
            f, j_min = min((self.min_badness(j) + self.badness(i, j), j)
                           for j in range(i + 1, self.n + 1))
        self.break_point_track[i] = j_min
        return f

Your badness function can be simplified by using sum, similar to how I used min above:

def badness(self, start, end):
    total_width = sum(len(word) for word in self.words[start:end])
    return abs((self.page_width - total_width)**3)

While it might be your most used use case, writing the output to a file prevents anyone from using this module in any other way. It would be better if justify just returned (even better and simpler: yielded) the justified text and writing to a file is left to the user or a dedicated method using justify internally.

def justify(self):
     self.min_badness(0)  # no-op or to populate the cache?
     brk = 0
     while brk < self.n:
         start, brk = brk, self.break_point_track[brk]
         yield " ".join(self.words[start:brk]) + "\n"

def write(self):
    with open(self.out_file_name, "w") as f_out:
        f_out.writelines(self.justify())

I'm not exactly sure why you have a lone self.min_badness(0) in justify. is it just to populate the cache with the value for zero? If so, this is worth to put a comment here, because otherwise you might accidentally delete it.


Updating number of article views - potential concurrent access issue? I have articles on my website (built in PHP) and when an article is viewed the number of views is recorded back in the database. The SQL code snippet of my load method is:

SELECT *
FROM article
WHERE id = :id;
UPDATE article
SET views = views + 1
WHERE id = :id;

This works fine, but I've only tested it locally with one user - me.

What happens if hundreds of people tried accessing the same article at once? I.e. would the update slow things down considerably? If so, is there a better way of doing this?

The performance with simple queries such as yours will depend more on what is going on in the database than what is going on in your code.

Here are a few things to consider if you are maintaining the DB yourself, or to bring up with the DBA if you are not:

If the id field is an integer, and ideally a  surrogate key (e.g. generated by an identity function instead of being a natural key using date/time, articlename, etc.), that will perform significantly better. Integers can be easily and swiftly ordered and generate relatively small indexes that can be searched quickly. A surrogate key improves performance for many reasons, one of which improved index performance by pushing data INSERTs to the leading edge of the index.
If the article table has a clustered index on the id field, that's even better for your performance as it will reduce the cost of both the SELECT and the UPDATE in most cases. The clustered attribute means that the data is already ordered by your ID column, significantly improving search performance.
If you don't have a lot of competing queries that try to lock bigger sets of data than a row at a time, that will also be good for the performance of these queries. You want to avoid contention for locking the same data as much as possible. For example, you don't want a big 100,000-row update that runs every 15 minutes competing with your single-row update.

Which brings me to the one thing I would change about your query: locking. Unless you really need per-transaction integrity when serving articles to the readers (and in most cases, for a publishing system, you probably don't) you can hint to the database that you'd like a more permissive transaction isolation level. In layman's terms, you can volunteer to let the other guy win if you both need a lock.

So if you are doing a SELECT at the same time an UPDATE is occurring to the same article, you can allow a READ UNCOMMITTED transaction isolation level on your query to avoid taking unnecessary locks. The syntax for doing this varies from one DBMS to another, but usually it's some variation on the theme of SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED. Some (MS SQL, for example) also have a shortened syntax such as WITH (NOLOCK).

Finally, a couple of caveats to this advice since you didn't specify your DB system. Some DB systems don't fit this mold. For example, Oracle implements non-blocking SELECTs without requiring dirty reads, so there's no equivalent to NOLOCK there because it's a built-in assumption. MySQL, on the other hand, has InnoDB and MyISAM tables, and on the latter type you are not going to be able to use READ UNCOMMITTED due to the underlying architecture of the table. However, even though you will be taking a table lock the architecture is designed to efficiently allow many concurrent reads by sharing the lock to multiple readers.

To sum up, your queries look fine but explore whether a NOLOCK-type option is available.


Monkey patching extra events in Node.js HTTP/Express This question is related to Express under Node.js.

Background

With Express, you stack up several "middleware" modules to handle a specific HTTP request.

app.use(express.logger());
app.use(express.favicon()));
app.use(express.cookieParser());
app.use(express.session());
app.use(app.router);

When a request comes in, Express goes through all of the functions in the stack until a module handles the request.  Specifically, each middleware module is a function (req, res, next), and that function will call next() to call the next module in the stack.  Functions can modify data in the req or res objects if they choose.

The Problem

I was interested in making custom log middleware modules for my Express application, and I needed to use more than one module at a time.  The data I need to log cannot be logged until the response has been sent to the client.  (I am tracking bytes sent, and the amount of time a connection was established.)  Unfortunately, Node.js's HTTP response object does not raise an end event.  Presumably, this is because it is up to the application to do any "end" work prior to calling .end() on the response object in the first place.  Express does not expose a hook prior to .end() being called.

Express/Connect's built-in logger middleware is able to track how long a request was running, so I decided to see what method they use.  They actually replace the res.end function with their own.  When their own res.end function is called, it swaps the old res.end back in place, finishes logging, then calls res.end with the parameters that their own res.end was called with.  Their method works, but can be problematic when a handful of modules try to do this.  (The order in which res.end function replacement occurs becomes critical.)

My Solution

I have used their method to patch res to fire end events so that any module in the chain can subscribe to that event in the usual way.

function (req, res, next) {
    var end = res.end;

    res.end = function () {
        res.end = end;
        res.emit('end');
        res.end.apply(this, arguments);
    }

    next();
}

Then, all my logger module has to do is:

res.on('end', function () { /* log here */ });

Is there any problem with what I have done?  Is there a better way to do it?

I did the following for something similar.  This uses the closure to create a chain-of-command pattern.

function (req, res, next) {
  var realEnd = res.end;
  res.end = function () {
    var realEndArgs = arguments;
    req.log.info ("HTTP RESPONSE CODE " + res.statusCode);
    realEnd.apply (res, realEndArguments);
  }
  next();
}

You could instead of logging the status code, do res.emit('end') as you described, or anything else, before returning control to the original res.end (which may itself be a replacement).  Or, you could do directly in this function whatever you want to do in response to the end event.

Note: I explicitly store res.end's arguments in realEndArguments in case I later add anything asynchronous, because arguments would then refer to the asynchronous action's callback's arguments instead of res.end's arguments.  A subtle bug I ran into at first.


Counting paths between 3 cities in C++ The task is to make a program that prints out how many possible paths a driver can use to visit three cities so that he visits each city exactly n times. The program must be executed within 1 minute and print the solution for n = 10. The program works correctly but for n above 7 it doesn't execute in time. Is there a way to get it to execute n=10 in time? These are some of the solutions: n = 1, the solution is 6, n = 2, the solution is 30, n = 3, the solution is 174 and n = 4, the solution is 1092.

#include<iostream>
#include <algorithm>
using namespace std;
double paths (long long unsigned int path[],int n,double s,int e){
    int r=0;
    do{
        for(int i=0;i<e-1;i++){
            if(path[i]!=path[i+1]){
                r++;
            }
        }
            if(r==e-1){
                s++;

            }
            r=0;

        }while(next_permutation(path, (path+e)));

        return s;
    }
int main(){
    double s=0;
    int y=0;
    int buff=0;
    int n;
    cin>>n;
    int e=(n*3);
    long long unsigned int path[e];
    while(y!=e){
       for(int t=1;t<=3;t++){
           path[y]=t;
           y++;
       }
    };
    bool test=false;
    for(int z=0;z<e;z++){
        for (int j =0; j<e; j++){
            if (path[j+1] < path[j]){
                buff=path[j];
                path[j]=path[j+1];
                path[j+1]=buff;
                test=true;
            }
        }
        if(!test){
            break;
        }else{
            test=false;
        }
    }
    cout<<"Number of posibilities: "<<paths(path,n,s,e)<<endl;

}

Simply modifying this algorithm will not solve the problem in the required time. When n=10, this code is going through every permutation of an array of 30 integers. That is 30! (about 2^107) permutations. Going faster through the loop in paths() will not be enough.

I would suggest a backtracking solution, which cuts down the search space enormously. I think the answer when n=10 should be around 125,000,000. I'd also claim the code should run in under 30 seconds.

Obligatory code review comment. In the loop in main(), there is an out of bounds bug when evaluating buff[j+1] when j == e-1;

Here is the code that I wrote using a backtracking approach.

#include<iostream>
#include <utility>
#include <vector>
#include <map>
using namespace std;

class TripCounter {
public:
    TripCounter(int cities, int visits) : length(cities*visits) {
        for (auto i = 1; i <= cities; i++)
            pool[i] = visits;
    }

    long Count() {
        count = 0;
        BackTracker(0);
        return count;
    }

private:
    void BackTracker(int level) {
        if (level == length) {
            count++;
            return;
        }
        for (auto& bucket : pool) {
            if (IsValidAtLevel(bucket, level)) {
                trip.push_back(bucket.first);
                bucket.second--;
                BackTracker(level + 1);
                bucket.second++;
                trip.erase(trip.end() - 1);
            }
        }
    }

    bool IsValidAtLevel(pair<int, int> bucket, int level) {
        if (bucket.second == 0)
            return false;
        if (level == 0)
            return true;
        if (bucket.first == trip[level - 1])
            return false;
        return true;
    }

private:
    map<int, int> pool;
    int const length = 0;
    vector<int> trip;
    int count = 0;
};

int main() {
    int n;
    cin >> n;

    auto counter = TripCounter(3, n);
    cout << "Backtracking: " << counter.Count() << endl;
}