Basic expressive Swift background thread execution I created a basic background thread class in swift to replace the ugliness of:

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0)) { () -> Void in
  // background thread code
  dispatch_async(dispatch_get_main_queue()) { () -> Void in
      // done, back to main thread
  }
}

with the expressiveness of:

Background { () -> () in
    // background code
  }.afterInterval(3) { () -> () in
    // main thread, run after interval IF not done
  }.completion { () -> () in
    // done, main thread
  }

afterInterval and completion are optional and interchangeable.

How reliable is this approach? Can we ever return from init(task) before completion is added, using the dot syntax? I have tested to my abilities and it seems rather bulletproof, but am wondering about the thoughts here.

class Background {

  private var done = false {
    didSet {
      if done {
        taskInterval = nil
        dispatch_async(dispatch_get_main_queue()) { () -> Void in
          completion?()
        }
      }
    }
  }

  private var taskInterval: (() -> ())?
  private var completion: (() -> ())?

  init(task: () -> ()) {
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0)) { () -> Void in
      task()
      self.done = true
    }
  }

  func afterInterval(interval: NSTimeInterval, closure: () -> ()) -> Background {
    taskInterval = closure
    let delayTime = dispatch_time(DISPATCH_TIME_NOW, Int64(interval * Double(NSEC_PER_SEC)))
    dispatch_after(delayTime, dispatch_get_main_queue()) { [weak self] in
      self?.taskInterval?()
    }
    return self
  }

  func completion(closure: () -> ()) -> Background {
    completion = closure
    return self
  }

}

"SwiftyThreads" on Github

Yes, I see what you mean: there do appear to be dodgy race conditions. I do like where you are going with this, though – dot syntax and all. Still I found at least one failing test. If you paste your code in a playground and then add the following:

/* your code here */

import XCPlayground
XCPlaygroundPage.currentPage.needsIndefiniteExecution = true

var i = 0

Background {
    i += 1 // don't call `print` here!
}.afterInterval(0) {
    i += 10
}.completion {
    i += 100
}

let t = dispatch_time(DISPATCH_TIME_NOW, Int64(NSEC_PER_SEC))
dispatch_after(t, dispatch_get_main_queue()) {
    print(i)
}

// prints: 101 (instead of 111)

True, delay of 0 seems a little contrived, but it does prove that your worries are founded. One way around this is to trigger a dispatch of those closures on demand (and repeatedly):

import Foundation
class Background {
    let qos: qos_class_t
    let task: (() -> ())?
    private(set) var delay: NSTimeInterval? = nil
    private(set) var delayedTask: (() -> ())? = nil
    private(set) var completionHandler: (() -> ())? = nil

    init(_ qos: qos_class_t = QOS_CLASS_BACKGROUND, task: (() -> ())? = nil) {
        self.qos = qos
        self.task = task
    }

    func delay(interval: NSTimeInterval, task: () -> ()) -> Background {
        self.delay = interval
        self.delayedTask = task
        return self
    }

    func completion(task: () -> ()) -> Background {
        self.completionHandler = task
        return self
    }

    func async() {
        dispatch_async(dispatch_get_global_queue(qos, 0)) { // TODO: unnecessary if `task == nil`
            self.task?()
            if let delayedTask = self.delayedTask, let delay = self.delay {
                let t = dispatch_time(DISPATCH_TIME_NOW, Int64(delay * NSTimeInterval(NSEC_PER_SEC)))
                dispatch_after(t, dispatch_get_main_queue(), delayedTask)
            }
            if let completionHandler = self.completionHandler {
                dispatch_async(dispatch_get_main_queue(), completionHandler)
            }
        }
    }
}

Which can be used like so:

import XCPlayground
XCPlaygroundPage.currentPage.needsIndefiniteExecution = true

var i = 0

let bg = Background {
    i += 1
}.delay(0) {
    i += 10
}.completion {
    i += 100
}

// nothing dispatched yet!

bg.async() // repeated invocations possible
bg.async()

Background().delay(1) {
    print(i)
}.async()

// prints: 222 (as it should)

In addition, I would probably rename Background...


Algorithm Divisible Sum Pairs I did the Divisible Sum Pairs problem on HackerRank

  input: n is length of array ar, k is an integer value.
  a pair is define only if ar[i]+ar[j] is dividable by k where i < j.
  Problem: find and return pairs in array.

def divisibleSumPairs(n, k, ar):
    i=0       #pointer 1
    j=1       #pointer 2 is faster than p1
    count =0  #pointer 3 will only increment 1 once j = n-1 (second last element)
    pairs=0
    while count < n-1:
        if (ar[i]+ar[j])%k==0:
            pairs+=1
        j+=1
        count+=1
        if count==n-1:
            i+=1
            j=i+1
            count =i
    print(pairs)

Code visualized

step 1:
 i  j
[a][b][c][e][f]
compare (i,j)
 i     j
[a][b][c][e][f]
compare (i,j)
 i        j
[a][b][c][e][f]
compare (i,j)
 i           j
[a][b][c][e][f]
compare (i,j)
i+=1
j=i+1

step2
    i  j
[a][b][c][e][f]
compare (i,j)
        .
        .
        .
        .
step n
          i  j
[a][b][c][e][f]
compare (i,j)
finish

I have a couple of questions:

Does this algorithm have a name?
Is there other way (maybe better, faster)?
Is there some code I could have done better/ differently?

#some test  data n=6 , k=3 ar =[1, 3, 2, 6, 1, 2]

Your code is not Pythonic as it does not adhere to the standard Python style guide.

divisibleSumPairs should be snake case divisible_sum_pairs.
You should have one space both sides of most operators. i=0 i+=1, ar[i]+ar[j] are all harder to read than they need to be.
Most of your variable names don't describe what they contain.
You print inside a function that should return.

def divisible_sum_pairs(length, divisor, items):
    i = 0       #pointer 1
    j = 1       #pointer 2 is faster than p1
    count = 0   #pointer 3 will only increment 1 once j = n-1 (second last element)
    pairs = 0
    while count < length - 1:
        if (items[i] + items[j]) % divisor == 0:
            pairs += 1
        j += 1
        count += 1
        if count == length - 1:
            i += 1
            j = i + 1
            count = i
    return pairs

You don't need pointer 3 as count = j + 1:

j += 1
count += 1

j = i + 1
count = i

We can just replace count with j - 1.
We can simplify all of the places where count was being used.
This is as you have - 1s  on both sides of the operators.
Rather than while j < length it would be clearer if you instead used while i < length - 1.
This comes in two parts:

It is confusing to see while j < length with if j == length in the body.
You're not actually bound by j you're bound by i.

Rather than using a while loop we can see that there's an opportunity to use two for loops to make things easier to read.

Note: These for loops have the exact same time complexity as your while.

def divisible_sum_pairs(length, divisor, items):
    pairs = 0
    for i in range(length - 1):
        for j in range(i + 1, length):
            if (items[i] + items[j]) % divisor == 0:
                pairs += 1
    return pairs

We can simplify the code by using using a comprehension.

For example we can extract getting the combinations of items.

combinations = (
    (items[i], items[j])
    for i in range(length - 1)
    for j in range(i + 1, length)
)
for a, b in combinations:
    if (a + b) % divisor == 0:

We can instead sum with a comprehension that generates numbers.

pairs = sum(
    1
    for a, b in combinations
    if (a + b) % divisor == 0
)

We can exploit the fact that bools are integers and move the if's expression as the comprehension's expression.
We can use itertools.combinations to remove the need to manually get the combinations.

import itertools

def divisible_sum_pairs(_, divisor, items):
    return sum(
        (a + b) % divisor == 0
        for a, b in itertools.combinations(items, 2)
    )

Every change has been a 1 to 1 replacement. The time complexity is still \$O(\binom{n}{2})\$ (\$O(n^2)\$) and memory complexity is still \$O(1)\$.

However now readability is much better.


Simple media ingest script Trying to script a simple command line tool for ingesting media to a target location following a structured naming convention.

It's functional in its current state but I'd like to know if there are things to improve.

#!/usr/local/bin/bash

#make target directory for transfer

make_directory(){

    echo -e "\n\nFollow the prompt to create a project directory.\n\n"
    sleep .5

    while [[ -z "$target_directory" ]]
        do
                echo -e "Path of target directory?"
                read target_directory
        done

    while [[ -z "$brand" ]]
        do
            echo -e "\nBrand Prefix?"
            read brand
        done

    while [[ -z "$project" ]]
        do
            echo -e "\nProject Name?"
            read project
        done

    while [[ -z "$media_type" ]]
        do
            echo -e "\nMedia Type?"
            read media_type
        done

    while [[ -z "$location" ]]
        do
            echo -e "\nLocation?"
            read location
        done

    while [[ -z "$employee" ]]
        do
            echo -e "\nEmployee?"
            read employee
        done

    path=${target_directory}/$(date +'%Y%m%d')_${brand}_${project}_${media_type}_${location}_${employee}

    echo -e "\nCreating directory: ${path}\n\n"

    mkdir -p "${path}"

}

# construct rsync command

construct_rsync(){

    echo -e "\n\nFollow the prompt to construct the rsync command.\n\n"
    while [[ -z "$source_path" ]]
    do
        echo -e "Path to source media?"
        read source_path
    done

    if [[ "$option" == "2" ]]; then
        while [[ -z "$target_directory" ]]
        do
            echo -e "Target directory?"
            read target_directory
        done
    path=$target_directory
    fi

    while true;
    do
        read -p "Additional rsync options? [y/n] " rsync_add
        case $rsync_add in
            [Yy]* )
                echo -e "\nEnter additional rsync parameters:"
                read rsync_options
                break;;
            [Nn]* )
                break;;
            *) echo "Please enter y or no!"
        esac
 done

    echo -e "\nConstructing rsync command...\n"
    sleep .5
    echo -e "Running rsync command:\n
    rsync \n
    -r \n
    --info=progress2 \n
    --log-file=${path}/$(date +'%Y%m%d')_transfer_log.txt \n
    ${rsync_options} \n
    ${source_path}/ \n
    ${path} \n"

    rsync -r --info=progress2 --log-file="${path}/$(date +'%Y%m%d')_transfer_log.txt" ${rsync_options} "${source_path}/" "${path}"
}

# log exit code of rsync

log(){

    echo -e "\nCreating error log..."
    echo $? > "${path}/error_log.txt"

    sleep .5

    if [[ "$?" == "0" ]]; then
        echo -e "\nTransfer complete!"
    elif [[ "$?" != "0" ]]; then
        echo -e "\nError in transfer! Please refer to error_log.txt!"
    fi
}

# read user input and run appropriate functions

while true
do
read -p "Enter [1] to start an ingest or [2] to complete a partial ingest. " option

    case $option in

        1 )
            make_directory
            sleep .5
            construct_rsync
            sleep .5
            log
            break;;
      2 )
            construct_rsync
            sleep .5
            log
            break;;
      * )
            echo "Please enter a valid option!";;
    esac
done

Your code is pretty clear and readable. Congratulations!

Here are some suggestions:

Stop using sleep! Unless this is for a Hollywood hacker movie, it just slows things down. Nobody thinks delays are cool after the first three times you run something.
Take command-line arguments instead of prompting for everything. It's a lot easier to just put stuff into a command line than it is to respond to it at the keyboard. Something like:

ingest -t $HOME/media -b SONY -p "My Project"

There are plenty of SO answers on how to do this.
Add some more functions! Anything you find yourself doing twice should be a function. Also, anything that you have to "break the flow" in order to do should be a function. Here are some examples:

while [[ -z "$target_directory" ]]
    do
        echo -e "Path of target directory?"
        read target_directory
    done

while [[ -z "$brand" ]]
    do
        echo -e "\nBrand Prefix?"
        read brand
    done

That's twice! Write a function to do this:

target_dir=$(prompt_for_variable target_dir 'Path of target directory?')"
brand="$(prompt_for_variable brand 'Brand Prefix?')"

Now consider this:

while true;
do
    read -p "Additional rsync options? [y/n] " rsync_add
    case $rsync_add in
        [Yy]* )

Right in the middle of "construct_rsync" you stop and loop forever prompting the user for a y/n answer. Write a function for that!

if get_yn 'Additional rsync options?'
then
     read -p "Enter the additional options: " rsync_options
fi

Don't lie to anybody, especially yourself. You have a function called construct_rsync but what does it do? It runs the command. Either change the name, or change the function.
Beware of $?. In your log function you refer to it several times. But $? is updated each time a command is run. So if you're going to make decisions based on the value, you should either capture the value into a separate variable (status=$? ... if $status) or make a single decision right up front (if $? ... else ... fi)


"Fast strlen" in C using scalar bithacks I've translated an implementation of strlen in x86 assembly to C and added alignment checking:

#include <strings.h>
#include <string.h>
#include <stdint.h>

#define NOT_HIGH_MASK 0x080808080
#define HIGH_MASK 0x7f7f7f7f
#define LOW_MASK 0x01010101
#define mul4(x) ((x) << 2)
#define div8(x) ((x) >> 3)

size_t strlen(const char *str)
{
    const char *cptr = str;
    uint32_t i, *s;
    size_t ctr = 0;

    /* Satisfy alignment requirements */
    while((uintptr_t)cptr & (sizeof(uint32_t)-1))
    {
        if(!*cptr)
            return cptr - str;
        cptr++;
    }

    s = (uint32_t *)cptr;

    do {
        i = s[ctr];
        /* Mask off high bit */
        i &= HIGH_MASK;
        /* subtract 0x01 from each byte,
           giving a set high bit if it
           was zero */
        i -= LOW_MASK;
        ctr++;
            /* Test for the set high bit
               and if it is found exit */
    } while(!(i &= NOT_HIGH_MASK));

    /* Find the first high bit set and
       create the corresponding byte index */
    i = div8(ffs(i));
    /* Remove the counter increment from the
       loop and multiply it by 4 to find the
       rest of the byte index */
    ctr = mul4(ctr - 1);

    /* Return the combined byte index with 1
       removed so it doesn't include the null
       terminator itself */
    return i + ctr - 1;
}

I'm looking for general critique, but I'd also like additional information in these areas:

Portability. Is this portable? Will it work on all common platforms (x86, arm, etc.) and possibly some uncommon ones?
Comments. The comments I've put here seem to already document the code well enough, but is there any additional information I could add?
Hidden Bugs. This definitely works (and has a noticeable improvement in speed), but are there any hidden bugs relating to alignment requirements or otherwise (such as extended ASCII)? For context, this is part of a standard C/POSIX library implementation.

I might note that I'm relying on my header to use the builtin version of ffs. This may be an issue on non-GNU compilers.

If a GCC-compatible compiler (gcc, clang, icc, etc.) is detected during the build process, the flags -std=gnu99 -O2 are appended to the build flags.

Bug

strlen("\x80\x80\x80\x80\x80\x80\x80") does not return the expected 7.  The do loop does not distinguish between '\0' and '\x80'.

strlen("\x80\x80\x80") returns 0, 1, 2  or 3 depending on alignment.

These render  the function broken.

Why int32_t?

Certainly int32_t* marches down the sting at a 4x clip rather than a plodding char *.  Yet for a 16-bit int machine, int32_t* may be slower.  For a 64-bit machine, int64_t* could even be faster.   I'd expect a unsigned * to work fast or even fastest.  I guess that is why strlen() is a library function - each implementation is expected to use its own optimal approach.

Minor: Clearly use unsigned mask constants

With bit masking, shifts and subtraction, using unsigned math has less review concerns.

0x01010101 --> 0x01010101u.

Portability

while(... & (sizeof(uint32_t)-1)) is a reasonable alignment test but not a specified correct one.  Conversion of a pointer to an integer need not follow the usual linear expectations.  I do not know of any implementation where this will not work, but it is not C specified.

Notes:
uint32_t is an optional type.  A unicorn platform may not have it defined.
uintptr_t is also an optional type.

Could use something like

#include <stdint.h>
#ifndef UINTPTR_MAX
  #error "You are kidding me? An implementation without uintptr_t!"
#endif

Comment nit

Mask off high bit should be "Mask off high bits" or "Mask off each byte high bit", ...

/* Mask off high bit */
i &= HIGH_MASK;


Basic Word Counter in C Working on a C programming question where I have to write a function which will determine how many words are in a given string. Assume that one or more consecutive white spaces is a delimiter between words, and that the string you pass to your function is null terminated.

Have to use pointers and only the #include(stdio.h) library. Wondering how this can be improved upon or if there are any possible errors. Here it is:

#include <stdio.h>
int word_counter(char string[])
{
  //We start with first word unless we have a empty string then we have no words
  int count;
  if(*string!='\0'){
    count=1;
}
  else{
    count=0;
    return 0;
  }
  //while we dont reach the end of the string
  while(*string!='\0'){
    //if we detect a whitespace
    if(*string==' '){
      //get previous character
      string--;
      // If previous character is not a space we increase the count
      // Otherwise we dont since we already counted a word
      if(*string!=' '){
        count++;
      }
      //return pointer to current character
      string++;
    }
    // set pointer to next character
    string++;
  }
  return count;
}

//just to test if it works
int main(void)
{
    char str[] = "Hello World!";
    printf("How many words? = %i\n", word_counter(str));
    return 0;
}

isspace

There are other characters besides for spaces. What happens if I do:

Hello<tab><tab>world!

Your code will report that there is one word. I would rewrite these:

if(*string==' '){
  //get previous character
  string--;
  // If previous character is not a space we increase the count
  // Otherwise we dont since we already counted a word
  if(*string!=' '){
    count++;
  }

You should instead use isspace for these kind of things. ' ' is for explicitly a space.

Indentation

Fix your indentation. Your main uses 4 spaces, your word_counter uses (maybe?) 2. Be sure that it is consistent. Choose one or the other.

Empty case rework

(Actually, as @200_success points out you don't need this corner case. I'm going to leave this up here though, because sometimes you will get cases like this and you should consider reworking them if they appear awkward)

Your empty corner case can be reworked:

  int count;
  if(*string!='\0'){
    count=1;
}
  else{
    count=0;
    return 0;
  }

First you don't need to set count = 0 if you just return immediately. I would restructure you if statement to be:

if (*string == '\0') {
    return 0;
}

And from there continue with:

int count = 1;

This means we don't leave count uninitialized either.


Cache wrapper - Generics vs Dynamic I've implemented a common wrapper pattern I've seen for the .NET cache class using generics as follows:

private static T CacheGet<T>(Func<T> refreashFunction, [CallerMemberName]string keyName = null)
{
    if (HttpRuntime.Cache[keyName] == null)
        HttpRuntime.Cache.Insert(keyName, refreashFunction(), null, DateTime.UtcNow.AddSeconds(600), System.Web.Caching.Cache.NoSlidingExpiration);
    return (T)HttpRuntime.Cache[keyName];
}

It could then be called like so:

public static Dictionary<string, string> SomeCacheableProperty
{
    get
    {
        return CacheGet(() =>
        {
            Dictionary<string, string> returnVal = AlotOfWork();
            return returnVal;
        });
    }
}

However, the CacheGet method could be implemented using dynamic:

private static dynamic CacheGet(Func<object> refreashFunction, [CallerMemberName]string keyName = null)
{
    if (HttpRuntime.Cache[keyName] == null)
        HttpRuntime.Cache.Insert(keyName, refreashFunction(), null, DateTime.UtcNow.AddSeconds(600), System.Web.Caching.Cache.NoSlidingExpiration);
    return HttpRuntime.Cache[keyName];
}

The questions I have:

Is there a technically (or philosophically) superior preference between these two implementations?
Are these different at runtime?
If they are both left in, which one is being called in the getter method?

First of all, I think you misspelled refresh as refreash.
Second, your usage can probably be simplified
CacheGet(AlotOfWork);

Finally, you might want to check if refreshFunction returns null and maybe log a warning then as that function returning null would cause a cache miss every time.
Now to answer your specific questions.

I'll say it, the generic implementation is better. dynamic is a great trapdoor when you get really bogged down with generics or anonymous types and there's neat things you can do with it (see Dapper) but it still has some gotchas. For example, I do not think your function with dynamic will work in most cases.
HttpRuntime.Cache expects and returns object types meaning all types are being downcast or boxed. Therefore, if your function returns a User object, what is stored is still an object and what is returned from the cache is downcast likewise. Therefore your user.Username property will not be available until you cast, even though it's dynamic.

Yes. The generic version - with some subtle yet real differences - will run as if it was written for the type you're filling <T> with. The dynamic version will just be a "value" and let the DLR figure out how to invoke members (which again, unless you're calling ToString() or GetHashCode(), will fail). dynamic will also be slower as the runtime binding has to be done every time, though admittedly this is unlikely to be any sort of bottleneck.

Obviously I'm going to say always use the generic version in this case.


Can I always use variable-length argument lists instead of arrays in argument types whenever is a choice? I changed the withColumns() method in this class:

public static class Options {
    public String table;
    public String[] columns;

    public Options withTable(String table) {
        this.table = table;
        return this;
    }

    public Options withColumns(String[] columns) {
        this.columns = columns;
        return this;
    }
}

so it receives variable-length argument list instead of array:

    public Options withColumns(String... columns) {
        this.columns = columns;
        return this;
    }

Now I can write both:

new Options().withColumns(SubjectContract.TITLE, SubjectContract.PHOTO);

and

new Options().withColumns(new String[] { SubjectContract.TITLE, SubjectContract.PHOTO });

But of course, withColumns(SubjectContract.TITLE, SubjectContract.PHOTO) is more readable.

So are there any disadvantages in declaring argument type as a variable-length argument list, not array, whenever is a choice?

so basically it is your choice :

with optional params you cannot enforce user to input the value, so user can leave giving any input and complier will not complain.

new Options().withColumns();

with list of string , you need to give at least one value , value can be null.

new Options().withColumns(null);

so it all depends upon your use case.In this case table will always have columns so passing a array of column will make sense.


Small program to download wikipedia articles to pdf I made a small app to download wikipedia articles (and optionally those that it links to) as PDFs to take on the go.  I'd eventually like to do a text-to-speech option and save the article as an mp3, though that's the next step.  Any thoughts would be helpful.

import wikipedia
import pdfkit
import os
from gtts import gTTS

class Page:

    def __init__(self):
        """Set default pdfkit options"""
        self.pdfOptions = {
            'page-size': 'Letter',
            'margin-top': '0.75in',
            'margin-right': '0.75in',
            'margin-bottom': '0.75in',
            'margin-left': '0.75in',
            'javascript-delay' : 2000,
            'minimum-font-size': 512
        }

        self.targetDir = os.path.dirname(os.path.realpath(__file__))
        self.includeLinks = False

    def getArticle(self, articleTitle):
        """fetch the article from wiki by title"""
        self.page = wikipedia.page(articleTitle)
        try:
            self.page.summary
        except wikipedia.exceptions.DisambiguationError as e:
            print "Multiple articles with that name: " + e.options

    def setURL(self,URL):
        """fetch the article by URL"""
        pass

    def download(self):
        """download the article (and maybe the articles it links to"""
        if self.includeLinks == False:
            filename = self.targetDir+"/"+self.page.title+'.pdf'
            pdfkit.from_url(self.page.url, filename, options = self.pdfOptions)
        else:
            for link in self.page.links:
                linkedPage = wikipedia.page(link)
                print "Downloading " + linkedPage.url
                filename = self.targetDir+"/"+linkedPage.title+'.pdf'
                pdfkit.from_url(linkedPage.url, filename, options=self.pdfOptions)

    def speak(self):
        pass

Here are some stylistic and code style points:

fix the variable naming - in Python, there is a lower_case_with_underscores variable naming style (PEP8 reference)
organize your imports as per PEP8 guidelines - first, the system-level imports, then third-parties, then your "local" imports. Also, remove unused from gtts import gTTS import:

import os

import pdfkit
import wikipedia

docstrings should start with a capital letter and end with a dot
I think you should define pdfOptions as a module-level (or configuration-layer-level) constant instead of having them defined as an instance variable
if self.includeLinks == False: can be simplified to if not self.includeLinks:
you should have spaces around the operators inside expressions (reference)
I think you can handle both cases in your download() method in a unified way:

def download(self):
    links = self.page.links if self.includeLinks else [self.page]
    for link in links:
        page = wikipedia.page(link)
        print("Downloading " + page.url)
        filename = self.targetDir + "/" + page.title + '.pdf'
        pdfkit.from_url(page.url, filename, options=self.pdfOptions)

I would also use os.path.join() instead of string-concatenating filename paths


Check if the undirected graph is cyclic Here is my approach. Do DFS and check in stack whether the new node is already in the Stack or not.

public static boolean isCyclicDFS(int[][] adjMat) {
        int len = adjMat.length;
        boolean[] isVisited = new boolean[len];
        for(int i =0; i<len; i++) {
            isVisited[i] = false;
        }

        Stack s = new Stack<>();
        s.add(0);

        while(!s.isEmpty()) {
            int current = (int) s.pop();
            System.out.println(current);
            isVisited[current] = true;
            for(int i =0; i<len; i++) {
                if(adjMat[current][i] ==1 && isVisited[i] == false) {
                    if(s.contains(i)) {
                        return false;
                    }
                    s.push(i);
                    break;
                }
            }

        }
        return true;

    }

Kindly suggest if any improvement/correction.

Formatting

Your spacing is inconsistent, which makes the code harder to read. By the original conventions released with the language, =, ==, and < should have a whitespace character on either side. Whatever you choose, make it consistent.

Implementation

Your System.out.println is for debugging and should be removed.

Use Arrays.fill() to populate your array.

Declaring len makes the code harder to read. Just refer to the length in your for loop.

As @Marc-Andre said, prefer a Deque to a Stack. And use generics.

Don't do if (foo == false). Use if (!foo).

I'm in the minority, but I prefer explicit boxing rather than autoboxing for clarity.

Don't use abbreviations for variable names. The extra characters enhance readability and cost nothing.

If it's in your control, for a non-weighted graph the adjacency matrix should probably be a boolean[][], not an int[][]. If this is a weighted graph, checking if the value == 1 is almost certainly a bug.

Correctness

You detect a cycle in this graph: { { 0, 1 }, { 1, 0 } }. Is it really a cycle if any two nodes are adjacent to each other? Is this an unweighted directed graph?

You also detect a cycle in this graph: { { 0, 1 }, { 0, 0 } }. Surely that is not correct. Please test before posting. CodeReview is for reviewing working code, not fixing broken code.


Inner join with first result In SQL Server, there is two tables: Houses, and their images.

I need a list with 20 houses with the first of their images (only one). I tried:

SELECT top 20 h.id, h.name, im.id, im.name
        FROM image im
        INNER JOIN house h ON im.house_id = h.id
        WHERE 1=1 AND im.id=(SELECT TOP (1) im2.id FROM image im2 WHERE im.id=im2.id ORDER BY image_code)

but that runs very slowly. There is any way to improve this query?

EDIT:

With the query:

SELECT   h.id, h.name, im.id, im.name  --  What you want to select
FROM     _house h, _image im              --  Tables in join
WHERE    h.id = im.id_house            --  The join (equivalent to inner join)
GROUP BY h.id                          --  This compresses all entries with the
                                       --  same h.id into a single row
HAVING   im.id =  min(im.id)           --  This is how we select across a group
                                       --  (thus compressing the image table per house)

I'm getting a error message:

_image.id' is invalid in the HAVING clause because it is not contained in either an aggregate function or the GROUP BY clause.

Then, I change to:

SELECT   h.id, h.name, im.id, im.name  --  What you want to select
FROM     _house h, _image im              --  Tables in join
WHERE    h.id = im.house_id            --  The join (equivalent to inner join)
GROUP BY h.id,im.id, h.name, im.name                          --  This compresses all entries with the
                                       --  same h.id into a single row
HAVING   im.id =  min(im.id)

And then I get this result:

How can I take out the repeated values?

EDIT2:

If somebody want to test the queries, this is the script to create the tables and the data that I'm using now (the real data is about 1Million rows):

CREATE TABLE _house(
    [id] [int] NOT NULL,
    [name] [varchar](50) NULL
)

CREATE TABLE _image(
    [id] [int] NULL,
    [name] [varchar](50) NULL,
    [house_id] [int] NULL
)

insert into _house (id, name) values (1,'house1');
insert into _house (id, name) values (2,'house2');

insert into _image (id, name, house_id) values (31,'img1',1);
insert into _image (id, name, house_id) values (32,'img2',2);
insert into _image (id, name, house_id) values (33,'img3',2);
insert into _image (id, name, house_id) values (34,'img4',2);

You should be using the clause group by

SELECT   h.id, h.name, im.id, im.name  --  What you want to select
FROM     house h,image im              --  Tables in join
WHERE    h.id = im.house_id            --  The join (equivalent to inner join)

GROUP BY h.id                          --  This compresses all entries with the
                                       --  same h.id into a single row
HAVING   min(im.id)                    --  This is how we select across a group
                                       --  (thus compressing the image table per house)

LIMIT    20;                           --  Selecting the first n values is very
                                       --  DB specific on mysql use the limit clause
                                       --  But I see in your DB it is `top 20`

Note:

Accosding to this page: http://developer.mimer.com/validator/parser200x/index.tml#parser

The having clause is more standard when specified like this (though I can't test this).

HAVING   im.id = min(im.id)

Edit (Based on question Edit).

Your problem is this line:

GROUP BY h.id, im.id, h.name, im.name

This means for every line that is unique across all four values will be compressed together (ie if all four values are the same the lines are compressed together). You need to maintain the original GROUP BY clause (and fix another part of the query).

GROUP BY h.id

I can't test this as I only have MySQL available and you seem to be using an MS product (and my original query worked on MySQL). But based on the error message:

  *_image.id' is invalid in the HAVING clause because it is not contained in either an aggregate function or the GROUP BY clause.*

We don't want to add anything to the GROUP BY clause. Thus following the error message indicates we need to use aggregate functions (in the select probably).

Try changing the select:

SELECT   h.id, h.name, min(im.id), im.name
                       ^^^^^^^^^^

I am sure if you play around with this you should be able to get it working. Sorry I can not be more exact but that would require using the same product as you.


SHA256 password hash generation and verification I would like to optimise this code. It seems a bit verbose, particularly with the 'elseif' that doesn't do anything.

This code either:

takes a plain text password, generates a salt, and returns them both OR
takes a plain text password and a salt with which to encrypt the password, and returns them both (even though the salt has already been supplied).

class Member extends ActiveRecord\Model {

private function process_password($password, $salt = '') {
    /**
     * Process a password to encrypt it for storage or verification.
     * @param string - plain text password for processing.
     * @access private
     * @return array Containing the encrypted password and the salt.
     */

    //Check if the salt has been supplied. If not, generate one.
    if (!$salt) {
        $salt = bin2hex(mcrypt_create_iv(32, MCRYPT_DEV_URANDOM));
    } elseif ($salt && strlen($salt) == 64)  {
        //Do nothing, the salt has already been supplied here.
    } else {
        log_message('info', 'Supplied password to process_password() was not the correct 64-byte length.');
        return false;
    }

    $hashed_password = hash('sha256', $password.$salt);

    return array('password' => $hashed_password, 'salt' => $salt);

}
}

How about the following:

if (!$salt) {
    $salt = bin2hex(mcrypt_create_iv(32, MCRYPT_DEV_URANDOM));
} elseif (strlen($salt) !== 64)  {
    log_message('info', 'Supplied password to process_password() was not the correct 64-byte length.');
    return false;
}
// if we're here, we have a valid salt

Improvements

Removed $salt from second condition (already known to be TRUE)
Flipped length logic, moved else code into second block
Removed empty condition block


Increase performance of a spate of 2x2 matrix multiplication I would like to improve the performance of the piece of code below (in Fortran). It gives good results but the profiling tells me that it is where it spends most of its running time.

Basically, it increments over a time window (j loop) and performs a spate of 2x2 matrix multiplications. I was wondering where I can refactor it to make it much more efficient. For instance, is there a smarter and faster way to initialise the identity matrices?

do j=1,nb_pts_t + 1
   t = t + dt
   ! Compute Zgates for all pairs in up/down states
   call Z_gate (eigen_ener_up, t / dble(2 * CP_seq), Zgate_u)
   call Z_gate (eigen_ener_down, t / dble(2 * CP_seq), Zgate_d)

   ! Initialize identity matrices
   Tfu%elements(1,1) = dcmplx(1.d0, 0.d0)
   Tfu%elements(1,2) = dcmplx(0.d0, 0.d0)
   Tfu%elements(2,1) = dcmplx(0.d0, 0.d0)
   Tfu%elements(2,2) = dcmplx(1.d0, 0.d0)
   Tfd%elements(1,1) = dcmplx(1.d0, 0.d0)
   Tfd%elements(1,2) = dcmplx(0.d0, 0.d0)
   Tfd%elements(2,1) = dcmplx(0.d0, 0.d0)
   Tfd%elements(2,2) = dcmplx(1.d0, 0.d0)

   ! work out transition matrices in up/down states
   ! and compute the decoherence
   do i=1,nb_pairs
      ! rotate to eigenbasis and propagate
      Tu(i)%elements = matmul(Zgate_u(i)%elements, matrot_u(i)%elements)
      ! rotate back to bath basis
      Tu(i)%elements = matmul(matrottrans_u(i)%elements, Tu(i)%elements)
      ! Idem down state
      Td(i)%elements = matmul(Zgate_d(i)%elements, matrot_d(i)%elements)
      Td(i)%elements = matmul(matrottrans_d(i)%elements, Td(i)%elements)

      ! Initialize Tud and Tdu
      Tud(i)%elements = matmul(Tu(i)%elements, Td(i)%elements)
      Tdu(i)%elements = matmul(Td(i)%elements, Tu(i)%elements)

     do k=1,CP_seq
         if(modulo(k, 2) .ne. 0) then
            Tfu(i)%elements = matmul(Tfu(i)%elements, Tud(i)%elements)
            Tfd(i)%elements = matmul(Tfd(i)%elements, Tdu(i)%elements)
         else if(modulo(k, 2) == 0) then
            Tfu(i)%elements = matmul(Tfu(i)%elements, Tdu(i)%elements)
            Tfd(i)%elements = matmul(Tfd(i)%elements, Tud(i)%elements)
         end if
      end do

      ! Decoherence from initial |down-up> bath state
      L_pairs(i) = abs(conjg(Tfd(i)%elements(1, 1))*Tfu(i)%elements(1, 1) &
           - Tfd(i)%elements(1, 2) * Tfu(i)%elements(2, 1))

      ! average over the bath states
      L_pairs(i) = 0.5d0 + 0.5d0 * L_pairs(i)
   end do

   ! Final decay as the product over all pair decays
   L = product(L_pairs)

   ! write the output
   write(16, fmt)t, L

end do

Leave matmul in
You can test the speed of matmul versus do-loops versus dot_product for any size arrays via the program found in this SO question. You can test this with any compiler and optimization you want, but the results are that any matrix of size < 50 (probably more, but I didn't test it higher than that), the three methods are identical in execution time.

Identity matrix initialization
This can be done with vector assignment and a simple loop

Tfu(i)%elements(:,:) = cmplx(0d0, 0d0)
do k=1,2
   Tfu(i)%elements(k,k) = cmplx(1d0,0d0)
end do

While Fortran defaults the imaginary component to zero when the 2nd argument is not present (e.g., cmplx(1d0)), it is probably better to be more clear by including it. Note that this won't change the run time, but it will make the declaration more compact.

Time variable in call to Z_gate
AFAIK, when there is math to be done in subroutine calls, Fortran will make a temporary copy of that variable. While it isn't much space for a double precision variable, you should still declare a new variable t_temp=t / dble(2 * CP_seq) and use that in place of your function call, especially since the math is done twice in subsequent calls to Z_gate.

It might also be worth declaring a new variable outside the j-loop

cp_seq_inv = 1d0/dble(cp_seq)

and making use of it as

t_temp = t * 0.5 * cp_seq_inv

As multiplication is faster than division, computing the inverse once (or at least once per call to this subprogram) should shave off some time.

Looping over k
Another thing to consider is that you have do loop increments at your disposal. That is to say, you can write your do k=1,CP_seq loop as

do k=1,CP_seq,2
! odd step
   Tfu(i)%elements = matmul(Tfu(i)%elements, Tud(i)%elements)
   Tfd(i)%elements = matmul(Tfd(i)%elements, Tdu(i)%elements)
! even step
   Tfu(i)%elements = matmul(Tfu(i)%elements, Tdu(i)%elements)
   Tfd(i)%elements = matmul(Tfd(i)%elements, Tud(i)%elements)
end do

Rather than wasting any time testing the two cases, do both in order and increment k by 2.


remove all nodes with same value in a linked list Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

The following is my code:

ListNode *getNextElement(ListNode *head, bool& repeated){
    while ((head->next) != NULL &&
            (head->val == head->next->val)){
        head = head->next;
        repeated = true;
    }

    return head->next;
}

ListNode *deleteDuplicates(ListNode *head) {
    ListNode *result = NULL;
    ListNode *copy_result = result;
    ListNode *next = NULL;

    for (ListNode *cur = head; cur != NULL; cur = next){
        bool cur_repeat = false;
        next = getNextElement(cur, cur_repeat);

        if (cur_repeat == true){
            while(cur!=next){
                ListNode *toFree = cur;
                cur = cur->next;
                delete toFree;
            }
        }
        else{
            if(result == NULL){
                result = cur;
                copy_result = result;
            }
            else{
                result->next = cur;
                result = result->next;
            }
        }
    }

    if(result != NULL)
        result->next = NULL;
    return copy_result;
}

Iterate through the list and remember the pointer to the first element in the group node. Then check if the current element has the same value as the first element in the group. Remove the current element and set some flag to remember to remove the first element in this group. Then if you have a new value, set the first element pointer to this value and do it all over again.


Alternate checked between buttons I'm trying to alternate if a button is checked. I've come up with this, which works but its feels unnecessary to write 70 lines of code for such a simple task.

How would I go about to shorten this up, is there any way I can call the base toolStripButton and tell it to uncheck other buttons when clicked on and check it self?

private void toolStripButton1_Click(object sender, EventArgs e)
{
    if (toolStripButton1.Checked == true)
    {
        toolStripButton2.Checked = false;
        toolStripButton3.Checked = false;
        toolStripButton4.Checked = false;
        toolStripButton5.Checked = false;
        toolStripButton6.Checked = false;
    }
}
private void toolStripButton2_Click(object sender, EventArgs e)
{
    if (toolStripButton2.Checked == true)
    {
        toolStripButton1.Checked = false;
        toolStripButton3.Checked = false;
        toolStripButton4.Checked = false;
        toolStripButton5.Checked = false;
        toolStripButton6.Checked = false;
    }
}

private void toolStripButton3_Click(object sender, EventArgs e)
{
    if (toolStripButton3.Checked == true)
    {
        toolStripButton1.Checked = false;
        toolStripButton2.Checked = false;
        toolStripButton4.Checked = false;
        toolStripButton5.Checked = false;
        toolStripButton6.Checked = false;
    }
}

private void toolStripButton4_Click(object sender, EventArgs e)
{
    if (toolStripButton4.Checked == true)
    {
        toolStripButton2.Checked = false;
        toolStripButton3.Checked = false;
        toolStripButton1.Checked = false;
        toolStripButton5.Checked = false;
        toolStripButton6.Checked = false;
    }

}

private void toolStripButton5_Click(object sender, EventArgs e)
{
    if (toolStripButton5.Checked == true)
    {
        toolStripButton2.Checked = false;
        toolStripButton3.Checked = false;
        toolStripButton1.Checked = false;
        toolStripButton4.Checked = false;
        toolStripButton6.Checked = false;
    }
}

private void toolStripButton6_Click(object sender, EventArgs e)
{
    if (toolStripButton6.Checked == true)
    {
        toolStripButton2.Checked = false;
        toolStripButton3.Checked = false;
        toolStripButton1.Checked = false;
        toolStripButton5.Checked = false;
        toolStripButton4.Checked = false;
    }

}

Yes, this can easily be achieved with a few non-redundant lines.

You can hook up all button clicks to this common MouseDown event:

private void toolStripButton_MouseDown(object sender, MouseEventArgs e)
{
    ToolStripButton button = sender as ToolStripButton;
    if (button == null) throw new InvalidCastException();
    foreach (ToolStripItem item in button.Owner.Items)
    {
        if (item is ToolStripButton)
        {
            ((ToolStripButton)item).Checked = (item == button);
        }
    }
}

Note that the Click event doesn't allow you to find out which button was clicked as all button clicks map to the ToolStrip itself! Therefore it doesn't lend itself to any sort of common processing that makes use of the sender paramter all events have..

As ever so often MouseDown works much better ;-)

The logic above assumes you want a radiobutton-like behaviour. RadioButtons can only be switched on; to switch them off you need to click another RadioButton in the group. If you want to be able to switch a button on and off directly you can expand it a little..


What is the shortest snippet that emulates `include` in JavaScript without third-party scripts? JavaScript doesn't offer a module system. There are many third-party solutions, like require.js or jQuery's $.getScript. Most, while good, they bring dependencies, extra kbs and/or limit your folder structures. Sometimes it's necessary to make a .js file self-sufficient. This said, what is the smallest snippet that can be inserted at the top of a .js file, which will emulate "import", so it can load other scripts before running itself?

The .js file should look like this, for example. Notice the addition is just a small one-liner:

(function(i,m,p,o,r,t){for(p=i.length,o=0;o<p;++o){r=(t=document).createElement('script');r.src=i[o];r.onload=function(){!--p&&m()};t.head.appendChild(r); }; })
(['http://ajax.googleapis.com/ajax/libs/jquery/1.8.3/jquery.min.js','http://underscorejs.org/underscore-min.js'],
function main(){
    console.log('jQuery loaded:',$);
    console.log('underscore.js loaded:',_);
});

For clarity, the top function above, expanded, is equivalent to:

(function (u, f, l, i, a, d) {
        for (l = u.length, i = 0; i < l; ++i) {
            a = (d = document).createElement('script');
            a.src = u[i];
            a.onload = function () {
                !--l && f()
            };
            d.head.appendChild(a);
        };
    })

Can this be minimized even further?

Here is what I do:

var a_script= document.createElement('script');
a_script.src = 'http://www.blah.com/some_script.js';
document.head.appendChild(a_script);

I should mention that in production I pretty much always combine all javascript files into one larger, minified, and google closure compiled file.


Unresolved External Symbol C++ I need to use sockets from winsok2.h. So, I written a class NetObject to use it. But, when I do compilation I am getting an error:

error LNK2019: unresolved external symbol "public: int __thiscall wsa::NetObject::connect(void)" (?connect@NetObject@wsa@@QAEHXZ) referenced in function _main

I do this using Visual C++ compiler.

Here is some code:

//wsa.h
#ifndef WSA_H_
#define WSA_H_

#include <winsock2.h>

namespace wsa {

sockaddr_in init(const int, const char *, const int);
sockaddr_in init(const int, const char *);
SOCKET init(const int, const int, const int);

class NetObject {
private:
    SOCKET sock;
    sockaddr_in addr;
    int check(const int);
public:
    NetObject
        (
            const int addr_family,
            const int sock_type,
            const int protocol,
            const char * ip_addr,
            const int port
        ): sock(init(addr_family, sock_type, protocol)),
           addr(init(addr_family, ip_addr, port)) {};
    int connect();
};
}

#endif //WSA_H_

//wsa.cpp
#include "wsa.h"
#include <winsock2.h>

namespace wsa {

sockaddr_in init(const int af, const char * ip_addr) {
    sockaddr_in addr;
    memset(&addr, 0, sizeof(addr));
    addr.sin_family = af;
    addr.sin_addr.s_addr = inet_addr(ip_addr);
    return addr;
}

sockaddr_in init(const int af, const char * ip_addr, const int port) {
    sockaddr_in addr = init(af, ip_addr);
    addr.sin_port = htons(port);
    return addr;
}

SOCKET init
    (
        const int af,
        const int type,
        const int protocol
    ) {

    SOCKET s;
    s = socket(af, type, protocol);
    while (s == INVALID_SOCKET) {
        if (closesocket(s) == SOCKET_ERROR) {
            return INVALID_SOCKET;
        }
        s = socket(af, type, protocol);
    }
    return s;
}

inline int NetObject::check(const int code) {
    if (code == SOCKET_ERROR) {
        if (closesocket(sock) == SOCKET_ERROR)
            return 1;
        return SOCKET_ERROR;
    }
    return 0;
}

inline int NetObject::connect() {
    int res = ::connect(sock, (sockaddr *)&addr, sizeof(addr));
    return check(res);
}
}

//main.cpp
#include "wsa.h"
#include <winsock2.h>

const int af       = AF_INET;
const int type     = SOCK_STREAM;
const int protocol = IPPROTO_TCP;

int main(int argc, char * argv[]) {

    WSADATA ws;
    if (WSAStartup(MAKEWORD(2, 0), &ws) == -1) {
        return 1;
    }

    wsa::NetObject server(af, type, protocol, argv[1], 80);
    server.connect();
    WSACleanup();
}

I can't see any errors. Please, help!

Thats because in Visual Studio, including winsock2.h to your headers is not enough. You have to tell the Linker your project will need the library wsock32.lib.

You can do that either by editing the properties of your project, or by including this line to your code:

#pragma comment(lib, "wsock32.lib")


Determining the largest sum of contiguous integers in a list I'm curious how I can improve the readability of this short program I wrote. Mainly, if and how there is a way to remove the for loops and maybe refactor the getTruncatedSubListsOf methods to one method since they are pretty similar. I tried using comments only when clarification was necessary.

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

import static java.util.Arrays.asList;
import static java.util.stream.Collectors.toList;

/**
 *  A program to determine the largest sum of contiguous integers in a list.
 *  The first argument is a path to a filename containing a comma-separated list of integers, one per line.
 *  The largest sum is printed to stdout. In other words, of all the possible contiguous subarrays for a given array,
 *  the one with the largest sum is found and printed.
 */
public class SumOfIntegers {

    public static void main(String[] args) throws IOException {

        Files.newBufferedReader(Paths.get(args[0])).lines()
                                                    .map(SumOfIntegers::turnToIntegerList)
                                                    .map(SumOfIntegers::getAllContiguousSubarrays)
                                                    .map(SumOfIntegers::getSumsOfSubarrays)
                                                    .mapToInt(Collections::max)
                                                    .forEach(System.out::println);
    }

    private static List<Integer> turnToIntegerList(String line) {

        return asList(line.split(",")).stream()
                                      .map(Integer::valueOf)
                                      .collect(toList());
    }

    /**
     * Returns all possible contiguous subarrays for a given List. This method calls getEndTruncatedSubListsOf each
     * different frontTruncatedSubList, yielding all possible front and end truncated lists - which are all subarrays.
     * @param integerList A List containing Integer values.
     * @return A List of all subarrays as Lists.
     */
    private static List<List<Integer>> getAllContiguousSubarrays(List<Integer> integerList) {
        List<List<Integer>> result = new ArrayList<>();

        for (List<Integer> frontTruncatedSubList : getFrontTruncatedSubListsOf(integerList)) {
            result.addAll(getEndTruncatedSubListsOf(frontTruncatedSubList));
        }

        return result;
    }

    private static List<List<Integer>> getFrontTruncatedSubListsOf(List<Integer> list) {
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < list.size(); i++) {
            result.add(list.subList(i, list.size()));
        }

        return result;
    }

    private static List<List<Integer>> getEndTruncatedSubListsOf(List<Integer> list) {
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < list.size(); i++) {
            result.add(list.subList(0, list.size() - i));
        }

        return result;
    }

    private static List<Integer> getSumsOfSubarrays(List<List<Integer>> subarrays) {
        return subarrays.stream()
                .map(subsubarray -> subsubarray.stream()
                                                .mapToInt(integer -> integer)
                                                .sum())
                .collect(toList());
    }

}

Unit testing

As it currently stands, testing your class means having to feed it a filesystem-based input (even if it's using something in-memory like Jimfs). You should consider implementing your application logic such that the input is the form of Stream<String>, so that the source of that stream is independent of the processing here.

String splitting as Stream<String>

Array.asList(string.split(",")).stream()

This can be better represented using Pattern.splitAsStream(CharSequence)

// consider making Pattern.compile(",") a static Pattern field too
Pattern.compile(",").splitAsStream(string)


Matrix bottom left to top right Can someone please review this simple code for printing all paths in a matrix from bottom left to top right? If an element is 1, it is a "wall" and you cannot take it.

Possible steps: up and right

  // Prints possible paths from bottom left to top right
    public static void findPath(int n, int i , int j, int[][] mat,ArrayList<Integer> path)
    {
        if(i==0 && j==n-1)
        {
            System.out.println();
            for(Integer step: path)
            {
                System.out.print(","+step);
            }
        }

        if(isPossibleStep(i+1,j,n,mat))
        {
            path.add(i+1);
            findPath(n,i+1, j,mat, path);
        }
        else if(isPossibleStep(i,j-1,n,mat))
        {
            path.add(j-1);
            findPath(n,i, j-1,mat, path);
        }

    }

    // Tells if a given path is possible
    public static boolean isPossibleStep(int i, int j, int n,int[][] mat)
    {
        if(mat[i][j]==1)
            return false;

        if(i < n && j > 0)
            return true;
        else
            return false;
    }

Also, how do I print just 1 possible path and then exit? It seems like a simple change but I am not able to think of a graceful way of doing it.

You can refactor the findPath logic somewhat and reduce the indent level while preserving the method's behavior:

// Prints possible paths from bottom left to top right
public static void findPath(int n, int i , int j, int[][] mat, ArrayList<Integer> path)
{
    if(i == 0 && j == n - 1)
    {
        System.out.println();
        for(Integer step: path)
        {
            System.out.print("," + step);
        }
    }

    boolean rightStep = isPossibleStep(i + 1, j, n, mat);
    if(!isPossibleStep(i, j - 1, n, mat) && !rightStep)
        return;

    path.add(rightStep ? ++i : --j);
    findPath(n, i, j, mat, path);
}

isPossibleStep can also be simplified by use of short-circuit logic. The following expresses the intent more directly with the benefit of being terse:

public static boolean isPossibleStep(int i, int j, int n, int[][] mat)
{
    return mat[i][j] != 1
        && i < n
        && j > 0;
}


Python Pandas - finding duplicate names and telling them apart (Somewhat) new to python and coding in general! Using python 3.7 and pandas, I'm running code to create a searchable list of people in my dataframe, and I feel like my way of telling duplicates apart is very roundabout. I would love some advice on making it simpler and more efficient.

I have a database in pandas, 'df2', which has three relevant rows: 'First Name', 'Last Name' and 'People ID'. Some people will have the same name, and these can be told apart by their 'People ID'. I start by making the 'Name' column as thus:

df2['Name'] = df2['First Name'] + ' ' + df2['Last Name']

Now I make a Dict, nameid, to find out how many different People IDs are associated to each unique 'Name' string.

nameid = {}
for i in df2.index:
    try:
        nameid[df2.loc[i, 'Name']].append(df2.loc[i, 'People ID'])
    except:
        nameid[df2.loc[i, 'Name']] = [df2.loc[i, 'People ID']]

There are multiple occurences of each person in the spreadsheet, so I want to just have each unique instance of a different 'People ID' using set().

for i in nameid.keys():
    nameid[i] = list(set(nameid[i]))

Now I create a second dict, namead, which is a "filtered" version of nameid where we've removed all reviewer names with just one ID value associated (those are fine as they are).

namead = {}

for i in nameid.keys():
    paceholder = ['Nothing']
    try:
        paceholder.append(nameid[i][1])
        namead[i] = nameid[i]
    except:
        pass

Finally, I use namead to make dupes, the list of index values of df2 where there are names belonging to different reviewers. I then pass that through df2 to add the 'People ID' to those names and ensure there is no confusion.

dupes = [i for i in df2.index if df2.loc[i, 'Name'] in namead.keys()]
for i in duperevs:
    df2.loc[i, 'Name'] += ' ' + str(df2.loc[i, 'People ID'])

Whew! I feel like I added several layers of complexity here but I'm not sure where to start - help would be much appreciated!

EDIT - I'm not sure how to put an extract of the dataframe in this textbox. Clarification: each row of data has information, and I need it to be searchable by name for the end user, with a placeholder to differentiate identical names (the People ID). The resulting data looks like: "Frank Jones / 14498", "Mitin Nutil / 35589", "Maveh Kadini 1433 / 1433" (indicating that there's more than one Maveh Kadini in the data). Each person (by People ID) will appear in many different rows of data.

First I will comment on the coding, then I will suggest an alternative solution

Variable naming

Ideally you want your variable names to express what the purpose of a variable is. nameid and df2 are partly understandable, namead is not.

Exception

Never just do try-except. Always try to be as specific as possible on the exception. In the creation of nameid you except a KeyError, and in the other case a IndexError. Then use it like that

collections.defaultdict or dict.setdefault

Instead of trying and getting the KeyError, it is easier to use

nameid = defaultdict(list)
for i in df2.index:
    nameid[df2.loc[i, 'Name']].append(df2.loc[i, 'People ID'])

would work

iteration

apart from the fact that you want to prevent iteration as much as possible when using pandas (or numpy), in Python in general, there is almost always a better way than to iterator over the index. In this particular case, you can use DataFrame.iterrows. If the column labels had been valid python identifiers, DataFrame.itertuples would have been even better

nameid = defaultdict(list)
for _, row in df2.iterrows():
    nameid[row['Name']].append(row['People ID'])

with _ being the convention for the name of a variable you don't need

set

later you do

for i in nameid.keys():
    nameid[i] = list(set(nameid[i]))

Why not use set from the start, and why the conversion to list afterwards?

nameid = defaultdict(set)
for _, row in df2.iterrows():
    nameid[row['Name']].add(row['People ID'])

does all you need

len

the next part

namead = {}

for i in nameid.keys():
    paceholder = ['Nothing']
    try:
        paceholder.append(nameid[i][1])
        namead[i] = nameid[i]
    except:
        pass

uses list indexing [1] and expects lists with only 1 element to throw an Exception. This can be expressed a lot simpler with a dict expression. Later it seems the actual ids are not even needed since you only use the keys, so a set expression does the trick.

namead = {
    name
    for name, ids in nameid.items()
    if len(ids) > 1
}

pandas indexing

dupes = [i for i in df2.index if df2.loc[i, 'Name'] in namead.keys()]
for i in duperevs:
    df2.loc[i, 'Name'] += ' ' + str(df2.loc[i, 'People ID'])

pandas.Series as an isin function, so there is no need to make an intermediate list of keys whose name has more id's

dupes = df2["Name"].isin(namead)
df2.loc[dupes, "Name"] += " " + df2["People ID"].astype(str)

works too

Alternative approach

You can also use groupby.nunique

dupes = df2.groupby(['Name'])["People ID"].nunique()

This is a Series with the Name as index, and the number of unique People IDs as value. Then you can filter those with a value > 1, and check against the name

Name
Jane Doe    1
John Doe    2
Name: People ID, dtype: int64

dupes_idx = df2["Name"].isin(dupes[dupes>1].index)

Now you just need to append the People ID  to the Name

df2.loc[dupes_idx, "Name"] += " " + df2["People ID"].astype(str)

This was tested on

data = [
    ["John", "Doe", 1],
    ["John", "Doe", 1],
    ["John", "Doe", 2],
    ["Jane", "Doe", 1],
    ["John", "Doe", 2],
    ["Jane", "Doe", 1],
    ["John", "Doe", 1],
]

df2 = pd.DataFrame(data, columns=['First Name', 'Last Name', 'People ID'])

First Name    Last Name   People ID   Name
0     John    Doe     1   John Doe 1
1     John    Doe     1   John Doe 1
2     John    Doe     2   John Doe 2
3     Jane    Doe     1   Jane Doe
4     John    Doe     2   John Doe 2
5     Jane    Doe     1   Jane Doe
6     John    Doe     1   John Doe 1


Static method to get user ID I have a method which extracts the logged-in user details from a SpringSecurityContext object.

I have read that only utility methods (which does certain calculations) should be static.

Here is my method; it doesn't seem to be a utility method but I don't find any reason why I shouldn't make it static as I am using it in multiple beans.

public static int getSignedUpUser()
    {
        final SecurityContext ctx = SecurityContextHolder.getContext();

        if(ctx != null)
        {
            final Authentication auth = ctx.getAuthentication();

            if(auth != null)
            {
                final Object principal = auth.getPrincipal();

                if(principal instanceof AUser)
                {
                    final AUser au = (AUser)principal;
                    return au.getId();
                }
            }
        }

        return 0;
    }
}

This is a utility method. There's nothing wrong with it being static. Its readability would benefit greatly from (a) using guard clauses instead of having multiple nesting levels, (b) using java bracket style, and (c) using java spacing. You might also want to add logging to indicate why there's no signed-in user, which is presumably a WARN or ERROR, but should at least be a DEBUG.

public static int getSignedUpUser() {
    final SecurityContext ctx = SecurityContextHolder.getContext();

    if (ctx == null) {
        LOGGER.debug("No security context available");
        return 0;
    }

    final Authentication auth = ctx.getAuthentication();
    if (auth == null) {
        LOGGER.debug("No authentication available in security context {}", ctx);
        return 0;
    }

    final Object principal = auth.getPrincipal();
    if (!(principal instanceof AUser) {
        LOGGER.warn("Principal {} is not an instance of AUser!", principal);
        return 0;
    }

    final AUser au = (AUser)principal;
    return au.getId();
}


Implementing a thread safe log class with simple functionality I have finally assembled an attempt to create a thread safe logging class and also ensured by file flags that file should not be accessed by different processes at same time. This classed will be inside DLL. Below is the implementation,

   static class GMLogger
    {

       private static List<string> _buffer = new List<string>();
       private static int _maxBufferSize = 25;  // number of messages  permitted in the buffer at a time
       public static string _logDir = "C:\\Logs";
       private static readonly object _syncObject = new object();

       // Log message
        public static  void Log(string logMessage)
        {
            try
            {
                lock (_syncObject)
                {
                    _buffer.Add(logMessage);

                    Save(_buffer);
                }
            }
            catch (Exception ex)
            {
                throw;
            }
        }

       // Save buffer if needed
        private static void Save(List<string> buffer)
        {
            if (buffer.Count > _maxBufferSize)
            {
                // Write to file
                if (!_logDir.EndsWith("\\")) _logDir += "\\";
                DirectoryInfo di = Directory.CreateDirectory(_logDir);
                var todaysLogFilePath = Path.Combine(_logDir,
                                                       ("Log" + DateTime.Now.ToString("yyyy-MMMM-dd") + ".txt"));
                using (FileStream aFile = new FileStream(todaysLogFilePath, FileMode.Append, FileAccess.Write, FileShare.None))
                using (StreamWriter sw = new StreamWriter(aFile))
                {
                    for (int i = 0; i < buffer.Count(); i++)
                    {
                        sw.WriteLine(buffer[i]);
                    }
                }

                // Clear buffer
                buffer.Clear();
            }

    }
}

Please note I am a beginner first of all, and if this class achieves the simple functionality of writing simple lines to file I am OK with it.

Of course you can comment also about other things which are in the context of CodeReview site. But please not too advanced feedback since as I said I am beginner.

Second, here are some specific questions I have about it:

Have I used the lock correctly?
This class maybe used by many threads, will I have performance problems because of thread waiting for each other? NOTE: I log only ERRORS so even if many threads are using it, not many errors should be occurring right? Also note how because of performance I have a cache for log messages.
Finally, only problem I see if different programs use this class to write to same file, how can I distinguish inside logs which program or process made an entry? How is this solved typically? (I assume one process can write to this file if another finished writing, isn't it?)

PS. This is all the functionality I want, I don't plan to extend this class. So please no recommendations about 3rd party libs. If my class achieves above points well, I am ok with it. Or if you see some problem with it, please tell.

And in general I am interested if its safe to use my class because some people always say to not create your own logging class. Is it ok if I use this class? I see people creating log classes such as here http://www.codeproject.com/Tips/585796/Simple-Log, so what is problem if I created one as above?

One of the things you can do to get some performance back (albeit not a lot, but still more than none) is rewrite Save to have one responsibility.

As it stands now, Save has several responsibilities. It's responsible for:

Checking if the buffer is of sufficient length to be saved.
Validating that _logDir ends with a \.
Creating the _logDir directory.
Coming up with the filename for the log file.
Saving the buffer to disk.
Clearing the buffer after saving.

The Save method should only be responsible for saving (and maybe clearing) the buffer. If you move the if check outside to the Log method, you remove a (minor) bit of overhead.

A better style would be to create a method SaveIfFull which does the if-check, then calls Save which actually saves the buffer.

You have a:

public static string _logDir = "C:\\Logs";

Which is generally frowned upon. The best-practice for public members is PascalCase with no leading characters. So, instead, it should be:

public static string LogDir = "C:\\Logs";

Never omit braces from if statements, and never one-line them. Adding braces won't prevent bugs, but it will help prevent bugs.

if (!_logDir.EndsWith("\\")) _logDir += "\\";

Should be rewritten as:

if (!_logDir.EndsWith("\\"))
{
    _logDir += "\\";
}

Likewise, you should make _logDir (which we to LogDir) a property, with a private backing field.

private static string _logDir = "C:\\Logs\\";
public static string LogDir
{
    get
    {
        return _logDir;
    }
    set
    {
        if (string.IsNullOrWhiteSpace(value))
        {
            throw new ArgumentException("The specified value must not be null, whitespace, or an empty string.", "value");
        }

        _logDir = value;

        if (!_logDir.EndsWith("\\"))
        {
            _logDir += "\\";
        }
    }
}

You can also add other validation logic in there as you need, but this way it helps separate responsibilities further.

To get rid of some of the other additional responsibilities Save has, we can consider a method GetLogFileName(DateTime loggedAt) which would return the filename, then Save would call string todayFileName = GetLogFileName(DateTime.Now) or string todayFileName = GetLogFileName(DateTime.UtcNow) as appropriate.

If you have C#6.0 a few of these tasks become easier/simpler:

Path.Combine(_logDir, ("Log" + DateTime.Now.ToString("yyyy-MMMM-dd") + ".txt")); simplifies to: Path.Combine(_logDir, $"Log{DateTime.Now.ToString("yyyy-MMMM-dd")}.txt");
You can replace "value" at the end of ArgumentException with nameof(value). (Which allows you to refactor that message cleanly.)

As far as your primary concerns:

Yes, the idea of the lock is to mark a shared resource as "in-use" so that threads know to wait on each other before they can proceed. You could, however, replace it with a bool instead of an object for smaller overhead.
You could have performance implications by the lock, but that's the downside of multithreading: somewhere you will have a bottleneck from context-switching, et al.
That is beyond the scope of Code Review.

Another concern: if there is a substantial delay between messages, it may occur that the log is never written to before the application is closed (or messages are left in the buffer), this can be alleviated by scheduling a Timer to save the log at periodic intervals as well, so that if there is a substantial delay the log is saved anyway.


Use a comma-separated field in another SQL query I was just wondering if there was a better way to write this block of code in php. I have a string with values separated by commas. I need to prepare that string to pass it on to the query using IN clause.

 $sql = "SELECT domain, items FROM rep_skills WHERE report_id = $id ";
 $data = $conn->query($sql)->fetch_object();

 while($data){
     // can this be done in one line?
     $array =  explode(",",$data->items); // string here is 39,40,41
     $items = implode("','",$array);  // string here is 39','40','41
     // end of block

     $result = $conn->query("SELECT description
           FROM ".$tables[$data->domain]."
           WHERE item_id IN ('".$items."')");

     $description = '';
     while($row = $result->fetch_object()){
        $details .= '- '.$row->description;
    }
}

It's a very weird database schema in the first place.

There should be never a thing like comma-separated values in one cell. Learn the database normalization and then create a link table wghich can be used to get all your records in a single query with JOIN.

There should be never a thing like multiple tables of the same structure. there should be only one table with a field to distinguish the kind of domain.


Registration in Django Can you say, is this a bad code for registration in Django? Do I need to fix something or use a pip instead? (I am learning)

def register(request):

    error_messages = {}

    if request.POST:
        form = UserCreationForm(request.POST)

        if form.is_valid():
            new_user = form.save()

            user = authenticate(username=request.POST["username"], password=request.POST["password1"])
            login(request, user)

            return redirect('index')
        else:
            form = UserCreationForm()
            return redirect('register')

    return render(request, 'account/register.html',
            {'title': 'Registration', 'error_messages': error_messages})

From what you can find on the docs you are pretty close. I may change a couple things a little just to be on the safe side:

Change:

user = authenticate(username=request.POST["username"], password=request.POST["password1"])

To:

user = authenticate(username=form.cleaned_data['username'], form.cleaned_data['password1'])

The first way is not wrong, but using validated data on forms is a better practice than using the raw post request. Is better to be consistent.


Transform letters in a string I am learning python and want to improve my skills in it. So could someone advice of how to improve the code below (this is a simple programming problem taken from one of the web sites). I feel like my code is not really Pythonic.

Problem: Using the Python language, have the function LetterChanges(str) take the str parameter being passed and modify it using the following algorithm. Replace every letter in the string with the letter following it in the alphabet (ie. c becomes d, z becomes a). Then capitalize every vowel in this new string (a, e, i, o, u) and finally return this modified string.

from sets import Set

def LetterChanges(str):
   vowels = Set(['a', 'e', 'i', 'o', 'u'])
   new_str = ''
   for i in str:
      cur_char = i.lower()
      if cur_char == 'z':
         new_str += 'A'
      elif ord(cur_char) >= 97 and ord(cur_char) < 122:
         new_char = chr(ord(i) + 1)
         new_str += (new_char if new_char not in vowels else new_char.upper())
      else:
         new_str += i
   return new_str

if __name__=='__main__':
   print(LetterChanges(raw_input()))

Your code defines a function with a clear input and a clear output. Also, you've put the call to it behind the if __name__ == '__main__':. You've taken good habits on this points. Nonetheless, a few things can still be improved.

Python version

If you are learning Python, there is no good reason to start with Python 2 which is reaching its end of life. You should focus on learning Python 3, going to be supported for a while and with various warts corrected (and obviously more features).

In any case, the sets module is not required since Python 2.6 since we have the set builtin.

Style

There is an official standard Python style guide called PEP 8. This is highly recommended reading. It gives guidelines to help writing code that is both readable and consistent. The Python community tries to follow these guidelines, more or less strictly (a key aspect of PEP 8 is that it provides guidelines and not strict rules to follow blindly).

It deals with various aspects of the code style: naming conventions, indentation convention, etc.

You'll find various tools to try to check whether your code is PEP 8 compliant and if is it not, to try and fix this:

pycodestyle package (formerly known as pep8) to check you code
pep8online to check your code with an online tool
autopep8 package to fix your code automatically
Also, this is also checked by various linters: pylint, pyflakes, flake8, etc.

In your case, the major points I would fix are:

indentation should be 4 space
function names should snake_cased
you could try to take into account the advice to use join instead of "CPython's efficient implementation of in-place string concatenation".

Naming

On top of the snake-case point mentioned above, a few things could be improved in the naming. Naming is a difficult part of programming so what I suggest are just personal, far from perfect, suggestions (from a non-native English speaker). In your case, I'd call the function tranform_string so that it conveys the fact that:

it is an action (a noun would correspond to an object/class name)
it applies to string (and not to single character even if the distinction is fuzzy in Python compared to other programming languages)

The name str is a bit of a problem because it hides the str builtin. I do not find any alternative better than str_ which is still pretty poor :-(.

Edit: I don't know why I didn't think about "s" in the first place but after reading it in another answer, it looks like a much better option indeed. I am too lazy to edit my code everywhere.

Finally, i is a good name for an (integer) index. For a single character, c seems easier to understand (char if you feel verbose).

Chained comparison

In Python, you can chain comparison. If your case, you can write:

elif 97 <= ord(cur_char) < 122:

More beautiful character check

From the Zen of Python:

  Beautiful is better than ugly.
  Explicit is better than implicit.
  Simple is better than complex.

In your case, you could avoid the call the ord and get rid of the magic number by writing the simple:

elif 'a' <= cur_char < 'z':

Rewriting the logic

You could have the logic adding a character to new_str in a single place.

    cur_char = c.lower()
    if cur_char == 'z':
        new_char = 'A'
    elif 'a' <= cur_char < 'z':
        new_char = chr(ord(c) + 1)
        if new_char in vowels:
            new_char = new_char.upper()
    else:
        new_char = c
    new_str += new_char

Then, you could try to makes the logic as close as possible to the way it is given in the problem for instance by making "z" a special case only for the operation where you take the following letter.

    low_char = c.lower()
    if 'a' <= low_char <= 'z':
        new_char = 'a' if low_char == 'z' else chr(ord(c) + 1)
        if new_char in vowels:
            new_char = new_char.upper()
    else:
        new_char = c
    new_str += new_char

Shorter way to define vowels

Because strings are iterable and set takes any kind of iterable, you could write:

vowels = set('aeiou')

Better ascii check

You could reuse values from the string module to make your test more beautiful:

   if low_char in string.ascii_lowercase:

Removing string concatenation

As mentionned earlier, it is advised not to use string concatenation and use join instead, when relevant.

At this stage, the code (with added tests) looks like:

import string

def transform_string(s):
    vowels = set('aeiou')
    lst = []
    for c in s:
        if c in string.ascii_letters:
            new_c = 'a' if c.lower() == 'z' else chr(ord(c) + 1)
            if new_c in vowels:
                new_c = new_c.upper()
        else:
            new_c = c
        lst.append(new_c)
    return "".join(lst)

if __name__=='__main__':
    assert transform_string("")            == ""
    assert transform_string("qwertyuiop")  == "rxfsUzvjpq"
    assert transform_string("asdfghjkl")   == "btEghIklm"
    assert transform_string("zxcvbnm")     == "AydwcOn"
    assert transform_string("1234567890")  == "1234567890"
    assert transform_string("QWERTYUIOP")  == "RXFSUZVJPQ"
    assert transform_string("ASDFGHJKL")   == "BTEGHIKLM"
    assert transform_string("ZXCVBNM")     == "AYDWCON"
    assert transform_string("(){}<>+_-=")  == "(){}<>+_-="


Finding whether there exists a pair of numbers in a set having a given product Devise an algorithm that will operate on a number x and a set of n
  distinct numbers such that in \$O(n \lg n)\$ time, the algorithm indicates
  whether or not there are two numbers in the set that have a product of
  x. Explain why your algorithm works.

My algorithm:

Sort the set //\$ O(n \lg n)\$
For every element in the set check if x % element =0 // \$O(n)\$
If so check if the dividend x/element exists in the set // \$O(\lg n)\$
If dividend exists and is not equal to element, the two numbers in the set (element and dividend) have a product of x.

This algorithm works because it only returns true when the condition(x=element*dividend where element and dividend are in the set) to be satisfied is met. And upon quick Analysis we can see that the algorithm is running at \$O(n\lg n)\$ for the sort and \$O(n)*(\lg n)\$ for checking if the two elements exists. Therefore it is running at \$O(n \lg n) + O(n \lg n) = O(2n \lg n) = O(n \lg n)\$

Can I have some feedback on my solution — whether you think it is correct or not and where you think it can be improved?

def findIfProdExists(x,items):
    items = mergeSort(items) # O(nlgn)
    for item in items:
        if(item!=0):
            if x%item ==0:
                if item!=x/item and find(x/item,items):  #binary Search O(lgn)
                    return True
    return False

def mergeSort(aList):
    size = len(aList)
    first = aList[:int(size/2)]
    second = aList[int(size/2):]

    if(size ==1):
         return aList
    if(size ==2):
        if(aList[1]<aList[0]):
            return list([aList[1],aList[0]])
        else:
            return aList
    else:
        return merge(mergeSort(first),mergeSort(second))

def merge(list1,list2):
        newList =[]
        i1 =0
        i2 =0
        while i1<len(list1) and i2 <len(list2) :
            if list1[i1] <list2[i2] :
                newList.append(list1[i1])
                i1+=1
            elif list1[i1]>list2[i2] :
                newList.append(list2[i2])
                i2+=1
            else:
                newList.append(list1[i1])
                i1+=1
        newList.extend(list1[i1:] +list2[i2:])
        return newList

def find(x,items):
    lo = 0
    hi = len(items)
    while lo<hi:
        mid = (lo + hi) // 2
        if x == items[mid]:
            return True
        elif x < items[mid]:
            hi = mid
        else:
            lo = mid + 1
    return False

The algorithm description is good, but the implementation of find is \$ O(n) \$, so the overall runtime is actually \$ O(n^2) \$.

Detailed review follows:

There are no docstrings. What does each function do? How do I call it? What does it return? Are there any constraints on the parameters, for example do the inputs have to be sorted? or do they have to be free of duplicates?
It's not necessary in Python to have parentheses around the condition of if statement, and it's best to omit them.
According to the analysis, find needs to be \$ O(\log n) \$, but the actual implementation is \$ O(n) \$. Here's a demonstration:

>>> from timeit import timeit
>>> for p in range(2, 8):
...     items = list(range(10**p))
...     '{:f}'.format(timeit(lambda:find(0, items), number=1))
...
0.000012
0.000022
0.000077
0.001386
0.038858
0.417670

The reason for this is the copying in the recursive calls. In Python, the list slice items[mid:] has to be copied, and the time taken to do this is proportional to the number of items in the copy. See the time complexity page on the Python wiki.
In order to avoid copying in find, it's best to keep indexes into the part of the sequence which might contain the item we're looking for:

def find(x, items):
    """Return True if x is an element of the sequence items, assuming
    items is sorted.

    """
    lo = 0
    hi = len(items)
    while lo < hi:
        mid = (lo + hi) // 2
        if x == items[mid]: return True
        elif x < items[mid]: hi = mid
        else: lo = mid + 1
    return False

Python has a built-in module bisect for binary search of sorted sequences, and using this module it's possible to write find like this:

from bisect import bisect_left

def find(x, items):
    """Return True if x is an element of the sequence items, assuming
    items is sorted.

    """
    i = bisect_left(items, x)
    return i < len(items) and items[i] == x

The corrected version of find locates an element in a sorted list in time \$ O(\log n) \$. But it's possible to do better than that using a set. Set lookup has average complexity \$ O(1) \$.
The implementation of merge goes into an infinite loop if list1 and list2 have a common item. This was easy for me to spot because there is an if … elif with no else at the end. When code has a sequence of conditions like this, it's always worth asking, "what happens if none of the conditions apply?"
Python has a built-in function heapq.merge for merging sorted iterables into a single sorted iterator, and a built-in function sorted for sorting an iterable (using a variant of mergesort, as it happens). These are fast and well-tested implementations, and (except as an exercise) they should be used in preference to writing your own.
In findIfProdExists the division x/item is computed twice in some cases.
It would be better to compute it once and remember the value.
In findIfProdExists the cheap test item!=x/item is computed after the expensive test find(x/item,items). It's usually best to compute cheap cases first so that if they fail the expensive test can be avoided altogether.

Putting all this together, I'd implement the algorithm like this:

def product_pair(x, items):
    """Return True if there is a pair of distinct elements in the iterable
    items whose product is x. Return False otherwise.

    """
    items = set(items)
    for item in items:
        if item != 0 and x % item == 0:
            y = x / item
            if y != item and y in items:
                return True
    return False


Sending email for allotment Requirement:

If the bookshop manager field changes from A to B, I need to email the person B saying that the new Bookshop has been allotted to him and he has to do certain activities.

private void SendEmailToAllottedManager()
{
   EmailExpress mEmailExpress = new EmailExpress();
   mEmailExpress.SendEmail(Shop.Bookstore.BookstoreName, Subject);
}

In the method where I am calling SendEmailToAllottedManager, I am checking if the Manager has indeed changed or not as below:

if (OriginalManager != CurrentManager)
{
    SendEmailToAllottedManager();
}

During code review, a colleague suggested that I move the check from outside the function SendEmailToAllottedManager() to inside it:

Proposed Code

private void SendEmailToAllottedManager()
{
    if (OriginalManager != CurrentManager)
    {
          EmailExpress mEmailExpress = new EmailExpress();
          mEmailExpress.SendEmail(Shop.Bookstore.BookstoreName, Subject);
    }

}

I maintain my stand that the function SendEmailToAllottedManager is only about emailing and not about performing the checks, etc.

What do you think?

I would say, that actually sending the email is part of the process of changing the store manager. It's part of the business logic (AFAIK), that when a store changes it's manager, the new manager should be notified, among other things.

Thats why the check if the manager changes is not a job for the email sender at all. The email sender should be a utility, which can be reused.


Find two integers with the largest sum within a budget (breaking ties by smallest difference) The algorithm finds a number pair that is as close to budget as possible, and if there are more pairs with same value, the pair with the least difference shall be given out. My algorithm works correctly, but is far too slow. Do you have ideas to improve it?

limit = highest value within budget atm,
i = smaller number of pair,
j = bigger number of pair

long limit = 0;
long i = 0, j = 0;
Arrays.sort(preis);

for (int a = 0; a < preis.length; a++) {
    for (int b = a + 1; b < preis.length; b++) {
        if (preis[a] + preis[b] > limit && preis[a] + preis[b] <= budget) {
            limit = preis[a] + preis[b];
            i = preis[a];
            j = preis[b];
        } else if (preis[a] + preis[b] == limit) {
            if (preis[a] > i) {
                i = preis[a];
                j = preis[b];
            }
        }
    }
}

I'm using Java 8.

To change your algorithmic order, say from N^2 to N lg N, you must change your algorithm. A simple change will not suffice. But I can think of a better algorithm:

Let us accept the theorum that for each number x in your list, you have a number y such that x + y = z and no other y for the given x will produce a z' where z < z' < budget. That is to say, y is the perfect match for x.

We can use a binary search to find the best y for a given x once the array is sorted.

We can find the y for each x in the array, and the corresponding z. We can loop over these results to find the highest z that does not break the budget, assuming one exists.

The actual code is left as an exercise to the reader, but I think there should be sufficient details to craft it, considering you understand the problem enough to have created a naive solution.


ResourceManager class consisting of multiple singletons I've implemented a class, which provides access to different static resources, which are used by different frontends. I'm hesitating, because in Java getters and setters are quite wide spread. So my question is, if this code smells bad?

public class ResourceManager {
    public static final Preferences Preferences = new Preferences();
    public static final ResourceBundle Texts = ResourceBundle.getBundle("com.stackexchange.resources.Language");

    public static Image getImage(String name) {
        Image retVal = null;

        try {
            retVal = ImageIO.read(ClassLoader.getSystemResource(name));
        } catch (IOException e) {
            // ToDo Use logging functionality
        }

        return retVal;
    }

    private ResourceManager() {
    }

    public static class UserInterface {
        public static final Font titleFont = new Font("default", Font.PLAIN, 18);
    }
}

The fact that you have "Manager" as part of the name of the class is a code smell.  This class violates the Single Responsibility Principle.

In particular, Preferences sounds like it contains user-specific data; I wouldn't call it a "resource".  It should be split into its own class.

On the other hand, Texts, getImage(), and UserInterface.titleFont appear to contain data that would be application-wide constants.  A class like this could make sense:

public class UIResources {
    public static UIResources getInstance(Locale locale) {
       …
    }

    public Image getImage(String name) {
        …
    }

    public String getText(String name) {
        …
    }

    public Font getFont(String role) {
        …
    }
}


BigInteger check in C++ from a string You might consider this question a follow-up of:

BigInteger check in C from a string

Although, this time, I used C++.

I am on Linux Mint 19.1 with the compiler version:

g++-8 (Ubuntu 8.2.0-1ubuntu2~18.04) 8.2.0

I tried to push myself hard in C, but it obviously requires one of:

more skill / experience
lower-level approach

or both.

That is why I decided to transition to C++, already bought one C++ online course on Udemy, but back to coding, the current version looks straightforward to me, I see no more pointers, etc., which sounds ideal to me:

#include <iostream>
//#include <string> // I don't get why it compiles without this header

bool string_contains_integer(std::string str)
/*
    This function iterates through an array of chars,
    and checks each character to be a digit;
    optionally including a starting "+/-" sign.

    Returns true if the string contains a number (string of digits);
    Returns false if the string contains another character(s).

    Starting "+/-" gets ignored, as we accept all integer numbers.
*/
{
    // if the string is empty, return right away
    if ( str.empty() ) return false;

    // I'd like to avoid repeated length() calls
    unsigned long long string_length = str.length();

    // find out if there is a "+/-" sign
    bool sign_present = ( (str[0] == '-') || (str[0] == '+') );

    // check if there is the sign only
    if ( sign_present && (string_length == 1) ) return false;

    // iterate through all characters in the string
    for (unsigned long long i = 0; i < string_length; i++)
    {
        // skip the digit check for the sign at the beginning
        if ( (i == 0) && sign_present ) continue;

        // this is actually the core part checking on digits
        if ( ! std::isdigit( (unsigned char) str[i] ) ) return false;
    }

    // If we got here, then all the characters are digits,
    // possibly starting with a sign.
    return true;
}

int main(void)
{
    if ( string_contains_integer("-123456789123456789123456789123456789123456789123456789123456789") )
    {
        std::cout << "PASS: Input is a number.\n";
        return 0;
    }
    else
    {
        std::cerr << "FAIL: Input is not a number!\n";
        return 1;
    }
}

This program I compile as follows:

g++-8 -std=c++17 -Wall -Wextra -Werror -Wpedantic -pedantic-errors -o bigInteger bigInteger.cpp

You do need to include <string>.  Your platform seems to bring it in as a side-effect of other includes, but you can't portably rely on that.

If there's no need to modify the contents of the string, prefer to pass by reference, to reduce copying:

bool string_contains_integer(const std::string& str)
//                           ^^^^^            ^

Instead of looping with indexes, learn to use iterators.  If you really must use indexes, use the correct type (std::string::size_type, not unsigned long long).

We don't need to write our own loop by hand, as there's a standard algorithm that will do that for us; we just need to supply the correct predicate function:

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

bool string_contains_integer(const std::string& str)
/*
    This function iterates through an array of chars,
    and checks each character to be a digit;
    optionally including a starting "+/-" sign.

    Returns true if the string contains a number (string of digits);
    Returns false if the string contains any other character(s).

    Starting "+/-" gets ignored, as we accept all integer numbers.
*/
{
    auto from = str.begin();
    auto to = str.end();

    if (from == to) {
        return false;
    }

    if (*from == '+' || *from == '-') {
        ++from;
    }

    return from != to
        && std::all_of(from, to,
                       [](unsigned char c){ return std::isdigit(c); });
}


Reverse int within the 32-bit signed integer range Problem

  Reverse digits of a 32-bit signed integer. When the reversed integer overflows return 0. Optimized code here.

Feedback

I'm looking for any ways I can optimize this with modern C++ features overall. I hope my use of const-correctness, exception handling, and assertions is implemented well here, please let me know. Is there any way I can use byte operations to reverse the int and keep track of the sign possibly?

Based on the submission feedback from LeetCode, is it safe to say that the time complexity is \$O(n)\$ and space complexity is \$O(n)\$? If I can reduce the complexity in anyway would love to know!

#include <cassert>
#include <climits>
#include <stdexcept>
#include <string>

class Solution
{
    public:
        int reverse(int i) {
            bool is_signed = false;
            if(i < 0) { is_signed = true; }

            auto i_string = std::to_string(i);

            std::string reversed = "";
            while(!i_string.empty()) {
                reversed.push_back(i_string.back());
                i_string.pop_back();
            }

            try {
                i = std::stoi(reversed);
            } catch (const std::out_of_range& e) {
                return 0;
            }

            if(is_signed) { i *= -1; }

            return i;
        }
};

int main()
{
    Solution s;
    assert(s.reverse(1) == 1);
    assert(s.reverse(0) == 0);
    assert(s.reverse(123) == 321);
    assert(s.reverse(120) == 21);
    assert(s.reverse(-123) == -321);
    assert(s.reverse(1207) == 7021);
    assert(s.reverse(INT_MAX) == 0);
    assert(s.reverse(INT_MIN) == 0);
}

General comments

There is no reason to use a class. Instead, the functionality should be made into a free function.
Your code is overly complicated. There is no reason to make new string from which you erase characters one-by-one. Instead, you can convert the input integer to a string and use a standard function to reverse that.
Also, pay attention to const correctness. This protects from unintended mistakes and helps the compiler optimize more.

I would simplify your function to just:

int reverse(int i)
{
    try
    {
        auto reversed{ std::to_string(i) };
        std::reverse(reversed.begin(), reversed.end());

        const auto result{ std::stoi(reversed) };
        return i < 0 ? -1 * result : result;
    }
    catch (const std::out_of_range& e)
    {
        return 0;
    }
}

Further comments

If you want to have a fast solution, you should avoid std::string altogether. This you can do by "iterating" through the digits using arithmetic operations (division and modulus), as in (using std::string to only show you what is happening):

int x = 1234;
std::string s;

while (x > 0)
{
    s.push_back('0' + (x % 10));
    x /= 10;
}

std::cout << s << "\n"; // Prints 4321

I will let you take it from here to use these ideas to make your program even faster.
Regarding your theoretical question concerning complexity, if we assume that the input is treated as a string of n characters, there is \$\Omega(n)\$ lower bound by a trivial adversary argument. Basically, if you don't spend at least n time, you can't read the whole of the input, and then you cannot guarantee correct output on every instance.