Subtle Secrets – Duty

In an organization of many individuals, we have loads of decisions to be taken. As a responsible organization, we want the right and just decision be taken at each step. For this, we diffuse the responsibility of decision making into multiple sometimes hierarchical set of people. This is what we simply mean by “politics”. Here the idea is that majority of views shall be for the right decision.

However, politics can lead to local optimization decisions if the resources to be distributed becomes less than required. Thus, people tend to take decisions that bring positive outcomes for small set of related people in the organizations misusing the power of decision making.

On an another note, diffusion of responsibilities removes the sense of ownership of an individual on decisions in the organization. This make them feel as they have little to offer beyond following the workflow defined by the organization for getting a particular work done losing any opportunity for creativity and innovation which are seldom appreciated in such environments.

Moreover, the decisions made in organizations are questionable by people in general since the organization is primarily working for the benefit of the public. Fear of being questioned have heavily lead to taking of wrong decisions in diffused power.

So from the technologist viewpoint, we seem to have a trade-off between ensuring efficiency of individual by giving ownership of power in decision making and ensuring correctness in decisions of the organization by diffusion of power.

Rightly said. But as we come to the standstill claiming we have to compromise and there is no other solution, are we right in saying this or should we change the perspective to gain insight and unravel a mysteriously hidden solution for it ?

Yes, sometimes perspectives are the culprit in giving illusions of such obvious deadlocks. A change in perspective alone can explain the mysteries of truth hidden among the daily activities …

So what is the perspective we are talking about for our scenario ? Its called DUTY.

Duty is the sense of selfless responsibility towards higher force. It is here that we forget “local optimization” to benefit particular group and forget “sense of ownership” to work efficiently and know that this is something very much near to humanity to even be “questionable”.

When every individual works with sense of duty, we shall not have any need for trade-off and everything shall happen in the best possible manner since it would be in sync with what has already be destined by Time and hence will also not be questionable to anyone.

This is not a solution to the above problem. This is the removal of the problem as whole and looking at it with a different perspective wherein the problem does not even arise as before.

Thus, it is only when an individual works with sense of duty that the work blossoms and spreads joy to the world …

Yahoo!

My Yahoo! selection experience :

[ Written Test ]
All CS related questions basically from C, Networking and Mathematics

[ Coding Test ]
1. Given N, find next smallest integer greater than N which is a palindrome.
2. Given a binary tree, find its diameter ( maximum number of nodes in path between any leaves )

[ 1st Technical Interview ]
1. Given a string, find the largest palindrome substring
2. What happens when you click on link on browser
3. Explain DNS system
4. Questions on resume, projects, research, interests
5. General discussion on web technologies, distributed systems, scalability, etc
6. Questions on why Yahoo!

[ HR Round ]
1. About myself
2. Why Yahoo!
3. Your plans and goals for long future
4. About interests, resume, projects
5. Some discussion on my background

[ 2nd Technical Interview ]
1. Given a file consisting of lines, each of which contains name of an employee followed by comma and space and then name of manager. The head is such an manager not having any higher manager above him. Find the head.
2. Given a file consisting of many strings, and a small pattern. Print all strings in file in which the pattern occurs.
3. Given a binary tree like organizational chart. CEO at root and he is about to resign. Replace him with either left child or right child depending upon which person has more employees below him in the tree. Design a strategy to make the replacement so that the structure of tree is kept intact.
4. Given a file consisting of lines, each of which contains name of an employee followed by comma and space and then name of organization. Print list of employees from such an organization having more than 100 employees.
5. Why Yahoo! and other general questions
6. Some discussion on my background

Wish all the very best🙂


Vibhaj Rajan (IDD CSE 08)
IIT (BHU) Varanasi

Basic Number Theory

Basic Number Theory Every Programmer Should Know…

http://www.codechef.com/wiki/tutorial-number-theory

The Peano axioms

(i) 0 is a natural number
(ii) Every natural number has a successor, which is also a natural number
(iii) 0 is not the successor of any natural number
(iv) Different natural numbers have different successors
(v) If a set contains the number 0 and it also contains the successor of every number in S, then S contains every natural number.

Fundamental Theorem of Arithmetic and the Division Algorithm

The fundamental theorem of arithmetic states that any integer greater than 1 can be written as a product of prime numbers in a unique way (up to the ordering of prime factors in the product).

The division algorithm states that given two integers a,b (b != 0) there exist two unique integers q and r such that

a = bq + r, 0 <= r < b

q is typically called quotient, whereas r is called remainder. If r = 0, we say that b divides a, and denote it as b|a.

Euclid’s Theorems

First theorem: p | ab => p|a or p | b.
Second theorem : There are infinitely many primes.

GCD, LCM, Bezout’s identity

If gcd(a,b) = d then (a/d, b/d) = 1.

GCD and LCM are related by a very simple equation: (a,b) * [a,b] = ab. This gives a very fast way to calculate LCM of two numbers.

The bezout’s identity states that if d = (a,b) then there always exist integers x and y such that ax+by = d. (Of course, the theory of linear diophantine equations assures existance of infinitely many solutions, if one exists).

Integer Factorization

The most commonly used algorithm for the integer factorization is the Sieve of Eratosthenes. It is sufficient to scan primes upto sqrt(N) while factorizing N.

Linear Congruence Equations

The equations of the form ax ≡ b (mod n) where (x is an unknown integer ) are called linear congruences. Such a congruence will have a solution if and only if there exists an integer x such that n | (ax-b), i.e. ax -b = ny for some integer y, or in other words ax + n(-y) = b.

Chinese Remainder Theorem

In general, a system of linear congruences:
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
x ≡ a3 (mod n3)
….
x ≡ ak (mod nk)

where (ni,nj) = 1 for every ni != nhas a unique solution modulo n where n = n1n2n3…nk.

Let ci= n/ni for every i. Let di be the solution for the congruence cix = 1 (mod ni) such that 0 <= di < ni. (This solution can be found out using Extended Euclid’s algorithm). Then the common solution to the above system of linear equations is given by
c = a1c1d1 + a2c2d2 + … + akckdk

A direct corollary of the Chinese Remainder theorem is as follows: Let n = p1a1 * p2a2 * …. * pkak be the prime factorization of n. Then, for any integers a and b, we have a = b (mod n) iff a = b (mod piai ) for each i.

Quadratic Congruences

Given q and n, if the quation x2 ≡ q (mod n) has a solution, then q is called quadratic residue modulo n. If this equation doesnot have a solution, then q is called “quadratic non residue” modulo n.

Finding whether a quadratic congruence having prime number modulus has a solution or not is somewhat easy: x2 ≡ a (mod p) has a solution only if a(p-1)/2 = 1 (mod p). In such a case, the Shank-Tonelli algorithm can be used to get the solution.

Euler Phi Function

Euler’s Phi function (also known as totient function, denoted by φ) is a function on natural numbers that gives the count of positive integers coprime with the corresponding natural number. Thus, φ(8) = 4, φ(9) = 6 etc. Following properties are worth noting about this function:

a) If p is prime then φ(pk) = (p-1)pk-1
b) φ function is multiplicative, i.e. if (a,b) = 1 then φ(ab) = φ(a)φ(b).
c) The value φ(n) can be obtained by Euler’s formula : Let n = p1a1 * p2a2 * …. * pkak be the prime factorization of n. Then φ(n) = n * (1- 1/p1)) * (1- 1/p2)) * … * (1- 1/pk))

Two important properties of φ(n):

i. aφ(n) ≡ 1 (mod n) whenever (a,n) = 1. Specifically, for a prime p, if p doesnot divide a then ap-1 ≡ 1 (mod p). This specialization is also known as Fermat’s little theorem.
ii. Let d1, d2, …dk be all divisors of n (including n). Then φ(d1) + φ(d2) + … + φ(dk) = n

DIVISOR FUNCTION, SUM OF DIVISORS

The divisior function, denoted by d(n) gives the number of divisors of a natural number. For example, d(18) = 6. Similarly, the sum of divisors function, denoted by σ(n), gives the sum of divisors of n. Thus, σ(18) = 1+2+3+6+9+18 = 39. Following properties are worth nothing about these two functions:

a) If p is a prime, then d(p) = 2. Also, d(pk) = k+1, and σ(p) = p+1
b) If n is a product of two distinct primes, say n = pq, then σ(n) = n+1+(p+q). Also observe that in this case, φ(n) = n+1-(p+q).
c) In general, Let n = p1a1 * p2a2 * …. * pkak . Then d(n) = (a1+1) * (a2+1) * … (ak + 1), and σ(n) is given by the following product: σ(n) = ( (p1(a1+1) – 1) / (p1-1) ) * ( (p2(a2+1) – 1) / (p2-1) ) * … * ( (pk(ak+1) – 1) / (pk-1) )

A number is called “perfect number” if σ(n) =2n. In other words, the sum of proper divisors of a perfect number equals the number itself.

MOBIUS FUNCTION

The mobius function, µ(n) is defined over all positive integers as follows:
µ(n) = 1 if n is square free (i.e. no prime-square divides n) and n has even number of distinct prime factors
µ(n) = -1 if n is square free (i.e. no prime-square divides n) and n has off number of distinct prime factors
µ(n) = 0 if n is not square free, i.e. when n is divisible by a square.

Mobius function is multiplicative, i.e. when a and b are coprime, µ(ab) = µ(a)*µ(b).

A useful formula to calculate Euler’s totient function can be given in terms of mobius function: Let d1, d2, …dk be all divisors of n. Then φ(n) = (d1 * mu (n/d1) ) * (d2 * µ(n/d2) ) * …. * (dk * µ(n/dk) )

Web Content Filtering with OpenDNS

The following post describes how we have setup web content filtering in IIT BHU VPN service using OpenDNS cloud service.

First, we register on OpenDNS for free Home service.
http://www.opendns.com/home-solutions/parental-controls/

After successful registration and confirmation, we get support on how to setup OpenDNS using named/bind or any other hardware/software.

We then setup a network and corresponding web content filtering options using categories specified by OpenDNS.

We now are ready to add OpenDNS IP addresses as our primary DNS servers in the configuration.

# edit resolv.conf
sudo vim /etc/resolv.conf

nameserver 208.67.222.222
nameserver 208.67.220.220

# set immutable attribute on the file
sudo chattr +i /etc/resolv.conf

# restart network
sudo service network restart

Resize Logical Volume in Linux

The following had worked in Centos 6.2 Linux with ext4 file systems :

# unmount volume
umount /home

# check file system in volume
e2fsck -f /dev/mapper/vg_webitsitbhu-lv_home

# resize file system in volume, 524288 blocks = 2GB for 4K block size
resize2fs /dev/mapper/vg_webitsitbhu-lv_home 524288

# reduce volume size
lvreduce -L-4G /dev/mapper/vg_webitsitbhu-lv_home

# mount the volume
mount /home

# extend the other volume
lvextend -L +4G /dev/mapper/vg_webitsitbhu-lv_root

# resize file system in volume
resize2fs /dev/mapper/vg_webitsitbhu-lv_root

# done, check new volume sizes
df

Filesystem                                                Size    Used      Avail         Use%         Mounted on
/dev/mapper/vg_webitsitbhu-lv_root         49G     34G       15G           70%                  /
tmpfs                                                        7.8G    284K      7.8G           1%             /dev/shm
/dev/sda1                                                 485M    86M       374M          19%              /boot
/dev/mapper/vg_webitsitbhu-lv_home     7.0G    411M      6.2G           7%              /home

References :
[1] http://tldp.org/HOWTO/LVM-HOWTO/reducelv.html
[2] http://linuxconfig.org/Linux_lvm_-_Logical_Volume_Manager#8-extend-logical-volume