Check if a binary tree is a binary search tree Given a binary tree, I need to check if it satisfies the binary search tree property i.e. left child is less than or equal to the current node and right child is greater than or equal to the current node.

from collections import namedtuple

Node = namedtuple('Node', 'key, left, right')

def is_bst(node, key_min=None, key_max=None):
    """Checks is the subtree rooted at this node is a BST."""
    if node is None:
        return True # By definiton
    if key_max is not None and node.key >= key_max:
        return False
    if key_min is not None and  node.key <= key_min:
        return False
    return is_bst(node.left, None, node.key) and is_bst(node.right, node.key, None)

import unittest

class TestBst(unittest.TestCase):
    def test_none(self):
        self.assertTrue(is_bst(None))

    def test_left_skewed(self):
        root = Node(8, Node(3, Node(1, None, None), None), None)
        self.assertTrue(is_bst(root))

    def test_right_skewed(self):
        root = Node(8, None, Node(10, None, Node(14, None, None)))
        self.assertTrue(is_bst(root))

    def test_bst(self):
        root = Node(8, Node(3, None, None), Node(10, None, None))
        self.assertTrue(is_bst(root))

    def test_non_bst(self):
        root = Node(8, Node(10, None, None), Node(6, None, None))
        self.assertFalse(is_bst(root))

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

I want to know if I can convert it to an iterative version. If yes, then how?

Time complexity

The algorithm visits each node exactly once, hence the complexity should be \$\Theta(n)\$, where \$n\$ is the number of node in the tree.

I think one of reasons that this question is on the verge of getting closed, is that the code presented doesn't make much sense combined with a question of iterative version. But let us come to back that.

Code and style review

Good naming of methods and variables – You are trying to follow the PEP8 and that is good
Combine similar if statements – When you have similar if condition, and they do the same, then combine them using the or operator
Use \ (line continuation) or parenthesis to break long if conditions – This is a matter of personal preferences, and one area where I'm not sure what I prefer to do in all cases. But if you have a long if condition, you can either break it using a single \ at the end of the line, or add the otherwise unneccessary parenthesis around the entire condition.
Add vertical space between non-similar if statements – In some places it can be good to introduce a little vertical space. This is especially true with following if/elif/else blocks. If not vertically spaced, one might wonder if they should have been using elif or else instead. And if they really are meant to be separate if statements, then separate them using extra newlines. This enhance readability, and code understanding
(optional) Shorten None conditions – Consider whether you want to test directly on not node or if you want to use the more verbose node is None. In most cases they are identical, but I tend to prefer the not node version my self.
Bug: Not keeping the key_min and key_max whilst traversing tree – Your code sets these to None, which would introduce errors if you have a tree with a little more levels then your test case, and you first traverse a left tree, and then go down the right tree. That value could now be higher than the root value, and you'll be happy with that. So extend test cases, and then afterwards correct the bug.

With these options implemented you'll get the following (untested) code:

def is_bst(node, key_min=None, key_max=None):
    """Checks is the subtree rooted at this node is a BST."""
    if node is None:
        return True

    if (not key_max and node.key >= key_max) \
        or (not key_min and node.key <= key_min):

        return False

    return is_bst(node.left, key_min, node.key) \
           and is_bst(node.right, node.key, key_max)

Algorithmic comments

Your implementation is good, and should do what it is supposed, with correction of bug, and does so in a recursive manner. You can't do it entirely iterative as retrieving the values of a tree is not an iterative procedure.

However, you do have the option of creating/returning/yielding something which you can use in an iterative manner. Either iterating over your returned list from inorder(), or by implementing an iterative version of the traversal, as I've done in my answer for values_in_order().

If having some you can iterate over you could do either of the following variants:

# First variant: Manually keeping the previous_node
previous_node = None
for node in inorder(root):
    if previous_node and previous_node.key > node.key:
        return False
    previous_node = node

# Second variant: Using the itertools.pairwise iterator
return any(prev.key > node.key for prev, node in pairwise(inorder(root)))

The last one depending on the itertools.pairwise recipe, which returns all pairs of nodes from the start through end.

Do however note, that neither of these methods are tested for efficiency or speed, but are mostly presented as alternate methods on how to do the check whether all the values are in sorted order which seems to the criteria for a binary search tree.

Another solution without using None. Using None create confusions and forces us to write extra conditional codes.

from collections import namedtuple

Node = namedtuple('Node', 'key, left, right')

def is_bst(node, key_min=float("-inf"), key_max=float("inf")):
    """Checks if the subtree rooted at this node is a BST."""
    if node is None:
        return True # By definiton
    if node.key <= key_max and node.key >= key_min:
        return is_bst(node.left, key_min, node.key) and\
            is_bst(node.right, node.key, key_max)
    else:
        return False

if __name__ == '__main__':
    import unittest

    class TestBst(unittest.TestCase):
        def test_none(self):
            self.assertTrue(is_bst(None))

        def test_left_skewed(self):
            """
                    8
                   / \
                  3   *
                 / \
                1   *
               / \
              *   *
            """
            root = Node(8, Node(3, Node(1, None, None), None), None)
            self.assertTrue(is_bst(root))

        def test_right_skewed(self):
            """
                    8
                   / \
                  *  10
                     / \
                    *  14
            """
            root = Node(8, None, Node(10, None, Node(14, None, None)))
            self.assertTrue(is_bst(root))

        def test_bst(self):
            """
                    8
                   / \
                  3  10
                 / \ / \
                *  * *   *
            """
            root = Node(8, Node(3, None, None), Node(10, None, None))
            self.assertTrue(is_bst(root))

        def test_non_bst(self):
            """
                    10
                   /  \
                  5   15
                 / \  / \
                *   *6   20
                    / \  / \
                   *   **   *
            """
            root = Node(10,
                Node(5, None, None),#left subtree
                Node(15,            #right subtree
                    Node(6, None, None), Node(20, None, None)))
            self.assertFalse(is_bst(root))

    unittest.main()


How to handle Throw exception + close connection I have a function that works with a database. If something wrong happens I want to throw an exception, and I also want that all resources have to be closed.

Is this a good way to do it? There is a better way to do it?

public Strint getStuff(Integer id) throws Exception {

    String result = "";

    Connection connection = db.openConection();
    ResultSet rs = null;

    try {
       // DO STUFF WITH DB
    } catch (Exception e) {
        throw e;
    } finally {
        rs.close();
        db.closeConection(connection);
    }
    return result;
}

You can skip catch part of try-catch-finally block
You should check that rs is not null

Instead of catching generic "Exception", its always better to catch specific exception and as @Andrew pointed its better to check for resultset not null.


Texas Holdem Poker Game I'm making a Texas Hold'em game for multiple players. So far, I have finished the flow control for betting / calling sequences, player stack / pot updating, and just now - the part responsible for drawing cards and distributing them. It is this last part that I would like reviewed, if possible.

Essentially, I wanted to know what I could do differently / more efficiently, suggested changes, really just anything that could be helpful. Things like checks for proper input from player etc are not yet in place so please ignore them.

import itertools
import random

player_count = int(input("How many players? "))

suits = ['s', 'c', 'd', 'h']
faces = ['A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K']

# Defining deck and drawing cards (5 + 2 per player):

deck = set(itertools.product(faces, suits))
drawn_cards = random.sample(deck,(5 + 2 * player_count))

# Storing a list with player object instances

players = []

class Players:

    def __init__(self, stack):

        self.stack = stack
        self.last_action = "none"  ## last action taken (check, call etc).
        self.street_bets = 0       ## total bets on current street

    def holecards(self):

## pop cards from list and pritifying their display. Cards will later be
## run through a function for checking value of hands:

        card1 = drawn_cards.pop(len(drawn_cards)-1)
        card2 = drawn_cards.pop(len(drawn_cards)-1)
        self.card1 = (card1[0]+"["+card1[1]+"]")
        self.card2 = (card2[0]+"["+card2[1]+"]")
        self.cards = self.card1+ " - " +self.card2
        print (self.cards)

class Table:

    def __init__(self):

        self.total_pot = 0

    def flop(self):

        card1 = drawn_cards.pop(len(drawn_cards)-1)
        card2 = drawn_cards.pop(len(drawn_cards)-1)
        card2 = drawn_cards.pop(len(drawn_cards)-1)
        self.card1 = (card1[0]+"["+card1[1]+"]")
        self.card2 = (card2[0]+"["+card2[1]+"]")
        self.card3 = (card2[0]+"["+card2[1]+"]")
        self.flop = self.card1+ " - " + self.card2 + " - " + self.card3
        print (self.flop)

    def turn(self):

        card = drawn_cards.pop(len(drawn_cards)-1)
        self.card = (card[0]+"["+card[1]+"]")
        self.turn = self.card
        print (self.turn)

    def river(self):

        card = drawn_cards.pop(len(drawn_cards)-1)
        self.card = (card[0]+"["+card[1]+"]")
        self.river = self.card
        print (self.river)

# Add player stacks and distribute holecards:

for i in range(player_count):
    players.append(i)
    players[i] = Players(100)
    players[i].holecards()

# Add dealer to table:

dealer = Table()

dealer.flop()
dealer.turn()
dealer.river()

Reasonable quality code. Here are a few comments:

1) I'd add a method drawNextCard, which encapsulates retrieval of the next card, and makes the code a bit more readable

def draw_next_card(drawn_cards):
    card = drawn_cards.pop(len(drawn_cards)-1)
    return readable_card_name(card)

def readable_card_name(short_card_name):
    return (short_card_name[0]+"["+short_card_name[1]+"]")

Then, for example, your flop() method would look like this:

def flop(self):
    (self.card1, self.card2, self.card3) = (draw_next_card(drawn_cards), draw_next_card(drawn_cards), draw_next_card(drawn_cards))
     self.flop = self.card1+ " - " + self.card2 + " - " + self.card3
     print (self.flop)

More readable, shorter, and on the way we fixed a copy/paste defect where you initialized card2 twice instead of card2 and card3.

2) You convert each drawn card to a readable representation. It's good for your debugging, but not so good for adding future functionality for actually calculating poker hands, and developing strategy. So, while my draw_next_card above returns a readable representation, you're better off creating a class Card, which has an __str__ method that has the same implementation as readable_class_name. The flop method would remain the same, but it will be much easier to extend the code.

3) Note that flop and river are copy/pastes. Both could just call draw_next_card. Also, while the flow and river are true to the game terms, they're not much benefit to software; you'd be better off collapsing flop, turn and river to a table_cards[5] vector. Once you start developing the actual game, it will make things much easier for you.

Hope this helps.

I found no direct way to reply to you RomanK, but I had to say thank you. So - thank you!

EDIT: sorry for the "Thank you", I guess.

Another question: after thinking it through, does using a class for dealing and distributing the flop, turn and river make sense at all? Wouldn't I be better off just using a function for this? The more I think of it the less I see any reason for having this part of the code in a class - seems to be more of a problem than a convenience.

Essentially, after the hole cards have been dealt to the players, what remains in the drawn_cards list are the 5 cards for the board. All I need to do now is display them with a function:

def deal_community_cards(street):

    if street == "flop":
        flop = drawn_cards[0:3]
        return flop

    elif street == "turn":
        turn = drawn_cards[3]
        return turn

    else:
        river = drawn_cards[4]
        return river

and finally I'd use another function to "pritify" the card display. Wouldn't this be a better solution than creating a whole class for this?


Find the closest number in a sorted list to a given target number Given a list of n integers sorted in ascending order, find the closest
  number (value) in the list to a given target number. How quickly can
  you do it?

I'm interested to know if there's any feedback for my code.

def getClosestValue(arr, target):
    n = len(arr)
    left = 0
    right = n - 1
    mid = 0

    # edge case
    if (target >= arr[n - 1]):
        return arr[n - 1]
    # BSearch solution: Time & Space: Log(N)

    while (left < right):
        mid = (left + right) // 2 # find the mid

        if (arr[mid] == target):
            return arr[mid]

        if (target < arr[mid]):
            # If target is greater than previous
            # to mid, return closest of two
            if (mid > 0 and target > arr[mid - 1]):
                return findClosest(arr[mid - 1], arr[mid], target)
            # update right
            right = mid
        else:
            if (mid < n - 1 and target < arr[mid + 1]):
                return findClosest(arr[mid], arr[mid + 1], target)
            # update i
            left = mid + 1
    return arr[mid]

# findClosest
# We find the closest by taking the difference
# between the target and both values. It assumes
# that val2 is greater than val1 and target lies
# between these two.

def findClosest(val1, val2, target):
    if (target - val1 >= val2 - target):
        return val2
    else:
        return val1

# Sample code
arr = [1, 2, 3, 4, 5, 5, 8, 10]
target = 7
print(getClosestValue(arr, target))

Conventions

The Style guide to follow in Python is PEP8. If you do so, your code blends right into the python community and it is immediately easier to follow. On that regard you'll see that the functions name's don't follow the recommended style.

getClosestValue

Should actually be:

get_closest_value

The relevant quote from PEP8 for this case

  Use the function naming rules: lowercase with words separated by
  underscores as necessary to improve readability.

Still in this topic, all the parenthesis used in the ifs are redundant and break the style.

if (target >= arr[n - 1]):

Should be turned into:

if target >= arr[n - 1]:

Although i suspect that this may be a habit brought from other languages.

Edge cases

You contemplated the case where the value is the highest or above, which gives you a quick way out:

# edge case
if (target >= arr[n - 1]):
    return arr[n - 1]

However there is no corresponding edge case for when the value is the lowest or below. I believe you merely forgot it.

#edge case - first or below all
if target <= arr[0]:
    return arr[0]

Logic

Now both edge cases are covered, so the while can be simplified to only have the navigation to the corresponding item if there is one.

while (left < right):
    mid = (left + right) // 2 # find the mid
    if arr[mid] == target:
        return arr[mid]

    if target < arr[mid]:
        right = mid
    else:
        left = mid + 1

After this last while if there isn't an exact match, calculate the nearest to the one you ended on, and return it:

if target < arr[mid]:
    return find_closest(arr[mid - 1], arr[mid], target)
else:
    return find_closest(arr[mid], arr[mid + 1], target)

Note that i don't need to check if mid - 1 or mid + 1 is a valid index, because if it wasn't it would mean that the value was below or above all elements, and those cases were already covered in the beginning of the function.
This is not only simpler but also more efficient since it only checks for the closest on the very end and not at each iteration.

Taking @bipll suggestion you can restructure the while a bit. Considering you are only getting if arr[mid] == target at the very last iteration you can first check for < or >. This avoids making one extra check that will fail most of the times:

while left < right:
    mid = (left + right) // 2  # find the mid
    if target < arr[mid]:
        right = mid
    elif target > arr[mid]:
        left = mid + 1
    else:
        return arr[mid]

When i have a simple condition with a return on both cases i rather write them inline since its easy to read and a bit more concise:

def find_closest(val1, val2, target):
    return val2 if target - val1 >= val2 - target else val1

But don't go over the top on this. It can easily be harder to read depending on the complexity of the condition.

Full Modified Version

For you to get a better picture of all the changes i mentioned, i'll leave you with the full modified version:

def get_closest_value(arr, target):
    n = len(arr)
    left = 0
    right = n - 1
    mid = 0

    # edge case - last or above all
    if target >= arr[n - 1]:
        return arr[n - 1]
    # edge case - first or below all
    if target <= arr[0]:
        return arr[0]
    # BSearch solution: Time & Space: Log(N)

    while left < right:
        mid = (left + right) // 2  # find the mid
        if target < arr[mid]:
            right = mid
        elif target > arr[mid]:
            left = mid + 1
        else:
            return arr[mid]

    if target < arr[mid]:
        return find_closest(arr[mid - 1], arr[mid], target)
    else:
        return find_closest(arr[mid], arr[mid + 1], target)

# findClosest
# We find the closest by taking the difference
# between the target and both values. It assumes
# that val2 is greater than val1 and target lies
# between these two.
def find_closest(val1, val2, target):
    return val2 if target - val1 >= val2 - target else val1

python has a binary search implementation: https://docs.python.org/2/library/bisect.html

so just:

import bisect
ind = bisect.bisect_left(arr, target)

if you get ind > len(arr)-2, then the solution is arr[-1]. Otherwise you just hceck arr[ind] and arr[ind+1] to find whichever is closest

Strictly speaking, if you implemented your own binary search it should be just as fast. However, having a two line implementation is easier to read than defining your own functions


Best syntax for executing an action between each loop iteration. The question of the cleanest way to write a loop that executes some action between each iteration has always interested me.

In a sense, what is the best way in c/c++ to implement this fictional construct:

for (...) {
} between {
}

Using such a construct you could trivially implement string join(): (pseudocode)

result = "";
foreach ( item : input ) {
    result += str(item);
} between {
    result += sep;
}

I have looked through some popular code libraries to see how these types of loops are implemented, and there are some common strategies:

move the "between" code into an "if (!first/last iteration)" inside the loop.

This is the go-to method when the index/iterator/result freely stores the notion of first/last iteration (such as checks for values of 0, .empty(), NULL etc).

transform the "loop body" into a function and call it from two places: before and during the loop, and change the loop to skip the first element. (minor code duplication)

This is the go-to method when the "loop body" is a single function call

Neither of these is a completely generalized solution, and while its only a few lines + a state variable, I'm trying to find an ideal solution.

Priorities:

No needless source code duplication (but willing to accept binary code duplication)
Efficiency
Clear semantics
Trivially usable (aka simple syntax, few library requirements)

The closest I've come to this in C or C++ is a slight modification to Knuth's loop-and-a-half:

template<class T>
void print(std::vector<T> const &x) {
  std::cout << '[';
  typename std::vector<T>::const_iterator
    begin = x.begin(),
    end = x.end();
  if (begin != end) {  // Duplicated condition to handle the empty case.
    while (true) {  // Here is the "loop and a half".
      std::cout << *begin;
      if (++begin == end) break;
      std::cout << ", ";
    }
  }
  std::cout << "]\n";
}

C++0x allows you to generalize:

template<class Iter, class Body, class Between>
void foreach(Iter begin, Iter end, Body body, Between between) {
  if (begin != end) {  // This duplication doesn't matter as it is
                       // wrapped up in a library function.
    while (true) {
      body(*begin);
      if (++begin == end) break;
      between();
    }
  }
}

template<class T>
void print(std::vector<T> const &x) {
  std::cout << '[';
  foreach(x.begin(), x.end(),
    [](T const& v) {
      std::cout << v;
      // Long code here is still readable.
    },
    []{
      std::cout << ", ";
      // Long code here is still readable.
    });
  std::cout << "]\n";
}

Lambda capture even allows you to modify local variables in the function calling foreach.

Read about visitor pattern...

For more complex object, sample:

template<class T>
struct Walker
{
    Walker(Item *parent): m_parent(parent){}
    Walker(Item *parent, T const& f): m_parent(parent), f(f){}
    // visit all elements
    Walker& Walk()
    {
        TestClass::iterator it = parent->begin(), end = parent->end();
        for( ; it != end; ++it)
        {
            f.Visit(*it);
        }
        return *this;
    }
    // get visited result
    T const& GetF()const { return f; }
private:
    Walker& operator = (Walker const& rhs);
    Item* m_parent;
    T f;
};

and define class, for example:

struct VisitorClass
{
    void Visit(TestClass*){}
};

after that use it:

Walker<VisitorClass> testVisit(this);


Tracking the stability of a website using ping monitor I'm new to coding and made a small Node script that checks when a website is down because of high traffic. It's a website that sells tickets and I don't want to press F5 every 10 seconds to check if the website works again.

Because I send a ping so often I sometimes receive something back from the website. But when I check it again a couple of seconds later I get a request timeout again.

So I made a counter to track how stable the website is. If I receive a request timeout subtract from the counter.

It works, but I was wondering if there is a better way or solution to do this. Because I'm still new I don't have much experience with other solutions to this sort of problem.

This is my code:

const Monitor = require('ping-monitor');
const sendEmail = require('./Email.js')

const myMonitor = new Monitor({
  website: 'https://www.pathe.nl/',
  title: 'Pathe',
  interval: 0.1 // minutes, so 0.1 is 6 seconds
});

let counterUp = 0;

myMonitor.on('up', function (res, state) {
  counterUp++
  console.log('counter is ' + counterUp)
  console.log('Yay!! ' + res.website + ' is up.');

  // send email when script made sure the website is really up and stable. Otherwise we receive an email when the website isn't fully up and running. Because we send a ping every 6 seconds.
  if (counterUp == 20) {
    sendEmail(myMonitor.title)
    console.log('sending email')
  }
});

myMonitor.on('down', function (res) {
  counterUp--
  console.log('counter is ' + counterUp)
  console.log('Oh Snap!! ' + res.website + ' is down! ' + res.statusMessage);
});

myMonitor.on('stop', function (website) {
  console.log(website + ' monitor has stopped.');
});

myMonitor.on('error', function (error) {
  console.log(error);
});

In reality, people just use third-party services for that. For instance, uptime website monitoring can be done StatusCake. If you own the target site, you install infrastructure tools like New Relic. Cloud services these days also provide uptime data and tools out of the box.

The only reason I would write my own uptime monitor is if  you're doing this for a small project or doing it for fun.

Now the problem with the uptime monitor you wrote is that it contributes to the site traffic. To the website, you're just another client trying to connect to the site. Together with your traffic are other sources of traffic, like legitimate users, web crawlers, malicious site scanners, DDOS bots, etc.

The reason you get the Request Timeout (HTTP 504) is because the site is already overloaded. It can be worse though. The site may choose to ignore you, block you temporarily, or even permanently. If you've seen a captcha appear when doing a Google search, that's one example.

So, what I recommend is to:

Reduce the rate you ping. Every 5, 15, or 60 minutes is reasonable. You're probably not going to need it every 6 seconds.
Hit a static asset on the domain instead, like the favicon. Hitting actual pages will cause 504s since it requires logic and probably database calls to generate the page. Just make sure it's not cached or served from a CDN.

This only tells you if the static server/caching proxy is up, not the actual server with the logic.

If the website has an API for uptime or a status page that you can scrape, use that instead. Those are usually served by a separate server so they can still tell you the status even if the main site is down.
If you own the website, monitor the infrastructure instead.


Exhaustive search for encryption keys This does the job, but is not especially elegant.

What is the preferred Pythonic idiom to my childish nests?

def bytexor(a, b):
    res = ""
    for x, y in zip(a, b):
        if (x == "1" and y == "0") or (y =="1" and x == "0"):
            res += "1"
        else:
            res += "0"

    return res

def get_all():
    res = []
    bit = ["0","1"]
    for i in bit:
        for j in bit:
            for k in bit:
                for l in bit:
                    res.append(i+j+k+l)
    return res

if __name__=="__main__":

    for k0 in get_all():
        for k1 in get_all():
            for k2 in get_all():
                for k3 in get_all():
                    for k4 in get_all():
                        if bytexor(bytexor(k0, k2), k3) == "0011":
                            if bytexor(bytexor(k0, k2), k4) == "1010":
                                if bytexor(bytexor(bytexor(k0,k1),k2),k3) == "0110":
                                    print k0, k1, k2, k3, k4
                                    print bytexor(bytexor(bytexor(k0, k1),k2),k4)

To convert an integer to a bit string with a particular number of digits, use string.format with the b format type. For example:

>>> ['{0:04b}'.format(i) for i in range(16)]
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111',
 '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

But really it looks to me as though you don't want to be working with bit strings at all. You just want to be working with integers.

So instead of get_all, just write range(16) and instead of bytexor, write ^. Your entire program can be written like this:

from itertools import product
for a, b, c, d, e in product(range(16), repeat=5):
    if a ^ c ^ d == 3 and a ^ c ^ e == 10 and a ^ b ^ c ^ d == 6:
        print a, b, c, d, e, a ^ b ^ c ^ e

(This will also run a lot faster without all that fiddling about with strings.)

I have answered awhile ago to this very type of question. This is a very simple problem. You should not complicate it at all with iterators.

The trick is that the bit pattern you are seeking for is actually the bits of numbers incremented by 1!

Something like:

def get_all():
    res = []
    for i in range(16):
        # get the last four bits of binary form i which is an int
        bin(i) # a string like '0b0000' - strip '0b', 0 pad it to 4 length

I am not really the python guy, but I hope the idea is clear. Equivalent Java code:

int len = 3; // your number of for loops
int num = (int)Math.pow(2, len);
for(int i=0; i<num; i++){
    // https://stackoverflow.com/a/4421438/1273830
    System.out.println(String.format("%"+len+"s", Integer.toBinaryString(i)).replace(' ', '0'));
}

Happy coding.


Remove vulnerabilities from query on public website I think that the following query is preventing against SQL injection, but what other measures do I need to take to ensure my queries are 100% safe from any malicious attacks?

$statement = $db->prepare(
    "INSERT INTO blogs (blogtitle, blogdesc, coverimage, userID, frontpage, tags)
    VALUES (:buildtitle, :builddesc, :buildcover, :userid, :frontpage, :addtags)"
);

if ($statement->execute(array(
    ':buildtitle' => $_POST['addbuildtitle'],
    ':builddesc' => $_POST['addbuilddesc'],
    ':buildcover' => $imagepath,
    ':userid' => $_POST['adduserid'],
    ':frontpage' => $frontpage,
    ':addtags' => $_POST['addtags']))
);

Though prepared statements do a pretty good job protecting your DB from injection attacks, it never hurts to perform some additional checks on the data you're receiving. For example: when a request is supposed to contain an email address, you might perform a SELECT query usign that email address, or insert it in your DB. If so, you should add this:

if (!filter_var($_POST['email'], FILTER_VALIDATE_EMAIL))
{
    exit();//redirect, optionally show error message
}

Same goes for any posted data, as one of the comments mentions: XSS attacks are one of the biggest threats on the web today. I've dealt with the matter in this answer.
The very least you could do is:

$execParam = array_map(
    'strip_tags'
    array(
        ':buildtitle' => $_POST['addbuildtitle'],
        ':builddesc' => $_POST['addbuilddesc'],
        ':buildcover' => $imagepath,
        ':userid' => $_POST['adduserid'],
        ':frontpage' => $frontpage,
        ':addtags' => $_POST['addtags']
    )
);
$statement->execute($execParam);

Here, I've just called strip_tags on each and every single item you're about to insert, to avoid some jokester posting

<script>location.href = 'http://malware-infested-site.org';</script>;

in the addbuilddesc field... because, if you don't filter those things out, people visiting your site won't be all too happy about that... and be honest: would you?

You can take this as far as you want. Since you're obviously using a traditional *SQL DB, you might use the table schema, to determine if the POST params are of the correct type and length:

//assume blogtitle is a VARCHAR(255) field:
':buildtitle' => sprintf('%255s',$_POST['addbuildtitle'])
//and userID is an unsigned int, 11 long
':userid' => sprintf("%11d",abs((int)$_POST['adduserid']))

This ensures your :buildtitle bind will be no longer than 255 chars. The userid value will not be negative, and will be an integer of max 11 digits long.
But to implement this would mean a huuuge mess of sprintf calls, so you could use dataModels for this (check pretty much all of my DB related answers on this site for details), and use getters and setters that use this sprintf function to format the data accordingly.
still, this will mean a lot of overhead for each and every query. Sadly, the tradoff will always be one of performance vs security. If security is all you're after, you'll also note that, in my other answers, I basically advise everybody who's trying to create a solid (as in strong, but also as in S.O.L.I.D.) query system, to have a look at doctrine. No need to reinvent the wheel...
Anyway, I'm going off course...

Now, as far as injection goes, prepared statements are pretty robust, provided you don't take it to new, absurd, extremes. I've seen people use variables instead of the DB name, just like I've seen them use POST params to fill in the table name. You don't seem to do that, and that's good... great even. Just a friendly warning: if ever you consider using variables in those parts of your query that should be static (SELECT fieldnames FROM tblNames), step back and rethink your approach, because that's where you may still introduce vulnerabilities to your system.

Basically, prepared statements work like this:

Pass a string, from which a statement is to be prepared. This is processed by the DB server as is.
The DB server parses, and "prepares" the query (optimization etc...)
Pass the arguments, with which the statement is to be executed. These values (binds) are sent via a different protocol and here's where they're being escaped correctly.

As you can see, the binds are what is being escaped and sent completely separatly, that's why prepared statements are safe. This also explains why the actual SELECT and FROM clauses in a prepared statement may not be gotten from user input. This part of the query isn't processed in the same way the binds are...

Other niggles:

At no point do you seem to be checking isset($_POST['adduserid']) and other post keys. You just seem to expect they're there. That might trigger notices, and slows your code down. Just isset() all those params.
You have a semi-colon at the end of your if statement. If you copy-pasted this code, then that's going to give you grief.
Ensure, especially with INSERT's to set the PDO::ERR_MODE correctly, and insert in transactions. In case something goes wrong, you can still use rollBack!

Here's a little sample of how that would look

$db->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);//force PDO to throw on error
try
{
    $db->beginTransaction();//start here
    $stmt = $db->prepare($query);
    $stmt->execute($sanitizedInsertParamsArray);
    $db->commit();//make insert permament
}
catch(PDOExcpetion $e)
{
    $db->rollBack();//revert insert!
    exit($e->getMessage());
}

The code above will throw an instance of PDOException if the prepare, execute call or even the commit fails. As long as commit hasn't been called, the transaction is still pending (ie the data isn't really inserted yet).
So simply put, this snippet asks the DB: prepare this statement, then try to execute it with these values, if you did that, then save it. If any of these three steps failed, $db->rollBack() just tells the DB: OK, so it didn't work, forget about it... don't try and save half of the data, just forget everything.

Transactions are a good way to avoid orphaned data (as are FK's, btw). And they make for a safer query all together, too...

100% safe is not possible; I'm sure someone will break prepared statements if they haven't already.  You have already take an big step in security by using prepared statements over escaping.

One important step is to validate your POST variables.  For instance let's say a valid buildtitle only consists of alpha numeric characters; it should be validated against that.  Then you would wind up with something like ':buildtitle' => $buildtitle_clean,.  You may already be doing this and just keeping it in the POST array, but it is important to change if you are not.

Other than that, I think it is as safe as you can make it.


Avoiding Duplicates in a Ruby on Rails Factory Girl Factory with Fake I have a Factory Girl factory that needs to generate a unique name using Faker. Unfortunately, Factory Girl generates duplicates relatively frequently, which causes intermittent test errors. I previously added a random integer after the Faker name, but I am now checking the database to make sure that a potential name from Faker doesn't already exist.

FactoryGirl.define do
  factory :company do
    name do
      name = Faker::Company.name
      name = Faker::Company.name while Company.exists?(name: name)
      name
    end
  end
end

The above code works but seems inelegant. I'm assigning name in the first row of the block so that only one DB lookup (instead of two) will be necessary in the most common case where a Fake name is unique.

I end the block with name as otherwise the while statement returns nil when the loop ends.

The simplest thing to do is probably to use FactoryGirl's sequence:

FactoryGirl.define do
  factory :company do
    sequence(:name) { |n| "#{Faker::Company.name} #{n}" }
  end
end

sequence basically gives you an auto-incrementing integer, so you can avoid uniqueness issues. Sure, it'll generate some slightly odd company names, but for testing that shouldn't matter much.

In general though, I don't feel too great a need for something like Faker. Something like this should work just as well:

FactoryGirl.define do
  factory :company do
    sequence(:name) { |n| "Acme Inc. #{n}" }
  end
end

If it's only your specs looking at the data, it doesn't really matter if the company name's "Acme", "foobar 42", or "ACC8B1B7-7EC0-4F05-AB2A-B487C134F6BF".

Besides, your current solution is:

non-deterministic, so it may never exit the while loop if it just happens to keep picking the same couple names again and again,
but even if we ignore that, the act of adding more tests that use company records, will mean more name collisions and longer time spent in the loop. I don't know how Faker works, but (unlikely but technically possible) you might even end up exhausting every name Faker can come up with, and end up looping forever.

A different approach would be to utilize the following code:

Faker::Lorem.unique.word


Projecteuler.net Problem 2 using collection pipeline Pattern I solve projecteuler.net Problem 2  deferent way

Generate number from 1 to range ex 100  and get the even number
Get Fibonacci numbers from list
Reduce array

I have one problem with a large set of numbers like 1000000 or 4000000.
can I ask how can I optimize the code? I am trying to solve the problem as a collection pipeline
swift code
var evenArray = ((0..<100).filter({$0 % 2 == 0}))

print(evenArray)

var evenFibArray = evenArray.filter {(isPerfectSquare(5 * $0 * $0  + 4) || isPerfectSquare(5 * $0 * $0  - 4))}

print(evenFibArray)

var result  = evenFibArray.reduce(into: 0){$0 += $1}

print(result)

func isPerfectSquare(_ x:Int ) -> Bool {
    let i = Int(sqrt(Double(x)))
    return  (i * i == x)
}

updated my code to use a deferent approach and apply collection pipeline
update my code

I use collection pipeline refactoring for more information about the
topics look
https://martinfowler.com/articles/refactoring-pipelines.html
I use stride function instead of filter to generate even Integer array

Sidenote: I don't know if I will save a couple of computing cycles—all I want to make my code more Swifty.
func isPerfectSquare(_ x:Int ) -> Bool {
    let i = Int(sqrt(Double(x)))
    return  (i * i == x)
}

var result  =  (Array(stride(from: 0`enter code here`, to: 100, by: 2)).filter{(isPerfectSquare(5 * $0 * $0  + 4) || isPerfectSquare(5 * $0 * $0  - 4))}).reduce(into: 0){$0 += $1}
print(result)


Validate that brackets are balanced I've done a test for a job (which I failed) and I'd like to know in which ways my code could've been better.

Here are the questions and my answers, it's not very long.

  1) Make a program that checks if a string has balanced parentheses or
  brackets.

  Braces: (), [], <>
  For every closing brace, there must've been an opening, and for every open there must be a closure
  return 1 if it's balanced, or 0 if it isn't

My code:

const verify = (string) => {

    // Array of the type of braces
    var braces = ["(", ")", "[", "]", "<", ">"];
    // Array half the length of braces Array
    var balanced = Array.apply(null, {length: braces.length/2}).map(function() { return 0; });

    for(let i = 0; i < string.length; ++i) {
        let char = string[i], braceIndex = braces.indexOf(char);

        if ( braceIndex == -1 ) {
            // If current char is not any type of brace, continue.
            continue;
        }

        // Get the index of the brace found halved and floored
        let braceBalancingIndex = braceIndex / 2, braceFloor = Math.floor( braceBalancingIndex );

        // If the halved index is equal to the index, then it must be an opening, else it must be a closing
        if (braceBalancingIndex == braceFloor) {
            balanced[braceFloor]++;
        }
        else {
            balanced[braceFloor]--;
        }

        // If at any type being, the balance is negative, there was a closing without opening
        for(let j = 0; j < balanced.length; ++j) {
            if (balanced[j] < 0) return 0;
        }

    }

    // If at the end the string is not balanced, there where more openings than closings
    for(let i = 0; i < balanced.length; ++i) {
        if (balanced[i] != 0) return 0;
    }

    return 1;
}

At its heart, this is a stack problem.  You can get O(n) worst-case performance and O(n) space complexity by simply iterating the string in place, pushing opening brackets onto a stack and when encountering a closing bracket, popping the last item off stack to compare against.

You need to end up with an empty stack, and you can never have a case where you try to read out of an empty stack.  This in addition, of course to making sure items you are comparing out of the stack match appropriately.  So, there are three failure scenarios.

The solution I present might technically be optimized by hard-coding the opening and closing bracket values into conditionals and such, but I find this solution more flexible and easier to maintain from a code standpoint, as you have decoupled the bracket "configuration" from the code logic.

var balanced = '({[test string](test [string])})';
var unbalanced = '{()}]';
var empty = '';

var bracketConfig = [
    { left: '{', right: '}' },
    { left: '[', right: ']' },
    { left: '(', right: ')' }
];

function isBalanced(subject, bracketConfig) {
    // not shown - perhaps validate subject as string and error out if failing

    // build bracket arrays from config
    var openingChars = [];
    var closingChars = [];
    bracketConfig.forEach( (item) => {
        openingChars.push(item.left);
        closingChars.push(item.right);
    });

    var stack = [];
    for (var i = 0, len = subject.length; i < len; i++) {
        var char = subject[i];
        var openIdx = openingChars.indexOf(char);
        var closeIdx = closingChars.indexOf(char);
        if (openIdx > -1) {
            stack.push(openIdx);
        } else if (closeIdx > -1) {
            if (stack.length === 0) return 0;
            lastIdx = stack.pop();
            if(lastIdx !== closeIdx) return 0;
        }
    }

    if (stack.length !== 0) return 0;
    return 1;
}

// run tests
console.log(isBalanced(balanced, bracketConfig));
console.log(isBalanced(unbalanced, bracketConfig));
console.log(isBalanced(empty, bracketConfig));

JSFiddle of this example

My guess is that, for your interview, they were really looking to see that you could identify this as a stack problem and come up with a reasonable implementation.

The solution that I presented was using stack push and pop method. There are some givens that we know it going to fail:

The last bracket must be a closing bracket otherwise, it fails.
The first bracket must be an opening bracket otherwise, it fails.
It must be an even number since bracket must be in pairs.

The solution I implemented was to push from last closing bracket into
balanced stack until it reaches opening bracket, then it must pair up with
with closing bracket in the balanced stack, if it doesn't match at top of balanced stack then it fails. If it matches then pop the closing bracket off the balanced stack. The balanced stack only stores closing brackets. arr is an array that stores all brackets that need to be iterated through from last to first bracket. The balanced bracket must be empty at the end in order to pass.

var open  = ['[','<','('];
var close = [']','>',')'];

var isBalanced = function(br){
  let balanced = [];

  let arr = br.replace(/[^\(\)\<\>\[\]]/g,'').split(''); //brackets only

    if(arr.length % 2 !== 0) return 0; // must be an even pair

    for(let i=arr.length-1; i>=0; i--){
        if(close.indexOf(arr[i])>=0) //check if it is a closing bracket
            balanced.push(arr[i]);
        else{  // if bracket match, then pop off balanced array
            if(open.indexOf(arr[i])!==close.indexOf(balanced[balanced.length-1]))
                return 0;
            else
                balanced.pop();
        }
    }
    return (balanced.length>0)?0:1;
};

console.log(isBalanced('<>[ccg[<a>]]b([09])'));   // 1
console.log(isBalanced('<[[<>>]]([])'));          // 0
console.log(isBalanced('][<>]]([])'));            // 0
console.log(isBalanced('foo(bar);'));             // 1


Custom Dynamic Array Pretty simple class but just want to make sure I've approached it correctly.

public class DynamicArray<T> : IEnumerable<T>, ICollection<T>
    {
        private T[] _items;
        private int _size;
        private const int _growFactor = 2;

        public DynamicArray()
        {
            _items = new T[4];
        }

        public int Count
        {
            get
            {
                return _size;
            }
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        public void Add(T item)
        {
            if (_size + 1 > _items.Length)
            {
                var newArray = new T[_items.Length * _growFactor];
                _items.CopyTo(newArray, 0);
                _items = newArray;
            }
            _items[_size] = item;
            _size++;
        }

        public void Clear()
        {
            _items = new T[2];
            _size = 0;
        }

        public bool Contains(T item)
        {
            foreach(var value in _items)
            {
                if (value.Equals(item))
                {
                    return true;
                }
            }
            return false;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            _items.CopyTo(array, arrayIndex);
        }

        public IEnumerator<T> GetEnumerator()
        {
            for(var i = 0; i < _size; i++)
            {
                yield return _items[i];
            }
        }

        public bool Remove(T item)
        {
            for(var i = 0; i < _items.Length; i++)
            {
                if (_items[i].Equals(item))
                {
                    _items[i] = default(T);
                    _size--;
                    return true;
                }
            }
            return false;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

Just a couple of minor points:

In your constructor, you create an the array with an initial size of 4:

_items = new T[4];

However in your Clear method you set it to an size of 2:

_items = new T[2];

It's odd that you set it to a smaller number.  If you had a constant for initial size, or called Clear from the constructor this could be avoided.
That said, do you really want clear to discard _items?  If you're reusing the array in a similar section of code, it seems reasonable to assume that after Clear has been called, there is a good chance the the array would grow again to a similar size.  It may be more efficient to simply reset _size, but leave _items intact.  Obviously this depends how you're using the array as to whether or not it's a good idea...
You don't limit the size of the array.  Dynamic doubling whilst efficient, can get big pretty quick.  You might want to consider adding a maximum size to your array, again, this would depend on what you're using it for as to whether or not it's worth while.  List limits it's growth for example, albeit to a rather large number.

I re-factored your implementation to be more efficient.
Such as removing unnecessary 'for-loops' and extra variables.

public class DynamicArray<T> : IEnumerable<T>, ICollection<T>
{
    private T[] _items;

    public DynamicArray()
    {
    }

    public int Count
    {
        get
        {
            if (_items == null)
                return 0;
            return _items.Length;
        }
    }

    public bool IsReadOnly => false;

    public void Add(T item)
    {
        if (_items == null)
        {
            _items = new T[1];
        }
        else
        {
            Array.Resize(ref _items,_items.Length+1);
        }
        _items[_items.Length - 1] = item;
    }

    public void Clear()
    {
        _items = null;
    }

    public bool Contains(T item)
    {
        if (_items == null)
            return false;
        return _items.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        _items.CopyTo(array, arrayIndex);
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (_items == null)
            return Enumerable.Empty<T>().GetEnumerator();
        return _items.AsEnumerable().GetEnumerator();
   }

    public bool Remove(T item)
    {
        if (item == null)
            return false;

        if(_items==null)
            return false;

        var temp = _items.Where(i => !i.Equals(item));
        _items = temp.ToArray();

        return true;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Please find below the Unit-Test class that I used to validate the implementation against your original intent.

[TestClass]
public class DynamicArrayTests
{

    private DynamicArray<int> _sut;

    [TestInitialize]
    public void Init()
    {
        _sut = new DynamicArray<int>();
    }

    [TestMethod]
    public void ReadOnly_ShouldReturn_False()
    {
        Assert.IsFalse(_sut.IsReadOnly);
    }

    [TestMethod]
    public void Count_ShouldReturn_InitialCount_0()
    {
        var expectedCount = 0;
        var actualCount = _sut.Count;
        Assert.AreEqual(expectedCount, actualCount);
    }

    [TestMethod]
    public void Add_ShouldIncreaseCount()
    {
        var expectedCount = 1;

        _sut.Add(4);
        var actualCount = _sut.Count;

        Assert.AreEqual(expectedCount, actualCount);

    }

    [TestMethod]
    public void Clear_ShouldClearAllElements()
    {
        var expectedCount = 0;

        _sut.Clear();
        var actualCount = _sut.Count;

        Assert.AreEqual(expectedCount, actualCount);
    }

    [TestMethod]
    public void Contains_ElementExists_True()
    {
        _sut.Add(5);
        var actual = _sut.Contains(5);

        Assert.IsTrue(actual);
    }

    [TestMethod]
    public void GetEnumerator_FromEmptyList_ReturnList()
    {
        var list = _sut.GetEnumerator();

        Assert.IsNotNull(list);
    }

    [TestMethod]
    public void GetEnumerator_ReturnExpectedValue()
    {
        _sut.Add(25);

        var list = _sut.GetEnumerator();
        list.MoveNext();

        Assert.IsTrue(list.Current.Equals(25));

    }

    [TestMethod]
    public void Remove_ShouldRemoveGivenElement_Return()
    {
        var expectedCount = 1;

        _sut.Add(20);
        _sut.Add(30);

        var status = _sut.Remove(20);

        var actualCount = _sut.Count;

        var contains = _sut.Contains(20);

        Assert.IsTrue(status);
        Assert.AreEqual(expectedCount, actualCount);
        Assert.IsFalse(contains);

    }

}

Also note that this implementation is not thread-safe.


Search set, return item Is there a more efficient way of achieving the same result besides setting up a database?

# In reality, contains 4 million tuples.
stuff_tuple = (
    ('hello', 241, 1),
    ('hi', 243, 3),
    ('hey', 242, 2)
)

# Convert tuple to set for faster searching?
stuff_set = set(stuff_tuple)

# Only first two values are known ("hello", 241), ('hi', 243), etc.
for item in stuff_set:
    if item[0] == 'hello' and item[1] == 241:
        print item[2]

If all your queries are similar to the example, you would obviously benefit from storing the data in a dict where a tuple of two values is the key, and the value is a list of ints -- all of the third items that share the same key.

from collections import defaultdict

stuff_dict = defaultdict(list)
for t in stuff_tuple:
    stuff_dict[t[:2]].append(t[2])

for item in stuff_dict['hello', 241]:
    print item

This question suggests that dictionaries and sets - which are both based on hashtables internally -- are the fastest for random retrieval of hashable data (which your sample seems to b). It's always a good idea to try the base data structures in Python, they're usually pretty high quality :)

If that's not fast enough, you have a couple of options.

If you can come up with a single sortable key value for your list, you could use the bisect module to speed up searches.  For example, if you had a deterministic way of turning the first two keys into a number, and then sort on that number, bisect should make it easy to find items quickly. The big drawback here is that you're on the hook for coming up with the method for creating that numberic key, which can be dicey depending on your data set.

The less ambitious (but maybe less risky) is to subdivide the data yourself so you don't search 4 million items every time. If you have to use data like the data in your example, you should look at patterns in your sample for characteristics that group it into similarly sized subsets and store the data that way first -- for example, if your whole table of four million entries included a roughly flat distribution of the second (integer) key you could bust the whole up into buckets in a pre-pass, producing a few hundred or few thousand lists with self-similar second keys:

 list_241 = [('hello', 241, 1), ('goodbye', 241, 2), ('yo!', 241, 3)....]
 list_242 = [('hi', 242, 3), ('hola', 242, 4)...]

then you store the lists in a dictionary and grab them as a first pass, then do the brute force search in the sub-list of thousands instead of the master list of millions.  Of course some data won't lend itself to this either, but if it looks anything like your sample it should not be too hard.  THe binning doesn't have to be super logical - you could bin on the length of the string in item[0] or the first letter as easily as you could on item 1 -- but to be useful it will need to produces bins of similar size.  The nice thing is that with really big lists it's easy to rack up big gains: even going from 1 list of 4million to 10 lists of 400000 will probably make things faster.


Sequence generation problem - Fibonacci Below is the representation and user interface fib_sequence for generating a Fibonacci sequence:

empty_rlist = None
#Representation - start
#Constructor
def rlist(first, rest):
    return (first, rest)

#Selector
def first(s):
    return s[0]

def rest(s):
    return s[1]

#Representation - end

def fib_sequence(k):
    prev, curr = 1, 0
    def generate_sequence(prev, curr, k):
        if k == 0:
           return empty_rlist
        elif k == 1:
           return (curr, empty_rlist)
        else:
           return rlist(curr, generate_sequence(curr, prev+curr, k - 1))
    return generate_sequence(prev, curr, k)

Program output:

>python -i fibonacci_sequence.py
>>> fib_sequence(0)
>>> fib_sequence(1)
(0, None)
>>> fib_sequence(2)
(0, (1, None))
>>> fib_sequence(3)
(0, (1, (1, None)))
>>> fib_sequence(4)
(0, (1, (1, (2, None))))
>>> fib_sequence(5)
(0, (1, (1, (2, (3, None)))))

The above program provides representation as (element, restOfTheList).

We have this sequence containers in Python:

>>> tuple =  (1, 2, 3, 4)
>>> r = range(1,5)
>>> str = '1234'

Is the representation of the aforementioned Python sequence containers same as the above representation of the Fibonacci sequence abstraction?

If no, can we make the representation of the Fibonacci sequence abstraction better, basically to forward this sequence for further processing by sequence processing functions like map() filter() sum() etc.?

You should call rlist() consistently, and write

elif k == 1:
    return rlist(curr, empty_rlist)

… for reasons that will become apparent.  Also be sure to use four spaces per level of indentation, as prescribed by PEP 8.

Are your tuple, range, and string the same as each other?  No, comparing them using == will obviously return False.  What they all have in common, though, is that they are all iterables.  Being iterable means that you can use them in for e in iterable expressions — either in a loop or a generator.

That means that if you want to be able to write things like print([e for e in fib_sequence(5)]), you'll need to make your rlist type iterable.  Here's one way you could accomplish that.

class rlist(tuple):
    def __new__(cls, first, rest):
        return super(rlist, cls).__new__(cls, (first, rest))

    def __iter__(self):
        seq = self
        while seq is not None:
            yield first(seq)
            seq = rest(seq)

This works as long as you have applied the rlist() fix to fib_sequence() as mentioned above.

I'm no ninja coder, still though I know to handle myself. Your function does not need to take three arguments, you just need two. Avoid adding many conditions when iterating, it makes it slower.
The most optimized solution I could find was this, is 10 times faster

def Fibonacci(n):
    a,b=0,1
    for i in range(n):
        a, b = b, a+b
    return a


Printing staircase revisited What can be more elegant ways to solve the given problem.

    #
   ##
  ###
 ####

Code:

function StairCase(n) {
    for (var i = 1; i <= n; i++) {
        var col = i;
        for(var j = 1; j <= n - col; j++) {
            process.stdout.write(' ');
        }
        for(var j = 1; j <= col; j++) {
            process.stdout.write('#');
        }
        process.stdout.write('\n');
    }

}

JavaScript function names should start with a lowercase character, and "staircase" is one compound word in English.

Since every line is nearly the same, and only one character changes at a time, you should take advantage of that and use an array as a buffer.

function staircase(n) {
    var line = Array(n + 1).fill(' ');
    line[n] = '\n';
    for (var i = n - 1; i >= 0; i--) {
        line[i] = '#';
        process.stdout.write(line.join(''));
    }
}

Here is the solution using ES6 array.map() with no for-loop used, which to me is the most clear and intuitive solution:

function staircase(n) {
    // intiate an empty n*n matrix
    let matrix = Array(n).fill().map(() => Array(n).fill());

    matrix.map((curArr, idY) => { // for each array row in matrix
        curArr.map((curVal, idX) => { // for each element in the current array row
            // evaluate each element's to-be-assigned value
            matrix[idY][idX] = (idX + idY + 1 >= n) ? '#' : ' ';
        }, [])
    }, [])

    // convert each row into string
    matrix.forEach((row) => {
        console.log(row.join(''));
    })
    // now we have the staircase
}

If you're interested, go researching about functional programming, pure functions and immutability.


Creating range of numeric values based on array of strings Basically I have an array of strings. In this array, a range separator word might exist. For this example, I'm going to use the word to as range separator. We can assume that the range separator is not the first or last entry in the array. If we find the range separator we need to get the entry before and the entry after the separator, compare the two entries that we can assume are safe to parse as integer and find the character that differs between them. We then need to create new entries by counting up the number that is different, and return an IEnumerable<string> containing the new entries. We can also assume that only one character will differ between the start of the range and the end of the range.

For example, if the array contains these values:

1102
to
1602

we need to return

1202
1302
1402
1502

And here's my code:

public static IEnumerable<string> GetRangeSegments(string[] segments, string rangeIndicator)
{
    var rangeIndicatorIndex = Array.IndexOf(segments, rangeIndicator);
    var rangeSegments = new string[] { };

    if (rangeIndicatorIndex < 0)
    {
        return rangeSegments;
    }

    var rangeStart = segments[rangeIndicatorIndex - 1];
    var rangeEnd = segments[rangeIndicatorIndex + 1];

    var startChars = rangeStart.ToCharArray();
    var endChars = rangeEnd.ToCharArray();

    if (startChars.Length != endChars.Length)
    {
        return rangeSegments;
    }

    var diffIndex = -1;

    for (var i = 0; i < startChars.Length; i++)
    {
        if (startChars[i] == endChars[i])
        {
            continue;
        }

        diffIndex = i;
        break;
    }

    if (diffIndex == -1)
    {
        return rangeSegments;
    }

    var start = int.Parse(startChars[diffIndex].ToString()) + 1;
    var end = int.Parse(endChars[diffIndex].ToString());

    var numbers = Enumerable.Range(start, end - start);
    return rangeSegments.Concat(numbers.Select(number => rangeStart.Remove(diffIndex, 1).Insert(diffIndex, number.ToString())));
}

If a method returns an IEnumerable<T> we expect an deffered execution using the yield keyword.

To make this happen and have a valid parameter validation we need another method which calls the method which is yielding.

So let us add one

public static IEnumerable<string> GetRangeSegments(string[] segments, string rangeIndicator)
{
    if (segments==null) { throw new ArgumentNullException(nameof(segments)); }
    if (rangeIndicator == null) { throw new ArgumentNullException(nameof(rangeIndicator)); }
    if (string.IsNullOrWhiteSpace(rangeIndicator)) { throw new ArgumentException("May not be empty.", nameof(rangeIndicator)); }

    return GetSegments(segments, rangeIndicator);
}

All the if statements will be executed and if the code comes to return it will immediately return because it knows about the yieldings in the GetSegments() method.

Using yield makes the empty string[] rangeSegments superflous because we just yield break. If you call ToArray() on the result of these yield break you get an empty array.

Because you can access the chars of a string by using its index you don't need ToCharArray().

If there isn't by some mistake either rangeStart[diffIndex] or rangeEnd[diffIndex] a digit the code blows up at the call to int.Parse(). A better way would be to use int.TryParse() and if this doesn't succeed you could yield break.

But if we e.g do int start = rangeStart[diffIndex] + 1; then the ascii value of that char will be casted to an int which we then can check if 47 < start < 58 and if not we yield break here.

The return statmenet in your method is just unreadable, hence hard to maintain as well. To "replace" a single char inside a string we can just use a StringBuilder.

Summing all up lead to

public static IEnumerable<string> GetRangeSegments(string[] segments, string rangeIndicator)
{
    if (segments == null) { throw new ArgumentNullException(nameof(segments)); }
    if (rangeIndicator == null) { throw new ArgumentNullException(nameof(rangeIndicator)); }
    if (string.IsNullOrWhiteSpace(rangeIndicator)) { throw new ArgumentException("May not be empty.", nameof(rangeIndicator)); }
    return GetSegments(segments, rangeIndicator);
}

private const int ascii0 = 48;
private const int ascii9 = 57;
private static IEnumerable<string> GetSegments(string[] segments, string rangeIndicator)
{
    var rangeIndicatorIndex = Array.IndexOf(segments, rangeIndicator);

    if (rangeIndicatorIndex < 0 || rangeIndicatorIndex == segments.Length - 1)
    {
        yield break;
    }

    var rangeStart = segments[rangeIndicatorIndex - 1];
    var rangeEnd = segments[rangeIndicatorIndex + 1];

    if (rangeStart.Length != rangeEnd.Length)
    {
        yield break;
    }

    var diffIndex = GetFirstDifferentCharPosition(rangeStart, rangeEnd);
    if (diffIndex == -1)
    {
        yield break;
    }

    var start = rangeStart[diffIndex] + 1;
    if (start < ascii0 || start > ascii9) { yield break; }

    var end = rangeEnd[diffIndex];
    if (end < ascii0 || end > ascii9) { yield break; }

    if (end < start) { yield break; }

    StringBuilder sb = new StringBuilder(rangeStart);
    for (int i = start; i < end; i++)
    {
        sb[diffIndex] = (char)i;
        yield return sb.ToString();
    }

}
private static int GetFirstDifferentCharPosition(string first, string second)
{
    var diffIndex = -1;

    for (var i = 0; i < first.Length; i++)
    {
        if (first[i] != second[i])
        {
            diffIndex = i;
            break;
        }
    }
    return diffIndex;
}

Here is my implementation of this. I chose a simpler way to go about it:

    static void Main(string[] args)
    {

        IEnumerable<string> retorno = GetInterval(new string[] { "1201", "to", "1601" }, "to");
        foreach(var item in retorno)
        {
            Console.WriteLine(item);
        }
        Console.Read();
    }

    public static IEnumerable<string> GetInterval(string[] segments, string separator)
    {
        List<string> lReturn = new List<string>();
        int separatorIndex = Array.IndexOf(segments, separator);
        string first = segments[separatorIndex - 1];
        string second = segments[separatorIndex + 1];
        int indexDiffer = -1;
        bool isDifferent = false;

        while (!(isDifferent = first[indexDiffer] != second[indexDiffer])) { indexDiffer++; };

        if (!isDifferent)
            return null;

        var counter = Convert.ToInt32(first.Remove(indexDiffer + 1)) + 1;
        var endRange = Convert.ToInt32(second.Remove(indexDiffer + 1));

        for (; counter < endRange; counter++)
            lReturn.Add(string.Concat(counter, first.Substring(indexDiffer + 1)));

        return lReturn;
    }

In my implementation i try to not use Linq, it will probably give you a better performance because you are controlling the iterations, also it gives you better maintenance.


Dijkstra's algorithm using priority queue running slower than without PQ I need to implement dijkstra's algorithm and I've done so using this Wikipedia page. I've done it both with priority queue and without.

Both versions work 100% correct, however I need the faster one (priority queue one). The problem is that it isn't faster. My tests show "faster" one runs in more than double the time that "slower" one does, it shouldn't do that. What am I doing wrong?

//more primitive version that in fact runs faster (it shouldn't)

//source is starting node, adj adjacency list, Road represents one edge
private static int dijkstra (int source, ArrayList<Road>[] adj) {
    HashSet<Integer> vertices = new HashSet<>();

    int[] dist = new int[adj.length];
    int[] prev = new int[adj.length];

    for (int i = 0; i < adj.length; i++) {
        dist[i] = Integer.MAX_VALUE;
        prev[i] = Integer.MAX_VALUE;
        vertices.add(i);
    }

    dist[source] = 0;

    while (!vertices.isEmpty()) {
        int currentPathLen = Integer.MAX_VALUE, current = -1;
        for (int v: vertices) {
            if (dist[v] < currentPathLen) {
                current = v;
                currentPathLen = dist[current];
            }
        }

        vertices.remove(current);

        for (Road v: adj[current]) {
            int alt = dist[current] + v.distance;

            if (alt < dist[v.end]) {
                dist[v.end] = alt;
                prev[v.end] = current;
            }
        }
    }
}

//this one should run faster

//same variables as primitive version, except for Node,
//which is made only for PQ prioritizing
private static int improvedDijkstra(int source, ArrayList<Road>[] adj) {
    PriorityQueue<Node> vertices = new PriorityQueue<>();

    int[] dist = new int[adj.length];
    int[] prev = new int[adj.length];

    dist[source] = 0;

    for (int i = 0; i < adj.length; i++) {
        if (i != source) {
            dist[i] = Integer.MAX_VALUE;
            prev[i] = Integer.MAX_VALUE;
        }

        vertices.add(new Node(i, dist[i]));
    }

    while (!vertices.isEmpty()) { //O(n)
        Node u = vertices.poll(); //this should have O(logn)

        for(Road v: adj[u.value]) {  // I suspect the problem is this loop, but it is same
                                     // as in Wikipedia page

            int alt = dist[u.value] + v.distance;

            if (alt < dist[v.end]) {
                dist[v.end] = alt;
                prev[v.end] = alt;

                vertices.add(new Node(v.end, alt)); //this should have O(logn)
            }
        }
    }

I think the problem is that you have more than one instance of a node in the priority queue at a given time.

In the relax operation:

 if (alt < dist[v.end]) {
     dist[v.end] = alt;
     prev[v.end] = alt;

     vertices.add(new Node(v.end, alt)); //this should have O(logn)
 }

You should remove the vertex before adding it or implement a indexed priority queue with a decreased key operation like this one. I'm not sure if java remove operation is \$O(ln(n))\$ thought. Like this:

if (alt < dist[v.end]) {
     dist[v.end] = alt;
     prev[v.end] = alt;
     Node newNode = new Node(v.end, alt);
     vertices.remove(newNode);
     vertices.add(newNode);
 }

Note: You need to override equals for the node.

With the indexed priority queue you would create and add the new node if the queue doesn't contains it, or do decreased key otherwise.

If you do it like this you will lazily add each vertex to the queue so you don't need to add them all at the beginning here:

   dist[source] = 0;
   for (int i = 0; i < adj.length; i++) {
        if (i != source) {
            dist[i] = Integer.MAX_VALUE;
            prev[i] = Integer.MAX_VALUE;
        }

        vertices.add(new Node(i, dist[i])); // <--here
    }

Also you can remove the inner if in the loop like this:

   for (int i = 0; i < adj.length; i++) {
       dist[i] = Integer.MAX_VALUE;
       prev[i] = Integer.MAX_VALUE;
    }
    dist[source] = 0;
    vertices.add(new Node(source, 0));

Do you really need it to be Dijkstra's Algorithm? Because there is an adaption to Dijkstra's algorithm available called A*. It is very similar to Dijkstra, except it uses an additional heuristic to greatly speed it up.

Here is a great article about the algorithm: https://www.raywenderlich.com/4946/introduction-to-a-pathfinding


Function to remove specified html tags from string I recently wrote this function that, when supplied a string and an array of element types, will remove those element types from the string.

As you could imagine this is a very very simple function, but I wanted to get opinions on speed, functionality, and any other comments anyone can come up with that can improve this function.

<?

    $str = <<<STRING
        Chocolate is very
Chocolate
!
        England is very
City
!
        England is my
city

        England is my
city

        England is my city
        Name

STRING;

    echo htmlentities(removeTags($str, array("b", "div", "span")));

    function removeTags($str, $tags) {

        $tagsString = "";
        foreach($tags as $key => $v) {
            $tagsString .= $key == count($tags)-1 ? $v : "{$v}|";
        }

        $patterns = array("/(<\s*\b({$tagsString})\b[^>]*>)/i", "/(<\/\s*\b({$tagsString})\b\s*>)/i");
        $output = preg_replace($patterns, "", $str);

        return $output;

    }

?>

Alright!  You made me do it.  I'm posting an answer :)

Parsing arbitrary HTML via regular expressions is nearly impossible.  If you were using this on HTML code that you control yourself, it is certainly possible, because you can make sure that all of the edge cases never happen.  However, if you are going to set this loose on arbitrary HTML from the internet, you will find that it fails to work in a number of cases.  Your use case is a little simpler because you are just trying to remove the tags themselves (and not their contents), but even still it can be surprisingly tricky.  You probably need a straight-up HTML parser.  There are a bajillion of them for PHP.  Other than the easy ones I mentioned in my initial comment, here are some more variations that I think will completely sink your current code.  I have actually seen this first one in use on the intertubes: it is technically valid HTML:

Hover me

Another good one: your new regular expression allows for more flexibility in the tag contents at the expense of tag specificity.  In other words, I'm pretty sure that if you use your script to try to remove  tags, you will also end up removing
 tags.

These, and the examples in my initial comment, are some exceptions I came up with just off the top of my head.  In contrast, the internet cumulatively has a bajillion hours experience writing hard-to-parse HTML strings.  Sure, your code might even work 90% of the time, but if you stick with regular expressions it will definitely fail on a regular basis.  It's up to you to decide if the failure rate is low enough.

Especially important: If you are trying to use this as a security tool then definitely don't.  It is nowhere near reliable enough.  Sorry.  It's not that your algorithm isn't well thought out.  It's just that HTML is a full dialect that needs an actual parser: regular expressions just aren't meant for this kind of thing.  It's like trying to build an actual house out of toothpicks.

See this similar question/answer:

Regex to remove inline javascript from string

I know this is not an answer regarding code quality, but instead of re-inventing the wheel, check this library for cleaning user inputted HTML:

http://htmlpurifier.org/


"Time Conversion" Python implementation Problem Statement

  You are given time in AM/PM format. Convert this into a 24 hour format.

  Note Midnight is \$ 12:00:00AM \$ or \$ 00:00:00 \$ and 12 Noon is \$ 12:00:00PM. \$

Input Format

  Input consists of time in the AM/PM format i.e. hh:mm:ssAM or hh:mm:ssPM
  where
  \$ 01 \le hh \le 12 \$,
  \$ 00 \le mm \le 59 \$,
  \$ 00 \le ss \le 59 \$

Output Format

  You need to print the time in 24 hour format i.e. hh:mm:ss
  where

  \$ 00 \le hh \le 23 \$,
  \$ 00 \le mm \le 59 \$,
  \$ 00 \le ss \le 59 \$

Sample Input

  \$ 07:05:45PM \$

Sample Output

  \$ 19:05:45 \$

Solution

class AbsTime(object):

    def __init__(self, hh, mm=0, ss=0, pm=False):
        self.hh = hh
        self.mm = mm
        self.ss = ss
        self.pm = pm

    def add(self, time):
        self.hh += time.hh
        self.mm += time.mm
        self.ss += time.ss

        if self.ss >= 60:
            self.ss -= 1
            self.mm += 1
        if self.mm >= 60:
            self.mm -= 1
            self.hh = self.hh % 24
        return self

    def midnight(self):
        return not self.pm and str(self) in ['00:00:00', '12:00:00']

    def noon(self):
        return self.pm and str(self) == '12:00:00'

    def __str__(self):
        return "{0:02d}:{1:02d}:{2:02d}".format(self.hh, self.mm, self.ss)

    def get(self):
        if self.midnight():
            return AbsTime(0)
        if self.noon():
            return AbsTime(12)
        if self.pm:
            if self.hh == 12:
                hh = self.hh
            else:
                hh = self.hh + 12
            return AbsTime(hh, self.mm, self.ss)
        else:
            return AbsTime(self.hh % 12, self.mm, self.ss)

    @classmethod
    def create_from_string(cls, time):
        pm = True if time[-2:] == 'PM' else False
        hh, mm, ss = map(int, time[:-2].split(':'))
        return cls(hh, mm, ss, pm)

def main(time):
    if time == '00:00:00':
        return time

    abstime = AbsTime.create_from_string(time)
    return abstime.get()

if __name__ == '__main__':
    TIME = raw_input().strip()
    print main(TIME)
    #print main('00:00:00')   #00:00:00
    #print main('12:00:00PM') #12:00:00
    #print main('12:00:00AM') #00:00:00
    #print main('02:00:00PM') #14:00:00
    #print main('02:00:00AM') #02:00:00
    #print main('11:59:00AM') #11:59:00
    #print main('12:59:00PM') #12:59:00
    #print main('01:00:00PM') #13:00:00
    #print main('11:59:59PM') #23:59:59
    #print main('12:59:59AM') #00:59:59

It really took me a while to do this simple solution, its fast when we do just structural programming but once I thought to step into OOP world things really got confusing. How can I improve this design?

Using an internal representation of time that is as simple as possible would simplify your work. For example, using internally seconds since midnight, the add method could become

def add(self, other):
    self.seconds = (self.seconds + other.seconds) % SECONDS_IN_DAY

You could just use strptime and strftime from the time module to do this:

current_time = time.strptime(time_string, "%I:%M:%S%p")
time_formatted = time.strftime("%H:%M:%S", current_time)


Lazy generator of strings in lexicographical order I needed to write a Python generator that lazily generates, in lexicographical order, strings composed of a certain alphabet (e.g. lowercase English letters).
My first thought was to make an infinite generator, but an infinite iterator would be pretty useless because it would just generate strings composed of only the character a. This is because the lexicographical ordering of strings is not a well-order; it can be thought of as composed of an infinite sequence of infinitely nested sequences: (a, (aa, ...), (ab, ...), ...), (b, (ba, ...), (bb, ...), ...), ... The generator would never reach ab since it has an infinite amount of predecessors.
Thus I went for limiting the maximum length of the strings. I.e., the full specification is a generator that lazily generates all strings in a given alphabet of up to a certain length in lexicographical order. E.g., for a maximum length of 3 with ASCII lowercase letters, it should generate, in this order: "", "a", "aa", "aaa", "aab", ..., "aaz", "ab", "aba", ..., "zzz".
The solution I came up with is elegant in the abstract; it uses the intrinsic recursive relationship of lexicographical ordering: if you take the set of all strings—including infinite strings—and remove the first character from each, you're still left with the set of all strings. But it's probably not very efficient in practice, as for each iteration it uses Python's string concatenation operation + \$m\$ times to build a string of length \$m\$ (\$m - 1\$ times in between characters plus the "terminating" empty string, as you'll see below), and strings are immutable so copies are made at every intermediate step, resulting in \$O(m^2)\$ time complexity at each iteration.
Here is my solution:
import string

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    yield ""
    if max_length == 0: return
    for first in alphabet:
        for suffix in lexstrings(max_length - 1, alphabet=alphabet):
            yield first + suffix

Example:
>>> g = lexstrings(max_length=3, alphabet="ab")
>>> list(g)
['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

This implementation also "supports" the infinite version by supplying a negative maximum length:
>>> g = lexstrings(-1)
>>> next(g)
''
>>> next(g)
'a'
>>> next(g)
'aa'
>>> next(g)
'aaa'
...

Some benchmarking confirms a single iteration of this is quadratic in terms of the string size. Here is a plot of execution time for generating a string of maximum length (in a single iteration) vs the maximum length:

The code to generate this plot using perfplot follows. (I modified the order of generation so that the first iteration yields a max-length string.)
import string
import perfplot
import sys

import numpy as np

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    if max_length == 0:
        return
    for first in alphabet:
        for suffix in lexstrings(max_length - 1, alphabet=alphabet):
            yield first + suffix
    yield ""

n_range = np.linspace(1, sys.getrecursionlimit() - 500)
benchmark = perfplot.bench(
    setup=lambda n: n,
    kernels=[
        lambda n: next(lexstrings(n)),
    ],
    labels=[
        "lexstrings",
    ],
    n_range=n_range,
    xlabel="maximum string length",
    title="Single iteration (max-length string)",
    target_time_per_measurement=0.1,
    equality_check=None,
)

benchmark.show(logx=False, logy=False)

It's a great question, and the only improvements I can see are superficial ones:

Your method has incomplete type hints. alphabet should be Iterable[str], and it should return -> Iterable[str] as well.
PEP8 discourages multi-statement lines (your return).

Otherwise, you should reconsider making this a recursive implementation. I see that you were careful to check sys.getrecursionlimit() in your test code, so you're already aware of the fact that this will break given sufficient depth. Python also does not have tail optimization so an iterative implementation will potentially yield performance improvements.

First... go read itertools. It's in the standard library, you're reinventing some wheels here. Note that there's a long 'recipes' section at the bottom.
In particular, the strings on a given alphabet of length n is just itertools.combinations_with_replacement(alphabet, r).
import itertools

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    return itertools.chain(itertools.combinations_with_replacement(alphabet, r)
                           for r in range(0, max_length+1))

or an abstract infinite one:
import itertools

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    return itertools.chain(itertools.combinations_with_replacement(alphabet, r)
                           for r in itertools.count())

In the future, you should also know about python 3.3 introducing yield from.
Edit: Last, if it's not lexicographical order, rename it from lexstrings.
Edit 2: Oh, looks like your original does preserve order. Keep my tips and ignore my (different order) rewrite.


Storing passwords in a database I just wrote this function and am wondering if it's secure enough for storing passwords in a database:

public static function hash($salt, $str) {
    $salt = md5($salt);
    $salt = '$2y$12$HfuPgoDY94nHJssqQeVLmH' . $salt . '$';

    return crypt($str, $salt);
}

Yes
Blowfish is a great algorithm for storing passwords, it makes generating a hash slow such that brute force attacks are unviable. It's also php's recommended means of storing passwords.
But
The salt for blowfish is supposed to be:

22 digits from the alphabet "./0-9A-Za-z".

This applies to the salt string which in the question is:
'HfuPgoDY94nHJssqQeVLmH' . $salt . '$'

That's 22 chars + 32 chars + '$', which is 65 characters long and contains an illegal '$'. The consequence of that is that the salt actually used is a fixed string, the first 22 characters and is the same for all generated hashes.
The salt should be random, and for example you could use something as simple as this:
$salt = '$2y$12$' . substr(md5(time()), 0, 22);
return crypt($str, $salt);

Note however that this code is simple for brevity and can be significantly improved upon since the salt will only be made up of hexadecimal (0-9a-f) characters. Here's an example implementation that could be used to generate a better salt.
Make cost a parameter
A cost of 12 is fine for passwords, but you may wish to make it a parameter so that e.g. unit tests are not needlessly slow whenever they generate a password.

No

If you can't pass hash length, salt length, and work units (iterations) into the hash function, you have no way of keeping up with faster CPU speeds.

The salt should be at least 64 characters, and it should be generated using a cryptographically secure random number generator. It needs to be unique for each hash. It should be the same size as the hash. Any less is too little entropy. Any more is wasted. Always pass work units into key stretching algorithms like bcrypt, PBKDF2, etc... That way you can increase the work required as CPUs get faster.

In 2014, a PBKDF2/HMAC+Sha1 algorithm needs 128,000 work units. Double the work every 2 years.

You need to store the work units with the hash so that you know how many to use for comparison, and you'll know to ask the users to select a new password when its time to upgrade their hash.

Addressing comments (there wasn't enough room in the comments field):

The salt should be at least 64 characters because the hash should be at least 64 characters. The salt should be the same size as the hash in order to prevent attackers from creating lookup tables for every possible salt. This is why it's a very bad idea to use a username as a salt -- especially now that we're fighting off attackers with enormous amounts of storage, CPU, and memory space compared to just a few years ago. In other words, having an equal length salt guarantees that generating tables for each salt (combining tables + dictionary attacks of the most common passwords) would take at least as long as a brute force attack.

The minimum length of 64 characters is the current recommendation (for the year 2014, 2013 is almost over) in response to changing CPU speeds. The recommendation of 22 was first made years ago -- CPUs double in speed every year, and current botnets exist with over 90,000 nodes, capable of generating billions of salts per second. Super cheap supercomputing clusters can be built today for less than $2k. The old standards just don't cut it anymore.

Salts need to be generated by a CSRNG in order to prevent collisions. Pseudo-random generators that are not CSRNGs are notoriously bad at that, often generating a collision within a few thousand hashes. For sites with hundreds of thousands or millions of users, that's not an acceptable rate.

It's important to prevent collisions because a collision means that the same tables can be used to attack multiple hashes at the same time.

  Work units = cost parameter?

Work units = cost parameter, yes, but the original question is about a function which does not take a cost parameter. The cost is hard-coded in the function.

  Sha1+HMAC is inappropriate

No, "HMACs are substantially less affected by collisions than their underlying hashing algorithms alone." Sha1+HMAC is far more secure than Sha1, and it is a currently accepted standard for password hashing.

  and PBKDF2 is weaker than bcrypt so overall..

No, it isn't. Once you go over 60 characters or so, the cost of PBKDF2 trumps bcrypt by orders of magnitude.

  It's ubiquitous and time-tested with an academic pedigree from RSA Labs, you know, the guys who invented much of the cryptographic ecosystem we use today. Like bcrypt, PBKDF2 has an adjustable work factor. Unlike bcrypt, PBKDF2 has been the subject of intense research and still remains the best conservative choice.
  There has been considerably less research into the soundness of bcrypt as a key derivation function as compared to PBKDF2, and simply for that reason alone bcrypt is much more of an unknown as to what future attacks may be discovered against it.

In other words, bcrypt is overrated. Especially if you think it's better than PBKDF2.

Source: http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html


DAO for happenings registration website As a learn-by-doing project to learn Java webapps, I'm creating a website for registering and displaying happenings using JSP/Servlets, Apache Tomcat server, JDBC and a MySQL database.

I use JSP for views, Servlets for controller functionality and business logic, and I've created ONE DBManager.java class (my only DAO) to abstract SQL statements from my Servlets and JSPs. In my Servlets, I use the DBManager class by declaring a new instance and calling its public methods.

For instance:

DBManager dbm = new DBManager();
Boolean userIsUpdated = dbm.updateUserInDB(user);

My DAO looks briefly like this:

public class DBManager {

    final String DATABASE_URL = "NOPE, I won't give you this one ;)";
    Connection connection = null;
    PreparedStatement pstmt = null;

    public DBManager() {
        //Nothing in constructor yet.
    }

    public ArrayList<Happening> getAllActivatedHappenings() {
        //code removed for readability
    }

    public User logInAndGetUserByEmailAndPassword(String email, String password) {
        //code removed for readability
    }

    public User insertUserIntoDB(User user) {
        //code removed for readability
    }

    public boolean updateUserInDB(User user) {
        //code removed for readability
    }

    public boolean insertHappeningIntoDB(Happening happening) {
        //code removed for readability
    }

    public boolean deleteHappeningFromDB(int happeningId, int userId) {
        //code removed for readability
    }

    public ArrayList<HappeningType> getAllHappeningTypes() {
        //code removed for readability
    }

    public ArrayList<Happening> getAllHappeningsByUserId(int userid) {
        //code removed for readability
    }

    public byte[] getPhotoByHappeningId(int happeningId, String imageType) {
        //code removed for readability
    }

    public Map<Integer, String> getCountiesMap() {
        //code removed for readability
    }

    public Boolean userIsHappeningOwner(int userId, int happeningId) {
        //code removed for readability
    }

    public Happening getHappeningByHappeningId(int happeningId) {
        //code removed for readability
    }

    public boolean updateHappening(Happening happeningDummy, String updateImage) {
        //code removed for readability
    }

    public ArrayList<Happening> getFilteredActivatedHappenings(HttpServletRequest request) {
        //code removed for readability
    }

    public boolean activateHappening(int happeningId) {
        //code removed for readability
    }

    public boolean updateEmailNotificationForUser(User user, String emailnotificationhappeningtypeids, String emailnotificationcountyids) {
        //code removed for readability
    }

    public User getUserByEmail(String email) {
        //code removed for readability
    }
}

As you can see, my DAO handles quite a lot of different transfer objects (happenings, users, cities, happening types etc.). Should I break this DAO into several smaller DAO classes (like HappeningDAO, UserDAO, etc.)? Any other reasons for doing this than readability?

Also, is this approach thread-safe as long as I declare a new instance of DBManager within my doGet/doPost methods in the servlets?

Just a quick note: ArrayList<...> return types should be simply List<...>. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

Unless it is a professional project, I suggest, for study before beginning a long work, you look before in Quick download db4o (you can load 8.1)

Inside zip file, you have doc directory with a tutorial for learn, and a reference for browser with index and search tool (very complete and uptodate doc).

First work with EmbeddedObjectContainer, have a look to

SODA query,
Transparent Activation and Transparent Persistence to understand OODB powerfulness,
After you can configure a Server.
Don't forget OME the integrated manager, it can be a model for your project.
You will forget 'select/join' SQL burden for a light/fast 'choose and navigate' in OODB.
Do not imagine table for data but graph : some fields are ActivatableArry[Set|List|..] linking instances, as internal indexes.

Have in mind that db4o can be migrated to Versant professional for huge databases.

If you are aware, this will take few time, and with a couple of hour you will be able to see OODB functionnality, then you will be able to test some tools.

You can try to work with JSON (Vaadin) for Web with Tomcat.
If you want to go further look Jease to avoid some pitfalls, and more stressed web conections

All those tools are Eclipse compatible

So you will be able if it is worth to continue in your first way or choose another perspective, but SGBDR will give you more problems, more works, more issues, and SQL is not powerfull for OO code, even if Hibernate is powerfull it is complicated, SQL have no future for OO languages, and JSON is more now mature.


Generate strings of random characters I've a function to generate random characters from a set of alphabets. This function would be called multiple times and thus I'm trying to make it use same set of variables, i.e. have same seed so that strings don't repeat as long as possible.

#include <iostream>
#include <random>
#include <string>

std::string generateRandomChar(const unsigned int _len)
    {
        std::string result;
        result.reserve(_len);

        static constexpr char alphanum[] = "0123456789"
                                           "abcdefghijklmnopqrstuvwxyz"
                                           "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, 61);

        for (int i = 0; i < _len;
            result += (alphanum[dis(gen)]);
        }
        return result;
    }

int main(){
    for(int i = 0; i < 10; ++i){
        std::cout << generateRandomChar(10) << std::endl;
    }
}

Unfortunately I don't have any expertise with C++11 <random> functions and I was only using srand and friends earlier, so I might be making lots of mistakes here. Currently it works and generates tons of strings without repeating, but I'm sure I could make either of:

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 61);

static variable too, so that it isn't calculated each time the function is called because that would be waste right?

So which one should be static here? Are there any mistakes/improvements that you see here?

Ideone

Wherever you place static will change the behaviour of your program tremendously. In the end, we have \$2^3 = 8\$ combinations, so let's check some of them.

A random_device may fall back to a pseudorandom engine if no hardware-device for random numbers is available. If you don't use static on random_device in this case, all your strings may end up the same, as the pseudorandom engine may get initialized with a implementation defined fixed seed, e.g.

 std::random_device a;
 std::random_device b;
 assert(a() == b());  // worst case if no hardware-device or a low-effort implementation is used

In this case, a mt19937 would get seeded with the same value all the time, and we end up with the same string in every call. This changes if either mt19937 or random_device is static, and may change if dist is static, as a uniform_int_distribution can use several calls to the generator for its internal state.

Of course, if mt19937 is static, you may as well change random_device to a static variant, as it will get evaluated only once. This is the closest your get to a single srand() call at the start of your program. Your uniform_int_distribution still loses its internal state, though.

In the end, it depends on whether we want two generateRandomChar calls to correlate to each other. If they shall not correlate at all, we need to reseed our PRNG with a new non-deterministic number and cannot use static at all.

Or, to put it in another way: if we use static for all three values, then

generateRandomChar(10) + generateRandomChar(10)

is the same as
    generateRandomChar(20)
If we use static on mt19937, then both may be the same, depending on both _len and dist.

Either way, if you want to have more control over the generation, you can just provide a generator in your function:

template <typename Generator>
std::string generateRandomChar(Generator & gen, const unsigned int _len)
    {
        ...
    }

Same holds for the distribution.

Other than that, I'd use sizeof instead of 61 to make sure that I don't accidentally change the pool of possible characters without changing the number bounds in dist's constructor:

static constexpr char alphanum[] = "0123456789"
                                   "abcdefghijklmnopqrstuvwxyz"
                                   "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, sizeof(alphanum) - 1);

I think you should create a separate wrapper class for this occasion. I used the following:

#include <random>
class randomStreamUniformInt {
public:
    explicit randomStreamUniformInt(int lower_bound, int upper_bound)
    : mt(rand()), uniform_dist(lower_bound, upper_bound) {}
    explicit randomStreamUniformInt(int lower_bound, int upper_bound, double seed)
    : mt(seed), uniform_dist(lower_bound, upper_bound) {}

    int operator ()(void) { return uniform_dist(mt); }
private:
    std::mt19937_64                     mt;
    std::uniform_int_distribution<>     uniform_dist;
};

You can obviously extend it to use your prefered generator. Then you should either pass this per reference to your function or create a class with generateRandomChar as a method.