Submitting callable tasks to a variable number of Threads in a ThreadPool I am getting into multithreading and I was wondering if the code below is good practice or not. This is one of my first tries at multithreading.

Is there a better way of getting the values from the Future<Integer> rather than saving them in a list and summing them up afterwards?

 // Counting the number of prime-numbers from 'from' to 'to' by using 'nrThreas' amount of threads.
public static int countParallel(final int from, final int to, final int nrThreads) throws ExecutionException, InterruptedException {

    int count = 0;
    int startFrom = 0;
    int numbersPerThread = (to - from)/nrThreads;

    ExecutorService threadPool = Executors.newFixedThreadPool(nrThreads);

    Future<Integer> countHelper = null;

    // Storing the futures in order to get the Integers after the tasks were submitted to its threads
    ArrayList<Future<Integer>> helperList = new ArrayList<>();

    // determining the amount if prime-numbers between 1 and 20.000.000.
    for(int i = 0; i < nrThreads; i++)
    {
        countHelper = threadPool.submit(new PrimeCounter(startFrom, startFrom + numbersPerThread));

        // gets the next chunk to be examined
        startFrom += numbersPerThread + 1;

        helperList.add(countHelper);

    }

    threadPool.shutdown();

    // summing up the helper.get() from the list
    for(Future<Integer> helper : helperList)
    {
        count += helper.get();
    }

    return count;
}

General concerns

Unrelated to multi-threading: you might want to think about fence post errors -- consider:

Assert.assertEquals(countParallel(8,10,2), countParallel(8,10,1));

Is it obvious that the code you've provided will pass this test?

Also, if a variable is only used within a given scope, it's a good idea to declare that variable within the scope....

for(int i = 0; i < nrThreads; i++)
{
    Future<Integer> countHelper = threadPool.submit(new PrimeCounter(startFrom, startFrom + numbersPerThread));

    // gets the next chunk to be examined
    startFrom += numbersPerThread + 1;

    helperList.add(countHelper);

}

... and within a scope, to declare the variable as close as possible to its first use:

int count = 0;
for(Future<Integer> helper : helperList)
{
    count += helper.get();
}

I find that doing this also reveals refactorings -- for example, collapsing the outputs of all the jobs into a single number is a single idea

int sum(List<Future<Integer>> resultList) {
    int count = 0;
    for(Future<Integer> helper : helperList)
    {
        count += helper.get();
    }
    return count;
}

Multi-Threading

The good: you created an ExecutorService, rather than creating your own threads.  10 out of 10.

The meh: you've completely punted on cancellation.  What should be be done to the jobs that are running if an InterruptedException is thrown?  For toy problems, where you aren't supporting the ability to cancel work in progress, that's fine.  Put it on the list of things to pick up later.

You're also being, perhaps, a little bit timid about dividing up the work.  An alternative to giving each thread it's own pile of work, is to provide lots of slices of work, and let the Executor service decide which thread gets to do what.  There's nothing wrong with submitting 7 jobs to an ExecutorService with 6 threads; for that matter, it could be 70 jobs.  Or 700 jobs.

The situation you would like to avoid is one where most of your threads are idle (because there is no more work available), but one thread is taking a long time because he got all of the hard parts of the problem.

So it might be better to distribute the work more fairly -- tell each PrimeCounter that you are solving the range [1,20.000.000], but the prime counters process every nTh entry in the list (ex: one PrimeCounter checks 0,6,12..., and the next PrimeCounter checks 1,7,13..., and the last one checks 5,11,17....).

  Is there a better way of getting the values from the Future rather than saving them in a list and summing them up afterwards?

I think the answer here is: it depends.  One of the good things you've done here is ensure that values are only written by one thread; this makes lots of things easier to reason about (compared with, for instance, trying to have each PrimeCounter add values to a common accumulator).

Here, where you are using the results so close to the place that you start the jobs, it might be easier to store the intermediate results in the Runnable, wait for all the threads to finish, and then iterate the Runnables to sum up the total.  You could use ExecutorService.awaitTermination to know when the jobs have finished running, or set them up to each signal their results via a CountDownLatch, or ....

I would be more inclined to use a Future if the consumption of the result was "further away" from the calculation; like on the other side of an abstraction layer.


DbSet IncludeAll method The Problem

As an ASP.NET MVC4 developper, I'm using Entity Framework a lot. Considering performance I often use lazy loading for my models.

public class Result {
    public int Id { get; set; }
    public decimal Grade { get; set; }
    public virtual Skill Skill { get; set; }
    public int SkillId { get; set; }
    public virtual Player Player { get; set; }
    public int PlayerId { get; set; }
    public virtual Category { get; set; }
    public int CategoryId { get; set; }
}

If I want to include all navigation models I'll have to include all those models.

public ActionResult Details(int id = 0)
{
    Result result = db.Results
                      .Include(r => r.Skill)
                      .Include(r => r.Player)
                      .Include(r => r.Category)
                      .SingleOrDefault(r => r.Id == id);
    //some viewmodel mapping
    return View(viewmodel);
}

My solution

I built an extension method to remove this from my controller code.

public static class IncludeExtensions
{
    public static IQueryable<Result> IncludeAll(this IQueryable<Result> results)
    {
        return results.Include(r => r.Skill)
                      .Include(r => r.Player)
                      .Include(r => r.Category);
    }

    public static Result IncludedFind(this IQueryable<Result> results, int id)
    {
        return results.IncludeAll().SingleOrDefault(r => r.Id == id);
    }
}

public ActionResult Details(int id = 0)
{
    Result result = db.Results.IncludedFind(id);
    //some viewmodel mapping
    return View(viewmodel);
}

There are a few problems with this:

I can't create an abstract extension class to force IncludeAll() and IncludedFind() method.
I still have to update the extension method if my models change.
I'll have a proliferation of extension methods/classes.
Isn't there an IncludeAll() like method available for Entity Framework?

Is there something like this on NuGet?

It just feels wrong...

A simple option would be to use reflection to check for properties that are virtual and has the Id-suffix. This is where I came up with, working for me;

public static IQueryable<T> IncludeAll<T>(this IQueryable<T> queryable) where T : class
{
   var type = typeof (T);
   var properties = type.GetProperties();
   foreach (var property in properties)
   {
       var isVirtual = property.GetGetMethod().IsVirtual;
       if (isVirtual && properties.FirstOrDefault(c => c.Name == property.Name + "Id") != null)
       {
           queryable = queryable.Include(property.Name);
       }
   }
   return queryable;
}

I hope this answers your question.


Java Single LinkedList I am a CS student and I was wondering is this code looks clean. I tested it and it passed every tested but I think the delete(Node node) is a bit long, I did not find a way to reduce it

Node class

public class Node {
      private int data;
      private Node next;
      Node(int data){
        this.data = data;
      }

      public int getValue(){
        return this.data;
      }

      public void setNext(Node next){
        this.next = next;
      }

      public Node nextNode(){
        return this.next;
      }
    }

LinkedList class

public class LinkedList {
  Node head;
  Node tail;
  int size = 0;

  public void add(Node node){
    if(tail == null && head == null){
      tail = node;
      head = node;

    } else{
      tail.setNext(node);
      tail = tail.nextNode();
    }
    size ++;
  }

  public int getSize(){
    return this.size;
  }
  public int getTail(){
    if(tail == null){
      return -1;
    } else {
      return tail.getValue();
    }
  }

  public void delete(Node node){
    if(isPresent(node)){
      if(size == 1){
        this.tail = null;
        this.head = null;
        size = 0;
      }
      else if(node == head){
        head = head.nextNode();
        size --;
      }

      else if(node == tail){
        Node iterator = head;
        while(iterator.nextNode().nextNode() != tail){
          iterator = iterator.nextNode();
        }
        tail = iterator.nextNode();
        iterator.nextNode().setNext(null);
        size --;
      }

      else{
        Node iterator = head;
        while(iterator.nextNode() != node){
          iterator = iterator.nextNode();
        }
        iterator.setNext(iterator.nextNode().nextNode());
        size --;
      }
    }
  }

  public int getHead(){
    if(head == null){
      return -1;
    } else {
      return head.getValue();
    }
  }

  public void printList(){
    Node iterator = head;

    while(iterator != null){
      System.out.println(iterator.getValue());
      iterator = iterator.nextNode();
    }
  }

  public boolean isPresent(Node node){
    if(head == null){
      return false;
    }

    else if(head.getValue() == node.getValue()){
      return true;
    }

    else {
      Node iterator = head;
      while(iterator != null){
        if(iterator.getValue() == node.getValue()){
          return true;
        }
        iterator = iterator.nextNode();
      }
      return false;
    }
  }
}

Indeed the cases for delete can be reduced.

  public void delete(Node node) {
    Node prior = null;
    Node current = head;
    while (current != node && current != null) {
      prior = current;
      current = current.next;
    }
    if (current != null) {
      if (prior == null) {
        head = current.next;
      } else {
        prior.next = current.next;
      }
      --size;
      if (current == tail) {
        tail = prior;
      }
    }
  }

In general one would keep Node an internal non-public class, for instance one would not
like people to play with the next field. Hence I would propose:

  public void delete(int value) {
    Node prior = null;
    Node current = head;
    while (current != null && current.value != value) {
      prior = current;
      current = current.next;
    }
    if (current != null) {
      if (prior == null) {
        head = current.next;
      } else {
        prior.next = current.next;
      }
      --size;
      if (current == tail) {
        tail = prior;
      }
    }
  }

For the rest:

A tab of 4 spaces is still my favorite, probably still mainstream.
iterator is an unlucky naming, as there exist an Iterator in java, with a collection method iterator(). I used current.

And (as goodie) what about System.out.println(list);:

@Override
public String toString() {
    StringBuilder sb = new StringBuilder("[");
    Node current = head;
    while (current != null) {
      if (sb.length() >= 1) {
          sb.append(", ");
      }
      sb.append(current.value);
      current = current.next;
    }
    sb.append("]");
    return sb.toString();
}


Joining collections... because it's fun I'm working on a LinqEnumerable class (reviewable here), and I'm no Big-O expert and I'm pretty bad with algorithms, so I wonder what the complexity is for what I've implemented here, and whether it could be improved.

Join

Correlates the elements of two sequences based on matching keys.

Private encapsulated As New Collection
Option Explicit

Public Function Join(ByVal inner As LinqEnumerable, _
                     ByVal outerKeySelector As Delegate, _
                     ByVal innerKeySelector As Delegate, _
                     ByVal resultSelector As Delegate) As LinqEnumerable

    Dim result As New LinqEnumerable

    Dim outerValue As Variant
    Dim outerKey As Variant

    Dim innerValue As Variant
    Dim innerKey As Variant

    Dim innerList As System.List
    Set innerList = inner.ToList

    For Each outerValue In encapsulated
        outerKey = outerKeySelector.Execute(outerValue)

        For Each innerValue In innerList
            innerKey = innerKeySelector.Execute(innerValue)
            If outerKey = innerKey Then
                result.Add resultSelector.Execute(outerValue, innerValue)
                innerList.Remove innerValue
            End If
        Next
    Next

    Set Join = result

End Function

I've been told this might be \$O(log(n))\$, but since innerList.Remove is \$O(n)\$ I'm not sure. Could it be?

The complexity here is much more than \$O(\log{n})\$. Let's go though it...

There's one \$O(o)\$ loop, where \$o\$ is the size of the outer List.

Now, for each outer loop, we then loop through all the members of innerList. If that has size \$i\$, the combined complexity is now \$O(o \times i)\$.

Inside that inner loop you then remove members of the innerList. The remove operation is horribly expensive too. First, it starts at the beginning of the list, and searches for the item to remove. When it finds it, it then goes through each remaining item in the list, and shuffles them forward one position, to 'remove' the item.

The resulting complexity that I can see here is.... \$O(o \times i^2)\$ which means, if the inner and outer data sets are about the same size (worst case), you have complexity of \$O(n^3)\$ where \$n\$ is the size of each list.

Now, that is tempered somewhat by the fact that you only do the inner remove if it actually matches something, and when it does, it makes the inner data list smaller. I don't believe this affects the complexity all that much though.

If you are looking for performance improvements, there are a few I can see.

First up, convert all the inner-member values to the key outside the outer loop and store them in a dictionary:

Dim innerKeyDict As Scripting.Dictionary
....

For Each innerValue In innerList
    innerKey = innerKeySelector.Execute(innerValue)
    innerKeyDict.Add innerKey, innerValue
Next

Then, this will save you having to recalculate the keys many times, and it also converts the lookup, and remove both to O(1) operations.

I believe, if you do this you end up with a \$O(n)\$ operation where \$n\$ is the combined size of inner and outer.


Zombie killers ranking Code Review has a Zombie Problem and, in comparison to The Walking Dead TV Show, our survival doesn't depend on killing them all day every day.

As a potential solution, I though it would be interesting to setup a friendly zombie killing competition (this wasn't talked about in meta yet), but in order for this to work we need a way to rank our killers.

I've written the following Stack Exchange Data Explorer query, which has the following requirements.

Questions must :

Not be closed/deleted/community owned
Be at least one month older than the competition's start date
Not have answers with a score greater than one preceding the competition's start date

And in order for the zombie to be killed, the questions targeted by the above requirements must have an answer with a score of 1 or more that follows the beginning of the competition's date.

I then group the answers per user, show their "kill count" and order by this value, in descending order.

The query in question

declare @startDate date;
set @startDate = CONVERT(datetime, '2019-07-21');

select top(25) u.DisplayName, count(*)
from   Posts q
       inner join Posts a on q.Id = a.ParentId
       inner join Users u on a.OwnerUserId = u.Id
where  q.PostTypeId = 1
       -- Target old questions with new answers
       and datediff(month, q.CreationDate, @startDate) > 1
       and a.Score > 0
       and a.CreationDate > @startDate
       and not exists (select Id from Posts where ParentId = q.Id and CreationDate < @startDate and Score > 0)
       -- Remove low quality/closed/deleted/community owned questions
       and q.Score >= 0
       and q.ClosedDate is null and q.CommunityOwnedDate is null and q.DeletionDate is null
group by u.Id, u.DisplayName
order by count(*) desc

I don't have a database schema in hand, but there are two table concerned :

Posts : Where we have questions and answers. The answers have a ParentId that is a question. A post has an owner (OwnerUserId) with an associated User. I think the rest of the columns names are pretty self explanatory, but I can add details if necessary.

I've tested the query and, to the best of my knowledge, it works. I'm not very used to SEDE so there might be things I missed, which I'd like to learn.

I'd also like to know if there are performance pitfalls in my query I should be aware of or best practices that I'm missing.

The query itself.

As a heads up - we have very different formatting styles for our code. Feel free to ignore that difference and don't consider it a comment on your style (unless you prefer mine, in which case please do).

Aliases
I really dislike the practice of using short aliases for tables. I've never seen a point, and it always makes it harder for me to understand. You can get easy aliases (e.g. q -> questions or a -> answers) for very few characters.
I also really like when each column of my output has an actual name, so its easier to understand. In this case, I would alias COUNT(*) as [Zombie Kill Count] or something.
Also, you can use the alias in your ORDER BY, which I find conceptually easier to understand.

Performance
One thing that jumps out at me is that you're using a function in your WHERE clause. This can cause the cardinality estimator to get really confused (I don't know if SEDE still uses the legacy cardinality estimator; if they do, then this problem is magnified) and you can end up with some less-than-ideal query plans. One way to avoid this is to not include your column in the function. For example, instead of this:
SELECT *
  FROM Posts
  WHERE DATEDIFF( MONTH, CreationDate, @startDate ) > 1;

You could do this
SELECT *
  FROM Posts
  WHERE CreationDate < DATEADD( MONTH, -1, @startDate );

This lets the cardinality estimator use the available statistics on the CreationDate column without confusing it with the function.
If you're grouping by a value that doesn't actually add a new level of granularity (Users.DisplayName doesn't actually change the grouping) it can be more efficient to use an aggregate there; you get the same result, but a cheaper sort.
SELECT MAX( u.DisplayName ) -- I'm cheaper than grouping on me

Playing around with the APPLY operator can be fun as well; I've often seen it perform better than a NOT EXISTS, like so (with a GoodAnswers.Id IS NULL in the WHERE clause to get an exclusive outer apply). Note - this one wasn't tested, so YMMV. APPLY can be pretty situational, but I always have fun writing them.
OUTER APPLY ( SELECT TOP( 1 ) Id
                FROM Posts OldAnswers
                WHERE OldAnswers.ParentId = Questions.Id
                  AND OldAnswers.CreationDate < @startDate
                  AND OldAnswers.Score > 0
                ORDER BY ( SELECT NULL ) ) GoodAnswers

Overall, I came up with something like this.
DECLARE @startDate date;
SET @startDate = CONVERT( datetime, '2019-07-21' );

SELECT TOP ( 25 )
       MAX( Answerers.DisplayName ) [Answerer Name],
       COUNT( * ) [Zombie Kill Count]
  FROM Posts Questions
    INNER JOIN Posts Answers
      ON Questions.Id = Answers.ParentId
    INNER JOIN Users Answerers
      ON Answers.OwnerUserId = Answerers.Id
    OUTER APPLY ( SELECT TOP ( 1 )
                         Id
                    FROM Posts OldAnswers
                    WHERE OldAnswers.ParentId = Questions.Id
                      AND OldAnswers.CreationDate < @startDate
                      AND OldAnswers.Score > 0
                    ORDER BY ( SELECT NULL )) GoodAnswers
  WHERE Questions.PostTypeId = 1
    -- Target old questions with new answers
    AND Questions.CreationDate < DATEADD( MONTH, -1, @startDate )
    AND Answers.Score > 0
    AND Answers.CreationDate > @startDate
    -- That didn't already have a good answer
    AND GoodAnswers.Id IS NULL
    -- Remove low quality/closed/deleted/community owned questions
    AND Questions.Score >= 0
    AND Questions.ClosedDate IS NULL
    AND Questions.CommunityOwnedDate IS NULL
    AND Questions.DeletionDate IS NULL
  GROUP BY Answerers.Id
  ORDER BY [Zombie Kill Count] DESC;

Some extra notes:

Unfortunately, I had a hard time finding information on the available
indices on SEDE. The best resource I found was this post. It
doesn't list any indices on the Posts table, although we do have
one on Users.Id. As such there aren't any great suggestions I have
for joins here; you're probably doing about as well as you can.
You have a pretty lengthy WHERE clause going on; that'll likely dilute the cardinality even further, but I don't see a reasonable
alternative.


Matrix transpose algorithm If I have a List<List<T> like the following :

Name    City   Id
Anna     NY     1
Joe      NJ     2

How can I transpose it efficiently in order to have :

Name    Anna     Joe
City    NY       NJ
Id      1        2

I tried the following

public static void MatrixTranspose<T>(ref List<List<T>> matrix)
{
   var h = matrix.Count - 2;
   var w = matrix[0].Count - 1;

   for (var i = 0; i < h; ++i)
   {
      for (var j = i + 1; j < w; ++j)
      {
          var tmp = matrix[i][j];
          matrix[i][j] = matrix[j][i];
          matrix[j][i] = tmp;
       }
   }
}

That seems to be working on paper I believe? But I feel like I'm doing too much permutations. Is there a way to optimize it? Also, is the use of ref correct here?

is the use of ref correct here?

Taken from MSDN: ref (C# Reference)

  The ref keyword causes an argument to be passed by reference, not by value. The effect of passing by reference is that any change to the parameter in the called method is reflected in the calling method. For example, if the caller passes a local variable expression or an array element access expression, and the called method replaces the object to which the ref parameter refers, then the caller’s local variable or the array element now refer to the new object.

The point of ref is to pass a value type (struct) to a method as if it was reference type (class). List<T> is a class, so there's no need to add refin this scenario as it's just acting as another level of redirection. Think of it as being a pointer to a pointer.

The problem with using List<List<T> is that the size of the nested lists could differ from the top-level list and this wouldn't be a matrix. I'd recommend that you use something with a guaranteed rectangular structure, such as T[,]. i.e:

public static void MatrixTranspose<T>(ref T[,] matrix)
{
    int columns = matrix.GetLength(0);
    int rows = matrix.GetLength(1);
    T[,] transposed = new T[rows, columns];
    for (int row = 0; row < rows; row++)
    {
        for (int column = 0; column < columns; column++)
        {
            transposed[row, column] = matrix[column, row];
        }
    }

    // Reassign matrix so that it gets picked up by ref.
    matrix = transposed;
}


Custom indexOf for strings javascript with regex I was wondering how efficient my code is creating custom indexOf for strings in JavaScript using regex instead of looping with a for statement the whole way in most solution I find and I believe this got \$O(1)\$ since no loop is needed.

The idea is to use regex that put either the key or any list of word that is not key; this way I know that the value will be either in arr[0] or arr[1].  I also check using regex earlier whether the key exist in the value or not; this way I created non-looping indexOf with regex. This way I just return 0 if the key is in arr[0] or arr[0].length if it not in arr[0].

function findindex(value,key){
  let regex = RegExp( "((?!"+key+").)+|"+key , "ig" ); //regex for separating keys in the array
  let regex2 = RegExp(key,"ig");  // regex for checking if the key is exist in the value or not

  //first check before looping whether key is available in array or not
  if( !regex2.test(value) || value.length < key.length ){
    return -1;
  }

  let arr  = value.match(regex); //make an array

  //alternative with condition statement
  return ( arr[0] === key || regex2.test(arr[0]) ) ? 0 : arr[0].length;
}

Too sad, it's not O(1).
There is a cost for:

Constructing the regex into a DFA
Calling test() or match() on the regex for the value

Complexities:

A well implemented regex construction will be O(M) where M is the length of the key.
While test/matching it afterwards will be O(N) where N is the length of the value. (best case, e.g. regexes with backtracking can result in horrible complexities)

So a couple of improvements can be:

if the key is always the same. Construct the regex for the key only once.
first start with comparing the length of the value and key before calling the more expensive test()-match() methods.
apart from that, the idea of a regex is ok but I don't know if it's the most understandable way of writing an indexOf.
Reference: Regex Complexities on SO


Reading, processing and counting an array setting limits Last weekend my teacher asked me to create code to solve a problem:

  Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. They follow N numbers, the actual elements of the array.

    Three brothers are going to work in the shop of their father for a time. The shop is doing well and every day generates profit which the three brothers may provide. The brothers agreed that they would divide the total time in three successive parts, not necessarily equal duration, and that each one will be working in the shop during one of these parts and collects the corresponding profit on his behalf. But they want to make a deal fairly, so that one received from three more profit someone else. Specifically, they want to minimize the profit the most favored of the three will receive.

  Now assume that we have the following array elements:

5 6 1 4 9 3 1 2

  The procedure we should make appears in the following diagram:

  We want every time to keep the lowest value of weight and in the end to generate a result.

I created the code and it works for all inputs. Is there any way to reduce the complexity from \$\mathcal{O}(n^3)\$ to  \$\mathcal{O}(N)\$ if we can keep in mind that this isn't tidied up and probably needs to be.

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

int sum_array(int* array, int cnt)
{
    int res = 0;
    int i;
    for ( i = 0; i < cnt ; ++i)
        res += array[i];
    return res;
}

int main()
{
    FILE* input = fopen("share.in","r");

    int N = 0;
    fscanf(input,"%d",&N);

    int *array = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++)
        fscanf(input,"%d",&array[i]);

    fclose(input);

    int Min = 0;
    int bestA = 0, bestB = 0, bestMin = INT_MAX;
    int A, B;
    int i;
    for ( A = 0; A < N - 2; ++A)
    {
        for ( B = A + 1; B < N - 1; ++B)
        {
            int ProfitA = sum_array(array, A + 1);
            int ProfitB = sum_array(array + A + 1, B - A );
            int ProfitC = sum_array(array + B + 1, N - 1 - B );

            //here the values are "current" - valid
            Min = (ProfitA > ProfitB) ? ProfitA : ProfitB;
            Min = (ProfitC > Min) ? ProfitC : Min;

            if( Min < bestMin )
                bestA = A, bestB = B, bestMin = Min;

        }
    }
    printf("%d\n", bestMin);
    free(array);
    return 0;
}

Here are some things that may help you improve your code.

Eliminate unused variables

Within main, the variables i, BestA and BestB are declared and some of them set, but they are otherwise unused.  They should be omitted from the program.

Don't abuse the comma operator

This line doesn't really need a comma operator:

bestA = A, bestB = B, bestMin = Min;

It should instead be three separate statements, or (if you follow the previous advice) reduced to a single one involving bestMin.

Don't cast the return from malloc

The return value from malloc or calloc is a void * and does not need an explicit cast.  See this question for a thorough discussion of the reasons not to, but for me the most compelling reason is that it's simply not needed.

Use const where practical

In your sum_array routine, the values in the array are never altered, which is just as it should be.  You should indicate that fact by declaring it like this:

int sum_array(const int* array, int cnt)

Use pointers rather than indexing for speed

Pointers are generally a faster way to access elements than using index variables.  Speed may not a particular goal in this program but it's useful to know anyway.  For example, your sum_array routine could be written like this:

int sum_array(const int* array, int cnt)
{
    int res;
    for ( res = 0; cnt; --cnt)
        res += *array++;
    return res;
}

Check return values for errors

The calls fopen, fscanf and malloc can each fail.  You must check the return values to make sure they haven't or your program may crash (or worse) when given malformed input or due to low system resources.  Rigorous error handling is the difference between mostly working versus bug-free software.  You should strive for the latter.

Consider separating I/O from the algorithm

The I/O is done first, and then the input values are processed to find the answer.  Consider separating those into to separate functions which would both make your program cleaner and also allow for better automated testing (such as automatically generating random values and then checking that the algorithm does the right things).

Reconsider your algorithm

Right now, the sums are recalculated many times, but this isn't strictly necessary. As you iterate through the combinations, the partitioning only moves by one value.  So what you could do instead would be to keep the three sums ProfitA, ProfitB and ProfitC and then just add and subtract the particular value that moves from one brother to another.

I've done some reading and it appears to me that the best you can do for complexity is \$\mathcal{O}(N^3)\$
See this question and the many links from it to explain that.

Think about negative numbers

While the problem states that the shop generates profit each day, it doesn't necesarily mean that every time period is profitable.  This suggests that some of the time periods could be associated with negative numbers.  If we use this input:

8
-5 6 1 4 -9 3 1 2

the program reports a max value of 1, which is correct, but you should verify that it is correct for any possible set of numbers.

Consider adding an "early bailout"

If it ever occurs that ProfitA == ProfitB == ProfitC (as with the values in the previous point) this must be the answer (do you see why?) so the program could exit early with that correct answer.

Eliminate return 0

You don't need to explicitly provide a return 0; at the end of main -- it's created implicitly by the compiler.


Ensuring client IDs are unique I'm writing a node.js application that involves handling clients based on their ID without any real way of confirming that the ID a client says it has is its actual ID. That is, it's possible for a client to tell the server it has an ID of foo even though it was assigned an ID of bar, thus being able to send and receive information from the server as though it was the existing client foo. This is obviously a significant security risk, so I want to ensure it's more or less effectively impossible to guess another client's ID.

I have a clients object, with keys corresponding to the ID of each client. I'm using the crypto library for PRNG and hashing; hashFct returns a SHA256 digest of the input. The following code is run when a client sends its initial creation request.

//Generate random string, hash, and truncate to 8 characters
rand = crypto.randomBytes(32).toString("base64");
id = hashFct(rand).substr(0, 8);

//Loop until unique
for(var i = 0; !!clients[id]; i++) {
    rand = crypto.randomBytes(32).toString("base64");
    id = hashFct(rand).substr(0, 8);
}

...

clients[id] = {
    id: id,
    ...
}

The idea behind the "loop until unique" section is to check if the clients object already has a value in it with the pseudo-random id as a key, and to regenerate the ID and try again until it's unique. Then the ID is put into the clients object as a new client, and the code moves on.

Is there anything glaringly stupid about this approach that I'm overlooking? Is there a better way to ensure an ID is unique, or perhaps a better way of generating the IDs?

rand = crypto.randomBytes(32).toString("base64");
id = hashFct(rand).substr(0, 8);

If those random bytes are random, passing them through a hash function adds nothing. If they are only somewhat random, hash + truncation is better than just truncation. However, crypto.randomBytes are from a strong RNG, so you can use them as is.

The problem is that 8 bytes is not always unique. You solve it by looping until you get one that is unique. However an attacker could do the inverse: guess until it hits a real ID.

The probablity of guessing a particular ID is \$2^{-b}\$, where b is the number of bits in the random number. If you have n users in your database the probability is n times as high. With \$n = 2^m\$, the attacker needs only about \$2^{b-m}\$ guesses to hit some ID.

If your ID's are 8 bytes:

2^64 bit IDs (8 bytes)
2^20 users   (~1 million)
//
2^44 guesses (~17 million million)

However, if your IDs are 8 characters in base64:

2^48 bit IDs (8 base64 characters)
2^20 users   (~1 million)
//
2^28 guesses (~268 million)

Depending on your application and the number of users it is possible that both, the latter or neither is insecure.

My recommendation (echoing well known advice) is to use the 32-byte random string directly as an ID (converted to base64 if needed). That gives such a small chance of collisions that you can do away with the loop as well. (It's likelier e.g. that the CPU fails to loop due to cosmic rays than that you see a collision.)


Can this code, to convert string to integer, be made more compact? Problem:
String to integer(leetcode)

Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:

Only the space character ' ' is considered as a whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-2^31, 2^31-1]. If the numerical value is out of the range of representable values, (2^31-1) or -2^31 is returned.

My solution:
I have implemented this code below. I have noted down the requirements and implemented the code. It was hard to keep track of all the details. Before acceptance, I got WA 4 times(and it seems like the code I've written is not compact).
class Solution:
    def myAtoi(self, s: str) -> int:
            l = len(s)
            if l==0:
                print(1)
                return 0
            if l==1:
                if s==" " or s=="+" or s=="-":
                    return 0
                elif(s.isnumeric()):
                    return int(s)
                else:
                    return 0
            res = ""
            i = 0
            while(i<l and s[i]==" "):
                i+=1
                if i==l:
                    return 0
            ispos = False
            if(s[i]=="+"):
                ispos = True
                i+=1
            isnegative = False
            if(s[i]=='-' and not ispos):
                isnegative = True
                i+=1
            if(i<len(s) and not s[i].isnumeric() and s[i]!='+' and s[i]!='-'):
                return 0
            while(i<l):
                if s[i].isnumeric():
                    res += s[i]
                else:
                    break
                i+=1
            if len(res)>0:
                x = int(res)
            else:
                return 0
            if isnegative:
                if x>=(1<<31):
                    return -(1<<31)
                x *= -1
            if x>=((1<<31) - 1):
                return (1<<31)-1
            return x

Can anyone write a compact code for this problem?

I also like to know if there is an approach to solve this kind of implementation problems so that I can write compact code. Can anyone share any better method to analyze this type of implementation problem? (or, any suggestion to be better in solving this kind of problems where we need to keep track of many things)

Styling

Try to make the code follow the PEP 8 Style Guidelines, this will make your code follow the Python conventions, and also more readable. So do
if l == 1 instead of if l==1, my_atoi instead of myAtoi, etc

Code structure

It seems that page requires the code to be inside a class. Leaving the exercise aside for a moment:
You don't need that function inside a class, because you are never using anything of the class itself. It makes more sense to define that method outside the class, and without the (unused) self parameter.

Skiping whitespaces

while(i<l and s[i]==" "):
    i+=1
    if i==l:
        return 0

You don't need those parenthesis on the while in Python.
Your code might not detect some whitespace characters like \t (it seems the exercise accepts that though); use the method isspace().
Instead of checking i == l on every iteration (when it could only happen in the last one), check it once you are out of the loop. This allows us to remove the special treatment to empty strings: if s is empty, it won't enter the loop and i == l, so it will return 0.

while i < l and s[i].isspace():
    i += 1

if i == l:
    return 0

Sign

Your code to handle the sign is too complicated. Instead of keeping ispos and isnegative, you could just keep a factor that is either 1 or -1. So instead of

ispos = False
if(s[i]=="+"):
    ispos = True
    i+=1
isnegative = False
if(s[i]=='-' and not ispos):
    isnegative = True
    i+=1

you can do

factor = -1 if s[i] == '-' else 1
# Skip the sign character if necessary
if s[i] == '-' or s[i] == '+':
    i += 1

Reading the number

if(i<len(s) and not s[i].isnumeric() and s[i]!='+' and s[i]!='-'):
    return 0
while(i<l):
    if s[i].isnumeric():
        res += s[i]
    else:
        break
    i+=1

If we have already parsed the sign, why accept another sign again?
Be careful, isnumeric() accepts things like ½, which you probably don't want; use isdigit() instead.
EDIT: As noted in the comments, isdigit() will accept things like "¹". So it's probably better to just do s[i] in '0123456789'
It's good practice (and helps avoid unexpected bugs) to declare variables the closest possible to where they are used. You declare res = "" at the beginning of your function, but haven't used it until now.
The while and if can be condensed into a single, more compact loop:

res = ""
while i < l and s[i].isdigit():
    res += s[i]
    i += 1

# You can check if an string is empty doing this:
if not res:
    return 0

Arrived to this point, if the function hasn't returned, we know res contains a number. The way you handle the valid range, before applying the sign, is not very intuitive; it's better if you first apply the sign.

x = factor * int(res)
if x > (1 << 31):
    return (1<<31)
elif x < -((1 << 31) - 1):
    return (1 << 31) - 1
else:
    return x

Or it might be even better to clamp your number using min and max:

return max(-(1 << 31) + 1, min(1 << 31, factor * int(res)))

Final code

I have removed the special case of l == 1 because it is already handled by the rest of the code. This is my final code (untested):

def my_atoi(s: str) -> int:
    l = len(s)

    while i < l and s[i].isspace():
        i += 1

    if i == l:
        return 0

    factor = -1 if s[i] == '-' else 1
    # Skip the sign character if necessary
    if s[i] == '-' or s[i] == '+':
        i += 1

    res = ""
    while i < l and s[i].isdigit():
        res += s[i]
        i += 1

    if not res:
        return 0

    return max(-(1 << 31) + 1, min(1 << 31, factor * int(res)))


Unisex Bathroom problem without semaphore Could I ask you to evaluate my solution to Unisex Bathroom Problem?

Problem description

  An office has a bathroom that can be used by both men and women, but not both at the same time. If a man is in the bathroom, other men may enter, but any women wishing to use the bathroom should wait for it to be empty. If a woman is in the bathroom, other women may enter, but any men wishing to use the bathroom should wait it to be empty. Each person (man or woman) will spend some time using the bathroom.

Task

  Design and implement a concurrent solution to the problem. The program should show when a person (man or woman) enters or exits the bathroom; as well as how many people (men or women) are in the bathroom at the moment. Because it is a space of relatively small size, the bathroom has a limiting capacity of persons C (provided as input via the command line or prefixed as a constant value) that can use it at the same time and the time that each person passes in the bathroom is random and different to each program execution.

My solution

I tried to also solve a starvation issue and I think I succeeded.

Besides all of that, what is the necessity of semaphores that the problem is related to? Why can't size be simply compared to capacity as I did?

public class Bathroom {

    private String inUseBy;

    private int size;

    private final int capacity;

    private final Lock lock = new ReentrantLock();

    private final Condition man = lock.newCondition();

    private final Condition woman = lock.newCondition();

    public Bathroom(final int capacity, final int size) {
        this.capacity = capacity;
        this.size = size;
        inUseBy = "";
    }

    public void enter(final String sex) throws InterruptedException {
        lock.lock();
        try {
            while (size == capacity || (size > 0 && !sex.equals(inUseBy))) {
                if (sex.equals("M")) {
                    man.await();
                } else {
                    woman.await();
                }
            }
            if (size == 0) {
                inUseBy = sex;
            }
            size++;
        } finally {
            lock.unlock();
        }
        System.out.println(sex + " using bathroom. Current employees in bathroom = " + size);
        Thread.sleep(10000);
        System.out.println(sex + " done using bathroom");
        lock.lock();
        try {
            size--;
            if (size == 0) {
                if (sex.equals("M")) {
                    woman.signalAll();
                } else {
                    man.signalAll();
                }
            } else {
                if (sex.equals("M")) {
                    man.signal();
                } else {
                    woman.signal();
                }
            }
        } finally {
            lock.unlock();
        }
    }

}

System.out.println(sex + " using bathroom. Current employees in bathroom = " + size);

This line is not protected by lock, so it is possible that size can change before the output is generated.

For example, if two 'M' arrive simultaneously, you could get as output:

M using bathroom.  Current employees in bathroom = 2
M using bathroom.  Current employees in bathroom = 2

which omits outputting ... = 1.

inUseBy is left as the last occupant, even when size decreases to 0.  In the constructor, it is initialized to "", implying that the empty string might also indicate the bathroom is available to any gender.  When you decrease size to zero, you should clear inUseBy.


A partition algorithm for positive integers I have encountered the following problem that I found very interesting to solve:

  Given an array of positive integers {a1, a2, ..., an} you are required
  to partition the array into 3 blocks/partitions such that the maximum
  of sums of integers in each partition is the minimum it can be.
  Restriction: you cannot alter the turn in which the numbers appear
  (example: if you have {2, 5, 80, 1, 200, 80, 8000, 90} one partition
  CANNOT be the {2, 80, 1, 90}). The program must output ONLY the maximum sum, not the partitions.

So, for example let's have the array:

{2, 80, 50, 42, 1, 1, 1, 2}

The best partitioning according to the problem is:

{ {2, 80}, {50}, {42, 1, 1, 1, 2} }

so the output of the program in this case would be 82.

I have already thought of a \$O(n^2)\$ algorithm, but isn't there any better (e.g. \$O(n)\$ or \$O(n\log n)\$) algorithm?

My \$O(n^2)\$ algorithm:

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {

    int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;

    cin >> n;
    arr = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total += arr[i];
    }

    // O(n^2) is the following

    for (int i = 1; i < n - 1; i++) {
        onee += arr[i - 1];
        twoo = 0;
        for (int j = i + 1; j < n; j++) {
            twoo += arr[j - 1];
            threee = total - twoo - onee;
            temp_maxx = max(max(onee, twoo), threee);
            if ((temp_maxx < maxx) || (maxx == -1))
                maxx = temp_maxx;
        }
    }

    cout << maxx;

    return 0;
}

Yes, more efficient algorithms do exist.

\$O(n*\log(n))\$:

Let's fix the end of the first part. Now we are interested in finding the end of the second one. I claim that we need to check only two candidates: the last index such that the sum of the second part is not greater then the sum of the third part and the one immediately after it (I will not post a formal proof here, but intuitively it is clear that we want keep these two sums as close to each other as possible.
To do it in efficient manner, we can use a binary search and prefix sums:

// Returns the sum of the [left, right] subarray in O(1) time.
int getSum(int left, int right)
    // Prefix sums are used here.
    ...

// Checks if the current answer is better than the current best
// and makes appropriate updates.
void updateAnswer(int firstEnd, int secondEnd)
    ...

// Corner cases are ignored here.
// This piece of code just represents an idea of the algorithm, it can
// contain bugs.
for (int first <- 0 ... n - 1)
    int low = first
    int high = n - 1
    while (high - low > 1)
        int mid = (low + high) / 2
        if (getSum(first + 1, mid) <= getSum(mid + 1, n - 1))
            low = mid
        else
            high = mid
    updateAnswer(first, low)
    updateAnswer(first, low + 1)

Now we can use the following observation: when the first variable increases in the code above, the low value either increases or stays the same, too. That's why we can apply two pointers technique and get an \$O(n)\$ time complexity.


Reporting duplicate entry for a given set of data While solving a problem on an online judge, I tried with these two implementations.

These two implementations do the same thing. Task is to report duplicate entry for a given set of data.

Implementation #1 : Converts input data to a String and adds to a HashSet. After all the input is read, appropriate message is displayed.

class Databse2 {

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine());//number of test cases
        int N=0,R=0,C=1;
        while(t-->0){ //while there are more test cases
            HashSet<String> set=new HashSet<String>();
            StringTokenizer st=new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                N=Integer.parseInt(st.nextToken());
                R=Integer.parseInt(st.nextToken());//Number of Rows of data
            }

            int ID=0,SC=0;boolean haha=true;
            for(int i=0;i<R;i++){ //for number of rows read each record in the row
                st=new StringTokenizer(br.readLine());
                while(st.hasMoreTokens()){
                    ID=Integer.parseInt(st.nextToken());
                    SC=Integer.parseInt(st.nextToken());
                }
                String key=ID+""+SC;//convert to string,this combo is used to check for duplicates
                haha=haha && set.add(key);

            }
            if(haha)
                System.out.println("Scenario #"+C+": possible");
            else System.out.println("Scenario #"+C+": impossible");
            C++;
        }
    }
}

Running time = 3.41 sec (for N number of test cases)

Implementation #2: Same task is accomplished as in Implementation #1 but in a different way. An object is created based on input type and added to HashSet.

class Database {

private int ID;
private int SC;

public Database(int ID,int SC){
    this.ID=ID;
    this.SC=SC;
}
@Override
public boolean equals(Object obj) {
    return (obj instanceof Database) ? ID==((Database)obj).ID:SC==((Database)obj).SC;
}

@Override
public int hashCode() {
    return 31*(ID+SC);
}

public static void main(String[] args) throws Exception{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int t=Integer.parseInt(br.readLine());
    int N=0,R=0,C=1;
    while(t-->0){
        HashSet<Database> set=new HashSet<Database>();
        StringTokenizer st=new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            N=Integer.parseInt(st.nextToken());
            R=Integer.parseInt(st.nextToken());
        }
        int ID=0,SC=0;boolean haha=true;
        for(int i=0;i<R;i++){
            st=new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                ID=Integer.parseInt(st.nextToken());
                SC=Integer.parseInt(st.nextToken());
            }
            haha=haha?set.add(new Database(ID, SC)):false;
        }
        String str=haha?"Scenario #"+C+": possible":"Scenario #"+C+": impossible";
        System.out.println(str);
        C++;
    }
}
}

Running Time #2 = 2.74 sec (for N number of test cases)

What causes implementation #2 to be faster? Is it the hashCode method?

String.equals() compare their char[] inside, which is slower than simply compare two ints.
String concatenation is slower than creating a Database.
String.hashcode() is just like its equals.

Note that your implementation of Database.equals is incorrect, though you're lucky this time.

@Override
public boolean equals(Object obj) {
    return (obj instanceof Database) && ID == ((Database)obj).ID &&
            SC == ((Database)obj).SC;
}

The hashcode implementation is only a suggestion.

@Override
public int hashCode() {
    return 31 * (31 * 17 + ID) + SC;
}


Yes/no confirmation buttons on a slide-out panel I have the following js code and am wondering how I can make it clean. It works fine but there are few repetitions. Is there a way to make it more clean?

$('.js-decline-button').click(function() {
    $('.js-confirmation').show().stop(true).animate({ left : '0' }, 500);
});

$('.js-confirmation-yes').click(function() {
    $('.js-confirmation').stop(true).animate({ left : '-100%' }, 500);
    $('.container').delay( 500 ).fadeOut( 200 ).hide(200);
});

$('.js-confirmation-no').click(function() {
    $('.js-confirmation').stop(true).animate({ left : '-100%' }, 500);
});

jsFiddle

I would add a couple of named functions:

var hideConfirmationMessage,
    showConfirmationMessage;

hideConfirmationMessage = function () {
    $('.js-confirmation').stop(true).animate({ left : '-100%' }, 500);
};

showConfirmationMessage = function() {
   $('.js-confirmation').show().stop(true).animate({ left : '0' }, 500);
};

Then your event handler attachment becomes much simpler:

$('.js-confirmation-yes').click(function() {
    hideConfirmationMessage();
    $('.container').delay(500).fadeOut(200).hide(200);
});

$('.js-confirmation-no').click(hideConfirmationMessage);
$('.js-decline-button').click(showConfirmationMessage);

I'm not sure if that's "cleaner" to you but I think it's easier to read and doesn't repeat itself.


Batch/PowerShell script that toggles the minimized state of a window I wrote this script for a user who wants to toggle the minimized state of a window that minimizes to the tray.  The user required a .bat script, so I wrote a bat + PowerShell hybrid script in order to import functions from user32.dll.

<# : minimize.bat
:: toggles minimized state of a window by its filename
:: minimize.bat /? for usage

@echo off & setlocal

if "%~1"=="" goto usage
set "prog=%~n1"
tasklist | findstr /i "\<%prog%\>" >NUL || goto usage

set /P "=Toggling the minimized state of %prog%... " <NUL
powershell -noprofile -noninteractive "iex ((gc \"%~f0\") -join \"`n\")"

goto :EOF

:usage
echo syntax: %~nx0 progname[.exe]
echo;
echo If the program is visible, minimize it.  If minimized, restore it.
goto :EOF

End batch / begin PowerShell hybrid chimera #>

Add-Type user32_dll @'
    [DllImport("user32.dll")]
    public static extern bool ShowWindowAsync(IntPtr hWnd, int nCmdShow);

    [DllImport("user32.dll")]
    public static extern int GetWindowLong(IntPtr hWnd, int nIndex);

    [DllImport("user32.dll")]
    public static extern IntPtr FindWindowEx(IntPtr parentHandle, IntPtr childAfter,
        IntPtr lclassName, string windowTitle);
'@ -namespace System

$hwnd = (ps $env:prog)[0].MainWindowHandle

if ($hwnd -eq 0) {
    tasklist /v /fi "imagename eq $env:prog*" /fo list | %{
        $title = $_ -replace '^[^:]+:\s+'
    }
    $zero = [IntPtr]::Zero
    $hwnd = [user32_dll]::FindWindowEx($zero, $zero, $zero, $title)
}

$state = [user32_dll]::GetWindowLong($hwnd, -16)

# mask of 0x20000000 = minimized; 2 = minimize; 4 = restore
if ($state -band 0x20000000) { $action = 4 } else { $action = 2 }

if ([user32_dll]::ShowWindowAsync($hwnd, $action)) {
    write-host "Success" -f green
} else {
    write-host "Fail" -f red
}

Questions:

Neither the get-process cmdlet nor gwmi win32_process nor [diagnostics.process]::getProcessByName() would show me either the window title or the HWND of a window that's minimized to the tray (uTorrent, for example).  Is there an API method I missed, or is tasklist.exe the correct hack here?
Is there any situation where FindWindowEx() would not be able to find a window that could be found with FindWindow()?  Should I import and use FindWindow() as well?

Suggested improvements and other comments (not including "Why not just write the whole thing in PowerShell?") are welcome, of course!

It took a bit to wrap me head around what you have here. It certainly is a piece of work. Rather clever what you have done in order to have a file that runs batch and PowerShell. Bravo sir! It also seems you like doing this with other languages as well!
I will first try to address your questions first and then some other points I feel worth mentioning.

In practice there are of course better options until you put in the minimized exception. In my minimal practice of you code and the suggestions you tried I think, in general, your approach is required. This is the weakest part of the review as I do not have much to offer here.

Is there any situation where FindWindowEx() would not be able to find a window that could be found with FindWindow()? Refering to the documentation for FindWindow() I did find some evidence which could convince you to stick with FindWindowEx()

Retrieves a handle to the top-level window whose class name and window name match the specified strings. This function does not search child windows. This function does not perform a case-sensitive search.

That might not change anything but depending on the target of the script it might not find the window you are looking for if you use FindWindow().

There is a few things to touch on. Most are just FYI. For the ones that are more than that I will try and draw a little more attention to them.
Invoke-Expression
The hybrid-ness of your script relies on this. I am sure that you do it so that it is self contained. However, in case no one mentioned it: Invoke-Expression can be evil. While I don't take that to heart it is potentially dangerous to use as someone can inject code into that file and it will execute blindly.
If you are willing to have a .ps1 file that gets called it would be safer. That is my tactful way of addressing "Why not just write the whole thing in PowerShell?"
Don't really expect you to adhere to the advice. Just wanted you to be aware.
Comments
This is a big one since you are giving this to someone else. This script is lacking of comments. While I do not code much in batch the PowerShell is lacking and some of the idiosyncrasies of this script were lost on me until I looked up the documentation. While you might know what is going on now you might not months/years from now.
For instance I had to look up to documentation for the line $hwnd = (ps $env:prog)[0].MainWindowHandle. Something simple like
# MainWindowHandle will return 0 if the process in hidden/minimized.

Again that could just be me but in general this is lacking context comments.
Get-Content
I see that you are reading the file in as one string using a -join. I would think that you have at least PowerShell v3.0. Either way there are cleaner options for reading the file in as one string.
# PowerShell v3.0+
"iex (gc \"%~f0\" -Raw)"
# PowerShell 2.0
"iex (gc \"%~f0\" | Out-String)"

Determining Title
Parsing cmd output is a specialty of mine. From the looks of it you are banking on Window Title being the last line of the output. While I doubt there will ever be a problem I can not say that nothing would go wrong with that logic.
With what little it would take to get more reliable results I would go so far as to change that.
$titles = tasklist /v /fi "imagename eq Keepass*" /fo list |
        Where-Object{$_ -match "^Window Title:\s+?(.*)"} |
        ForEach-Object{$Matches[1]}

Notice I also used $titles since you could have multiple matches. The way you had it before would just take the last one. Could do just the same with a Select -First 1

Again, I am impressed with the script you have set up here.


A (deep) cloning method for ES-Objects I have written a (recursive) deep clone method for ES/JS-objects. It seems to work fine, but maybe I'm missing things. Please, feel free to comment!
Note: the method will not clone cyclic structures. If it should be somehow necessary to be able to clone such structures, maybe Crockfords cycle.js can be used - but it will mangle the structure.

initializeObjCloner();
const log = Logger();
// initial object
const test1 = {
  foo: [1, 2 ,3],
  bar: { foo: {bar: 5}, foobar: "foobar", bar2: {bar3: {foo: 42}} },
};
// clone it
const test2 = Object.clone(test1);
// change a few props to demonstrate
// test2 not being a reference to test1
test2.bar.foo.foobar = "barfoo";
test2.bar.bar2.bar3.foo = 43;
test2.foo = test2.foo.map(v => v + 10);
test2.test2Only = "not in test1";
log (`**Test1:`, test1, `\n**Test2:`, test2);

// error on cyclic structures
const c = {hello: "world"};
c.recycled = c;
log(`\n${Object.clone(c)}`);

function initializeObjCloner() {
  const isImmutable = val =>
    val === null ||
    val === undefined ||
    [String, Boolean, Number].find(V => val.constructor === V);
  const isObject = obj =>
    (obj.constructor !== Date &&
    JSON.stringify(obj) === "{}") ||
    Object.keys(obj).length;
  const cloneArr = arr => arr.reduce( (acc, value) =>
    [...acc, isObject(value) ? cloneObj(value) : value], []);
  const isCyclic = obj => {
    try {
      JSON.stringify(obj);
    } catch(err) {
      return err.message;
    }
    return null;
  };
  // --------------------------
  // The actual cloning method
  // --------------------------
  const cloneObj = (obj) => {
    const cyclic = isCyclic(obj);
    return cyclic ?
      `Object.clone error: Cyclic structures can not be cloned, sorry.` :
      Object.keys(obj).length === 0 ? obj :
        Object.entries(obj)
        .reduce( (acc, [key, value]) => ( {
            ...acc,
            [key]:
              value instanceof Array
              ? cloneArr(value) :
                !isImmutable(value) && isObject(value)
                  ? cloneObj(value)
                  : value && value.constructor
                    ? new value.constructor(value)
                    : value } ),  {} );
  };
  Object.clone = cloneObj;
}

function Logger() {
  const report =
    document.querySelector("#report") ||
    document.body.insertAdjacentElement(
      "beforeend",
      Object.assign(document.createElement("pre"), { id: "report" })
    );
  return (...args) =>
    args.forEach(
      arg =>
        (report.textContent +=
          (arg instanceof Object ? JSON.stringify(arg, null, 2) : arg) + "\n")
    );
}
body {
  font: normal 12px/15px verdana, arial, sans-serif;
  margin: 2rem;
}

if readability is an issue, cloneObj may also be written as:
function cloneObj(obj) {
  if (Object.keys(obj).length < 1) { return obj; }

  if (obj.constructor === Date) {
    return new Date(obj);
  }

  if (obj.constructor === Array) {
    return cloneArr(obj);
  }

  let newObj = {};

  for ( let [key, value] of Object.entries(obj) ) {
    if (!isImmutable(value) && isObject(value)) {
      newObj[key] = cloneObj(value);
    }

    if (!newObj[key] && value && value.constructor) {
      newObj[key] = new value.constructor(value);
    }

    if (!newObj[key]) {
      newObj[key] = value;
    }
  }
  return newObj;
};

I spent a ton of time on this;

The choice to replicate Date but not the other 50+ built-ins is interesting
I would write isObject as const isObject = x => (typeof x === 'object' && x !== null)
A question to ask yourself, what about functions, do you want to clone those as well?
 if (Object.keys(obj).length < 1) { return obj; } is interesting, this means you will allow for modifications in the original object to impact the new object
The poor man's deep clone for non-cyclic structures is JSON.parse(JSON.stringify(o))
After the construction here: newObj[key] = new value.constructor(value); I would still copy over the properties as well
Still mulling over a counter example..


Tracking the number of string elements using std::unordered_map I'm looking for the most simple and efficient way to track the number of string elements in a container.

Previously, I used std::vector but I tried changing the container to std::unordered_map since I hear that it can be easier and more performant for my use.

My Code :

#include <iostream>
#include <string>
#include <unordered_map>

class Table
{
public:
    void insert(const std::string &name)
    {
        auto it = data.find(name);
        if (it == data.end())
        {
            data[name] = 1;
            return;
        }
        data[name]++;
    }
    void remove(const std::string &name)
    {
        auto it = data.find(name);
        if (it == data.end())
            return;
        if (--data[name] == 0)
            data.erase(it);
    }
    /* get the number of occurrences */
    int count(const std::string &name)
    {
        auto it = data.find(name);
        if (it == data.end())
            return 0;
        return data[name];
    }
private:
    std::unordered_map<std::string, int> data;
};

int main()
{
    Table table;
    table.insert("Apple");
    table.insert("Apple");
    table.insert("Orange");
    table.insert("Orange");
    table.remove("Orange");
    std::cout << "Number of Apples : " << table.count("Apple") << std::endl;
    std::cout << "Number of Oranges : " << table.count("Orange") << std::endl;
    std::cout << "Number of Lemons : " << table.count("Lemon") << std::endl;
}

The Result :

Number of Apples : 2
Number of Oranges : 1
Number of Lemons : 0
Program ended with exit code: 0

Is there a way to improve the class Table so my program can be more efficient than now?

The program seems to work but I used std::unordered_map for the first time so I'm not really sure if my implementation is correctly done.

void insert(const std::string &name)
{
    auto it = data.find(name);
    if (it == data.end())
    {
        data[name] = 1;
        return;
    }
    data[name]++;
}

If it is available, you should prefer taking std::string_view parameters over std::string const&. You see, every time you do:

table.insert("Orange");
table.remove("Orange");

a string has to be constructed for "Orange". Especially when all you're doing is removing or getting the count, that's very wasteful. std::string_view is very lightweight, and automatically converts from both C-strings and std::string. Even in the case of insert(), because your inserts are conditional, it's worthwhile.

Now your insert() can be simplified quite a bit because when you do data[???] with an unordered_map, and ??? is not in the map, it automatically gets inserted with a default value. For int, the default value is 0.

So all you need is:

void insert(std::string_view name)
{
    ++data[name];
}

remove() works, but it's not very efficient. The problem is that after you find the element and have the iterator... you throw that information away! Then you use data[name] which has to do another search.

Instead, use what you've got. When you have the iterator, use it.

void remove(std::string_view name)
{
    auto const it = data.find(name);
    if (it != data.end())
    {
        if (--it->second == 0)
            data.erase(it);
    }
}

count() has bit of a bug, and it's one the compiler would have informed you about if you'd made the function const.

The bug is that, as with remove(), after finding the element and getting an iterator to it, you throw that information away and use operator[]... but in this case, operator[] is non-const, meaning it might modify the map. That's not something you want happening if you're just getting a count.

Once again, the solution is to simply not throw the iterator away, but to use it:

int count(std::string_view name) const noexcept
{
    auto const it = data.find(name);
    if (it == data.end())
        return 0;
    return it->second;
}


Inefficient differential converter Following Pimgd's question, I decided to take a look at the TIS-100 myself.

This is my solution to the 3rd challenge, building a differential converter.

Requirements:

  Read values from IN.A and IN.B
  Write IN.A - IN.B to OUT.P
  Write IN.B - IN.A to OUT.N

Instruction set:

I got the basics down, but I'm doing something terribly inefficient. All the calculations are done in the top two nodes and 4 nodes are doing nothing else than just passing along the data.

It's efficient in amount of instructions and memory, but not in computation cycles. There is no guide about what's idiomatic yet, but I suppose the computation cycles are top priority.

Where Pimgd's question was using an extra node he wanted to get rid of, I don't mind using extra nodes if that brings the amount of computation cycles down.

Code overview:

For convenience, I've also included the code in text.

Top left:

MOV UP, ACC
SAV
MOV ACC, RIGHT
SWP
SUB RIGHT
MOV ACC, DOWN

Top right:

MOV UP, ACC
SAV
SUB LEFT
MOV ACC, DOWN
SWP
MOV ACC, LEFT

Other nodes:

MOV UP, DOWN

Benchmarks:

Luckily, the TIS-100 system has an in-built measurement of cycles, nodes and instructions. So I know exactly how good or bad it performs in which area.

My solution is overall considered 'nominal'. Is my solution inefficient performance-wise? If yes, how should I bring the required amount of cycles down?

So, my first attempt at this solution was very slightly more efficient.  With 2 more instructions, I managed 39 fewer cycles.  I'm not exactly certain right now what the difference is (it's pretty close), but I'm not concerned with that right now.

Thinking about this problem some more, I realized there's a mathematical trick going on here that we can make use of to drastically decrease both the number of instructions and the number of cycles.

A - B == -1 * (B - A)

That is, instead of subtracting left from right for the left column and right from left for the right column, we can just subtract once, pass the positive result to one column and the negative result to the other column.

Using this trick, I'm also able to eliminate an entire node.

As you can see, 201 cycles 5 nodes, 10 instructions.

So, starting with the top left node, we pull A into memory, subtract B, then pass it down.  Middle left just passes it down again.  Bottom left saves it to ACC, passes it down, negates it and passes it right.  The top right node just reads in B and passes it left.  The bottom right node just moves stuff from left to down.

Three of the five nodes are just there to move the values around.

Here's the source...

TOP RIGHT

MOV UP, LEFT

TOP LEFT

MOV UP, ACC
SUB RIGHT
MOV ACC, DOWN

MIDDLE LEFT

MOV UP, DOWN

BOTTOM LEFT

MOV UP, ACC
MOV ACC, DOWN
NEG
MOV ACC, RIGHT

BOTTOM RIGHT

MOV LEFT, DOWN


Grouping an array of strings into anagrams This program takes an arbitrary array of strings and group anagrams into arrays and return them in a array. Any string without any anagrams is still put in an array.

This code works perfectly and I would appreciate any comments on making this more efficient in terms of computation time.

import java.util.Arrays;
import java.util.HashMap;
import java.util.ArrayList;

public class AnagramSort{

    public static void main( String[] args ){
        HashMap< Integer, ArrayList< String >> hm = new HashMap();

        groupAnagrams( args, hm );
        System.out.println( hm );
    }

    public static void groupAnagrams( String[] list, HashMap< Integer, ArrayList< String >> hm ){

        for( int x=0; x<list.length; x++ ){
            if( list[ x ] == null ) continue;

            String curX    = list[ x ];
            int    hashX   = primeHash( curX );

            hm.put( hashX, new ArrayList( Arrays.asList( curX )));

            for( int y=x+1; y<list.length; y++ ){

                String curY    = list[ y ];
                int    hashY   = primeHash( curY );

                if( curY == null || curY.length() != curX.length())  continue;

                if( hashX == hashY ){
                    hm.get( hashX ).add( curY );

                    list[ y ] = null; // if its an anagram null it out to avoid checking again
                }
            }
        }
    }

// Utility Mehthods

    public static int primeHash( String word ){
        int productOfPrimes = 1;
        int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
            37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

        for( char ch : word.toCharArray() ){
            productOfPrimes *= prime[ (int) ch - (int) 'a' ];
        }
        return productOfPrimes;
    }

}

Sample Input:

[ mother, mothre, dad, add, gift, gender ]

Output:

[ [mother, mothre], [dad,add], [gift], [gender] ]

Technical

   groupAnagrams( args );

That should be:

    groupAnagrams( args, hm );

Bug in copy/paste somehow?

1-liner statements, even simple ones like this:

      if( list[ x ] == null ) continue;

should be braced like:

       if( list[ x ] == null ) {
           continue;
       }

This prevents maintenance problems later, and makes revision history easier to follow.

Algorithm

Your algorithm is taking each member of the array, and comparing to each subsequent member, removing anagram matches.

The primeHash() method is interesting, but ultimately it is a red herring of sorts... and it only works for lower-case input words. You have obviously invested some thought in to it, but there's a simpler solution to that problem:

private static final String anagramKey(String word) {
    word = word.toLowerCase();
    char[] chars = word.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

Take all letters, sort them, return a String. All anagrams of the same letters will have the same keys.

With that key system, the basic code can be come simpler with:

HashMap<String,List<String>> matchMap = new HashMap<>();
for (String word : args) {
    String key = anagramKey(word);
    if (!matchMap.containsKey(key)) {
        matchMap.put(key, new ArrayList<String>());
    }
    matchMap.get(key).add(word);
}

System.out.println(matchMap);

That reduces your problem to an \$O(n)\$ one.


Simple string tokenizer wrapper Is this orthogonal?

#ifndef TOKENIZER_H
#define TOKENIZER_H

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

class StringTokenizer
{
private:
        std::vector<std::string> tokens;
        unsigned int index;

public:
    StringTokenizer(std::string const & str, const char delim)
    {
        index = 0;
        // Populate the token vector...
        std::istringstream stream(str);
        std::string token;
        while (std::getline(stream, token, delim))
        {
            tokens.push_back(token);
        }
    }
    ~StringTokenizer(void) { };

    bool HasMoreTokens() { return index < tokens.size(); };
    std::string NextToken() { return TokenAtIndex(index++); };
    std::string PreviousToken() { return TokenAtIndex(index--); };
    std::string TokenAtIndex(int x)
    {
        std::string token = "";
        try
        {
            token = tokens.at(x);
        }
        catch (const std::out_of_range& range_error)
        {
            std::cerr << "[!!] Out of Range: " << range_error.what() << std::endl;
        }
        return token;
    }
    void Clear() { index = 0; };
};

#endif

Your constructor is nigh-identical to this up-voted answer for splitting a string.

The rest of the class doesn't add much value: IMO the vector provides the same API as your class and more besides; so a user might prefer to have the vector than to have your StringTokenizer instance which wraps/encapsulates/hides the vector.

vector.at returns a const reference, instead of returning by value: perhaps your methods should too.


OOP PHP best practices I've worked with PHP for a few years now and have a degree of understanding about classes / objects, but I've never written my own until now.

In that vein then, I'm looking for a bit of confirmation of the code below and that I am doing things properly before I go any further. Any advice / critique is greatly appreciated.

class People {

protected $people = array();

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

    $defaults = array(
        'model_type' => 'post_type',
        'post_type' => 'post'
    );
    $options = wp_parse_args(get_option('my_options'), $defaults);

    $this->model = $options['model_type'];
    $this->type = $options['post_type'];
}

public function get_people() {
    switch($this->model) {
        case 'user' :
            $people = get_users();
            if(!empty($people)) {
                foreach($people as $person) {
                    $new_person = new Person( $person->ID, $person->first_name, $person->user_email );
                    $this->people[] = $new_person;
                }
            }
        break;

        case 'post_type' :
            $args = array(
                'posts_per_page'   => -1,
                'orderby'          => 'post_title',
                'order'            => 'DESC',
                'post_type'        => $this->type,
                'post_status'      => 'publish',
            );
            $people = get_posts( $args );
            if(!empty($people)) {
                foreach($people as $person) {
                    $new_person = new Person( $person->ID, $person->post_title, get_post_meta($person->ID, '_email_address', true) );
                    $this->people[] = $new_person;
                }
            }
    }

    return $this->people;
}

}

class Person {

public $id;
public $name;
public $email;

public function __construct( $id, $name, $email ) {
    $this->id = $id;
    $this->name = $name;
    $this->email = $email;
}

}

protected $people = array();

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

This may not be doing what you want.  After doing that, I would expect $this->people to equal null, as you just overwrote the previous value of array() with the value of a previously undeclared variable.

                $this->people[] = $new_person;

Which makes that line create an array the first time that it is reached.

$this->model = $options['model_type'];
$this->type = $options['post_type'];

This is bad style.  You should always declare class properties before using them so that you can give them the proper scope.  This also makes them quicker to access (it checks for declared variables first).

                $new_person = new Person( $person->ID, $person->post_title, get_post_meta($person->ID, '_email_address', true) );

This looks suspicious to me.  Is the post title really a person's name?  If so, you should comment and explain why this would be true.  Otherwise, someone will later create a bunch of posts whose titles aren't people and wonder why posts are showing up under a list of people.

Alternately, if post titles are not names of people, then this type is misnamed.

You also might want to consider extending your class rather than using a switch in get_people.  Then you could have a People class and a Post class, and each could define its own get_people.


Day elapsed since today from a given date My function calculates days elapsed from the current date.  Input is fixed.  I will get vector.

Please comment on this.

static bool daysElapsed(const std::vector<char>& vec,int& val)
{
    std::string str(vec.begin(),vec.end());
    char *pos;// whose value is set by the function to the next character in str after the numerical value.
    int l = strtol(str.c_str(),&pos,10); // Its intention we don’t check till which length strtol converted
    if ((errno == ERANGE && l == LONG_MAX) || l > INT_MAX)      return false;
    if ((errno == ERANGE && l == LONG_MIN) || l < INT_MIN)      return false;

    int year = l/10000;
    int month = (l%10000)/100;
    int date = l%100;

    struct std::tm a = {0,0,0,date,
        month-1,   //Month (0 – 11; January = 0).
        year-1900  //Year (current year minus 1900).
    };
    struct std::tm b;

    time_t rawtime;
    time (&rawtime);                // Get the current calendar time UTC !-> Do not rely on this time, Convert to local time first
    localtime_s (&b,&rawtime);
    time_t x = std::mktime(&a);
    time_t y = std::mktime(&b);
    if ( x != (std::time_t)(-1) && y != (std::time_t)(-1) ) // Ensure both time are valid
    {
        double difference = std::difftime(y, x) / (60 * 60 * 24);
        std::cout << "difference = " << difference << " days" << std::endl;
    }
    else
        return false;

    return true;

}

It's weird to take a std::vector<char> instead of a std::string.  If you must take a std::vector<char>, then make two overloaded versions of the function, where the vector variant calls the string variant.

You never use the val parameter.  You probably meant to use it to return the computed result?  However, the computed difference is a double.

strtol() returns a long, but you assign it to an int.  Then you check if that int exceeds INT_MAX or is less than INT_MIN — which is impossible by definition.  Comparing an int with LONG_MAX and LONG_MIN is similarly nonsensical.  Really, all you want to do is check whether errno is non-zero.

You seem to expect the input in YYYYMMDD format, but you don't do any validation other than checking for overflow or underflow.  There are plenty of 8-digit numbers that shouldn't be valid dates.

Unfortunately, the localtime_s() function is Windows-only.  POSIX has localtime_r(), whose arguments are in the other order, but Windows doesn't support it.  You'll probably need an #ifdef _WIN32.

When testing for the validity of x and y, put the early-return failure case first.  That's just a better pattern for error handling, because the successful case doesn't have to be indented another level.


json2CSV fails because of lack of RAM memory I run this code on my Heroku Node.js server in order to get CSV for few hundred rows, but it fails with R14 - Memory Quota Exceeded.
It worked fine when there were less rows in DB, even without writing to file, I was able to write CSV directly to HTTP response.
What can I do to solve this?

var mongoose = require("mongoose");
const fs = require('fs');
const path = require('path')
const Json2csvParser = require("json2csv").Parser;
var Follow = require("../models/follow");
const fields = ["brand", "handle", "title", "followDateTime", "posts", "followers", "following", "description", "link", "isPrivate"];

module.exports = function(app) {
    app.get("/csv", (req, res) => {
        Follow.find({}).exec(function(err, follows) {
            if (err) {
                res.status(500).send(err);
            } else {
                let csv;
                try {
                    const json2csvParser = new Json2csvParser({ fields });
                    csv = json2csvParser.parse(follows);
                } catch (err) {
                    return res.status(500).json({ err });
                }
                const dateTime = Date.now();
                const filePath = path.join(__dirname, "..", "public", "exports", "csv-" + dateTime + ".csv");

                fs.writeFile(filePath, csv, function (err) {
                    if (err) {
                      return res.json(err).status(500);
                    }
                    else {
                      setTimeout(function () {
                        fs.unlinkSync(filePath); // delete this file after 30 seconds
                      }, 30000)
                      return res.json("/exports/csv-" + dateTime + ".csv");
                    }
                  });
            }
        });
    });
};
```

Before we dive into code, I'd like to ask: Does this CSV really need to be generated on-the-fly/on-demand? If the answer is no, you can probably run a cron job using mongoexport. This way, you avoid Node altogether.

Libraries aren't immune to memory limits. They create objects too! In this case, it starts when you loaded up a lot of Follow entries into follows. This is compounded when you converted all of that data into CSV. Under the hood, you 1) loaded a lot of data into an huge array of objects and 2) you converted that huge array of objects into a huge string.

Now luckily, json2csv has a streaming API. What this means is that, instead of processing all of your results in one go in memory, you have the option to build that CSV by chunk. Since we're dealing with an array of objects instead of strings, buffers and arrays of raw data, you should look at the "object mode".

So what you do is set up a pipeline - a bunch of functions connected together and called one after the other with the output of the previous being the input of the next. Data is streamed into this pipeline, transforming on every transform function it passes through until it reaches the end.

In your case, it would look something like this:

const { createWriteStream } = require('fs')
const { Readable } = require('stream')
const { Transform } = require('json2csv')

// ...somewhere in your controller code...

// With streams, everything starts with and ends with a stream. This is the start.
const input = new Readable({ objectMode: true })
input._read = () => {} // Not sure what this is for, really.

// We set up the transformer, the thing that converts your object into CSV rows.
const json2csv = new Transform ({ fields }, { objectMode: true })

// Create a stream to the file. This is the end of the line.
const output = createWriteStream('./output')

// You can optionally listen to the output when all the data is flushed
output.on('finish', () => { /* all done */ })

// We connect the dots. So this reads like:
// 1. Read data into input.
// 2. Input gets fed into json2csv.
// 3. The output of json2csv is fed into output (which is our file).
const stream = input.pipe(json2csv).pipe(output)

// Start pumping data into the stream. You could use setInterval if you wanted.
follows.forEach(o => input.push(obj))

// Close the input.
input.push(null)

Now I'm not too familiar with Mongoose. But if it has an API that exposes your results as a stream, you can skip object mode and pipe that stream to json2csv instead. This way, the entire thing uses streams and at no point would all data be stored in memory. They get loaded, processed and flushed a few pieces at a time.

const stream = streamFromMongoose.pipe(json2csv).pipe(output)


WHERE NOT IN SQL Performance SELECT TOP 1 l.ID
FROM Leads l
WHERE
     l.ID NOT IN (SELECT LeadID FROM LeadFollowups)
     AND l.ID NOT IN (SELECT LeadID FROM LeadsWorking)
     AND l.ID NOT IN (SELECT LeadID FROM LeadsDead)
     AND l.ID NOT IN (SELECT LeadID FROM LeadHolds)
     AND l.ID >= (RAND() * (SELECT MAX(ID) FROM Leads))
ORDER BY l.QualityScore DESC

I have a table growing by a 10 to 100 thousand rows a day.  I have several tables to track actions of the current leads that shouldn't be included when grabbing the new lead.  My query is pretty quick now, but as this grows is NOT IN the most efficient solution for this? Especially if I get in to the range of ~10 million rows in the Leads table?

My query is pretty quick now, but as this grows is NOT IN the most efficient solution for this?

I expect it would be quicker if you had an indexed Status field in the Leads table (so that records in the LeadsDead table had a corresponding Status=Dead in the Leads table); and quicker still if Status were a clustered index, so that all the leads with a given Status were contiguous in the Leads table.


Workaround for unchecked cast of a deserialized Object to ArrayList For a class I was assigned to write code to read objects of the class Vehicle using ObjectInputStream (in). The objects are stored in an ArrayList called orders.

SSCE:

// Read all orders
Object obj = in.readObject();
orders = (ArrayList<Vehicle>) obj;

However, the compiler complains:

MacBook:Homework Brienna$ javac Orders.java -Xlint:unchecked
Orders.java:152: warning: [unchecked] unchecked cast
                    orders = (ArrayList<Vehicle>) in.readObject();
                                                                ^
  required: ArrayList<Vehicle>
  found:    Object
1 warning

I always try to improve my code instead of ignoring or suppressing warnings. In this case, I have come up with a solution, but I'm trying to understand why it works, and if there is a better solution.

This update stops the warning:

// Read all orders, casting each order individually
Object obj = in.readObject();
ArrayList ar = (ArrayList) obj;
for (Object x : ar) {
    orders.add((Vehicle) x);
}

Based on what I understand from what I've been reading, it works because (ArrayList<Vehicle>) obj may throw an exception if not all the elements are Vehicle. I am confused -- non-Vehicle objects can be added to the ArrayList even if its type parameter has been specified as Vehicle? Also, is there a better solution, e.g. using instanceof?

In general, the Java compiler knows the type of each variable, at every point during the execution. And when you operate on incompatible types, the program won't compile.

When you cast an object to ArrayList<Vehicle>, the Java runtime environment can only ensure that the cast to ArrayList<something> succeeds, but due to backwards compatibility (Java 1.4 from 2002), the cast will succeed, no matter if the arraylist contains Integer or String or Vehicle objects. Therefore, in this situation, the compiler warning tells you: Hey, you are doing something that cannot be checked, make sure you know what you are doing.

Your code that first deserializes the list as a raw type (ArrayList instead of ArrayList<Vehicle>) doesn't produce the compiler warning since the raw ArrayList is equivalent to ArrayList<Object>, and you won't get a surprising ClassCastException when working with this list.

If you are sure that the serialized list will only ever contain objects of type Vehicle, you can safely ignore that warning. In my code, I have written a utility function like this:

@SuppressWarnings("unchecked")
public static <T> T castToAnything(Object obj) {
    return (T) obj;
}

…

ArrayList<Vehicle> vehicles = castToAnything(in.readObject());

Another way is to not serialize the list, but to create a wrapper class:

public class SerializedData implements Serializable {
    public final ArrayList<Vehicle> vehicles = new ArrayList<>();
}

When you serialize this class and deserialize it, you still have to cast the type using (SerializedData) in.readObject(), but the warning goes away.

This still doesn't guarantee that the vehicles list contains only vehicles after deserialization, but that is an entirely different problem.


Go function to generate permutations of a given integer array I'm writing a function to generate a permutation of given []int:

// Input: [1,2,3]
// Output:
// [
//   [1,2,3],
//   [1,3,2],
//   [2,1,3],
//   [2,3,1],
//   [3,1,2],
//   [3,2,1]
// ]

func permute(nums []int) [][]int {
    var tmp []int
    var res [][]int
    invalid_pos := make([]bool, len(nums))
    res = backtrack(nums, tmp, invalid_pos, res)
    return res
}

// backtrack generates all the permutations of the given `nums` and put them into `res`.
// `invalid_pos` keeps track of which number is valid to pick from `nums` to form a permutation
// `tmp`
func backtrack(nums []int, tmp []int, invalid_pos []bool, res [][]int) [][]int {
    if len(tmp) == len(nums) {
        tmp2 := make([]int, len(tmp))
        copy(tmp2, tmp)
        res = append(res, tmp2)
    } else {
        for i, num := range nums {
            if invalid_pos[i] {
                continue
            }
            invalid_pos[i] = true
            tmp = append(tmp, num)
            res = backtrack(nums, tmp, invalid_pos, res)
            invalid_pos[i] = false
            tmp = tmp[:len(tmp)-1]
        }
    }
    return res
}

My question is do I need to make a copy copy(tmp2, tmp)? I read about capturing iteration variables and I was wondering if this will have any side effect? I think I can simplify the code by removing copy...

To make it nicer for your reviewers you could post as a complete and
runnable example:

package main

import "fmt"

...

func main() {
    input := []int{1, 2, 3}
    output := permute(input)
    fmt.Printf("Input: %v\nOutput:\n", input)
    for _, x := range output {
        fmt.Printf("  %v\n", x)
    }
}

With that out of the way, I'd simplify permute a bit:

func permute(nums []int) [][]int {
    return backtrack(nums, []int{}, make([]bool, len(nums)), [][]int{})
}

In backtrack I'd consider returning early for the first case, that
lets you remove one level of indentation for the rest:

func backtrack(nums []int, tmp []int, invalid_pos []bool, res [][]int) [][]int {
    if len(tmp) == len(nums) {
        tmp2 := make([]int, len(tmp))
        copy(tmp2, tmp)
        return append(res, tmp2)
    }
    ...
}

Regarding your question:  Well, what happens if you remove the copy
call?

0 go % go run perm.go
Input: [1 2 3]
Output:
  [0 0 0]
  [0 0 0]
  [0 0 0]
  [0 0 0]
  [0 0 0]
  [0 0 0]

Clearly it does something and you cannot remove it just like that.  It
also has nothing to do with capturing iteration variables, the only ones
you have here are i and num - both aren't even part of the copy
call, plus, you're not capturing anything, there's no func() {...}
declaration anywhere that even could capture variables.

Variable capturing and the (most common?) problem with it comes only if you have a construction like this:

for i := ... {
    x := func() {
        foo(i)
    }
}

The i in the anonymous function is the one from the loop - and since it's always the same variable, all the created functions reference ... the same variable!  That can be confusing since people might expect that on each iteration of the loop we're capturing that one value that i currently has.  Go could've done that, but I'm guessing mostly for performance reasons that's not being done and you've to explicitly make it happen yourself:

for i := ... {
    j := i
    x := func() {
        foo(j)
    }
}

Now foo gets called with all the different values of i.

Okay so that's that, now I'd just recommend simplifying this algorithm
to get rid of invalid_pos, tmp and the res parameter and do it all
functionally and recursively.  I'm saying that because the code right
now is pretty complex for the problem and yet it doesn't do everything
upfront that it could, like preallocating the res array to the final
length, so it seems this is more of a learning exercise.

Start with the base cases, empty list and one element, then consider the
one element longer list:

func permute2(nums []int) [][]int {
    if len(nums) <= 1 {
        return [][]int{nums}
    }
    result := [][]int{}
    for i, x := range nums {
        ...
    }
    return result
}

Don't optimise to early for reusing things, that can also follow once
the algorithm is in its most simple form; clarity comes first.

Hint:  You can do it without copy or manually instantiating any
more slices via []int{}, just check out
append and how to do
subslices.  Take particular care to not simply append slices together without considering how the underlying data is going to be shared (that's why append([]int{}, <slice here>) might be necessary to prevent the slice from being modified).

As a spoiler:

   func permute2(nums []int) [][]int {
     if len(nums) <= 1 {
         return [][]int{nums}
     }
     result := [][]int{}
     for i, x := range nums {
         without := append(append([]int{}, nums[:i]...), nums[i+1:]...)
         for _, y := range permute2(without) {
             result = append(result, append([]int{x}, y...))
         }
     }
     return result
 }


Simple retrieving sessionId rows from indexed SQL column is slow I have to select all the rows from a database table containing a defined (long)sessionId where the sessionId row is indexed.
But it is slow, and since the code to access it is really simple, I'm wondering where the problem is. Here is the code of the three layers:

var localPath = BusinessClient.Instance.Tracker.GetSpecifiedMilestonesInSessionObjects(milestonesInSession.SessionId).ToList();

public IQueryable<MilestonesInSession> GetSpecifiedMilestonesInSessionObjects(long sessionId)
    {
        var query = from m in _milestonesInSessionRepository.GetAll()
                    where m.SessionId == sessionId
                    select m;

        return query;
    }

    public IQueryable<Model.Tracker.MilestonesInSession> GetAll()
    {
        var query = from milestoneSession in _dataContext.Repository<Linq.TrackerMilestonesInSession>()
                    select new Model.Tracker.MilestonesInSession
                               {
                                   MilestoneId = milestoneSession.MilestoneId,
                                   CreatedDate = milestoneSession.CreatedDate,
                                   SessionId = milestoneSession.SessionId,
                                   ProductId = milestoneSession.ProductId,
                                   TrackerId = milestoneSession.TrackerId,
                                   StatusId = milestoneSession.StatusId,
                                   BankId = milestoneSession.BankId
                               };
        return query;
    }

Here attached the screenshot of the performance using ANTS:

Presentation Layer

Business Layer

Data Access Layer

The sessionId in the database is not unique, but I created an index on them, why accessing it is not an instant operation?

I think the bottleneck is in IQueryable<Model.Tracker.MilestonesInSession> GetAll() because it looks like you are executing that query into memory by creating a new Model.Tracker.MilestonesInSession
Try this:

public IQueryable<MilestonesInSession> GetSpecifiedMilestonesInSessionObjects(long sessionId)
{
    var allMilestones = from milestoneSession in
                        _dataContext.Repository<Linq.TrackerMilestonesInSession>()
                        select new {
                                     MilestoneId = milestoneSession.MilestoneId,
                                     CreatedDate = milestoneSession.CreatedDate,
                                     SessionId = milestoneSession.SessionId,
                                     ProductId = milestoneSession.ProductId,
                                     TrackerId = milestoneSession.TrackerId,
                                     StatusId = milestoneSession.StatusId,
                                     BankId = milestoneSession.BankId
                                   };
      var query = from m in allMilestones
                  where m.SessionId == sessionId
                  select new Model.Tracker.MilestonesInSession
                  {
                    MilestoneId = m.MilestoneId,
                    CreatedDate = m.CreatedDate,
                    SessionId = m.SessionId,
                    ProductId = m.ProductId,
                    TrackerId = m.TrackerId,
                    StatusId = m.StatusId,
                    BankId = m.BankId
                  };
      return query;
}