Active Directory

Active Directory (AD) is a directory service that Microsoft developed for Windows domain networks. A server running Active Directory Domain Services (AD DS) is called a domain controller. It authenticates and authorizes all users and computers in a Windows domain type network—assigning and enforcing security policies for all computers and installing or updating software. For example, when a user logs into a computer that is part of a Windows domain, Active Directory checks the submitted password and determines whether the user is a system administrator or normal user. Also, it allows management and storage of information at admin level and provides authentication and authorization mechanisms and a framework to deploy other related services (AD Certificate Services, AD Federated Services, etc.).

Active Directory is an integral part of the Windows 2000 architecture. Like other directory services, such as Novell Directory Services (NDS), Active Directory is a centralized and standardized system that automates network management of user data, security, and distributed resources, and enables interoperation with other directories. Active Directory is designed especially for distributed networking environments.

Active Directory provides a common interface for organizing and maintaining information related to resources connected to a variety of network directories. The directories may be systems-based (like Windows OS), application-specific or network resources, like printers. Active Directory serves as a single data store for quick data access to all users and controls access to users based on the directory's security policy.

Active Directory features include:

• Support for the X.500 standard for global directories

• The capability for secure extension of network operations to the Web

• A hierarchical organization that provides a single point of access for system administration (management of user accounts, clients, servers, and applications, for example) to reduce redundancy and errors

• An object-oriented storage organization, which allows easier access to information

• Support for the Lightweight Directory Access Protocol (LDAP) to enable inter-directory operability

• Designed to be both backward compatible and forward compatible.

Active Directory (AD)

     Active Directory provides the following network services:

• Lightweight Directory Access Protocol (LDAP) - An open standard used to access other directory services

• Security service using the principles of Secure Sockets Layer (SSL) and Kerberos-based authentication

• Hierarchical and internal storage of organizational data in a centralized location for faster access and better network administration

• Data availability in multiple servers with concurrent updates to provide better scalability

Active Directory is internally structured with a hierarchical framework. Each node in the tree-like structure is referred to as an object and associated with a network resource, such as a user or service. Like the database topic schema concept, the Active Directory schema is used to specify attribute and type for a defined Active Directory object, which facilitates searching for connected network resources based on assigned attributes. For example, if a user needs to use a printer with color printing capability, the object attribute may be set with a suitable keyword, so that it is easier to search the entire network and identify the object's location based on that keyword.

A domain consists of objects stored in a specific security boundary and interconnected in a tree-like structure. A single domain may have multiple servers - each of which is capable of storing multiple objects. In this case, organizational data is stored in multiple locations, so a domain may have multiple sites for a single domain. Each site may have multiple domain controllers for backup and scalability reasons. Multiple domains may be connected to form a Domain Tree, which shares a common schema, configuration and global catalog (used for searching across domains). A Forest is formed by a set of multiple and trusted domain trees and forms the uppermost layer of the Active Directory.

Novell's directory service - an Active Directory alternative - contains all server data within the directory itself, unlike Active Directory.

References:

https://en.wikipedia.org/wiki/Active_Directory

https://www.techopedia.com/definition/25/active-directory

http://serverfault.com/questions/402580/what-is-active-directory-domain-services-and-how-does-it-work

Two circles have their centers 21 cm apart. The radii of the circles are 10 cm and 17 cm. Find the length (in cm) of the common chord of the two circles.

 if two circles having radii a and b with the distance between them as c,
Length of common chord= 2* Sqrt [ a^2 - ((a^2+c^2-b^2)/2c)^2]

Ans. 84

If the HCF of two number is 23 and the LCM is 4186, one of the two numbers is one of the following: 

a) 276 b) 300 c) 322 d) 345. Which one is it?

Ans. c) 322 

 Both number should be divisible by its HCF and LCM should be divisible by  both the numbers whose  HCF and LCM are to determine. 
 a) 276%23=0
      4186%276=46

b)300%23=1
  4186%300=286

c)322%23=0
 4186%322=0

d)345%23=0
 4186%345=46

How do I find two numbers when I know that their LCM is 36 and HCF is 15?

If the HCF of the two numbers say x and y is 15; the numbers can be represented as following:

x = 15a and y = 15b where a and b are positive integers

It is given that LCM of x and y is 36

Now LCM (x,y) * HCF (x,y) = x * y

Hence, 36 * 15 = 15a * 15b

540 = 225*a*b

or 2.4 = a*b

The product of two integers cannot be 2.4 hence such two numbers do not exist.

The sum of two numbers is 52 and their LCM is 168. What are the numbers?

As LCM of two numbers is 168 that two numbers must be factors of 168

now think about what are all factors of 168 that are less than 52(because sum of those two is 52)

factors=(2,3,4,6,8,7,8,12,14,24,28,42)

from above factors u have to select two numbers such that sum of two is 52

only possibility is 24+28

What is the difference between two numbers if their LCM is 630 and HCF is 9 and the sum of the two numbers is 153?

Given GCD of two numbers is 9 and LCM is 630.

Let a, b be two numbers
As we know,

LCM × HCF = The product of given numbers

a×b=9×630
Given a+b=153
By using formula
(a-b)^2=(a+b)^2-4×a×b
(a-b)^2=(153^2)-(4×9×630)
(a-b)^2=729
x-y=27
Ans.27

Another Solution:

Let's assume the numbers are 9*a and 9*b (as the hcf is 9).

As we know,

LCM × HCF = The product of given numbers

So, (9*a)*(9*b) = 630*9

So, a*b = 70
Again 9*(a + b)= 153

By solving those two equations, we get either a=10, b=7 or a=7 , b=10
So either way, the two numbers are 90 and 63.

So, $(\mathrm{90}-\mathrm{63})=27$ or the difference between the two numbers is 27.

Ans.27

The LCM of 1, 2, 3, ... 60 is N. What is the LCM of 1, 2, 3, ... 65?

Answer: 61*2*n

We are given LCM (1, 2, 3 ... 60) = n
Now, we need to find out LCM (1, 2, 3... 65)

= LCM (n, 61, 62, 63, 64, 65) 
{The first 60 numbers can be replaced with 'n' as we already know their LCM}

= LCM (n, 61,64) 

{62, 63, and 65 can be broken down into prime factors which are in turn factors of n} 

= 61*2*n  
{61 is a prime number. 64 is 2^6. 2^5 occurs in 32. An extra 2 is required to accommodate it}

= 122n

Explanation:

Lcm of first 60 numbers is n, so we need to consider 5 more numbers 61...65. Lets use prime factorization and try to figure out how inclusion of each of these numbers will affect lcm.
61 - It is a prime number and so it has not been included in n till now. So Lcm of 1...61 become 61*n.
62 - Prime factorization of 62 is 2*31 and both of these numbers are already included in n. So lcm doesn't change by inclusion of 62 and it remains 61*n.
63 - Prime factorization of 63 is 3*3*7 and these numbers are already there in n. In fact 3 is there three times (for 27) and 7 is there two times (for 49). So inclusion of 63 also doesn't change lcm and lcm remain 61*n for numbers 1....63.
64 - Factorization of 64 is 2^6. Now 2^5 is already there in n for 32. So we need to include only one more 2, and lcm of numbers 1..upto 64 becomes 61*2*n.
65 - 65 factorizes as 5*13. Both of these numbers are there in n already and by inclusion of 65, lcm doesn't change. So it remains 61*2*n.

How-many-pairs-of-2-numbers-are-there-whose-LCM-is-N

If N= a^m*b^n *c^o then ordered solution such that LCM = N is (2m+1)*(2n+1)*(2o+1)
Unordered will be (2m+1)*(2n+1)*(2o+1) /2 +0.5

A 4 digit no. is formed using the digits 0,2,4,6,8 without repeating any 1 of them. What is the sum of all such possible no.s?

1)519960 2)402096 3)133320 4)4321302

If you fix 8 as the last digit, you see that there are 4*3*2 ways to complete the number. Thus, 8 appears 24 times as the last digit. By the same logic, if we enumerate all possible numbers using these 5 digits, each number appears 24 times in each of the 4 positions. That is, the digit 8 contributes (24*8+240*8+2400*8+24000*8). In total, we have
(0+2+4+6+8)(24+240+2400+24000)=533280
as our total sum.
In case 4-digit numbers cannot start with 0, then we have over-counted. Now we have to subtract the amount by which we over-counted, which is found by answering: "What is the sum of all 3-digit numbers formed by using digits 2,4,6, and 8?" Now if 8 appears as the last digit, then there are 6 ways to complete the number, so 8 contributes (6*8+60*8+600*8). In total, we have
(2+4+6+8)(6+60+600)=13320.
Subtracting this from the above gives us 519960.

Which is the Smallest number that has 4 prime factors & 48 total factors?

Take first 4 prime numbers as
2^a*3^b*5^c*7^d
Give maximum powers to 2 and 3 to get the minimum number 
(a+1)(b+1)(c+1)(d+1)=48
4*3*2*2=48
a=3 b=2 c=1 d=1

8*9*5*7=2520 Ans.

A ball is dropped from a height of 96 feet and it rebounds 2/3 of the height it falls. If it continues to fall and rebound, find the total distance that the ball can travel before coming to rest? 

a.240 ft b 360 ft c.480 ft d.none of these

Here is a trick if ball rebounds for 2/3 or for any other fraction (p/q) like 3/4, 1/2 or 5/2 
then use this (p+q)*height.
so we get, according to this question,
(2+3)*96= 480 Feet.

Another Trick:

96(1+r)/(1-r)=96(5/3)/(1/3)=480

Power of 2

How do you find out if an unsigned integer is a power of 2?

The trick here is to know that an unsigned integer which is a power of 2 has only one of its bits as 1. So a simple solution would be to loop through the bits and count the number of 1s.

There is another solution which uses bit manipulation.

isPower = (x !=0 && !(x & (x-1)))

x & (x-1) will always give you a 0 if x is a power of 2. !(x & (x-1)) should give us what we want but there is one corner case. If x is 0, then the second term alone would return true when the answer should be false. We need the check to make sure x is not 0.

Reverse a String

First Solution

void reverseString(char* str) { int len, loop;
char temp; len = strlen(str); for(loop = 0; loop < (len / 2); loop++) { temp = str[loop];
str[loop] = str[len - loop - 1];
str[len - loop - 1] = temp; } }

Second Solution

The second solution is slightly better than the first as it does not need the char space. It uses bit manipulation (XOR in this case) to swap the chars in place.

void reverseStringBetter(char* str) { int loop1 = 0, loop2; loop2 = strlen(str) - 1; for (loop1 = 0; loop1 < loop2; loop1++, loop2--) { str[loop1] ^= str[loop2] ; str[loop2] ^= str[loop1] ; str[loop1] ^= str[loop2] ; } }

Number of Ones

Write a function that determines the number of bits set to 1 in the binary representation of an integer.
Going by the brute force approach, it would be easy to come up with the following solution. If the least significant bit of a number is 1, it will return a result of 1 when we AND it with 1. Using this logic, we can shift bits in the number to the right and keep testing if the least significant bit is 1. When there are no 1’s left in the number, it will become zero. 

int numOnesInInteger(int num) { int numOnes = 0; while(num != 0) { if((num & 1) == 1) { numOnes++; } num = num >> 1; } return numOnes; }

Time Complexity: O(n) ==> Where n in the number of bits in the integer.

Improved Solution:

Let’s think, what happens to a number when it we AND it with (number – 1). Let’s take 7 (0111) as an example.

7 & 6 = 0111 & 0110 = 0110 = 6
6 & 5 = 0110 & 0101 = 0100 = 4
4 & 3 = 0100 & 0011 = 0000 = 0

Do you see a pattern yet? Essentially, when you AND a number with (number – 1), the last 1 bit in the number gets set to zero. So if we continue to set every 1 bit in the number to zero, the number will eventually become zero. If we use this logic to count the number of 1s, we have an algorithm that runs in O(m) where m is the number of bits set to 1 in the number. Here’s some code.

int numOnesInInteger(int num) { int numOnes = 0; while(num != 0){ num = num & (num – 1); numOnes++; } return numOnes; }

int main()
{
     int num, count = 0;
     printf(“Enter the number: “);
     scanf(“%d”,&num);
     count = number_of_ones(num);
     printf(“\nNumber of one’s are %d\n”, count);

     return 0;

}

Meaning of “referencing” and “dereferencing”

Referencing means taking the address of an existing variable (using &) to set a pointer variable. In order to be valid, a pointer has to be set to the address of a variable of the same type as the pointer, without the asterisk:

int  c1;
int* p1;
c1 = 5;
p1 = &c1;
//p1 references c1

Dereferencing a pointer means using the *operator (asterisk character) to access the value stored at a pointer. NOTE: The value stored at the address of the pointer must be a value of the same type as the type of variable the pointer "points" to. e.g. *p = *p +1; Note: & is the reference operator and can be read as “address of”.* is the dereference operator and can be read as “value pointed by”.

Search an element in a sorted and rotated array

#include <stdio.h>

int searchElementInRotatedArray(int arr[], int start, int end, int key) {
    while(start < end) {
        int mid = (start + end) / 2;
        if(arr[mid] == key) {
            return 1;
        }
        if(arr[start] <= arr[mid]) {
            if((key >= arr[start]) && (key <= arr[mid])) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            if((key >= arr[mid]) && (key <= arr[end])) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return 0;
}

int main() {
    int len, num;
    printf("Enter Length of Array: ");
    scanf("%d", &len);
    int arr[len];
    printf("Enter Elements of Array: ");
    for(int loop = 0; loop < len; loop++) {
        scanf("%d ", &arr[loop]);
    }
    printf("Enter Element to Search: ");
    scanf("%d", &num);
    (searchElementInRotatedArray(arr, 0, len, num))?printf("Key Found\n"):printf("Key Not Found\n");
    return 0;
}

Solution Using Temporary Array

Input arr[] = [10, 12, 23, 40, 53, 36, 78], d = 2, n =7
1) Store d elements in a temp array
   temp[] = [10, 12]
2) Shift rest of the arr[]
   arr[] = [23, 40, 53, 36, 78, 36, 78]
3) Store back the d elements
   arr[] = [23, 40, 53, 36, 78, 10, 12]

Time complexity O(n)
Auxiliary Space: O(d)

Implementation:

#include <stdio.h>

int main() {
    long num, rot;
    scanf("%ld %ld", &num, &rot);
    unsigned long arr[num];
    unsigned temp[rot];
    for(long loop = 0; loop < num; loop++) {
        scanf("%lu", &arr[loop]);
    }
    for(long loop = 0; loop < rot; loop++) {
        temp[loop] = arr[loop];
    }
    for(long loop = rot; loop < num; loop++) {
        arr[loop - rot] = arr[loop];
    }
    long index = 0;
    for(long loop = (num - rot); loop < num; loop++) {
        arr[loop] = temp[index++];
    }
    for(long loop = 0; loop < num; loop++) {
        printf("%lu ", arr[loop]);
    }
    return 0;
}

Compare two linked lists

int CompareLists(Node *headA, Node *headB)
{
    while((headA != NULL) && (headB != NULL)) {
        if(headA->data != headB->data) {
            break;
        }
        headA = headA->next;
        headB = headB->next;
    }
    if((headA == NULL) && (headB == NULL)) {
        return 1;
    } else {
        return 0;
    }
}

Reverse a Linked-List

void ReversePrint(Node *head)
{
    Node *prev = NULL, *curr = head, *next;
    if(head != NULL) {
        while(curr != NULL) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        while(prev != NULL) {
            printf("%d\n", prev->data);
            prev = prev->next;
        }  
    }
}

What are P, NP, NP-complete, and NP-hard?

Problems in class P can be solved with algorithms that run in polynomial time.

Say you have an algorithm that finds the smallest integer in an array.  One way to do this is by iterating over all the integers of the array and keeping track of the smallest number you've seen up to that point.  Every time you look at an element, you compare it to the current minimum, and if it's smaller, you update the minimum.

How long does this take?  Let's say there are n elements in the array.  For every element the algorithm has to perform a constant number of operations.  Therefore we can say that the algorithm runs in O(n) time, or that the runtime is a linear function of how many elements are in the array.*  So this algorithm runs in linear time.

You can also have algorithms that run in quadratic time (O(n^2)), exponential time (O(2^n)), or even logarithmic time (O(log n)).  Binary search (on a balanced tree) runs in logarithmic time because the height of the binary search tree is a logarithmic function of the number of elements in the tree.

If the running time is some polynomial function of the size of the input**, for instance if the algorithm runs in linear time or quadratic time or cubic time, then we say the algorithm runs in polynomial time and the problem it solves is in class P.

NP

Now there are a lot of programs that don't (necessarily) run in polynomial time on a regular computer, but do run in polynomial time on a nondeterministic Turing machine.  These programs solve problems in NP, which stands for nondeterministic polynomial time.  A nondeterministic Turing machine can do everything a regular computer can and more.***  This means all problems in P are also in NP.

An equivalent way to define NP is by pointing to the problems that can be verified in polynomial time.  This means there is not necessarily a polynomial-time way to find a solution, but once you have a solution it only takes polynomial time to verify that it is correct.

Some people think P = NP, which means any problem that can be verified in polynomial time can also be solved in polynomial time and vice versa.  If they could prove this, it would revolutionize computer science because people would be able to construct faster algorithms for a lot of important problems. 

Ex: Subset Sum, 0-1 knapsack etc.
 
NP-hard

What does NP-hard mean?  A lot of times you can solve a problem by reducing it to a different problem.  I can reduce Problem B to Problem A if, given a solution to Problem A, I can easily construct a solution to Problem B.  (In this case, "easily" means "in polynomial time.")

If a problem is NP-hard, this means I can reduce any problem in NP to that problem.  This means if I can solve that problem, I can easily solve any problem in NP.  If we could solve an NP-hard problem in polynomial time, this would prove P = NP.





Ex: Travelling Salesman, Subset Sum etc.
 
NP-complete

A problem is NP-complete if the problem is both

• NP-hard, and
• in NP.

Note: The interesting observation here is that, we are still unable to find a single problem that is NP, but not NP-Hard.