Tar 101

I keep forgetting the options
http://www.cyberciti.biz/faq/how-do-i-compress-a-whole-linux-or-unix-directory/

Virtual Memory Management in x86

System Developer Manuals:
http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html

Condensed picture:
http://osr507doc.sco.com/en/OSAdminG/addr_trans.html

Some more explanation:
http://www.cs.cmu.edu/~410/doc/segments/segments.html

When is LDT used?
http://en.wikipedia.org/wiki/Local_Descriptor_Table

http://stackoverflow.com/questions/4575032/reason-for-different-segments-in-linux-on-x86

Follow my blog with Bloglovin

Programming Interview Questions

1) Given an integer x and a sorted array a of N distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i] + a[j] == x
http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum

2) Find the starting node of the linked list cycle
http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work
Using this diagram. Let
i = m + p.n + k - m
2i = m + q.n + k - m

k = (q - 2p).n    i.e. a multiple of cycle length

Now, let
k - m + x = n
Then,
k = (q - 2p -1).n + k - m + x
m = (q - 2p -1).n + x

So, if two pointers start at the beginning of the list and the meeting point and move the same number of steps, they will meet at the starting node of the cycle.

3) Given a string find all its permutations:

#include <stdio.h>
#include <string.h>
void perm(char * base, int * res, int pos)
{
int i,j;
for (i = 0; i < strlen(base); i++){
 for (j = 0; j < pos; j++)
   if (i == res[j])
      break;
 if (j==pos){
    res[pos] = i;
    if (pos+1 != strlen(base))
      perm(base, res, pos + 1);
    else{
      for (j = 0; j < strlen(base); j++)
         printf("%c",base[res[j]]);
      printf("\n");
      return;
    }
 }
}
}
int main(){
int i;
char str[10];
int res[10];
printf("Enter a string: ");
scanf("%s",str);
for (i = 0; i < strlen(str); i++)
{
res[0] = i;
perm(str, res, 1);
}
return 0;
}

4) Counting inversions in a array:
http://stackoverflow.com/questions/337664/counting-inversions-in-an-array

5) Find the element appearing more than n/2 times in an array in O(n) time.
http://keithschwarz.com/interesting/code/?dir=majority-element

6) Find the median of two sorted arrays
http://www.youtube.com/watch?v=_H50Ir-Tves

7) Each node of a linked list is of struct data type

struct node {
    struct node *next;
    struct node *what;
    void *data;
};

what is a pointer to a random node in the list. Duplicate the list in O(N) time without using any extra space.

http://stackoverflow.com/questions/1924741/deep-copy-linkedlist-without-destroying-original-list-and-extra-storage-space-u/1924968#1924968

8) Given an array of size N, find the sub-sequence of elements of size L in the array which has the maximum sum in O(N) time.

http://stackoverflow.com/questions/7861387/maximum-contiguous-subsequence-sum-of-at-least-length-l

Cache Basics

For uniprocessor:
http://www.ccs.neu.edu/course/com3200/parent/NOTES/cache-basics.html

What constrains the size of L1 cache?
1) Space constraints - Since L1 is located on CPU chip it needs to small.
2) Larger the cache more is the access latency.
3) Larger cache have more soft errors. We remove ECC bits from L1 cache by keeping it small. This also lowers the latency of L1.

TLB and Page Tables
http://users.dickinson.edu/~braught/courses/cs354f97/Classes/Class17/Class17LN.html

Mbps vs MBps vs MiBps

I forget what is what every year, so this is for future me:
http://en.wikipedia.org/wiki/Data_rate_units