Find The Duplicates in two arrays Find The Duplicates

Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note that the output array should be sorted in an ascending order.

Let N and M be the lengths of arr1 and arr2, respectively. Solve for two cases and analyze the time & space complexities of your solutions: M ≈ N - the array lengths are approximately the same M ≫ N - arr2 is much bigger than arr1.

My approach:

import java.io.*;
import java.util.*;
import java.lang.*;

class Solution {

  static int[] findDuplicates(int[] arr1, int[] arr2) {
    // your code goes here
    int i = 0, j = 0, k = 0;
    ArrayList<Integer> ans = new ArrayList<>();
    while(( i < arr1.length) && (j < arr2.length))
    {
      if(arr1[i] < arr2[j])
          i++;
      else if(arr1[i] == arr2[j])
      {
          ans.add(arr1[i]);
          k++;
          i++;
          j++;
      }
      else
          j++;
     }
    int[] arr = new int[ans.size()];

    for(int l = 0; l < ans.size(); l++) {
    if (ans.get(l) != null) {
        arr[l] = ans.get(l);
    }
}
    return arr;
  }
   //M = arr1.length, N = arr2.length
  //Time = O(M+N)
  //Space = O(min(M,N))

I have the following questions regarding my code:

1) How can I improve the time and space complexity of my code?

2) Is there a better way(lesser lines of code, better data structures) that can be used to improve the code?

Source: Mock interview

Here are my comments:

The variable k was probably meant to keep track of size of the array list (number of duplicates).  However, it is redundant, since you use the list's size() method.
To convert a list to array you can use the stream API. while I am not certain if it provides any time/space benefits, it is probably the most optimized way to do it, and it saves you having to declare the return array. Since it is tricky to do the conversion with primitive types arrays, here it is: ans.stream().mapToInt(item -> item.intValue()).toArray(); and you can make it the return value of the method.
The while condition is using redundant parentheses that have the && between them . It can be argued as a matter of taste, but in my eyes, the condition is clearer without them. I add an additional space around the higher order operator: while(i < arr1.length  &&  j < arr2.length)


Transform dollars in exact change The program was to turn an integer into exact change and uses a bunch of if statements.

Are there steps a beginner like me can do to remove some or is it just how it will be? I can't find anything on it. At least I'm not sure as I'm still in the basic course.

The program is turned in and was fine and this would be for my personal use. I know I may learn this in my classes in time, but I find more direct answers to help more.

change = int(input('')) # receive input from the user
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#                                                                               #
# This code it so provide exact change using the least amount of coins possible #
#                         COMPUTER SCIENCE 161A                                 #
#                                                                               #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
if change > 0:                          # checks if there is change to provide coins
    if change >= 100:                   #checks if the amount is greater or equal to 100
        if (change // 100) != 0:        # this is to check if there is change at this point
            if (change // 100) > 1:     # provide the plural if more than 1
                print('{} Dollars'.format(change // 100))
                change = (change % 100)
            else:
                print('{} Dollar'.format(change // 100)) # prints the dollar amount without a float
                change = (change % 100) # this leaves the remainder after calculating the amount of change
        else:                           # if there is no change do this
            change = (change % 100)     # if there no change here there will be no output
    if change <= 99:                    #checks if the amount is lower or equal to 99
        if (change // 25) != 0:         # this is to check if there is change at this point
            if (change // 25) > 1:
                print('{} Quarters'.format(change // 25))
                change = (change % 25)
            else:
                print('{} Quarter'.format(change // 25))
                change = (change % 25)
        else:
            change = (change % 25)
    if change <= 24:                    #checks if the amount is lower or equal to 24
        if (change // 10) != 0:         # this is to check if there is change at this point
            if (change // 10) > 1:
                print('{} Dimes'.format(change // 10))
                change = (change % 10)
            else:
                print('{} Dime'.format(change // 10))
                change = (change % 10)
        else:
            change = (change % 10)
    if change <= 9:                     #checks if the amount is lower or equal to 9
        if (change // 5) != 0:          # this is to check if there is change at this point
            if (change // 5) > 1:
                print('{} Nickels'.format(change // 5))
                change = (change % 5)
            else:
                print('{} Nickel'.format(change // 5))
                change = (change % 5)
        else:
            change = (change % 5)
    if change <= 4:                     #checks if the amount is lower or equal to 4
        if (change // 1) != 0:          # this is to check if there is change at this point
            if (change // 1) > 1:
                print('{} Pennies'.format(change // 1))
            else:
                print('{} Penny'.format(change // 1))
else:
    print('No change')                  # tells the user to fuck off if there is nothing to convert

Firstly, I think your overall approach is sensible. You work your way through the coin types, from highest to lowest, pulling out as many coins of that type as possible, and passing the remainder to the next stage. So, logically, you're on the right track.

But as you've probably noticed, there's a lot of duplication in your code. You need to think about what you're doing the same for each coin type, and pull that logic into its own function. Which will yield something like the following:

def calculate_coins_of_denomination(change, denom):
    """
    Returns a tuple where the first value is the number of coins of the given denomination,
    and the second is the remainder

    Examples:

    calculate_coins_of_denomination(105, 100) => (1, 5)
    calculate_coins_of_denomination(100, 25) => (4, 0)
    """
    num_coins = change // denom
    return (num_coins, change - (num_coins * denom))

Once you've got this function in place, you can then call it repeatedly with each coin type, passing just the remainder to each successive function call:

(num_dollars, change) = calculate_coins_of_denomination(change, 100)
(num_quarters, change) = calculate_coins_of_denomination(change, 25)
(num_dimes, change) = calculate_coins_of_denomination(change, 10)
(num_nickels, change) = calculate_coins_of_denomination(change, 5)
(num_pennies, change) = calculate_coins_of_denomination(change, 1)

Now you've got the values for num_dollars etc, it's just a question of printing your output in the desired format.

As a final note, avoid using profanity or insults in code comments, even for little experimental programs like these. The brief satisfaction that it yields does not justify the potential cost in terms of looking unprofessional or developing bad habits.


Save parameters in a "key: value" format I have been playing with Java for around a year and I started writing this API for storing data in files. I wrote this method which will save the parameters in a "key: value" format in a file.

The method is getting fairly long and I am just wondering if there is a better/shorter/more efficient way to do this.

public void set(String key, Object value) {
    try {
        BufferedWriter bw = new BufferedWriter(new FileWriter(this.path, true));
        BufferedReader br = new BufferedReader(new FileReader(this.path));
        ArrayList<String> file = new ArrayList<String>();
        if(this.getValue(key) != null) {
            for(String line; (line = br.readLine()) != null;) {
                if(line.startsWith(this.COMMENT_PREFIX)) {
                    file.add(line);
                } else if(line.isEmpty()) {
                    file.add("");
                } else {
                    try {
                        if(!line.contains(":")) {
                            throw new MyFormatException("Missing a colon!");
                        }
                    } catch(MyFormatException e) {
                        e.printStackTrace();
                        bw.close();
                        br.close();
                        return;
                    }
                    String lineKey = line.substring(0, line.indexOf(":"));
                    String lineValue = line.substring(line.indexOf(":") + 2);
                    if(lineKey.equals(key)) {
                        if(value instanceof ArrayList) {
                            StringBuilder newValue = new StringBuilder(value.toString());
                            newValue.replace(value.toString().lastIndexOf("]"), value.toString().lastIndexOf("]") + 1, "");
                            newValue.replace(value.toString().indexOf("["), value.toString().indexOf("[") + 1, "");
                            bw.append(key + ": " + newValue.toString());
                            bw.newLine();
                        } else {
                            file.add(lineKey + ": " + value);
                        }
                    } else {
                        file.add(lineKey + ": " + lineValue);
                    }
                }
            }
            this.clear();
            for(String line : file) {
                bw.append(line);
                bw.newLine();
            }
        } else {
        if(value instanceof ArrayList) {
                StringBuilder newValue = new StringBuilder(value.toString());
                newValue.replace(value.toString().lastIndexOf("]"), value.toString().lastIndexOf("]") + 1, "");
                newValue.replace(value.toString().indexOf("["), value.toString().indexOf("[") + 1, "");
                bw.append(key + ": " + newValue.toString());
                bw.newLine();
            } else {
                bw.append(key + ": " + value);
                bw.newLine();
            }
        }
        br.close();
        bw.close();
    } catch(Exception e) {
        e.printStackTrace();
    }
}

There are many things deeply wrong with this method:

It does too much. It seems completely unaware of the single responsibility principle. It's extremely important that every method has one clear main responsibility. This method has so many it's not even clear which one is the most important:

Parse a config file?
Update a config file?
Update an internal hashmap?

You really need to split this up.
The entire method body is wrapped in one giant try-catch block. This is a bad practice. There are many points inside where an exception can be thrown, and by wrapping the entire method like this, you cannot distinguish the failure point and respond gracefully. And since you catch all exceptions and just print on the console (another bad practice by the way), the method will appear to have succeeded, even if it actually failed. As such, the method cannot be trusted.
The way you use MyFormatException is absolutely awful. You throw this poorly named custom exception just to catch it yourself. A simple if statement is the right tool for this, better in every way.
Methods shouldn't be too long in general. Even when they really have a single responsibility. Long methods are hard to understand, test and debug.

A general purpose utility like the one you described and hinted by this implementation can be certainly accomplished in a simpler way.
After you split up this method to smaller functions where each has a clear single responsibility,
the resulting code will be longer than this method.
But it will be composed of smaller component that are easier to understand and test.

There are many other smaller practical problems too:

Declare variables with interface type instead of implementation when possible. For example List instead of ArrayList, like this: List<String> file = new ArrayList<>();
file is a very poor name for a list. It's a list, so name it that way. When I saw file at many places in the code my instinct was that it's probably a File instance, but it's far from it. Very confusing.
The usage this.COMMENT_PREFIX suggests that COMMENT_PREFIX is an instance variables, despite the all capital name which is a convention reserved for static final constants.

I suggest to completely rework this class, splitting up this one big method to smaller methods where each has precisely one responsibility, and post it for another review.


Replacing strings to have a single blank In Kernighan and Ritchie (the C programming language):

  Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.

I wrote the following code.  Do you have advice to improve it?

#include <stdio.h>

/* copy input to output, replacing each
string of one or more blanks by a single blank */

main(){

    int c;
    double nc;
    char otherBlank;

    otherBlank = 'f';

    while ((c = getchar()) != EOF){
        if (otherBlank == 't' && c != ' '){
            /* read a non blank and had a blank before */
            putchar(' ');
            putchar(c);
            otherBlank = 'f';
        }

        else if (c == ' ')
            /* read a blank */
            otherBlank = 't';

        else
            /* read a non blank and had no blank before */
            putchar(c);

    }

}

There a few concerns I have with this program.  Let's go through it line by line:

You don't declare what you are returning from main(), or what parameters you are going to take in.  You should always be declaring these instead of letting the compiler assume them.

int main(void)

You asked in the comments why we should declare this to return an int and not void.  We don't want to just throw away that useful exit status information. There is great answer here that goes into great detail as to why, you should take a look over there.

"But wait!", you say.  "We didn't actually return anything from our main function!  How does this black magic work?"  Yep, I know.  That is just what is declared in the standards.

  C99 & C11 §5.1.2.2(3):

  "...reaching the } that terminates the main() function returns a value of 0."

You don't use your nc variable in your program.  It should be removed.
You declare otherBlank as a char on one line and assign it the character f on the next line.  You should be assigning on the same line as you are declaring in this case.
Analyzing your program further, it is questionable as to why you aren't using a boolean value to represent otherBlank.  You only seem to be using it as a "flag" of a sort, so it makes sense to me to represent it as the bool type.  Keep in mind that you will have to include <stdbool.h> if you choose to change this.
Further refactoring your program, there is no need for the otherBlank variable.  Use a while loop to capture all of the ' ' characters and then output only one ' ' character.  Then continue with the printing of the other non-blank characters.
You don't check putchar for it's return value, as you should be doing.  @Michael went into great detail with this, give his answer a look and an upvote to see why!

Here is what I managed to come up with:

#include <stdio.h>

int main(void)
{
    int c;
    while ((c = getchar()) != EOF) {
        if (c == ' ') {
            while ((c = getchar()) == ' ');
            if (putchar(' ') == EOF) return -1;
            if (c == EOF) break;
        }
        if (putchar(c) == EOF) return -1;
    }
}

Here is how this could be further improved:

Use the function fgets() to capture the input once; looping over each character to capture it manually isn't very efficient (and if your program doesn't handle input properly, it could be dangerous).
Store the input string in a character array and loop over the characters to test them for ' '.  Then make the necessary changes and print out the entire string at once, instead of looping and printing out the individual characters (again, inefficient).


Using Stored Procedures in ColdFusion / Lucee This is how I write all my database interactions now in Lucee:

storedproc
    procedure='OrderDetail.WhereOrderHeaderID' {
    procparam value=session.Usr.UsrID;
    procparam value=url.OrderHeaderID;
    procresult resultset=1 name='OrderDetail';
    procresult resultset=2 name='OrderHeader';
}

Assuming I've done this in SQL Server:

create schema OrderDetail authorization dbo
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'OrderHeader.[get]') AND type in (N'P', N'PC'))
DROP PROC OrderHeader.[get]
GO
CREATE PROC OrderHeader.[get]
(@UsrID Int
,@OrderHeaderID Int
) AS
SELECT OrderHeaderInfo
FROM OrderHeader
WHERE OrderHeaderID = @OrderHeaderID

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'OrderDetail.WhereOrderHeaderID') AND type in (N'P', N'PC'))
DROP PROC OrderDetail.WhereOrderHeaderID
GO
CREATE PROC OrderDetail.WhereOrderHeaderID
(@UsrID Int
,@OrderHeaderID Int
) AS
SELECT Item,Qty
FROM OrderDetail
WHERE OrderHeaderID = @OrderHeaderID
exec OrderHeader.[get] @UsrID,@OrderHeaderID

your code could use some formatting so that it can be read without much effort

create schema OrderDetail authorization dbo
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'OrderHeader.[get]') AND type in (N'P', N'PC'))
DROP PROC OrderHeader.[get]
GO
CREATE PROC OrderHeader.[get]
(@UsrID Int
,@OrderHeaderID Int
) AS
SELECT OrderHeaderInfo
FROM OrderHeader
WHERE OrderHeaderID = @OrderHeaderID

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'OrderDetail.WhereOrderHeaderID') AND type in (N'P', N'PC'))
DROP PROC OrderDetail.WhereOrderHeaderID
GO
CREATE PROC OrderDetail.WhereOrderHeaderID
(@UsrID Int
,@OrderHeaderID Int
) AS
SELECT Item,Qty
FROM OrderDetail
WHERE OrderHeaderID = @OrderHeaderID
exec OrderHeader.[get] @UsrID,@OrderHeaderID

you also should be consistent about Capitalization of Keywords in SQL, it will make it easier to see what is going on in your SQL.

CREATE SCHEMA OrderDetail authorization dbo
IF EXISTS (SELECT *
               FROM sys.objects
               WHERE object_id = OBJECT_ID(N'OrderHeader.[get]')
                   AND type IN (N'P', N'PC'))
DROP PROC OrderHeader.[get]
GO

CREATE PROC OrderHeader.[get]
(
    @UsrID INT
    ,@OrderHeaderID INT
) AS
SELECT OrderHeaderInfo
    FROM OrderHeader
    WHERE OrderHeaderID = @OrderHeaderID

IF EXISTS (SELECT *
               FROM sys.objects
               WHERE object_id = OBJECT_ID(N'OrderDetail.WhereOrderHeaderID')
                   AND type IN (N'P', N'PC'))
DROP PROC OrderDetail.WhereOrderHeaderID
GO

CREATE PROC OrderDetail.WhereOrderHeaderID
(
    @UsrID INT
    ,@OrderHeaderID INT
) AS
SELECT Item
    , Qty
    FROM OrderDetail
    WHERE OrderHeaderID = @OrderHeaderID

EXEC OrderHeader.[get] @UsrID,@OrderHeaderID

That is much easier to read, wouldn't you agree?


speed up square digit function for the following function

#!/usr/bin/ruby -w
e=0
g=0
h=1
while h < 10000000
    a = h
    f=0
    while f !=1 && f!= 89
        d=0
        f=0
        while a.to_s[d] != nil
            e = a.to_s[d]
            b = e.to_i
            f += b**2
            d+=1
        end
        a = f
        f = 89 if [4,16,37,58,20,42,145].include? f
    end
    h += 1
    g+=1 if f == 89
end
p g

this is a porject i'm working for a certain programming practice website which i will not mention by name so my solution can't be found on google, but it's the 92nd problem. it runs about three times slower than i would like, everything that i have tried to speed it up with ends up adding a few seconds instead of subtracting, and that icludes storing values in arrays for later comparisons, any suggestions?
run time is 3:10 and the result is 8581146
the purpose of this code is to find square digit chains from one to ten thousand that either end up in one or eighty-nine and to run a count of how many end at eightnine and out put the total when the program finishes. i get the square digit result for a number by first converting it into a string and converting individual chars back into nums and running it repeatedly, i have an if statement to catch f if it hits any of the numbers on the eighty-nine loop so i can shave off a few cycles here and there.

In benchmarking various techniques for this question, I found the biggest speed boost was in abandoning string conversion in favor of %10 to get the individual digits - try using a method like this to get your sums:

def sum_square_digits(n)
  sum = 0
  until n == 0
    sum += (n % 10) ** 2
    n /= 10
  end
  sum
end


I've started Tuples to LINQ and I'm not sure if it's an anti pattern I have

public static class TupleExtensions {

    public static IEnumerable<T> SelectMany<T>(this IEnumerable<Tuple<T, T>> te)
    {
        foreach (var t in te)
        {
            yield return t.Item1;
            yield return t.Item2;
        }
    }

    public static IEnumerable<T> SelectMany<T, U>(this IEnumerable<U> source, Func<U, Tuple<T, T>> fn)
    {
        foreach (var s in source)
        {
            var t = fn(s);
            yield return t.Item1;
            yield return t.Item2;
        }

    }

    public static IEnumerable<T> SelectMany<T, U>(this IEnumerable<U> source, Func<U, Tuple<T, T, T>> fn)
    {
        foreach (var s in source)
        {
            var t = fn(s);
            yield return t.Item1;
            yield return t.Item2;
            yield return t.Item3;
        }

    }

    public static IEnumerable<T> SelectMany<T, U>(this IEnumerable<U> source, Func<U, Tuple<T, T, T,T>> fn)
    {
        foreach (var s in source)
        {
            var t = fn(s);
            yield return t.Item1;
            yield return t.Item2;
            yield return t.Item3;
            yield return t.Item4;
        }

    }
}

I can then do as a trivial example

IEnumerable<int> source = ...
source.SelectMany(i=>Tuple.Create(i, i+1, i+2))

Obviously the tuple must have the same types throughout. My use
case is where I have a mathematical solver which will always return
two solutions for a given input. Returning a list makes it unclear
how many solutions would be returned.

However in the end I would want all my solutions merged. For example

static Tuple<Point,Point> Intersect(this Shape shape, Line other);

Shape shape = ...
IEnumerable<Line> lines = ...

IEnumerable<Point> intersections = lines.SelectMany(line=>shape.Intersect(line));

Is there some good reason not to treat Tuple<T,T,T....> as a container that we can flatten?

In general, I think this pattern makes sense, because it clearly expresses what the method returns and lets you easily do the computation you want to do with the result.

Some thoughts:

I don't see any reason why your extension methods should only work on a collection of Tuples and not on a single Tuple. Because of that, I would probably write extension methods that convert a single Tuple to IEnumerable:

public static IEnumerable<T> ToEnumerable<T>(this Tuple<T, T> tuple)
{
    yield return tuple.Item1;
    yield return tuple.Item2;
}

Since this would make the code you showed more complicated, it might make sense to also keep SelectMany(), but express it using ToEnumerable():

public static IEnumerable<T> SelectMany<T>(
    this IEnumerable<Tuple<T, T>> tuples)
{
    return tuples.SelectMany(t => t.ToEnumerable());
}

public static IEnumerable<T> SelectMany<T, U>(
    this IEnumerable<U> source, Func<U, Tuple<T, T>> selector)
{
    return source.SelectMany(x => selector(x).ToEnumerable());
}

It might make sense to create custom types that mean “pair (triple, …) of items of the same type”. As a side benefit, you wouldn't need custom ToEnumerable() or SelectMany() extensions, since those types could implement IEnumerable<T> directly.


Adding to a dictionary and skipping duplicate keys What is the cleanest way to use dictionaries and protect against an unhandled ArgumentException if the key already exists in the dictionary?

I'd like to say that I can always guarantee uniqueness upstream, but I'm dealing with legacy code and mildly corrupt data from an old bug in the system.

I find myself using this pattern frequently but wonder if there is a better way.

public void AddToDictionaryContainsKey(Dictionary<int,string> myDictionary, int myKey, string myValue )
{
    if (!myDictionary.ContainsKey(myKey))
    {
        myDictionary.Add(myKey, myValue);
    }
}

Maybe a try/catch block -  but this seems less readable.  The advantage is that if I ever do decide to log the problem I have a place to do it.

public void AddToDictionaryTryCatch(Dictionary<int, string> myDictionary, int myKey, string myValue)
{
    try
    {
        myDictionary.Add(myKey, myValue);
    }
    catch (ArgumentException e)
    {
        // keep on truckin'
    }
}

The dictionaries are relatively small (typically < 1000 entries) so I prefer readability over performance.

Generating and handling exceptions is considered to be an expensive operation, so if(! x.ContainsKey()) is better. Yeah, the code example I see in MSDN uses try/catch but that's to illustrate the exception not advocate that as "best practice."  Documentation I've read is pretty adamant about not throwing exceptions needlessly.

And you don't need try/catch to trap the duplicate key; just an else to the above if.


FixedArray Class In Ruby I had an assignment recently to build a FixedArray using Ruby. It's supposed to simulate a FixedArray in C, that is, an array that allocates a certain amount of arbitrary memory when initialized, and that this amount of memory can neither increase nor decrease. It cannot dynamically resize itself like Ruby's default Array (because at a low-enough level, there's no such thing as arrays that can resize themselves...only FixedArrays). If you try to access an index that is out of bounds, you get an exception.

Note that I cannot use Ruby's default Array (since that's kinda misses the point of the assignment, in my opinion), so you get something like this:

class OutOFBoundsException < RuntimeError
end

class FixedArray
  attr_reader :size

  def initialize(size)
    @size = size
    size.times do |index|
      self.instance_variable_set(:"@index#{index}", nil)
    end
  end

  def get(index)
    if instance_variable_defined?(:"@index#{index}")
      self.instance_variable_get("@index#{index}")
    else
      raise OutOFBoundsException
    end
  end

  def set(index, value)
    self.instance_variable_set(:"@index#{index}", value)
    value
  end

end

This seems rather hacky to me though. I'm having to use metaprogramming in order to create FixedArrays, and metaprogramming ought to be used as a last resort. Is there a better solution that can allow me to create FixedArrays?

I'm not sure that delegating to a normal array is not the best solution. Normally when I create classes like this the intent is to provide a more rigid interface over an array and delegation would be the best solution. What you have will certainly work but is going to be extremely in-efficient speed wise since those get/set/defined methods are quite slow. i.e. This is great as an exercise but I would never write code like this in a real world app.

Some changes I would make:

The set method does no checking so it is currently possible to add items to the array
Instead of instance_variable_defined? I would use (0..size).include?(index)
I would extract the index checking into a method and use it in both set/get:

def check_index!(index)
  raise OutOfBoundsError unless (0..size).include?(index)
end

I would add [] and []= aliases for get and set

Also most style guides recommend against using self. redundantly to prefix method names.


Sorting a set of numbers in a file using Java BitSet I have implemented a program to sort a file consisting of numbers. The program generates a different output file with all numbers sorted in it. I have implemented this program using BitSet and want to understand BitSet.

public class Application {
    public static void main(String[] args) throws Exception {

        String inputFile = "c:\\temp\\numbers.txt";
        NumberFileSorter.sort(inputFile, 100);
    }
}

class NumberFileSorter {

    private NumberFileSorter() {
    }

    public static void sort(String inputFile, int maxValue) throws Exception {

        final BitSet bitSet = createBitSet(inputFile, maxValue);
        final String outputFile = deriveOutputFile(inputFile);
        writeBitSet(bitSet, outputFile);
    }

    private static BitSet createBitSet(String inputFile, int maxValue)
            throws Exception {

        final FileInputStream stream = new FileInputStream(inputFile);
        final InputStreamReader streamReader = new InputStreamReader(stream);
        final BufferedReader buffReader = new BufferedReader(streamReader);

        String line = null;
        int totalBits = maxValue + 1;
        BitSet bitSet = new BitSet(totalBits);

        try {
            while ((line = buffReader.readLine()) != null) {
                int number = Integer.parseInt(line);
                bitSet.set(number, true);
            }
        } finally {
            buffReader.close();
            streamReader.close();
            stream.close();
        }

        return bitSet;
    }

    private static String deriveOutputFile(String inputFile) {
        String outputFileName = Paths.get(inputFile).getParent().toString()
                + "/output.txt";
        return outputFileName;
    }

    private static void writeBitSet(BitSet bitSet, String outputFile)
            throws Exception {

        final File file = new File(outputFile);
        file.createNewFile();

        final FileOutputStream outputStream = new FileOutputStream(file);
        final OutputStreamWriter writer = new OutputStreamWriter(outputStream);
        final BufferedWriter buffWriter = new BufferedWriter(writer);

        try {
            for (int bitIndex = 0; bitIndex < bitSet.length(); bitIndex++) {
                if (bitSet.get(bitIndex)) {
                    buffWriter.write(Integer.toString(bitIndex));
                    buffWriter.newLine();
                }
            }
        } finally {
            buffWriter.close();
            writer.close();
            outputStream.close();
        }
    }
}

I request reviewers to provide feedback on the following:

Is existing code readable? What are changes required to make it more readable?
Is it advisable to unit test sorting logic by decoupling it from the file-system by introducing appropriate interfaces and using dependency injection?
Can this program be made more reliable and robust?
Can this code be structured differently for the better?
Would you integration test it or unit test it?  Could you explain the reason?

Overall your code is very well formatted and readable but I have some complaints at the moment:

Don't declare all methods with throws Exception. Only declare the Exceptions you really need to declare, such as IOException. Declaring throws Exception will force the caller to also catch all RuntimeExceptions, which I say is a big no-no as that could potentially catch important bugs (NPEs for example) in your code. I prefer to let RuntimeExceptions cascade up the hierarchy, without catching them.
Your deriveOutputFile is as far as I can see only called from one place, and consists of only one line. Does it really need to be it's own method? I'd also say that it's name is somewhat ambiguous. deriveOutputFileName would be better.
Your entire class is static. I'm not so sure about this decision. If you'd want to test it in any way you would probably want it non-static, as you then could use a mocking framework to simulate the file input.

Regarding your questions I have some comments:

There's a really good question on StackOverflow about Testing internal implementation or public behaviour
Decoupling the sorting from the file system sounds like a very good idea and would make your code re-usable, so that you could easily use it in another project if needed. By all means, if you really want to then you can abstract things more by making the sorting an interface, and possibly the file system an interface. Remember that there's a risk of over-engineering though. Always remember the rule of YAGNIT.


Extract left text outside the parenthesis if any Im trying to extract the text on the left, outside the parenthesis ():

import re
clean_title = re.match(r'(.*)\(.*\)', title.lower())
if clean_title:
   return clean_title.group(1).rstrip()

Any suggestions to improve it, maybe without regex?

Expected results:

>>'Alone in the Dark (The Cincinnati Series Book 2)'
>>'alone in the dark'

Assuming the text on the left cannot contain opening parenthesis, splitting by the first opening parenthesis might work as well:

>>> clean_title = 'Alone in the Dark (The Cincinnati Series Book 2)'
>>> clean_title.split('(', 1)[0].lower().rstrip()
'alone in the dark'

Note that it will not fail even if there are no parenthesis:

>>> clean_title = 'Test'
>>> clean_title.split('(', 1)[0].lower().rstrip()
'test'

As far as the regular expression approach, you might also use re.sub() which would not require checking if there is a match or not. And, as a bonus, let's account for the extra space before the parenthesis:

>>> re.sub(r"(.*?)\s?\(.*?\)", r"\1", clean_title).lower()
'alone in the dark'

Or:

>>> re.sub(r"\s?\(.*?\)", r"", clean_title).lower()
'alone in the dark'

You can also do the lowering part in a replacement function:

>>> re.sub(r"(.*?)\s?\(.*?\)", lambda m: m.group(1).lower(), clean_title)
'alone in the dark'

Also note that I'm using non-greedy regular expressions.


Effeciency Project Euler #1 If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
  Find the sum of all the multiples of 3 or 5 below 1000.

Could someone point out if there is something wrong with the code; where I should optimize/modify it?

import java.util.Scanner;

public class SumBelowN {

    private double getSum(int N) {
        int n1 = 3;
        int next_n1 = 3;
        int n2 = 5;
        int next_n2 = 5;
        double sum = 0;

        while (next_n1 < N || next_n2 < N) {
            if (next_n1 == next_n2) {
                sum += next_n1;
                next_n1 += n1;
                next_n2 += n2;
                continue;
            } else if (next_n1 < next_n2) {
                sum += next_n1;
                next_n1 += n1;
                continue;
            } else {
                sum += next_n2;
                next_n2 += n2;
                continue;
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int i = sc.nextInt();

        // print the sum of all the numbers below 'i'
        // which are divisible by both 3 and 5.
        SumBelowN sumBelowN = new SumBelowN();

        System.out.println("Sum: " + sumBelowN.getSum(i));
        sc.close();
    }
}

I'm assuming that you did read about the solution that runs in constant time, but wanted to add your own non-constant solution.

continue

Your continue statements are unnecessary; you can just remove them.

Naming

Your naming violates every standard for Java. Java uses camelCase and doesn't allow names to start with uppercase letters.

It is also generally discouraged to use numbers in names if they can be avoided, which in this case they can: n1 could be called three, and n2 could be five. If you want to stay flexible, use firstMultiple and secondMultiple or something similarly expressive.

Constants

As n1 and n2 are constants, I would declare them as static fields.

Comments

As your solution is not straightforward, I would add a comment or two about how it works.

Efficiency

In case you're interested, here are the results that I get if I compare your solution with the solutions from the other thread (mentioned in the comments):

name                       per call (mean, ns)     per call (median, ns)     95th percentile (ns)     total (ms)     runs
three loops                280                     277                       256                      0.224          1000000
without function calls     392                     392                       362                      0.3136         1000000
getSum                     694                     695                       641                      0.5552         1000000
with function calls        3739                    3766                      3338                     2.9912         1000000


Query performance of this Select Where each Column is a Select I would like to know how to improve the performance of the following query:

SELECT          Kunde.Nachname,
                Kunde.Vorname,
                Kunde.Debitorennummer,
                sum(Abmeldestatus) AS Abmeldestatus,
                Ab1.Fruehstuck,
                Best1.Menu1,
                Best2.Menu2,
                Ab2.Vesper,
                Ab3.Abendbrot

FROM            Kunde
LEFT OUTER JOIN
                (   SELECT      EssenTyp AS Fruehstuck,
                                RefKundeId
                     FROM       Abbestellungen
                     WHERE      ([date] =@Datum)
                     AND        (EssenTyp = 0)
                ) AS Ab1 ON Ab1.RefKundeId = Kunde.KundeId

LEFT OUTER JOIN
                (   SELECT      BestellDetails.Anzahl AS Menu1,
                                Bestellung.RefKundeId
                    FROM        Bestellung
                    INNER JOIN  BestellDetails ON Bestellung.BestellId = BestellDetails.RefBestellId
                    WHERE       (BestellDetails.Datum = @Datum)
                    AND         (BestellDetails.SpaltenNr = 0)
                ) AS Best1 ON Best1.RefKundeId = Kunde.KundeId

LEFT OUTER JOIN
                (   SELECT      BestellDetails.Anzahl AS Menu2, Bestellung.RefKundeId
                    FROM        Bestellung
                    INNER JOIN  BestellDetails ON Bestellung.BestellId = BestellDetails.RefBestellId
                    WHERE       (BestellDetails.Datum = @Datum)
                    AND         (BestellDetails.SpaltenNr = 1)
                ) AS Best2 ON Best2.RefKundeId = Kunde.KundeId

LEFT OUTER JOIN
                (   SELECT      EssenTyp AS Vesper,
                                RefKundeId
                    FROM        Abbestellungen
                     WHERE      ([date] =@Datum)
                    AND         (EssenTyp = 1)
                ) AS Ab2 ON Ab2.RefKundeId = Kunde.KundeId

LEFT OUTER JOIN
                (   SELECT      EssenTyp AS Abendbrot,
                                RefKundeId
                    FROM        Abbestellungen
                     WHERE      ([date] =@Datum)
                    AND         (EssenTyp = 2)
                ) AS Ab3 ON Ab3.RefKundeId = Kunde.KundeId

LEFT OUTER JOIN
                (   SELECT      AbmeldeId AS Abmeldestatus,
                                RefKundenId
                    FROM        Abmelden
                     WHERE      (StartDate <= @Datum)
                    AND         (EndDate IS NULL OR EndDate >= @Datum)
                ) AS Abm ON Abm.RefKundenId  = Kunde.KundeId

INNER JOIN  dbo.iter_intlist_to_tbl(@Kunden) AS i ON Kunde.KundeId = i.number

GROUP BY    Kunde.Nachname,
            Kunde.Vorname,
            Kunde.Debitorennummer,
            Ab1.Fruehstuck,
            Best1.Menu1,
            Best2.Menu2,
            Ab2.Vesper,
            Ab3.Abendbrot

The query above takes 13sec to execute for 100 Kunden which is not acceptable.

My function iter_intlist_to_tbl takes a list of numbers (IDs) and creates a table with them.

I build my SELECT based on multiple SELECTs which are OUTER JOIN to return what I expect.

The result looks like:

Nachname | Vormane | Debitorennummer | Fruehstuck | Menu1 | Menu2 | Vesper | Abendbrot
--------------------------------------------------------------------------------------
Schmiedt | Lee     | 123456789       | NULL        |   1  |  NULL |   1    |    1
Müller   | Marie   | 123456700       |     1       | NULL |  NULL |  NULL  |    NULL

Execution plan:

You could try to use a PIVOT statement in order to convert values of several rows into columns. I show it for Abbestellungen.EssenTyp here. You will have to combine it with the rest of your query.

SELECT RefKundeId, [0] AS Fruehstuck, [1] AS Vesper, [2] AS Abendbrot
FROM (SELECT RefKundeId, EssenTyp FROM Abbestellungen WHERE [date] = @Datum) a
PIVOT
(
    MAX (EssenTyp)
    FOR EssenTyp IN ([0], [1], [2])
) AS pvt;

I am not sure which value you want to return for the EssenTyp columns. Your query returns the EssenTyp id, but your example result set returns 1. So may be you want a count? Then you would have to replace MAX(EssenTyp) by SUM (1) or COUNT(EssenTyp). If you are storing a number of meals say in a column Anzahl (german 'number'), then write SUM(Anzahl). In any case you need an aggregate function for the pivot operation.

Will it be faster? I don't know. Make experiments. Instead of making two independent pivot queries for Abbestellungen and Bestellung, you could combine the two in a UNION query and pivot them together:

SELECT
    RefKundeId,
    [0] AS Fruehstuck, [1] AS Vesper, [2] AS Abendbrot, [10] AS Menu1, [11] AS Menu2
FROM (
    SELECT RefKundeId, EssenTyp AS nr, 1 AS value
    FROM Abbestellungen
    WHERE [date] = @Datum

    UNION ALL

    SELECT B.RefKundeId, D.SpaltenNr + 10 AS nr, D.Anzahl AS value
    FROM
        Bestellung B
        INNER JOIN BestellDetails D
            ON B.BestellId = D.RefBestellId
    WHERE D.Datum = @Datum
) A
PIVOT
(
    SUM (value)
    FOR nr IN ([0], [1], [2], [10], [11])
) AS pvt;


Multiple Accordion on one page I have two accordions on the same page

First, I have a page, Freemarker, that includes two other Freemarkers that have the accordion.

[#include "page1.ftl"]
[#include "page2.ftl"]

On page1:

&nbsp;&nbsp;&nbsp;&nbsp;Page1

On page2:

&nbsp;&nbsp;&nbsp;&nbsp;Page2

In the Javascript file:

$(document).ready(function(){
  $('#toggle-image').attr("class", "toggle-image-expand");
    //Hide (Collapse) the toggle containers on load
    $(".toggle-container").hide();

    $("h3.trigger").click(function(){
        $(this).toggleClass("active").next().slideToggle("slow");

        if($('#toggle-image').attr("class") == "toggle-image-collapse") {
            $('#toggle-image').attr("class", "toggle-image-expand");
        } else {
            $('#toggle-image').attr("class", "toggle-image-collapse");
        }
        return false;
    });
});

$(document).ready(function(){
  $('#toggle-image2').attr("class", "toggle-image-expand");
    //Hide (Collapse) the toggle containers on load
    $(".toggle-container2").hide();

    $("h3.trigger2").click(function(){
        $(this).toggleClass("active").next().slideToggle("slow");

        if($('#toggle-image2').attr("class") == "toggle-image-collapse") {
            $('#toggle-image2').attr("class", "toggle-image-expand");
        } else {
            $('#toggle-image2').attr("class", "toggle-image-collapse");
        }
    return false;
});

It works fine, but the redundant code I used in JS is typical and the difference is on the variable it uses. How could I make it dynamic?

Don't rely on IDs when your cases are general.  Rely on classes.
Use the DOM hierarchy to reference elements

page1 (added a container div, "toggle-image" class name):

      &nbsp;&nbsp;&nbsp;&nbsp;Page1

page2 (same changes):

      &nbsp;&nbsp;&nbsp;&nbsp;Page2

JavaScript (generalized with class selectors, sibling selectors, improved class logic):

 $(document).ready(function(){
      $('.toggle-image').attr("class", "toggle-image-expand");
      //Hide (Collapse) the toggle containers on load
      $(".toggle-container").hide();

      $("h3.trigger").click(function(){
          $(this).toggleClass("active").next().slideToggle("slow");

          $(this).children('.toggle-image')
              .toggleClass('toggle-image-collapse')
              .toggleClass('toggle-image-expand');

          return false;
      });
 });


Dynamic array of Years I wanted to make a dynamic select statement from this year to 10 years. This gets the job done, but I feel like it's a little much.

 form_dropdown('year', array_combine(range(date('Y'), date('Y')+10), range(date('Y'), date('Y')+10)), set_value('year'));

Specifically, is there a better way to create this array, other than this?

array_combine(range(date('Y'), date('Y')+10), range(date('Y'), date('Y')+10))

Desired output (at least for this year):

Array
(
    [2014] => 2014
    [2015] => 2015
    [2016] => 2016
    [2017] => 2017
    [2018] => 2018
    [2019] => 2019
    [2020] => 2020
    [2021] => 2021
    [2022] => 2022
    [2023] => 2023
    [2024] => 2024
)

In order to get the output that you wanted, using array_combine will most likely be your best bet. You can simplify your statements pretty easily because variables are you friends:

$current_year = date('Y');
$date_range = range($current_year, $current_year+10);

form_dropdown('year', array_combine($date_range, $date_range), set_value('year'));

Addendum by @brettsantore

I think this solves what I thought to be a problem, the combining of so many functions. I ended up simplifying it a little more.

$current_year = date('Y');
$range = range($current_year, $current_year+10);
$years = array_combine($range, $range);


Basic Reverse Polish CL Parser K and R Exercise 5-10

  Write the program expr, which evaluates a reverse Polish expression
  from the command line, where each operator or operand is a separate
  argument.

  For example,

expr 2 3 4 + *

  evaluates

2 * (3+4)

#include <stdio.h>
#include "expression_parser.h"

int parse_polish(int size, char *expression[])
{
    char *entry;
    int temp1, temp2;

    if (expression[1] && ((isdigit(*expression[1]) &&
        isdigit(*expression[2])))) {
        stack_init(&size, expression);
        expression++;
        for ( ; *expression; expression++) {
            if (isdigit(*(entry = *expression)))
                push(atoi(entry));
            else {
                switch (*entry) {
                    case '+':
                        push(pop() + pop());
                        break;
                    case '-':
                        temp1 = pop();
                        temp2 = pop();
                        push(temp1 - temp2);
                        break;
                    case '*':
                        push(pop() * pop());
                        break;
                    case '/':
                        temp1 = pop();
                        temp2 = pop();
                        if (!(temp2))
                            return -1;
                        else
                            push(temp1 / temp2);
                        break;
                    default:
                        return -1;
                }
            }
        }
        return pop();
    } else
          return -1;
}

Repository

Your function is called parse_polish(), but it actually does much more: it evaluates the expression too!
pop() takes no arguments, and push() takes just one argument, so I deduce that they must be operating on a global variable, which is bad practice.
Your function returns -1 on error, but that could very well also be the result of a legitimate calculation.  I recommend one of the following strategies:

Passing the calculation result as an out-parameter.
Requiring the caller to initialize the stack and pass it to your evaluator.  The caller can then pop the result off the stack (which could be empty in case of an error).
Using floating-point calculations.  Not only do you get floating-point division, but you also have the possibility of returning positive infinity, negative infinity, or NaN.

Why do you test that *expression[1] and *expression[2] are digits?  What if the expression consists of a single token { "5" } — shouldn't the result be 5?
Perhaps you want to allow negative integers as inputs too?


Correct way to refer to a view in Android What is the correct way of referring to a view (a) or (b).?

(a).

TextView textView = (TextView) rootView.findViewById(R.id.text);
textView.setText("Some Text");

(b).

((TextView) rootView.findViewById(R.id.text)).setText("Some Text");

I sometimes use the combination of both in my code. Will that affect my structure negatively in any way?

Is there any disadvantage / advantages when using any of those?

The first is a sequence of method calls, the second is a method call chain. They are equivalent, so both are correct.

Which way is better really depends on the rest of your code.
For example, instead of this:

((TextView) rootView.findViewById(R.id.text)).setText("Some Text");
((TextView) rootView.findViewById(R.id.text)).append("more text");
((TextView) rootView.findViewById(R.id.text)).setOnClickListener(...);

This is clearly better:

TextView textView = (TextView) rootView.findViewById(R.id.text);
textView.setText("Some Text");
textView.append("more text");
textView.setOnClickListener(...);

It's better, because this does only one lookup in rootView, and it's also more compact.

On the other hand, if you only use the TextView once, then the chained call version is better, because you won't pollute your local scope with a variable you only use once, and it's more compact.

Sometimes I split chained calls for debugging purposes:
it can be hard to see which step failed in a long chain,
and easier to follow the execution step by step.


Build String Hackerrank Online challenge on Hacker Rank.

Please follow the description from the above link.

import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;

class Main {
  private static List<String> substrings(String s) {
    int length = s.length();
    List<String> list = new ArrayList<>();

    for (int i = 0; i < length; i++) {
      for (int j = i + 1; j <= length; j++) {
        list.add(s.substring(i, j));
      }
    }
    return list;
  }

  private static int solve(String text, int A, int C) {
    int length = text.length();
    StringBuilder sb = new StringBuilder(length);
    Set<String> set  = new HashSet<>();

    int cost = 0;
    int len  = 0;
    for (int i = 0; i < length; i++) {
      len = sb.length();
      if (len == 0) {
        sb.append(text.charAt(0));
        set.add(sb.toString());
        cost += A;
        continue;
      }

      while (len > 0) {
        int sum = i + len;
        int end = (sum > length) ? length : sum;
        String lookAhead = text.substring(i, end);
        if (set.contains(lookAhead)) {
          if (lookAhead.length() == 1 && A <= C) {
            cost += A;
          } else {
            cost += C;
          }

          i += len - 1;
          sb.append(lookAhead);
          for (String sub : substrings(sb.toString())) {
            set.add(sub);
          } // end for
          break;
        } // end if
        else {
          if (lookAhead.length() == 1) {
            cost += A;
            sb.append(lookAhead);
            for (String sub : substrings(sb.toString())) {
              set.add(sub);
            } // end for
            break;
          }
          len--;
        } // end else
      } // end while
    } // end for
    //return sb.toString();
    return cost;
  }

  public static void main(String[] args) {
    System.out.println(solve("a", 4, 5));   // 4 A
    System.out.println(solve("ab", 4, 5));  // 8 A + A
    System.out.println(solve("aba", 4, 3)); // 11 A + A + C
    System.out.println(solve("aabaacaba", 4, 5)); // 26 A + A + A + C + A + C
    System.out.println(solve("bacbacacb", 8, 9)); // 42 A + A + A + C + C
  }
}

Note:

I have to confess this time that I really didn't know what I was doing, I spent more than couple of hours on this problem and still its faling on some test cases and times out (which I knew since its kind of brute force).

The only positive things that I can conclude from my not so worthy effort is although I came up with the basic idea pretty fast but in process of writing code I was really struggling to follow the flow and had to dance with the logic for more than an hour basically I had a hard time converting my idea to code.

Any suggestion would be really helpful as I have some major interview in couple of days so, some tips would defintely help.

Second and most important thing is that how to check the correctness of such algorithms since I had to print values several times and it became very painful.

Apart from that I would like to know an effcient algorithm.

private static List<String> substrings(String s) {

Concerning speed, this is the first bug. There are too many substrings O(n**2) and generating all of them is wasting O(n**3) time (as the copying has linear complexity). You're using it in a loop, so it may be O(n**4), really slow.
It'd be slightly better to generate a Set rather than a List. Given the input aabaacaba, there are quite some substrings repeated. I see, you're using a Set later. You could avoid any intermediate collection when you implemented
private static void addSubstringsTo(Collection<String> result, String s)`

instead.
But this is a minor optimization. A much bigger one would be to observe, that all substrings are already there, except for those ending on the current position.
But even this is by far not the fastest way.

 if (len == 0) {

This seems to be superfluous. Sure, you can only append, but the reason is that there are no usable substrings. So you can save this test and proceed in the usual way.
} // end for

Please don't. Keep your method short enough so that such garbage is unnecessary. While IIRC the style guide requires indentantion of 2 spaces, I use 4, so that the code structure is easier to see.

int length = text.length();
...
int len  = 0;

That's crazy. len is a pretty common abbreviation for length, many dislike it, I find it acceptable. But using both in the same method is perverted.

int end = (sum > length) ? length : sum;

You surely mean
int end = Math.min(sum, length);

It's the same, but it doesn't make me think.

} // end if
    else {
      if (lookAhead.length() == 1) {

You're repeating yourself in the code below this. Something like
if (lookAhead.length() == 1 || set.contains(lookAhead)) {
    ... append, update the set, break
}

should work.

You could get some speed by not generating the strings. While the HashSet lookup is very fast, you're putting therein much more strings than you can ever use... so you're wasting time. Something like
 text.substring(0, i).lastIndexOf(lookAhead)

should be faster. But still not perfect.

Concerning the cost optimization, you're making at least two mistakes.
It's possible that appending a substring costs more than appending a character twice, so you probably should look at A * lookAhead.length() compared to C (which is called B in the linked challenge).
You're using a greedy strategy. Appending some string may be advantageous at a moment, but it may prevent appending a much longer string later. I guess, you should always explore every possibility, except when one is clearly worse than some other. By "clearly worse" I actually mean "the same string at higher cost" as a shorter string may be better sometimes.

Concerning speed, I guess, not generating any strings is the way to go. As the text is given, all you need is to remember the substring indexes. Calling substring is wasting time, create a trivial immutable class containing start and end instead.
An exactly optimizing algorithm would probably keep track of the cheapest way of creating text.substring(0, i) for every value of i. In each step, it'd try to build a longer substring and store or update its cost. It's not trivial and I haven't solved it yet, so I can't give more details. But look at dynamic programming, which is the general way of solving such problems.
Slow code
Note that one big problem with your algorithm is that it's too long. You wrote "I really didn't know what I was doing" and I trust you on it. This happens to everyone, when the code gets too long and/or disorganized. Refactoring (e.g., extracting methods or classes) is the way to go (thought sometimes rewriting the good parts from scratch is better).
Without much thinking I wrote this O(3) code. It solves 10 test cases out of 21, when it fails, it's due to timeout.
private static int solve(int a, int b, String text) {
    // Cost as a function of length.
    final int costs[] = new int[text.length() + 1];
    Arrays.fill(costs, Integer.MAX_VALUE);
    costs[0] = 0; // Empty string is free.

    // Minimum length to be copied (as copying less is not worth it).
    final int minLen = Math.min(1, b / a);
    for (int i=1; i<costs.length; ++i) {
        costs[i] = Math.min(costs[i], costs[i-1] + a);
        final String start = text.substring(0, i);

        // We copy no more than we have and no more than we need.
        for (int len=minLen; len<=i && i+len<costs.length; ++len) {
            boolean found = start.contains(text.substring(i, i+len));
            if (!found) break;
            costs[i+len] = Math.min(costs[i+len], costs[i] + b);
        }
    }
    return costs[text.length()];
}


Accelerate computing a Gram-like matrix with large files I have N(>1000) .npy files, each has ~80MB, each contains a vector of high dimension (P).

I have to deal with these data with the code below:

G = np.zeros((N, N))
for i in range(N):
    vi = np.load(str(i)+'.npy')
    for j in range(i, N, 1):
        vj = np.load(str(i)+'.npy')
        G[i, j] = process(vi, vj)
        G[j, i] = G[i, j]

post_process(G)

It takes a lot of time depending on reading files and I'd like to accelerate it.

Is there any suggestion?

Try to cache as much as possible.

I suppose buying more RAM and read all .npy files in advance is out of the question.

But, for instance, if it is possible to keep the data of 20 files in memory, you could read 10 files for vi-data and 10 files for vj-data, now you can fill a block of 10x10 in matrix G at the cost of 20 file reads instead of 10 + 10x10 = 110 file reads. Looping and indexing will get a bit more complicated of course.


App to Encrypt and Decrypt file public sealed class Class1
{
    Class1()
    {

    }
    private static readonly object padlock = new object();
    private static Class1 instance = null;
    public static Class1 Instance
    {
        get
        {
            if (instance == null)
            {
                lock (padlock)
                {
                    if (instance == null)
                    {
                        instance = new Class1();
                    }
                }
            }
            return instance;
        }
    }

    public bool EncryptFile(string path)
    {
        string ext = Path.GetExtension(path).Replace(".","");
        string filename = Path.GetFileNameWithoutExtension(path);

        byte[] b= System.Text.ASCIIEncoding.ASCII.GetBytes(ext);
        string encrypted = Convert.ToBase64String(b);
        var newPath = path.Replace(filename+"."+ext, filename+"_"+ encrypted + ".vik");

        try
        {
            string password = @"vik12389"; // Your Key Here
            UnicodeEncoding UE = new UnicodeEncoding();
            byte[] key = UE.GetBytes(password);

            string cryptFile = newPath;
            FileStream fsCrypt = new FileStream(cryptFile, FileMode.Create);

            RijndaelManaged RMCrypto = new RijndaelManaged();

            CryptoStream cs = new CryptoStream(fsCrypt,
                RMCrypto.CreateEncryptor(key, key),
                CryptoStreamMode.Write);

            FileStream fsIn = new FileStream(path, FileMode.Open);

            int data;
            while ((data = fsIn.ReadByte()) != -1)
                cs.WriteByte((byte)data);
            fsIn.Close();
            cs.Close();
            fsCrypt.Close();
            File.Delete(path);

            return true;

        }
        catch(Exception e)
        {
            return false;
        }
    }

    public bool DecryptFile(string path)
    {
        string ext = Path.GetExtension(path).Replace(".", "");
        string filename = Path.GetFileNameWithoutExtension(path);

        string[] splitFilename = filename.Split('_');

        byte[] b = Convert.FromBase64String(splitFilename[1]);

        string decryptedfileext = System.Text.ASCIIEncoding.ASCII.GetString(b);

        var newPath = path.Replace(filename + ".vik", splitFilename[0] + '.'+ decryptedfileext);
        try
        {
            string password = @"vik12389"; // Your Key Here

            UnicodeEncoding UE = new UnicodeEncoding();
            byte[] key = UE.GetBytes(password);

            FileStream fsCrypt = new FileStream(path, FileMode.Open);

            RijndaelManaged RMCrypto = new RijndaelManaged();

            CryptoStream cs = new CryptoStream(fsCrypt,
                RMCrypto.CreateDecryptor(key, key),
                CryptoStreamMode.Read);

            FileStream fsOut = new FileStream(newPath, FileMode.Create);

            int data;
            while ((data = cs.ReadByte()) != -1)
                fsOut.WriteByte((byte)data);

            fsOut.Close();
            cs.Close();
            fsCrypt.Close();

            return true;

        }
        catch (Exception e)
        {
            return false;
        }

    }

}

My Project Link on GitHub :https://github.com/vivianm94/EncryptFile.
how do I improve my code any suggestion.any features that could be added to the project

So, the most interesting bits about this code are the wildly differing styles throughout. It seems as it's almost copy-and-pasted from several sources. The reason I bring this up is because consistency is a hallmark of clean and maintainable code. A few things I noticed:

There's a debunked use of "double-checked locking" to attempt to use a lazily-instantiated singleton. Two things with this: A. This class doesn't have state and could be static to begin with, and thus do not need to worry about instances at all, and B. There's a very easy way these days to have a lazy singleton: the Lazy<T> class. You'll see its usage below.
There's a mish-mash of ASCIIEncoding.ASCII and new UnicodeEncoding(). The canonical way to access predefined encodings is through static members of the Encoding class: Encoding.ASCII and Encoding.Unicode.
Path.Combine() is wisely used to, of course, combine paths. But then string concatenation is used to pop an extension on the file name. Path.ChangeExtension() exists for just this task.
x.Close() isn't needed if you wrap your IDisposable resources in using blocks. This also has the benefit of guaranteeing disposal/closing in the case of an exception (it's syntactic sugar for a try..finally construct`.
There's a mix of using and not using var for variable declarations. Since the latter is less than the former, standardize on just using the actual type name for declarations.
I added two more - you don't need to read/write the file byte by byte. These are streams for a reason, and .NET gives us a handy method CopyTo to take care of the details. Also, CreateEncrpytor and CreateDecryptor return IDisposable-implementing classes, so I extracted them into their own usings.

Putting all that together, the class now looks like (note that I went with Lazy<T> rather than static class):

public sealed class Class1
{
    private static readonly Lazy<Class1> instance = new Lazy<Class1>(() => new Class1());
    public static Class1 Instance => instance.Value;

    public bool EncryptFile(string path)
    {
        string ext = Path.GetExtension(path).Replace(".", string.Empty);
        string filename = Path.GetFileNameWithoutExtension(path);

        byte[] b = Encoding.ASCII.GetBytes(ext);
        string encrypted = Convert.ToBase64String(b);
        string newPath = path.Replace(Path.ChangeExtension(filename, ext), filename + "_" + encrypted + ".vik");

        try
        {
            string password = @"vik12389"; // Your Key Here
            byte[] key = Encoding.Unicode.GetBytes(password);

            string cryptFile = newPath;
            using (FileStream fsCrypt = new FileStream(cryptFile, FileMode.Create))
            using (RijndaelManaged RMCrypto = new RijndaelManaged())
            using (ICryptoTransform ct = RMCrypto.CreateEncryptor(key, key))
            using (CryptoStream cs = new CryptoStream(fsCrypt,
                ct,
                CryptoStreamMode.Write))
            using (FileStream fsIn = new FileStream(path, FileMode.Open))
            {
                fsIn.CopyTo(cs);
            }

            File.Delete(path);

            return true;

        }
        catch(Exception e)
        {
            return false;
        }
    }

    public bool DecryptFile(string path)
    {
        string ext = Path.GetExtension(path).Replace(".", string.Empty);
        string filename = Path.GetFileNameWithoutExtension(path);

        string[] splitFilename = filename.Split('_');

        byte[] b = Convert.FromBase64String(splitFilename[1]);

        string decryptedfileext = Encoding.ASCII.GetString(b);

        string newPath = path.Replace(Path.ChangeExtension(filename, "vik"), splitFilename[0] + '.'+ decryptedfileext);
        try
        {
            string password = @"vik12389"; // Your Key Here

            byte[] key = Encoding.Unicode.GetBytes(password);

            using (FileStream fsCrypt = new FileStream(path, FileMode.Open))
            using (RijndaelManaged RMCrypto = new RijndaelManaged())
            using (ICryptoTransform ct = RMCrypto.CreateDecryptor(key, key))
            using (CryptoStream cs = new CryptoStream(fsCrypt,
                ct,
                CryptoStreamMode.Read))
            using (FileStream fsOut = new FileStream(newPath, FileMode.Create))
            {
                cs.CopyTo(fsOut);
            }

            return true;

        }
        catch (Exception e)
        {
            return false;
        }

    }

}


Convert IP address to its binary representation For a recent lab at the university we had to match the longest prefix for an IP (v4) address by using a Trie data structure. The code works fine, but it takes about 2 minutes to load a 14 million-line routing table. I examined what was causing the slowness, and it was the (String) IP to (String) binary format conversion.

For example, the IP address 127.0.0.1 should be converted to 01111111000000000000000000000001. I my original method (slow) uses String.format, which I find much more readable and easy to follow. I then wrote a different method using a temporary char[], filled with '0' to use as padding.

The speedup of the fast method is about 6x. Below is a stripped down version for demonstration and measurement:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        final String ip = "127.0.0.1";
        String binaryIp;
        final long start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i ++) {
            binaryIp = fast(ip);
        }

        long fast = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i ++) {
            binaryIp = slow(ip);
        }

        long slow = System.currentTimeMillis();

        System.out.println("Fast time: " + (fast - start) + " ms");
        System.out.println("Slow time: " + (slow - fast) + " ms");
    }

    public static String fast(String ip) {

        StringBuilder bStringBuilder = new StringBuilder();
        String ipParts[] = ip.split("\\.");

        for (String ipPart : ipParts) {

            String binString = Integer.toBinaryString(Integer.parseInt(ipPart));
            int length = 8 - binString.length();
            char[] padArray = new char[length];
            Arrays.fill(padArray, '0');
            bStringBuilder.append(padArray).append(binString);
        }
        System.out.println(bStringBuilder.toString());
        return bStringBuilder.toString();
    }

    public static String slow(String ip) {

        StringBuilder bStringBuilder = new StringBuilder();
        String ipParts[] = ip.split("\\.");

        for (String ipPart : ipParts) {

            String binString = Integer.toBinaryString(Integer.parseInt(ipPart));
            String binaryPart = String.format("%8s", binString).replace(' ', '0');
            bStringBuilder.append(binaryPart);
        }
        return bStringBuilder.toString();
    }
}

For which the output is:

Fast time: 3936 ms
Slow time: 23527 ms

I can't think of a more efficient way to pad a binary string appropriately... I don't think that there's any need to improve the slow method as it's now obsolete compared to fast. However, is there any way that I can improve fast?

PS - magic number 8 would be a magic number that never changes, so I don't think I need a static final int ipv4SectionLength = 8 or anything like that!

I don't have access to your test file, but try:

private static final String[] PAD_ZEROS=
    new String[] {
        "00000000",
        "0000000",
        "000000",
        "00000",
        "0000",
        "000",
        "00",
        "0",
        ""
    };

   public static String fast(final String ip) {
        final StringBuilder result = new StringBuilder();
        final String octals[] = ip.split("\\.");
        for (final String octal: octals) {
            final String binaryString = Integer.toBinaryString(Integer.parseInt(octal));
            result.append(PAD_ZEROS[binaryString.length()]);
            result.append(binaryString);
        }
        return result.toString();
    }

In general, I'd suggest avoiding hungarian notation (bStringBuilder), unnecessary abbreviations(binString), and magic numbers (if you keep the 8, it should be in a private static final class-level variable).

Note that your performance testing is flawed. The problem is the VM performs internal optimizations as it runs which can improve the performance of the system. You should test either fast or slow, but not both, in one execution. Don't test the same string over and over again, but pull in your routing file. Then, unless your whole application is to run this one method on the file and then stop, you should run for a while, throw out that data, then start measuring. Maybe do 2 executions of the file, but only time the second one. That imitates the method being called from a live system that's been running a while, instead of a cold system.

Two more things: as @rofl said, presize the StringBuilder. Also pull the System.out.println() out of your method - it's an artificial drag on the performance.

-- Working off of @rofl's other suggestion, this is 25% faster on my machine than your fast method, including the time to populate the map. It does consume more memory, and it eagerly maps numbers which may not be used. It is less elegant than @rofl's suggestion, and possibly slower, but I find it easier to read.

private static final String[] PAD_ZEROS =
        new String[] {
            "00000000",
            "0000000",
            "000000",
            "00000",
            "0000",
            "000",
            "00",
            "0",
            ""
        };

private static final Map<String, String> MAP =
        new HashMap<String, String>(256);

private static void populateMap() {
    for (int i = 0; i < 256; i++) {
        final String binaryString = Integer.toBinaryString(i);
        MAP.put(
            Integer.toString(i),
            PAD_ZEROS[binaryString.length()] + binaryString);
    }
}

public static String faster(final String ip) {
    final StringBuilder result = new StringBuilder(32);
    final String octals[] = ip.split("\\.");
    for (final String octal: octals) {
        result.append(MAP.get(octal));
    }
    return result.toString();
}


Adding a new node in an AVL tree I was working on a class assignment today and I wrote this code which works perfectly fine. It looks tho kind of has too much 'if statements' in it, and I was thinking that it could be written much better than this. (I'm still a beginner in C).

Do you suggest any new techniques that I could use/learn to avoid so many if statements and how could you improve this code without making it much longer or complex?

The code is a part of much bigger code to add a new node in an AVL tree.

if (avlt->root == NULL) {
    new = &(avlt->root);
    parent = NULL;
}
if (avlt->root != NULL) {
    parent = avlt->root;
    while (1)
    {
        if (parent->value > value)
        {
            if (parent->left) parent = parent->left;
            else
            {
                new = &(parent->left);
                break;
            }
        }
        else if (parent->value < value)
        {
            if (parent->right) parent = parent->right;
            else
            {
                new = &(parent->right);
                break;
            }
        }
        else return;
    }
}

These are the structs, maybe they can be useful for you to understand the code:

struct AVLNode {
  struct AVLNode* left;
  struct AVLNode* right;
  struct AVLNode* parent;
  int value;
  int height;
};

struct AVLTree {
  struct AVLNode* root;
  int numberOfNodes;
};

typedef struct AVLNode AVLNode;
typedef struct AVLTree AVLTree;

Complexity
One method for determining how complex your code is, is called cyclomatic complexity. You basically count the number of branches in the code to determine its complexity. I count about 10 in the above code snippet. A cyclomatic complexity of 10 is often considered the maximum you should have in good readable code. (This is of course subjective.) By that standard, this code is fine. I do think the code could be made more clear, though.
Infinite Loops
I generally hate infinite loops in code unless it's some top-level thing like an event loop that realistically should never stop. The infinite loop you've created is not one of those cases. It has a very clear criteria for stopping. When the value is either greater than the greatest value along this path, or less than the minimum value along this path, or equal to any value along the path. Fixing that will make the code clearer, though I don't know if it will reduce the number of conditions to check. It might be worth breaking it out into a separate function. Something like this:
void whateverFunctionThisIs(AVLTree* avlt)
{
    //...
    if (avlt->root == NULL) {
        new = &(avlt->root);
        parent = NULL;
    }
    else
    {
        new = findPositionInTree(avlt->root);
    }

    if (new == NULL) {
        return;
    }
    // ...
}

That immediately reduces the complexity of that function from 10 to 3. Now we can rewrite the loop in its own function like this:
AVLNode* findPositionInTree(AVLNode* parent)
{
    struct AVLNode* new = NULL;

    int found = 0;
    do {
        if (parent->value > value)
        {
            if (parent->left)
            {
                parent = parent->left;
            }
            else
            {
                new = &(parent->left);
                found = 1;
            }
        }
        else if (parent->value < value)
        {
            if (parent->right)
            {
                parent = parent->right;
            }
            else
            {
                new = &(parent->right);
                found = 1;
            }
        }
        else
        {
            found = 1;
        }
    } while (!found);

    return new;
}

Even though we have the same number of if statements, it seems clearer to me without the break and return statements. And this function only has a cyclomatic complexity of 8.
Reducing ifs
You could reduce the number of if statements if you don't actually need to use parent after the loop ends by inverting the sense of the inner-most ifs. For example, instead of:
if (parent->right)
{
    parent = parent->right;
}
else
{
    new = &(parent->right);
    found = 1;
}

you could do this:
if (parent->right != NULL)
{
    new = &(parent->right);
    found = 1;
}
parent = parent->right;

At this point parent is NULL so you can't use it for anything in the future, so I really don't like that idea. But it does eliminate 2 if statements thereby reducing your complexity. (If you're using the infinite loop, then the found = 1; becomes just a break and parent is no longer NULL. But that feels gross to me.)


An idiom to use the same view function to create or edit an object? Here is the skeleton of my (first!) Django app:

# models.py
class Task(models.Model):
    description = models.CharField(max_length = 200)
    ...

# forms.py
class AddTaskForm(forms.ModelForm):
    class Meta:
        model = Task

I then created two views using AddTaskForm: one to create a new instance, the other to edit an existing one.  I was able to refactor those two views (and the function they call) into one, but I'm not sure I got the best possible result...

# urls.py:
(r'^yata/add_task/$',              'yata.views.edit'),
(r'^yata/(?P<task_id>\d+)/edit/$', 'yata.views.edit'),

# views.py
def edit(request, task_id = None):
    t = get_object_or_404(Task, pk=task_id) if task_id else None
    if request.method == 'POST':
        form = AddTaskForm(request.POST, instance=t)
        if form.is_valid():
            form.save()
            return HttpResponseRedirect('/yata/')
    else:
        form = AddTaskForm(instance = t)

    # Either the form was not valid, or we've just created it
    d = {'form': form}
    if task_id:
        # The template needs the id to decide if the form's action
        # is .../add_task or .../{{id}}/edit
        d['id'] = t.id
    return render_to_response('yata/edit.html', d,
        context_instance=RequestContext(request))

And here is the corresponding part of the template:

# edit.html
{% if id %}
    <form action="/yata/{{ id }}/edit/" method="post">
{% else %}
    <form action="/yata/add_task/" method="post">
{% endif %}
{{ form.as_p }}
<input type="submit" value="Save!" />
</form>

Is there a better Django idiom to handle this 'add or create' issue?
Or can this be considered a correct way?

I have looked at your code and I think that it actually looks pretty clean and straight forward. However, I would suggest that you make it more DRY by using reverse() to figure out what action to assign to the form.

views.py:

if task_id:
    action = reverse(edit, args=[task_id])
else:
    action = reverse(edit)
d['action'] = action

edit.html:

<form action="{{ action }}" method="post">
    {{ form.as_p }}
    <input type="submit" value="Save!" />
</form>


Generating random number from a binomial distribution In my application of Monte Carlo simulation, the crucial part is to generate a random number from a binomial distribution with parameters n = size and p = 0.5. Here is my current implementation

#include <stdio.h>
#include <stdint.h>
#include <x86intrin.h>

int64_t rbinom(int64_t size) {
    if (!size) {
        return 0;
    }

    int64_t result = 0;
    while (size >= 64) {
        uint64_t random64;
        while (!_rdrand64_step(&random64)) {
            fprintf(stderr, "HW_RND_GEN not ready\n");
        }
        result += _popcnt64(random64);
        size -= 64;
    }

    uint64_t random64;
    while (!_rdrand64_step(&random64)) {
        fprintf(stderr, "HW_RND_GEN not ready\n");
    }
    result += _popcnt64(random64 & ~(UINT64_MAX << size));

    return result;
}

However, the result of benchmarking terrifies me:

I'm spending 99.68% of the runtime on this function! How can I optimize it?

The result doesn't need to be cryptographically secure, as long as it's good enough for Monte Carlo simulations.

The RDRAND instruction generated from the _rdrand64_step intrinsic is actually very slow, though high quality (modulo some concerns about back doors). Depending on the processor it may take hundreds (Ivy Bridge through Skylake) or even thousands (Intel Atom, AMD) of cycles per RDRAND. So just replacing the random number generator will help a lot.

For example, xoroshiro128+ is a relatively fast PRNG, it has some weaknesses but they don't seem too bad for this purpose. An interesting aspect is that it contains no operation that must go to execution port 1 on Intel processors, so its operations do not "fight" the popcnt much, in contrast to PRNGs that contain multiplication.

So overall, something like this:

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

static uint64_t s[2];

uint64_t next(void) {
    const uint64_t s0 = s[0];
    uint64_t s1 = s[1];
    const uint64_t result = s0 + s1;

    s1 ^= s0;
    s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
    s[1] = rotl(s1, 37); // c

    return result;
}

int64_t rbinom(int64_t size) {
    if (!size) {
        return 0;
    }

    int64_t result = 0;
    while (size >= 64) {
        result += _popcnt64(next());
        size -= 64;
    }

    result += _popcnt64(next() & ~(UINT64_MAX << size));

    return result;
}

Elsewhere in the application, the state s must be seeded with a non-zero random-enough number. For example, you could use _rdrand64_step to seed it once, at the start of the application.

But different strategies are possible. With a size in the thousands or even millions (as indicated in the comments), SIMD could be used both to generate pseudo-random bits and to accumulate the pop-counts. Using some techniques from Faster Population Counts Using AVX2 Instructions (mainly, reducing the amount of actual pop-counting by using carry-save addition) and Xorshift+ as PRNG (I avoid rotate because AVX2 does not have them built in, and multiplication because AVX2 also has no 64bit integer multiply built in), it could look like this:

__m256i bigstate0, bigstate1;

__m256i xorshift128plus_avx2(__m256i *state0, __m256i *state1)
{
    __m256i s1 = *state0;
    const __m256i s0 = *state1;
    *state0 = s0;
    s1 = _mm256_xor_si256(s1, _mm256_slli_epi64(s1, 23));
    *state1 = _mm256_xor_si256(_mm256_xor_si256(_mm256_xor_si256(s1, s0),
        _mm256_srli_epi64(s1, 18)),
        _mm256_srli_epi64(s0, 5));
    return _mm256_add_epi64(*state1, s0);
}

__m256i popcnt_AVX2(__m256i x) {
    const __m256i popcntLUT = _mm256_setr_epi8(
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
    );
    const __m256i nibmask = _mm256_set1_epi8(15);
    const __m256i zero = _mm256_setzero_si256();

    __m256i L = _mm256_shuffle_epi8(popcntLUT, _mm256_and_si256(x, nibmask));
    x = _mm256_srli_epi16(x, 4);
    __m256i H = _mm256_shuffle_epi8(popcntLUT, _mm256_and_si256(x, nibmask));
    return _mm256_sad_epu8(_mm256_add_epi8(L, H), zero);
}

__m256i CSA(__m256i a, __m256i b, __m256i c, __m256i *carry) {
    __m256i t0 = _mm256_xor_si256(a, b);
    __m256i t1 = _mm256_xor_si256(t0, c);
    *carry = _mm256_or_si256(_mm256_and_si256(a, b), _mm256_and_si256(t0, c));
    return t1;
}

int64_t rbinom_AVX2(int64_t size) {
    if (!size) {
        return 0;
    }

    int64_t result = 0;

    __m256i sum1 = _mm256_setzero_si256();
    __m256i sum2 = sum1;
    __m256i sum4 = sum1;
    __m256i sum = sum1;
    while (size >= 2048) {
        __m256i sample0 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample1 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample2 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample3 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample4 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample5 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample6 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        __m256i sample7 = xorshift128plus_avx2(&bigstate0, &bigstate1);
        // reduce weight 1
        __m256i c0, c1, c2, c3;
        __m256i t0 = CSA(sample0, sample1, sample2, &c0);
        __m256i t1 = CSA(sample3, sample4, sample5, &c1);
        __m256i t2 = CSA(sample6, sample7, sum1, &c2);
        sum1 = CSA(t0, t1, t2, &c3);
        // reduce weight 2
        __m256i c4, c5;
        __m256i t3 = CSA(c0, c1, c2, &c4);
        sum2 = CSA(c3, t3, sum2, &c5);
        // reduce weight 4
        __m256i c6;
        sum4 = CSA(sum4, c4, c5, &c6);
        sum = _mm256_add_epi64(sum, _mm256_slli_epi64(popcnt_AVX2(c6), 3));
        size -= 2048;
    }
    sum1 = popcnt_AVX2(sum1);
    sum2 = popcnt_AVX2(sum2);
    sum4 = popcnt_AVX2(sum4);
    sum = _mm256_add_epi64(sum, sum1);
    sum = _mm256_add_epi64(sum, _mm256_slli_epi64(sum2, 1));
    sum = _mm256_add_epi64(sum, _mm256_slli_epi64(sum4, 2));
    result += _mm256_extract_epi64(sum, 0);
    result += _mm256_extract_epi64(sum, 1);
    result += _mm256_extract_epi64(sum, 2);
    result += _mm256_extract_epi64(sum, 3);

    while (size >= 64) {
        result += _mm_popcnt_u64(next());
        size -= 64;
    }

    result += _mm_popcnt_u64(next() & ~(UINT64_MAX << size));

    return result;
}

Algorithmic tricks such as the alias method may be appropriate. I have no experience with this so I cannot explain it or even really recommend it, but it's something to look into.


Convert image to grayscale To convert JPEG file, C function, bgraToGrayscale is called from Swift.

Is there a better way to

1.allocate memory and

2.access pointers

than the ways they have been done in code below?

And maybe things that have been completely missed, like freeing memory?

converter.swift

func BGRAToGrayscale(srcImg: CGImage) -> CGImage {
    let BytesPerPixel = 4

    guard let srcProv = srcImg.dataProvider else { fatalError("dataProvider is nil") }
    guard let srcProvData = srcProv.data else { fatalError("dataProvider.data is nil") }

    let srcPtr = CFDataGetBytePtr(srcProvData)
    let srcSize = srcImg.width * srcImg.height * BytesPerPixel

    var destPtr = [CUnsignedChar](repeating: 0, count: srcSize)
    bgraToGrayscale(&destPtr, srcPtr, Int32(srcImg.width), Int32(srcImg.height))

    let destCgContext = CGContext(data: &destPtr,
                                  width: srcImg.width, height: srcImg.height,
                                  bitsPerComponent: srcImg.bitsPerComponent,
                                  bytesPerRow: srcImg.bytesPerRow,
                                  space: srcImg.colorSpace!,
                                  bitmapInfo: srcImg.bitmapInfo.rawValue)

    guard let destImg = destCgContext?.makeImage() else {
      fatalError("Destination Image is nil")
    }

    return destImg
}

converter.c (slow way of converting to grayscale, will write assembly code for this, just for the sake of learning :-) )

void bgraToGrayscale( unsigned char * __restrict dest, const unsigned char* src, int width, int height ) {
  int BYTES_PER_PIXEL = 4;
  int numPixels = width * height;

  for( int idx=0; idx < numPixels; idx++ ) {

    float weight = ((float)src[0]) * 0.11 +
                  ((float)src[1]) * 0.59 +
                  ((float)src[2]) * 0.3;

    dest[0] = (int)weight;
    dest[1] = (int)weight;
    dest[2] = (int)weight;
    dest[3] = src[3];
    dest += BYTES_PER_PIXEL;
    src += BYTES_PER_PIXEL;
  }
}

// Not following Swift naming conventions, should be bytesPerPixel
let BytesPerPixel = 4

// Better to make function throwable and throw specific error.
guard let srcProv = srcImg.dataProvider else { fatalError("dataProvider is nil") }
guard let srcProvData = srcProv.data else { fatalError("dataProvider.data is nil") }

For unwrap of srcImg.colorSpace! is not good solution, I would recommend to use guard ... else and throw an exception if value is nil.

Overall: why you are using abbreviations and shortcuts for every variable/constant name? It is much harder to read such code


Robot Return to Origin The task
is taken from leetcode

  There is a robot starting at position (0, 0), the origin, on a 2D
  plane. Given a sequence of its moves, judge if this robot ends up at
  (0, 0) after it completes its moves.

  The move sequence is represented by a string, and the character
  moves[i] represents its ith move. Valid moves are R (right), L (left),
  U (up), and D (down). If the robot returns to the origin after it
  finishes all of its moves, return true. Otherwise, return false.

  Note: The way that the robot is "facing" is irrelevant. "R" will
  always make the robot move to the right once, "L" will always make it
  move left, etc. Also, assume that the magnitude of the robot's
  movement is the same for each move.

  Example 1:

  Input: "UD" Output: true  Explanation: The robot moves up once, and
  then down once. All moves have the same magnitude, so it ended up at
  the origin where it started. Therefore, we return true.

  Example 2:

  Input: "LL" Output: false Explanation: The robot moves left twice. It
  ends up two "moves" to the left of the origin. We return false because
  it is not at the origin at the end of its moves.

const arr = "UD";

My imperative solution:

function judgeCircle(moves) {
  let horizontal = 0;
  let vertical = 0;

  [...moves].forEach(m => {
    switch(m) {
      case "U":
        ++vertical;
        break;
      case "D":
        --vertical;
        break;
      case "R":
        ++horizontal;
        break;
      case "L":
        --horizontal;
        break;
      default:
        // be a good code
    }
  });
  return !(horizontal) && !(vertical);
};

console.log(judgeCircle(arr));

My functional solution:

const judgeCircle2 = moves => {
  const {h, v} = [...moves].reduce((acc,m) => {
    switch(m) {
      case "U":
        ++acc.v;
        return acc;
      case "D":
        --acc.v;
        return acc;
      case "R":
        ++acc.h;
        return acc;
      case "L":
        --acc.h;
        return acc;
      default:
        // be a good code
    }
  }, {h: 0, v: 0});
  return !h && !v;
};

console.log(judgeCircle2(arr));

It could be made more functional by avoiding the mutation of acc. The effects are contained within judgeCircle so it's not a big deal, but it feels like if you're going to mutate the accumulator, you might as well just use an imperative loop.

I also preferred to be explicit about the final check. I find the intent of !h && !v isn't quite as clear as h == 0 && v == 0;.

I ended up with:

const judgeCircle3 = moves => {
  const [hori, vert] = [...moves].reduce(([h, v], move) => {
    switch(move) {
      case "U":
        return [h, v + 1];

      case "D":
        return [h, v - 1];

      case "R":
        return [h + 1, v];

      case "L":
        return [h - 1, v];
    }

  }, [0, 0]);

  return hori == 0 && vert == 0;
};

The need for the switch here is unfortunate, but the only other alternative I could think of was some mess where a you'd do a lookup on a map which returned a function that returned a "altered" accumulator state.

I also got rid of the default since it didn't seem to be doing anything. You could have done error handling in there (and should in most cases), but if it's a challenge with predefined input, that's probably not necessary unless it's part of the challenge.


Big O notation for quicksort implementation I am trying to find out what would be the Big O notation of a quick sort implementation I wrote. If I can get some analysis on the code, that would be great.

public class JavaApplication1 {

public static void main(String args[]) {

    int[] input = { 23, 31, 1, 21, 36, 72};
    System.out.println("Before sorting : " + Arrays.toString(input));
    quickSort(input); // sort the integer array using quick sort algorithm
    System.out.println("After sorting : " + Arrays.toString(input));

    // input with duplicates
    int[] withDuplicates = { 11, 14, 16, 12, 11, 15};
    System.out.println("Before sorting : " + Arrays.toString(withDuplicates));
    quickSort(withDuplicates); // sort the integer array using quick sort algorithm
    System.out.println("After sorting : " + Arrays.toString(withDuplicates));
}

/**
 * public method exposed to client, sorts given array using QuickSort
 * Algorithm in Java
 * @param array
 */
public static void quickSort(int[] array) {
   if(array.length <= 1) return;
   int leftwall = 0;
   int rightwall  = array.length - 1 ;
   int pivot = array[array.length/2];
   rechelperquickSort(array,leftwall,rightwall,pivot);
}

public static void rechelperquickSort(int[] array ,int left , int right , int pivot ){

    int idx;
    idx = left;

    if(left>=right) return;

    while(idx<=right){

        if(pivot > array[idx])swapinarray(array,left++,idx);

        idx++;
    }
    if(left >= right) return;
    pivot = array[left+1];
    rechelperquickSort(array,left+1,right,pivot);
    rechelperquickSort(array,0,left,array[left/2]);
}

public static void swapinarray(int[] array,int leftelementidx, int rightelementidx){
    int tmp = array[leftelementidx];
    array[leftelementidx] = array[rightelementidx];
    array[rightelementidx] = tmp;
}

}

Doesn't work

Your sort doesn't work on this array:

int[] input = { 4, 5, 3, 2, 6, 1};

The output is:

Before sorting : [4, 5, 3, 2, 6, 1]
After sorting : [1, 2, 3, 5, 4, 6]

What's wrong?

One problem with your quicksort is that it doesn't always rearrange items to the left and right of the pivot.  If you pick the pivot that is the smallest element in the array, no swaps will be made.  Thus, you should either pick the leftmost item to be the pivot so that "no swaps" will just work, or swap the pivot item into the correct spot after your loop is finished.

Another problem with it is that you have a hardcoded 0 which is wrong:

rechelperquickSort(array,0,left,array[left/2]);

That 0 there should be the original value of left passed into the array.  Otherwise you are creating more work.


CamelCase word count Online challenge on Hacker Rank.

  Problem Description

  Alice wrote a sequence of words in CamelCase as a string of letters, S ,
  having the following properties:

  It is a concatenation of one or more words consisting of English
  letters. All letters in the first word are lowercase. For each of the
  subsequent words, the first letter is uppercase and rest of the
  letters are lowercase. Given, print the number of words in  on a new
  line.

  Input Format

  A single line containing string S.

  Constraints

  Output Format

  Print the number of words in string.

  Sample Input

saveChangesInTheEditor

  Sample Output

5

public class Solution {
    private static int solve(String input) {
        int len = input.length();
        if (len == 0) {
            return 0;
        }
        int count = 1;
        for (int i = 0; i < len; i++) {
            char c = input.charAt(i);
            if ('A' <= c && c <= 'Z') {
                count++;
            }
            else if (c == ' ') {
                break;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        System.out.println(solve(s));
    }
}

Glaring Deficiencies

What are you doing? You haven't bothered to explain your algorithm, either in the question body or in program comments.
Bugs. As pointed out by @Abhisek, your code prints 3 instead of 2. When you count the number of camelCase words, you should ignore whitespace, in fact, you should treat any non-alphabetic characters as lower-case, as per my understanding of the problem (although this is an edge case).
You haven't bothered to use any of Java's standard libraries. You would find the functions Character.isUpperCase(char), Character.isLowerCase(char) and Character.isWhitespace(char) extremely useful, instead of doing error-prone and language-limited manual checking. Also, String.isEmpty() is always a better check than String.length() == 0.
Non-descriptive naming. Your method does indeed solve a HackerRank problem, but that does not describe it properly. You could name it for what it does, something like getCamelCaseWordCount(String), as per some guidelines for Java method naming (Effective Java by Joshua Bloch).
You only use len once without the emptiness check. In fact, that is not required either, as the general code will handle that too. Just use the emptiness check to set the initial value of the word count to 0 or 1, depending on whether the input is empty or non-empty. respectively. You do not need to return early to avoid the loop as the loop won't iterate in the first place.
For that matter, as Strings are immutable, repeatedly calling .length() on the same String object does not have much overhead, so you do not need len even if you are concerned about the loop.
Avoid all the len business, and use a for-each loop. Kind of like:

for(char c : input.toCharArray()){//for JDK 1.5+
    ...
}

OR,

for(char c : input.chars()){//for JDK 1.8+
    ...
}

As usual, this is a 1-liner with Java 8 streams. This is an exact equivalent:

return in.isEmpty() ? 0 : 1 + in.chars().filter(Character::isUpperCase).count();

Note that the above returns a long, not an int. That's as per the Stream API.

Putting it all together,

Modified Code

public class Test{
    public static long getCamelCaseWordCountNormal(String in){
        long words = in.isEmpty() ? 0 : 1;
        for(char c : in.toCharArray()){
            if(Character.isUpperCase(c)){
                words++;
            }
        }
        return words;
    }

    public static long getCamelCaseWordCountStreams(String in){
        return in.isEmpty() ? 0 : 1 + in.chars().filter(Character::isUpperCase).count();
    }
}