Global data singleton I need a global data in my application. My application uses several threads to access and add items to my global variable. The global variable is a ConcurrentDictionary I choose to ensure data is added to the variable. What do you think about my approach?

public class GlobalData
{
    private static volatile GlobalData instance;
    private volatile ConcurrentDictionary<string, object> _data = new ConcurrentDictionary<string, object>();
    private static object syncRoot = new Object();

    public static GlobalData Instance
    {
        get
        {
            if (instance == null)
            {
                lock (syncRoot)
                {
                    if (instance == null)
                        instance = new GlobalData();
                }
            }

            return instance;
        }
    }

    public void Add(string id, object obj)
    {
        _data.TryAdd(id, obj);
    }

    public object Get(string id)
    {
        object value;
        _data.TryGetValue(id, out value);
        return value;
    }
}

Singletons are evil
Even if you do want to use it, use Lazy<T> instead of manually doing double-checked locking

Best solution would be to leverage IoC container to inject dependencies you need.

Do not use singleton

If you dare...

... and you are on .NET 4.0 use Lazy<T>


Takes a list and return a dict of distinct values pointing to a list of index locations of each value I came up with a way to get a dict of distinct elements in a list pointing to the location of each element; it works, but I feel pretty awful about this code, it's very ugly. Is there a more natural/pythonic way to do this?
from itertools import groupby
sample_data = [1,2,3,3,1,0,5]
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in itertools.groupby(list(enumerate(dta)), lambda x:x[1])}
print(give_groups(sample_data))

{1: [4], 2: [1], 3: [2, 3], 0: [5], 5: [6]}

The performance is also bad.
Created this alternate that does work, but is kinda slow:
def alt_grouping(dta):
    retdict = defaultdict(list)
    for position, item in enumerate(dta):
        retdict[item].append(position)
    return retdict

The first try :
from itertools import groupby
sample_data = [1,2,3,3,1,0,5]
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in itertools.groupby(list(enumerate(dta)), lambda x:x[1])}
print(give_groups(sample_data))

Have to be corrected to:
from itertools import groupby # --> you don't have to call itertools.groupby just groupby
sample_data = [1,2,3,3,1,0,5]
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in groupby(list(enumerate(dta)), lambda x:x[1])}
print(give_groups(sample_data))

But seems to be replacing items and not appending them, don't see why.

In the alt_grouping function, defaultdict doesn't exists:
def alt_grouping(dta):
    retdict = defaultdict(list) # don't know what is defaultdict
    for position, item in enumerate(dta):
        retdict[item].append(position)
    return retdict

Then I found a solution that works, it's based on your function alt_grouping:
sample_data = [1,2,3,3,1,0,5]

retdict = {}
for position, item in enumerate(sample_data):
        if item in retdict.keys():
            retdict[item].append(position)
        else:
            retdict[item] = [position]

print(retdict)

I take some execution & times testing in the first try and my alternative with a bigger sample a list of two range(100).
Sample Data:
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76,
77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

First Function:
{0: [100], 1: [101], 2: [102], 3: [103], 4: [104], 5: [105], 6: [106], 7: [107], 8: [108], 9: [109], 10: [110], 11: [111], 12: [112], 13: [113], 14: [114], 15: [115], 16: [116], 17: [117], 18: [118], 19: [119], 20: [120], 21: [121], 22: [122], 23: [123], 24: [124], 25: [125], 26: [126], 27: [127], 28: [128], 29: [129], 30: [130], 31: [131], 32: [132], 33: [133], 34: [134], 35: [135], 36: [136], 37: [137], 38: [138], 39: [139], 40: [140], 41: [141], 42: [142], 43: [143], 44: [144], 45: [145], 46: [146], 47: [147], 48: [148], 49: [149], 50: [150], 51: [151], 52: [152], 53: [153], 54: [154], 55: [155], 56: [156], 57: [157], 58: [158], 59: [159], 60: [160], 61: [161], 62: [162], 63: [163], 64: [164], 65: [165], 66: [166], 67: [167], 68: [168], 69: [169], 70: [170], 71: [171], 72: [172], 73: [173], 74: [174], 75: [175], 76: [176], 77: [177], 78: [178], 79: [179], 80: [180], 81: [181], 82: [182], 83: [183], 84: [184], 85: [185], 86: [186], 87: [187], 88: [188], 89: [189], 90: [190], 91: [191], 92: [192], 93: [193], 94: [194], 95: [195], 96: [196], 97: [197], 98: [198], 99: [199]}
--- 0.001995563507080078 seconds ---
My Function:
{0: [0, 100], 1: [1, 101], 2: [2, 102], 3: [3, 103], 4: [4, 104], 5: [5, 105], 6: [6, 106], 7: [7, 107], 8: [8, 108], 9: [9, 109], 10: [10, 110], 11: [11, 111], 12: [12, 112], 13: [13, 113], 14: [14, 114], 15: [15, 115], 16: [16,
116], 17: [17, 117], 18: [18, 118], 19: [19, 119], 20: [20, 120], 21: [21, 121], 22: [22, 122], 23: [23, 123], 24: [24, 124], 25: [25, 125], 26: [26, 126], 27: [27, 127], 28: [28, 128], 29: [29, 129], 30: [30, 130], 31: [31, 131], 32: [32, 132], 33: [33, 133], 34: [34, 134], 35: [35, 135], 36: [36, 136], 37: [37, 137], 38: [38, 138], 39: [39, 139], 40: [40, 140], 41: [41, 141], 42: [42, 142], 43: [43, 143], 44: [44, 144], 45: [45, 145], 46: [46, 146], 47:
[47, 147], 48: [48, 148], 49: [49, 149], 50: [50, 150], 51: [51, 151], 52: [52, 152], 53: [53, 153], 54: [54, 154], 55: [55, 155], 56: [56, 156], 57: [57, 157], 58: [58, 158], 59: [59, 159], 60: [60, 160], 61: [61, 161], 62: [62,
162], 63: [63, 163], 64: [64, 164], 65: [65, 165], 66: [66, 166], 67: [67, 167], 68: [68, 168], 69: [69, 169], 70: [70, 170], 71: [71, 171], 72: [72, 172], 73: [73, 173], 74: [74, 174], 75: [75, 175], 76: [76, 176], 77: [77, 177], 78: [78, 178], 79: [79, 179], 80: [80, 180], 81: [81, 181], 82: [82, 182], 83: [83, 183], 84: [84, 184], 85: [85, 185], 86: [86, 186], 87: [87, 187], 88: [88, 188], 89: [89, 189], 90: [90, 190], 91: [91, 191], 92: [92, 192], 93:
[93, 193], 94: [94, 194], 95: [95, 195], 96: [96, 196], 97: [97, 197], 98: [98, 198], 99: [99, 199]}
--- 0.0009963512420654297 seconds ---

Seems to be pretty similar then I try with list(range(10000)):
First Function:
--- 0.015984535217285156 seconds ---
My Function:
--- 0.005953311920166016 seconds ---

Here we see a difference.
There is the code for tests - EDITED :
import time
sample_data = list(range(1000000)) + list (range(1000000))
# print ("Sample Data:\n",sample_data, "\n")

print("First Function:")
start_time = time.time()

from itertools import groupby
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in groupby(list(enumerate(dta)), lambda x:x[1])}
# print(give_groups(sample_data))
give_groups(sample_data)

print("--- %s seconds ---" % (time.time() - start_time))

print("My Function:")
start_time = time.time()
retdict = {}
for position, item in enumerate(sample_data):
        if item in retdict.keys():
            retdict[item].append(position)
        else:
            retdict[item] = [position]

print("--- %s seconds ---" % (time.time() - start_time))

print("Other Function:")

from collections import defaultdict

start_time = time.time()
def dict_with_indices(dta):
    """ Returns a dictionary with a list of indices for each item in dta

    Args:
        dta (list): list of data to be indexed

    Returns:
        dict: dict with list of indices as values

    Examples:
        >>> dict_with_indices([1,2,3,3,1,0,5]]
        {1: [0, 4], 2: [1], 3: [2, 3], 0: [5], 5: [6]}
    """
    result = defaultdict(list)
    for idx, val in enumerate(dta):
        result[val].append(idx)
    return result

dict_with_indices(sample_data)

print("--- %s seconds ---" % (time.time() - start_time))

Times for this new tests:
First Function:
--- 1.9537413120269775 seconds ---
My Function:
--- 0.7061352729797363 seconds ---
Other Function:
--- 0.6053769588470459 seconds ---

New Solution seems to be the better one, thanks to @agtoever :
from collections import defaultdict

    def dict_with_indices(dta):
        """ Returns a dictionary with a list of indices for each item in dta

        Args:
            dta (list): list of data to be indexed

        Returns:
            dict: dict with list of indices as values

        Examples:
            >>> dict_with_indices([1,2,3,3,1,0,5]]
            {1: [0, 4], 2: [1], 3: [2, 3], 0: [5], 5: [6]}
        """
        result = defaultdict(list)
        for idx, val in enumerate(dta):
            result[val].append(idx)
        return result

    dict_with_indices(sample_data)

#This is simple understandable code

alpha=['a','b','c','d','e']#list
dic={}#dict

alpha.sort(reverse=True)
length=len(alpha)

for key in range (length):
    value=alpha.pop()
    dic[key]=value

print(dic)


Determining optimal weight lifting bar configuration This program is meant to take two weights and return the best way to load a barbell for two people using different weights, so you don't have to keep changing out super heavy weights. I also made functionality for one person to use it to calculate the most efficient way to load the bar (least # of plates used).

If you notice, user_one() and user_two() are mostly the same code, with minor adjustments. perfect_combo() also shares some of the same.  I feel like there's a way to cut down on the code in this program.

weights=[100, 45, 35, 25, 10, 5, 2.5]
bar_weight = 45
prog_select = int(input('How many people on this bar?'
'(enter 1 or 2) '))
if prog_select == 1:
    target_weight = int(input('Enter weight: '))
elif prog_select == 2:
    target_weight = int(input('Enter first weight: '))
    target_weight1 = int(input('Enter second weight: '))

def user_one():
    nweights = []
    remaining = target_weight - bar_weight
    for  i, weight in enumerate(weights):
        if int(remaining / weight) % 2 == 0:
            nweights.append(int(remaining/ weight))
        else:
            nweights.append(int(remaining/ weight) - 1)
        remaining = remaining - nweights[i]*weights[i]
        if remaining == 0:
            break

    listweights=zip(nweights, weights)
    print(f'{bar_weight}lb bar')
    print(f'{target_weight}lbs')

    for weight in listweights:
        if weight[0] >= 2:
            print(f"{weight[0]} | {weight[1]}'s")

    if remaining !=0:
        print(f'the correct weight combination cannot be found,'
              f'the remaining weight is: {remaining} pound')

def user_two():
    nweights = []
    remaining = target_weight1 - bar_weight
    for  i, weight in enumerate(weights):
        if int(remaining / weight) % 2 == 0:
            nweights.append(int(remaining/ weight))
        else:
            nweights.append(int(remaining/ weight) - 1)
        remaining = remaining - nweights[i]*weights[i]
        if remaining == 0:
            break

    listweights=zip(nweights, weights)
    if prog_select == 1:
        print(f'{target_weight1}lbs')
    else:
        print(f'{bar_weight}lb bar')
        print(f'{target_weight1}lbs')
    for weight in listweights:
        if weight[0] >= 2:
            print(f"{weight[0]} | {weight[1]}'s")

    if remaining !=0:
        print(f'the correct weight combination cannot be found,'
              f'the remaining weight is: {remaining} pound')

def perfect_combo():
    nweights = []
    remaining = (target_weight - target_weight1)

    print("Add " + str(remaining) + "lbs for first weight")

    for  i, weight in enumerate(weights):
        if int(remaining / weight) % 2 == 0:
            nweights.append(int(remaining/ weight))
        else:
            nweights.append(int(remaining/ weight) - 1)
        remaining = remaining - nweights[i]*weights[i]
        if remaining == 0:
            break

    listweights=zip(nweights, weights)

    for weight in listweights:
        if weight[0] >= 2:
            print(f"{weight[0]} | {weight[1]}'s")
    if remaining !=0:
        print(f'the correct weight combination cannot be found,'
              f'the remaining weight is: {remaining} pound')

# Run the program

if prog_select == 1:
    user_one()
elif prog_select == 2:
    remaining = (target_weight - target_weight1)
    if remaining > 99:
        print("You might want to use seperate bars...")
    else:
        user_two()
        perfect_combo()
else:
    print("That's too many peeps on one bar!")

The layout of your program is non-standard.  You have:

main program part 1
function definitions
main program part 2

Keep your main program together, don't split it up by adding functions in the middle, at least, not without a compelling reason.

There is minimal error checking in the program.  If the target weight is less than the bar weight, this is not reported.

    for  i, weight in enumerate(weights):
        if int(remaining / weight) % 2 == 0:
            nweights.append(int(remaining/ weight))
        else:
            nweights.append(int(remaining/ weight) - 1)
        remaining = remaining - nweights[i]*weights[i]
        if remaining == 0:
            break

    listweights=zip(nweights, weights)

This code is duplicated in user_one(), user_two() and perfect_combo().  You should move this into a function.

The code computes the number of a specific weight, and then adds the number to a list if it is even, or 1 less if it is odd.  Presumably, this is because the weights have to be added in pairs, one on each side of the bar, but this is never spelt out.

Finally, the list is zipped with the original list of weight options, to create pairs of counts and weights.

Let's create the function which does this computation, but let's make it more general.  You might have different bar types, say a light weight bar and a heavy weight bar.  The light weight bar would be lighter, and perhaps uses a different set of weights, but the algorithm would remain the same.  So the available weights should be passed in:

def weights_in_pairs(added_weight, available_weights):

    """Compute and return list of numbers and sizes of weights to
    form the desired additional weight for bar-bell.  Also returns any
    excess weight that could not be added."""

    weights = []
    remaining = added_weight
    for weight in available_weights:
        pairs = int(remaining / (2*weight))
        if pairs  > 0:
            weights.append((pairs * 2, weight))
            remaining -= 2 * pairs * weight

    return weights, remaining

Instead of dealing with even/odd numbers, we double the weight and compute the number of pairs that can be added add.  Instead of zipping at the end, we add the (count, weight) tuple to the weights list; this allows us to omit the zero counts, to simplify printing later

    for weight in listweights:
        if weight[0] >= 2:
            print(f"{weight[0]} | {weight[1]}'s")

    if remaining !=0:
        print(f'the correct weight combination cannot be found,'
              f'the remaining weight is: {remaining} pound')

This code is also duplicated between user_one(), user_two() and perfect_combo().  Again, we'll move this into a function.

def print_weights(weights, remaining):

    """Print out the weights to be added to the bar-bell,
    and the amount of un-added weight, if necessary."""

    for n, weight in weights:
        print(f"{n} | {weight}'s")

    if remaining != 0:
        print(f'the correct weight combination cannot be found,'
              f'the remaining weight is: {remaining} pound')

Note that the for loop immediate extracts the tuple into two variables, with the names n and weight.  This allows us to use these named quantities in the body of the loop, instead of indexes like weight[0] and weight[1] where the reader will have to look elsewhere to determine what was stored in the different indexes.

Also, since we skipped added the zero-count weights, we didn't need the if weight[0] >= 2: statement.

We can combined the above two functions, to compute and print out the information displayed by user_one() and user_two().  Again, we'll pass in arguments for the desired weight, the bar weight, and the available weights:

def print_bar_configuration(target_weight, bar_weight, weights):

    """Compute and print bar-bell configuration for given weights."""

    listweights, remaining = weights_in_pairs(target_weight - bar_weight, weights)

    print(f'{bar_weight}lb bar')
    print(f'{target_weight}lbs')

    print_weights(listweights, remaining)

With the above functions, perfect_combo() can be simplified:

def perfect_combo(heavy_weight, light_weight):

    """Compute and print optimal additional weight configuration."""

    weight_difference = heavy_weight - light_weight

    print(f"Add {weight_difference}lbs for heavier weight")

    listweights, remaining = weights_in_pairs(weight_difference, weights)
    print_weights(listweights, remaining)

Note: This raise the question of "what happens if the first weight was lighter than the second?"  Perhaps your program should mention that requirement, and test for it.  Or adapt the reversed data input.

Using the above functions, we can simplify the main program, moving and combining the code at the top with the code at the bottom.  Also, renaming odd variables like target_weight1 to something more meaningful:

if prog_select == 1:
    target_weight = int(input('Enter weight: '))
    print_bar_configuration(target_weight, bar_weight, weights)
elif prog_select == 2:
    heavy_weight = int(input('Enter heavier weight: '))
    light_weight = int(input('Enter lighter weight: '))

    if heavy_weight - light_weight > 99:
        print("You might want to use separate bars...")
    else:
        print_bar_configuration(light_weight, bar_weight, weights)
        perfect_combo(heavy_weight, light_weight)
else:
    print("That's too many peeps on one bar!")

Because the 'perfect_combo' seems useless in your script, I only implement user1 and user2.

Please note python is a OOP language. The best practice to reduce code reimplement is inheritance.

Hope my code is useful for you to explore python OOP features.

class User:
    weights=(100, 45, 35, 25, 10, 5, 2.5)
    bar_weight = 45
    def __init__(self, target_weight):
        self.target_weight = target_weight
        self.remaining = target_weight - self.bar_weight
    def compute(self):
        remaining = self.remaining
        nweights = []
        weights = self.weights
        for  i, weight in enumerate(weights):
            if int(remaining / weight) % 2 == 0:
                nweights.append(int(remaining/ weight))
            else:
                nweights.append(int(remaining/ weight) - 1)
            remaining = remaining - nweights[i]*weights[i]
            if remaining == 0:
                break

        listweights=zip(nweights, weights)
        print(f'{self.bar_weight}lb bar')
        print(f'{self.target_weight}lbs')

        for weight in listweights:
            if weight[0] >= 2:
                print(f"{weight[0]} | {weight[1]}'s")

        if remaining !=0:
            print(f'the correct weight combination cannot be found,'
                    f'the remaining weight is: {remaining} pound')

if __name__ == "__main__":
    prog_select = int(input('How many people on this bar? (enter 1 or 2) '))
    if prog_select == 1:
        target_weight = int(input('Enter weight: '))
        User(target_weight).compute()

    elif prog_select == 2:
        target_weight = int(input('Enter first weight: '))
        target_weight1 = int(input('Enter second weight: '))
        if target_weight - target_weight1 > 99:
            print("You might want to use seperate bars...")
        else:
            User(target_weight1).compute()
    else:
        raise ValueError('input should be 1 or 2, no other values!!!')


Look over my code for PDO and MVC I'm building this website with PDO and Pattern MVC.  I'm currently working on the login page and would like to know if this structure is correct for MVC pattern.  I'd also like your opinions and advice on this.

For my login view I have:

<form action="test.php" name="loginform" method="post">
    <input type="text" name="login">
    <input type="password" name="password">
    <input type="submit" name="login_submit" value="Se connecter">
</form>

For my login controller I have:

if(isset($_POST['login_submit'])){
    if(!empty($_POST['login']) && !empty($_POST['password'])){
        $auth = new auth();
        $auth->setLogin($_POST['login']);
        $auth->setPassword(md5(sha1($_POST['password'])));
        if(($row = $auth->login('u_login,u_email,u_id_level', 'users', 'u_login', 'u_password'))){
            $_SESSION['back_office'] = array(
                'login' => $row->u_login,
                'email' => $row->u_email,
                'level' => $row->u_id_level
            );
        }else{
            message::showError('Compte non reconnu');
        }
    }else{
        message::showError('Veuillez remplir tous les champs');
    }
}

For my login model I have:

class auth{
    protected $rowUser;
    protected $login;
    protected $password;
    protected $email;

    public function setLogin($login){
        $this->login = $login;
    }
    public function setPassword($password){
        $this->password = $password;
    }
    /**
     * @return array $row
     */
    public function login($fields, $table, $col_login, $col_password){
        $query = Db::getInstance()->prepare('SELECT '.$fields.' FROM '.$table.' WHERE '.$col_login.' = :login AND '.$col_password.' = :password');
        $query->bindValue(':login',$this->login,PDO::PARAM_STR);
        $query->bindValue(':password',$this->password,PDO::PARAM_STR);
        $query->execute();
        if($query->rowCount() > 0){
            $row = $query->fetch();
            return $row;
        }else{
            return false;
        }
        $query->closeCursor();
    }
}

A part of code in auth::login() of method you should move to other class, for example 'db'. Because you class auth has too much responsibility. For example if you want to have dynamic define fields in class auth:

Db class:

class db {
    public function getItem($table, $fields = '*', $conditions = array()) {
        // you code ...
        return $row;
    }
}

Your model:

class auth {
    private $table = 'users';
    private $fields = 'u_login, u_email, u_id_level';
    private $fieldLogin = 'u_login';
    private $fieldPassword = 'u_password';

    public function setTable($value) { $this->table = $value; }
    public function setFields($value) { $this->fields = $value; }
    public function setFieldLogin($value) { $this->fieldLogin = $value; }
    public function setFieldPassword($value) { $this->fieldPassword = $value; }

    public function login() {
        $db = new db();
        return $db->getItem($this->table, $this->fields, array(
            $this->fieldLogin => $this->login,
            $this->fieldPassword => $this->password
        ));
    }
}

This code is more elastic and simpler will be change it.

Just a minor note: I'd reverse some conditions and use guard clauses to make the code flatten.

if(empty($_POST['login']) || empty($_POST['password'])){
    message::showError('Veuillez remplir tous les champs');
    return;
}

$auth = new auth();
$auth->setLogin($_POST['login']);
$auth->setPassword(md5(sha1($_POST['password'])));
if(!($row = $auth->login('u_login,u_email,u_id_level', 'users', 'u_login', 'u_password'))){
    message::showError('Compte non reconnu');
    return;
}
$_SESSION['back_office'] = array(
    'login' => $row->u_login,
    'email' => $row->u_email,
    'level' => $row->u_id_level
);

(You might need to extract this out to a function.)

References:

Replace Nested Conditional with Guard Clauses in Refactoring: Improving the Design of Existing Code by Martin Fowler;
Flattening Arrow Code


Make all additional threads return from a method using Interlocked.Increment I need to ensure a method is executed only by one thread at a time. Contrary to what most of the synchronization primitives do, I don't need other threads to wait, I want them to return from the method immediately if it is already executed by another thread. Additional complexity is that the method uses async/await calls.

I implemented it using Interlocked.Increment. I tested in a simple test scenario and it seems to be working. However, I'm not sure, is it a correct implementation and will it work in all cases? Or maybe there is a simpler way to achieve the same goal?

private int _threadsCount = 0;

public async Task Method()
{
    if (Interlocked.Increment(ref _threadsCount) > 1)
    {
        Interlocked.Decrement(ref _threadsCount);
        return;
    }

    try
    {
        await DoWork();
    }
    finally
    {
        Interlocked.Decrement(ref _threadsCount);
    }
}

Yes, your code should work. Though the first part can be simplified to:

if (Interlocked.CompareExchange(ref _threadsCount, 1, 0) != 0)
{
    return;
}

Or maybe there is a simpler way to achieve the same goal?

You could also use Monitor.TryEnter instead:

private object _lock = new object();

public async Task Method()
{
    if (!Monitor.TryEnter(_lock)
    {
        return;
    }

    try
    {
        await DoWork();
    }
    finally
    {
        Monitor.Exit(_lock);
    }
}


Recursively printing equations I did this program and I need to make sure I did it right. The answers come out to be right but I want to make sure nothing is wrong with the coding.

class RecursiveMethods
{
    RecursiveMethods()          //default constructor
    {
    }

    public int fOf(int x)
    {
        if (x <= 10)                        //the base case
        {
            System.out.println(x + " <= 10, therefore ... f(" + x + ") = -5");
            return -5;
        }
        else
        {
            System.out.println(x + " > 10, therefore ... f(" + x + ") = f(" + x + " - 3) + 2 = f(" + (x -3) + ") + 2");
            return fOf(x-3) + 2;
        }
    }
}

public class RecursionMethodTester
{
    public static void main(String[] args)
    {
        int x;
        RecursiveMethods rMethods = new RecursiveMethods();

        System.out.println("---------------------------------");
        System.out.println("       f(x - 3) + 2    if x >  10");
        System.out.println("f(x) = ");
        System.out.println("       -5              if x <= 10");
        System.out.println("---------------------------------");
        System.out.println();

        x = 20;
        System.out.println("Example 1:  x = " + x);
        System.out.println("f(" + x + ") = " + rMethods.fOf(x));
        System.out.println();

        x = 19;
        System.out.println("Example 2:  x = " + x);
        System.out.println("f(" + x + ") = " + rMethods.fOf(x));
        System.out.println();

        x = 18;
        System.out.println("Example 3:  x = " + x);
        System.out.println("f(" + x + ") = " + rMethods.fOf(x));
        System.out.println();
    }
}

As mentioned by @Cyrille fOf is not a good method name.

I disagree with the use of more comments, if you name your function well enough, you shouldn't need comments.  Comments should be used to explain hard to understand or confusing code, not describe what is going on.

In java the opening { is usually placed at the end of the line where the code block starts.  i.e.

if (somethingIsTrue) {

You can get rid of the else in your fOf function.  It is implied with the return in the if.

You don't need to specify the default constructor.  It does nothing, so it is just clutter.

I'm also not happy with having the System.out.println in your class.  Off of the top of my head, I would create an reporting structure, which would include an interface and at least one class.  Something like

interface Reporter {

    void reportLine(string message);
}

Then you could implement it like

public class ConsoleReporter implements Reporter {

    void reportLine(string message) {
        System.out.println(message);
    }

}

and your implementation.  Notice the constructor now does something, so my point about removing it is not valid in this case.

class RecursiveMethods {

   private Reporter reporter;

   RecursiveMethods(Reporter reporter)          //default constructor
   {
       this.reporter = reporter;
   }

   public int fOf(int x)
   {
       if (x <= 10)                        //the base case
       {
           reporter.reportLine(x + " <= 10, therefore ... f(" + x + ") = -5");
           return -5;
       }

       reporter.reportLine(x + " > 10, therefore ... f(" + x + ") = f(" + x + " - 3) + 2 = f(" + (x -3) + ") + 2");

        return fOf(x-3) + 2;
   }
}

public static void main(String[] args)
{
    Reporter reporter = new ConsoleReporter();
    int x;
    RecursiveMethods rMethods = new RecursiveMethods(reporter);

    // Change all System.out.writeLn to reporter.reportLine
}

Doing this will allow you to output to different mediums, for instance, you could create FileReporter, which would output to a file, or StreamingReporter, which would output to a stream of some sort.  It just makes your code more versatile.  You could also add a method like reportString, which would write an entire formatted string.

It is fine. The code could use the following improvements:

some additional comments, to describe in particular what the recursive function does. Recursive functions are by nature harder to read.
"fOf" is not a particularly good method name. Try to use longer, explicit names.


Determine if input word can be created from a list of letters I am looking for a more elegant way to validate in an input word can be created from a list of letters.

# Necessary variables (change as needed to test your code).
user_word = 'BANANA'
letters = ['N', 'B', 'N', 'A', 'A', 'P', 'M', 'S', 'A']

# This function checks whether a word entered by the user contains appropriate letters.
# It receives the letters and the word as parameter values, and returns True or False.
def validate_word(word, letters):
    from collections import Counter
    Count = Counter(letters)
    for letters in word:
        if not Count[letters]:
            return False
        Count[letters] -= 1
    return True

# Print the return value of the function to test it.
print(validate_word(user_word, letters))

As commented the function needs to return True if all the letters in the word are in the list, False otherwise.

Imports

In general, imports should be listed at the top of the script, not inside function definitions.  So instead of this:

def validate_word(words, letters):
    from collections import Counter
    ...

Write:

from collections import Counter

def validate_word(words, letters):
    ...

Variable names

In Python, variable names should be snake_case.  Words beginning with upper case letters are reserved from classes, like Counter, so Count should be called count.

Test Code

user_word and letters are declared far from the code that uses them.  They should be declared near where they are used, so at the bottom of the script, and ideally inside a __name__ == '__main__' guard:

from collections import Counter

def validate_word(word, letters):
    ...

if __name__ == '__main__':
    user_word = 'BANANA'
    letters = ['N', 'B', 'N', 'A', 'A', 'P', 'M', 'S', 'A']
    print(validate_word(user_word, letters))

A String is a List of Characters

The Counter class accepts an iterable for its construction argument, such as the list of letters you want to count.  But a string is also an iterable list of characters, so instead of a list, you could simply pass in a string, and it would work just as well:

if __name__ == '__main__':
    user_word = 'BANANA'
    letters = 'NBNAAPMSA'
    print(validate_word(user_word, letters))

Counters

You are counting up the counts of letters you are allowed to use.  Why not count up the count of letters in the user_word?

>>> Counter('NBNAAPMSA')
Counter({'A': 3, 'N': 2, 'B': 1, 'P': 1, 'M': 1, 'S': 1})
>>> Counter('BANANA')
Counter({'A': 3, 'N': 2, 'B': 1})

Then instead of looping over the letters of the user word, and subtracting 1 from the letter count, you could compare the letter counts directly.

Or ... you could subtract one from the other ...

>>> counts = Counter('NBNAAPMSA')
>>> counts.subtract('BANANA')
>>> counts
Counter({'P': 1, 'M': 1, 'S': 1, 'N': 0, 'B': 0, 'A': 0})
>>>

As long as all values in the counter are non-negative, the word is valid.

>>> all(count >= 0 for count in counts.values())
True

From this, a simpler function can be created.  Left to student.

There is a very short way to accomplish what you are trying to do:

def validate_word(word: str, letters: list) -> bool:
    """
    Determines if the `word` can be made out of `letters`
    """
    matched_word = ""
    for letter in word:
        for index, value in enumerate(letters):
            if value == letter:
                matched_word += value
                del letters[index]
                break
    return word == matched_word

What this does it loop through word and letters. It then matches up each letter in word and letters, and if they match, it adds it to the matched_word. It then returns if they are equal or not.

The break is used to exit out of the inner loop, so multiple letters are not added if they match.


Check if select has a certain option I suspect there is a simpler way to find if a select has a certain option, but don't know what. The objective of the following is to check if the desired option exists or not, and if it does, set it as the selected option:

Markup

<input type="text" size="2" id="selectVal"/>
<button onclick="setSelect()">Set the select</button>
<select id="mySelect">
    <option value="0">Select an option</option>
    <option value="1">A</option>
    <option value="2">B</option>
    <option value="3">C</option>
    <option value="4">D</option>
</select>

JS

function setSelect() {
    var desiredOption = $("#selectVal").val();
    if (desiredOption == '') {
        $("#selectVal").focus();
        return false;
    }
    var hasOption = $('#mySelect option[value="' + desiredOption + '"]');
    if (hasOption.length == 0) {
        alert('No such option');
    } else {
        $('#mySelect').val(desiredOption);
    }
    $("#selectVal").select();
}

To be clear, I wonder if a single method could do the job of the following two lines:

var hasOption = $('#mySelect option[value="' + desiredOption + '"]');
if (hasOption.length == 0)

Any suggestions?

jsfiddle here.

You could try and force the option to be selected.  Because jQuery doesn't throw errors when it doesn't have a set of elements, you can use this to your advantage inside an if statement. Couple this with jQuery's chaining and you can do something like:

function setSelect() {
    var desiredOption = $("#selectVal").val();
    if (desiredOption == '') {
        $("#selectVal").focus();
        return false;
    }
    if (!$('#mySelect option[value="' +desiredOption+ '"]').prop("selected", true).length) {
        alert('No such option');
    }
    $("#selectVal").select();
}

  Updated fiddle: http://jsfiddle.net/SPvrA/7/

How about plain vanilla Javascript:

if(document.getElementById("selectVal").options.namedItem(desiredOption)===null){
  // option  in desiredOption variable not found
}else{
  // option in desiredOption variable found
}


Counting adjacent swaps to sort an array with 3 different values This is the Kindergarten Excursion problem from kattis.com:

  The kindergarten teachers had finally managed to get all the kids in a line for the walk to the bus station and the weekly excursion. What they hadn’t thought of was the fact that today different kids were supposed to go to different excursions. They should walk as one line to the bus station, but to avoid total chaos when they arrive there, all the kids going to the zoo should be in the beginning of the line, the ones going to the lake should be in the middle and the rest, going to the science museum, should be in the end.

  Since it takes a lot of time to get all the kids to stand in a line no kid may step out of the line. To get the line organized after excursion group, kids standing next to each other can swap places. Now the kindergarten teachers wonder, if they will have time to do this and still catch their bus.

  Task

  You will be given a sequence of numbers 0, 1, and 2, denoting the excursion destinations of each kid from first to last in the line. Pairs of adjacent kids can swap positions, and the line should be organized after destination number starting with 0 and ending with 2. What is the minimum number of swaps required to organize the line?

  Input

  The only line of input contains a string consisting of characters 0, 1 or 2, denoting the destinations of kids. The length of the string will be at most 1,000,000 characters.

  Output

  Output one line with one integer – the minimum number of swaps needed to get the kids in order.

  Sample Input 1

10210

  Sample Output 1

5

This is my code. My solution is too slow and I need help with optimization or a different approach for this problem.

def excursion(str):
    digits = [0, 0, 0]
    x = 0
    for i in range(len(str)):
        for j in range((int(str[i])) + 1, 3):
            x += digits[j]
        digits[int(str[i])] += 1
    return x

print(excursion(input()))

The code in the post runs in linear time, so we can't hope to improve the asymptotic complexity, but we might be able to make some piecewise optimizations. Let's start by making a random test case:

>>> import random
>>> CASE = ''.join(random.choice('012') for _ in range(10**6))

Timing the performance on this test case establishes a baseline for any improvements.

>>> from timeit import timeit
>>> timeit(lambda:excursion(CASE), number=1)
1.1623761800583452

The expression int(str[i])) appears twice, so let's remember it in a local variable:

def excursion2(str):
    digits = [0, 0, 0]
    result = 0
    for i in range(len(str)):
        digit = int(str[i])
        for j in range(digit + 1, 3):
            result += digits[j]
        digits[digit] += 1
    return result

This saves about 25% of the runtime:

>>> timeit(lambda:excursion2(CASE), number=1)
0.867930110078305

The code only uses the index i to look up the corresponding character of str. So instead of iterating over the indexes, iterate over the characters themselves:

def excursion3(str):
    digits = [0, 0, 0]
    result = 0
    for c in str:
        digit = int(c)
        for j in range(digit + 1, 3):
            result += digits[j]
        digits[digit] += 1
    return result

This saves about 3%:

>>> timeit(lambda:excursion3(CASE), number=1)
0.8365003759972751

We can save an assignment statement by using map to apply the function int to the characters of str:

def excursion4(str):
    digits = [0, 0, 0]
    result = 0
    for digit in map(int, str):
        for j in range(digit + 1, 3):
            result += digits[j]
        digits[digit] += 1
    return result

This saves about 4%:

>>> timeit(lambda:excursion4(CASE), number=1)
0.7819818791467696

We could cache the range objects, to avoid rebuilding them on each loop:

def excursion5(str):
    n = 3
    digits = [0] * n
    ranges = [range(i + 1, n) for i in range(n)]
    result = 0
    for digit in map(int, str):
        for j in ranges[digit]:
            result += digits[j]
        digits[digit] += 1
    return result

This saves about 25%:

>>> timeit(lambda:excursion5(CASE), number=1)
0.497486931970343

The cumulative impact of these changes reduced the overall runtime by about 60%. Is that good enough to pass the time limit?

Since you know that there will only be 3 distinct values, you should use bucket sort. We will store the counts in a dictionary, and then build the string at the end to avoid the cost of repeated concatenation. This code is both simpler and faster.

def excursion(string):
    digits = {'0':0, '1':0, '2':0}
    for char in string:
        digits[char] += 1
    return '0'*digits['0'] + '1'*digits['1'] + '2'*digits['2']

n=0b10000001000000
print(len(excursion('2'*n+'1'*n+'0'*n)))


Checking whether a number is a power of 10 Is there a better way to check whether a number is a power of 10? This is what I've implemented:

    public class PowersOfTen {

    public static boolean isPowerOfTen(long input) {

        if (input % 10 != 0 || input == 0) {
            return false;
        }

        if (input == 10) {
            return true;
        }

        return isPowerOfTen(input/10);
    }

    public static void main(String[] args) {

        System.out.println("1000: " + isPowerOfTen(1000));
        System.out.println("4: " + isPowerOfTen(4));
        System.out.println("0: " + isPowerOfTen(0));
        System.out.println("10: " + isPowerOfTen(10));
        System.out.println("100: " + isPowerOfTen(100));
    }
}

Recursing seems pretty heavy for this. You can use much the same logic but with a simple loop:
while (input >= 10 && input % 10 == 0)
  input /= 10;
return input == 1;

This checks to make sure the input is at least 10 (since any integers below that, including zero and negative values, can't be powers of 10) and also a multiple of 10 (as all powers of 10 greater than 1 obviously are). It does the simpler comparison first as a small micro-optimization; the short-circuit evaluation will avoid performing an unnecessary division to compute an unneeded modulus.
If both conditions are met it does an integer division by 10 and repeats the process. For any power of 10, this will terminate with the value 1; if 1 itself is passed in, it will do so without ever executing the body of the while loop.

I know it's possibly not the best option, but I always find interesting to approach math-y simple problems from a human perspective and no one suggested the approach yet of, in this case, looking at how the number is written:

boolean isPowerOfTen(int n) {
    char[] digits = (n+"").toCharArray();
    if (digits[0] != '1') return false;
    for (int i = 1; i<digits.length; i++) {
      if (digits[i] != '0') return false;
    }
    return true;
}

You can easily extend it for negative powers (0.000001) and it's arguably much easier to read and short than other methods, though it has a worse performance.


Java Concurrent Multimap I've implemented a concurrent multimap that support concurrent put and remove but I'm unsure of its correctness. I would appreciate your feedback.

public class ConcurrentMultiMap<K, V> {
    private static ConcurrentHashMap emptySet = new ConcurrentHashMap();
    private ConcurrentHashMap<K, ConcurrentHashMap<V, Object>> map = new ConcurrentHashMap<>();

    // return true if the method increased the size of the multimap or false if the multimap already contained the key-value pair
    public boolean put(K k, V v) {
        Preconditions.checkNotNull(k);
        Preconditions.checkNotNull(v);
        boolean tryAgain;
        boolean success = true;
        do {
            ConcurrentHashMap<V, Object> oldSet = map.get(k);
            if (oldSet == null) {
                tryAgain = map.putIfAbsent(k, new ConcurrentHashMap<>(Collections.singeltonMap(v, 1))) != null;
            } else {
                success = oldSet.putIfAbsent(v, 1) == null; //I do not allow multiple equal values for the same key
                if (success) {
                    // if the put was a success we check that the key was not removed from the map by a concurrent remove operation.
                    ConcurrentHashMap<V, Object> currentSet = map.get(k);
                    tryAgain = currentSet == null || !currentSet.contains(v);
                } else {
                    return false;
                }
            } while(tryAgain);
            return success;
    }

    // returns true if the multimap changed
    public boolean remove(K k, V v) {
        Preconditions.checkNotNull(k);
        Preconditions.checkNotNull(v);
        ConcurrentHashMap<V, Object> oldSet = map.get(k);
        if (oldSet == null) {
            return false;
        }
        if (oldSet.remove(v) != null) {
            if (oldSet.size() == 0) {
                map.remove(k, emptySet);
            }
            return true;
        }
        return false;
    }
}

You should have HashMap<K, Set<V>>, not ConcurrentHashMap<K, ConcurrentHashMap<V, Object>>.


Leap year check in Java I'm looking for 3 different answers:

Using Java predefined functions
Converting from string to number
Without the above two (any other types of answers are also welcome)

I am looking for improving my code (as per the above 3 conditions for 3 answers) taken from my repository here.

/*
 * Checks if the year passed is a leap year
 *
 * @param year; requires the year to have 4 digits
 * @return true if leap, else false
 *
 */

public static boolean isLeapYear(int year) {
    String testYear = String.valueOf(year);
    if (testYear.charAt(2) == '1' || testYear.charAt(2) == '3' ||
            testYear.charAt(2) == 5 || testYear.charAt(2) == '7' ||
            testYear.charAt(2) == '9') {
        //If the third digit is odd

        if (testYear.charAt(3)=='2'||testYear.charAt(3)=='6'){
            return true;
        }
        else{
            return false;
        }
    }
    else{
        if (testYear.charAt(2) == '0' && testYear.charAt(3) == '0') {
            if(testYear.charAt(0) == '1' || testYear.charAt(0) == '3' ||
                    testYear.charAt(0) == 5 || testYear.charAt(0) == '7' ||
                    testYear.charAt(0) == '9'){
                //If first digit is odd

                if(testYear.charAt(1)=='2'||testYear.charAt(1)=='6'){
                    return true;
                }
                else{
                    return false;
                }
            }

            //If second digit is not odd
            else if(testYear.charAt(1)=='0'||testYear.charAt(1)=='4'||
                    testYear.charAt(1)=='8'){
                return true;
            }
            else
                return false;
        }
        else if (testYear.charAt(3)=='0'||testYear.charAt(3)=='4'||
                testYear.charAt(3)=='8'){
            //If fourth digit is not odd
            return true;
        }
        else
            return false;
    }
}

Processing the number as a string

Don't. In general, converting a numerical value to a string and using some string processing on what was once a number is a code smell. You of course often need to convert numbers to strings for output and formatting, but mathematical operations should be done mathematically.

If you for instance wanted to check whether the second-last digit is even, you can divide your number by 10 and check the oddity of that result. That's an arithmetic check without involving any string processing.

The correct algorithm

Whenever you approach a problem, you should think about the correct algorithm to solve it, and do some research, if applicable. Leap years for instance can be detected by a much simpler algorithm. Leap years in the Gregorian calendars are years that are divisible by 4 but not 100, unless they are also divisible by 400. So:

If it's not divisible by 4, it's not a leap year.

If it's divisible by 4, it's a leap year if: it's not divisible by 100, or it's divisible by 400.

Now that looks almost like an algorithm in code. Which you can write along the lines of

if (year % 4 == 0) {
    if (year % 100 != 0) {
        return true; //Divisible by 4 and not by 100, leap year
    }
  return (year % 400 == 0); //Divisible by 4 and by 100. Leap year if divisible by 400.
}
return false; //Not divisible by 4 - not a leap year.

Of course that could also be a one-liner, but this perhaps makes the decision logic a bit more clear.

Java 8

In Java 8, a lot of functionality for handling calendars has been added, such as the Year class. The following would work:

return Year.isLeap(year);

General

It's hard not to notice that your formatting is inconsistent. Sometimes space before opening braces, sometimes not. Sometimes you surround a single statement with braces, sometimes not. Those are largely up to individual preference (although I think space before braces is a must, as is enclosing single statements in braces), but consistency is definitely very important.

Also, as the answer by RubberDuck notes, it's not needed or a good practice to write code of the if (something) return true; else return false type when you can just return the condition directly.

You can also do it using the java.util.calendar library.

A year is a leap year if:

The remainder is 0 when divided by 4
February has 29 days instead of 28 days

We saw ideas checking when the remainder is 0. I will present an idea of when we want to check if February has 29 days. It is done using the Java built-in library java.util.calendar.

Using the Java Calendar utility, we can set our year to need one and month to 1 (because in Java.util.calendar, months go from 0-11), so 1 is February. We can't set it to any other because only in February we can see it is a leap year.

getActualMaximum(Caledanr.DAY_OF_MONTH) is a function that returns an int value that presents the maximum number of days for a date for which we set the month/year value. If the value is 29 we know that it is a leap year, else it is not a leap year.

It is more effective than your solution, but in some cases other solutions in this question can work better.

public static boolean leap_yr(int year){
Calendar calendar = Calendar.getInstance();
calendar.clear();
calendar.set(Calendar.MONTH, 1);
calendar.set(Calendar.YEAR, year);

if(calendar.getActualMaximum(Calendar.DAY_OF_MONTH) == 29){
 return true;
}
else{
 return false;
}

}


Simple method to detect int overflow To detect int overflow/underflow in C, I use this code. What might be a simpler and more portable way of coding this (that is, fewer conditions)?

Assume 2's complement and don't use wider integers.

int a,b,sum;
sum = a + b;
// out-of-range only possible when the signs are the same.
if ((a < 0) == (b < 0)) {
  if (a < 0) {
    // Underflow here means the result is excessively negative.
    if (sum > b) UnderflowDetected();
  }
  else {
    if (sum < b) OverflowDetected();
  }

It's not possible to avoid undefined behaviour by testing for it after the fact! If the addition overflows then there is already undefined behaviour here:

sum = a + b;

so attempting to test afterwards is too late. You have to test for possible overflow before you do a signed addition. (If you're puzzled by this, read Dietz et al. (2012), "Understanding Integer Overﬂow in C/C++". Or even you're not puzzled: it's an excellent paper!)

If it were me, I'd do something like this:

#include <limits.h>

int safe_add(int a, int b) {
    if (a > 0 && b > INT_MAX - a) {
        /* handle overflow */
    } else if (a < 0 && b < INT_MIN - a) {
        /* handle underflow */
    }
    return a + b;
}

but I'm not entirely sure what the point of having separate cases for overflow and underflow is.

I also use Clang's -fsanitize=undefined when building for test.

Why not use a long to hold the result of the calculation?  Then the long can be checked against the (int) MAX and MIN values to see if overflow or underflow occurred?  If no violations have occurred, then the result can safely be re-cast back to an (int).

Or, is this too simple and I'm missing something very fundamental?  One thing that I HAVE omitted is the possibility that the long will also overflow.


Find maximum length of array where every entries are the same Is the complexity of this code \$O(n^3)$? How can I improve the efficiency and reduce the complexity?

A = [3,2,4,2,4,2,4,5,3]
n= len(A)
def ALG2 (A,i,j):  #to check whether all entries between A[i] and A[j] are the same
    if i==j:
        return True
    for k in range (i,j-1):
        if A[k] != A[k+1]:
            return False
    return True

def  ALG1(A,n):   #find the max length of the arrays that are found in ALG2
    l=0
    for i in range (0,n-1):
        for j in range (i+1,n-1):
            if ALG2(A,i,j) and (j-i)>l:
                l= j-i

    return l

result = ALG1(A,n)

print (result)

You should use better function names ALG1 and ALG2 don't really say what they're performing.
You should keep the creation of A, n and result at the bottom of your code.
You should keep your 'main' code in a main guard block:

if __name__ == '__main__':
    A = [3,2,4,2,4,2,4,5,3]
    n= len(A)
    result = ALG1(A,n)
    print(result)

You should follow PEP 8, so that it's easier for others to read your code.
ALG2 can be simplified by slicing the array from i to j, A[i:j], and then checking if the set has a size of one.

def ALG2(A, i, j):
    return len(set(a[i:j])) == 1

Your entire code can be drastically simplified by using itertools.groupby.

import itertools

def ALG1(array):
    sizes = (
        sum(1 for _ in g)
        for _, g in itertools.groupby(array)
    )
    return max(sizes, default=0)

Your algorithm is indeed n^3, but you can do it in linear time. https://ideone.com/Ke3q5o

A = [3,2,5,4,4,4,4,2,4,4]

def findLongestContinuousSection(A):
    if len(A) == 0:
        return
    longestStart = 0
    longestStop = 0
    longestLength = 0
    longestVal = 0
    curStart = 0
    curStop = 0
    curLength = 1
    curVal = A[0]
    for k in range(1,len(A)-1):
        if curVal != A[k]: # record cur as longest
            longestVal = curVal
            longestStart = curStart
            longestStop = curStop
            longestLength = curLength
            curStart = k
            curStop = k
            curLength = 1
            curVal = A[k]
        else: # continue to build current streak
            curStop = k
            curLength += 1
    return (longestStart, longestStop, longestLength, longestVal)

print findLongestContinuousSection(A)


String.IsNullOrEmpty in JavaScript I am aware of it being frowned upon to do something like write C# in JavaScript. (see this if you don't know what I'm talking about)

But as a judgement call, I think we could stand to have a relatively simple check for values that are null or empty, so I'm looking for feedback on this implementation of String.isNullOrEmpty.

String.isNullOrEmpty = function (value) {
    return (!value || value == undefined || value == "" || value.length == 0);
}

Starting with:

return (!value || value == undefined || value == "" || value.length == 0);

Looking at the last condition, if value == "", it's length MUST be 0. Therefore drop it:

return (!value || value == undefined || value == "");

But wait! In JS, an empty string is false. Therefore, drop value == "":

return (!value || value == undefined);

And !undefined is true, so that check isn't needed. So we have:

return (!value);

And we don't need parentheses:

return !value

Q.E.D.

You should use Object.prototype.isNullOrEmpty = function() { alert(this) }.  This ties it to the String object in all instances.  This would start to give you access to use strings and variables like "".isNullOrEmpty or var x = null; x.isNullOrEmpty();

If your intent is to use it as a function to pass in variables: String.isNullOrEmpty();


Menu system and Turtle I had to do a small application using a menu system and Turtle. I have finished it and worked perfect. Just to make sure, can you please check it if it has done properly?

#!/usr/bin/python

## draw_shape.py

import turtle as t

def how_many():
    while True:
        print "  How many of then do you want to draw?"
        print "  -Range is from 1 to 5-"
        global shape_no
        shape_no = raw_input('  Enter your choice: ')
        try:
            shape_no = int(shape_no)
            if (1 <= shape_no <= 5):
                print "Your number is ok"
                break
            else:
                print
                print "from 1 to 5 only"
        except:
            print "Only numbers allowed - Please try again"
    return True

#=========#=========#=========#=========#=========#=========#=========#
def start_point():
    t.penup()
    t.setpos(-240,0)
    t.pendown()

def draw_square(howmanyof):
    start_point()
    for a in range(howmanyof):
        for a in range(4):
            t.forward(80)
            t.left(90)
        t.penup()
        t.forward(100)
        t.pendown()

def draw_triangle(howmanyof):
    start_point()
    for a in range(howmanyof):
        for a in range(3):
            t.forward(80)
            t.left(120)
        t.penup()
        t.forward(100)
        t.pendown()

def draw_rectangle(howmanyof):
    start_point()
    for a in range(howmanyof):

        for a in range(2):
            t.forward(80)
            t.left(90)
            t.forward(40)
            t.left(90)
        t.penup()
        t.forward(100)
        t.pendown()

def draw_hexagon(howmanyof):
    start_point()
    for a in range(howmanyof):
        for a in range(6):
            t.forward(50)
            t.left(60)
        t.penup()
        t.forward(110)
        t.pendown()

def draw_octagon(howmanyof):
    start_point()
    for a in range(howmanyof):
        for a in range(8):
            t.forward(40)
            t.left(45)
        t.penup()
        t.forward(110)
        t.pendown()

def draw_circle(howmanyof):
    start_point()
    for a in range(howmanyof):
        t . circle(50)
        t.penup()
        t.forward(120)
        t.pendown()

#=========#=========#=========#=========#=========#=========#=========#
def main():
    while True:
        print
        print "  Draw a Shape"
        print "  ============"
        print
        print "  1 - Draw a square"
        print "  2 - Draw a triangle"
        print "  3 - Draw a rectangle"
        print "  4 - Draw a hexagon"
        print "  5 - Draw an octagon"
        print "  6 - Draw a circle"
        print
        print "  X - Exit"
        print

        choice = raw_input('  Enter your choice: ')

        if (choice == 'x') or (choice == 'X'):
            break
        elif choice == '1':
            how_many()
            draw_square(shape_no)
        elif choice == '2':
            how_many()
            draw_triangle(shape_no)
        elif choice == '3':
            how_many()
            draw_rectangle(shape_no)
        elif choice == '4':
            how_many()
            draw_hexagon(shape_no)
        elif choice == '5':
            how_many()
            draw_octagon(shape_no)
        elif choice == '6':
            how_many()
            draw_circle(shape_no)
        else:
            print
            print '  Try again'
            print

#=========#=========#=========#=========#=========#=========#=========#
if __name__ == "__main__":
    main()

#=========#=========#=========#=========#=========#=========#=========#

Why are you using a global? There seems to be no need for it, and in general it's something to avoid.
Why not factor out the common stuff? In your main loop you have a bunch of if cases which all start in the same way and then all call methods which are very similar. If you start by checking that it's a valid input you could pull out the calls to how_many() and start_point() and even the loop for a in range(howmanyof):.

Fix your prints.
Proper syntax is:
    print("Hi")

and this will print Hi.
Also, you didn't import raw_input.
Instead of using raw_input, use input(), I'm pretty sure that it does the same thing.


Alternative for two sequentially executed loops with identical ranges For the moment I'm executing my code as follows:

foreach (int data in dataList)
{
    PreProcess(data);
}
foreach (int data in dataList)
{
    Process(data);
}

First I have to loop over some data (from a list) and to do some pre-processing after which then I do have to loop again over the same data list and do some processing, but those loops have to be run one after another, and cannot be merged as follows...

foreach (int data in dataList)
{
    PreProcess(data);
    Process(data); // Cannot be run in the same loop with PreProcess(data);
}

...because PreProcess(data) and Process(data) are logging a lot of information which could be interlaced in case both are looping together.

The only alternative I've found will be using Linq, but still has the same duplicate ForEach:

dataList.ForEach(data => { PreProcess(data); });
dataList.ForEach(data => { Process(data); });

Is there any way to rewrite this in order to remove the redundancy for two loops with same range, but still looping sequentially first over PreProcess(data) and Process(data) afterwards?

You could also define something like

private void MyLoop<T>(Action<T> action, IEnumerable<T> dataList)
{
    foreach (var data in dataList)
    {
        action(data);
    }
}

and use it

MyLoop(Process, dataList);

or using Action

Action<Action<int>> myLoop= action =>
{
    foreach (var data in dataList)
    {
        action(data);
    }
};

and use it like this

myLoop(Process);

interface IActionStrategy
{
    void applyTo(RequiredDataType data);
}
// ...
foreach (IActionStrategy strategy in strategyQueue)
    foreach (RequiredDataType data in dataList)
        strategy.applyTo(data);

Each strategy have to implement common interface in order to do it.


More groovifed way of sublist with varying range Student list of 50 students and a teacher list of 3 teachers.

Section XML as the output where each teacher is assigned to a section, and up to 20 students are assigned in that section.

Need to loop on each teacher element, and for each teacher element, loop on the student name from 1-20, than for 2nd teacher, students 21-40 etc.

The following is working code. However, feeling that there could be better groovified way to get 20 students for a teacher

def students = """<Students>
    <name> st name 1</name>
    <name> st name 2</name>
    <name> st name 3</name>
    <name> st name 4</name>
    <name> st name 5</name>
    <name> st name 6</name>
    <name> st name 7</name>
    <name> st name 8</name>
    <name> st name 9</name>
    <name> st name 10</name>
    <name> st name 11</name>
    <name> st name 12</name>
    <name> st name 13</name>
    <name> st name 14</name>
    <name> st name 15</name>
    <name> st name 16</name>
    <name> st name 17</name>
    <name> st name 18</name>
    <name> st name 19</name>
    <name> st name 20</name>
    <name> st name 21</name>
    <name> st name 22</name>
    <name> st name 23</name>
    <name> st name 24</name>
    <name> st name 25</name>
    <name> st name 26</name>
    <name> st name 27</name>
    <name> st name 28</name>
    <name> st name 29</name>
    <name> st name 30</name>
    <name> st name 31</name>
    <name> st name 32</name>
    <name> st name 33</name>
    <name> st name 34</name>
    <name> st name 35</name>
    <name> st name 36</name>
    <name> st name 37</name>
    <name> st name 38</name>
    <name> st name 39</name>
    <name> st name 40</name>
    <name> st name 41</name>
    <name> st name 42</name>
    <name> st name 43</name>
    <name> st name 44</name>
    <name> st name 45</name>
    <name> st name 46</name>
    <name> st name 47</name>
    <name> st name 48</name>
    <name> st name 49</name>
    <name> st name 50</name>
</Students>"""

def teachers = """<Teachers>
    <name> Teacher name 1</name>
    <name> Teacher name 2</name>
    <name> Teacher name 3</name>
</Teachers>"""

def getData  = { xml, elementName ->
    def parseXml = new XmlSlurper().parseText(xml)
    parseXml.'**'.findAll { it.name() == elementName }
}

def teacherNodes = getData( teachers, 'name')
def studentNodes = getData( students, 'name')

def sublist (data, start, end) {
    start == 0 ? data.take(end) : data.drop(start).take(end-start)
}

def incrementBy = 20
def startStudents = 0
def endStundents = incrementBy
def builder = new groovy.xml.StreamingMarkupBuilder()
builder.encoding = 'UTF-8'
def xml = builder.bind {
    mkp.xmlDeclaration()
    Assignments {
        teacherNodes.eachWithIndex { teacherNode, index ->
            Section {
                id (index+1)
                teacher (teacherNode.text())
                studentList {
                    sublist(studentNodes, startStudents, endStundents).each { studentNode ->
                        name (studentNode.text())
                    }
                }
            }
            startStudents = endStundents
            endStundents += incrementBy
        }
    }
}

println groovy.xml.XmlUtil.serialize(xml)

You could start with:

def groups = [:]
teacherNodes.each { teacher ->
    groups[teacher] = studentNodes.take(incrementBy)
    studentNodes    = studentNodes.drop(incrementBy)
}


Preorder traversal using stack I wrote the code for an iterative pre-order traversal using stack for binary search tree. Below is the code for same. Please help me verify the correctness of the algorithm. Here t.t is the value of node t.

static void preorder(TreeNode t)
{
    MyConcurrentStack<TreeNode> s = new MyConcurrentStack<TreeNode>();
    while(s.peek()!=null || t!=null)
    {
        if(t!=null)
        {
            System.out.print(t.t+":");
            s.push(t);
            t = t.left;
        }
        else
        {
            t = s.pop();
            t = t.right;
        }
    }
}

There are a few points that can be critizised.

The method signature suggests that the architecture of the system isn't well-designed. Traversal of a Tree should likely be encapsulated in an Iterator class. In that case, the stack would be a private field of the iterator, and the actual code would use a foreach loop.

for (TreeNode node : tree)
  System.out.print(node.t + ":");

(preorder iteration is a good default)
Even if we let the design of your classes as they are, your implementation could be improved.

Single-letter variable names should be avoided. True, there are only two variables in your method, but using node and stack would be so much less cryptic.

The stack does not have to be concurrent, because it is not shared accross multiple threads. The vanilla java.util.Stack should work just fine. If you care about concurrency, you should rather worry about the tree nodes. What happens when a node was stored on the stack, but removed from the tree before the right child can be consumed by your code? Make sure the nodes aren't mutated until you visited them.

The body of your loop does not have a single comment although the stack manipulation may not be totally obvious to everybody (incl. you).

If you are optimizing for readability and not for space, I'd strongly suggest a recursive solution. This also makes writing correct code much easier:

static void preorder(TreeNode node) {
  if (node == null) return;

  System.out.println(node.t + ":");

  preorder(node.left);
  preorder(node.right);
}

(Not that your code was incorrect, this is just much easier to verify).

Next, I would like to reorder the parts of your loop to make it more obvious what is happening:

while (true)
{
    // check if we have to pop a value of the stack
    while (node == null) {
      if (stack.empty()) return;
      node = stack.pop().right;
    }

    System.out.print(node.t + ":");

    stack.push(node);  // store the node to continue the right path later
    node = node.left;
}

Note: If we use the java.util.Stack, then peek() could throw an EmptyStackException. We should rather use the empty() method which returns a boolean.

I think it would be more elegant to put the right childs on the stack, not the nodes which we already visited. We should also test whether these are null before adding them to the stack. This would keep the stack smaller:

while (true)
{
    // check if we have to pop a value of the stack WITHOUT LOOPING:
    // It is guaranteed that there never is a null node on the stack.
    if (node == null) {
      if (stack.empty()) return;
      node = stack.pop();
    }

    System.out.print(node.t + ":");

    // store the right node to continue there later
    if (node.right != null) stack.push(node.right);

    node = node.left;
}

I am not too comfortable with a while (true) loop, but the alternatives would mean slight code duplication (e.g. in your original code, you have two t!=null tests.)

Finally, you likely want to print a newline after this iteration. (In that case, the return should be a break).

Here is my latest implementation:

public class Tree<K> implements Iterable<K>
{
    private TreeNode<K> root;
    static class TreeNode<K>
    {
        K k;
        TreeNode<K> left;
        TreeNode<K> right;
        public TreeNode(K k)
        {
            this.k = k;
        }
    }

    public void insert(K k)
    {
        Comparable cc = (Comparable)k;
        if(root == null)
        {
            root = new TreeNode<K>(k);
        }
        else
        {
            TreeNode temp = root;
            TreeNode parent = root;
            while(temp!=null)
            {
                parent = temp;
                Comparable c = (Comparable)temp.k;
                if(c.compareTo(cc) < 0)
                {
                    temp =temp.right;
                }
                else
                {
                    temp = temp.left;
                }
            }
            Comparable c = (Comparable)parent.k;
            if(c.compareTo(cc) > 0)
            {
                parent.left = new TreeNode(k);
            }
            else
            {
                parent.right = new TreeNode(k);
            }
        }
    }

    @Override
    public Iterator<K> iterator()
    {
        return new MyIterator<K>();
    }
    private class MyIterator<K> implements Iterator<K>
    {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode<K> t = (TreeNode<K>) root;

        @Override
        public boolean hasNext()
        {
            if(s.peek()!=null || t!=null)
            {
                return true;
            }
            return false;
        }

        @Override
        public K next()
        {
            while(s.peek() !=null || t!=null)
            {
                if(t!=null)
                {
                    s.push(t);
                    t = t.left;
                }
                else
                {
                    t = s.pop();
                    TreeNode<K> temp = t;
                    t = t.right;
                    return temp.k;
                }
            }
            return null;
        }

        @Override
        public void remove()
        {

        }

    }
}


Pagination object oriented This a little pagination script that I am writing "Object Oriented" and I have no idea how to set the current page equal to total page, if the current page is greater.  I also would really like it if anyone can tell me how to improve my code.

class pagination extends Db_connection {

    public $per_page;
    public $current_page;
    public $sql;

    //put your code here
    function __construct($per = 3, $current = 1) {
        parent::__construct();
        $this->per_page = $per;
        $this->current_page = $current;
    }

    function execute_query($sql) {
        $this->sql = $sql;
        $q = $this->query($sql);
        return $q;
    }

    function total_pages() {
        $total = ceil($this->count_rows() / $this->per_page);
        return $total;
    }

    function current_page() {
        if (isset($_GET['page']) && is_numeric($_GET['page']))
            $this->current_page = intval($_GET['page']);

        return $this->current_page;
    }

    function offset() {
        $off = ($this->current_page() - 1) * $this->per_page;
        return $off;
    }
    public function previous_page(){
        //move to previous record by subtracting one into the current record
        return  $this->current_page - 1;
    }
    public function next_page(){
        //mvove to next record by incrementing the current page by one
        return  $this->current_page + 1;

    }

    function count_rows() {
        $nums = mysqli_fetch_row($this->execute_query("select count(post_id) from Post"));
        return $nums[0];
    }

    function results() {
        $off = $this->offset();
        $per = $this->per_page;
        $query = $this->execute_query("Select * from Post limit $off, $this->per_page");
        while ($result = mysqli_fetch_array($query)) {
            $data[] = $result;
        }
        return $data;
    }
}

If you have to identify the main objects here, we could conclude that you have at least 3

-- The connection to the DataBase

-- The pagination object that knows how to paginate a query

-- The query it self

so ie this is a possible solution:

abstract class DBConnection{
    //Logic
    public function executeQuery(Query $query)
    {
        $sql = $query->getSql();

        //Logic and return results
    }
}

class Query{
    private $sql;
    private $limit;
    private $offset;

    //getters and setters for each private property ... getSql ... setSql ...

    public function __construct($sql)
    {
        $this->sql = $sql;
    }

    public function getSql()
    {
        return $this->sql += "offset $this->getOffset() limit $this->getLimit()";
    }
}

class Paginator
{
    private $currentPage;
    private $perPage;
    private $query;
    private $connection;

    //Getters and setters...

    public function __construct(Query $query, $currentPage = 0, $perPage = 10)
    {
        $this->query = $query;
        $this->connection = new DBConnection();
    }

    public function nextPage()
    {
        $this->currentPage++;
    }

    public function prevPage()
    {
        $this->currentPage--; //check if 0 not substract
    }

    public function execute()
    {
        $this->query->setOffset($this->currentPage * $this->perPage);
        $this->query->setLimit($this->perPage);
        return $this->connection->executeQuery($this->query);
    }
}


Find out whether number is of Power of Two The task

is taken from leetcode

  Given an integer, write a function to determine if it is a power of
  two.

  Example 1:

  Input: 1

  Output: true

  Explanation: 20 = 1

  Example 2:

  Input: 16

  Output: true

  Explanation: 24 = 16

  Example 3:

  Input: 218

  Output: false

My solution

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
  if (n <= 0 ) { return false; }
  if (n <= 2) { return true; }
  let num = n;
  do {
    const x = num / 2;
    if ((x | 0) !== x) { return false; }
    if (x === 2) { return true; }
    num = x;
  } while(num);
  return false;
};

I mean, I would use a library to do this. Namely, Math.log2

function isPowerOfTwo(n) {
  return Math.log2(n) % 1 === 0;
}

console.log(isPowerOfTwo(3)); //false
console.log(isPowerOfTwo(4)); //true
console.log(isPowerOfTwo(7)); //false
console.log(isPowerOfTwo(8)); //true
console.log(isPowerOfTwo(-1));//false

I realize that this is an old question, but I though I'd provide my approach anyway.

What you really want to do, is count the number of active or set bits, as a power of two is always represented as a single bit.

Now, I'm not much for javascript, so this is semi pseudo/c code, but I do believe the operators are more or less the same.

bool isPowerOf2( uint64_t b )
{
    b = ((b >>  1) & 0x5555555555555555) + (b & 0x5555555555555555);
    b = ((b >>  2) & 0x3333333333333333) + (b & 0x3333333333333333);
    b = ((b >>  4) & 0x0f0f0f0f0f0f0f0f) + (b & 0x0f0f0f0f0f0f0f0f);
    b = ((b >>  8) & 0x00ff00ff00ff00ff) + (b & 0x00ff00ff00ff00ff);
    b = ((b >> 16) & 0x0000ffff0000ffff) + (b & 0x0000ffff0000ffff);
    b = ((b >> 32) & 0x00000000ffffffff) + (b & 0x00000000ffffffff);
    return (b==1);
}

Now this is able to handle 64 bit, but if you only need 32 or less, it can be adapted accordingly.
It may look complicated, but it really isn't.
What you do is separate the bit up in to pairs and add them. First you add bit 0 with bit 1, bit 2 with bit 3, etc. Then you do the same again, adding bit 0-1 with 2-3, 4-5 with6-7, and so on.

With the exception of some architecture depended instructions, like GCCs __builin_popcount, I know of no way that is more efficient, but then again, if you're coding in javascript, that is probably not a priority, and you may want to use another method. Just know that what you really want to do, is count bits.


File read/write methods I'm using some simple files for caching and some basic user data. I was first just using file_put_contens and file_get_contents, but realized this could quickly go wrong when traffic starts increasing.

I've been trying to figure out how to do it properly with flock, correct file modes, etc, and come up with the following functions. Have I understood things correctly? Will this be safe in most normal use-cases, with small to medium web site usage?

class File
{

    public static function read($path, $default = NULL)
    {
        $fp = @fopen($path, 'r');
        if( ! $fp)
            return $default;

        flock($fp, LOCK_SH);
        $data = fread($fp, filesize($path));
        flock($fp, LOCK_UN);
        fclose($fp);

        return $data;
    }

    public static function write($path, $data)
    {
        self::check(dirname($path));

        $fp = fopen($path, 'c');
        flock($fp, LOCK_EX);
        ftruncate($fp, 0);
        fwrite($fp, $data);
        fflush($fp);
        flock($fp, LOCK_UN);
        fclose($fp);

        return $data;
    }

    public static function check($dir)
    {
        if( ! is_dir($dir))
        {
            // https://en.wikipedia.org/wiki/Chmod#System_call
            @mkdir($dir, 06750, true);
            @chmod($dir, 06750);
        }
        return $dir;
    }
}

Some particular things:

Should using LOCK_SH in read allow for multiple simultaneous reads?
(which will be the bulk of what's happening since writes will happen quite seldom)
Will using LOCK_EX in write make sure nobody else is reading or writing while the file is changed?
Will using the directory permission mask 06750 makes sure that

any files created in that directory will get the same permissions as the directory, and
the directory/file will only be writable by the web server user and readable by its group?

Suppressing errors

  Edit

Error suppression should be avoided if possible as it doesn't just suppress the error that you are trying to stop, but will also suppress errors that you didn't predict would ever occur. This will make debugging a nightmare.

Other then that, looks nice.


Given two strings, a and b, determine the minimum number of character deletions required to make a and b anagrams I'm trying to figure out how my code could be improved. I solved a HackerRank problem from the Cracking the Coding Interview section, and am thinking that it should be able to be solved a simpler than what I did.

The problem is as follows:

  Strings: Making Anagrams

  Alice is taking a cryptography class and finding anagrams to be very
  useful. We consider two strings to be anagrams of each other if the
  first string's letters can be rearranged to form the second string. In
  other words, both strings must contain the same exact letters in the
  same exact frequency For example, bacdc and dcbac are anagrams,
  but bacdc and dcbad are not.

  Alice decides on an encryption scheme involving two large strings
  where encryption is dependent on the minimum number of character
  deletions required to make the two strings anagrams. Can you help her
  find this number?

  Given two strings, a and b, that may or may not be of the same
  length, determine the minimum number of character deletions required
  to make a and b anagrams. Any characters can be deleted from
  either of the strings.

  Input Format

  The first line contains a single string, a. The second line contains
  a single string, b.

  Constraints

  \$1 \le |a|,|b| \le 10^4\$
  It is guaranteed that a and b consist of lowercase English alphabetic letters (i.e., a through z).

  Output Format

  Pring a single integer denoting the number of characters you must
  delete to make the two strings anagrams of each other.

  Sample Input

cde
abc

  Sample Output

4

  Explanation

  We delete the following characters from our two strings to turn them
  into anagrams of each other:

  Remove d and e from cde to get c.
  Remove a and b from abc to get c.

  We must delete 4 characters to make both strings anagrams, so we print
  4 on a new line.

My Implementation

I am using C++, and since strings are immutable, what I decided to do was to create two int arrays (vectors, actually) that hold the ASCII value of the chars in each string. Then I would sort the vectors. Then I would iterate through the arrays together, counting the number of elements that don't exist in the other.

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

using namespace std;

int calcDeletions(vector<int> a, vector<int> b) {

    int deletions = 0;
    int ai = 0;
    int bi = 0;

    // step through arrays until the end of one is reached
    while (ai < a.size() && bi < b.size()) {
        if (a[ai] < b[bi]) {
            deletions++;
            ai++;
        }
        else if (a[ai] > b[bi]) {
            deletions++;
            bi++;
        }
        else {
            ai++;
            bi++;
        }
    }

    // carry over left-overs
    deletions += (a.size() - ai);
    deletions += (b.size() - bi);

    return deletions;
}

int number_needed(string a, string b) {
    vector<int> aInt;
    vector<int> bInt;

    // create two int vectors to store ascii val of strings
    for (int i = 0; i < a.length(); i++) {
        aInt.push_back((int)a.at(i));
    }
    for (int i = 0; i < b.length(); i++) {
        bInt.push_back((int)b.at(i));
    }

    // sort vectors
    sort(aInt.begin(), aInt.end());
    sort(bInt.begin(), bInt.end());

    // call calcDeletions function with the longer vector passed as first arg
    if (aInt.size() > bInt.size()) {
        return calcDeletions(aInt, bInt);
    }
    else {
        return calcDeletions(bInt, aInt);
    }
}

int main() {
    string a;
    cin >> a;
    string b;
    cin >> b;

    cout << number_needed(a, b) << endl;
    return 0;
}

What is a better, more efficient way of solving this problem?

I'm trying to figure out how my code could be improved. I solved a HackerRank problem from the Cracking the Coding Interview section, and am thinking that it should be able to be solved a simpler than what I did.

Probably. But these hacker problems are usually very specific. You can probably google a perfect solution in 10 minutes.

  What is a better, more efficient way of solving this problem?

Create a count of the number of each letter from both strings. To be anagrams these counts must be the same. So look across the counts and sum the differences.

  I am using C++, and since strings are immutable,

No they are not. Strings are perfectly mutable.

  what I decided to do was to create two int arrays (vectors, actually) that hold the ASCII value of the chars in each string. Then I would sort the vectors. Then I would iterate through the arrays together, counting the number of elements that don't exist in the other.

The complexity of this is (ignoring the copy to a vector)

O(n1.log(n1))      // Sort first string
O(n2.log(n2))      // Sort second string
O(max(n1,n2))      // Loop Over counting.

That seems to work. I like getting the count of each letter better. The difference in the counts is the number of letters to be deleted.

O(n1)             // Count each character into an array.
O(n2)             // Count each character into an array.
O(1)              // count the diffs.
                  // There is a loop over 255 characters (26 if you only count lower case letters).
                  // This is constant and not dependant on the size of
                  // the input and thus is `1`

Code Review.

Using Namespace

Please stop doing this.

using namespace std;

Its a bad habit that will cause you grief one day. See every other C++ code review for a good explanation.

Pass by const reference

You are passing the parameters by value. This will cause both the vectors to be copied.

int calcDeletions(vector<int> a, vector<int> b) {

Since you don't modify the values it can be made simpler by passing a const reference of each parameter. Thus having no copy.

int calcDeletions(vector<int> const& a, vector<int> const& b) {

Prefer Pre Increment

            deletions++;
            ai++;

Yes. Yes. It makes no difference for integers. But it does no harm to use pre-increment on integers either. But again it's one of those habits you should get into. There are situations where it does make a difference so it's best to pre-increment and then it will always be correct (even if you change the types of your objects).

Prefer operator[] over at()

The difference between the two is that at() performs bounds checking.

    for (int i = 0; i < a.length(); i++) {
        aInt.push_back((int)a.at(i));
    }

In this context you are guaranteed that there is no out of bounds access as you are already checking that i is smaller than a.length(). Thus you are effectively doing the check twice.

Don't use C style casts.

C style casts are hard to spot.

 (int)a.at(i)
 ^^^^^

They are also extremely dangerous (they basically tell the compiler to shut up and do what you're told as I the programmer am god and know better than you the simple compiler). In reality this is usually wrong: the compiler always knows better than you and telling it to shut up is usually hiding an error message.

As a result, C++ has its own casts. There are actually four of them:

static_cast<>()
const_cast<>()
reinterpret_cast<>()
dynamic_cast<>()

Your above cast is actually best done by a static_cast<>()

static_cast<int>(a.at(i));

BUT There is no actual need to cast a char to an integer. This will happen automatically (as a char is an integer type the conversion is automatic) with no loss in precision.

Is there a need to put the largest first.

I don't see you taking advantage of this in the function above!

    // call calcDeletions function with the longer vector passed as first arg
    if (aInt.size() > bInt.size()) {
        return calcDeletions(aInt, bInt);
    }
    else {
        return calcDeletions(bInt, aInt);
    }

Looking at the Cool Shark implementation you provided it still has a couple of issues.

String wo1 = "fowl", wo2 = "owl", wo3 = "howl", wo4 = "low";

   HashMap<String, Integer> wo1Map = new HashMap<String, Integer>();
   HashMap<String, Integer> wo2Map = new HashMap<String, Integer>();
   HashMap<String, Integer> wo3Map = new HashMap<String, Integer>();
   HashMap<String, Integer> wo4Map = new HashMap<String, Integer>();
   wo1Map = convertToHashMap(wo1.toLowerCase());
   wo2Map = convertToHashMap(wo2.toLowerCase());
   wo3Map = convertToHashMap(wo3.toLowerCase());
   wo4Map = convertToHashMap(wo4.toLowerCase());

   HashSet<String> unionKeys = new HashSet<>(wo4Map.keySet());
   unionKeys.addAll(wo1Map.keySet());
   unionKeys.removeAll(wo4Map.keySet());
   System.out.println("remove letter"+unionKeys);

   HashSet<String> intersectionKeys = new HashSet<>();
   for(String i : wo1Map.keySet()) {
       for(String j : wo3Map.keySet()) {
           if( i.equals(j) )
                intersectionKeys.add(i);
       }
   }

   System.out.println("common letters "+intersectionKeys);


Largest prime factor function I have written a function which finds the largest prime factor of some number. This function works but the problem is that it is too slow. For instance, when I enter 600851475143 as a parameter, the process of finding largest prime factor lasts too long. How can I modify it so that it works faster?

class test {

static addArray(someArray, member) {
    for (var i = 0; i <= someArray.length; i++) {
        if (i == someArray.length) {
            someArray[i] = member;
            return someArray;
        }
    }
}
static someLength(someArray) {
    var i = 0;
    while (someArray[i] !== undefined) {
        var lastItem = i;
        i++;
    }
    return i;
}
static testPrime(i) {
    for (var k=2; k < i; k++) {
        if (i % k == 0) {
            return false;
        }
    }
    return true;
}
}

var primeArray = [];
function largestPrime(n) {
    for (var i=2; i < n; i++) {
        //var k = n / i;
        if (n % i == 0 && test.testPrime(i) == true) {
            test.addArray(primeArray, i);
            n == n / i;
        }
    }
    return primeArray[test.someLength(primeArray) - 1];
}

document.write(largestPrime(600851475143));

The algorithm can be improved. I took the liberty to use my existing Java, also as Python might be somewhat slower.

On the Python code: X == true should simply be X.

long largestPrimeFactor(long x) {
    long largest = 0;
    long n = x; // Remaining number where factors divided out.
    if (n % 2 == 0) {
        largest = 2;
        do {
            n /= 2;
        } while (n % 2 == 0);
    }
    for (int c = 3; c*c <= n; c += 2) {
        if (n % c == 0) {
            largest = c;
            do {
                n /= c;
            } while (n % c == 0);
        }
    }
    // Wrong: return largest == 0 ? x : largest;
    return n > 1 ? n : largest;
}

The loop searching for factors handles 2 before the loop and then loops from 3 with steps of 2.

    for (int c = 3; c*c <= n; c += 2) {

In every loop step, if c is a factor of n, n is divided by c as often as possible. In fact n has no longer smaller factors than c.

Hence c is a prime, and in fact the largest found prime upto then.

If after the loop no largest prime was found, the parameter itself is a prime.

As n in every step is divided by all smaller factors, you need only to loop while c <= n / c holds: the second c being the smallest co-factor of n for c. Together with += 2 this hugely decreases the number of steps.

Your extra test on the factor being prime is the largest slow-down, as it does not exploit the factor filtering till then.

[Ported from SO]

Alright, before we go into that, let's get a little bit of theory sorted. The way you measure the time a particular piece of code takes to run is, mathematically, denoted by the O(n) notation (big-o notation) where n is the size of the input.

Your test prime function is of something called linear complexity meaning that it'll become linearly slow as the size of n (in this case, your number input) gets large.

For the number 15, the execution context is as follows:

15 % 2 == 0 (FALSE)
15 % 3 == 0 (TRUE)
...
15 % 14 == 0 (FALSE)

This means that for the number 100, there will be 98 (2 - 99) steps. And this will grow with time. Let's take your number into consideration: 600851475143. The program will execute 600851475143; the for-loop will get triggered 600,851,475,141 times.

Now, let's consider a clock cycle. Say each instruction takes 1 clock cycle, and a dumbed down version of your loop takes 2, the number 600851475143 will execute 1,201,702,950,286 times. Consider each clock cycle takes 0.0000000625 seconds (for a 16-MHz platform such as the Arduino), the time taken by that code alone is:

0.0000000625 * 1201702950286 = ~75,106 seconds

Or around 20 hours.

You see where I am going with this.

Your best best to get this program to work faster is to use a probabilistic test and confirm your findings using this number (or a BigInteger variant thereof).

Your approach is more linear, in the sense that the number of iterations for the for-loop to check for primality increases with an increasing number. You can plot the CPU cycle time along with the number and you'll realize that this is a rather inefficient way to do this.

I have discrete mathematics at my Uni, so just a word of warning - primality tests and their variants get really messy as you get into the utopia of faster and faster tests. It's a path filled with thorns of mathematics and you should have a seat belt while riding through the jungle! ;)

If you need more information on this, I would be glad to assist! I hope this helped! :)


Find max in-order difference in array Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

If there is no solution possible, return 0.

Example :

A : [3 5 4 2]

Output : 2
for the pair (3, 4)

My Code :

def maximumGap(self, A):
    if len(A)==1: return  0
    a_list = sorted(([Val,indeX] for indeX,Val in enumerate(A)), reverse=True)

    rest = [indeX for val,indeX in a_list] # rest stores all the index from a_list which is sorted in decreasing order
    len_rest = len(rest)
    del a_list[:]
    results = []

    for i in range(len_rest):
        if i != len_rest-1:
            results.append(rest[i] - min(rest[i+1:]))
        else: continue

    ans = max(results)
    if ans < 0: return 0
    else: return ans

Sample input taken for explanation:

A = [34, 8, 10, 3, 2, 80, 30, 33, 1]

Brief summary of my algorithm:

1. a_list is a list of lists which will store all the numbers from the orginal list (list A) in sorted order along with their indexes.

`a_list = [[80, 5], [34, 0], [33, 7], [30, 6], [10, 2], [8, 1], [3, 3], [2, 4], [1, 8]]`

2. rest is a list which will store all the indexes from a_list.

`rest = [5, 0, 7, 6, 2, 1, 3, 4, 8]`

(After this, a_list is deleted to empty the space)

3. Now, the crux of the logic is:
Since list is sorted in descending order, I need not take care of the constraint: A[i] <= A[j]

I will just iterate the list: rest and in each iteration, say 0th iteration, rest[0] = 5 is subtracted from the smallest remaining elements in list: rest

Each result of the iteration is stored in list: results

4. results = [5, -1, 6, 5, 1, -2, -1, -4]

5. Max of list results will give me the answer.

(It is important to note that while sorting the list we must also store the original index of the values instead of blindly sorting it.)

Now, coming to the actual problem:

On submitting my solution at interviewbit website, my code is giving correct answers to all test cases but time limit is exceeded

I am not able to figure out what how to optimise this further.

Time complexity of my code,correct me if i am wrong, is O(N log N)

Sorting takes O(N log N) time in the worst case when using sort function in python.

My main question is how to optimise this code further?

Found on www.interviewbit.com

Actually in the last part, during the iteration over list named rest, its O(N^2), so, its not working.
Refer to Geeksforgeeks for O(n).