Programmer's Blog

Programmer's reference

Category Archives: Uncategorized

[C++] find maximum in each of subsequence

problem: Find max in each of the 3 numbers in the sequence

2 3 1 5 6 3 6

ans: 3 5 6 6 6

void printKMax(int arr[], int n, int k){
 deque<int> d;
 int max = 0;
 int maxpos = 0;
 for (int i = 0 ; i < n ; i++)
 {
     d.push_back(arr[i]);
     if (d.size() > k) d.pop_front(); //if size > subseq, drop

     if (max < d.back())  //compare first number in deque
     {
         max = d.back();
         maxpos = k - 1;
     }
     else
         maxpos--;        //the pos in maximum in subseq shifts
 
     if (maxpos <= 0)  //if max num is out of deque
     {                 //check all numbers in the subseq
         max = 0;
         for (int j = 0 ; j < d.size() ; j++)
         {
             if (max < d.back())
             {
                 max = d.back();
                 maxpos = j;
             }
             d.push_back(d.front());
             d.pop_front();
     } 
 }
 
 if (d.size() < k)
 continue;

 cout << max << " ";
}
 
 
 cout << "\n";
}

[C++] (LCS) Longest common sequence problem

 string k = String1;
 string g = String2;
 k.insert(0,1,' ');
 g.insert(0,1,' ');
 
 int m = k.length();
 int n = g.length();
 int arr[m][n];
 
 for (int i = 0 ; i < m ; i++) arr[i][0] = 0;
 for (int j = 0 ; j < n ; j++) arr[0][j] = 0;
 
 for (int i = 1 ; i < m ; i++ )
 {
     for (int j = 1 ; j < n ; j++)
     {
         if (k[i] == g[j])
         {
             arr[i][j] = arr[i-1][j-1] + 1;
         }
         else
         {
             arr[i][j] = arr[i][j-1] > arr[i-1][j] ? arr[i][j-1] : arr[i-1][j];
         }
     }
 } 
 
 cout << arr[m-1][n-1] << endl;

[java] thread pool example

public class ThreadPool implements Runnable{
   private final LinkedBlockingQueue\<Runnable\> queue;
   private final List\<Thread\> threads;
   private boolean shutdown;

public ThreadPool(int numberOfThreads) {
   queue = new LinkedBlockingQueue\<\>();
   threads = new ArrayList<>();

for (int i=0; i\<numberOfThreads; i++) {
   Thread thread = new Thread(this);
   thread.start();
   threads.add(thread);
   }
}

public void execute(Runnable task) throws InterruptedException {
   queue.put(task);
}

private Runnable consume() throws InterruptedException {
   return queue.take();
}

public void run() {
   try {
       while (!shutdown) {
         Runnable task = this.consume();
         task.run();
       }
   } catch(InterruptedException e) {
 }
   System.out.println(Thread.currentThread().getName() + " shutdown");
 }

public void shutdown() {
   shutdown = true;

   threads.forEach((thread) -\> {
   thread.interrupt();
   });
}

public static void main(String[] args) throws InterruptedException {
    ThreadPool threadPool = new ThreadPool(5);
    Random random = new Random();

    for (int i=0; i\<10; i++) {
        int fi = i;
        threadPool.execute(() -\> {
          try {
             Thread.sleep(random.nextInt(1000));
             System.out.printf("task %d complete\n", fi);
          } catch (InterruptedException e) {
             e.printStackTrace();
          }
        });
    }

    Thread.sleep(3000);
    threadPool.shutdown();
}
}

[java] virtual functions

source: http://stackoverflow.com/questions/16617291/abstract-virtual-functions-in-java

As I mentioned in my comment private functions are not virtual and I want to demonstrate it using following example:

class A {
    public void foo() {
        System.out.println("A#foo()");
    }

    public void bar() {
        System.out.println("A#bar()");
        qux();
    }

    private void qux() {
        System.out.println("A#qux()");
    }
}

class B extends A {
    public void foo() {
        System.out.println("B#foo()");
    }

    private void qux() {
        System.out.println("B#qux()");
    }
}

Now lets run following code:

A foobar = new B();
foobar.foo(); // outputs B#foo() because foobar is instance of B
foobar.bar(); // outputs A#bar() and A#qux() because B does not have method bar 
              // and qux is not virtual

[C++]single consumer lock_free_queue implementation

#include \<iostream\>
#include \<atomic\>
#include \<thread\>
#include \<chrono\>
#include \<mutex\>

template\
class lock_free_queue
{
private:
    struct node
    {
        std::shared_ptr\<T\> data;
        node* next;
        node(): next(nullptr) {}
    };

    std::atomic\<node*\> head;
    std::atomic\<node*\> tail;
    node* pop_head()
    {
        node* const old_head=head.load();
        if(old_head==tail.load())
        {
            return nullptr;
        }
    head.store(old_head-\>next);
    return old_head;
    }

public:
    lock_free_queue():
    head(new node),tail(head.load()) {}
    lock_free_queue(const lock_free_queue& other)=delete;
    lock_free_queue& operator=(const lock_free_queue& other)=delete;
    ~lock_free_queue()
    {
        while(node* const old_head=head.load())
        {
            head.store(old_head-\>next);
            delete old_head;
        }
    }
    std::shared_ptr\<T\> pop()
    {
        node* old_head=pop_head();
        if(!old_head)
        {
            return std::shared_ptr\<T\>();
        }
        std::shared_ptr\<T\> const res(old_head-\>data);
        delete old_head;
        return res;
    }

    void push(T new_value)
    {
        std::shared_ptr\<T\> new_data(std::make_shared\<T\>(new_value));
        node* p=new node;
        node* const old_tail=tail.load();
        old_tail-\>data.swap(new_data);
        old_tail-\>next=p;
        tail.store(p);
    }
};

int main()
{
    lock_free_queue\<int\> queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    std::cout \<\< *queue.pop() \<\< "\n";
    std::cout \<\< *queue.pop() \<\< "\n";
    queue.push(4);
    std::cout \<\< *queue.pop() \<\< "\n";
    std::cout \<\< *queue.pop() \<\< "\n";
}

//result: 1 2 3 4

[C++]Simple lock-free stack implementation

#include \<iostream\>
#include \<atomic\>

using namespace std;

template \<typename T\>
struct node
{
    T data;
    node* next;
    node* previous;
    node(const T& data) : data(data), next(nullptr), previous(nullptr) {}
};

template \<T\>
class stack
{
    std::atomic\<node\<T\>*\> head;
public:
    void push(const T& data)
    {
        node\<T\>* new_node = new node\<T\>(data);

        new_node->previous = head.load(std::memory_order_relaxed);
        new_node->next = head.load(std::memory_order_relaxed);

        while(!head.compare_exchange_weak(new_node->next, new_node,
        std::memory_order_release,
        std::memory_order_relaxed));
    }

    T pop_front()
    {
        node\<T*\> read_node;
        read_node = head.load(std::memory_order_relaxed);
        T ret = read_node->data;

        while(!head.compare_exchange_weak(read_node, read_node->previous,
        std::memory_order_release,
        std::memory_order_relaxed));

        return ret;
    }
};

int main()
{
    stack\<int\> s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.pop_front() << "\n";
    cout << s.pop_front() << "\n";

    s.push(4);
    cout << s.pop_front() << "\n";
    cout << s.pop_front() << "\n";

} 

//result: 3 2 4 1

[vim] settings for .vimrc

set hidden

set nowrap        " don't wrap lines
set tabstop=4     " a tab is four spaces
set backspace=indent,eol,start
                    " allow backspacing over everything in insert mode
set autoindent    " always set autoindenting on
set copyindent    " copy the previous indentation on autoindenting
set number        " always show line numbers
set shiftwidth=4  " number of spaces to use for autoindenting
set shiftround    " use multiple of shiftwidth when indenting with '<' and '>'
set showmatch     " set show matching parenthesis
set ignorecase    " ignore case when searching
set smartcase     " ignore case if search pattern is all lowercase,
                    "    case-sensitive otherwise
set smarttab      " insert tabs on the start of a line according to
                    "    shiftwidth, not tabstop
set hlsearch      " highlight search terms
set incsearch     " show search matches as you type
set history=1000         " remember more commands and search history
set undolevels=1000      " use many muchos levels of undo
set wildignore=*.swp,*.bak,*.pyc,*.class
set title                " change the terminal's title
set visualbell           " don't beep
set noerrorbells         " don't beep
set nobackup
set noswapfile

[C] Returnable 2D array and readfile

char** create2DCharArray(int m, int n)
{
   char* values = calloc(m*n, sizeof(char));
   char** rows = malloc(n*sizeof(char*));
   int i;
   for (i=0; i<n; ++i)
   {
       rows[i] = values + i*m;
   }
   return rows;
}

void destroy2DCharArray(char** arr)
{
   free(*arr);
   free(arr);
}

char** readFileInto2DArray ( const char* fileName )
{
   FILE *f;
   f = fopen(fileName,"r");
   char ch, strr[32767], *str;
   int row = 0, column = 0, i = 0, j = 0;
   while(fgets(strr, sizeof strr, f))
   {
      row++;
      if(column < strlen(strr) )
           column = strlen(strr);
   }
   rewind(f);
   char** arr = create2DCharArray(column,row);
   while(i < row)
   {
     do
     {
        ch = fgetc(f);
        if ( ch == '\r')
        ch = fgetc(f);
        arr[i][j] = ch;
        j++;
     }
     while( !( ch == '\n' || ch == EOF ) );
     arr[i][--j] = '\0';
     i++;
     j = 0;
   }
   fclose(f);
   return arr;
}

[C++] check hardware concurrency

unsigned int n = std::thread::hardware_concurrency();

[C++] Scoped thread class

class scoped_thread
{
  std::thread t;
public:
  explicit scoped_thread(std::thread t_) : t(std::move(t_))
  {
    if(!t.joinable())
      throw std::logic_error(“No thread”);
  }

  ~scoped_thread()
  {
    t.join();
  }
  scoped_thread(scoped_thread const&)=delete;
  scoped_thread& operator=(scoped_thread const&)=delete;
};