C function to find and delete a node from a singly linked list I'm looking for the most commonly used style for writing the delete_item() function of a singly linked list, that find a matching item and deletes it. Is what I have the 'typical' or 'normal' solution? Are there more elegant ones?

What seems inelegant to me about my solution below, although I don't know a better way to express it, is that the code needs to check the first record individually (i.e. a special case), then as it goes through the iteration, it's not checking iter, it's checking iter->next, ahead of the iterator's present location, because in a singly linked list you can't go backwards.

So, is there a cleaner way to write the delete_item() function?

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

struct node {
    int x;
    struct node *next;
};

struct node *head;

struct node *create_item(int x);
void print_list();
void delete_item(int x);

int main(int argc, int argv) {

    struct node *n;
    int i;

    // initialise a linked list with a few items
    head = create_item(1);
    n = head;

    for (i = 2; i < 10; i++) {
        n->next = create_item(i);
        n = n->next;
    }

    // before
    print_list();

    // delete 7.
    delete_item(7);

    // after
    print_list();

    // lets delete all odd numbers for effect.
    delete_item(1);
    delete_item(3);
    delete_item(5);
    delete_item(9);

    print_list();
}

struct node *create_item(int x) {
    struct node *new;

    new = (struct node *) malloc (sizeof(struct node));
    new->x = x;
    return new;
}

void print_list() {
    struct node *iter;

    iter = head;

    while (iter != NULL) {
        printf("num: %i\n", iter->x);
        iter = iter->next;
    }
}

//We're looking for the best way to right this.
//This is _my_ standard solution to the problem.
// (that is, to test the first element explicitly
// the use current->next != NULL to be one behind
// the search).
//I wondered what other people's is or if there
//is a convention?
void delete_item(int x) {

    struct node *iter;
    iter = head;

    if (iter == NULL) {
        printf("not found\n");
        return;
    }

    if (iter->x == x) {
        printf("found in first element: %i\n", x);
            head = head->next;
        return;
    }

    while (iter->next != NULL) {
        if (iter->next->x == x) {
            printf("deleting element: %i\n", x);
            iter->next = iter->next->next;
            return;
        }

        iter = iter->next;
    }

    printf("not found\n");
}

This is a complete example that can be compiled and tested. The output:

23:28: ~$ gcc -o ll linked_list.c
23:28: ~$ ./ll
num: 1
num: 2
num: 3
num: 4
num: 5
num: 6
num: 7
num: 8
num: 9
deleting element: 7
num: 1
num: 2
num: 3
num: 4
num: 5
num: 6
num: 8
num: 9
found in first element: 1
deleting element: 3
deleting element: 5
deleting element: 9
num: 2
num: 4
num: 6
num: 8

The neatest way to deal with this is to use what I was taught as the "2 pointer trick" (thank you Charles Lindsay all those years ago):

Instead of holding a pointer to the record you hold a pointer to the pointer that points to it - that is you use a double indirection. This enables you to both modify the pointer to the record and to modify the record without keeping track of the previous node.

One of the nice things about this approach is that you don't need to special case dealing with the first node.

An untested sketch using this idea for delete_item (in C++) looks like:

void delete_item(node** head, int i) {
  for (node** current = head; *current; current = &(*current)->next) {
    if ((*current)->x == i) {
      node* next = (*current)->next;
      delete *current;
      *current = next;
      break;
    }
  }
}

This loop will break after the first entry it finds, but if you remove the "break" then it will remove all entries that match.

Deleting an item from a singly-linked list requires finding the previous item.  There are two approaches one can use to deal with this:

When deleting an item, search through the list to find the previous item, then do the unlink.
Have a "deleted" flag for each item.  When traversing the list for some other reason, check the "deleted" flag on each node.  If a "deleted" node is encountered, unlink it from the previously-visited node.

Note that in a garbage-collected system, it's possible to add items to the start of the list, or perform the #2 style of deletion, in a lock-free thread-safe manner.  Nodes which are deleted may get unlinked in one thread and accidentally relinked in another, but the delete flag will cause the node to be unlinked again on the next pass.  In a multi-threaded system requiring explicit deallocation, such an unlink and relink sequence could be disastrous, since a node could be unlinked, deallocated, and relinked; locks would thus be necessary to avoid problems.


check if two elements exist in array with older browser support Currently I have this code

function foo(firstId, secondId){
    var boolOne = false;
    var boolTwo = false;

    for (var i = 0; i < arr.length; i++) {
        var current = arr[i];
        var id = current.id;

        if(firstId == id){
            boolOne = true;
        }

        if(secondId == id){
            boolTwo = true;
        }

        if(boolOne && boolTwo){
            break;
        }
    }

    if(boolOne && boolTwo){
        bar();
    } else {
        // throw error
    }
}

I want to check if two objects with the given parameter ids already exist in the array.

I put my code into one for-loop but I could also split the code into two loops and break on a match.

I know I could also use

var boolOne = arr.includes(item => item.id == firstId)

but I have to support the Internet Explorer 9+. Is there something that can be optimized?

From a short look

foo is a terrible name

If this is not the real name, then please do submit the real code

arr seems to be a global, bad practice
You don't need current, you could just go for var id = arr[i].id;
For older browsers, it is faster to cache arr.length instead of retrieving it every time
bar is a terrible name, I really hope you don't write production code like that
the call to bar should probably happen outside of that function

Given that, I would go for the below pseudo code:

function arrayHasBothObjects(list, id1, id2){
    var boolOne = false,
        boolTwo = false,
        size = list.length;

    for (var i = 0; i < size; i++) {
        var id = list[i].id;

        boolOne = boolOne || id == id1;
        boolTwo = boolTwo || id == id2;

        if(boolOne && boolTwo){
            return true;
        }
    }
    return false;
}

You can solve it using functional approach, which makes code more consice.
I suggest you to try solve more general problem with n identifiers, because arguments names like 'id1' or 'firstId' is a bad smell.

My solution:

var hasBoth = function(list, id1, id2) {
    return [true, true].toString() === list.reduce(function(res, x) {
        return [id1 === x.id || res[0], id2 === x.id || res[1]];
  }, [false, false]).toString();
}


Concurrent queue with pthread implementation I'm writing a multi-threaded queue implemented with pthreads. Since I came up with the code based on several tutorials from Internet, I would like to make sure there are no logic errors in my code:

template <typename T>
class ThreadQueue {
public:
    ThreadQueue() {
        pthread_mutex_init(&m_qmtx, NULL);
        pthread_cond_init(&m_condv, NULL);
    }

    ~ThreadQueue() {
        pthread_mutex_lock(&m_qmtx);
        m_queue.clear();
        pthread_mutex_unlock(&m_qmtx);
    }

    void push(T t_data) {
        pthread_mutex_lock(&m_qmtx);
        m_queue.push_back(t_data);
        pthread_mutex_unlock(&m_qmtx);

        pthread_cond_signal(&m_condv);
    }

    T front() {
        T ret;
        pthread_mutex_lock(&m_qmtx);
        while (m_queue.empty()) {
            pthread_cond_wait(&m_condv, &m_qmtx);
        }
        ret = m_queue.front();
        pthread_mutex_unlock(&m_qmtx);
        return ret;
    }

    void pop() {
        pthread_mutex_lock(&m_qmtx);
        if (!m_queue.empty())
            m_queue.pop_front();
        pthread_mutex_unlock(&m_qmtx);
    }

private:
    std::deque<T> m_queue;
    pthread_mutex_t m_qmtx;
    pthread_cond_t m_condv;
};

Correctly initialized members.

ThreadQueue() {
    pthread_mutex_init(&m_qmtx, NULL);
    pthread_cond_init(&m_condv, NULL);
}

But you don't check the error codes.
The object is potentially created with invalid members. Use exceptions to gurantee the state of your object.

Destructor does not do anything useful.

~ThreadQueue() {
    pthread_mutex_lock(&m_qmtx);
    m_queue.clear();
    pthread_mutex_unlock(&m_qmtx);
}

The destructr is supposed to clean resources.
It does not. You should destroy the mutex and condition variable in the destructor (reverse order of creation to be consistent).

Also locking before clearing the queue does not buy you anything. If at the point the destructor is called the object is still visible to other threads then it is going to break anyway. The queue is going to call clear in its own destructor so it is pointless doing it manually.

The call to signal should be inside the lock.

void push(T t_data) {
    pthread_mutex_lock(&m_qmtx);
    m_queue.push_back(t_data);
    pthread_mutex_unlock(&m_qmtx);

    pthread_cond_signal(&m_condv);
}

Since you should be using RAII for you locking anyway (See below) the signal is going to fall inside the lock stratergy unless you do something complex.

Also you should pass the parameter by const reference rather than value.

Normally front() is going to give you a reference to the front object.

T front() {
    T ret;
    pthread_mutex_lock(&m_qmtx);
    while (m_queue.empty()) {
        pthread_cond_wait(&m_condv, &m_qmtx);
    }
    ret = m_queue.front();
    pthread_mutex_unlock(&m_qmtx);
    return ret;
}

Returning a copy is probably not what you want (especially for anything interesting). But returning a reference is not really an option either as that opens you to situations where you have race conditions (you have a reference to the top object and another thread pops it (destroying it) just before you call a method).

So you need to provide a method for accessing the object while maintaining the lock (this will probably require the return of a wrapper object that maintains a lock on the queue) or alternatively removing this function.

Other non C++ things that should be addressed:

The mutex should be locked/unlocked using RAII. You are leaving your code open to exception handling problems. If an exception is generated by T which you have no control over then you could leave your queue in an unusable state with the mutex locked and no way to unlock it (because the stack of the locker has been unwound past the unlock because of an exception).

Yes this is correct:

   if (!m_queue.empty())
        m_queue.pop_front();

But don't get into bad habbits. No using the braces can lead to maintenance problems on C/C++ code because of macros. Best practice dictates that you always use {} for sub statements of if/while/for.

To make the code easy to read when including the code in the interface declaration put the variables at the top. Thus you can read the code in with the context of the variables and knowing their type. If you interface declaration is just an interface (and the code is put in the source file rather than the header) then it is fine to put the private variables at the bottom.

Your use of the mutex and condition variable seem correct.

It's a queue. Use a std::queue internally and mimic its interface. You're missing a lot of things. Here's the interface of one I wrote, which exactly mimics std::queue...

template<typename T, typename Container = std::deque<T>>
class ConcurrentQueue
{
public:
    typedef          Container                  container_type;
    typedef typename Container::value_type      value_type;
    typedef typename Container::size_type       size_type;
    typedef typename Container::reference       reference;
    typedef typename Container::const_reference const_reference;

                                 explicit ConcurrentQueue(const Container& c);
                                 explicit ConcurrentQueue(Container&& c = Container());
                                 ConcurrentQueue(const ConcurrentQueue& other);
                                 ConcurrentQueue(ConcurrentQueue&& other);
    template<typename Allocator> explicit ConcurrentQueue(const Allocator& a);
    template<typename Allocator> ConcurrentQueue(const Container& c, const Allocator& a);
    template<typename Allocator> ConcurrentQueue(Container&& c, const Allocator& a);
    template<typename Allocator> ConcurrentQueue(const ConcurrentQueue& other, const Allocator& a);
    template<typename Allocator> ConcurrentQueue(ConcurrentQueue&& other, const Allocator& a);

    ConcurrentQueue& operator=(const ConcurrentQueue& other);
    ConcurrentQueue& operator=(ConcurrentQueue&& other);

    bool empty() const;
    size_type size() const;

    void push(const T& item);
    void push(T&& item);
    template< class... Args >
    void emplace(Args&&... args );
    T pop();
    void swap(ConcurrentQueue& other);

private:
    std::queue<T, Container> m_Queue;
    /* ... */
};

I'll leave it to you to fill in the implementation. I used the C++ standard library, not pthread. I recommend you do too. Note I also called it ConcurrentQueue. It's a more standard name than ThreadQueue for this class. SharedQueue is also quite popular (needless to say, this is a popular thing to write).


Shorter way of prompting for a height of x feet y inches? I'm currently working on a BMI calculator and just wondered if there was a shorter or more condensed version of doing the if validating statement.

I have currently done it this way for both Height and Weight, but I find it to be a mess and it seems to cluttered. There must be a way of shortening this down or condensing it.

boolean Hresult = false;
int resulth = 0;
while(Hresult == false) {

    System.out.print("\nPlease enter your feet: ");
    int heightft = scanner.nextInt();

    if (heightft >=2 && heightft <=7 ){
        System.out.println("You entered: " + heightft);
        Hresult = true;
    }
    else {
           System.out.println("Please try again");
           Hresult = false;
    }
    System.out.print("Please enter your inches: ");
    int heightin = scanner.nextInt();

    if (heightin >=0 && heightin <=11 ){
        System.out.println("You entered: " + heightin);
        Hresult = true;
    }
    else {
        System.out.println("Please try again");
        Hresult = false;
    }
    int resultin = (heightft * 12);
    resulth = (resultin + heightin);
}
return resulth;

The short answer is: Yes, there are ways to improve it!

Coding conventions

First of all, you are not following some Java coding conventions of indentation and where to put }-characters and similar.

Error messages

"Please try again" is not a message that really describes what went wrong. If I would see that message my first reaction would be to try to enter the exact same value again, which would just give me the same error message.

What your code does

Your code is essentially divided into two parts. The first part is:

    System.out.print("\nPlease enter your feet: ");
    int heightft = scanner.nextInt();

    if (heightft >= 2 && heightft <= 7) {
        System.out.println("You entered: " + heightft);
        Hresult = true;
    }
    else {
        System.out.println("Please try again");
        Hresult = false;
    }

Second part:

    System.out.print("Please enter your inches: ");
    int heightin = scanner.nextInt();

    if (heightin >= 0 && heightin <= 11) {
        System.out.println("You entered: " + heightin);
        Hresult = true;
    }
    else {
        System.out.println("Please try again");
        Hresult = false;
    }

Hresult in the first part of the code essentially has no effect because it will be overwritten by Hresult in the second part.

Now let's see what the common areas of this code are:

Show a message
Read an int from the Scanner
Check the range of the entered value
Show what you entered
Return whether or not the result was successful.

This could become it's own method.

public static int inputWithExpectedRange(String message, int min, int max) {
    do {
        System.out.print(message);
        int value = scanner.nextInt();

        if (value >= min && value <= max) {
            System.out.println("You entered: " + value);
        }
        else {
            System.out.println("Expected a value between " + min + " and " + max + ". Please try again");
        }
    }
    while (value < min || value > max);
    return value;
}

Now what you can do is to call this method twice from your previously existing method. It is also likely that you will find use for that method when the user should enter his/her weight.

System.out.println(); // this will print a line break *before* entering the input-method.
int feet = inputWithExpectedRange("Please enter your feet: ", 2, 7);
int inches = inputWithExpectedRange("Please enter your inches: ", 0, 11));
return feet * 12 + inches;

Violà.

An entirely different approach

As mentioned in the comments to your question, you can also use Regular Expressions to verify input and parse it. Here is a brief example of how to use Regular Expressions to input this. I will let you work on the details for it (such as making sure feet and inches are in the proper ranges). And you probably also want it inside some kind of loop (either while or do-while) to make sure that the user enters acceptable values.

    String input = scanner.nextLine();
    String regex = "(\\d+)'(\\d+)\"";
    Pattern pattern = Pattern.compile(regex);
    Matcher matcher = pattern.matcher(input);
    if (!matcher.find()) {
        System.out.println("Input was not in normal feet and inch format");
    }
    int feet = Integer.parseInt(matcher.group(1));
    int inches = Integer.parseInt(matcher.group(2));

If you enter 5'11" the variable feet will be 5 and inches will be 11.

What about some while blocks?

int heightft = 0;
boolean validHeight = false;
do {
    height = scanner.nextInt();
    validHeight = heightft >=2 && heightft <=7;
} while( !validHeight );


Noughts and Crosses game in Python I wrote a two player Noughts and Crosses game in Python 3, and came here to ask how I can improve this code.

import random
cell = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
board = '\n\t ' + cell[0] + ' | ' + cell[1] + ' | ' + cell[2] + '\n\t-----------\n\t ' + cell[3] + ' | ' + cell[4] + ' | ' + cell[5] + '\n\t-----------\n\t ' + cell[6] + ' | ' + cell[7] + ' | ' + cell[8]
def owin(cell):
    return cell[0] == cell[1] == cell[2] == 'O' or cell[3] == cell[4] == cell[5] == 'O' or cell[6] == cell[7] == cell[8] == 'O' or cell[0] == cell[3] == cell[6] == 'O' or cell[1] == cell[4] == cell[7] == 'O' or cell[2] == cell[5] == cell[8] == 'O' or cell[0] == cell[4] == cell[8] == 'O' or cell[2] == cell[4] == cell[6] == 'O'
def xwin(cell):
    return cell[0] == cell[1] == cell[2] == 'X' or cell[3] == cell[4] == cell[5] == 'X' or cell[6] == cell[7] == cell[8] == 'X' or cell[0] == cell[3] == cell[6] == 'X' or cell[1] == cell[4] == cell[7] == 'X' or cell[2] == cell[5] == cell[8] == 'X' or cell[0] == cell[4] == cell[8] == 'X' or cell[2] == cell[4] == cell[6] == 'X'
def tie(cell):
    return cell[0] in ('O', 'X') and cell[1] in ('O', 'X') and cell[2] in ('O', 'X') and cell[3] in ('O', 'X') and cell[4] in ('O', 'X') and cell[5] in ('O', 'X') and cell[6] in ('O', 'X') and cell[7] in ('O', 'X') and cell[8] in ('O', 'X')
print('\tNOUGHTS AND CROSSES\n\t\tBy Lewis Cornwall')
instructions = input('Would you like to read the instructions? (y/n)')
if instructions == 'y':
    print('\nEach player takes turns to place a peice on the following grid:\n\n\t 1 | 2 | 3\n\t-----------\n\t 4 | 5 | 6\n\t-----------\n\t 7 | 8 | 9\n\nBy inputing a vaule when prompted. The first to 3 peices in a row wins.')
player1 = input('Enter player 1\'s name: ')
player2 = input('Enter player 2\'s name: ')
print(player1 + ', you are O and ' + player2 + ', you are X.')
nextPlayer = player1
while not(owin(cell) or xwin(cell)) and not tie(cell):
    print('This is the board:\n' + board)
    if nextPlayer == player1:
        move = input('\n' + player1 + ', select a number (1 - 9) to place your peice: ')
        cell[int(move) - 1] = 'O'
        board = '\n\t ' + cell[0] + ' | ' + cell[1] + ' | ' + cell[2] + '\n\t-----------\n\t ' + cell[3] + ' | ' + cell[4] + ' | ' + cell[5] + '\n\t-----------\n\t ' + cell[6] + ' | ' + cell[7] + ' | ' + cell[8]
        nextPlayer = player2
    else:
        move = input('\n' + player2 + ', select a number (1 - 9) to place your peice: ')
        cell[int(move) - 1] = 'X'
        board = '\n\t ' + cell[0] + ' | ' + cell[1] + ' | ' + cell[2] + '\n\t-----------\n\t ' + cell[3] + ' | ' + cell[4] + ' | ' + cell[5] + '\n\t-----------\n\t ' + cell[6] + ' | ' + cell[7] + ' | ' + cell[8]
        nextPlayer = player1
if owin(cell):
    print('Well done, ' + player1 + ', you won!')
elif xwin(cell):
    print('Well done, ' + player2 + ', you won!')
else:
    print('Unfortunately, neither of you were able to win today.')
input('Press <enter> to quit.')

Some notes:

  cell = ['1', '2', '3', '4', '5', '6', '7', '8', '9']

Try to be less verbose: cell = "123456789".split() or cell = [str(n) for n in range(1, 10)]. Anyway, conceptually it's very dubious you initialize the board with its number instead of its state. Also, cell is not a good name, it's a collection, so cells.

board = '\n\t ' + cell[0] + ...

Don't write such a long lines, split them to fit a sound max width (80/100/...). Anyway, here the problem is that you shouldn't do that manually, do it programmatically (grouped from itertools):

board = "\n\t-----------\n\t".join(" | ".join(xs) for xs in grouped(cell, 3))

  return cell[0] == cell1 == cell[2] == 'O' or cell[3] == cell[4] == cell[5] == 'O' or cell[6] == cell[7] == cell[8] == 'O' or cell[0] == cell[3] == cell[6] == 'O' or cell1 == cell[4] == cell[7] == 'O' or cell[2] == cell[5] == cell[8]== 'O

Ditto, use code:

groups = grouped(cell, 3)
any(all(x == 'O' for x in xs) for xs in [groups, zip(*groups)])

Note that you are not checking if a cell has already a piece.

You should change input to raw_input so that its automatically passed as a string.


RXJS queue up multiple http requests and send when x conditions happens Just started to use rxjs few weeks ago, I think I'm getting most of it right, but my code seems to be not that efficient and prone to bugs I haven't run into yet!

I need to be able to send http requests my app is online(1) and when the user is authenticated(2) and when there's anything to send(3). I'm pretty sure there's a smart way to combine those 3 conditions the "rxjs" way :)

SuperHttpRequest

class SuperHttpRequest extends HttpRequest<any> {

  _id: string; // Used for localStorage

  constructor(method: string, url: string, body: any, _id?: string) {
    super(method, url, body);
    this._id = _id || UUID.UUID();
  }
}

HttpRequestHandler

@Injectable()
class HttpRequestHandler extends ReplaySubject<SuperHttpRequest> {

  nbItemsInQueue$: ReplaySubject<Number>; // Needed by a component (sync progress), would be better to use the combined http request time
  private requests: SuperHttpRequest[];
  private requestsSubcription: Subscription;

  constructor(
    private network: Network, // Ionic service
    private http: HttpClient,
    private localStore: LocalStore<SuperHttpRequest[]>,
    private authService: AuthenticationService) {

    super();

    this.requests = [];
    this.nbItemsInQueue$ = new ReplaySubject(this.requests.length);

    this.localStore.get('http-request')
      .then(requests => {
        if (requests) {
          requests.forEach(request => {
            this.next(new SuperHttpRequest(request.method, request.url, request.body, request._id));
          });
        }
      });

    this.nbItemsInQueue$
      .subscribe(() => this.localStore.set('http-request', this.requests));

    this.authService.currentUser$
      .subscribe(user => {
        if (!user) { if (this.requestsSubcription) { this.requestsSubcription.unsubscribe(); } }
        else {
          this.requestsSubcription = this
            .takeWhile(() => {
              if (navigator.onLine) { return true; }
              else { throw Error(); }
            })
            .retryWhen(() => this.network.onConnect())
            .subscribe(request => this.handleHttpRequest(user, request));
        }
      });
  }

  private handleHttpRequest(user: Credentials, request: SuperHttpRequest) {
    this.http.request(request.clone({ setHeaders: { Authorization: `Bearer ${user.token}` } }))
      .retryWhen(error => {
        return error
          .mergeMap((error: any) => {
            if (error.status === 503) {
              return of(error.status).delay(2000)
            }
            return Observable.throw({ error: 'No retry' });
          })
          .take(5)
          .concat(Observable.throw({ error: 'Sorry, there was an error (after 5 retries)' }));
      })
      .subscribe(res => {
        if (res instanceof HttpResponse) {
          remove(this.requests, (req) => req._id === request._id);
          this.nbItemsInQueue$.next(this.requests.length);
        }
      });
  }

  next(request: SuperHttpRequest) {
    this.requests.push(request);
    this.nbItemsInQueue$.next(this.requests.length);
    super.next(request);
  }

}

//Maintain Queue of http Observable
const quequeHTTP = [];

//Dummy Http Request
getData(){
   return this.http.get('./api');
}

addInQueuqe(observable:Observable<any>){
     quequeHTTP.push(observable);
}

//Dummy addition 4 request
addInQueuqe(this.getData());
addInQueuqe(this.getData());
addInQueuqe(this.getData());
addInQueuqe(this.getData());

eventWhenXHappen(){
  Observable.forkJoin(quequeHTTP).subscribe((resArr)=>{
     console.log('When all request succesfully executed ');
},(err)=>{
  console.log('When error occur');
})

}


Using hash_file for image recognition My team is writing software to be able to grade a basic skills in word/excel/powerpoint test. We are trying to figure out the best way to verify that they included a correct image in their word doc. We know how to get the image file that they use through the xml of the word file. The problem is when we want to verify that the image is the one we expect to be there. Right now we are using the hash_file function in php:

//we know this is the correct hash for the image
$img_hash_correct = 'ab9df995315e2c5cbd0d5cf2210410afa44958c3ca55147497c7a6761340e058';

$hashed_file_submitted = hash_file("sha256", 'hashtest/word/media/image2.jpg');

if ($hashed_file_submitted == $img_hash_correct) {
   echo 'same image!   ';
} else {
   echo 'these are not the same   ';
}

This code has worked after doing some testing. Is this a reliable way to verify that a submitted image is what we are looking for, or is there a more reliable way that you know of?

Without knowing much about your use case, the code looks straightforward. It does exactly what you specify and nothing more.

A few points:

The constant image hash can be defined as global(?)
Use === for comparison.


Minimum number of coins to make change I am new to programming and I am taking CS50 2014 online through iTunes University. This is the change-making problem in Problem Set 1:

  Write a program that first asks the user how much change is owed and then spits out the minimum number of coins with which said change can be made. Assume that the only coins available are quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢).

I am pretty sure that my code is super "hacky." I would love understandable input on how I could have made a better algorithm or how I should have broken down the problem or "You did 'x' here"..."it would be better if you did 'y'."

#include <stdio.h>
#include <cs50.h>
#include <math.h>

int main(void)
{

    // declare float
    float money;

    // Get user input and check if input is positive
    do
    {
        printf("Please input the some amount of money you would like to make change for:  \n");
        money = GetFloat();
    } while (money < 0);

    // Get the Dollars from the Float
    int getDollars = money;

    // Get the cents from the Float
    float getCents = roundf((money * 100) - (getDollars * 100));
    int convertCents = getCents;

    // Greedy Algorithm for Dollars
    int getHundreds = getDollars / 100;
    int getFifties = ((getDollars) - (100 * getHundreds)) / 50;
    int getTwenties = ((getDollars) - (50 * getFifties) - (100 * getHundreds)) / 20;
    int getTens = ((getDollars) - (20 * getTwenties) - (50 * getFifties) - (100 * getHundreds)) / 10;
    int getFives = ((getDollars) - (10 * getTens) - (20 * getTwenties) - (50 * getFifties) - (100 * getHundreds)) / 5;
    int getOnes = ((getDollars) - (10 * getTens) -(5 * getFives) - (20 * getTwenties) - (50 * getFifties) - (100 * getHundreds)) / 1;

    //Greedy Algorithm for Cents
    int getQuaters = convertCents / 25;
    int getDimes = ((convertCents) - (getQuaters * 25)) / 10;
    int getNickles = ((convertCents) - (getQuaters * 25) - (getDimes * 10)) / 5;
    int getPennies = ((convertCents) - (getQuaters * 25) - (getDimes * 10) - (getNickles * 5)) / 1;

    printf("\n");
    if (convertCents == 0)
    {
        printf("The least possible steps you can make change from $%i.%i0 is %i. \n", getDollars, convertCents, (getHundreds + getFifties + getTwenties + getTens + getFives + getOnes + getQuaters + getDimes + getNickles + getPennies));
    }
    else if (convertCents < 10 && convertCents > 0)
    {
        printf("The least possible steps you can make change from $%i.0%i is %i. \n", getDollars, convertCents, (getHundreds + getFifties + getTwenties + getTens + getFives + getOnes + getQuaters + getDimes + getNickles + getPennies));
    }
    else
    {
        printf("The least possible steps you can make change from $%i.%i is %i. \n", getDollars, convertCents, (getHundreds + getFifties + getTwenties + getTens + getFives + getOnes + getQuaters + getDimes + getNickles + getPennies));
    }
}

Also please forgive me I kind of went out of the scope of the problem. I appended it knowing the fact that I would like to use currently circulating paper denominations as well as coins.

Printf format

I noticed that at the end of your program you had 3 cases due to trying to print the number of cents out correctly.  You can do it all in 1 case by using the %02i format.  This format prints an integer with 2 digit width and pads the leading digits with zeros.

Simplifying the logic

Right now, your logic for each denomination gets more and more complicated as you go along because you are subtracting more and more things from the total on each step.  If you simply subtracted the amount from the total right away, you wouldn't have to repeat it on each step.  For example:

int getHundreds = getDollars / 100;
getDollars -= getHundreds * 100;
int getFifties = getDollars / 50;
getDollars -= getFifties * 50;
int getTwenties = getDollars / 20;
getDollars -= getTwenties * 20;
// etc.

Using functions

Now that you have simplified the logic, you can put that logic into a function.  For example:

/**
 * @param        pAmount          Points to amount of money.  Returns the amount
 *                                minus the amount used up by this denomination.
 * @param        denomination     The value of this denomination.
 * @return                        The number of units of this denomination.
 */
int makeChange(int *pAmount, int denomination)
{
    int ret = *pAmount / denomination;

    *pAmount -= ret * denomination;
    return ret;
}

int main(void) {
    // ...
    int remainingDollars = getDollars;
    int getHundreds = makeChange(&remainingDollars, 100);
    int getFifties  = makeChange(&remainingDollars,  50);
    int getTwenties = makeChange(&remainingDollars,  20);
    // etc.
}

Reducing the number of variables

Since you aren't actually printing out how many of each bill/coin you are using, you don't need so many variables.  You only actually need to know how many bills plus coins you need.  So you could change your code to:

    int remainingDollars  = getDollars;
    int numBillsPlusCoins = 0;

    numBillsPlusCoins += makeChange(&remainingDollars, 100);
    numBillsPlusCoins += makeChange(&remainingDollars,  50);
    numBillsPlusCoins += makeChange(&remainingDollars,  20);
    // etc.

Using arrays

There's still a lot of repetition.  It would be nice to not have to copy/paste one line per denomination.  You can use arrays to handle each denomination in a loop instead.  You just need to create an array with the possible bill denominations and one for the coin denominations.

Some other miscellany:

I added my own GetFloat() function because I don't have whatever library you are using.
I removed the use of roundf() and just did the rounding myself.
I used a DIM() macro which returns the dimensions of a given array.  You will encounter this in C a lot for loops which need to loop over a statically defined array.

Here is the final code:

#include <stdio.h>

#define DIM(array)        (sizeof(array)/sizeof(array[0]))

float GetFloat(void)
{
    float ret = 0;
    scanf("%f", &ret);
    return ret;
}

/**
 * @param       pAmount         Points to amount of money.  Returns the amount
 *                              minus the amount used up by this denomination.
 * @param       denomination    The amount for this denomination.
 * @return                      The number of units of this denomination.
 */
int makeChange(int *pAmount, int denomination)
{
    int ret = *pAmount / denomination;

    *pAmount -= ret * denomination;
    return ret;
}

int main(void)
{
    // declare float
    float money;
    const int billDenominations[] = { 100, 50, 20, 10, 5, 1 };
    const int coinDenominations[] = { 25, 10, 5, 1 };

    // Get user input and check if input is positive
    do
    {
        printf("Please input the some amount of money you would like to "
                "make change for:  \n");
        money = GetFloat();
    } while (money < 0);

    // Get the Dollars from the Float
    int numDollars = (int) money;

    // Get the cents from the Float (rounded to nearest cent)
    int numCents = (int) ((money - numDollars) * 100 + 0.5f);

    int remainingDollars = numDollars;
    int remainingCents   = numCents;
    int numBillsAndCoins = 0;

    // Greedy Algorithm for Dollars
    for (int i = 0;i < DIM(billDenominations);i++)
        numBillsAndCoins += makeChange(&remainingDollars, billDenominations[i]);

    // Greedy Algorithm for Cents
    for (int i = 0;i < DIM(coinDenominations);i++)
        numBillsAndCoins += makeChange(&remainingCents, coinDenominations[i]);

    printf("\nThe least possible steps you can make change from "
            "$%i.%02i is %i. \n", numDollars, numCents, numBillsAndCoins);
}

You should use a loop, the algorithm I suggest is this:

def minimum_coins (amount, coins):
    coins_used = []
    while amount:
        coin = max(c for c in coins if amount >= c)
        amount -= coin
        coins_used.append(coin)
    return len(coins_used)

of course translating this into low level C won't be short, but for sure shorter and more understandable than your implementation.

Let me make an example of my greedy algorithm, take the biggest possible coin each time:

  How do I pay 117 cents using only [100, 20, 10, 5, 1] ?

117 - 100 = 17
17 - 10 = 7 # 100 and 20 would be too big
7 - 5 = 2 # 100, 20 and 10 would be too big
2 - 1 = 1
1 - 1 = 0

Using five coins, namely [100, 10, 5, 1, 1].


Parse a value to a given datatype For our (internal) automated test project, I am writing a part where parameters can be passed to an SSIS Package before it gets executed. The tester delivers the parameter name, value and desired datatype in a table format. I get the datatype and parses it to the correct type. We assume a happy flow (when testers do something wrong, no pretty feedback is needed, they can read the exceptions).

The following code is the snippet I am not happy with:

foreach (var row in parametersTable.Rows)
{
    object value;
    if (parametersTable.ContainsColumn("DataType") && !String.IsNullOrEmpty(row["DataType"]))
    {
        string dataType = row["DataType"].ToLower();
        if ("int64".Equals(dataType))
        {
            value = Int64.Parse(row["Value"]);
        }
        else if ("datetime".Equals(dataType))
        {
            value = DateTime.Parse(row["Value"]);
        }
        else
        {
            throw new ArgumentException("DataType " + row["DataType"] + " is not supported");
        }
    }
    else
    {
        value = row["Value"];
    }

    pfe.AddParameter(row["Name"], value);
}

I think, my string manipulation and testing can be improved and I'd like to make the "test and parse" section more expandable. Maybe an Enum or an helper object where I just have to add a single value to make it work for additional datatypes.

There is no magic method in .NET that will know the datatype and magically returns the right parsed value for you. So, creating your own method of parsing and doing manipulation is not a bad thing. This can be improved though.

Use a method:

I prefere to place code that does a certain manipulation or calculation on variables in a separate method/function. This gives me the ability to reuse the code if necessary and maintaining the code is also easier then looking in chunks of code to change just a small bit (like adding a datatype in your case).

switch vs. if/else:

When facing a simple check for a value or condition of a variable, an if/else-statement will certainly do. But when you have a list of options for a variable, it's better to use a swicth-statement. Your code not only looks cleaner, it is cleaner and again, easier to maintain.

This results in following code:

public object ParseValue(string type, string value)
{
    switch(type)
    {
        case "int64" : return Int64.Parse(value);
        case "datetime" : return DateTime.Parse(value);
        case "double" : return Double.Parse(value);
        default: throw new ArgumentException("DataType is not supported");
    }
}

And the usage:

foreach (var row in parametersTable.Rows)
{
    object value;

    if (parametersTable.ContainsColumn("DataType") && !String.IsNullOrEmpty(row["DataType"]))
    {
        var dataType = row["DataType"].ToLower();
        value = ParseValue(dataType, row["Value"]);
    }
    else
    {
        value = row["Value"];
    }

    pfe.AddParameter(row["Name"], value);
}

Another way of using a method is making it return a bool to see if the parsing succeeded and using the out parameter. This results in following method and usage:

public bool TryParseValue(string type, string value, out object parsedValue)
{
    switch(type)
    {
        case "int64" : parsedValue = Int64.Parse(value); return true;
        case "datetime" : parsedValue = DateTime.Parse(value); return true;
        case "double" : parsedValue = Double.Parse(value); return true;
        default: parsedValue = null; return false;
    }
}

foreach (var row in parametersTable.Rows)
{
    object value;

    if (parametersTable.ContainsColumn("DataType") && !String.IsNullOrEmpty(row["DataType"]))
    {
        var dataType = row["DataType"].ToLower();
        if(!TryParseValue(dataType, row["Value"], out value))
        {
            throw new ArgumentException("DataType is not supported");
        }
        //'value' will be correct if the parsing succeeeded
    }
    else
    {
        value = row["Value"];
    }

    pfe.AddParameter(row["Name"], value);
}

You are going to want to use SqlDbType in System.Data.

Something like this:

SqlDbType dataType = row["DataType"] as SqlDbType;
switch(dataType)
{
   case SqlDbType.Int:
      value = Int64.Parse(row["Value"]);
      break;
   case SqlDbType.Int:
      DateTime.Parse(row["Value"]);
      break;
}

Hope that helps.


Immutable subclass of a Set class If I'm creating an immutable class from an existing class, should I override methods that mutate the property or have an instance of it and write my own methods to read from the property?

I have an existing class Set which is basically a fancy array. There's a few more methods in the class but for the purposes of this question they aren't relevant.

<?php

class Set implements \ArrayAccess, \Countable, \IteratorAggregate
{
    protected $items;

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

    public function has($key) {
        return array_key_exists($key, $this->items);
    }

    public function get($key) {
        return $this->has($key) ? $this->items[$key] : null;
    }

    public function set($key, $value) {
        $this->items[$key] = $value;
    }

    public function remove($key) {
        unset($this->items[$key]);
    }

    public function count() {
        return sizeof($this->items);
    }

    public function offsetExists($offset) { return $this->has($offset); }
    public function offsetGet($offset) { return $this->get($offset); }
    public function offsetSet($offset, $value) { $this->set($offset, $value); }
    public function offsetUnset($offset) { $this->remove($offset); }

    public function getIterator() {
        return new \ArrayIterator($this->items);
    }
}

Now I want to create ImmutableSet and here are two options that I came up with:

class ImmutableSet extends Set
{
    public function set($key, $value) {
        throw new \Exception('Cannot set things');
    }

    public function remove($key) {
        throw new \Exception('Cannot remove things');
    }
}

The problem I see with this approach is the existence of set and remove for an immutable object doesn't seem right and supposing that the Set class implemented a method for example clear then I'd have to override that too.

Alternatively, I can do this:

class ImmutableSet implements \Countable, \IteratorAggregate
{
    private $items;

    public function __construct(array $items) {
        $this->items = new Set($items);
    }

    public function has($key) {
        return $items->has($key);
    }

    // Implement get, count, and getIterator to call $items->
}

My concern with this design is basically the opposite of the other one. Supposing that Set implemented a method getAllKeys, I'd have to implement it here too to benefit from the functionality.

What is the better approach here?

You are right it seems rather weird for an immutable object to provide setters, which will throw an exception no matter how you call it. I would use inheritance and two different interfaces in this situation.

Imagine the base set. I would argue the base class should be the immutable set, since the immutable set declares functionality which both classes should be able to use. An example could be:

interface ImmutableInterface {

    public function fetch($key);
    public function exists($key);

}

class ImmutableSet implements ImmutableInterface {

    protected $items = [];

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

    public function fetch($key)
    {
        return $this->items[$key];
    }

    public function exists($key)
    {
        return array_key_exists($key, $this->items);
    }

}

You now have a basic implementation. You make your set manipulatable you could write a new interface declaring methods for changing values inside your set. The new interface could be:

interface ChangeableInterface {

    public function add($key, $value);

}

You could then write a sub-class of your original immutable set and implement the new interface. Since the $items array was declared protected any sub-class also has access to it.

class ChangeableSet extends ImmutableSet implements ChangeableInterface {

    public function add($key, $value)
    {
        $this->items[$key] = $value;
    }

}

You can now type-hint against a specific required implementation by using the interfaces. You also have the opportunity to use other classes as long as they implement the specific interface.

You can think of this strategy as declaring the fewest amount of required methods for your class to work. If you want to add more functionality you write an interface declaring no more than the required methods for that functionality to work. You can even take this further. Imagine not all your changeable sets should be able to remove items again. This could be an interface:

interface RemoveableInterface {

    public function remove($key);

}

You would then write a new sub-class of either the ChangeableSet or ImmutableSet, depending on your requirements, and implement the new interface. You can now type-hint specifically against sets which are only able to remove items. This strategy can continue forever, but do be careful. This can also be too much. Too many sub-classes can become a hell to maintain. So try to keep the amount of interfaces low, while still maintaining your required flexibility and the method signatures they declare concise.

The interface/class names used in these examples are not set in stone. They are by purpose very descriptive, so you can always rename them. Also keep in mind  there are no error checking in the examples.

I hope this can help you, happy coding!

I would recommend doing it the other way around, making ImmutableSet the base class and encapsulating the functionality you need.

class ImmutableSet implements \ArrayAccess, \Countable, \IteratorAggregate
{
    protected $items;

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

    public function has($key) {
        return array_key_exists($key, $this->items);
    }

    public function get($key) {
        return $this->has($key) ? $this->items[$key] : null;
    }

    public function count() {
        return sizeof($this->items);
    }

    public function offsetExists($offset) { return $this->has($offset); }
    public function offsetGet($offset) { return $this->get($offset); }
    public function offsetSet($offset, $value) { $this->set($offset, $value); }
    public function offsetUnset($offset) { $this->remove($offset); }

    public function getIterator() {
        return new \ArrayIterator($this->items);
    }
}

You then inherit and implement the extra methods:

class Set extends ImmutableSet
{
    public function set($key, $value) {
        $this->items[$key] = $value;
    }

    public function remove($key) {
        unset($this->items[$key]);
    }
}

This would happen if we were to follow your naming convention, however that could also change. You should call the base class Set and the child class MutableSet, which seems to make more sense in terms of inheritance.

The pattern is not complete if you can't change from one to the other, however, which requires implementing copy methods and constructors, such as copy and immutableCopy. You'll notice that this is the exact pattern used by Objective-C frameworks.

Edit for further clarification:

What I mean is that you need to implement a mechanism of turning mutable sets into immutable ones and vice-versa. Take the following example:

function foo(Set $set)
{
    $set = (MutableSet)$set;
    $set->set('key', 'value');
}

// Somewhere
$set = new MutableSet();
foo($set);

Disclaimer: the code isn't tested and I haven't written anything in PHP for a while, there might be issues, even syntactic.

Notice how the set is assumed to be immutable but it still mutates, and it's perfectly valid code. This depends on how far you want to take this, because if it's a requirement to prevent situations like these you'll need to create copies:

$set = new MutableSet();
foo($set->immutableCopy()); // Or just "copy"

This would prevent situations like the one I described. Again, this is the pattern used by Objective-C, I'm not making anything up.


Sending a C++ array to Python/NumPy and back I am going to send a C++ array to a Python function as NumPy array and get back another NumPy array. After consulting with NumPy documentation and some other threads and tweaking the code, the code is finally working but I would like to know if this code is written optimally considering the:

Unnecessary copying of the array between C++ and Numpy (Python).
Correct dereferencing of the variables.
Easy straight-forward approach.

C++ code:

// python_embed.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION
#include "Python.h"
#include "numpy/arrayobject.h"
#include<iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    Py_SetProgramName(argv[0]);
    Py_Initialize();
    import_array()

    // Build the 2D array
    PyObject *pArgs, *pReturn, *pModule, *pFunc;
    PyArrayObject *np_ret, *np_arg;
    const int SIZE{ 10 };
    npy_intp dims[2]{SIZE, SIZE};
    const int ND{ 2 };
    long double(*c_arr)[SIZE]{ new long double[SIZE][SIZE] };
    long double* c_out;
    for (int i{}; i < SIZE; i++)
        for (int j{}; j < SIZE; j++)
            c_arr[i][j] = i * SIZE + j;

    np_arg = reinterpret_cast<PyArrayObject*>(PyArray_SimpleNewFromData(ND, dims, NPY_LONGDOUBLE,
        reinterpret_cast<void*>(c_arr)));

    // Calling array_tutorial from mymodule
    PyObject *pName = PyUnicode_FromString("mymodule");
    pModule = PyImport_Import(pName);
    Py_DECREF(pName);
    if (!pModule){
        cout << "mymodule can not be imported" << endl;
        Py_DECREF(np_arg);
        delete[] c_arr;
        return 1;
    }
    pFunc = PyObject_GetAttrString(pModule, "array_tutorial");
    if (!pFunc || !PyCallable_Check(pFunc)){
        Py_DECREF(pModule);
        Py_XDECREF(pFunc);
        Py_DECREF(np_arg);
        delete[] c_arr;
        cout << "array_tutorial is null or not callable" << endl;
        return 1;
    }
    pArgs = PyTuple_New(1);
    PyTuple_SetItem(pArgs, 0, reinterpret_cast<PyObject*>(np_arg));
    pReturn = PyObject_CallObject(pFunc, pArgs);
    np_ret = reinterpret_cast<PyArrayObject*>(pReturn);
    if (PyArray_NDIM(np_ret) != ND - 1){ // row[0] is returned
        cout << "Function returned with wrong dimension" << endl;
        Py_DECREF(pFunc);
        Py_DECREF(pModule);
        Py_DECREF(np_arg);
        Py_DECREF(np_ret);
        delete[] c_arr;
        return 1;
    }
    int len{ PyArray_SHAPE(np_ret)[0] };
    c_out = reinterpret_cast<long double*>(PyArray_DATA(np_ret));
    cout << "Printing output array" << endl;
    for (int i{}; i < len; i++)
        cout << c_out[i] << ' ';
    cout << endl;

    // Finalizing
    Py_DECREF(pFunc);
    Py_DECREF(pModule);
    Py_DECREF(np_arg);
    Py_DECREF(np_ret);
    delete[] c_arr;
    Py_Finalize();
    return 0;
}

Python Code:

def array_tutorial(a):
    print("a.shape={}, a.dtype={}".format(a.shape, a.dtype))
    print(a)
    a *= 2
    return a[-1]

1. Review

It's not recommended to use using namespace std; — the problem is that this imports all of the identifiers from std, and some of these may shadow names from other modules that you need to use. See this question on Stack Overflow.
The code doesn't check for success/failure of many of the functions it calls. These can all fail:

new long double[SIZE][SIZE]
PyArray_SimpleNewFromData
PyUnicode_FromString
PyTuple_New
PyTuple_SetItem
PyObject_CallObject

(and maybe others that I didn't spot).
There's no Py_DECREF for pArgs.
It would be possible to avoid constructing the argument tuple, by using PyObject_CallFunctionObjArgs instead of PyObject_CallObject.
Error messages should be written to standard error (cerr), not standard output.
It's clearer to use the macros EXIT_SUCCESS and EXIT_FAILURE from <cstdlib> instead of 0 and 1.
The code calls PyArray_NDIM and PyArray_SHAPE on np_ret without checking to see if this object is in fact an array. Call PyArray_Check first.
Using value initialization for int variables seems perverse to me. With int i{} you have to remember that the default constructor gives the variable the value 0. With int i = 0 there's no need to remember (and the code is no less efficient: the compiled code doesn't actually create a temporary 0 object and then call the int assignment constructor).
This code doesn't provide as much information about errors as it could. In particular, errors inside Python cause Python to create an exception object containing information about the error (see "Exception Handling"). It would be a good idea to print this object if it exists, by checking PyErr_Occurred and then calling PyErr_Print.
Each block of error handling code has to undo the effect of all the previous successful blocks of code. This makes the length of the function quadratic in the number of error cases! This is risky, because every time you change something, you have to adjust all the error cases accordingly, and it is very easy to forget (as in §1.3 above). Also, the pain of writing out all the error-handling code makes it tempting to skip error handling for functions that you believe are likely to succeed (as in §1.2 above).

See the revised code below for one way to arrange that each "undo" operation appears just once.

2. Revised code

This is untested, so probably has some errors.

int _tmain(int argc, _TCHAR* argv[])
{
    int result = EXIT_FAILURE;

    Py_SetProgramName(argv[0]);
    Py_Initialize();
    import_array();

    // Build the 2D array in C++
    const int SIZE = 10;
    npy_intp dims[2]{SIZE, SIZE};
    const int ND = 2;
    long double(*c_arr)[SIZE]{ new long double[SIZE][SIZE] };
    if (!c_arr) {
        std::cerr << "Out of memory." << std::endl;
        goto fail_c_array;
    }
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < SIZE; j++)
            c_arr[i][j] = i * SIZE + j;

    // Convert it to a NumPy array.
    PyObject *pArray = PyArray_SimpleNewFromData(
        ND, dims, NPY_LONGDOUBLE, reinterpret_cast<void*>(c_arr));
    if (!pArray)
        goto fail_np_array;
    PyArrayObject *np_arr = reinterpret_cast<PyArrayObject*>(pArray);

    // import mymodule.array_tutorial
    const char *module_name = "mymodule";
    PyObject *pName = PyUnicode_FromString(module_name);
    if (!pName)
        goto fail_name;
    PyObject *pModule = PyImport_Import(pName);
    Py_DECREF(pName);
    if (!pModule)
        goto fail_import;
    const char *func_name = "array_tutorial";
    PyObject *pFunc = PyObject_GetAttrString(pModule, func_name);
    if (!pFunc)
        goto fail_getattr;
    if (!PyCallable_Check(pFunc)){
        std::cerr << module_name << "." << func_name
                  << " is not callable." << std::endl;
        goto fail_callable;
    }

    // np_ret = mymodule.array_tutorial(np_arr)
    PyObject *pReturn = PyObject_CallFunctionObjArgs(pFunc, pArray, NULL);
    if (!pReturn)
        goto fail_call;
    if (!PyArray_Check(pReturn)) {
        std::cerr << module_name << "." << func_name
                  << " did not return an array." << std::endl;
        goto fail_array_check;
    }
    PyArrayObject *np_ret = reinterpret_cast<PyArrayObject*>(pReturn);
    if (PyArray_NDIM(np_ret) != ND - 1) {
        std::cerr << module_name << "." << func_name
                  << " returned array with wrong dimension." << std::endl;
        goto fail_ndim;
    }

    // Convert back to C++ array and print.
    int len = PyArray_SHAPE(np_ret)[0];
    c_out = reinterpret_cast<long double*>(PyArray_DATA(np_ret));
    std::cout << "Printing output array" << std::endl;
    for (int i = 0; i < len; i++)
        std::cout << c_out[i] << ' ';
    std::cout << std::endl;
    result = EXIT_SUCCESS;

fail_ndim:
fail_array_check:
    Py_DECREF(pReturn);
fail_call:
fail_callable:
    Py_DECREF(pFunc);
fail_getattr:
    Py_DECREF(pModule);
fail_import:
fail_name:
    Py_DECREF(pArray);
fail_np_array:
    delete[] c_arr;
fail_c_array:
    if (PyErr_Check())
        PyErr_Print();
    PyFinalize();
    return result;
}

I find this simple code work well though it sends array to a Python function as Tuple but not numpy array, but it is easier to change Tuple into numpy array in Python:

c++
...
PyObject* pArgs = PyTuple_New(2);
PyTuple_SetItem(pArgs, 0, Py_BuildValue("i", 1));
PyTuple_SetItem(pArgs, 1, Py_BuildValue("i", 2));
PyObject_CallObject(pFunc, pArgs);
...

&

python
def func(*list):
  print list[0] + list[1]


Fluent interface for Logger I was trying to wrap a Logback logger in order to provide some handy methods and already defined default keys of the logged json output and I came up with something like this.

Do you spot any problem with it, or do you have any suggestion?

public class Log {

    private Logger logger = LoggerFactory.getLogger("jsonLogger");

    private String msg;
    private long start;
    private Map<String, Object> kvs;

    private Log(String msg) {
        this.msg = msg;
        this.start = System.currentTimeMillis();
        this.kvs = new HashMap<>();
    }

    public static Log msg(String msg) {
        return new Log(msg);
    }

    public Log kv(String key, Object value) {
        kvs.put(key, value);
        return this;
    }

    public void log() {
        kvs.put("elapsed", System.currentTimeMillis() - start);
        List<StructuredArgument> args = new ArrayList<>();
        for (String k : kvs.keySet()) {
            args.add(StructuredArguments.kv(k, kvs.get(k)));
        }
        logger.info(msg, args.toArray());
    }

}

In this way you can log just a message, custom key-values and have a way to keep track of the execution between a function:

// just a message
Log.msg("my message").log();

// message with custom kv or complex objects
Log.msg("my message").kv("foo", "bar").kv("arr", new String[]{"a", "b", "c"}).log();

// elapsed time
Log logger = Log.msg("my message").kv("foo", "bar");
Thread.sleep(1240);
logger.log();

i do not think this is really a good idea (sorry to say that)...

why is is not a good idea? it's breaking the concept of segregaton of concerns:

a Logger is responsible for logging
a Profiler is responsible for measuring execution time
a Logger is NOT responsible for keeping track of items (who is responsible for cleaning these entries?)

another issue i see is that you create a new logger whenever you want to write something into you log, i don't see any reason for that...

what would i suggest?

create a timesheet

public class Timesheet{

   private final Map<TimeStamp, KeyValue kv> entries;
   private final Logger logger;

    public Timesheet(Logger logger){
        this.logger = logger
        entries= ...
    }

    public Timesheet kv(Object key, Object value) {
        TimeStamp timestamp = new TimeStamp();
        entries.put(timestamp , new KeyValue(key, value));
        log.debug("adding key/value {}/{} at {}", key, value, timestamp );
        return this;
    }

    public Timesheet msg(Object msg) {
        logger.debug(msg);
        return this;
    }

    public Timesheet elapsed() {
        logger.debug("time elapsed {}", calculateTimeElapsed());
        return this;
    }

}

not all is implemented here, it should just girve you an idea of how you could do it...

Timesheet timesheet = new Timesheet(LoggerFactory.getLogger("jsonLogger")); //now availible for all classes
timesheet.msg("hello");
timesheet.kv("foo", "bar");
Thread.sleep(1234);
timesheet.elapsed();

some final words...

i think it is not a good idea of using KeyValue pairs - if you know what kind of entries these are, give them a proper name!

i think if you would have choosen a more compliant name (Log is really confusing) your idea would not have been so bad...


fs to fs-extra using node js I wrote a code by using var fs= require("fs").promises;

to read all my files in directories and sub-directories

var fs= require("fs").promises;

async function checkFileLoc(folderPath, depth) {
  depth -= 1;
  let files = await fs.readdir(folderPath);
  files = await Promise.all(
    files.map(async (file) => {
      const filePath = path.join(folderPath, file);
      const stats = await fs.stat(filePath);
      if (stats.isDirectory() && depth > 0) {
        return checkFileLoc(filePath, depth);
      } else if (stats.isFile()) return filePath;
      else return null;
    })
  );
  return files
    .reduce((all, folderContents) => all.concat(folderContents), [])
    .filter((e) => e != null);
}

Then I install fs-extra package in my project and replace var fs=require("fs");to var fse=require("fs-extra"); and made changes in my code like this

var fse=require("fs-extra");

async function checkFileLoc(folderPath, depth) {
  depth -= 1;
  let files = await fse.readdir(folderPath);
  files = await Promise.all(
    files.map(async (file) => {
      const filePath = path.join(folderPath, file);
      const stats = await fse.stat(filePath);
      if (stats.isDirectory() && depth > 0) {
        return checkFileLoc(filePath, depth);
      } else if (stats.isFile()) return filePath;
      else return null;
    })
  );
  return files
    .reduce((all, folderContents) => all.concat(folderContents), [])
    .filter((e) => e != null);
}

when I was using fs i was getting the desire output and someone told me fs-extra is advance then fs and all you have to do is replace fs with fse
my code not working properly any solution where i have made mistake ?

I tried to figure it out what changes i have to made if I am using var fse= require("fs-extra");
so my code will look like this

var fse=require("fs-extra");

async function checkFileLoc(folderPath, depth) {
  depth -= 1;
  let files = fse.readdirSync(folderPath);
  files = await Promise.all(
    files.map(async (file) => {
      const filePath = path.join(folderPath, file);
      const stats = fse.statSync(filePath);
      if (stats.isDirectory() && depth > 0) {
        return checkFileLoc(filePath, depth);
      } else if (stats.isFile()) return filePath;
      else return null;
    })
  );
  return files
    .reduce((all, folderContents) => all.concat(folderContents), [])
    .filter((e) => e != null);
}

I replaced my

var fs=require("fs"); to var fse=require("fs-extra");
let files = await fs.readdir(folderPath); with let files = fs.readdirSync(folderPath);
const stats = await fs.stat(filePath); with const stats = fs.statSync(filePath);

now i am getting my desire output


Simple yet threadsafe file cache in java I'm attempting to cache contents of a file to avoid frequent reads, using a very simple implementation in a single class. The file contains a list of emailids, one per line. The file changes rarely, and the cache should be updated immediately when it does. So I've checked the file's timestamp in each read operation. The class will be used in servlets and rest apis - as member variable. Although I've synchronized the only public method of the class, I'm not sure whether the code is threadsafe. Do I need to add/change something here to ensure thread safety ?

public class CachedFile {

    private File file ;
    private long lastModified ;
    private List<String> fileLines ;
    private boolean fileCached ;

    public CachedFile( final String inputFileName )
    {
            file = new File( inputFileName ) ;
            fileCached = false ;
    }

    public synchronized List<String> getLines() throws IOException
    {
            //if file is not cached or if its modified after the last read, read & cache it
            if( fileCached == false || fileModifiedAfterLastRead() )
            {
                    readFile() ;
            }

            return fileLines ;
    }

    private void readFile() throws IOException
    {
            //read file to cache
            fileLines = FileUtils.readLines( file ) ;

            //cache the last modified time
            lastModified = file.lastModified() ;

            //set the cached flag to true
            fileCached = true ;
    }

    private boolean fileModifiedAfterLastRead()
    {
            return( file.lastModified() > lastModified ) ;
    }
}

Since you mentioned that the file could be written by another process (assuming in another jvm), there is no way you can introduce the Object monitor based thread safety. So you can depend upon the last modified time of the file object. You can also remove the synchronization from your getLines() if you dont return the instance variable. But you do return that so synchronization should be there in getLines().

Basically you want to read the file without the data corruption. That could happen if another process is writing to the file when your process reads from it. If that is the case, you want to re-read the file. Here is how I would implement it.

 private void readFile() throws IOException {
     int retryCount = 5;

     while (retryCount > 0) {

       long beforeRead = file.lastModified();
        //read file to cache
       fileLines = FileUtils.readLines(file);

       if (beforeRead == file.lastModified())
           break;

       retryCount--;
     }
  //cache the last modified time
    lastModified = file.lastModified() ;

  //set the cached flag to true
    fileCached = true ;
}

The while loop will retry the read operation if there is a mismatch. Also the retry has to be finite number to avoid looping forever in case of any file system failures.

Your cache is fine and correctly synchronized.

One thing I would change is to remove the throws IOException from the public method. Just for convenience of the calling code.

For the process that updates the file, make sure that it updates the file atomically. That is, first write the data to a temporary file and then rename that to the final file.


Checking multiple XML in PHP I am working on a code to see if a video already exists. The problem is that I have to check multiple sections. The code is working but it should not be this big, I think, and it takes a long time to load.

Is there an easier way to do this?

$xmlurl7b = 'http://mysite.me/library/sections/2/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl1b = 'http://mysite.me/library/sections/5/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl2b = 'http://mysite.me/library/sections/7/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl3b = 'http://mysite.me/library/sections/9/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl4b = 'http://mysite.me/library/sections/10/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl5b = 'http://mysite.me/library/sections/11/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl6b = 'http://mysite.me/library/sections/13/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl8 = 'http://mysite.me/library/sections/3/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl9 = 'http://mysite.me/library/sections/8/all?title=' . $movie->title() . '&HndJk7Sd';
$xmlurl7 = 'http://mysite.me/library/sections/2/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$xmlurl1 = 'http://mysite.me/library/sections/5/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$xmlurl2 = 'http://mysite.me/library/sections/7/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$xmlurl3 = 'http://mysite.me/library/sections/9/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$xmlurl4 = 'http://mysite.me/library/sections/10/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$xmlurl5 = 'http://mysite.me/library/sections/11/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$xmlurl6 = 'http://mysite.me/library/sections/13/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd';
$achxml8 = simplexml_load_file($xmlurl8);
$achxml9 = simplexml_load_file($xmlurl9);
$achxml1 = simplexml_load_file($xmlurl1);
$achxml2 = simplexml_load_file($xmlurl2);
$achxml3 = simplexml_load_file($xmlurl3);
$achxml4 = simplexml_load_file($xmlurl4);
$achxml5 = simplexml_load_file($xmlurl5);
$achxml6 = simplexml_load_file($xmlurl6);
$achxml7 = simplexml_load_file($xmlurl7);
$achxml1b = simplexml_load_file($xmlurl1b);
$achxml2b = simplexml_load_file($xmlurl2b);
$achxml3b = simplexml_load_file($xmlurl3b);
$achxml4b = simplexml_load_file($xmlurl4b);
$achxml5b = simplexml_load_file($xmlurl5b);
$achxml6b = simplexml_load_file($xmlurl6b);
$achxml7b = simplexml_load_file($xmlurl7b);
if( $achxml1->Video && ($achxml1->Video != '')
OR $achxml2->Video && ($achxml2->Video != '')
OR $achxml3->Video && ($achxml3->Video != '')
OR $achxml4->Video && ($achxml4->Video != '')
OR $achxml5->Video && ($achxml5->Video != '')
OR $achxml6->Video && ($achxml6->Video != '')
OR $achxml7->Video && ($achxml7->Video != '')
OR $achxml8->Directory && ($achxml8->Directory != '')
OR $achxml9->Directory && ($achxml9->Directory != '')
OR $achxml1b->Video && ($achxml1b->Video != '')
OR $achxml2b->Video && ($achxml2b->Video != '')
OR $achxml3b->Video && ($achxml3b->Video != '')
OR $achxml4b->Video && ($achxml4b->Video != '')
OR $achxml5b->Video && ($achxml5b->Video != '')
OR $achxml6b->Video && ($achxml6b->Video != '')
OR $achxml7b->Video && ($achxml7b->Video != '')
 ) {
echo 'Exists';
} else {
echo 'New';
}

This is a giant mess! Here's what you should do to start cleaning it up.

Code organization

Everything you are doing is quite repetitive with minimal variations. Start by constructing an array of each section number you need to inspect for title and each section number you need to inspect by guid. You can then iterate through these systematically without writing everything out.
Turn these two strings into constants you define at the top of your file '%3Flang%3Dnl&HndJk7Sd'  and '&HndJk7Sd'. SImilarly does $movie->title() return the same value each time you call it? If so, move this value into a constant too.
I would then do a loop of a kind like this (pseudocode):

for each filename in possible files{
 video = simplexml_load_file(filename)
 if(video->Video && video->Video!='') {
     echo 'Exists'
     gracefully exit script?
}
//If script has not exited file doesn't exist
echo 'New';

Note that this general organization means you stop as soon as you find a file. The way you have set up your code now, you load all directories but you might have actually found the video in the very first place you checked.

PHP language features

Any reason the standard function file_exists() isn't applicable in some way? Not sure why you seem to have all these special functions just to check if a file exists?

Try this approach: instead of using an if condition with many terms OR-ed together, which is hard to read and error prone, use a loop.

$sources = [
    [
        'url'  => 'http://mysite.me/library/sections/2/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/5/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/7/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/9/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/10/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/11/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/13/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/3/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Directory'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/8/all?title=' . $movie->title() . '&HndJk7Sd',
        'node' => 'Directory'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/2/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/5/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/7/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/9/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/10/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/11/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ],
    [
        'url'  => 'http://mysite.me/library/sections/13/all?guid=movieid' . $movieid . '%3Flang%3Dnl&HndJk7Sd',
        'node' => 'Video'
    ]
];

$exists = false;
foreach ($sources as $source) {
    $xml = simplexml_load_file($source['url']);

    if (isset($xml->{$source['node']}) && $xml->{$source['node']} != '') {
        $exists = true;
        break;
    }
}

if ($exists) {
    echo 'Exists';
} else {
    echo 'New';
}


Minimum number of moves for a knight The problem is to find the minimum number of moves that a knight will take to go from one square to another on a 'n' cross 'n' chessboard. The code below is based on backtracking. It works well until n equals 5 but from n equals 6 the time limit is exceeded on ideone. How can I make the code more efficient?

#include <stdio.h>

int minimum(int a, int b)
{
    /* Returns the minimum of two numbers */
    if (a <= b) {
        return a;
    } else {
        return b;
    }
}

int minmoves(int r1, int c1, int r2, int c2, int array[10][10], int n)
{
    int moves;

    /*
     * If the place is already occupied dont go to it otherwise it will
     * lead to a infinite loop so we return a large value so that the
     * knight does not take this path
     */
    if (array[r2][c2] == 1) {
        return 32764;
    }

    /* We cannot go outside the board */
    if ((r2 < 0) || (r2 > n - 1) || (c2 < 0) || (c2 > n - 1)) {
        return 32764;
    }

    /* Condition to check if the path is complete */
    if ((r1 == r2) && (c1 == c2)) {
        return 0;
    }

    /* We add the point with coordinates r2, c2 to the path */
    array[r2][c2] = 1;

    /* All the possible moves that a knight can make */
    moves = 1 + minmoves(r1, c1, r2 - 2, c2 - 1, array);
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 2, c2 + 1, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 1, c2 - 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 1, c2 + 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 1, c2 - 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 1, c2 + 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 2, c2 - 1, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 2, c2 + 1, array));

    array[r2][c2] = 0;

    return moves;
}

int main()
{
    int r1, c1, r2, c2, x, i, j, n;
    int array[10][10];

    scanf("%d\n%d\n%d\n%d\n%d", &r1, &c1, &r2, &c2, &n);

    /* All the elements of array are initialised to zero */
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            array[i][j] = 0;
            printf("0 ");
        }
    }

    x = minmoves(r1, c1, r2, c2, array, n);

    printf("%d",x);
    return 0;
}

I will answer an isomorphous question of finding a minimal value in a binary tree. In your case, the tree is octal, but the same rules apply.

Consider that you have

typedef struct node {
     struct node *pLeft, *pRight;
     int value;
} node_t;

The tree is completely unsorted, and you need to find the minimal value. What you are doing is something like this:

int minval(node_t *pRoot)
{
    if (pRoot == NULL)
        return INT_MAX;

    int min = pRoot->value;

    min = minimum(min, minval(pRoot->pLeft));
    min = minimum(min, minval(pRoot->pRight));

    return min;
}

This is a recursive algorithm. It's elegant, nice, cool and bloody slow.
Recursion is slow because every time you call a function it has to do all sorts of staging (pass arguments, call function, allocate stack space), and then repeat all that on return (clean up stack, return from call, clean up arguments).

There are non recursive algorithms to most problems, but there's also a nice way to get rid of all the costly staging for calling a function. (inlining a function does that too, but it is not possible for recursive functions). Let us take a look at code that does exactly the same thing as above, but without recursion:

int minval(node_t *pRoot)
{
    if (pRoot == NULL)
        return INT_MAX;

    node_t *stack[100]; // At least max tree depth*2, in your case n*8
    int sp = 0;
    int min = INT_MAX;

    stack[sp++] = pRoot;
    while (sp > 0)
    {
        node_t *p = stack[--sp];
        min = minimum(min, p->value);

        if (p->pLeft  != NULL) stack[sp++] = p->pLeft;
        if (p->pRight != NULL) stack[sp++] = p->pRight;
    }

    return min;
}

Here we have a simulated program stack, but we don't do so much with it, we only add one pointer for every tree node, which in your case is 8^5, or 32768. Compared to that many function calls.

If you modify your program to not actually call the function recursively, you should gain a very significant speed boost. Using the template I provided, it shouldn't be a problem, you'll just have 8 things to put on the stack every iteration.

Fun fact: What you are doing is known as a preorder tree traversal, also known as a depth-first search. If you were to do a level order traversal (also known as a breadth-first search), the code would go faster. The difference is that DFS will look at all paths, while you can stop BFS early as soon as it finds one.

Maybe try combining the two 'if' statements that both end up returning 32764.

Also, you might gain slightly more efficiency making the line ' if((r1==r2)&&(c1==c2))' into an 'else if...' statement and combining it with the statements above. Not too sure what it will do in execution time, but it will shorten the line count a bit.

Another thing might b to reorder the if statement that I mentioned at the beginning of my post. While C does not always have the same execution order between compilers, you might find putting the various items you are testing for in order of least complexity/most common will mean that it uses less time and/or less processing cycles to make a determination if it is indeed going to hit one of those items. If it does not match any, then it would have anyways needed to be checked anyways and that cannot really be reduced.


Is My Function to Find Triplets in Scala running in O(N^2) Given the classical problem to find triplets that sum to zero in an array. Is my Scala implementation correct and executed in O(N^2)? If yes, why? Can someone make a running time analysis.
What other ways could we solve this issue? With duplicated elements and not using the two pointer technique?
def tripletsFromArrayThatSumZero(input: Array[Int]): Array[Array[Int]] = {
    val target = 0 // the target is the number after the sum
    val sortedArray = input.sorted
    var resultsArrayOfTriplets = Array[Array[Int]]()

    for (i <- sortedArray.indices) {
      var j = i + 1
      var k = sortedArray.length - 1
      val twoSum = target - sortedArray(i)

      Breaks.breakable {
        while (j < sortedArray.length) {
          val sum = sortedArray(j) + sortedArray(k)
          if (k == j) Breaks.break()
          if (sum > twoSum) {
            k -= 1
          } else if (sum < twoSum) {
            j += 1
          } else if (sum == twoSum) {
            val triplet = Array(sortedArray(i), sortedArray(j), sortedArray(k) )
            resultsArrayOfTriplets = resultsArrayOfTriplets :+ triplet
            Breaks.break()
          }
        }
      }
    }
    resultsArrayOfTriplets
  }

I have a few issues with the posted code. We'll start with the trivial.
Code posted on Code Review should be complete. You forgot to include the necessary import to make this compile.
val target = 0 - I find this somewhat redundant. If target isn't zero then you also need to change the name of the method. On the other hand, we're not supposed to bury "magic numbers" in our code, so it's debatable.
But the real problem here is that you're writing imperative code in a functional language. You've written C code in Scala.
Imperative : Create an empty mutable collection. Run code with a side-effect of filling the collection. Return the collection.
Functional : Start with one or more populated collections. Filter, collect, and transform them, without mutation, into the resulting collection.
Here's an implementation that's similar in that the i index starts at zero, the j index starts at i+1, and the k index searches the remaining space for the result.
def zeroSumTriples(input: Array[Int]): Array[Array[Int]] = {
  val sortedInput = input.sorted

  sortedInput.takeWhile(_ < 1).indices.flatMap{ i =>
    (i+1).until(input.length-1).flatMap{ j =>
      val (a, b) = (sortedInput(i), sortedInput(j))
      Iterator.from(j+1).take(input.length-j-1)
              .dropWhile(a + b + sortedInput(_) < 0)
              .takeWhile(a + b + sortedInput(_) == 0)
              .map(k => Array(a, b, sortedInput(k)))
    }
  }
}.toArray

Your solution also works with O(n ^ 2), except you need to cover few cases as mentioned in the comments above.
A small solution that could make things look neat:
Efficient O(n ^ 2) ThreeSum Solution In Scala
object Solution {
  import scala.util.Sorting
  import scala.collection.mutable
  def threeSum(a: Array[Int]): List[List[Int]] = {
    if(a.isEmpty) List.empty
    else {
      Sorting.quickSort(a)
      val resArr = mutable.Set.empty[List[Int]]
      val range = a.indices.init
      for {
        i <- range
      } yield {
        var l = i + 1
        var r = a.length - 1
        while(l < r) {
          val tSum = a(i) + a(l) + a(r)
          if(tSum == 0) {
            resArr.addOne(List(a(i), a(l), a(r)))
            l += 1
            r -= 1
          } else if(tSum < 0) { l += 1 }
          else { r -= 1  }
        }
      }
      resArr.toList
    }
  }
}


Convert object array to hash map using lodash The use case is to convert an array of objects into a hash map where one property is the key and the other property is the value. Common case of using this is converting a "link" object in a hypermedia response into a hash map of links.

jsfiddle

function toHashMap(data, name, value) {
    return _.zipObject(_.pluck(data, name),
                       _.pluck(data, value));
}

function toMap(data, name, value) {
    return _.reduce(data, function(acc, item) {
        acc[item[name]] = item[value];
        return acc;
    }, {});
}

var data = [
    { rel: 'link1', href: 'url1'},
    { rel: 'link2', href: 'url2'},
    { rel: 'link3', href: 'url3'},
    { rel: 'link4', href: 'url4'},
];

console.log(toHashMap(data, 'rel', 'href'));

console.log(toMap(data, 'rel', 'href'));

toHashMap appears much more readable, but less efficient. toMap seems to have the best efficiency at the expense of readability.

Is there a more elegant solution - i.e. both readable and efficient? I suspect that Lodash might have a function to do this already, but I haven't found anything like this after looking at the API documentation.

I think you are looking for _.keyBy (or _.indexBy in older versions)

_.keyBy(data, 'rel');

I see a lot of good answers already. I would just like to add one more answer to the list using Ramda's indexBy.

const data = [{
    id: 1,
    foo: 'bar'
  },
  {
    id: 2,
    baz: 'lorem'
  }
];

const dataById = R.indexBy(R.prop('id'), data);
console.log(dataById)
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.25.0/ramda.min.js"></script>

I hope it helps someone else :)


Three Numbers in Java Given three positive numbers A, B, and C. Find the number of positive
  integers less than D that are divisible by either of A, B or C.

  Input format

  The 1st argument given is an Integer A. The 2nd argument given is an
  Integer B. The 3rd argument given is an Integer C. The 4th argument
  given is an Integer D.

  Output Format

  Return an Integer X, the number of positive integers that are
  divisible by either of A, B, or C.

  Constraints

  1 <= A, B, C, D <= 1e9

  For Example

  Input:

  A = 2

  B = 3

  C = 4

  D = 10

  Output:

  6

  Explanation:

  positive numbers less than D that are divisible by either of A, B or C are    2, 3, 4, 6, 8, 9

My approach:

import java.math.BigInteger;

public class Solution {
    public int solve(int A, int B, int C, int D) {
        BigInteger numDivA = BigInteger.valueOf((D - 1)/A);

        BigInteger numDivB = BigInteger.valueOf((D - 1)/B);

        BigInteger numDivC = BigInteger.valueOf((D - 1)/C);

        BigInteger newA = BigInteger.valueOf(A);

        BigInteger newB = BigInteger.valueOf(B);

        BigInteger newC = BigInteger.valueOf(C);

        BigInteger newD = BigInteger.valueOf(D);

        BigInteger limit = new BigInteger("1000000000");

        BigInteger lcmAB = (newA.divide(hcf(newA, newB))).multiply(newB);

        BigInteger lcmAC = (newC.divide(hcf(newA, newC))).multiply(newA);

        BigInteger lcmBC = (newB.divide(hcf(newB, newC))).multiply(newC);

        BigInteger lcmABC = lcmAB.divide(hcf(lcmAB,newC)).multiply(newC);

        BigInteger numDivAB = newD.subtract(BigInteger.ONE).divide(lcmAB);

        BigInteger numDivBC = newD.subtract(BigInteger.ONE).divide(lcmBC);

        BigInteger numDivAC = newD.subtract(BigInteger.ONE).divide(lcmAC);

        BigInteger numDivABC = newD.subtract(BigInteger.ONE).divide(lcmABC);

        BigInteger numTotal = (((((numDivA.add(numDivB)).add(numDivC)).subtract(numDivAB)).subtract(numDivBC)).subtract(numDivAC)).add(numDivABC);

        return (numTotal.mod(limit)).intValue();
    }

    private BigInteger hcf (BigInteger a, BigInteger b) {

        BigInteger hcf = a.gcd(b);

        return hcf;
    }

}

I have the following questions with regards to the above code:

How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?
Have I gone too overboard by using BigInteger?

Reference

1e9 is only 1 billion, which will fit into a standard integer range of 2 billion some.

The hcf function is unexpected, because it's just a wrapper for BigInteger. I think just using the built in GCD function would be better than making your own method that calls a standard function. If it's critical to the algorithm understanding that we think of a highest common factor instead of a greatest common denominator, then keep the function. If you do keep it, though, use the full name instead of an abbreviation i.e. private BigInteger highestCommonFactor.

I looked at your code and expected to see a loop. I'm assuming you've worked out the math to do this without loops, which is good and probably more efficient. But, I don't really know how this would work, and would be worried someone else looking at the code would have the same problem. A code comment indicating what mathematical principles, or even the name of a theorem, would help immensely.

Using BigInteger would increase the complexity of the program you can do it simpily.


Finding all integers in an array with odd occurrence I am doing an interview exercise problem from here.

The problem is to find "all numbers that occurred an odd-number of times in an array".

Here is my high level psuedo code thinking:

Construct a map that will map integers to their frequencies.
Iterate through the array, use the map to record the frequency count.
Iterate through all the keys in the map and add the keys that have an odd value to another collection.
Convert that collection to an array and return it to the user.

Here is the my implementation of this high level psuedo code in Java:

public static int[] allOdd(int[] array) {
    Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
    for(int c=0;c<array.length;c++) {
        if(hm.containsKey(array[c])) {
            hm.put(array[c], hm.get(array[c]) + 1);
        } else {
            hm.put(array[c], 1);
        }
    }
    List<Integer> allOdds = new ArrayList<Integer>();
    for(int key: hm.keySet()) {
        if(hm.get(key) % 2 == 1) {
            allOdds.add(key);
        }
    }
    int[] allOs = new int[allOdds.size()];
    for(int c=0;c<allOdds.size();c ++){
        allOs[c] = allOdds.get(c);
    }
    return allOs;
}

I tested this for two of my test cases and in both test cases ( {2,3,2,4,4,4,6,8,8} and {90,91,91,93,93,93,95,98,98,97} ), this function produced the right results([3, 4, 6] and [97, 93, 95, 90] respectively).

Is there anything I can do to improve the time and space complexity of this method. One of the worries I had was that I created too many collections (too much space) But to me each collection had its own purpose. The map was to map values to frequencies. The ArrayList was a dynamic structure to hold the odd occurrences. You needed to initialize the last array because ArrayList is a collection that holds objects so you need to manually iterate through the ArrayList and store those ints (Auto box) in the new array. To Array

Is there anything you can point out that can improve time and space efficiency in this function?

You don't really need to keep track of how many times you've seen each integer, only whether you've seen it an odd number of times. So start with your data structure (map, hash table, dictionary, whatever) being empty, which correctly reflects the state that you have seen no numbers an odd number of times. Now for each number x in the array, if x is in the map then remove it (now you've seen it an even number of times) otherwise add it.

import java.util.HashSet;

public class OddOccurence {

public static void main(String[] args) {

    int[] a = {1,1,1,2,2,3,3,4,4,4,5,6,6,6,6,7,7,8,8,8,3,8,8};
    int i=0;
    int j=0;

    HashSet<String> result = new HashSet<String>();

    System.out.println(a[i] );
    for( i = 0 ; i<a.length; i++){
        int counter = 0;
        for( j = 0; j<a.length; j++){
            if(a[i]==a[j])
                counter++;
        }
        if(counter%2 != 0)
            result.add(Integer.toString(a[i]));
    }

    System.out.println(result);

}

}


Open closed principle in a method I have an ASP.NET MVC project wherein I need to follow the open closed principles.

The project converts a .csv file to a model from a database, but in the future we might also have to convert Excel files to the same model from the database.

Now, I have this code in the Convertor class:

public class Convertor
{
    private static ICompanyRepository companyRepository;

    /// <summary>
    /// converts the uploaded csv data to Company model
    /// </summary>
    /// <param name="filePath">the csv data</param>
    /// <returns>a list of Compamy model</returns>
    public List<Company> ConvertCsvToCompanyModel(string filePath)
    {
        companyRepository = new CompanyRepository(new ImportContext());
        List<Company> companies = new List<Company>();

        //Read the contents of CSV file.
        string csvData = System.IO.File.ReadAllText(filePath);

        //we skip the first row, because it contain the header
        var csvLines = csvData.Split('\n').Skip(1);

        //Execute a loop over the rows.
        foreach (string row in csvLines)
        {
            if (!string.IsNullOrEmpty(row))
            {
                if (!companyRepository.CompanyExist(row.Split(',')[0]))//check if already contains the ExternalId
                {
                    companies.Add(new Company
                    {
                        //CounterPartId
                        ExternalId = row.Split(',')[0],
                        //Name
                        TradingName = row.Split(',')[1],
                        //IsBuyer
                        IsForwarder = Convert.ToBoolean(Enum.Parse(typeof(BooleanAliases), row.Split(',')[2])),
                        //IsSeller
                        IsCarrier = Convert.ToBoolean(Enum.Parse(typeof(BooleanAliases), row.Split(',')[3])),
                        //Phone
                        Phone = row.Split(',')[4],
                        //Fax
                        Fax = row.Split(',')[5]
                    });
                }
            }
        }
        return companies;
    }
}

Can you please give me some hints how to change this code in order to follow the open closed principle? In the future, as I mentioned, it is possible to need a converter for Excel files, too.

Before reviewing micro-design we may focus on overall architecture. You already know that in future you will also need to read an Excel file, it may be a good moment to introduce an abstract base class (or an interface) to abstract this detail from the client:

public abstract class Convertor
{
    public abstract IEnumerable<Company> ToCompanyModel(string path);
}

Note few changes:

I'm using Convertor as base class name then you will have, for example, CsvConvertor, no need to repeat any of those information in the method name.
I'm returning IEnumerable<Company> instead of List<Company>. The effective type you're using to store the result is an implementation detail, here I picked the most generic one but you may return IList<Company> as well (what if, for example, you will decide to store Company as an hash-table to detect duplicates?)

How to create the right Convertor instance? I assume you have DI in-place then you may have a factory class which will create the right instance according to file extension (assuming you're sure you will need Excel files). Something similar to:

public interface IConvertorFactory
{
    Convertor Create(string path);
}

If not then simply use DI to get the converter instance without any factory. You now have another problem: testing. Do you want to unit test your converter using physical files? Of course you need to but it's also handy to work with in-memory representations then you may add an overload with StreamReader:

public abstract class Convertor
{
    public abstract IEnumerable<Company> ToCompanyModel(string path);
    public abstract IEnumerable<Company> ToCompanyModel(StreamReader stream);
}

Default implementation may simply open the stream reading line-by-line and you won't need to worry about file size because it won't read everything in memory. Another benefit is that you can check for reader logic without mixing with I/O logic (and this is good to write extensive testing).

ICompanyRepository companyRepository has no reason to be static, you just make your class not thread-safe without any other benefit.

You're not doing any error handling. Things may go wrong and caller will get unknown exception. You'd better handle possible errors and return a single well-known exception (let's say InvalidDataException) with all the required details. Do not forget to document exceptions you may throw. You may even decide to ignore errors in one row and continue processing.

You're splitting each line with row.Split() multiple times, it's a waste: do it once.

To reduce nesting you can use continue and filters (example, again, without error handling):

foreach (string row in csvLines.Where(x => !String.IsNullOrEmpty(x))
{
    var fields = row.Split(',');

    var externalId = fields[0];

    if (companyRepository.CompanyExist(externalId))
        continue;

    // ...
}

However the truth is that you do not need to do CSV parsing by hand. In Microsoft.VisualBasic assembly (if you do not want to use an external library) you already have a well-tested and complete implementation:

using (var parser = new TextFieldParser(new StringReader(stream)))
{
    parser.SetDelimiters(new string[] { "," });

    // Skip header
    parser.ReadLine();

    while (!parser.EndOfData)
    {
        var fields = parser.ReadFields();

        // Same as before
    }

Note that you can catch MalformedLineException to handle errors and you can specify exactly the expected type of each field (if you want to). Also text fields may be enclosed in quotes, use TextFieldParser.HasFieldsEnclosedInQuotes property to instruct the parser. Blank lines are, by default, skipped and you may even use comments (see TextFieldParser.CommentTokens property).

Very last note: if CSV file is generated by Excel then be aware that it won't always use the comma as delimiter but the current list separator character (see CultureInfo.TextInfo.ListSeparator).

When you actually need the Excel feature, you'll know exactly what you need. Right now, you will only guess and do it wrong.

This might means 2 things:

You'll have to change it in the future, because it wasn't like you guessed.
Eventually, you won't need that feature and have made it complex unnecesarily.