TapeEquilibrium implementation I took a test at Codility called TapeEquilibrium. The task description that I received can be seen here.

I came up with a solution that worked, and I was pretty happy with. However, the performance was apparently awful. The expected time complexity is apparently supposed to be \$O(N)\$, but I got \$O(N * N)\$. I'm not quite sure what exactly that means, but I've heard about it several times.

I'd like some help on improving my solution and get information about what I did wrong and how it could be done better, and why. I'm doing this to learn and improve.

public int solution(int[] A) {
    int min = Int32.MaxValue;
    for (int i = 0; i < A.Length - 1; i++) {
        // p = i + 1
        int part1 = 0, part2 = 0;
        for (int j = 0; j <= i; j++) part1 += A[j];
        for (int j = i + 1; j <= A.Length - 1; j++) part2 += A[j];

        int val = Math.Abs(part1 - part2);
        if (val < min) min = val;
    }
    return min;
}

Style

Initializing of multiple variables on one line removes readability.
Writing for loops on one line removes readability.

Dead code should be deleted (// p = i + 1)

Bug

It seems that you have a little unnoticed bug in your code. Your loop

for (int i = 0; i < A.Length - 1; i++) {

misses the last element of your array.

Problem

Let us assume we have an array A containing 8 elements like

3 5 7 2 5 2 1 3

The ideal divider would be if the arrays left half summed up would be equal to the right half summed up.
Unfortunatetly here

sumLeft = A[0] + A[1] + A[2] + A[3] == 17
sumRight = A[4] + A[5] + A[6] + A[7] == 11
difference = sumLeft - sumRight == 6

So as we see that the left half > right half let us take the last element of the left side and check if 2 * A[half-1] <= difference wich is 2 * 2 <= 6 so we can do

sumLeft = sumLeft - A[3] == 15
sumRight = sumRight + A[3] == 13
difference = difference - 2 * A[3] == 2

Or simplified for sumLeft > sumRight

difference = sumLeft - sumRight;
while (2*A[currentHalf-1] <= difference)
{
    currentHalf = currentHalf -1;
    sumLeft = sumLeft - A[currentHalf]
    sumRight = sumRight + A[currentHalf]
    difference = difference - 2 * A[currentHalf];
}

EDIT : Based on @Dmitry's comments I rechecked the algorithm and came to the result that this algorithm only works for positive numbers.

And my implementation of the above

public int solution(int[] A)
{
    int length = A.Length;
    int sumLeft = 0;
    int sumRight = 0;

    int currentArrayHalf = length / 2;

    for (int i = 0; i < currentArrayHalf; i++)
    {
        sumLeft = sumLeft + A[i];
        sumRight = sumRight + A[i + currentArrayHalf];
    }

    Boolean isEven = length % 2 == 0;

    if (!isEven) { sumRight = sumRight + A[length - 1]; }

    int step = 1;
    if (sumLeft > sumRight)
    {
        step = -1;
        if (isEven)
        {
            currentArrayHalf--;
        }
    }

    int difference = Math.Abs(sumLeft - sumRight);
    if (difference == 0) { return difference; }

    while (currentArrayHalf >= 0 && currentArrayHalf < length && 2 * A[currentArrayHalf] <= difference)
    {
        sumLeft = sumLeft - A[currentArrayHalf];
        sumRight = sumRight + A[currentArrayHalf];
        difference = difference - 2 * A[currentArrayHalf];
        currentArrayHalf = currentArrayHalf + step;
    }

    return difference;
}


Variant of 2-SUM Problem using Hashtable with multi-threading I am doing a Coursera assignment on Hashtable and my solution is taking too long to run. Here is the problem as described in the assignment:

The goal of this problem is to implement a variant of the 2-SUM algorithm covered in this week's lectures.
The file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.
Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t

Here is my entire Python code:
from collections import defaultdict
import threading

def hash_fn(n):
    M=1999993
    return n%M

def two_sum_present(target):
    global ans
    bool=True
    for x in nums:
        y = target-x
        if y in my_hash_table[hash_fn(y)] and y!=x:
            bool=False
            ans+=1
            return 1
    if bool == True:
        return 0
f = open('_6ec67df2804ff4b58ab21c12edcb21f8_algo1-programming_prob-2sum.txt')
nums=[]
my_hash_table = defaultdict(list)
for line in f.readlines():
    num = int(line.split('\n')[0])
    nums.append(num)
    my_hash_table[hash_fn(num)].append(num)

ans=0
for nr in range(-10000, 10001):
    thr = threading.Thread(target = two_sum_present, args=(nr,))
    thr.start()

print(ans)

Notes:

I found a page for the same problem here, but this solution uses neither hashing nor binary search, so it should take longer than my solution. This solution is essentially this:
 ans = sum(any(n-x in nums and 2*x != n for x in nums) for n in range(-10000, 10001))

The text file can be found here. if someone is interested. But think of it as a  big text file with 1M lines having 1 integer(+ve or -ve) on each line.

'distinct' as mentioned here only means that x+x=t is not a valid 2-sum pair; but two (x, y) pairs where x and y are not same constitute a valid pair

functions

split the work you want to do in logical functions. I try to limit the work that is done in the general script (and thus the global namespace) as much as possible. Lookups of local variable are supposed to be faster, but it make the code easier to read and test as well, so win-win.

hashing

Why device your own hashing? just dumping all the numbers in a set will eliminate all the duplicates, and 1M integers is a limited amount of memory. Certainly a lot less that the defaultdict you use

global variable ans

Instead of passing the global variable ans, the easiest way would be to use the fact that in a numeric context (like sum), True equals 1 and False equals 0, so you can just return True or False in two_sum_present

my take on this:

read the file

Using the fact that a file is an iterator, I would do something like this

def read_file(filename):
    with open(filename, 'r') as file:
        return set(map(int, file))

find the target

About the same as your two_sum_present with my remarks incorporated

def find_target(numbers, target):
    for i in numbers:
        if target - i in numbers and 2 * i != target:
            return True
    return False

iterate over the interval

def find_sums(numbers, start=-10000, end=10000):
    for target in range(start, end + 1):
#         print(target)
        yield find_target(numbers, target)

putting it together

def main(filename, start=-10000, end=10000):
    numbers = read_file(filename)
#     print(f'numbers found: {len(numbers)}')
    return sum(find_sums(numbers, start, end))

if __name__ == '__main__':
    filename = 'data/_6ec67df2804ff4b58ab21c12edcb21f8_algo1-programming_prob-2sum.txt'
    print(main(filename, -100, 100))

All in all, it took 43 seconds to scan those 201 numbers on my system, to find 5 matches. Reading the file took about .6s of that time

This solution is essentially the same as sum(any(n-x in numbers and 2*x != n for x in numbers) for n in range(-100, 101)), but that one took 59s

Multithreading

If you want to, you can divide out all the call to find_target to different workers/cores/... In this case, a frozenset instead of a set might be more appropriate since it's immutable, and will give less problems with concurrency

distinct

As noted by Gareth Rees, the original question is ambiguous on what is mean with distinct numbers x,y. To cover the second interpretation, You can change the set to a collections.Counter, and change the test criterium slightly

from collections import Counter

def read_file_distinct(filename):
    with open(filename, 'r') as file:
        return Counter(map(int, file))

def find_sums_distinct(numbers, start=-10000, end=10000):
    for target in range(start, end + 1):
#         print(target)
        yield find_target_distinct(numbers, target)

def find_target_distinct(numbers, target):
    for i in numbers:
        if target - i in numbers and (2 * i != target or numbers[i] > 1):
            return True
    return False

def main_distinct(filename, start=-10000, end=10000):
    numbers = read_file_distinct(filename)
#     print(f'numbers found: {len(numbers)}')
    return sum(find_sums_distinct(numbers, start, end))

This has an effect on speed, though

%timeit main(filename, -10, 10)

4.51 s ± 32.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit main_distinct(filename, -10, 10)

6.42 s ± 48.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

distinct 2

A slightly different, faster approach can be used to tackle the 2nd interpretation

def find_sums_distinct2(numbers, repetitions,start=-10000, end=10000):
    for target in range(start, end + 1):
#         print(target)
        yield find_target_distinct2(numbers, repetitions, target)

def find_target_distinct2(numbers, repetitions, target):
    for i in numbers:
        if target - i in numbers and (2 * i != target or i in repetitions):
            return True
    return False

def main_distinct2(filename, start=-10000, end=10000):
    numbers = read_file_distinct(filename)
    repetitions = {k for k, v in numbers.items() if ((v > 1) and (start < k < end))}
#     print(repetitions)
    numbers = set(numbers)
#     print(f'{len(numbers)} numbers found, {len(repetitions)} repetitions')
    return sum(find_sums_distinct2(numbers, repetitions, start, end))

%timeit main_distinct2(filename, -10, 10)

4.92 s ± 160 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


Testable network calls Swift I want to make testable network calls using Swift.

For example, I want to download the latest from AWS if and only if it's version is newer than the downloaded file.

In order to do this I've created a function:

func requestDownloadLinkForAWS() {
    DispatchQueue.global(qos: .background).async { [weak self] in
        guard let self = self else {return}
        // Hard coded download for testing - where will this compatibility file be hosted??
        do {
            let decoder = JSONDecoder()
                if let dataResponse = content.data?[0]
                    {
                        if (dataResponse.appMinimumVersion >= appVersionString) && (dataResponse.appTargetVersion >= appVersionString) {
                            if let version = self.stagingBundle.getVersion()
                            {
                                if (version < dataResponse.version) {
                                    self.downloadLatestFileAWS(dataResponse.bucketName, dataResponse.folderName, dataResponse.version)
                                }
                            }
                        }
                    }
            }
        } catch let error as NSError {
            print ("\(error) 2 error")
        }
    }
}

Now my self.downloadLatestFileAWS is an async function that I can easily test.

My problem is to test the function above. There is no output here, but I need to test this function. What refactoring could I do to make this testable?

You can refactor this method (and downloadLatestFileAWS, too), to take an optional completion handler parameter:

func requestDownloadLinkForAWS(completion: @escaping ((Result<URL, Error>) -> Void)? = nil) {
    ...

    do {
        ...
        downloadLatestFileAWS(dataResponse.bucketName, dataResponse.folderName, dataResponse.version, completion: completion)
    } catch let error {
        completion?(.failure(error))
    }
}

func downloadLatestFileAWS(_ bucket: String, _ folder: String, _ version, completion: @escaping ((Result<URL, Error>) -> Void)? = nil) {
    ...
    completion?(.success(url)) // the file URL of the saved file
}

Then you can test it:

func testDownload() {
    var result: String?

    let expectation = self.expectation(description: "download")
    requestDownloadLinkForAWS { result in
        if case .failure(_) = result {
            XCTFail("Download failed")
        }
        expectation.fulfill()
    }
    wait(for: [expectation], timeout: 10)
}

By the way, by adding a completion handler to the download method, it also offers you the opportunity to have the caller specify what UI updates should take place when the download is done. For example, you generally don’t want to bury those UI updates within downloadLatestFileAWS. Also, rather than just printing the error to the Xcode console, the caller can now specify what it wants to do when an error occurs.

That having been said, you might not want to actually perform network requests in unit tests. You might, instead mock the network service, or use URLProtocol to mock it behind the scenes.

But either way, you can make your methods testable by providing them with completion handler closures.


Printing simple SQL comparsion I'm comparing two variables which I'd like to be printed to the console like so:

==Full Ex Vat==
true

Currently the code to do this is:

print '==Full Ex Vat=='
print case when
@aTotalExVat = @sTotalExVat
then 'true' else 'false' end

which I feel isn't as elegant as it could be.

Any tips?

SQL uses three valued logic.

When one of the operands is null the expression evaluates to UNKNOWN not false. Your current code does not take account of this and can be altered as below to do so.

PRINT CASE
        WHEN @aTotalExVat = @sTotalExVat THEN 'true'
        WHEN @aTotalExVat <> @sTotalExVat THEN 'false'
        ELSE 'unknown'
      END

If you wanted to treat NULL = NULL as true and NULL = any not null value as false you could use

DECLARE @Message VARCHAR(5) = CASE WHEN EXISTS(SELECT @aTotalExVat
                                               INTERSECT
                                               SELECT @sTotalExVat)
                                   THEN 'true'
                                   ELSE 'false'
                               END;

PRINT '==Full Ex Vat==';
PRINT @Message;

On SQL Server 2012 there are a couple of new functions that shorten the above somewhat

DECLARE @Message VARCHAR(5) = IIF(EXISTS(SELECT @aTotalExVat
                                         INTERSECT
                                         SELECT @sTotalExVat),
                                  'true',
                                  'false');

PRINT CONCAT('==Full Ex Vat==', CHAR(13), ( CHAR(10) ), @Message);


Solving the Fibonacci series using a for loop I have developed what I believe to be a novel way of coding the Fibonacci series in Java using a for loop. This code appears to work, but I was wondering if this is a good solution and how it could be improved.
 static int loopFibonacci(int num) {
        if(num <1) {
            throw new IllegalArgumentException("this number is not valid for fibonacci series");
        }
        int sum = 1;
        int prev = 0;
        for (int i=1;i<num;i++) {
            sum+=prev;
            prev = sum-prev;
//            System.out.println("sum="+sum+" , prev = "+prev);
        }
        return sum;
    }
}

...what I believe to be a novel way of coding the Fibonacci series...

Ahrm, no. Has been done like that forever.

static int loopFibonacci(int num) {

Do not shorten variables just because you can, it makes the code harder to read and harder to maintain.
Everything without visibility modifiers is by default package-private. In my opinion package-private should be avoided as it leads very easily to hard to maintain coupling of classes and interfaces, and it is very easy to make non-extendable constructs with it.

throw new IllegalArgumentException("this number is not valid for fibonacci series");

Good example of a bad error message. The error message should tell me why the number is not usable, what the not usable number was and what a usable number would be, for example:
throw new IllegalArgumentException("Input argument must be a positive number greater or equal to 1, given <" + Integer.toString(number) + ">.");

for (int i=1;i<num;i++) {

I'm still a very persistent advocate of the rule to only use single-letter variable names when dealing with dimensions. For "simple" for loops using index or counter improve most of the time readability quite a bit.

sum+=prev;

As a note, a += b is not shorthand for a = a + b but for a = (TYPE_A)(a + b), which means that it might silently truncate data, for example when adding a float to an int.

        int sum = 1;
        int prev = 0;
        for (int i=1;i<num;i++) {
            sum+=prev;
            prev = sum-prev;
//            System.out.println("sum="+sum+" , prev = "+prev);
        }

Your logic is rather hard to follow, that is because before you really read it it seems to be doing something completely different. So what you want to do is clear that up, partly by using better names and partly by making the logic easier to follow:
int current = 1;
int previous = 0;

for (int counter = 0; counter < steps; counter++) {
    System.out.print(current);
    System.out.println(" ");

    int next = current + previous;

    previous = current;
    current = next;
}

That makes it rather clear how the logic operates.

Looking at possible performance implications is complicated, in my opinion, but let us look at the generated bytecode before jumping to conclusions:
This is the bytecode created for original solution:
0: iconst_1
1: istore_1        /* sum */
2: iconst_0
3: istore_2        /* prev */
4: iconst_1
5: istore_3        /* i */
6: goto            20
9: iload_1         /* sum */
10: iload_2         /* prev */
11: iadd
12: istore_1        /* sum */
13: iload_1         /* sum */
14: iload_2         /* prev */
15: isub
16: istore_2        /* prev */
17: iinc            i, 1
20: iload_3         /* i */
21: iload_0         /* num */
22: if_icmplt       9
25: iload_1         /* sum */
26: ireturn

And here is the bytecode for my revised solution:
0: iconst_1
1: istore_1        /* current */
2: iconst_0
3: istore_2        /* previous */
4: iconst_0
5: istore_3        /* counter */
6: goto            22
9: iload_1         /* current */
10: iload_2         /* previous */
11: iadd
12: istore          next
14: iload_1         /* current */
15: istore_2        /* previous */
16: iload           next
18: istore_1        /* current */
19: iinc            counter, 1
22: iload_3         /* counter */
23: iload_0         /* steps */
24: if_icmplt       9
27: iload_1         /* current */
28: ireturn

So both solutions are using 22 instructions to accomplish their goals. After removing any noise, the difference boils down to this (original to the left):
13: iload_1         /* sum */        14: iload_1         /* current */
14: iload_2         /* prev */       15: istore_2        /* previous */
15: isub                             16: iload           next
16: istore_2        /* prev */       18: istore_1        /* current */

So the only difference is one sub operation, which we trade for a store operation. The performance difference here will be miniscule, in my opinion.


Convert a boxed integer to an nullable integer with potentially different type Given a boxed integer (with a boxed short, int, ...) I want to convert it to an unboxed, nullable type instead. It should be possible to convert non-matching types (for example: boxed int to short?) Can you please comment on:

using System;

public class Test
{
    public static void Main()
    {
        int? x = Unbox<int>((short)42);
        short? y = Unbox<short>(42);
    }

    static T? Unbox<T>(object x) where T : struct
    {
        return typeof(T) == x.GetType() ? (T)x : (T)Convert.ChangeType(x, typeof(T));
    }
}

You should probably add IConvertible restriction on T, since it is used by Convert.ChangeType method.

Also this check: typeof(T) == x.GetType() looks like an overhead. Convert.ChangeType does nothing if types match. For example, check out Int32 sources:

int IConvertible.ToInt32(IFormatProvider provider) {
    return m_value;
}

So you might as well just check for null instead:

static T? Unbox<T>(object x) where T : struct, IConvertible
{
    if (x == null) return null;
    return (T)Convert.ChangeType(x, typeof(T));
}

Edit: as mentioned by sir t3chb0t, there are cases, where Convert.ChangeType can throw. So it might be a good idea to swallow exceptions inside your method and return null in those cases. But it also can be a very bad idea. It depends on use case, which you should carefully evaluate.


Given a string S and Q query strings(q1,q2,...), check for each query string whether or not it is sub-sequence of S Here is my approach. Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

import java.io.InputStreamReader;
import java.util.Scanner;

public class Query {

public static void main(String[] args) {

    Scanner scanner = new Scanner(new InputStreamReader(System.in));
    String str=scanner.next();
    int n=scanner.nextInt();
    while(n-->0){
        String sub=scanner.next();
        if(isSub(str,sub))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

static boolean isSub(String str, String sub){
    int j=0;
    int x=str.length();
    int y=sub.length();
    for(int i=0;i<x && j<y;i++){
        if(str.charAt(i)==sub.charAt(j)) j++;
    }
    return (j==y);
}
}

Please critique my code and also suggest me how to increase efficiency of this code.

Formatting

Everything inside your class body should be indented by one step further than it currently is.
Binary operators (+,-, ...) are usually surrounded by one space to make reading them easier

Outputting results
Your if-else statement can be easily replaced by a ternary statement because it IMO is too trivial to actually be worth the effort of reading 5 lines for it.
In other cases I'd advocate against using the ternary, but here it's just so crudely obvious I can't help but recommend using it.
Immutability
It's significantly cleaner to not allow changing your reference string after you read it in. Mark effectively final variables as final explicitly to ease reading.
After applying this handful of changes your code looks as follows:
public class Query {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(new InputStreamReader(System.in));
        final String str = scanner.next();
        int n = scanner.nextInt();
        while (n-- > 0) {
            String sub = scanner.next();
            System.out.println(isSub(str,sub) ? "Yes" : "No");
        }
    }
}


LeetCode 284: Peeking Iterator I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem

Given an Iterator class interface with methods: next() and
hasNext(), design and implement a PeekingIterator that support the
peek() operation -- it essentially peek() at the element that will
be returned by the next call to next().
Example:
list: [1,2,3].

Call next() gets you 1, the first element in the list. Now you call
peek() and it returns 2, the next element. Calling next() after that
still return 2.  You call next() the final time and it returns 3, the
last element.  Calling hasNext() after that should return false.

Follow up: How would you extend your design to be generic and work
with all types, not just integer?

Code
#include <vector>

class PeekingIterator : public Iterator {
    int next_num;
    bool num_has_next;

public:
    PeekingIterator(const std::vector<int> &nums) : Iterator(nums) {
        num_has_next = Iterator::hasNext();

        if (num_has_next) {
            next_num = Iterator::next();
        }
    }

    int peek() const {
        return next_num;
    }

    int next() {
        int curr_next = next_num;
        num_has_next = Iterator::hasNext();

        if (num_has_next) {
            next_num = Iterator::next();
        }

        return curr_next;
    }

    bool hasNext() const {
        return num_has_next;
    }
};

Reference
LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename. For this question, the template is:
/*
 * Below is the interface for Iterator, which is already defined for you.
 * **DO NOT** modify the interface for Iterator.
 *
 *  class Iterator {
 *      struct Data;
 *      Data* data;
 *      Iterator(const vector<int>& nums);
 *      Iterator(const Iterator& iter);
 *
 *      // Returns the next element in the iteration.
 *      int next();
 *
 *      // Returns true if the iteration has more elements.
 *      bool hasNext() const;
 *  };
 */

class PeekingIterator : public Iterator {
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        // Initialize any member here.
        // **DO NOT** save a copy of nums and manipulate it directly.
        // You should only use the Iterator interface methods.

    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {

    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    int next() {

    }

    bool hasNext() const {

    }
};

Problem

Solution

Discuss

Passing larger sized data in functions by const &data is a good idea since it does not make a copy. Note that when a parameter is passed by const&, the extra cost dereferencing and fewer opportunities for compile optimizing. You should do this typically when the data is large in size

From your next() function

    int next() {
        int curr_next = next_num;
        num_has_next = Iterator::hasNext();

        if (num_has_next) {
            next_num = Iterator::next();
        }

        return curr_next;
    } ```

What is the use of the if (num_has_next) branch? You are returning a copy of next_num that was copied before any modifications, and since curr_next is not a reference of next_num, any changes to next_num will not effect return curr_next. I think what you might want to do is
int next(){
    next_num = (num_has_next) ? Iterator::next() : NULL;
    return next_num;
}

ternary operators
Since @hjpotter92 has mentioned it,  calling next() or peek() on the last element should return NULL.

Have a look at templates in C++ if you want to work with multiple types.


Simple binary search tree for use in programming competitions I made a binary search tree implementation in C++ for my personal use in programming competitions.

#include <iostream>

using namespace std;

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    string value;
};

Node root_node; // Binary search tree

string inline query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != NULL) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
}
void inline insert_bst(int key, string value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != NULL) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    Node new_node;
    new_node.key = key;
    new_node.value = value;
    next_node = &new_node;
    if (key < cur_node->key) {
        cur_node->leftnode = next_node;
    } else {
        cur_node->rightnode = next_node;
    }
}

int main() {
    /* Test code */
    root_node.key = 1;
    insert_bst(2, "Node #3");
    insert_bst(3, "Node #4");
    cout << query_bst(3) << '\n';
}

I'm not generalizing the code or using OOP because I typically will only need one BST for programming competitions. insert_bst should be able to be redesigned so next_node is not required thereby reducing computation time and shortening the code. query_bst returns an awkward string when it fails to find an element. Overall, I believe the code is a bit bulky and requires optimization to be feasible for use in a programming competition.

First of all, your code does not work. In the "insert_bst" function, you create a Node named "new_node" and then assign the rightnode pointer that node's address. However, your "new_node" variable has automatic storage duration, and thus is destroyed at the end of the function. Therefore, after the function call is over, your pointer is pointing to unallocated memory
(or something like that; my knowledge might be inadequate, I rarely deal with pointers). In order to avoid this, you need to use dynamic memory allocation.

Edit: To confirm my claims, I asked a question on StackOverflow.

Then, here is my version of inset_bst() function without next_node variable. However, I did not use it in the code, because I am not sure whether it actually improves the computation time, because it uses more if statemets. And I am too lazy to check :D

void insert_bst(int key, const std::string& value) {
    Node *cur_node = &root_node;
    // Search through bst for key
    while (1) {
        if (key < cur_node->key) {
            if(cur_node->leftnode == nullptr) {
                cur_node->leftnode = new Node(key, value);
                break;
            }
            cur_node = cur_node->leftnode;
        } else {
            if(cur_node->rightnode == nullptr) {
                cur_node->rightnode = new Node(key, value);
                break;
            }
            cur_node = cur_node->rightnode;
        }
    }
}

Here is the modified code with the rest of my criticism/tips:

#include <iostream>

/**
    1. Avoid using "using namespace std". There are plenty of reasons why,
    google it if you doubt my word.
    2. Use nullptr instead of NULL macro
**/

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    std::string value;

    /** 3. It is always wise to use constructors instead of creating empty instances of
        structs / classes and then initializing member variables one by one
    **/
    Node(int tkey, const std::string& tvalue) : leftnode(nullptr), rightnode(nullptr), key(tkey), value(tvalue) {}

    //If you want the ability to construct nodes with undefined keys/values
    //Node() : leftnode(nullptr), rightnode(nullptr) {}
};

// I initialized it here for testing purposes, you did it in main, it doesn't really matter,
// except that previously the value of root_node was an empty string
Node root_node(1, "Node #1"); // Binary search tree

/**
    4. No need to use the "inline" specifier, at least in this case. The compiler usually
    can decide whether to inline functions by itself.
**/

std::string query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != nullptr) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
    /**
        5. If you don't want to return such awkward empty string, you might consider
        implementing some exception handling (i.e throw an std::runtime_error() with an
        appropriate error message on failure)
    **/
}

/**
    6. Pass strings by const ref if you are not going to modify them
**/
void insert_bst(int key, const std::string& value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != nullptr) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    /**
        7. Currently your code allows duplicate keys. As I did not know whether such
        behaviour was intentional, I left it as it is.
    **/
    if (key < cur_node->key) {
        cur_node->leftnode = new Node(key, value);
    }
    else {
        cur_node->rightnode = new Node(key, value);
    }
}

/**
   8. Finally, with this modified code, you'd need to properly handle dynamically allocated
   memory. However, as your code did not provide any removal functions, I did not implement
   memory deallocation.
**/

int main() {
    /* Test code */
    //root_node.key = 1;
    insert_bst(2, "Node #2");
    insert_bst(3, "Node #3");
    std::cout << query_bst(3) << '\n';
}

Finally, here is the same code without all the comments:

#include <iostream>

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    std::string value;
    Node(int tkey, const std::string& tvalue) : leftnode(nullptr), rightnode(nullptr), key(tkey), value(tvalue) {}
};

Node root_node(1, "Node #1"); // Binary search tree

std::string query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != nullptr) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
}

void insert_bst(int key, const std::string& value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != nullptr) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    if (key < cur_node->key) {
        cur_node->leftnode = new Node(key, value);
    }
    else {
        cur_node->rightnode = new Node(key, value);
    }
}

int main() {
    /* Test code */
    insert_bst(2, "Node #2");
    insert_bst(3, "Node #3");
    std::cout << query_bst(3) << '\n';
}


Bitmap-based Sieve of Erastothenes I have written a simple implementation of Sieve of Erasthotenes (in C, MSVC flavour), which I believe is correct (source below). Is there a way to make it faster and more readable?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <intrin.h>

typedef unsigned long long bitmap_entry_t;
#define NUMBERS_TO_CALCULATE (1024*1024*1024)
#define BITMAP_ENTRY_BITS (sizeof(bitmap_entry_t)*8)

inline void bitmap_set(bitmap_entry_t *bitmap, unsigned long long index)
{
    _bittestandset64(&bitmap[index / BITMAP_ENTRY_BITS], index%BITMAP_ENTRY_BITS);
}

inline void bitmap_unset(bitmap_entry_t *bitmap, unsigned long long index)
{
    _bittestandreset64(&bitmap[index / BITMAP_ENTRY_BITS], index%BITMAP_ENTRY_BITS);
}

inline bitmap_entry_t bitmap_get(bitmap_entry_t *bitmap, unsigned long long index)
{
    return _bittest64(&bitmap[index / BITMAP_ENTRY_BITS], index%BITMAP_ENTRY_BITS);
}

int main(void)
{
    bitmap_entry_t *bitmap = malloc((1 + NUMBERS_TO_CALCULATE / BITMAP_ENTRY_BITS) * sizeof(bitmap_entry_t));
    for (int i = 0; i < (1 + NUMBERS_TO_CALCULATE / BITMAP_ENTRY_BITS); i++)
    {
        bitmap[i] = 0xFFFFFFFFFFFFFFFFLL;
    }

    for (int i = 2; i < sqrt(NUMBERS_TO_CALCULATE); i++)
    {
        if (bitmap_get(bitmap, i - 2))
        {
            for (int j = 2 * i; j < NUMBERS_TO_CALCULATE; j += i)
            {
                bitmap_unset(bitmap, j - 2);
            }
        }
    }

    for (int i = 2; i < NUMBERS_TO_CALCULATE; i++)
    {
        if (bitmap_get(bitmap, i - 2))
        {
            printf("%d ", i);
        }
    }

    getchar();
}

I see a few things that might help you improve your code.

Declare local routines static

If you declare bitmap_get and the other routines as static, the compiler will know that they can never be called outside this one file.  With that information, much more agressive optimization can be done and the inline keyword will probably not even be needed.

Eliminate unused routine

The code defines a routine bitmap_set but it is not actually used and can be eliminated from the code.  Smaller code typically runs faster, so there's a small chance that this could improve speed as well.

Use calloc and reverse the sense of the bits

You could eliminate the initialization of all of the bits to 1 by using calloc instead of malloc and reversing the meaning of the bits in the bitmap.  On my Linux box, the times were about the same, but of course the calloc version was shorter.

Skip all even numbers

Your bitmap could be half the current size by simply eliminating the storage of even numbers.  The only even prime is 2, so your program doesn't really need to allocate bits for even numbers.

Optimize the inner loop

If we only test odd numbers, as per the last suggestion, we can also optimize the inner loop.  Once we know that i is an odd number, it's obvious that 2*i must be an even number, so there's no reason to mark it as non-prime since we already know that all even numbers except 2 are non-prime.  Using both suggestions, we can double the speed of both inner and outer loops by writing them like this:

for (int i = 3; i < sqrt(NUMBERS_TO_CALCULATE); i+=2)
{
    if (bitmap_get(bitmap, i - 2))
    {
        for (int j = 3 * i; j < NUMBERS_TO_CALCULATE; j += 2*i)
        {
            bitmap_unset(bitmap, j - 2);
        }
    }
}

Prefer portable constants

If you elect not to use calloc, you could still revise the way the constant is written.  At the moment, the code uses this:

bitmap[i] = 0xFFFFFFFFFFFFFFFFLL;

It would be shorter, less potentially error prone (quick -- how many F's should there be?) and easier to read like this:

bitmap[i] = ~0;

On my machine, using gcc as the compiler, they compile to the same thing.

Consider using pointers

On some compilers, depending on optimizations used, the use of pointers can be faster than using indexing.  You could test this on your machine with your compiler.  For example, the initialization loop could be written like this:

for (bitmap_entry_t *p = bitmap;
        p < &bitmap[(1 + NUMBERS_TO_CALCULATE / BITMAP_ENTRY_BITS)]; ++p)
{
    *p = ~0;
}

Optimize printing

As you may already know, it's the number conversion and printing of the results that takes most of the time for this program.  If that's of interest, you could write your own special purpose output formatter.  By keeping a static string array in memory and using that to increment through the numbers, you may be able to speed the entire program.


Find the number in an array which is closest to an given number Exercise from an Assembly course I'm enrolled in:

  Find closest number.

  Add the following into the data section:

  nums  dd  23h,75h,111h,0abch,443h,1000h,5h,2213h,433a34h,0deadbeafh

  This is an array of numbers.

  Write a program that receives a number x as input, and finds the dword
  inside the array nums, which is the closest to x. (We define the
  distance between two numbers to be the absolute value of the
  difference: |a-b|).

  Example:

  For the input of 100h, the result will be 111h, because 111h is closer
  to 100h than any other number in the nums array. (|100h - 111h| =
  11h).

Full exercise-sheet on GitHub - xorpd

Here's my approach. Please pay attention to the comments which I've added to explain my ideas.

format PE console
entry start

include 'win32a.inc'

section '.data' data readable writeable
    nums  dd  23h, 75h, 111h, 0abch, 443h, 1000h, 5h, 2213h, 433a34h, 0deadbeafh
    nums_end:

section '.text' code readable executable

start:
    xor         esi,        esi                     ; Current array-index.
    mov         ecx,        (nums_end - nums) / 4   ; Array-length
    mov         ebx,        0x100                   ; Input, Value to compare too.
    mov         edx,        0x7fffffff              ; Smallest value found until now. Start with the greatest value possible.
    mov         edi,        edi                     ; Index of the element with the smallest value.
    ; -------------------------------------------------------------------------------------------------------------------
check_next:
    mov         eax,        ebx                     ; Make a copy compare-value.
    mov         ebp,        dword[nums + 4 * esi]   ; Move the value of the current element to ebp.
    cmp         eax,        ebp                     ; If eax is smaller then ebp then we must not subtract ebp from eax.
    jb          eax_is_smaller                      ;   This would result in a negative number. ...
    sub         eax,        ebp
    jmp         subtraction_done
eax_is_smaller:
    sub         ebp,        eax                     ; ... subtract eax from ebp instead.
    mov         eax,        ebp                     ; ... and move the result to eax.
subtraction_done:
    cmp         eax,        edx                     ; Compare the result to the current smallest value.
    jnb         prepare_next
    mov         edx,        eax                     ; If the result is smaller then the current smallest value the result becomes the smallest value.
    mov         edi,        esi                     ; Save the index of the smallest value.
prepare_next:
    inc         esi                                 ; Increment the array-index.
    loop        check_next                          ; Check the next array-element.
    ; -------------------------------------------------------------------------------------------------------------------
    mov         eax,        dword[nums + 4 * edi]   ; Use the index of the nearest element to get the value. Then print it to stdout.
    call        print_eax                           ; Print to stdout. Function provided by the tutor.
    ; Exit the process:
    push        0
    call        [ExitProcess]

include 'training.inc'

I've tried it with different compare-values and it provided the expected value every time. So I guess it's generally correct. Nevertheless I'm not completely satisfied. I have used a lot of register.

How can I reduce the number of register? I have found a solution for the problem with getting negative values when subtracting a larger number from a smaller number. It works but it isn't elegant. Is there a better solution?

mov edi, edi    ; Index of the element with the smallest value.

An error here. You want to zero this register. Use xor

A better strategy will be to simply subtract without looking at which number is the largest and then later take the absolute value of the difference.

    mov     eax, [nums + 4 * esi]
    sub     eax, ebx
    jnl     IsPositive
    neg     eax
IsPositive:
    cmp     eax, edx ; Compare the result to the current smallest value.
    jnb     prepare_next
    mov     edx, eax
    mov     edi, esi
prepare_next:

Less code and less register usage!

A further optimization will come from not using ECX as a loop counter. You can determine if the loop is completed by looking at the ESI array index.

    xor     esi, esi         ;Start at index 0
check_next:
    ...
    inc     esi
    cmp     esi, (nums_end - nums) / 4
    jb      check_next

In stead of branching, you could use one of the conditional forms of mov.
Same code size but faster. Having less labels is also nicer.

    cmp     eax, edx ; Compare the result to the current smallest value.
    cmovb   edx, eax
    cmovb   edi, esi

About coding style.

mov eax, dword[nums + 4 * edi]

Does your assembler requires you to write this redundant mention of the size?
Do you get an error if you write it shorter?

    mov     eax, [nums + 4 * edi]


Database connection approach We have recently started working in ASP.NET and starting a simple CRUD Web application in ASP.Net. Here is the approach we are following to connect to DB.

Connection.cs

public class Connection
{
    public SqlConnection con = new SqlConnection(ConfigurationManager.ConnectionStrings["CWConnectionString"].ConnectionString);
    private readonly log4net.ILog logger = log4net.LogManager.GetLogger("Connection.cs");

    public Connection()
    {
        //
        // TODO: Add constructor logic here
        //
    }

    public bool CheckOpenConnection()
    {
        try
        {
            if (con.State == ConnectionState.Open)
            {
                con.Close();
                return true;
            }
            else
            { return false; }
        }
        catch (Exception Ex)
        {
            logger.Error("Error in CheckOpenConnection : " + Ex.Message);
            return false;
        }
    }

    public void OpenConnection()
    {
        try
        {
            if (CheckOpenConnection() == false)
                con.Open();
        }
        catch (Exception Ex)
        {
            logger.Error("Error in OpenConnection : " + Ex.Message);
        }
    }

    public void CloseConnection()
    {
        try
        {
            if (CheckOpenConnection() == true)
                con.Open();
        }
        catch (Exception Ex)
        {
            logger.Error("Error in CloseConnection : " + Ex.Message);
        }
    }
}

Then we use some methods like this in another cs file

Dal_authentication.cs

public DataTable AuthenticateUser(string UserName, string Password)
{
    try
    {

        DataTable results = new DataTable();
        Connection cn = new Connection();
        cn.OpenConnection();
        string sql_SP = "uspAuthenticateLogin";

        using (SqlCommand cmd = new SqlCommand(sql_SP, cn.con))
        {
            cmd.CommandType = CommandType.StoredProcedure;

            cmd.Parameters.Add(new SqlParameter("@UserName", SqlDbType.NVarChar, 50));
            cmd.Parameters["@UserName"].Value = UserName;

            cmd.Parameters.Add(new SqlParameter("@Password", SqlDbType.NVarChar, 50));
            cmd.Parameters["@Password"].Value = Password;

            SqlDataAdapter da = new SqlDataAdapter(cmd);
            da.Fill(results);
        }
        cn.CloseConnection();

        return results;
    }
    catch (Exception Ex)
    {
        //logger.Error("AuthenticateUser : " + Ex.Message);
        return null;
    }
}

Is there any flaw in this approach? Is it the right way to connect to DB?  Are there any possible improvements?

As @chrfin mentioned, this type of question is best suited for CodeReview.

This is the wrong way to use connections. Keeping a connection open indefinetely is bad because it accumulates locks, transactions remain open,it wastes server resources due to blocking  and forces you to use more connections than you actually need.

ADO.NET (and ADO before it, way back to the late 90s) support connection pooling so that whenever you close a connection, it terminates any existing transactions, frees up all locks and remains dormant until the next time you need a connection with the exact same string. This way, a couple of connections can handle commands from multiple classes.

The difference in speed and scalability can be orders of magnitude because you drastically reduce blocking issues:

The proper way to connect is something like this:

using(var con=new SqlConnection(myConnectionString))
using(var cmd=new SqlCommand(myCommand,con))
{
    cmd.Parameters.Add ...
    ...
    con.Open();

    SqlDataAdapter da = new SqlDataAdapter(cmd);
    da.Fill(results);

}

You don't need to close the connection explicitly because it's closed automatically when execution exits the using block, even if an exception occurs.

A better solution would be to use an ORM like Entity Framework or NHibernate to handle connections and map the results to objects.

You can find numerous tutorials on using Entity Framework with ASP.NET MVC at Microsoft's ASP.NET site


Optimizing and improving a username regex I have created this regular expression to validate usernames which I need in my projects:

^(?=.{3,32}$)(?!.*[._-]{2})(?!.*[0-9]{5,})[a-z](?:[\w]*|[a-z\d\.]*|[a-z\d-]*)[a-z0-9]$

It works just fine. But I'm wondering if there is any improvement and optimization for it, since I'm not exactly a regex-guy.

The regex and tests are available here.

Rules are:

usernames should start with [a-z]
usernames should end with [a-z0-9]
usernames can have a length between 3 and 32
usernames can contain any of [a-z0-9\._-]
Numbers should not be in the vicinity of each other more than 4 times. I mean p1234 is a match and p12345 is not.
each username can contains only one of [\._-]. I mean a username can contain . or - or _
each ., -, and _ should be followed by an alpha-numeric. I mean a . can not be followed by another .. They should not be in the vicinity of each other.

Tests:

j1vad-amiry            match
j1vad-ami-ry           match
ja23d_am8ry            match
ja_23d_am8ry           match
jav5d2.am3y            match
jav.ad.amiry           match
jav.ad.ami.ry.2        match
ja3fd4                 match
page2491               match
page24915              not match
jav-ad_amiry           not match
javad_am-iry           not match
jav.ami-ry             not match
jav.ami_ry             not match
jav.ami__ry            not match
2jav                   not match
2jav_ad                not match
2jav_ad3               not match

I would very strongly recommend against using a regular expression for this. There is no clear mapping between the list of requirements you posted and the code.

Imagine another developer looking at this. Are they able to deduce the list of requirements? Given the list of requirements, are they able to verify that the regular expression is correct? How long would it take to convince them that it's correct?

In fact, it's not correct. The character class \d is not the same as [0-9] (unless you specify ECMAScript-compliant behaviour), and your regexp matches the username j1vad-a٠miry (that's an ARABIC-INDIC DIGIT ZERO). (It doesn't match on the link you posted, but that's a Ruby, not .NET, regexp tester.)

Now suppose one of your requirements changes -- this code is going to be tricky to maintain.

Instead, I would recommend writing a series of tests, each corresponding to one of your requirements. Here is the code I came up with. It still uses regular expressions where appropriate, but very simple ones.

public static bool IsValidUsername(string username)
{
    if (username == null)
    {
        return false;
    }

    var length = username.Length;
    if (length < 3 || length > 32)
    {
        return false;
    }

    if (!IsLowerAlpha(username[0]))
    {
        return false;
    }

    if (!IsLowerAlphanumeric(username[length - 1]))
    {
        return false;
    }

    if (!Regex.IsMatch(username, "^[a-z0-9._-]*$"))
    {
        return false;
    }

    if (Regex.IsMatch(username, "[0-9]{5,}"))
    {
        return false;
    }

    // Each username can contain only one of '.', '_', '-'.
    var punctuation = new [] { '.', '_', '-' };
    if (punctuation.Count(c => username.Contains(c)) > 1)
    {
        return false;
    }

    // Each '.', '_', and '-' should be followed by an alpha-numeric.
    for (var i = 0; i < length - 1; i++)
    {
        if (punctuation.Contains(username[i]) && !IsLowerAlphanumeric(username[i + 1]))
        {
            return false;
        }
    }

    return true;
}

private static bool IsLowerAlpha(char c)
{
    return c >= 'a' && c <= 'z';
}

private static bool IsLowerAlphanumeric(char c)
{
    return IsLowerAlpha(c) || (c >= '0' && c <= '9');
}

Now, IsValidUsername is getting a bit long. We could split out each check into a separate static method, for instance,

private static bool IsNotNull(string username)
{
    return username != null;
}

private static bool IsInLengthRange(string username)
{
    var length = username.Length;
    return length >= 3 && length <= 32;
}

And then just check our rules like this:

private static readonly Predicate<string>[] Rules = new Predicate<string>[]
{
    IsNotNull,
    IsInLengthRange,
    StartsWithLowerAlpha,
    ...
};

public static bool IsValidUsername(string username)
{
    return Rules.All(rule => rule(username));
}


HackerEarth Crazy kangaroo challenge I want to find the lowest hop count from source to destination.
The challenge, in summary:

  The first line contains the number of test cases T, 1 ≤ T ≤ 100000.
  The next T lines each contains three integers A, B, and M.  1 ≤ A ≤ B ≤ 1012.  1 ≤ M ≤ 1012.

  For each test case, print the number of multiples of M that are in the range [A, B] (inclusive).

My output is correct but the execution time of my program is like 1.0015 seconds when given 100000 entries. But I need to do the program within 1 second time frame. I have tried a lot to reduce the execution time but couldn't. Can anybody help me to achieve an execution time within 1 sec.

#include<stdio.h>
int main()
{
    unsigned int n, i, j, k, h,count=0,l=0;
    scanf("%u", &n);
    for (i=0;i<n;i++)
    {
        scanf("%u %u %u", &j, &k, &h);
        l=j;
        count = 0;
        while(l<=k)
        {
          if(l%h==0)
          {
            count=count+1;
          }
          l++;
        }
        printf("%u\n", count);
    }
    return 0;
}

sample input-> 1 10 2

sample output-> 5

Data declarations

Your data types are not large enough.  By the C standard, an int is only guaranteed to hold up to 32767, which is smaller than 100000.  Similarly, an int could be insufficient to hold the values of A, B, and M.  You'll need a long long or int64_t.

A big block of declarations like this is not ideal:

unsigned int n, i, j, k, h,count=0,l=0;

You should declare variables as close to the point of use and in as tight a scope as possible.
Single-character names are cryptic.

Algorithm

You don't have to simulate a kangaroo, counting hops, to answer these questions.  The answer will be roughly

$$\frac{B - A}{M}$$

… except that you have to take care of fencepost (off-by-one) errors at the edges.  I'll leave it to you to figure out the details.


XAML Markup Improvements I have a Windows Store and Windows Phone app, and in this app I have many pages like this:

<Grid Background="Transparent">
    <ScrollViewer Style="{StaticResource DataPage}">
        <StackPanel>
            <TextBlock>
                Some text here:
                <LineBreak/>
            </TextBlock>
            <Viewbox MaxHeight="112">
                <Border BorderBrush="Black" BorderThickness="1">
                    <Image Source="MyImage.png"/>
                </Border>
            </Viewbox>
        </StackPanel>
    </ScrollViewer>
</Grid>

These pages are loaded into a Frame to be displayed when needed.  Now, however, I have many pages, and I was wondering if there is a better way to do this.  I have been doing it like this so far because easy to make the page content dynamically reload to fit the screen/app size the best with VisualStates and because it is easy to use XAML markup to style my text, image borders (not always there), and layout perfectly, and any solution provided must support everything this does and work in both Windows Store and Phone apps.

Just for reference, this is the C# that loads this page into the frame:

DataFrame.Navigate(Data.Pages[Items.SelectedIndex]);

DataFrame is the Frame, obviously; Data.Pages is an ObservableCollection<Type> in my ViewModel (Data is an instance of the VM class); Items is the ListBox that contains the selectable options.

This image shows the context of what I am doing, with the content in one of these pages outlined in black:

There isn't much to say about the markup here - it looks like much was stripped from the markup. One thing though:

            <Border BorderBrush="Black" BorderThickness="1">
                <Image Source="MyImage.png"/>
            </Border>

I wouldn't hard-code paths into the XAML like this; instead, bind to an ImageSource property on your ViewModel. If/when that image needs to change, you'd certainly rather modify C# code than dig up the path in the XAML markup.


Text cleaning script, producing lowercase words with minimal punctuation I created following script to clean text that I scraped. The clean text would ideally be lowercase words, without numbers and at maybe only commas and a dot at the end of a sentence. It should only have white-space between words and remove all "\n" elements from the text.

Particularly, I'm interested in feedback to the following code:

def cleaning(text):

    import string
    exclude = set(string.punctuation)

    import re
    # remove new line and digits with regular expression
    text = re.sub(r'\n', '', text)
    text = re.sub(r'\d', '', text)
    # remove patterns matching url format
    url_pattern = r'((http|ftp|https):\/\/)?[\w\-_]+(\.[\w\-_]+)+([\w\-\.,@?^=%&amp;:/~\+#]*[\w\-\@?^=%&amp;/~\+#])?'
    text = re.sub(url_pattern, ' ', text)
    # remove non-ascii characters
    text = ''.join(character for character in text if ord(character) < 128)
    # remove punctuations
    text = ''.join(character for character in text if character not in exclude)
    # standardize white space
    text = re.sub(r'\s+', ' ', text)
    # drop capitalization
    text = text.lower()
    #remove white space
    text = text.strip()

    return text

The script is cleaned via

cleaner = lambda x: cleaning(x)
df['text_clean'] = df['text'].apply(cleaner)
# Replace and remove empty rows
df['text_clean'] = df['text_clean'].replace('', np.nan)
df = df.dropna(how='any')

So far, the script does the job, which is great. However, how could the script above be improved, or be written cleaner?

Unclear seems the difference between

text = re.sub(r'\n', '', text)
text = re.sub('\n', '', text)

and whether

text = re.sub(r'\s+', ' ', text)
...
text = text.strip()

makes sense.

Actually, your approach consists to remove or to replace with a space all that isn't a word (urls and characters that are not an ascii letter). Then you finish the job removing duplicate spaces, spaces at the beginning or the end of the string, and converting all in lower-case.

The idea makes sense.

But concretely, what is the result of this script?
It returns all words in lower-case separated by a space.

Described like that, you easily understand that you can extract the words and join them with a space. To do that, a simple re.findall(r'[a-z]+', text) suffices, but you have to remove the urls first if you don't want to catch letter sequences contained in them.

The url pattern

If you read your url pattern, you can see that the only part that isn't optional is in fact [\w-]+(?:\.[\w-]+)+ (written [\w\-_]+(\.[\w\-_]+)+ in your script: _ is already inside \w, you can put - at the end of a character without to escape it, the capture group is useless).All that comes after this part of the pattern doesn't require a precise description and can be replaced with a \S* (zero or more non-white-spaces). Even if it catches a closing parenthesis or a comma, it isn't important for what you want to do (we will see how to handle commas or dots later).

One of the weaknesses of the url pattern is that it starts with an alternation in an optional group. This means that at each failing position of the string, the regex engine has to test the three alternatives (http|ftp|https) and without the whole group for nothing.
It's possible to improve that a little if you start the pattern with a word boundary and if you replace the last alternative (https) with an optional s in the first.

The url pattern can be rewritten like this:

\b(?:(?:https|ftp)://)?\w[\w-]*(?:\.[\w-]+)+\S*

and the whole function:

import re

def cleaning2(text):
    text = re.sub(r'\b(?:(?:https?|ftp)://)?\w[\w-]*(?:\.[\w-]+)+\S*', ' ', text.lower())
    words = re.findall(r'[a-z]+', text)
    return ' '.join(words)

Note that the URL syntax can be particularly complex, and that it isn't always possible to extract an URL from a non-formatted string.

If you want to keep commas and dots:
Few changes, you only have to be sure that \S* in the url pattern doesn't eat a comma or a dot at the end of the url with a negative lookbehind (?<!...), and to add them in the character class in the re.findall pattern:

import re

def cleaning2(text):
    text = re.sub(r'\b(?:(?:https?|ftp)://)?\w[\w-]*(?:\.[\w-]+)+\S*(?<![.,])', ' ', text.lower())
    words = re.findall(r'[a-z.,]+', text)
    return ' '.join(words)


Query column names and then using them in statements I currently have a table with over 250 columns, in which ~10-15 columns have column names that have a specific prefix, namely EQP_.

Assume that you do not want to type the names of these columns, but still want only a result set containing those columns.

Some possible solutions I thought of:

Using a common_table_expression
Using a table variable with a function
Using an INNER JOIN with INFORMATION_SCHEMA

All of these seem like overkill to me, so I ended using a temp table and dynamic SQL to get something working. I am not a fan of dynamic SQL, so I was hoping to get some feedback on how to do this better.

Query

SELECT TOP 15 COLUMN_NAME 'name', 0 'selected'
INTO #columns
FROM Production.INFORMATION_SCHEMA.COLUMNS
WHERE TABLE_NAME = N'it_master'
AND COLUMN_NAME LIKE 'EQP_%'

DECLARE @sql NVARCHAR(MAX)
SET @sql = 'SELECT TOP 10 ' ;

WHILE EXISTS(SELECT 1 FROM #columns WHERE [selected] = 0 )
BEGIN

    DECLARE @column NVARCHAR(100)

    SELECT TOP 1 @column  = [name] FROM #columns WHERE [selected]= 0

    SET @sql = @sql + @column + ', '

    UPDATE c
    SET [selected] = 1
    FROM #columns c
    WHERE [name] = @column

END

SET @sql = LEFT(@sql, LEN(@sql) - 1) + ' FROM it_master '

EXECUTE sp_executesql @sql

IF OBJECT_ID('tempdb..#columns') IS NOT NULL
    DROP TABLE #columns

There is no need for loop/temporary table at all. You could use GROUP_CONCAT equivalent in SQL Server(STUFF + XML) trick:

DECLARE @col NVARCHAR(MAX) = STUFF((SELECT  ',' + QUOTENAME(COLUMN_NAME)
                                    FROM INFORMATION_SCHEMA.COLUMNS
                                    WHERE TABLE_NAME = N'it_master'
                                      AND TABLE_SCHEMA = 'dbo'
                                      AND COLUMN_NAME LIKE 'EQP_%'
                                    ORDER BY COLUMN_NAME
                                    FOR XML PATH(''))
                                   ,1,1,'');

DECLARE @query NVARCHAR(MAX) = N'SELECT <placeholder> FROM it_master;';
SET @query = REPLACE(@query,'<placeholder>', @col);

EXEC [dbo].[sp_executesql] @query;

LiveDemo

Notes:

It is a good practice to filter from INFORMATION_SCHEMA.COLUMNS with table name and schema_name (tables with the same name could exist in many schemas)
Concatenating main query with + is not readable. You could use REPLACE or printf equivalent

SQL Server 2012+:

DECLARE @query NVARCHAR(MAX) = FORMATMESSAGE('SELECT %s FROM it_master;', @col);

LiveDemo2

Another way is to use SQL Server Management Studio:

Object Explorer -> Database_Name -> Tables -> Table_Name -> Columns -> (Click Filter and type EQP optional)

Highlight all needed columns with SHIFT and drag and drop to query pane.


Converting input containing special character to float This is the beginning of my program that calculates simple interest. Interest rate will have the following format : 0.97 , 0.67 , 0.17 etc. They won't be bigger than 1. So if the user enter 9 for the interest, program will convert it to 0.09 (by dividing it by 100) . Also user can enter input using '/'. So program will convert input like 97/100 to 0.97.

I wrote the code below. It works but it seems to me that there might be a easier and more elegant solution to this. Maybe using more build-in functions etc. If you help me with that I would be very appreciated.

def toNum(interest):

    if '/' not in interest:
        if float(interest) > 1:
            return float(interest)/100

        else:
            return float(interest)

    else:
        l= []
        n = 0
        count = 1

        list_interest=[]
        for e in interest:
            list_interest.append(e)

        for e in list_interest:

            if count == 1 or count == 3:
                l.append(e)
                count = count +1
                continue

            if e == '/':
                n = n + 1
                count = count +1
            else:
                l[n] = l[n] + e

        return int(l[0]) / int(l[1])

interest = input("Interest rate: ")
interest = toNum(interest)
print(interest)

For reading a fraction such as "97/100", you can use the fractions library.

For example:

from fractions import Fraction

f = Fraction("97/100")

print(float(f)) # prints 0.97

And because the constructor also takes a float, we can remove the check for /. Therefore, the final code is:

from fractions import Fraction

def toNum(interest):
    f = Fraction(interest)
    f = float(f)

    if f > 1:
        f /= 100

    return f

print(toNum("97/100")) # prints 0.97
print(toNum(0.97)) # prints 0.97
print(toNum(9)) # prints 0.09


Swapping Elements in a list Challenge:

  Swap positions in a list

Specifications:

  Your program should accept as its first argument a path to a filename.
  The file contains several test cases, one on each line.
  Each test case is a list of numbers, supplemented with positions to be swapped.
  List and positions are separated by a colon.
  Positions start with 0.
  There may be more than one position swaps, separated by a comma.
  Positions swaps are processed left to right.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class SwapElements {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            String[] temp = input.nextLine().split(":");
            printSwapped(swapList(temp[0], temp[1]));
        }
    }

    public static void printSwapped(List<String> list) {
        StringBuilder result = new StringBuilder();

        for (String s : list) {
            result.append(' ').append(s);
        }

        System.out.println(result.substring(1));
    }

    public static List<String> swapList(String input, String swapKey) {
        List<String> result = modifyToList(input);

        for (String s : swapKey.split(",")) {
            String[] keys = s.split("-");
            int index1 = Integer.parseInt(keys[0].substring(1));
            int index2 = Integer.parseInt(keys[1]);

            String target1 = result.get(index2);
            String target2 = result.get(index1);

            result.set(index1, target1);
            result.set(index2, target2);
        }

        return result;
    }

    public static List<String> modifyToList(String list) {
        List<String> result = new ArrayList<>(list.length());

        for (String s : list.split("\\s+")) {
            result.add(s);
        }

        return result;
    }
}

Sample Input:

  1 2 3 4 5 6 7 8 9 : 0-8
  1 2 3 4 5 6 7 8 9 10 : 0-1, 1-3

Sample Output:

  9 2 3 4 5 6 7 8 1
  2 4 3 1 5 6 7 8 9 10

It's actually been a while since I did one of these and I get the feeling it shows. The solution itself, of course, works, but I get the sense that it's memory intensive and/or slow. I'd mostly like to focus on optimizing speed, but any and all general feedback is welcome.

What do you think?

Switching from a List<Integer> to an int[] speeds things up quite a bit, for the  input examples you've provided. Note: I've slightly simplified your code to work off a fixed array of strings, merely because it made my testing easier.

public class SwapElements {

  private static final String[] lines = { "1 2 3 4 5 6 7 8 9 : 0-8",
      "1 2 3 4 5 6 7 8 9 10 : 0-1, 1-3" };

  public static void main(String[] args) throws Exception {
    for (String line : lines) {
      String[] temp = line.split(":");
      int[] numbers = toPrimitiveArray(temp[0]);
      printSwapped(swapList(numbers, temp[1]));
    }
  }

  private static int[] toPrimitiveArray(String input) {
    String[] numbers = input.split(" ");

    int[] result = new int[numbers.length];
    for (int i = 0; i < numbers.length; i++) {
      result[i] = Integer.parseInt(numbers[i]);
    }
    return result;
  }

  private static void printSwapped(int[] list) {
    StringBuilder result = new StringBuilder();

    for (int i : list) {
      result.append(' ').append(i);
    }

    System.out.println(result.substring(1));
  }

  private static int[] swapList(int[] input, String swapKey) {
    for (String s : swapKey.split(",")) {
      String[] keys = s.split("-");
      int index1 = Integer.parseInt(keys[0].substring(1));
      int index2 = Integer.parseInt(keys[1]);

      int target1 = input[index2];
      int target2 = input[index1];

      input[index1] = target1;
      input[index2] = target2;
    }

    return input;
  }
}

Some basic benchmarking showed me that this improved performance from 4,125ns to 2,536ns (almost 40% reduction), for processing both input strings.

Other comments:

I've  changed most of your public methods to private, since they don't appear to be used outside of the class.
Your original code doesn't correctly close the Scanner you use. These days, you can avoid that entire problem using NIO classes:

List<String> fileLines = Files.readAllLines(Paths.get(args[0]));

You may wish to refactor your code to introduce a int[] swapElements(String input) method, so you can unit test more easily.


Maximum Subarray Problem - Iterative O(n) algorithm I implemented an iterative \$O(n)\$ algorithm for solving the maximum sub-array problem. I would like a general review for it.

Here the max_subarray is the main function and the ones which are static are auxiliary functions for it.

#include<stdio.h>

int max_subarray(int array[], int *low, int *high);

static void initialize(int *sum, int *low, int *high);
static void update_var(int increase, int *sum, int *low, int *high, int i);

int main()
{
    //The maximum subarray-sum is 43 for the following
    int array[16] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int low = 0;
    int high = 15;

    printf("%d", max_subarray(array, &low, &high));
    printf("\n%d %d", low, high);

    return 0;
}

int max_subarray(int array[], int *low, int *high)
{
    int max_sum, max_low, max_high;
    int bet_sum, bet_low, bet_high;
    int inc_sum, inc_low, inc_high;

    initialize(&max_sum, &max_low, &max_high);
    initialize(&bet_sum, &bet_low, &bet_high);
    initialize(&inc_sum, &inc_low, &inc_high);

    for (int i = *low; i <= *high; i++)
    {
        if (max_sum + bet_sum + array[i] > max_sum) {
            update_var(bet_sum + array[i], &max_sum, &max_low, &max_high, i);
            initialize(&bet_sum, &bet_low, &bet_high);
            initialize(&inc_sum, &inc_low, &inc_high);

        } else {
            update_var(array[i], &bet_sum, &bet_low, &bet_high, i);
            if (inc_sum + array[i] > inc_sum) {
                update_var(array[i], &inc_sum, &inc_low, &inc_high, i);
                if (inc_sum > max_sum) {
                    max_sum = inc_sum;
                    max_low = inc_low;
                    max_high = inc_high;
                    initialize(&bet_sum, &bet_low, &bet_high);
                    initialize(&inc_sum, &inc_low, &inc_high);
                }
            }
        }
    }
    *low = max_low;
    *high = max_high;
    return max_sum;
}

static void update_var(int increase, int *sum, int *low, int *high, int i)
{
    *sum += increase;
    *high = i;
    if (*low == -1) {
        *low = i;
    }
}

static void initialize(int *sum, int *low, int *high)
{
    *sum = 0;
    *low = -1;
    *high = -1;
}

Subarray representation

Name of low and high: I prefer lower and upper because they contain the same number of characters, so that code lines up nicely. ☺
Inclusive-inclusive intervals: Your low and high variables form an inclusive-inclusive interval.  Usually, you would be better off with an inclusive-exclusive interval, especially in a language with zero-based arrays.  Consider examples

std::vector::end in C++
String.substring(beginIndex, endIndex) in Java
range(start, stop) in Python

The generic benefit of having high being one greater than the last element is that high - low is the number of elements.  This is nicer — you don't have to hard-code 16 or 15 anywhere:

int array[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
int lower = 0, upper = sizeof(array) / sizeof(array[0]);

A specific benefit for this problem is that any interval with lower == upper represents an empty interval.  You don't have to use -1 for that.
Type of low and high: Array indices should be size_t rather than int.  Especially since your array consists of ints, there could be confusion as to whether int *lower should be a pointer to the first data element (i.e., &array[0]) or a pointer to the index of the first element.  Not having to support -1 lets you use size_t instead, which clarifies your intentions.
Clusters of variables: Variables blah_sum, blah_low, and blah_high are always initialized and updated together.  There should be a struct representing subarrays, with operations "init" and "extend".

typedef struct {
    int sum;
    size_t lower;
    size_t upper;
} subarray;

static void init_subarray(subarray *sa, size_t i) {
    sa->sum = 0;
    sa->lower = sa->upper = i;
}

static void extend_subarray(subarray *sa, size_t i, int increase) {
    sa->sum += increase;
    sa->upper = i + 1;
}

Nitpicks

Const-correctness: max_subarray() should take a const int array[].
Brace style: Pick a brace style and stick with it.

Algorithm

Your code is wrong.  For an input array { -1, 5 }, it prints 4 instead of 5 as the maximum sum.

As @cat_baxter points out, Kadane's algorithm is simpler.

/**
 * Finds the earliest consecutive block of array elements with the maximum sum.
 *
 * Parameters:
 * lower  IN: a pointer to an integer that is the array index of the first
 *            element to consider (normally 0).
 *       OUT: a pointer to an integer that is the array index of the first
 *            element of the maximum subarray.
 *
 * upper  IN: a pointer to an integer that is one greater than the array index
 *            of the last element to consider (normally sizeof(array) /
 *            sizeof(int)).
 *       OUT: a pointer to an integer that is one greater than the array index
 *            of the last element of the maximum subarray.
 *
 * Returns: the sum of the maximum subarray
 */
int max_subarray(const int array[], size_t *lower, size_t *upper) {
    subarray max, tmp;
    init_subarray(&max, *lower);
    init_subarray(&tmp, *lower);

    for (int i = *lower; i < *upper; i++) {
        if (tmp.sum < 0) {
            init_subarray(&tmp, i);
        }
        extend_subarray(&tmp, i, array[i]);

        if (tmp.sum > max.sum) {
            max = tmp;
        }
    }
    *lower = max.lower;
    *upper = max.upper;
    return max.sum;
}

int main() {
    //The maximum subarray-sum is 43 for the following
    int array[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
    size_t lower = 0, upper = sizeof(array) / sizeof(array[0]);

    printf("%d\n", max_subarray(array, &lower, &upper));
    printf("%zu %zu\n", lower, upper);

    return 0;
}


C++ Implementation of a Python-like memoization decorator Coming from a Python background, one thing I really miss in C++ is a memoization decorator (like functools.lru_cache. As I sometimes compete on Codeforces, I found myself implementing a similar thing in C++17 in case I ever need a quick and easy way to memoize function calls. I was wondering whether I could get some feedback on my implementation, and whether something like this could be effective and practical to use in production code.
Thanks!
#include <bits/stdc++.h>

// Using a map
template <typename RetType, typename... ArgTypes>
auto memoize(std::function<RetType(ArgTypes...)> func) -> decltype(func) {
    return [
        memo = std::map<std::tuple<ArgTypes...>, RetType>(),
        func = std::move(func)
    ](ArgTypes... args) mutable -> RetType {
        auto key = make_tuple(args...);
        if (auto it = memo.find(key); it != memo.end()) {
            return it->second;
        }
        auto [it, emplaced] = memo.emplace(key, func(args...));
        return it->second;
    };
}

// Using an unordered_map

// From boost
template<typename T>
inline void hash_combine(std::size_t& seed, const T& val) {
    std::hash<T> hasher;
    seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <typename RetType, typename... ArgTypes>
auto memoizeHashed(std::function<RetType(ArgTypes...)> func) -> decltype(func) {
    using KeyType = std::tuple<ArgTypes...>;
    struct KeyHashFnc {
        size_t operator() (const KeyType& key) const {
            size_t result = 0;
            std::apply([&result](auto&&... args) {
                (
                    hash_combine(result, std::forward<decltype(args)>(args)),
                    ...
                );
            }, key);
            return result;
        }
    };
    return [
        memo = std::unordered_map<KeyType, RetType, KeyHashFnc>(),
        func = std::move(func)
    ](ArgTypes... args) mutable -> RetType {
        auto key = std::make_tuple(args...);
        if (auto it = memo.find(key); it != memo.end()) {
            return it->second;
        }
        auto [it, emplaced] = memo.emplace(key, func(args...));
        return it->second;
    };
}

// Intended usage (solves the problem: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/)
using namespace std;
int INF = 1e9+5;
class Solution {
public:
    int minDifficulty(const vector<int>& arr, int d) {
        int N = arr.size();

        using DpFuncType = function<int(int,int)>;
        DpFuncType dp = [&dp, &arr, N](int i, int k) {
            int n = N-i;

            if (k <= 0) {
                return -1;
            }
            else if (k > n) {
                return -1;
            }
            else if (k == n) {
                return accumulate(arr.begin()+i, arr.end(), 0);
            }
            else { // k < n
                if (k == 1) {
                    return *max_element(arr.begin()+i, arr.end());
                }
                else {
                    int result = INF;
                    int maxVal = arr[i];
                    for (int j = i+1; j < N; ++j) {
                        int curr = dp(j,k-1);
                        if (curr != -1) {
                            result = min(result, maxVal + curr);
                        }
                        maxVal = max(maxVal, arr[j]);
                    }

                    if (result == INF) {
                        return -1;
                    }
                    else {
                        return result;
                    }
                }
            }
        };
        dp = memoizeHashed(dp); // memoize(...) can also be used here

        return dp(0,d);
    }
};
```

Only #include public headers from the STL
You should not #include <bits/stdc++.h>. It is a non-standard header that is not guaranteed to exist or work as you expect it to. If you do this regularly, please unlearn this, and instead #include the proper header files. You only need two for your memoizer:
#include <map>
#include <functional>

No need for trailing return types
I see you specify trailing return types for several of the functions and lambdas you define, but I do not think they are not necessary here. The compiler can automatically deduce them, and while returning a lambda with an auto return type is not the same as when the return type is explicitly set to a std::function as mentioned by HTNW, the caller can always do this conversion themselves if necessary, and indeed that is what happens when you write dp = memoize(...) inside minDifficulty().
Consider rewriting it as a class
Instead of writing memoize() as a function that returns a mutable lambda function, I would just go for the less exciting way of writing a class. The main reason is that more people will be familiar with it, and if you ever want to add functionality to the memoizer, a class makes that much easier. Here is how it could look:
template <typename RetType, typename... ArgTypes>
class memoize {
    std::function<RetType(ArgTypes...)> func;
    std::map<std::tuple<ArgTypes...>, RetType> memo;
public:
    memoize(std::function<RetType(ArgTypes...)> func): func(func) {}
    auto operator()(ArgTypes... args) {
        auto key = std::make_tuple(args...);
        if (auto it = memo.find(key); it != memo.end()) {
            return it->second;
        }
        auto [it, emplaced] = memo.emplace(key, func(args...));
        return it->second;
    };
};

This is actually a complete drop-in replacement for the lambda, even this line will still work:
dp = memoize(dp);

Use in production code
Your memoizer could be used in production code, sure! However, apart from coding challenges I've found the number of cases where I would ever need this to be vanishingly small. Either things need to be remembered much longer than the lifetime of a program, in which case a proper database is used, or all the values you could probably want are precomputed once and included with the binary, or the algorithm I am implementing would be just as easy to implement by reading/writing to a container directly instead of using a memoizer function.
A std::map or std::unordered_map is also not always the most efficient way to store things, often a std::vector is much more efficient if the function just gets a single integer argument. And your memoizer also doesn't handle the case where some parameters to the function are not part of the key to be memoized, although you could work around that by using std::bind() or some other form of currying.
In short, there's nothing wrong with it as far as I can see, but I think there won't be very many occasions where you would need it.


Is this FizzBuzz Swift-y? for (var i = 1; i <= 100; ++i) {
    var fizzBuzz = ""

    if i % 3 == 0 {
        fizzBuzz += "Fizz"
    }

    if i % 5 == 0 {
        fizzBuzz += "Buzz"
    }

    if fizzBuzz == "" {
        fizzBuzz += "\(i)"
    }

    println(fizzBuzz)
}

I don't really like comparing strings with ==, but apparently, that's how you do it in Swift (and there's not another option).

The parenthesis in if statements are optional in Swift.  Should that be a thing, or should we stick with them?  The curly-braces were optional in Objective-C (and lots of programming languages) but they're not in Swift.  Despite their former optionality, I never thought it was a good idea to not use them--is it a good idea to not use parenthesis here?

Not explicitly declaring the type of variable is now a thing in Swift (although the variable still has an explicit type, it's just implicitly determined).  Is it okay to let the type be implicitly determined, or should we stick with explicitly declaring the type?

Is this FizzBuzz Swift-y?

Kinda, but it could be a lot better.  Here's what I would do to fix it:

Extrapolate this code into a method, then call the method from the for loop.

func fizzbuzz(i: Int) -> String
{
   // ...
}

There is a handy Swift feature called "Tuples". Tuples are groupings of values.   We can use them to represent our results from the modulo operation.

let result = (i % 3, i % 5)

Now that we are using a Tuple to represent the result, we can easily use a switch to perform the necessary actions.

switch result
{
    case (0, 0):
        return "FizzBuzz"
    case (0, _):
        return "Fizz"
    case (_, 0):
        return "Buzz"
    default:
        return "\(i)"
}

You might be wondering what that underscore is.  That _ is used to indicate a discarded value that we don't really care about, the value in the tuple that doesn't really matter to us in the evaluation.
Your for loop isn't very "Swift-y".  Here's how I would write is so that it calls the function 100 times.

for number in 1...100
{
    println(fizzbuzz(number))
}

Answers to your questions

  The parenthesis in if statements are optional in Swift. Should that be
  a thing, or should we stick with them?

This is a very style-oriented question.  Style differs from person to person, and is very organic.  Since no "style rules" have been put in place, do whatever you are most comfortable with.

  The curly-braces were optional in Objective-C (and lots of programming
  languages) but they're not in Swift.

This was implemented in order to prevent simplified if conditional statements and the class of bugs that associated with them.  For example:

if (someCondition)
    doThisForSomeCondition()
    doThisAsWell()
if (someOtherCondition)
// ...

Swift's forced usage of braces eliminated the execution of doThisAsWell() outside of the someCondition conditional statement.

  Is it okay to let the type be implicitly determined, or should we
  stick with explicitly declaring the type?

Whether or not you include the explicit type is a matter of taste. In some contexts it might make your code more readable.  However, this is usually not the case; and since the compiler will almost never assign the wrong type to your variable, I usually leave the type to be implicitly determined.  Whatever way you decide will not affect speed/efficiency of the code, so that is not a factor.


Parsing ARP cache in C How can I make this better?

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>

#define ARP_CACHE       "/proc/net/arp"
#define ARP_BUFFER_LEN  1024
#define ARP_DELIM       " "

int readLine(int Fd, char *Buffer)
{
    if (Fd < 0)
    {
        return -1;
    }

    char ch;
    size_t Read = 0;

    while (read(Fd, (Buffer + Read), 1))
    {
        ch = Buffer[Read];
        if (ch == '\n')
        {
            break;
        }
        Read++;
    }

    if (Read)
    {
        Buffer[Read] = 0;
        return 0;
    }

    return -1;

}

char * getField(char * Line_Arg, int Field)
{
    char * Line = malloc(strlen(Line_Arg)), *ptr;
    memcpy(Line, Line_Arg, strlen(Line_Arg));
    ptr = Line;

    char * s;
    s = strtok(Line, ARP_DELIM);
    while (Field && s)
    {
        s = strtok(NULL, ARP_DELIM);
        Field--;
    };

    char * ret;
    if (s)
    {
        ret = (char*)malloc(strlen(s) + 1);
        memset(ret, 0, strlen(s) + 1);
        memcpy(ret, s, strlen(s));
    }
    free(ptr);

    return s ? ret : NULL;
}

int main()
{
    int Fd = open(ARP_CACHE, O_RDONLY);

    if (Fd < 0)
    {
        fprintf(stdout, "Arp Cache: Failed to open file \"%s\"\n", ARP_CACHE);
        return 1;
    }

    char Buffer[ARP_BUFFER_LEN];

    /* Ignore first line */
    int Ret = readLine(Fd, &Buffer[0]);

    Ret = readLine(Fd, &Buffer[0]);
    int count = 0;

    while (Ret == 0)
    {
        char * Line;
        Line = &Buffer[0];

        /* Get Ip, Mac, Interface */
        char * Ip       = getField(Line, 0);
        char * Mac      = getField(Line, 3);
        char * IfaceStr = getField(Line, 5);

        fprintf(stdout, "%03d: Mac Address of [%s] on [%s] is \"%s\"\n",
                ++count, Ip, IfaceStr, Mac);

        free(Ip);
        free(Mac);
        free(IfaceStr);

        Ret = readLine(Fd, &Buffer[0]);
    }
    close(Fd);
    return Ret;
}

Concept

I don't believe that there is a cross-platform way to read the ARP cache.  From the use of /proc filesystem, I deduce that you are targeting Linux.  In Linux, you could read /proc/net/arp as you have done, or run the command ip neigh, which does something similar to your program.  (On OS X, you could run arp -a -n instead.)

A comment worth a thousand words

You should include a comment like this in your program:

/**
 * /proc/net/arp looks like this:
 *
 * IP address       HW type     Flags       HW address            Mask     Device
 * 192.168.12.31    0x1         0x2         00:09:6b:00:02:03     *        eth0
 * 192.168.12.70    0x1         0x2         00:01:02:38:4c:85     *        eth0
 */

That picture tells me everything I need to know about what you are trying to accomplish — you need hardly explain further.  Conversely, not having that picture makes me work a lot harder to reverse-engineer your code.

Minutiae

&Buffer[0] is usually written as Buffer.
You repeat the readLine() call — once before entering the loop, once at the end of the loop.  This is a good opportunity to make use of C's support for side-effects.

while (0 == (Ret = readLine(Fd, Buffer))) {
    …
}

Since ARP_CACHE is a compile-time constant string, you can just write

fprintf(stdout, "Arp Cache: Failed to open file \"" ARP_CACHE "\"\n");

instead of doing a %s substitution at runtime.
Reading one byte at a time is wasteful.
Print errors to standard error; don't contaminate standard output.
I suggest naming your variables to be consistent with the /proc/net/arp header fields.  For example, device instead of IfaceStr.  Also, be consistent with capitalization: count starts with lowercase, which is more common.

Big-picture issues

The function int readLine(int Fd, char *Buffer) is kind of susceptible to buffer overflow.  I can deduce that fact from the function signature: you pass a pointer to a buffer without also passing the size, so it seems unlikely that readLine would know how to stop when the buffer fills up.  You could hard-code it to use ARP_BUFFER_LEN as a limit, but it would be unfortunate to cripple an otherwise generic function like that.  It would be better to pass in the buffer size explicitly.  That's a general pattern you'll see in C APIs: a pointer to a buffer is frequently accompanied by the buffer's size.

In practice, /proc/net/arp should never contain a line long enough to overflow a 1024-byte buffer, so you're safe.  Still, you should follow idiomatic C conventions.
Once you modify readLine() to take a size parameter, you'll find that you've just reinvented fgets().
In C, passing strings from a function to its caller is usually avoided, since it involves malloc(), which introduces the potential for memory leaks.  Rather, have the caller pass a buffer and size, like how fgets() and scanf() work.

The only good reason to return a string that was allocated using malloc() would be to support arbitrary-length results.  At first glance, your getField() accomplishes that, as it allocates a buffer as large as strlen(Line_Arg).  (You forgot to add a byte to accommodate the terminating NUL character, by the way.)  But, that turns out not to be the case, since Line_Arg itself is not a string of arbitrary length.  It's either less than ARP_BUFFER_LEN bytes long (if you got "lucky") or a buffer overflow (as discussed in (1) above).
You seem to be working very hard at I/O and string processing.  Why not just use fscanf()?

The whole program, then, can be simplified to

#include <stdio.h>

/**
 * Macros to turn a numeric macro into a string literal.  See
 * https://gcc.gnu.org/onlinedocs/cpp/Stringification.html
 */
#define xstr(s) str(s)
#define str(s) #s

#define ARP_CACHE       "/proc/net/arp"
#define ARP_STRING_LEN  1023
#define ARP_BUFFER_LEN  (ARP_STRING_LEN + 1)

/* Format for fscanf() to read the 1st, 4th, and 6th space-delimited fields */
#define ARP_LINE_FORMAT "%" xstr(ARP_STRING_LEN) "s %*s %*s " \
                        "%" xstr(ARP_STRING_LEN) "s %*s " \
                        "%" xstr(ARP_STRING_LEN) "s"

int main()
{
    FILE *arpCache = fopen(ARP_CACHE, "r");
    if (!arpCache)
    {
        perror("Arp Cache: Failed to open file \"" ARP_CACHE "\"");
        return 1;
    }

    /* Ignore the first line, which contains the header */
    char header[ARP_BUFFER_LEN];
    if (!fgets(header, sizeof(header), arpCache))
    {
        return 1;
    }

    char ipAddr[ARP_BUFFER_LEN], hwAddr[ARP_BUFFER_LEN], device[ARP_BUFFER_LEN];
    int count = 0;
    while (3 == fscanf(arpCache, ARP_LINE_FORMAT, ipAddr, hwAddr, device))
    {
        printf("%03d: Mac Address of [%s] on [%s] is \"%s\"\n",
                ++count, ipAddr, device, hwAddr);
    }
    fclose(arpCache);
    return 0;
}


Check if a string contains matching brackets Trying to solve a case for a set of multiple types of brackets.

class BracketHelper {
    // checks if the string contains properly formatted brackets
    public static bool ProperBrackets(string s) {
        int p = 0;
        return ProperBrackets(s.ToCharArray(), ref p);
    }

    // main method, uses recursion to check if the brackets are properly formatted
    private static bool ProperBrackets(char[] arr, ref int ptr, char oppBracket = ' ') {

        for(;ptr<arr.Length;ptr++) {
            var ch = arr[ptr];

            if ( IsOpen(ch)) {  // found an open bracket - let's check the inner content
                ptr +=1; // start checking from the next position
                if (ProperBrackets(arr, ref ptr, OppositeOf(ch)) == false) // inner content is malformed?
                    return false;
            }
            if ( IsClose(ch) ) // found a closing bracket
                return ch == oppBracket; // is this what we were looking for? If not - then we found a malformity!
        }

        // we reached the end. are we still searching for the closing bracket?
        return oppBracket == ' ';
    }

    private static char[] OpenBrackets = new char[] { '{', '[', '(' };
    private static char[] CloseBrackets = new char[] { '}', ']', ')' };

    // check helpers
    private static bool IsOpen(char ch)  {      return OpenBrackets.Contains(ch);       }
    private static bool IsClose(char ch) {      return CloseBrackets.Contains(ch);      }

    // returns a closing bracket character
    private static char OppositeOf(char ch) {
        for(var i=0;i<OpenBrackets.Length;i+=1)
            if ( ch == OpenBrackets[i] )
                return CloseBrackets[i];
        throw new Exception($"'{ch}' is not an open bracket");
    }
}

Some test cases for LinqPad:

(BracketHelper.ProperBrackets("{}") == true).Dump();
(BracketHelper.ProperBrackets("{[]()}") == true).Dump();
(BracketHelper.ProperBrackets("{[()][{}]{}}") == true).Dump();
(BracketHelper.ProperBrackets("{[}]}") == false).Dump();
(BracketHelper.ProperBrackets("{[{(}])}") == false).Dump();
(BracketHelper.ProperBrackets("{[][][][{(})}]}") == false).Dump();
(BracketHelper.ProperBrackets("{[]}}") == false).Dump();
(BracketHelper.ProperBrackets("{") == false).Dump();

This can be done with the ref argument, so the pointer is a member of a class but in this case the method won't be static and I just wanted to make its usage as convenient as possible.

Let's first take a look at the code

The code could use some space to breathe by adding spaces before and after operators. For example for(;ptr<arr.Length;ptr++) would be more readable like
for (; ptr < arr.Length; ptr++)
The expected bracing style would be to place an opening bracket on a new line.
Omitting braces {} although they might be optional can lead to hidden and therefor hard to find bugs. I would like to encourage you to always use them.
Comments should describe why something is done. Comments like if ( IsClose(ch) ) // found a closing bracket are superflous and reduce the readability of the code.
I know that naming things is a hard task but one should at least try to do this in a way that a reader of the code can grasp the meaning of a variable fast which isn'tthe case for oppBracket.  If a method returns a bool one should name that method like a question. E.g AreBracketsProper would be a better name.

Using recursion is a way one can use, but recursion isn't the holy grail for such a task. You need a ref int and an optional oppBracket to achieve the goal by using recursion.

I would use a Stack<Stack<T>> for keeping track of the nesting levels and instead of two char[] arrays I would use two strings and would use IndexOf(char) to get the index of a bracket and to check if the current char is a bracket at all.

If I find an opening bracket I will create a new Stack<int> which contains the value of openingBrackets.IndexOf() and then I will Push() it on the Stack<Stack<int>>. If I find an closing bracket I will take the last index from the Stack<int> if ther is any and check if it is the same as the value returned from closingBrackets.IndexOf(). This coul truned into an extension method as well, like so

static class BracketHelper
{
    private const string openingBrackets = "{[(";
    private const string closingBrackets = "}])";

    public static bool AreBracketsProper(this string value)
    {
        if (value == null) { throw new ArgumentNullException(nameof(value)); }
        if (string.IsNullOrWhiteSpace(value)) { return true; }

        var stacks = new Stack<Stack<int>>();
        var currentStack = new Stack<int>();
        foreach (char c in value)
        {
            var bracketIndex = 0;
            if ((bracketIndex = openingBrackets.IndexOf(c)) > -1)
            {
                currentStack = new Stack<int>();
                currentStack.Push(bracketIndex);
                stacks.Push(currentStack);
            }
            else if ((bracketIndex = closingBrackets.IndexOf(c)) > -1)
            {
                while (currentStack.Count == 0 && stacks.Count > 0)
                {
                    currentStack = stacks.Pop();
                }

                if (currentStack.Count == 0 || bracketIndex != currentStack.Pop()) { return false; }
            }
        }
        return stacks.Count == 0 || stacks.Pop().Count == 0;
    }
}

Which could be called as an extension method like so

("{}".AreBracketsProper() == true).Dump();
("{[]()}".AreBracketsProper() == true).Dump();
("{[()][{}]{}}".AreBracketsProper() == true).Dump();
("{[}]}".AreBracketsProper() == false).Dump();
("{[{(}])}".AreBracketsProper() == false).Dump();
("{[][][][{(})}]}".AreBracketsProper() == false).Dump();
("{[]}}".AreBracketsProper() == false).Dump();
("{".AreBracketsProper() == false).Dump();
("}".AreBracketsProper() == false).Dump();