ldd - tracking used libraries/versions

To figure out what libraries(and its location/version as well) an executable is using hit it with "ldd". When using it know in mind that it needs the exact path to the executable.

For example to track down what "ls" is using try this

~> ldd /bin/ls
       linux-vdso.so.1 =>  (0x00007fffdfad4000)
       librt.so.1 => /lib/librt.so.1 (0x00007f33ad7a1000)
       libselinux.so.1 => /lib/libselinux.so.1 (0x00007f33ad585000)
       libacl.so.1 => /lib/libacl.so.1 (0x00007f33ad37e000)
       libc.so.6 => /lib/libc.so.6 (0x00007f33ad01c000)
       libpthread.so.0 => /lib/libpthread.so.0 (0x00007f33ace00000)
       /lib64/ld-linux-x86-64.so.2 (0x00007f33ad9aa000)
       libdl.so.2 => /lib/libdl.so.2 (0x00007f33acbfc000)
       libattr.so.1 => /lib/libattr.so.1 (0x00007f33ac9f8000)

Explain a database

Question
Explain a database in three sentences to your eight-year-old nephew.

Answer:
A database is like a book shelf. You look at all the spines and pick out the book you want to read.

2 eggs and a 100-story building

Question:
You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make in the worst case. You are allowed to break 2 eggs in the process.

Answer:
You can brute force it by starting at 1 and dropping your first egg until it breaks. This takes 100 drops, 1 egg and a good set of lungs... and maybe a defibrillator...

Since we have 2 eggs we can cut it down by wasting 1 egg first.
So divide and conquer, if we start half way and drop 1 egg. Then if it breaks we have to start at the bottom. However if it didn’t break then we can go up to the 75th floor and try agian. repeating this until we break the egg and then going back to the prior floor that was successful and start dropping the second egg until it breaks. This cuts down the number of drops to less than 50.

However as you can see the problem is when the first egg breaks we are back to the brute force method.

So we need to take it slower with the first egg. So lets start a the 10th floor. we drop the egg and if it doesn't break we go to the 20th floor and repeat. If it breaks we go to the 1st floor and brute force it until the 9th floor. Now consider what happens when the egg brakes on the 99th floor we needed to drop the first egg from the 10th-100th in steps of 10. That's 10 drops. Then we need to drop the second egg 91-99 that s 9 more times for a total of 19 drops in the worst case.

However this worst case happens once. Isnt there a way to make the worst case the same for all combination's and maybe reduce the overall worst case.

So with each drop of the first egg the number of drops we should make for the worst case with the second egg decreases by 1. That way the worst case count is constant. So to figure this out we start from the END at the 100th floor.. that drop will tell us if its 99 or 100 with 1 drop of the second egg at 99 to tell them apart. So the prior drop for the first egg should be at the 98th floor and there would be 2 drops of the second egg after it. Get the picture? So the sequence of eggs drops first then second drops work like this;

First egg(Sequence in reverse) => Second sequence egg if the broke

100 => 99
98 => 96,97
95 => 92,93,94
91 => 87,88,89,90
86 => 81,82,83,84,85
80 => 74,75,76,77,78,79
73 => 66,67,68,69,70,71,72
65 => 57,58,59,60,61,62,63,64
56 => 47,48,49,50,51,52,53,54,55
46 => 36,37,38,39,40,41,42,43,44,45
35 => 24,25,26,27,28,29,30,31,32,33,34
23 => 11,12,13,14,15,16,17,18,19,20,21,22
10 => 1,2,3,4,5,6,7,8,9

And the worst case is now 14

Interview tip - Answering Tech Questions

In interviews everyone wants to impress. So when a question of technical nature comes I have the tendency to find and present the best solution to the interviewer. I believe this to be incorrect.

Heres why;

• If you mess up the solution up from nerves or pressure. Then what can the interviewer do but mark you down for it.
• The best solution often takes time to consider and the interviewer is doing what in that time? While you sit around thinking what is the interview thinking about your performance?
• Often if things get to slow the interviewer will start to interfere with you to speed it along. He might offer tips to you, tips that you may of may not have needed, either way he is again likely to take marks off you for having to help you.

So here is an alternate approach, its inspired in part by the the old social engineering tricks made famous by hackers. Consider for a moment what the interviewer is doing, he has a problem and he knows the solution, he also probably knows some tips or key info about the solution that can help you. SO if he isnt talking to you there is no way he can tell you them by accident.

First of all start at brute force. Call it that so the interviewer knows you know better. Talk about it and its negative points and get the interviewer involved get him talking with you about it, make him think that your his fellow peer and you two are talking about a problem at work. Then propose a fix on one of the negative points and slowly change your answer into your ideal one. This gets the interviewer use to the idea that your solution isnt final and its just a discussion point.

Pay close attention to the interviewer, if you propose a fix and the interview was to say "yes but that cant insert with 0(1) complexity" then bingo he might want a data structure like a hash. So again point out a negative of your new solution and suggest a hash and do it gradually so he doesn't catch on that what he said was your key.

Sometimes the interviewer will stay tight lipped in the case of a tight lipped interviewer run down your list of ideas on how to optimize things. Here is mine generally one.

• Divide and Conquer:
  
  • Look at each part of the solution and see if there is any dependence between the parts how is it dependent and can it be broken apart?
  • Start looking at any abnormalities in the computation, if its is excluded does the computation become simpler, can the exception to the rule be added back in in the last moment?
  • Take an array or LUT and divide it in half whats the logic to merge the parts back together after the division?
  • For example take an array and sum all elements but the current element only, then cant you sum the left normally and then the right normally and then add the two sums on either side together of the current point together?
• Inductive repeating computations
  
  • Examine the nature of computation especially ones that are repeated heavily or other pieces of data, reduce it to the induction formula and see if the partial results can be shared out some how.
  • For example sums are an accumulation, and that reduces into a mathematics induction formula; ie Sum(x) = Sum(x-1) + f(x)

Some worked examples:
Here are posts in which i work out a solution to the question with the above rules;
WILL EDIT AND ADD THEM LATER

Interview tip - Company rejections.

If a Company rejects you then you have several choices;
1) Get mad and do something stupid.
2) Cry about it.
3) Be pro-activate and correct the faults, and then keep doing what you love.

I was just recently rejected from a large company that I really wanted to work for and after initial plans to hurt then in a stupid and childish way I calmed down talked it out with a friend, finally I decided to take his advice and follow the better road:

Be Pro-activate look back at the interview contents and figure out why they didn't hire you. Repeat the questions and deeply research the answers. Write it all up so that you can read it in six months and know what happened.

Then contact the recruiter(s)/interviewer(s) of the company that didnt hire you and network with him, ask him if he is interested and send him on yourself own self-review of the interview. Then in a few months pull out dust it off re-read it all do the interview again yourself and THEN reapply for another job at that same company, start with the people how accepted your networking request.

Here is Steve jobs talking about being proactive after being fired
http://www.ted.com/talks/steve_jobs_how_to_live_before_you_die.html

To bet or not to bet:: A Pairs card game

Question
Your friend offers to play a card game with you using a normal deck of 52 cards.  The rules of the game are that you'll turn over two cards at a time.  If the cards are both black, they go into his pile.  if they are both red, they go into your pile.  If there is one red and one black, they go into the discard pile.

You repeat the two card flipping until all 52 cards are used.  Whoever has more cards in their pile at the end wins.  But your friend also wins if there is a tie.  If you win, you get a dollar.  How much would bet on the game?

Answer 1)
First of all its a trick if you get one pair of reds then 1 pair of blacks remain extra in the deck once all the cards are draw the game will always draw and your friend will always win.

That wasn't interesting. SO...

Answer 2)
Assuming that we use a casino deck with a random mix of cards and we draw a random number of cards..

First consider the risk analysis;
P(Win)*Reward - P(Lose)*Bet > 0
Hence: Bet < Reward*P(Win)/P(lose)


Now the odds:
Lets simplify it we divide the 52 cards into 26 pairs. Each pair has four possibles BB, BR, RB, RR. The pairs all have the same chance of occurring.

So in terms of the score
+1 has 25%
0 has 50%
-1 has 25%

Lets start small;
If there is only 1 pair
then you have 25% chance of wining
and 50% + 25% = 75% chance of losing.

Since Bet < Reward*P(Win)/P(lose)
Bet < 1* (1/4)/(3/4)
     < 1/3

Hence you need to bet less than 33 cents against a dollar to come out on top.

As you can see above the only number that really counts is the probability of 0. Since the remaining chance splits evenly between you and your friend

So if there are 2 pairs. the possible 0 end scores become
0,0  => 1 way at 0.5^2
+1,-1 => 2 ways at 0.25^2

The permutations are; +-, -+

Total = 1/2^2 + 2*1/4^2
= 1/4 + 2/16
= 4/16 + 2/16
= 6/16
The remaining chance 10/16 splits evenly resulting in;
Chance to win 5/16
Chance to lose 11/16

Since Bet < Reward*P(Win)/P(lose)
Bet < 1* (5/16)/(11/16)
     < 5/11
     < 0.45
ie bet less than 45 cents to come out on top..

if there are 3 pairs then
000 => 1 way 0.5^3
+0- => nCr(3,1)=3 possible places for +1, leaving nCr(2,1)=2 places for -1
=> hence there are 3*2=6 ways total

They are:
+-0, +0-
0+-, -+0
-0+, 0-+

Total = 1 * 0.5^3 + 6 * 0.25^2 * 0.5
= 1/8 + 6/32
= 1*4/32 + 6*1/32
= 10/32

That leaves 22/32 which splits equally between you and your friend..
Chance to win 11/32
Chance to lose 21/32

Since Bet < Reward*P(Win)/P(lose)
Bet < 1* (11/32)/(21/32)
     < 11/21
     < 0.52
ie bet less than 52 cents to come out on top..


If there are 4 pairs
0000 => nCr(4,0)=1 arrangements of +, and nCr(4,4)=1 for 0s giving a total of  1 way 0.5^3
+00- => nCr(4,1)=4 possible arrangements for the +, leaving nCr(3,2)=3 arrangements for the 0
=> hence there are 4*3 = 12 ways total at 0.5^2 * 0.25^2

+00-, +0-0 ,+-00
0+0-, 0+-0, -+00
00+-, 0-+0, -0+0
00-+, 0-0+, -00+

++-- => nCr(4,2)=6 possible arrangements for +, leaving nCr(3,0)=1 arrangements for the 0
=> hence there are 6*1 ways total at 0.25^4

++--, +-+-, +--+, -++-,-+-+, --++

Total = (1 * 0.5^4) + (12 * 0.5^2*0.25^2) + (6 * 0.25^4)
= 1/16 + 12/(16*4) + 6/256
= 1*16/256 + 12*4/256 + 6*1/256
= (16+48+6)/256
= 70/256

That leaves 186/256 which splits equally between you and your friend..
Chance to win 93/256
Chance to lose 163/256

Since Bet < Reward*P(Win)/P(lose)
Bet < (93/256)/(163/256)
< 93/163
< 0.57
ie bet less than 57 cents to come out on top..

Ok so now lets generalize it. for the number of pairs n the probability of 0;
Denominator is always 4^n
Numerator is always Sum( 4^(n-2i) * nCr(n,i) * nCr(n-i, n-2i ) ) where i = floor(n/2) ... 0

Thus
P(0) = Sum(...) / 4^n

Therefore the
Chance to win = (1 - P(0) ) /2
Chance to lose = (1 - P(0) ) /2 + P(0)
= (1 + P(0) ) /2

Since Bet < Reward*P(Win)/P(lose)
Bet <  (1 - P(0) ) /2 / (1 + P(0) ) /2
<  (1 - P(0) ) / (1 + P(0) )
< (4^n - Sum(...) ) / (4^n + Sum(...))

Hence with the 26 pairs case the p(0) becomes 0.11 and the bet increases to < 0.80  cents

pairs	p(0)	Bet
1	0.5	0.333
2	0.375	0.4545
3	0.3125	0.52381
4	0.273438	0.570552
5	0.246094	0.605016
6	0.225586	0.631873
7	0.209473	0.653613
8	0.196381	0.671709
9	0.185471	0.687084
10	0.176197	0.700395
13	0.154981	0.73163
16	0.13995	0.754463
19	0.128585	0.77213
22	0.119604	0.786346
26	0.110116	0.801613

Bit twidding vs lookup tables

In semiconductor and RTL design using a pipeline of operations is much faster than a LUT(Look up table). However in software the result is flipped and small scale LUTs cut the complex sequence of operations to a single simplified action. In short memory lookup tables are generally much faster despite the chance of cache and memory glitches. Since im a semiconductor background the result always seems to surprise me when I revisit it.

The output is

speed of twiddling: 1482
speed of a lookup table: 874

The test code was:

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

// ********************* BIT TWIDDLER ********************* //

#define SUM_MASK1 0x55555555
#define SUM_MASK2 0x33333333
#define SUM_MASK3 0x07070707
#define SUM_MASK4 0x000f000f
#define SUM_MASK5 0x0000001f

unsigned int SumOfOnesTwiddle(unsigned int x)
{
  x = (SUM_MASK1 & (x >>  1)) + (SUM_MASK1 & x);
  x = (SUM_MASK2 & (x >>  2)) + (SUM_MASK2 & x);
  x = (SUM_MASK3 & (x >>  4)) + (SUM_MASK3 & x);
  x = (SUM_MASK4 & (x >>  8)) + (SUM_MASK4 & x);
  x = (SUM_MASK5 & (x >> 16)) + (SUM_MASK5 & x);

  return x;
}

void SumOfOnesTwiddleArray(unsigned int* in, unsigned int* out, unsigned int size)
{
  for(int i=0;i<size;i++)
    out[i] = SumOfOnesTwiddle(in[i]);
}

// ********************* LOOKUP TABLE ********************* //

#define TABLE_SIZE  256
unsigned int table[TABLE_SIZE];

void computeTable()
{
  for(int i=0; i<TABLE_SIZE; i++)
      table[i] = SumOfOnesTwiddle(i);
}

unsigned int SumOfOnesTable(unsigned int x)
{
  return  table[(x    ) & 0xff] +
          table[(x>>8 ) & 0xff] +
          table[(x>>16) & 0xff] +
          table[(x>>24) & 0xff];
}

void SumOfOnesTableArray(unsigned int* in, unsigned int* out, unsigned int size)
{
  for(int i=0;i<size;i++)
    out[i] = SumOfOnesTable(in[i]);
}

//testing

template<class itor>
void printOut(itor start, itor end)
{
  cout << hex << "0x";
  copy (start, end, ostream_iterator<int>(cout, " 0x"));
  cout << endl << endl;
}

#define SIZE 5000
int main()
{
  unsigned int indata[SIZE];
  unsigned int outdata[SIZE];
  unsigned int outdata2[SIZE];

  clock_t start_time, end_time;
  computeTable();

  srand(time(NULL));
  for(int i=0;i < SIZE; i++)
    indata[i] = rand();

  printOut(indata, indata+SIZE);
  SumOfOnesTwiddleArray(indata, outdata, SIZE);
  SumOfOnesTableArray  (indata, outdata2, SIZE);
  printOut(outdata,  outdata+SIZE);
  printOut(outdata2, outdata2+SIZE);

  for(int i=0;i < SIZE; i++)
    if(outdata[i] != outdata2[i])
       cout << "BUG!" << endl;

  start_time = clock();
  for(int i=0;i < SIZE; i++)
    SumOfOnesTwiddleArray(indata, outdata, SIZE);
  end_time = clock();

  cout << dec << "speed of bit twiddling: " << (end_time - start_time) << endl;

  start_time = clock();
  for(int i=0;i < SIZE; i++)
    SumOfOnesTableArray(indata, outdata, SIZE);
  end_time = clock();
  cout << dec << "speed of a lookup table: " << (end_time - start_time) << endl;

}