Apt-get speed issues

Apt downloads seem to get slower when ftp protocal is used. Something is up with the servers and the problem can be fixed by switching to the http sources instead.

unix process tricks

kill -

kill levels
TERM 15
KILL 9
SIGABRT 6

http://unixhelp.ed.ac.uk/CGI/man-cgi?signal+7

nice the process

the nice level is the priority 1 being the highest and 19 being the lowest for normal users but super users can reach down to -20. The default level is inherited from the parent process but is usually 0.

nice -n nice_value command arguments

renice
renice [ -n increment ] [ -g | -p | -u ] ID ...

renice priority [ -p ] pid ... [ -g gid ... ] [ -p pid
... ] [ -u user ... ]

renice priority -g gid ... [ -g gid ... ] [ -p pid ... ]
[ -u user ... ]

renice priority -u user ... [ -g gid ... ] [ -p pid ... ]
[ -u user ... ]



nohup
start the process independent of its parent so you can kill its source shell

nohup cmd &

With 3 arrays of sorted data find the tuple with the minuim distance

Question;
You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
* Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))
* Please give a solution in O(n) time complexity

Answer;
Note it contains the paired as well as the tuple type solution. I didnt know how to do so i trial it with a pair type..

EDIT: Also on the web I noticed several other solutions that just move the min number I didnt click until now.. But be careful the mins movement is a property of this particular distance function if that changes then moving the min might not be the best course of action.

#include <math.h>
#include <iostream>
#include <list>
using namespace std;

#define MAX3(a,b,c) ((a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c))

#define DIST2(a,b) abs(a-b)
#define DIST3(a,b,c) MAX3(abs(a-b),abs(a-c),abs(b-c));

struct Tuple
{
  int a;
  int b;
  int c;

  Tuple(int _a, int _b, int _c) { a = _a; b = _b; c = _c; }
};

typedef list ListTuple;

void min_tuple(int* a, int* b, int* c, int sizea, int sizeb, int sizec)
{
  ListTuple best_tuple;

  //best_pairs.push_back(Pair(0,0));
  int best = DIST3(a[0], b[0], c[0]);

  int i, j, k;
  i = j = k = 0;
  
  while(
        (i < sizea) &&
        (j < sizeb) &&
        (k < sizec)
        )
    {
      //check the current for best status
      int dist = DIST3(a[i], b[j], c[k]);
      if(dist < best)
        {
          best_tuple.clear();
          best_tuple.push_back(Tuple(i,j,k));
          best = dist;
        }
      else if(dist == best)
        best_tuple.push_back(Tuple(i,j,k));
      
      //move to the next possible minium...
      int dist_i = DIST3(a[i+1], b[j],   c[k]);
      int dist_j = DIST3(a[i],   b[j+1], c[k]);
      int dist_k = DIST3(a[i],   b[j],   c[k+1]);
    
      if(dist_i < dist_j)
        if(dist_i < dist_k)
          i++;
        else
          k++;
      else
        if(dist_j < dist_k)
          j++;
        else
          k++;
      cout << i << "," << j << "," << k << " -> ";
    }
  cout << endl;

  cout << "best tuples are: " << endl;
  for(ListTuple::iterator pit = best_tuple.begin(); pit != best_tuple.end(); pit++)
    {
      Tuple& t = *pit;
      cout  << "index: " << t.a << "," << t.b << "," << t.c 
            << " values: "<< a[t.a] << "," << b[t.b] << "," << c[t.c] << endl;
    }
  cout << endl;
  cout << "best distance was: " << best;
}


struct Pair
{
  int a;
  int b;

  Pair(int _a, int _b) { a = _a; b = _b; }
};

typedef list ListPair;

void min_pair(int* a, int* b, int sizea, int sizeb)
{
  ListPair best_pairs;

  //best_pairs.push_back(Pair(0,0));
  int best = DIST2(a[0], b[0]);

  int i, j;
  i = j = 0;

  while(
        (i < sizea) &&
        (j < sizeb)
        )
    {
      //check the current for best status
      int dist = DIST2(a[i], b[j]);
      if(dist < best)
        {
          best_pairs.clear();
          best_pairs.push_back(Pair(i,j));
          best = dist;
        }
      else if(dist == best)
        best_pairs.push_back(Pair(i,j));

      //move to the next possible minium...
      if(i < sizea)
        if(j < sizeb)
          if(DIST2(a[i+1], b[j]) < DIST2(a[i], b[j+1]))
            i++;
          else
            j++;
        else
          i++;
      else
        j++;
      cout << i << "," << j << " -> ";
    }
  cout << endl;

  cout << "best pairs are: ";
  for(ListPair::iterator pit = best_pairs.begin(); pit != best_pairs.end(); pit++)
    {
      Pair& p = *pit;
      cout  << "index: " << p.a << "," << p.b
            << " values: "<< a[p.a] << "," << b[p.b] << endl;
    }
  cout << endl;
  cout << "best distance was: " << best;
}
 
void print(int* data, int size)
{
  for(int i = 0; i < size; i++)
    cout << data[i] << " ";
  cout << endl;
}

void bubblesort(int data[], int size)
{
  bool change = true;
  int tmp;
  while(change)
    {
      change = false;
      for(int i = 0;i < size-1;i++)
        if(data[i] > data[i+1])
          {
            tmp = data[i];
            data[i] = data[i+1];
            data[i+1] = tmp;
            change = true;
          }
    }
}

#define COUNT 10
int main()
{
  int data1[COUNT];
  int data2[COUNT];
  int data3[COUNT];

  srand(time(NULL));
  for(int i = 0; i < COUNT; i++)
    {
      data1[i] = rand()%200;
      data2[i] = rand()%200;
      data3[i] = rand()%200;
      //data1[i] = -20 + i*3;
      //data2[i] = i*5;
    }

  bubblesort(data1, COUNT);
  bubblesort(data2, COUNT);
  bubblesort(data3, COUNT);

  print(data1, COUNT);
  print(data2, COUNT);
  print(data3, COUNT);

  min_pair(data1, data2, COUNT, COUNT);
  cout << endl;
  min_tuple(data1, data2, data3, COUNT, COUNT, COUNT);

}

Question:
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Answer:

void mult_of_other_no_div(int* data, int* out, int size)
{
  //O(n)
  int multi = 1;
  int i;

  for(i = 0; i < size; i++)
    {
      out[i] = multi;
      multi *= data[i];
    }

  multi = 1;
  for(i = size-1; i >= 0; i--)
    {
      out[i] *= multi;
      multi  *= data[i];
    }      
}

bit reversal

#if _WIN64 || __amd64__ || _M_X64
#define IS_64_BIT
#else
#define IS_32_BIT
#endif

#ifdef IS_64_BIT
uint64_t bitRevInt32(uint64_t value)
{
  value = (value & 0x00000000ffffffff) << 32 | (value & 0xffffffff00000000) >> 32;
  value = (value & 0x0000ffff0000ffff) << 16 | (value & 0xffff0000ffff0000) >> 16;
  value = (value & 0x00ff00ff00ff00ff) << 8  | (value & 0xff00ff00ff00ff00) >> 8;
  value = (value & 0x0f0f0f0f0f0f0f0f) << 4  | (value & 0xf0f0f0f0f0f0f0f0) >> 4;
  value = (value & 0x3333333333333333) << 2  | (value & 0xcccccccccccccccc) >> 2;
  value = (value & 0x5555555555555555) << 1  | (value & 0xaaaaaaaaaaaaaaaa) >> 1;
  return value;
}
#endif

uint32_t bitRevInt32(uint32_t value)
{
  value = (value & 0x0000ffff) << 16 | (value & 0xffff0000) >> 16;
  value = (value & 0x00ff00ff) << 8  | (value & 0xff00ff00) >> 8;
  value = (value & 0x0f0f0f0f) << 4  | (value & 0xf0f0f0f0) >> 4;
  value = (value & 0x33333333) << 2  | (value & 0xcccccccc) >> 2;
  value = (value & 0x55555555) << 1  | (value & 0xaaaaaaaa) >> 1;
  return value;
}

unsigned char bitRevChar(unsigned char value)
{
  value = (value & 0x0f) << 4 | (value & 0xf0) >> 4;
  value = (value & 0x33) << 2 | (value & 0xcc) >> 2;
  value = (value & 0x55) << 1 | (value & 0xaa) >> 1;
  return value;
}

Pointer sizes

On 32 bit systems;
- pointers are 32bits or 4 bytes
- the memory is limited to 4GB

On 64 bit systems
- pointers are 64bits or 8bytes

Special notes;
- Microsoft likes to make a mess... for Microsoft compilers pointers can vary in size when multiple inheritance is involved. (http://blogs.msdn.com/b/oldnewthing/archive/2004/02/09/70002.aspx)
- some far pointers also include a virtual page index in the upper bits, for a 32 bit machine you might end up with a 48 bit far pointer.

Breath First Search

Breath first search

Algorithm;
1) place the header node into the open node queue (FIFO)
2) get the next item from the queue
3) check for a match of the search
4) push all child nodes that havent been visited into the queue in order
5) repeat from 2

Complexity:
The numbers are odd.. need to find out why..

class Node
{
public:
  string title;
  list children;

  Node(string _title);
  virtual ~Node();

  void addChild(Node* kid);
  Node& operator<<(Node& kid);
};

typedef list NodeList;
typedef set NodeTree;

Node* breath_first_search(Node* node, string target)
{
  NodeList open;
  NodeTree visited;

  open.push_back(node);

  NodeList::iterator nit;
  while(open.size() > 0)
    {
      node = open.front();
      open.pop_front();
      cout << node->title << " ";
      
      if(node->title == target)
        return node;
      
      for(nit = node->children.begin();nit != node->children.end();nit++)
        {
          Node* child = *nit;
          if(visited.find(child) == visited.end())
            {
              visited.insert(child);
              open.push_back(child);
            }
        }
    }
  return NULL;
}