DCODERS

How do I reset a lost administrative password in UBUNTU?

2013-09-14T04:30:00.001-07:00

How do I reset a lost administrative password in UBUNTU?

How do I reset a lost administrative password?

By default the first user's account is an administrative account, so if the UI is prompting you for a password it's probably that person's user password. If the user doesn't remember their password you need to reset it. To do this you need to boot into recovery mode.

Boot up the machine, and after the BIOS screen, hold down the left Shift key. You will then be prompted by a menu that looks something like this:

I've noticed on some systems that timing when to hit the left Shift key can be tricky, sometimes I miss it and need to try it again.

Hit the down arrow until you select the 2nd entry from the top (the one with the recovery mode in the description) and then hit Enter.

Now you should see this menu:

Using the arrow keys scroll down to either root or netroot (doesn't matter in this case) and then hit Enter.

You should now see a root prompt, something like this:

root@ubuntu:~#

At this stage it is possible you have a read-only filesystem. You have to remount it with write permissions:

mount -rw -o remount /

Now we can set the user's password with the passwd command. (In this example I will use jorge as the example, you need to substitute whatever the user's username is):

passwd navneet

Enter new UNIX password:

Retype new UNIX password:

passwd: password updated successfully

root@ubuntu:~#

Type in what you want the new password to be at the prompt. After it's successful reboot the machine and the user will be able to log in with their new password.

Recovery Mode documentation
Lost password documentation

Input Taking Strategies

2013-09-01T17:46:00.000-07:00

Input Taking Strategies

Judging by some of the submissions we receive most people seem to be getting the programming approach right on many of the problems, but fumble when it comes to handling the sometimes tricky input descriptions that the problems have. Here we shall see methods to handle some of the more common (and uncommon) input specifications of problems.

I. Single test case, number of inputs specified

This is as simple as it can get; a single test case with the number of inputs following specified.

Example:

Input consists of a single test case, beginning with a number N, specifying the number of inputs to follow.

Sample Input:

[C++ Code]

int N = 0;

cin >> N;

for (int i = 0; i < N; i++)

{

&bsp;	int val;
	cin >> val;
}

[C++ Code]

int N = 0;

cin >> N;

while (N--)

{

int val;

cin >> val;

}

[C Code]

int N = 0;

scanf("%d", &N);

for (int i = 0; i < N; i++)

{

int val;

scanf("%d", &val);

}

[C Code]

int N = 0;

scanf("%d", &N);

while (N--)

{

int val;

scanf("%d", &N);

}

Note that cin and scanf ignore whitespace. So the above code would work even if more than one input were on the same line, as follows:

Sample Input

5 1 2 3

4 5

II. Multiple test case, number of inputs for each test case specified

In this case, each test case specified the number of inputs in it at the beginning, but there can be multiple test cases, the count of which is not specified.

Example:

Input consists of a multiple test cases, each beginning with a number N, specifying the number of inputs in that test case.

Sample Input:

Here, a test case may be followed by either another test case, or EOF (End-Of-File), which is a special character that signals the end of the input (on most implementations it is -1). You can send EOF on the console with Ctrl-Z. So what we have to do here is take input until EOF is encountered. Let’s see this in action:

[C++ Code]

int N = 0;

while (cin >> N)

{

for (int i = 0; i < N; i++)

{

int val = 0;

cin >> val;

}

[C Code]

int N = 0;

while (scanf("%d", &N) != EOF)

{

for (int i = 0; i < N; i++)

{

int val = 0;

scanf("%d", &val);

}

III. Inputting strings - whitespace separated words

Handling strings can often be tricky. Let’s consider the case where we simply want to input space separated strings (words).

Example:

Input consists of a number of space separated words.

Sample Input:

Association for Computing Machinery

[C++ Code]

char str[64] = { 0 };

while (cin >> str)

cout << str << endl;

[C Code]

char str[64] = { 0 };

while (scanf("%s", str))

printf("%s\n", str);

IV. Inputting strings - lines of strings

In this case you have to read each line of text, terminated by '\n'.

Example:

Input consists of multiple lines of text.

Sample Input:

Association for Computing Machinery

a club dedicated

to the promotion of computing

as a profession and

science

[C++ Code]

char str[64] = { 0 };

while (cin.getline(str, 64))

cout << str << endl;

[C Code]

char str[64] = { 0 };

while (fgets(str, 64, stdin)) // fgets appends the '\n' to the

string

printf("%s", str);

Sometimes you may find it useful to read a line of text one character at a time...

[C++ Code]

char str[64] = { 0 };

int inp = 0;

while ((inp =	cin.get()) != EOF)	// There is a reason why int
is used where there	can be a potential	EOF

// The reason is given in

Kernighan & Ritchie

{

int i = 0;

str[i] = inp;

while ((str[++i] = cin.get()) != '\n');

str[i] = 0;

cout << str << endl;

}

[C Code]

char str[64] = { 0 };

int inp = 0;

while ((inp = getchar()) != EOF)

{

int i = 0;

str[i] = inp;

while ((str[++i] = getchar()) != '\n');

str[i] = 0;

cout << str << endl;

}

V. Reading formatted input

Often you get input specifications where the input is given in a particular format. For example, you may have to read a date given in the following format: dd/mm/yyyy

C comes in very handy for the above situation. Note that you can use the powerful formatted I/O functions of C in C++ by including <cstdio>.

[C/C++ Code]
#include <cstdio>	//	If	you	are	using	C++
#include <stdio.h>	//	If	you	are	using	C
...

int d, m, y;

scanf("%d/%d/%d", &d, &m, &y);

VI. Really Tricky Inputs

Example:

Input consists of multiple test cases. Each test case consists of a list of numbers on a single line. The count of numbers per line is not specified and may vary from line to line.

Sample Input:

1 2 3 4 5

6 7 8

9 10 11 23

100 500 600

This one is really tricky. If you are not familiar with some of the less known functions of &t;iostream> or <stdio.h>, your first approach might be to read one character at a time, if it is a digit you have got the beginning of a new number and continue reading characters and appending to the number till you hit whitespace, skip all the whitespace, read next digit, and so on... until you read '\n' which indicates the end of a test case. This really dirty approach might look something like this:

[C Code]

int N = 0;

int numbers[64] = { 0 };

int current = 0;

int temp = 0;

while ((current = getchar()) != EOF)

{

	N = 0;
	do
&nbp;	{
	while (!isdigit(current) && current != '\n')
	current = getchar();
	if (current == '\n')
	break;
	current -= '0';
	while (isdigit(temp = getchar()))
	current = current * 10 + temp - '0';
	numbers[N++] = current;
	} while (1);
}

Really ugly, right? Fortunately, C gives us a way to solve this problem very elegantly. Check out the neat code below:

[C Code]

int numbers[64] = { 0 };

char str[128] = { 0 };

int N = 0;

int len = 0;

int n = 0;

while (fgets(str, 128, stdin))

{

len = 0;

N = 0;

while (sscanf(str + len, "%d%n", &numbers[N], &n) != EOF)

{

len += n;

N++;

}

%n is a little known specifier in scanf that returns the number of bytes read as input till the point where it is specified. sscanf is a function that reads input from a specified string. Its output counterpart is sprintf. The rest should be easy to understand.

C++ also gives us a way to do this using streams. It is much more elegant and intuitive but we will not be explaining it here as it is beyond the scope of this tutorial. Look up "string" and "stringstream" classes in the STL (Standard Template Library). The code is as follows:

[C++ STL Code]

#include <string>

#include <sstream>

...

string str;

int numbers[64] = { 0 };

int N = 0;

while (getline(cin, str))

{

N = 0;

stringstream in(str);

while (in >> numbers[N])

N++;

}

Master these techniques and input taking will no longer be a problem for you. Good luck!

Permutations of Binary Search tree

2013-08-26T03:09:00.000-07:00

Given an array of integers arr = [5,6,1].

When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.

Now if our input is changed to [5,1,6], still our BST structure will be identical.

So given an array of integers, how to find the number of different permutations of the input array that results in the identical BST as the BST formed on the original array order?

Startegy:

Your question is equivalent to the question of counting the number of topological orderings for the given BST.

For example, for the BST

the set of topological orderings can be counted by hand like this: 10 starts every ordering. The number of topological orderings for the subtree starting with 20 is two: (20, 15, 30) and (20, 30, 15). The subtree starting with 5 has only one ordering: (5, 7). These two sequence can be interleaved in an arbitrary manner, leading to 2 x 10 interleavings, thus producing twenty inputs which produce the same BST. The first 10 are enumerated below for the case (20, 15, 30):

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

The case (20, 30, 15) is analogous --- you can check that any one of the following inputs produces the same BST.

This examples also provides a recursive rule to calculate the number of the orderings. For a leaf, the number is 1. For a non-leaf node with one child, the number equals to the number of topological orderings for the child. For a non-leaf node with two children with subtree sizes |L| and |R|, both having l and r orderings, resp., the number equals to

  l x r x INT(|L|, |R|)

Where INT is the number of possible interleavings of |L| and |R| elements. This can be calculated easily by (|L| + |R|)! / (|L|! x |R|!). For the example above, we get the following recursive computation:

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

Useful Link:

http://stackoverflow.com/questions/1701612/permutations-of-bst?rq=1

l x r x INT(|L|, |R|) comes from (1) "l" different ways to order the sequence that produces the left subtree, (2), "r" different ways to order the sequence that produces the right subtree, and (3) INT(|L|, |R|) different ways to mix those two sequences, i.e. interleave them. INT(a,b) = (a+b)!/(a! b!) because among all interleavings of a+b elements, we are interested only in those where the sequence of elements a has a fixed ordering, ditto for sequence of elements b, hence divide by a! and b! separately.


#include <vector>
#include <iostream>

using namespace std;

int factorial(int x) {
  return (x <= 1) ? 1 : x * factorial(x - 1);
}

int f(int a, int b) {
  return factorial(a + b) / (factorial(a) * factorial(b));
}

template <typename T>
int n(vector<T>& P) {
  if (P.size() <= 1) return 1;
  vector<T> L, R;
  for (int i = 1; i < P.size(); i++) {
    if (P[i] < P[0])
      L.push_back(P[i]);
    else
      R.push_back(P[i]);
  }
  return n(L) * n(R) * f(L.size(), R.size());
}

int main(int argc, char *argv[]) {
  vector<int> a = { 10, 5, 7, 20, 15, 30 };
  cout << n(a) << endl;
  return 0;
}

alerts of the coding contests via sms or email...

2013-08-26T01:44:00.000-07:00

Add Programming contest calender to ur Google Calendar With these One Click Links :

HackerRank : Hackerrank
Top Coder : Topcoder
CodeForces : CodeForces
Code Chef : Codechef

Customize your notifications in google calender

Google Calendar offers different options for receiving event reminders. You can choose to receive your event reminders via SMS messages, emails, or popups within Google Calendar itself.

Here's how you can customize your reminder settings:

In the calendar list on the left, click the down-arrow button next to the appropriate calendar, then select Reminders and notifications.

In the Event reminders section, select the reminder method from the drop-down menu and enter the corresponding reminder time (between five minutes and four weeks). If you'd like to add additional default reminders, simply click Add a reminder.

You can also choose to be notified of specific activities on the calendar by selecting the appropriate options in the Choose how you would like to be notified section.

Click Save.

So that you do not miss any contest...

So much with Binary search tree...

2013-08-16T12:21:00.000-07:00

A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order:

for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>).

Basic structure of a node of BST :-

struct node {

int data;

struct node* left;

struct node* right;

}

Download it here

Is this how u allocate memory!!

2013-08-15T05:52:00.000-07:00

Flexibility in allocation in C...

One of the reasons why the C programming language is so popular is the flexibility of its use for memory management. Programmers have opportunities to control how, when, and where to allocate and deallocate memory. Memory is allocated statically, automatically, or dynamically in the C programming language.

Static variables and global variables are static-duration variables, which are allocated along with the

executable code of the program and persist during the execution of the application. When a local variable is declared as static inside a function, it is initialized only once. Whatever values the function puts into its static local variables during one call will be present when the function is called again.

The following is a typical interview question about static local variables: What is the output when the function test executes?

C Code with Static Variables :-

int hasStatic(int n) {

static int x = 0;

x += n;

return x;

}

void test(){

int sum;

sum = 0;

for(int i = 1; i <= 4; ++i)

sum += hasStatic(i);

printf("Result of sum is %d.\n", sum);

}

The variable x in the function hasStatic is declared as static. When the function is called the first

time with a parameter 1, the static variable x is initialized as 0, and then set to 1. When the function is

called the second time with a parameter 2, it is not initialized again and its value 1 persists. It becomes 3 after execution. Similarly, its value becomes 6 and 10 after execution with parameters 3 and 4. Therefore, the result is the sum 1+2+6+10=19.

Automatic-duration variables, also called local variables, are allocated on the stack. They are allocated and deallocated automatically when the program execution flow enters and leaves their scopes. In the sample code below, there is a local array str in the function allocateMemory. What is the problem with it?

C Code to Allocate Memory :-

char* allocateMemory() {

char str[20] = "Hello world.";

return str;

}

void test() {

char* pString = allocateMemory();

printf("pString is %s.\n", pString);

}

Because the array str is a local variable, it is deallocated automatically when the execution flow leaves the function allocateMemory. Therefore, the returned memory to pString in the function test is actually invalid, and its content is somewhat random.

One limitation of static-duration and automatic-duration variables is that their size of allocation is

required to be compile-time constant. This limitation can be avoided by dynamic memory allocation in which memory is more explicitly, as well as more flexibly, managed. In the C programming language, the library function malloc is used to allocate a block of memory dynamically on the heap, where size is specified at runtime. This block of memory is accessible via a pointer that malloc returns. When the memory is no longer needed, the pointer should be passed to another library function, free, which deallocates the memory in order to avoid memory leaks.

The function allocateMemory below utilizes the function malloc to allocate memory

dynamically. What is the problem in it?

C Code to Allocate Memory :-

void allocateMemory(char* pString, int length) {

pString = (char*)malloc(length);

}

void test() {

char* pString = NULL;

allocateMemory(pString, 20);

strcpy(pString, "Hello world.");

}

The parameter pString in the function allocateMemory is a pointer, and the string content it points to

can be modified. However, the memory address it owns cannot be changed when the function

allocateMemory returns. Since the input parameter pString of allocateMemory in the function test is NULL, it remains NULL after the execution of allocateMemory, and it causes the program to crash when the NULL address is accessed in test. In order to fix this problem, the first parameter of allocateMemory should be modified as char** pString.

Enjoyy...

Playing around with some macros...

2013-08-15T05:22:00.000-07:00

C Code with Macros :-

#define SQUARE(x) (x*x)

void test() {

printf("Square of (3+4) is %d.\n", SQUARE(3+4));

}

The result of 3+4 is 7, and the square of 7 is 49. However, 49 is not the result of SQUARE(3+4). Macros are substituted by the preprocessor, so SQUARE(3+4) becomes 3+4*3+4, which is actually 19. In order to make the result as expected, the macro should be modified to #define SQUARE(x) ((x)*(x)).

Even in the revised version of macro SQUARE, its result might look surprising if it is not analyzed carefully in some cases.

For instance, what are the results of x and y after the code below is executed?

#define SQUARE(x) ((x)*(x))

void test() {

int x = 5;

int y = SQUARE(x++);

printf("Result of x is %d, y is %d.\n", x, y);

}

It looks like that the variable x increases only once in the code above. However, when the macro is

substituted, the variable y is assigned as ((x++)*(x++)). The result of y is 25, and x becomes 7 because it increases twice.

Enjoyyy...

What is the size of a EMPTY class!!!

2013-08-15T05:04:00.001-07:00

C++ Concepts

The most popular questions in this category concern the keyword sizeof.

For instance, the following dialog is repeated again and again in many interviews:

Interviewer: There is an empty class, without any member fields and functions inside its definition.

What is the result of sizeof for this class?

Candidate: It is 1.

Interviewer: Why not 0?

Candidate: The size seems to be 0 since the class is empty without any data. However, it should

occupy some memory; otherwise, it cannot be accessed. The size of memory is decided

by compilers. It occupies 1 byte in Visual Studio.

Interviewer: What is the result of sizeof if we add the constructor and destructor functions in the

class?

Candidate: It is also 1. The addresses for functions are irrelevant to instances, and compilers do not

add any data in instances of this class.

Interviewer: How about declaring the destructor function as a virtual function?

Candidate: When a C++ compiler sees a virtual function inside a class, it creates a virtual function

table for the class and adds a pointer to the table in each instance. A pointer in a 32-bit

machine occupies 4 bytes, so the result of sizeof is 4. The result on a 64-bit machine is 8

because a pointer occupies 8 bytes there.

The size of the empty class is always ONE and not ZERO. This is because of below reasons 1. Every object should have some address location to identify, independent of the no.of member variables in the class. Generally the size of the object is the sum of the member variables in the class. if no data is there, one byte of memory allocated to the object to identify. this will help to not conflicting with other empty objects. 2. One more logical reason is that Some times we will use the sizeof() operator in division operation like X%sizeof(emptyclass) and if the value of empty class is zero , application/program will crash.

Hope U liked it...

So much with linked list..

2013-08-13T12:40:00.000-07:00

Linked list

General structure and functions :-

  

struct node
{
    int x;
    node* next;
};
 
class llist
{
        node *list;
public:
        llist();
        void addnode(int);
        void print();
        void count(int x);
        void getnth(int x);
        void getnth1(int x);
        void dellist();
        int pop();
        void insertnth(int,int);
        void sortedinsert(int);
        void insertsort();
        void append(llist&);
        void frontbacksplit(llist&,llist&);
        void removeduplicates();
        void movenode(llist&);
        void alternatingspilt(llist&,llist&);
        void sufflemerge(llist&,llist&);
        void sortedintersection(llist&,llist&);
        void reverse2();
        void reverse();
};

Link to Download

Topcoder-588 Div-2 Easy-250

2013-08-12T12:16:00.000-07:00

Topcoder-588 Div-2 Easy-250

Simple ad-hoc problem.. One should get logic just by reading the problem statement..

problem statement

My solution:-

Another easier way :-

Regarding any doubt.. Don't forget to comment..

nCr using DP..

2013-08-12T07:37:00.002-07:00

Calculate ⁿC_r with out having overflow when it is guaranteed that the final result will not overflow:

From pascal's triangular relation, we get,
ⁿC_r = ^n-1C_r + ^n-1C_r-1

Using this recursive formula directly will lead the program to exceed the time limit, as this may calculate the same value for many times which is un-necessary and we can remove this part by saving the states which means by using dynamic programming concepts.

In this formulation, one thing is to be noted that n and r keep decreasing, and sometimes is is possible that n becomes smaller than r. So considering these cases we get our base conditions for the recursive formula.

We know,
ⁿC_n = 1
ⁿC₁ = n
ⁿC₀ = 1
and
ⁿC_r = ^n-1C_r + ^n-1C_r-1

So, we can build the recursive function as follows:


function nCr(n, r):
    if n == r:
        return 1
    if r == 1:
        return n
    if r == 0:
        return 1
    return nCr(n-1, r) + nCr(n-1, r-1)

Now, to reduce recursive steps, we maintain a table for saving the values of ⁿC_r of intermediate steps. So, when we face a sub-problem which is already solved, we can look up its value from the pre-calculation table.


table dp[N][R]

function nCr(n, r):
    if n == r:
        dp[n][r] = 1
    if r == 1:
        dp[n][r] = n
    if r == 0:
        dp[n][r] = 1
    if dp[n][r] is not yet calculated:
        dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1)
    return dp[n][r]

Here is a sample code written in C++ which demonstrates the idea. (It is assumed that MAX N is 65 and N >= R).

GCD really!!!

2013-08-12T06:17:00.002-07:00

Welcome Dcoders

2013-08-12T05:40:00.000-07:00

DCODERS

How do I reset a lost administrative password in UBUNTU?

How do I reset a lost administrative password?

Input Taking Strategies

Permutations of Binary Search tree

alerts of the coding contests via sms or email...

Add Programming contest calender to ur Google Calendar With these One Click Links :

Customize your notifications in google calender

So that you do not miss any contest...

So much with Binary search tree...

Is this how u allocate memory!!

Flexibility in allocation in C...

Playing around with some macros...

What is the size of a EMPTY class!!!

So much with linked list..

Linked list

Topcoder-588 Div-2 Easy-250

Topcoder-588 Div-2 Easy-250

nCr using DP..

Calculate nCr with out having overflow when it is guaranteed that the final result will not overflow:

GCD really!!!

Welcome Dcoders

Calculate ⁿC_r with out having overflow when it is guaranteed that the final result will not overflow: