Software engineering interview questions – Intersection of two arrays

A few approaches are presented herein for solving the question on computing the intersection of two arrays. What follows is also attached in the pdf format here – algorithm1

Software Engineering Interview Questions: C++ – constructor, copy constructor, assignment – 2

This is continued from the previous post on constructors, copy constructors and copy assignment operators in C++.

Software Engineering Interview Questions: C++ – constructor, copy constructor and assignment – 1

The following two posts cover the topic of constructors, copy constructors and copy assignment operators in C++. At the end of reading these posts, you should be able to answer the following questions:

1. What is the difference between shallow copy and deep copy?

2. What are the functions C++ provides to our classes by default?

3. When should we provide our own copy constructor and copy assignment operator?

The posts have been taken from a file I had written for aiding in preparation for software engineering interviews. The style of exposition in the posts would hence exhibit a marked difference from that of a textbook, and orient itself more towards an informal synopsis written with the express purpose of aiding the understanding of the reader, who is assumed to be familiar with certain C++ concepts.

The pdf file which forms the basis for these two posts is attached here -  C-tutorials

Strings in C++ : Find the first non-repeated character in a string – 3

APPROACH 3

We can approach this problem using a lookup table. Using a lookup table, the running time can be significantly reduced.

For simplicity, let us assume that our input string can only contain characters from the English alphabet i.e. only 26 characters are possible, though each may be repeated any number of times.

The idea is to construct a lookup table having space for 26 entries. Each entry in the lookup table corresponds to a character in the input string.

We will proceed as follows— Create a lookup table of size 26. Initialize each entry in the lookup table to be 0. The entries in the lookup table correspond to the 26 characters in the English alphabet, and are equal to the number of times that particular character appears in the input string.

Traverse the input string. Say the string that you are given is “elephant”. The first character is ‘e’. Go to the lookup table entry corresponding  to ‘e’ and increment the count in that entry by 1. But which is the entry in the lookup table corresponding to ‘e’?

Let us call the lookup table L.

L[0] will store the count of ‘a’. L[1] will store the count of ‘b’. … L[25] will store the count of ‘z’.

So, for ‘e’, we go to L[4] and increment that count by 1.

Now, once we have finished traversing the string, and have the counts of all characters available to us in L, we need to output the first non-repeated character.

For this, we proceed as follows:

Traverse the input string again. Take the first character in the input string. Go to the entry corresponding to that character in L. (Note that we can do this in O(1) time.) Check if the count is 1. If so, output it. Else, go to the next character in the input string, and repeat the same procedure.

————

Now, what would be the running time of this procedure?

Initializing the look up table takes O(1) [since the size of the lookup table is a constant.]

Traversing the string to populate the lookup table with appropriate counts takes O(n) time. (n is the length of the input string.)

Traversing the string again, to output the first non-repeated character takes O(n) time.

Hence, the total running time is O(n).

The memory requirement is that of a lookup table of constant size, which is O(1).

———

In C++, we can code it as follows:

——–

#include <iostream.h>

//func f returns the first non-repeated character in s.

char f ( char *s)

{

//check for null string.

if ( ! s)

return ”;

int L [26] = {0}; //lookup table, initially all entries are 0.

//we now traverse the string to populate L.

char *t = s;

while (  *t != ”)

{

L [ *t - 'a']++; // e.g. if *t is ‘e’, we need to increment L[4] which is L ['e' - 'a'].

t++;

}

//we have now populated L with counts.

//we now traverse s and using L, output the first non-repeated char.

t = s;

while ( *t != ”)

{

if ( L [ *t - 'a' ] == 1)

return *t;

}

//no non-repeated char in s.

return ”; //we may also write: return 0; (using the ASCII value of NUL)

}

———-

Now, what if remove the simplifying assumption made earlier and say  that s can contain any character. In this case, the lookup table needs to have 128 entries (one for each ASCII character).

For the preceding program, we use L [ ch - 'a' ] to access the lookup table entry corresponding to ch. In the new lookup table having 128 entries, we can use the ASCII values of the characters as direct indices into the lookup table, i.e. we can use L[ch] to access the count of character ch.

The remaining part of the code would remain more or less the same as above.

———-

Strings in C++ : Find the first non-repeated character in a string – 2

APPROACH 2

The previous approach consider each character of the string and then compared it with each of the remaining characters (albeit only those following it) to check if it gets repeated anywhere. Hence it took time. We can do better than that by sorting the string. Once the string is sorted, checking if any given character in that string gets repeated becomes a simple matter of checking the elements adjacent to it.

What we propose to do is this:

- Copy the original string into a new string.

- Sort this new string. (This will take time. )

But now we are faced with a problem.

We need to determine a non-repeated character in the original or new string. If we wanted just any non-repeated character, that would have been simple. — We would traverse through the sorted new string, and in time, we would have been able to output a non-repeated character in that string. Hence, the total running time would have been . However, what we want is  the first non-repeated character.

One idea could be to proceed as follows: Take the first character in the original string. Using  the sorted string, check if that character is being repeated. If not, return that character. Else, go to the next character in the original string and repeat the same process again.

But again, we are faced with a problem — How do we determine the location of the first character of the original string in the new sorted string in constant time? (We can, of course, do so in O(n) time. But that would only lead to an O(n^2) algorithm, which would mean that even after sorting we weren’t able to improve the running time.)

—–

From the above, we observe 2 things –

1. Sorting would help in finding repeated / non-repeated characters in a string.

2. But sorting, as such, would not help us efficiently find the first non-repeated character, because we cannot perform a constant time lookup for any given character in the sorted string.

The solution is somewhat clear given the above observations. Do a sort akin to bucket sort. i.e. keep a bucket for each character that a string can possibly have. Once you have that array of buckets each corresponding to one possible character, you can perform constant time lookup in that array for any given character. i.e. we can construct a lookup table. This leads us to the approach detailed in the next post.

Strings in C++ : Finding the first non-repeated character in a string

We are given a string, and told to find the first non-repeated character in it. Let’s look at an example: let’s say our string is “alligator”. The first non-repeated character in this string is “i”.

Now, how do we go about finding this first non-repeated character programmatically?

APPROACH 1

There is a very direct algorithm which we can employ — Take the first character of the given string (which is ‘a’ in our example string “alligator”). Compare it with each of the other characters in the string. If that character does not appear anywhere else, return that character and terminate the algorithm. Else, if the character does appear somewhere else in the string (as in the case of the ‘a’ in “alligator”), go to the 2nd character of the string, and repeat the same process (i.e. check if the 2nd character of the string gets repeated anywhere). Continue this process for each character of the string (i.e. in the k th iteration, we would compare the k th character of the string with each character in the string to determine if it appears anywhere else). If, at the end of the algorithm, we find that all characters get repeated somewhere, i.e. there is no non-repeating character, print a message to that effect.

———

The above algorithm is simple to understand and implement. It will run in time where is the length of the input string.

——

In pseudocode, the algorithm would look as follows:

——-

Input: String s of length n.

Output: First non-repeated character in s.

Algorithm:

For i going from 0 upto n-1:

flag = true; // flag is a boolean variable initialized to true.

For each j going from 0 upto n-1:

If ( s[i] == s[j] )

flag = false;

End For. //end the inner For loop.

If ( flag == true ) //i.e. if flag is true when we come out of the inner For loop

return s[i];  //character s[i] is the 1st non-repeated character in s.

End For. // end the outer For loop.

//If the algorithm reaches this statement, it means that there is no non-repeated character in s.

// Hence we return a default character, which would not otherwise be returned.

// We choose the null character — NUL for this purpose.

return NUL;

———

So that was the pseudocode for the algorithm. We can translate the above code into C++ as follows:

———

#include <iostream.h>

// function f takes a string s, and returns the first non-repeated character in s.

// In case there is no non-repeated character, it returns the null character ” (having ASCII value 0)

char f (char *s)

{

//we first check if s is the null string.

if ( !s)

return ”; // return the null character is s is the null string.

int i = 0, j;

bool flag;

while ( s[i] ! = ”)

{

flag = true;

j = 0;

while ( s[j] ! = ”)

{

if ( s[i] == s[j] )

flag = false;

j ++;

}

if (flag)

return s[i];

i++;

}

return ”; //i.e. no non-repeated character was found.

}

————

Numerical computations in C++ : Converting from Decimal to Binary

Converting from decimal to binary notation is fairly standard and straightforward.

Let’s say we need to find the binary representation of .

The method that most of us would have been taught in school is the following:

- Divide 100 by 2. You get 50, with remainder = 0. Write 0.

- Divide 50 by 2, to get 25 and remainder = 0. Write 0.

- Divide 25 by 2 to get 12 and remainder = 1. Write 1.

- Continue doing so until the number (which is 25 at present) becomes 0.

- The binary representation of 100 is the reverse of what you have written.

——

We can write a recursive function to compute the binary representation of a decimal number. Using the power of recursion, we can avoid having to reverse the output as is necessitated by the above method.

——-

// Function dec_to_bin outputs the binary equivalent of the decimal number n.

void dec_to_bin ( int n)

{

if ( n < 0)

{

cout << “-”;

n = -n;

}

if (n == 0)

return;

dec_to_binary (n/2);

cout << n%2;

}

——–

dec_to_bin will take time proportional to the number of bits in the binary equivalent of n.

——–

Numerical computations in C++ : Converting from Decimal to Binary – 2

Earlier we looked at a recursive method for conversion from decimal to binary. We can also achieve the conversion in an iterative manner, however adding to the task the additional overhead of reversing the answer that we obtain.

The underlying method is the one discussed at the beginning of the previous post. At each iteration, we divide a number by 2 and store the corresponding remainder in an array. At the end of the process, we reverse the contents of the array.

Now, we are faced with a small problem. How do we know what the size of our array should be? Fortunately, we can proceed without knowing that, using the resizeable vector container class. (A vector is like a dynamic array. We need not specify its size at the time of definition.)

In order to reverse the vector, we can simply use the reverse algorithm defined in the algorithm header. Or if we simply want to output the binary representation (without needing to store it anywhere), we may simply use a reverse_iterator to iterate through our vector.

———–

// function dec_to_bin outputs the binary equivalent of the decimal input n.

#include <iostream>

#include <vector>

using namespace std;

void dec_to_bin ( int n )

{

vector <int> v; // vector of ints to store the binary representation.

int temp = n;

if ( n < 0)

temp = -n;

while ( temp != 0)

{

v.push_back (temp%2);

temp / = 2;

}

vector<int> reverse_iterator i;

if ( n < 0)

cout << ” – ” ;

for ( i = v.rend ( ); i != v.rbegin ( ); ++i)

cout << *i;

}

——-

If we used a list or a deque instead of a vector, we wouldn’t be faced with the task of having to reverse the values computed by us. We can do this by storing successive numbers that we generate at the front of the data structure instead of at the end.

We may do that using the push_front member function for lists and deques. (Note that we cannot use push_front for a vector. We can only insert and delete elements (efficiently i.e. in constant time) at the back of a vector.)

——

The above program using a deque along with push_front would look as follows:

——

#include <iostream>

#include <deque>

#include <algorithm>

using namespace std;

void dec_to_bin ( int n )

{

deque <int> v;

int temp = n;

if ( n < 0)

temp = -n;

while (temp != 0)

{

v.push_front ( temp%2);

temp /=2;

}

if ( n < 0)

cout << “-”;

copy (v.begin( ), v.end ( ), ostream_iterator<int> (cout,”");

}

——-

Instead of using an iterator to iterate through the deque, we can use the copy algorithm defined in the header algorithm to directly output the contents of the deque. (Note that the statement #include <algorithm> though written as part of the above program is not necessary, since algorithm.h automatically gets included when we write #include <deque>. )

——-

Numerical computations in C++ – Exponentiation by repeated squaring

Let’s say that we have to compute the power of a number without using the inbuilt pow function. We can compute the answer using the method of repeated squaring.

Firstly, we assume that the exponent is an integer.

For example. let us compute (13.5)^5.

Now, we know that 5 is 101 in binary notation.

Hence, what we need to compute is

We also observe that and that .

From these observations, we can deduce that repeated squaring of and multiplication of the appropriate intermediate results would lead us to the desired answer. (i.e. Compute and take the product of and .)

Here, prior to the repeated squaring, we calculated the binary representation of the given exponent. We need not necessarily do that. We can do the squaring and the computation of the binary representation simultaneously.

———

Here is a C++ code fragment to illustrate that:-

//function f takes a computes x^e (where e >= 0)  and returns a long value.

long f (int x, int e)

{

int temp = e, rem; //rem stands for remainder.

long answer = 1, term = 1;

while ( temp != 0)

{

term = term * x;

rem = temp%2;

if (rem == 1)

{

answer = answer * term;

}

temp / = 2;

}

return answer;

}

——–

If we assume that all arithmetic operations take O(1) time, then the above function takes O(n) time where n represents the number of bits in the binary representation of the exponent, e.

———

Dynamic Programming – Maximum sum contiguous subsequence

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be .

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

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

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

}

}

}

————

APPROACH 2:

We can improve the running time to by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

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

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of .

Let denote the sum of a maximum sum contiguous subsequence ending exactly at index .

Thus, we have that:

(for all )

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over for .

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array where would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

EndFor.

Output max_start and max_end.

———–

The above algorithm takes time and space.

——–

We can however improve upon the space requirements, reducing it to . The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

End For.

Output max_end and max_start.

———–

The above algorithm takes time and space.

———-

Greedy algorithms – Coin changing using minimum number of coins

We have coins of denominations 1 cent, 5 cents and 25 cents with us. What we would like to do is represent a total of cents using these coins, such that a minimum number of coins are used.

For example, if we want to represent 31 cents, we could do that by using 1 25-cents coin, 1 5-cents coin and a single coin of 1-cent, thereby utilizing a total of 3 coins. And this indeed is the bast we can do. Why is that so? Let’s look at it this way — the current solution uses one 25-cent coin, one 5-cent coin and one 1-cent coin. One way in which we can try to modify this solution would be to decide to not use any 25-cent coin at all (instead of the one coin that we are currently using). That would mean that we would have to represent the shortage of 25 cents that we are now faced with, using coins of denominations 1 and 5-cents. We can see that we would need at least five coins of denomination 5-cents in order to represent 25-cents. Hence, using a 25-cent coin was actually a wise choice enabling us to save on the number of coins used.

Now, what if we had to represent 57 cents. The best solution would be to use two coins of 25-cents, one coin of 5-cents and two coins of 1-cent.

Again, we can intuitively infer its optimality by observing that:

1. if we use lesser number of 25-cents coins than what we are currently using, we would actually end up using more coins. —(If we use just one 25-cent coin, then we would require 5 coins of 5-cents each to cover up the deficit of 25-cents. Similarly if we do not use any 25-cents coins at all, we would need 10 coins of 5-cents each to cover the deficit.)  Hence, the idea is to use as many 25-cent coins as we possibly can.

2. Similarly, once we have used the maximum number of 25-cent coins, we are left with cents (where ) to represent using 1 and 5-cent coins. Analogous to what we observed above, we can infer that we must use as many 5-cent coins as we can in order to cover the deficit of cents. Whatever is left can be represented using 1-cent coins.

———

Hence, the algorithm would look something like this.

//Represent n cents using the least number of total coins where coins are of denominations – 1, 5 and 25-cents.

1. Divide n by 25 to get quotient q1 and remainder k1.

2. Use q1 coins of 25-cents each.

3. If k1 == 0, we are done. Else, divide k1 by 5 to get quotient q2 and remainder k2.

4. Use q2 coins of 5-cents, and k2 coins of 1-cent.

———-

Now, if we have coins at our disposal having denominations -cents and we had to represent cents with the minimum number of coins, we could do the following:-

———–

i = 3;

num = n;

While ( exponent >= 0)

{

Divide num by k^i to get quotient q and remainder r.

Use q coins of denomination k^i cents.

If ( r == 0)

break;

num = r;

i – - ;

}

———

Now, take the following example, represent 31 cents using coins of denominations 1, 10 and 25 cents such that the least number of coins are used.

Here, the idea behind the greedy algorithm of using the maximum possible number of coins of the highest denomination would not work. That approach would get us a solution that uses 6 coins : one 25-cent coin, and 6 1-cent coins.

In contrast, we can get a better solution using 4 coins: 3 coins of 10-cents each and 1 coin of 1-cent.

In the problems presented at the beginning of this post, the greedy approach was applicable since for each denomination, the denomination just smaller than it was a perfect divisor of it. (i.e. 25 was a factor of 125; 5 was a factor of 25; 1 was a factor of 5}. However, that not being true in this case {10 is not a factor of 25} leads to the failure of the greedy approach.

Recursion in C++ : The Coin Changing Problem

Let’s say that we have an infinite supply of pennies ( 1 cent ), nickels ( 5 cents ), dimes (10 cents ) and quarters (25 cents). (That would probably be a nice thing — having an infinite number of coins, whatever be the denomination. On a different note, the fact that this question assumes such an infinite supply of coins should convince everyone of the hypothetical nature of this and similar problems. That said, it is sometimes useful to get a fair idea of how to go about solving seemingly contrived problems in order to tackle realistic ones.)

Coming back to the problem — We buy a commodity and are required to pay cents for it. Now, the interesting bit is that we are required to pay exactly cents, i.e. we cannot pay more and get change in return. So, the question is — How many ways can we possibly pay cents using our infinite supply of coins?

The question could be rephrased thus:

Given the equation: where are non-negative integers, find the total number of possible solutions to the equation.

——-

Let’s take an example to clarify things — say. n = 91.

Let denote the number of ways can be represented in terms of coins having denomination 1, 5, 10 and 25.

Thus, our task is to compute .

The coin of the highest denomination is that of 25 cents.

We have 2 choices before us: (1) use at least one 25-cent coin, or  (2) do not use 25-cent coins at all.

is the sum of the number of ways we can perform (1) and (2).

(1) If we decide to use at least one 25-cent coin:

We can see that we can use either 1, 2 or 3 such coins.

If we use 1 25-cent coin, we are left with 66 cents to be represented using coins of denominations 1, 5 and 10. So, we now see that we have a smaller subproblem — that of representing 66 cents using 1, 5 and 10 cent coins.

We digress here to make a remark about notation.

—-

Let us denote by the total number of ways in which we can represent cents using coins of denomination with the added condition that at least 1 coin of denomination is used.

Thus, we have that .

(The 1st term denotes the number of ways we can represent cents using 1, 5, 10 and 25-cent coins such that at least 1 25-cent coin is used. The 2nd term — f(n,10) denotes the number of ways wherein we do not use any 25-cent coins and use at least 1 10-cent coin. Similarly, we can work out the meaning of the remaining terms. It can be observed that the events represented by each of the these terms are in some sense disjoint, which is why we can simply add these terms to get our desired result.)

——–

Going back to our example, the number of ways we can represent 66 cents using coins of denomination only 1, 5 or 10 cents is equal to .

—-

We again digress to make another remark on notation.

We use to denote the number of ways in which we can represent cents using coins of denominations .

Hence, our original task, which was to compute is the same as computing .

——–

Again, coming back to the example, we see that the number of ways to represent cents using 1, 5  and 10-cent coins is simply .

—

Now, what if we decide to use 2 25-cent coins in representing 91 cents. Then, we are left with representing 41 cents using 1, 5 and 10-cent coins, which can be done in ways.

Similarly, we can see that we can represent 91 cents using 3 25-cent coins in ways.

—-

A little reflection would get us the following equation:-

———

We can now write the method discussed above in the form of a function in C++.

——-

#include <iostream.h>

// Let’s say we have a global array A[4] = {25, 10, 5, 1}.

//func F takes a non-negative input n, and an index into the array A.

// It returns f (n, A[i]) [where the notation f(n,k) is as discussed earlier.]

int F (int n, int index) ;

// func G takes non-negative input n, and an index into the array A, and returns g(n,A[i]) as discussed above.

int G (int n, int index) // the initial call from the main ( ) function would be G(n,0).

{

int i = index;

int ans = 0;

for ( ; i < 4; i++)

ans + = F (n, i);

return ans;

}

//Now we give the implementation of func F.

int F ( int n, int index )

{

if ( n < A[index] )

return 0;

if ( index == 3)

return 1; // because f(n,1) == 1.

int ans = 0, quotient = n/ A[index];

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

{

ans + = G (n – i*A[index], index+1)

}

return ans;

}

———

Arrays in C++ – Finding appropriate pairs in an array – 4

APPROACH 3 contd.

Now, what if we remove the 2 assumptions we made earlier -

1. all elements in A are distinct.What if duplicates are now allowed?

2. Array A contains elements only in the range 0 – 99. What if the ints in A can have any possible value?

—–

If we remove the first restriction, we would possibly need to print a pair more than once depending on the number of times each element of the pair appears in A.

For example, if 10 appears thrice and 25 appears twice, and our target is 35, then we would need to print the 10, 25 pairs 6 times.

—–

Let’s now look at removing the 2nd restriction.

Earlier we were able to declare a lookup array L of a constant size =100 because of the simplifying assumption on the range of possible values in A.

Now, if all values are allowed, the size of the lookup table would have to be (assuming sizeof(int) == 4).

——–

Making these 2 modifications, we would be able to tackle the problem.

——-

There are a couple of observations on running time complexity that we would like to make here –

1. Whenever we want to decide which algorithm to go for, it is a good idea to look at both the time and space complexities of the algorithms concerned. Also, for a very large input size, the asymptotic i.e. big-O analysis provides a fairly accurate estimate of the complexity. However, for small input sizes, one should be careful to see what the hidden constants in the big-O notation are, as it is possible that for small input sizes these hidden constants may be the dominating factor in deciding the actual time it takes to run the algorithm.

2. If we are going to perform a similar type of query a number of times, then it makes sense to construct a sort of lookup table which can be used with minimal overhead for future queries. The time/ space required to construct the lookup table can be made to seem insignificant if the number of queries based on that table is large. However, if we are just going to make a single query of a particular type, then one would need to carefully decide if it is worth allocating a large amount of memory for a lookup table and using up a large amount of time to construct it, given that we would be using it only once.

————

Arrays in C++ – Finding appropriate pairs in an array – 3

APPROACH 3

Having seen and algorithms for this problem, the natural question to ask is whether we can do better than that.

Firstly, we observe that to output all pairs that sum to target, we would need to access all elements of the array. That gives a lower bound of for any algorithm that we may think of.

So, the question is whether we can actually achieve that lower bound and devise an algorithm with a time complexity of .

——–

To simplify our task let us assume that the array A only contains integers in the range 0 – 99, and that A contains only distinct elements.

For example, A = { 10, 20, 70, 40, 65, 55} and target = 75.

Now, for element 10, we would like to see if 65 is contained in A. Since the ints are from a given fixed range : 0-99, we can construct a lookup table of size 100, containing the counts of the number of time each corresponding int appears in A.

If the lookup table is called L, L[i] would contain the count of the integer i.

Thus, when processing element 10, we would simply check if L[65] is 1. This takes O(1) time.

Similarly, we would lookup some values corresponding to each of the other elements in A. Hence, the total time complexity is .

Also, the space complexity is since the size of L is constant.

———–

In pseudocode form, the above method would look like this:-

Create int array L of size 100. //we could as well use a boolean array, and indeed that would save memory.

Initialize L to all zeros.

For i going from 0 to n-1:

L [ A[i] ] ++; //increment count of element A[i].

//now print the pairs.

For i going from 0 to n-1:

If A[ i ] < (target – A [ i ] )// We need this to prevent a pair twice (e.g. as {10, 25} and {25,10} ).

If ( L [target - A[i] ] == 1 )

Print A[i], target – A[i].

————

We could code it in C++ like this:

#include <iostream.h>

void f (int *A, int n, int target)

{

int L [100] = {0};

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

L [ A[i] ] ++;

for ( i =0 ; i < n ; i++)

{

if ( A[i] < target – A[i])

if ( L [target - A[i] ] == 1 )

cout << A[i] << ” and ” << target – A[i] <<endl;

}

}

———–

Arrays in C++ – Finding appropriate pairs in an array – 2

APPROACH 2

The previous approach had a running time of . (In terms of memory requirements, it was optimal, using space.)

The question is whether we can do better in terms of running time.

—

As a thought experiment, assume that we have a sorted array, of length , and an int , and that we have to perform the same task as was assigned to us earlier. Also, for simplicity, let us assume that all elements in are distinct.

How would we go about doing it?

We could approach it as follows — Take the first element of . Subtract it from to get a new number say . Now, if x is indeed part of , we would need to output the pair .

So, what we want to do is to search for a number – , in our case – in a sorted array. We can apply binary search, which would take time.

Therefore, we take time processing .

We then proceed to and search for in . That again takes time.

As you would have guessed by now, we take time for each of the elements of , and hence the running time would be .

Now, since the original array in question is not sorted, we would first need to sort, which would take time.

Hence the running time complexity of the algorithm is .

We assume that we do not want to modify the array passed to the function. Hence, we would use separate storage for the sorted array. That would mean a memory usage of .

———-

Let us try to write the above method in C++:-

#include <iostream>

#include <vector> //This automatically implies “#include <algorithm>”. So we need not explicitly write that.

using namespace std;

//func f takes int array A, length n of A, and an int target.

// It outputs all pairs of elements in A which sum to target.

void f ( int * A, int n, int target)

{

vector <int> v;

copy (A, A+n, inserter (v, v.begin( ) ) ); //we would need to use this syntax for copying in insert mode.

sort (v.begin ( ), v.end ( ) ); // Now v has the elements of A in ascending order.

//we can now use the find algorithm or write our own function, bin_search, for binary search.

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

{

if (bin_search (v, target – A[i]) )

cout << “{  ” << A[i] << “, ” << target – A[i] << ” }”;

}

}

————

Arrays in C++ : Finding appropriate pairs in an array – 1

We are given an array A of ints, say of length n, and an integer target. Our task is to output all pairs of elements in A which add up to target.

For example, if target = 90, and the array A = {40, 20, 30, 50, 35, 60}, the output should be {40, 50}, {30, 60}. (The output is allowed to be in any order we like as long as all relevant pairs appear in it exactly once.)

————

APPROACH 1

A direct method could be to check all possible pairs of elements in A. For each pair that satisfies the required condition, we output that pair. For an array of length n, there are possible pairs. The processing time for each pair is . Hence, the running time is . Also, the memory requirement is .

——

In pseudo code, we could write it as follows:

For i going from 0 to n-1

For j going from i+1 to n-1

If A[i] + A[j] == target

Print {A[i], A[j]}

——

Transcribing that in C++, we would get:-

——

#include <iostream.h>

// function f takes an int array A, length n of A, and an int target.

//It prints all pairs of elements in A that sum to target.

void f (int *A, int n, int target)

{

for ( int i = 0; i < n-1; i++)

for (int j = i+1; j < n-1; j++)

if (A[i] + A[j] == target)

cout << endl << “{ ” << A[i] << “, ” << A[j] << ” }”;

}

———–

Minimizing waiting time – Greedy Algorithms – 2

Question.We are given n requests which need to be serviced. Assume that all requests are given to us at time t=0. It takes time, t [i] to service request i.

The waiting time of request , denoted by W[i] is defined as :

. (where the summation is over all requests serviced prior to servicing request i.)

We want to service the requests such that the total waiting i.e. the sum of the waiting times of the n requests, is minimized.

Solution.

This is a simple application of the greedy paradigm.

As is intuitively clear, we would like to service shorter requests first, before moving on to requests with a larger t [i] value.

We make the intuition concrete as follows:

——–

Sort the n requests in non-decreasing order of t[i] values.

Service the requests in this order.

——–

Intuitive proof of correctness of algorithm:

Consider what happens when you have to decide which request to service, and there are more than one requests. Consider any 2 such requests. If you schedule the request with the larger t[i], it would mean that the other request would have to wait for that larger amount of time before being serviced, thus adding that large quantity to the total waiting time. On the other hand, in case you service the smaller request first, the addition to the total waiting time would only be equal to the t[i] value of the smaller request. Hence, whenever you have a choice, go for the request with the smaller t[i] value.

This directly translates to the above algorithm.

——–

Scheduling Tutors – Greedy Algorithms – 1

Question.We are a tutor-scheduling organization. We have at our disposal an infinite number of tutors using whom we service the tutoring requests that come our way.

Consider any particular day. We get a certain number of tutoring requests. Each request has a specified starting time, and the duration of the tutoring session is exactly 30 minutes. Each tutor can work for any continuous period of 2 hours in a day. (The tutor need not actually be tutoring for the whole of the 2 hours; it is just that he/she will certainly not tutor outside of that 2 hour period.) We are the ones who decide the starting time of the 2 hour working period for each tutor.

We also need to remember that a tutor cannot service more than one request simultaneously.

Our aim is to service the tutoring requests using a minimum number of tutors. How can we achieve that?

Solution.

We can tackle this problem greedily.

We order the requests in non-descending order on the basis of their starting times. Take the first request. Schedule a tutor to start his/her 2 hour period at exactly the starting time of the 1st request. Now, look at the 2nd request. Ask yourself the following question: Can the 1st tutor (i.e. the one who has already been scheduled to work) also service this request? If yes, let him/her do so. If not, schedule a 2nd tutor to start his/her 2 hour period at exactly the starting time of this new request. Continue in the same manner for the succeeding requests. i.e. Do the following: For each new request, check if that request can be serviced by any of the tutors already scheduled to work. If yes, schedule the tutor who has the shortest time remaining in his/her 2 hr period, to service this request. If not, schedule a new tutor to start his/her 2 hour period at exactly the starting time of this new request.

——-

In pseudo code form, we would have:

Sort the requests in non-decreasing order of starting times.

count = 0; // this is the # of tutors assigned thus far.

flag = UNSERVICED. // an indicator for whether a particular request has been serviced or //not.

While (one or more requests remain to be serviced)

Remove the 1st request from our sorted list.

For ( each of the tutors scheduled thus far )

//Note: we iterate through the already assigned tutors in the order in which they were

// assigned (so as to be able to schedule the tutor with the least remaining time in

// his/her 2 hr period.

If ( that tutor can service this request )

Schedule him/her to service this request.

Come out of the For loop.

Set: flag = SERVICED.

If (flag == UNSERVICED)

// means that no already scheduled tutor was able to service the new request.

// We need a new tutor.

Assign a new tutor to start his/ her 2 hr period at the starting time of the new request.

Set: flag = UNSERVICED.

count ++ ;

End of While loop.

End.

———-

Analysis of running time:

- Say there are n requests. Sorting them will take O(n log n) time.

- In the worst case, we might need to schedule n tutors to service n requests.In such a scenario, the time required for assigning tutors will be (this is because of the fact that before we assign a new tutor we check with each of the already assigned tutors as to whether they can service the new request).

- Hence, the algorithm will run in time.

———-

Intuitive proof of correctness of the algorithm:

- Consider the 1st request (in sorted order). Obviously, since no tutors have been assigned thus far, we need to schedule a new tutor for this request. Now, consider the choice we have wrt when to schedule this new tutor. Certainly, we cannot schedule him/her to start his/her 2 hr period after the starting time of the 1st request. If we schedule him/her to start working before the starting time of the 1st request, the time that elapses between the moment the tutor’s 2 hr period starts and the starting time of the 1st request would be effectively wasted. Hence, the best thing would be to schedule the 1st tutor to start his/her 2 hr period at exactly the starting time of the 1st request.

- Similarly, one can argue that for each newly assigned tutor, the algorithm chooses exactly the right time for him/her to start their working period.

- Also, we observe that the algorithm does not assign any new tutors unless there is a need to do so.

- And finally, the algorithm always schedules a tutor with the least remaining time in their schedule to service a new request (when selecting among already assigned tutors). This results in maximum number of requests being serviced by already assigned tutors without having the need to assign a new one.

————–

Selection Sort – Sorting in C++ – 2

Selection sort works as follows: we select the max element in the array and place it at the last position. In the next iteration, we select the 2nd largest element of the array, and place it at the 2nd last position. Continue doing so until the array is sorted.

————–

void sel_sort (int A [ ], int n)

{

int max, max_index;

for (int i = 0; i < n-1; i++)

{

max = A[0];

max_index = 0;

for (int j = 1; j < n-i; j++)

{

if ( A[j] > max)

{

max = A[j];

max_index = j;

}

}

//now swap A[n-i] and A[max_index].

temp = A[n-i];

A[n-i] = A[max_index];

A[max_index] = temp;

}

}

———–

Running time : for all cases – O(n^2).

———–

Bubble Sort – Sorting in C++ – 1

Given an array of elements, the bubble sort algorithm for sorting the elements in no-descending order proceeds as follows:

Compare the first element with the 2nd. If the 1st element is greater, swap. Now, compare the 2nd and the 3rd elements. If the 2nd is greater than the 3rd, swap. Continue doing this until you reach the end of the array, at which point the largest element has been placed at the last position. Now do the same to place the 2nd largest element at its rightful position, then the 3rd largest at its rightful position, and so on.

———

void bubble_sort (int A [ ], int n)

{

int temp;

for (int i = 0; i < n-1; i++)

for (int j = 0; j < n-1-i; j++)

{

if (A[j] > A[j+1])

{

//swap

temp = A[j];

A[j] = A[j+1];

A[j+1] = temp;

}

}

}

——–

Running time: Average case/ Worst case / Best case : O(n^2).

Binary Search Trees in C++ – 3 : insert function

The insert function works much like the search function. It takes a data entry and inserts that into the BST whose root is passed as an argument to the insert function.

The key is to find the correct insertion position. This is done exactly the same way as in the search function.

We will look at a nonrecursive version of the insert function.

———-

bool insert ( Node *root, const Item& entry)

{

//firstly, create a new node.

Node *new_ptr = new Node;

if ( ! new_ptr) //memory allocation error

return false;

new_ptr->data = entry;

new_ptr->left = new_ptr->right = 0;

 

//special case where the tree is currently empty.

if ( ! root)

{

root = new_ptr;

return true;

}

//other cases.

Node *temp = root;

while (true)

{

if (entry <= temp->data)

{

if (temp->left == (Node*) 0)

{

//insert here

temp->left = new_ptr;

return true;

}

temp = temp->left;

}

else

{

if (temp -> right == (Node*) 0)

{

//insert here.

temp->right = new_ptr;

return true;

}

temp = temp->right;

}

}

}

————–

The worst case running time for insertion is O(n) while the average case is O(log n).

————–

Binary Search Trees in C++ – 2 : Occurrences function

We now look at a function which counts the number of occurrences of any particular data entry in a BST.

We first give a recursive version of the function.

——–

int occurrences ( Node *root, const Item& target)

//returns the # of occurrences of target in the BST rooted at root.

{

if (! root )

return 0;

if (root->data == target)

return 1 + occurrences(root->right, target) + occurrences (root->left, target);

else if (target< root->data)

return occurrences(root->left, target);

else

return occurrences (root->right, target);

}

————

In the non-recursive version of the occurrences function, we use a while loop to scan the relevant nodes. Each time we encounter target, we increment a variable count by 1.

—–

int occurrences ( Node *root, const Item& target)

{

int count = 0;

Node *temp = root;

while (true)

{

if (! temp)

break;

if (temp->data == target)

count ++;

else if (target < temp->data)

temp = temp->left;

else

temp = temp-> right;

}

return count;

}

————–

Counting the number of times an entry appears in a BST takes O(log n) time in the average case, and O(n) time in the worst case.

—————

Binary Search Trees in C++ – 1 : search function

A binary search tree – BST is a binary tree with the following properties:

1. The data in the left child of a node is <= its own data.

2. The data in the right child of a node is >= its own data.

——-

We can easily see why it is called a binary search tree. Consider what happens if we try to search for a particular data entry. We compare the data entry with the data stored in the root of the BST. If they are equal, we are done. Else, if our target entry is less than the data contained in the root, we know that the target entry, if it exists in the tree, has to exist in the left subtree. Thus, we have eliminated the right subtree from further consideration. Analogous is the case when the target entry is greater than the data stored in the root. Thus, we can see that this is exactly the same as what happens when we try to search for an element in a sorted array using a binary search algorithm. Hence the name BST.

—————-

We first look at a recursive formulation of the search function.

———

struct Node

{

typedef char Item;

Item data;

Node *left;

Node *right;

};
——

// returns null is target is not present; else returns pointer to appropriate node.

Node* search (Node *root, const Item& target)

{

Node *null_ptr = (Node*) 0;

if ( ! root )

return null_ptr;

if ( root->data == target)

return root;

else if (root->data < target)

return search(root->right, target);

else

return search (root->left, target);

}

———-

We now look at a non-recursive version of the search function. The basic idea of searching remains the same — if the target is less than the root’s data, go to the left child, else if it is greater, go to the right.

———

Node* search (Node *root, const Item& target)

{

Node *temp = root, *null_ptr = (Node*) 0;

while (true)

{

if (temp == (Node*) 0)

return null_ptr;

if (temp -> data == target)

return temp;

else if (target < temp->data)

temp = temp->left;

else

temp = temp -> right;

}

}

——–

Searching in a BST takes O(log n) time in the average case. In the worst case – if the tree is highly skewed, it takes O(n) time. [n is the number of nodes in the BST.]

—————-

Binary trees in C++ – 6 : preorder traversal – nonrecursive

We now look at another nonrecursive version of the preorder traversal of a binary tree. This time we do not use any additional data structure such as a stack.

Instead we assume that each node has 2 additional fields:

1. a bool flag.

2. a pointer to the parent node. (For the root node, this would be null).

Initially the flags of all nodes are false. We set the flag of a node to be true once we have traversed it.

———-

struct Node

{

int data;

Node *left;

Node *right;

Node *parent;

bool flag;

};

void preorder ( Node *root)

{

Node *temp = root;

if (root == (Node*) NULL)

return;

while (true)

{

if (temp->flag == false)

{

//print its data

cout << temp->data <<endl;

temp -> flag = true;

}

//make temp->left the new temp (if temp->left is not null, and its flag is false)

if (temp->left && !(temp->left->flag))

temp = temp->left;

else if (temp->right && !(temp->right->flag))

//if temp->left is null, then make temp->right the new temp (if temp->right is not //null, and its flag is false).

temp = temp -> right;

else if (temp == root)

//we are done traversing all nodes.

break;

else

// we are done exploring all nodes in subtree rooted at temp.

// make temp->parent the new temp.

temp = temp -> parent;

}

}

———-

As can be seen, not using the stack has resulted in this code taking a seemingly complicated look.

———-

Binary Trees in C++ – 5 : Preorder traversal – nonrecursive

Here we implement a preorder traversal of a binary tree in a non-recursive fashion.

The methodology is as follows: in the recursive version, we are able to accomplish our task very easily because we have an implicit stack data structure with us. So, in order to implement the preorder traversal non-recursively, we shall make explicit use of a stack data structure.

The code is fairly simple to understand.

We assume that we have access to a stack data structure which supports push, pop and is_empty functions.

————

we assume each node of the tree to be of this form:

struct Node

{

int data;

Node *left; //left child pointer

Node *right; //right child pointer

};

void preorder ( Node *root)

{

Stack s;

Node *temp;

s.push (root ) ;

while ( ! s.is_empty() )

// while the stack is not empty

{

temp = s.pop( ); // in the very 1st iteration, root is popped out.

// print the data of temp.

cout << temp->data << endl;

// now push the right child of temp into the stack (if temp does have a right child)

if (temp->right)

s.push (temp->right);

 

// now push the left child of temp into the stack (if left child is not null)

if (temp -> left)

s.push (temp->left)

}

}

—————

At the beginning, the stack only contains the root node. We enter the while loop. In the 1st iteration, the root is popped out, and the data stored in the root is printed. After that, we know that a preorder traversal should print out the nodes in the left subtree of root, followed by the nodes in the root’s right subtree.

Therefore, we push the right child of temp into the stack, followed by the left child of temp.

Now, consider what happens in the next iteration of the while loop. The left child of root which is now the top-most element in the stack is popped out and the data contained in it is printed. This is followed by pushing in its children into the stack. As can be seen, this effectively means that all these nodes now pushed in would be printed before the right child of the root node.

Hence, it can be seen that the preorder traversal property is maintained by the code.

———-

The code runs in O(n) time.

——–

Binary Trees in C++ – 4 : Traversal

Question. Print the nodes of a binary tree along with their respective level numbers, in the order specified by preorder traversal.

Solution.

We assume that the root is at level 0. The level number of any other node is 1 greater than the level number of its parent.

We can do the printing of the nodes and their level numbers quite easily using recursion.

——–

struct Node

{

int data;

Node *left;

Node *right;

};

void pre_level (const Node *root, int level)

{

if ( ! root )

return;

cout << root -> data << “   LEVEL:   ” << level;

pre_level (root->left, level+1);

pre_level (root->right, level+1);

}

———

This code will run in O(n) time on a tree having n nodes.

Binary Tree in C++ – 3 : Traversals

We look at 3 standard ways to traverse the nodes of a binary.

1. Preorder traversal

2. Postorder traversal

3 . Inorder traversal

——

1. Preorder traversal – A node pointer to the root of the tree (or subtree) to be traversed is passed to the function.

in this, we traverse the root first, before traversing the left subtree and the right subtree. Each subtree is in turn traversed in a preorder fashion. This results in a sequence of traversal wherein the parent is always traversed before either of its children.

——–

void preorder ( Node* root)

{

if ( root == (Node*) NULL)

return;

 

cout << root -> data << endl;

preorder (root -> left_ptr);

preorder (root -> right -> ptr);

}

———

Preorder traversal on a tree having n nodes takes O(n) time.

——

2. Postorder traversal – here, the root is traversed after the left and right subtrees have been traversed.

—-

void postorder ( Node* root)

{

if ( root == (Node*) NULL)

return;

postorder ( root -> left_ptr);

postorder (root -> right_ptr);

cout << root -> data << endl;

}

——-

Postorder traversal takes O(n) time.

—–

3. Inorder traversal – here, the order of traversal is the left subtree followed by the root followed by the right subtree.

——

void inorder ( Node *root)

{

if ( root == (Node*) NULL)

return;

inorder (root -> left_ptr);

cout << root -> data << endl;

inorder (root -> right_ptr);

}

——

Inorder traversal also takes O(n) time.

——-

Binary Tree in C++ – 2

We continue our discussion of the binary tree toolkit with a couple of other functions.

3. The tree_clear function deallocates and returns to the heap the memory dynamically allocated for the nodes of the tree, and sets the root pointer to null.

We implement this function recursively.

In general, many of the tree functions can be implemented in a recursive fashion, because the problem generally reduces to problems of exactly the same kind but with the original parameter’s left and right children as its new parameters.

——

void tree_clear (Node* node_ptr)

{

if ( ! node_ptr)

// if root is null, we don’t need to do anything.

{

tree_clear (node_ptr -> left_ptr);

tree_clear (node_ptr -> right_ptr);

delete node_ptr;

node_ptr = 0;

}

}

——–

The clearing of the tree is accomplished in O(n) time since O(1) is spent on the non-recursive portion of the code for each of the n nodes of the tree.

——–

4. The tree_copy function takes a pointer to a node as an argument and returns a tree (i.e. the pointer to the root of a tree) which is an exact copy of the tree rooted at the node pointer passed as argument.

This function is also implemented recursively in a straightforward manner:

——

Node* tree_copy ( Node* node_ptr)

{

Node *root, *left, *right;

if ( ! node_ptr)

{

root = 0;

return root;

}

left = tree_copy ( node_ptr -> left_ptr);

right = tree_copy (node_ptr -> right_ptr);

root = create_node ( node_ptr -> data, left, right);

return root;

}

——–

Copying a tree also takes O(n) time.

——–

Binary Tree in C++ – 1

We create a toolkit of functions useful for a binary tree.

A binary tree is a tree where every node has at most 2 children – the left and the right child. Each node, other than the root, has exactly one parent. The root has no parent.

We define a struct for a node of the binary tree, containing the data stored in the node, apart from the pointers to the left and the right child. One could also include, if they wish, pointers to the parent and to siblings.

——-

struct Node

{

typedef char Item;

Item data;

Node* left_ptr;

Node* right_ptr;

};

————–

We now look at a few functions to manipulate a binary tree.

1. The create_node function creates a new node using the arguments passed to it.

void create_node ( const Item& data, Node* l_ptr = 0, Node* r_ptr = 0);

———

The default values for the left and right child pointers have been set to null.

Node* create_node (const Item& data, Node* l_ptr = 0, Node* r_ptr)

{

Node* myNode_ptr;

myNode_ptr -> data = data;

myNode_ptr -> left_ptr = l_ptr;

myNode_ptr -> right_ptr = r_ptr;

return myNode_ptr;

}

——–

2. Another simple function checks if a node is a leaf – i.e. if both of its children are null.

bool is_leaf (const Node* node_ptr)

{

if (! node_ptr)

return false;

return ( ! (node_ptr -> left_ptr) &&  ! (node_ptr -> right_ptr) );

}

——–

Kite-cutting : More on dynamic programming – 4

Question. We are given a sheet of rectangular paper of length L and width W (where L and W are integral). We need to cut it in order to make rectangular kites. We have a set of n types of kites, each of integral dimensions, which we can make. Kite i has length , width and sells for a profit of . As is obvious, we would like to maximize the profit we can make from our rectangular sheet of paper.

Now, we are given a cutting device to cut the sheet. The cutting device can cut a sheet of paper only either horizontally or vertically. What this means is that we cannot cut a sheet into arbitrary shapes. Given a rectangular sheet to start with, the above condition implies that we will always obtain 2 smaller rectangles from it. The smaller rectangles can be obtained by either cutting along the width or along the length.

Also, we are told that there is no restriction on the number of kites we are allowed to make of any particular type.

Solution.

We can solve this in a fairly straightforward fashion using dynamic programming.

Let’s denote by the maximum profit we can derive out of a sheet of paper of length x and width y.

Thus, our aim is to compute .

Now, we know that we can cut the dimension sheet only either along its length or along its width (or we can also choose not to cut the sheet at all).

If we cut along the length, the 2 smaller rectangles obtained are of sizes: and where lies in the range .

Similarly, one can cut width-wise.

Also, let us denote by the profit we would get if by directly selling (i.e. without cutting) our sheet of paper. (Note that this means that there exists some kite-type which has exactly these dimensions.)

——

We obtain the following recurrence based on the above observations:

.

.

.

——-

Further, we have the following obvious results:

for all .

for all .

——–

Using the above recurrence, we can compute the OPT table as follows:

——

// in C++

//we assume we have already computed P[x][y].

int OPT[L]{W];

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

OPT[i][W] = 0;

for ( i =0; i < W; i++)

OPT [L][i] = 0;

int j, k, temp1 = 0, temp2 = 0, max;

for (i = 0; i < L; i++)

for (j=0; j < W; j++)

{

for (k =1; k < i ; k++)

{

if (OPT[k][j] + OPT[i-k][j] > temp1)

//temp1 stores the max value of term1

temp1 = OPT[k][j] + OPT[i-k][j];

}

for ( k = 1; k < j; k++)

{

if ( OPT[i][k] + OPT [i][j-k] > temp2)

//temp 2 stores the max value of term2

temp2 = OPT[i][k] + OPT [i][j-k];

}

//now take the max of temp1, temp2 and P[i][j].

max = (temp1 > temp2) ?temp1 : temp2;

OPT[i][j] = (max > P[x][y]) ? max : P[x][y];

}

———

The answer that we want is OPT[L][W].

The above code would run in time O(L^2 W^2).

(Note that we assume P[x][y] values to be part of the input.)

——-

Maximum Sum Subarray in C++ : More on dynamic programming – 2

Question. We are given an array A of n integers. We wish to find a contiguous subarray of A having the greatest sum.

Solution.

We note first that the required subarray can end at any of the n indexes , 0 through n-1. Hence, let us define as the value (i.e. sum) of the optimal subarray ending at index k.

Let OPT denote the value of the required optimal subarray.

Therefore, we have that:

.

We can compute OPT using the V[k] values in O(n) time.

——-

We now look at computing the V[k] values.

We have the following recurrence:

(Since the subarray has to end at index , is always part of it.)

——–

Further, in order to compute the optimal subarray, we need to keep track of the starting index of the subarray. We store the starting index of the optimal subarrays for our subproblems in an array of length n called Index.

———

We can compute the array and the Index array using the above recurrence in a bottom up manner.

Pseudocode for computing V and Index:

V[0] = A[0];

Index[0] = 0;

For (i going from 1 to n-1)

//Use the above recurrence to compute V[i].

If ( V[i-1] > 0)

V[i] = V[i-1] + A[i];

Index[i] = Index[i-1];

Else

V[i] = A[i];

Index[i] = i;

End of algorithm.

——————————

We can write the above pseudocode in C/ C++ as follows:

// 1. computing the V and Index arrays. (array A of length n is given to us.)

int V[n], Index[n], OPT;

V[0] =A[0];

Index[0] = 0;

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

{

//use the recurrence to find V[i] and Index[i].

if ( V[i-1] > 0)

{

V[i] = A[i] + V[i-1];

//starting index of opt. subarray ending at i is Index[i-1].

Index [i] = Index[i-1];

}

else

{

V[i] = A[i];

//starting index of opt subarray ending at i is i itself.

Index[i] = i;

}

}

—————-

// 2. Now, we can compute OPT using V in O(n) time.

OPT = V[0];

int final_index = 0; //final_index will store the ending index of the opt subarray in A.

for (i = 1; i < n; i++)

{

if (V[i] > OPT)

{

OPT = V[i];

final_index = i;

}

}

————–

// 3. We can compute the optimal subarray (the starting and ending indices) from Index.

//ending index is final_index (which we have already computed).

int begin_index = Index[final_index];

———-

That completes our algorithm.

Analysis of the algorithm:

1. Computing V and Index arrays takes O(n) time.

2. Computing OPT and final_index from V takes O(n) time.

3. Computing begin_index from Index takes O(1) time.

————

Longest non-decreasing subsequence : More on dynamic programming – 1

Question. We are given an array A of n integers. We wish to find the longest subsequence such that if the indices in the subsequence are (where ), we want that .

Solution.

Let us define to be the length of the longest non-decreasing subsequence ending at index .

Now if denotes the length of the longest non-decreasing subsequence in A, then we have that:

.

We can do the above step in time.

——

Let us now look at computing values.

We have the following recurrence:

.

In the above equation, the maximum is taken over all indices for which . (i.e. for which we can safely add A[k] to the already existing longest non-decreasing subsequence ending at i.)

In case there exists no such index , .

——-

Now that we have the recurrence, we can compute the values in a bottom up fashion iteratively. We will also keep a record of the index (as defined above) for each that we compute. This will help us when we want to reconstruct the optimal solution.

—–

Pseudo-code for computing L(k) values:

L[0] = 1;

For ( k going from 1 to n-1)

Compute L[k] using the above recurrence.

Index[k] = i;

End.

——

Coding in C/ C++ would give us:

int L[n], Index[n], OPT = 0, final_index = -1;

//final_index is the index of the last term in the optimal subsequence. (Note: there can be //more that one optimal subsequence. We consider one of them.

L[0] = 1;

for (int k=1; k<n; k++)

{

int temp_max = 0, temp_index = k; //default values of L[k]-1 and Index[k].

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

{

if (A[i] <= A[k]) //it is safe to include A[k] in this subsequence.

{

if (L[i] > temp_max)

{

temp_max = L[i];

temp_index = i;

}

}

}

L[k] = 1 + temp_max;

Index[k] = temp_index;

}

//now, to compute OPT.

for (k=0; k<n; k++)

{

if (L[k] > OPT)

{

OPT = L[k];

final_index = k;

}

}

//Now, we construct the optimal subsequence using our Index array.

// We do so recursively using a function Print_Solution.

// void Print_Solution ( int Index [ ], int n);

void Print_Solution ( int Index [ ], int n, int final_index)

{

int prev_index = Index[final_index];

if (prev_index == final_index) //this is where the subsequence begins; end recursion.

return;

Print_Solution (Index, n, prev_index);

cout << A [final_index] << endl;

}

———–

Analysis of the algorithm:

- Computing the L and Index arrays takes time.

- Computing OPT from L values takes time.

- Constructing the optimal subsequence from Index values takes O(n) time.

———–

More on linked lists in C++

Question. You are given a singly linked list, and are supposed to delete the from last node.

Solution.

Firstly, we observe that this task would be much simpler and straightforward if we had a doubly linked list. We could start at the end of the list, and traverse through m nodes before reaching our desired node, after which we could delete it.

In a singly linked list, we do not have that ability to traverse in the backward direction and hence must think of an alternate strategy.

To make the notation clear, m=1 denotes that we wish to delete the last node of the linked list. m=2, 3 and so on follow naturally from that.

One method could be the following:-Traverse the linked list from the start of the list. Thus we can compute its length. Then traverse again from the beginning to the desired node (we can now do so since we know the length of the list) and delete it.

A more elegant technique and one which we would employ would use 2 pointers. The idea is the following:

Say we want the 4th from last node of the linked list. Make one pointer point to the 4th node of the list, and another to the start of the list. Then, move each pointer forward through the list in tandem until the one in front reaches the last node of the list. At that point, the one at the back points to the node which we wish to delete.

—

A small note on the above idea would be in place: When we want to delete a node, we need to be able to identify it when we are at the node before it. Only then will we be able to manipulate the “next” pointer of the node before the one which we wish to delete. With this in mind, we would need to slightly modify the idea mentioned above.

—-

The code can be written as follows:

// the function returns true if deletion was successful, and false otherwise.

// deletion can fail if the list is of size < m.

// Node ** head is a pointer to the head pointer of the list.

// void ** myData will point to the data contained in the deleted node pointer once the function call is        //  completed.

bool myDelete (Node **head, void **myData, int m)

{

if ( ! (*head) )

//empty list.

return false;

Node *front, *back; // front will be m nodes ahead of back.

back = front = *head;

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

{

if (! front)

// checking if the length of the list is < m.

return false;

front = front -> next;

}

 

// special case if list is of length 1 (note that in this case m is necessarily = 1.

*myData = (*head) -> data;

delete *head;

*head = 0;

 

//special case if we have to delete the first node.

// in this case, front would currently point to the last node.

Node *temp;

if ( ! (front -> next) )

{

temp = (*head) -> next;

*myData = (*head)-> data;

delete *head;

*head = temp;

}

// now that front is m nodes ahead of back, we move both forward until front reaches

// the end of the list.

// Since we need to know the node which precedes the node to be deleted, we will

// move the pointers forward until front->next -> next becomes null.

while ( ! (front -> next -> next ) )

{

front = front -> next;

back = back -> next;

}

// Now we need to delete back -> next.

// We do that using a temporary node pointer.

temp = back -> next;

*myData = temp -> data;

back -> next = temp -> next;

delete temp;

return true;

}

——

We need to make sure that boundary case are handled properly:

1. What if the list is empty?  — We have a separate test for that.

2. What if the list is of size < m? — We test that within the code.

3. What if the list is of length 1, and m=1? — We handle this case separately.

4. What if the list is of length 2, and m = 1 ?  —- the code handles it properly.

5. What if m equals the length of the list i.e. we need to delete the first node?  —- That case is handled separately in the code.

6. What if m =1 ? — The code handles it properly.

——

A good code should in general check for extreme cases where there is the possibility that the code might fail.

——-

Bag ADT using Dynamic Array – 5

We now move to the constant member functions of the Bag class.

8. size_t size ( ) const; was implemented within the class definition as an inline function.

9. size_t occurrences (const Item& target) const;

This function returns the number of copies of target present in the bag.

Implementing it is straightforward.

——–

size_t Bag:: occurrences (const Item& target) const

{

size_t count = 0;

for (size_t i =0; i < used; i++)

{

if (data[i] == target)

count ++;

}

}

———-
10. our final function is the print_bag function, which is also fairly straightforward.

void Bag :: print_bag ( ) const

{

cout << “Members of the bag” << endl;

for ( size_t i =0; i < used; i++)

cout << data[i] << endl;

}

————

This completes our discussion of Bag ADT using a dynamic array implementation.

For more on ADTs and related topics, one is referred to the excellent book : Data Structures and Other Objects in C++, by Savitch and Main.

Bag ADT using Dynamic Array – 4

We now look at the implementations of the overloaded += and + operators.

7. void operator += (const Bag& addend);

The Items in the addend are added to the data array of the calling Bag instance. In case, the data array does not have enough capacity, we call the resize function.

———-

void Bag :: operator += (const Bag& addend)

{

if ( used + addend.used > capacity)

resize (used + addend.used);

//copy Items.

for (size_t i = 0; i < addend.used; i++)

data[used+i] = addend.data[i];

used + = addend.used;

}

—–

It is a good habit to check for boundary cases such as the call: b + = b;

——

8. The overloaded + operator. : Bag operator + (const Bag& b1, const Bag& b2);

implementing this is simple if we use the overloaded += operator, which is what we will be doing.

——–

Bag Bag::operator + (const Bag& b1, const Bag& b2)

{

Bag union ( b1.capacity + b2.capacity);

//note that since this is a friend function, we can access the private variable, capacity.

union + = b1;

union + = b2;

return union;

}

———

Bag ADT using Dynamic Array – 3

We now look at the implementations of the resize, insert and remove member functions.

4. We begin with the resize member function: void resize ( size_t new_cap);

This function allocates new memory in the heap equal to that needed to store new_cap number of Items.

We note that if capacity == new_cap, we do not need to do anything. Also, if new_cap < used, then obviously, since we cannot allow that to happen, we set new_cap = used.

Once we have allocated new memory, we copy Items to that location, after which we free the old memory.

——

void Bag:: resize (size_t new_cap)

{

if (capacity == new_cap)

return;

if (new_cap < used)

new_cap = used;

//allocate new memory.

Item *new_data = new Item[new_cap];//new_handler gets called in case of failure.

//copy old items to new memory.

for (size_t i = 0; i < used; i++)

new_data[i] = data [i];

//free old memory.

delete  [ ] data;

data = new_data;

capacity = new_cap;

}

———

We now look at the insert function.

4. void insert (const Item& entry);

Given that we have the resize function with us, implementing insert becomes that much more easier.

——

void Bag:: insert (const Item& entry)

{

//check if we have space to insert in existing data array.

if ( used == capacity)

resize (capacity + 1);

//insert the Item entry.

data[used] = entry;

used ++;

}

——

5. remove is also simple to implement — bool remove (const Item& target);

In case the Item target is not present in our Bag, we return false. Else, we remove one instance of the Item from our Bag, and return true.

——-

bool Bag :: remove ( const Item& target)

{

for (size_t i = 0; (i < used) && (data[i] != target)  ; i++);

//if target is not present, i == used.

if (i == used)

return false;

//overwrite at the index of target.

data[i] = data[used-1];

used – - ;

return true;

}

——–

Bag ADT using Dynamic Array – 2

We now look at the implementation of functions from the Bag ADT.

We start with the 2 constructors and the overloaded assignment operator.

1. Constructor:It allocates dynamic memory which is given by the argument passed to it. (And in case, no argument is passed to it, DEFAULT_CAP is used as the default argument.)

Bag :: Bag (size_t initial_cap)

{

data = new Item [initial_cap];

capacity = initial_cap;

used = 0;

}

——

That was simple enough. We now go to the copy constructor.

2. Copy constructor: Bag (const Bag& other_bag);

Note that a copy constructor is required for our Bag ADT since we are using dynamic memory in our class. If we do not provide a copy constructor, the default copy constructor would be used which, since it does a shallow copy, would result in undesired outcomes. For the same reason, we also need to overload the assignment operator, which we shall see a bit later.

—–

Bag :: Bag ( const Bag& other_bag)

{

//allocate memory equal to other_bag.capacity number of Items.

data = new Item[other_bag.capacity];

//set capacity value.

capacity = other_bag.capacity;

//set “used” value.

used = other_bag.used;

//copy Items.

for (size_t i =0; i< used; i++)

data[i] = other_bag.data[i];

}

——–

3. We now come to the overloaded assignment operator.The implementation is fairly along the same lines as the copy constructor, with the exception that we first check whether the calling bag instance’s capacity is equal to other_bag’s capacity.

Note that the Bag instance calling the assignment operator has already been instantiated. Hence, this is slightly different from the scenario of calling a copy constructor.

——–

void Bag::operator = (const Bag& other_bag)

{

if (capacity != other_bag.capacity)

{

//allocate new memory.

Item *new_data = new Item[other_bag.capacity];//new_handler gets called in case //of failure of memory allocation.

delete [ ] data;

data = new_data;

capacity = other_bag.capacity;

}

for (size_t i = 0; i < other_bag.used; i++)

data[i] = other_bag.data[i];

used = other_bag.used;

}

———

We make a note here: we wrote “new_data = new Item [..]; delete [ ] data; data = new_data;” instead of the more direct, “delete  [ ] data; data = new Item [..];”

The reason is that it is a good habit to maintain the invariant of the ADT at any time when “new” is called, because otherwise, a failure of the “new” call would lead to problems in debugging.

——–

In the next post, we shall look at implementing other functions of the Bag ADT.

Bag ADT using Dynamic Array – 1

We shall look at implementing the Bag ADT using a dynamic array as the underlying data structure. This improves upon our previous implementation using static array.

By using a dynamic array, we do not suffer under the constraint of having a fixed capacity which may not be exceeded. We can dynamically allocated more memory from the heap as and when needed.

——

We first give the class definition of the Bag class. We postpone the function implementations to future posts.

——

//implementing BAG ADT using dynamic array.

#ifndef BAG2_H

#define BAG2_H

class Bag

{

public:

typedef int Item; //our Bag contains items of type Item.

static const int DEFAULT_CAP = 30;

Bag ( size_t initial_cap = DEFAULT_CAP); //parameterized constructor, which can also
// act as default constructor.

Bag (const Bag& other_bag); //copy constructor — needed since we use dynamic //memory in class.

//MODIFICATION MEMBER FUNCTIONS

void operator = (const Bag& other_bag); //overloaded assignment operator — needed //since we use dynamic memory in class.

void insert (const Item& entry);

bool remove (const Item& target);

void operator += (const Bag& addend);

friend Bag operator + (const Bag& b1, const Bag& b2); //implements Bag union.

 

//CONSTANT MEMBER FUNCTIONS

size_t size ( ) const { return used; }

size_t occurrences ( const Item& target) const;//returns how many times target appears //in the bag.

void print_bag ( ) const;

 

private:

Item *data; //our dynamic array.

size_t used; //how much of the “data” array is currently being used.

size_t capacity; //what is the current capacity of the “data” array.

};

//Non-member function.

Bag operator + (const Bag& b1, const Bag& b2);

#endif

———-

Invariant of the Bag ADT:

- Items are stored in the dynamic array, data.

- If no Items are currently stored, used = 0.

- If some number of Items are currently stored, they are stored in the indices 0 through used-1.

- We do not care what is stored in the “data” array from index “used” through “capacity-1″.

- The current size of the data array is given by “capacity”.

Now that we have the class definition with us, we can go on to see the implementations of these functions in the coming posts.

——–

Bag ADT : Abstract Data Types in C++ – 5

We discuss here the overloaded + operator, which is a non-member function.

Bag operator + ( const Bag& b1, const Bag& b2);

——

The + operator returns a Bag instance contains the union of the Items contained in b1 and b2. (Note that this may result in multiple copies of some Items.)

The function performs the union only if the combined sizes of the 2 instances is at moat CAPACITY.

——

Bag operator + (const Bag& b1, const Bag& b2)

{

Bag answer;

assert (b1.size ( ) + b2.size ( ) <= CAPACITY);

answer += b1;

answer += b2;

}

——

Bag ADT: Abstract Data Types in C++ – 4

We now look at the overloaded += member function.

void operator += ( const Bag& addend);

——

We note the following:

- the operation can only take place if the total size of the 2 bag instance (the calling bag instance and addend) is no greater than CAPACITY.

- If enough space is available, we simply copy the contents the addend’s data array into the calling instance’s data array.

——-

void Bag :: operator += ( const Bag& addend)

{

assert ( size ( ) + addend.size ( ) < = CAPACITY); // include assert.h for this.

addend_size = addend.size ( );

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

data[used + i ] = addend.data[i];

}

———

Note that we use “i < addend_size” as the condition in the for loop, instead of the more natural, “i < addend.size ( )”. This is because the latter condition would fail in case the addend instance is the same as the calling instance (i.e. something of the kind, b + = b.)

———

Bag ADT : Abstract Data Types in C++ – 3

We continue our discussion of the Bag ADT with the remove member function.

bool remove ( const Item& myItem);

—–

We note the following as regards remove:

- if used = 0, then it returns false.

- if myItem is present in the data array, it removes the first copy of myItem, and returns true.

- else, it returns false.

——–

bool Bag :: remove ( const Item& myItem)

{

if (used == 0)

// empty Bag.

return false;

size_t index = 0;

while (index < used  && data[index] != myItem )

index ++;

//if myItem is not present, index would be == used.

if (index == used)

return false;

// myItem is now removed.

// we overwrite data[index] with data[used-1] and decrement used by 1.

data[index] = data[used-1];

used – - ;

return true;

}

———

Bag ADT: Abstract Data Types in C++ – 2

We continue our discussion of the Bag ADT.

We first look at the implementation of the insert function.

(All function implementations are part of an implementation file, bag.cpp, in which, among other header files, “bag.h” is included.)

—–

The insert function : bool insert (const Item& myItem); works as follows:

- it inserts the argument, myItem into the “data” array if there is space for insertion into the array, i.e. if size( ) < CAPACITY.

- In that case, it inserts myItem at index “used” in the array, and returns true.

- Otherwise, (i.e. if there is no space for insertion) it returns false.

——

bool  Bag :: insert ( const Item& myItem)

{

if ( size ( ) >= CAPACITY)

return false;

data[used] = myItem;

used ++;

return true;

}

——

Note that we pass the argument myItem by reference. Passing by reference helps to optimize on memory in case the argument is of a large size. Further, by passing it as a const reference, we ensure that what we are passing does not get accidentally modified.

——-

Bag ADT : Abstract Data Types in C++ – 1

Here we will consider the implementation of an ADT which we call the Bag ADT. This container class will contain entries of type Item. We will implement the container class using pre-allocated partially filled array.

Let’s look at the ADT in more detail.

- The Bag class contains a member called data, which is an array of Items.

- The size of the “data” array is defined using a static const called CAPACITY defined inside the Bag class definition.

- We use another member of the Bag class called “used” to indicate how many Items the “data” array currently holds.

- Invariant of the Bag ADT: The member variable “used” is an int in the range 0 through CAPACITY-1. If the “data” array does not contain any Items, then “used” = 0. If the “data” array does contain Items, those Items are contained within the indices 0 through “used”-1. We do not care what is contained in the indices starting from “used” up through CAPACITY-1.

——-

Here we present the file, bag.h.

—–

#ifndef BAG_H

#define BAG_H

#include <iostream.h>

#include <assert.h>  //if we want to use “assert” function.

#include <stdlib.h>//if we want to use “size_t”

class Bag

{

public:

static const int CAPACITY = 10; // This is the max # of Items “data” can hold.

typedef int Item; // if we want, we could change int to char or float or any such type.

//constructor

Bag ( ) { used = 0; }

//Modification member functions

bool insert ( const Item& myItem);

bool remove ( const Item& myItem);

void operator += (const Bag& addend);

//constant member function.

size_t size ( ) const { return used;}

private:

size_t used;

Item data [CAPACITY];

};

// non-member function.

Bag operator + (const Bag& b1, const Bag& b2);

#endif

——-

- The insert member function takes as argument a const reference to an Item to be inserted into the Bag object.If there is space for the item to be inserted, the function inserts it and returns true. Else, it returns false.

- The remove member function takes as argument a const reference to an item, the first copy of which would be removed from the Bag instance, if the item is present in it. It returns true in such a case. Else, it returns false.

- The size member function returns the number of Items currently held by the Bag instance.

- We shall look at the 2 overloaded operators later.

——-

Creating and Deleting a Stack : Stacks in C++ – 3

Question. Create a stack using the linked list implementation of a stack. Also, given a stack, delete it.

Solution.

To create a stack, we do not need to do anything special. We simply need to set the head pointer to NULL.

We can do this as follows:

—–

bool createStack ( Node **stack)

{

*stack = 0;

return true;

}

—-

Note that we declare the return type to be bool, and return a true value. When implementing a stack as a linked list, creating the stack is trivial and there is no possibility of failure. However that may not be the case in case we implement the stack via other means. Hence, it is a good idea to include a boolean return value so that if one day someone decides to change the linked list implementation in favor of some other implementation, he may know that there is the possibility of failure in the creation of a stack.

—–

In order to delete a given stack, we could call pop successively until no more nodes are left, or we could simply “delete” each node as we encounter it.

We could do that as follows.

—–

bool deleteStack ( Node **stack)

{

Node *curr;

while ( *stack )

{

curr = (*stack) -> next;

delete *stack;

*stack = curr;

}

——–
Note that we use pointer to a pointer in order to pass the head of the stack. Note also that we always need to store a pointer to the node which immediately follows the node we are deleting before we actually delete the node. Hence the need to have a “curr” pointer.

——

Pop from a Stack: Stacks in C++ – 2

Question. We wish to pop the top-most node from the stack.

Solution.

We could code it as follows:

——

//*stack denotes a pointer to the top node of the Stack.

//the data which is being popped is stored in *data.

//function returns false if Stack is empty; else, returns true.

bool pop ( Node **stack, void **data)

{

if (! (*stack) )

return false;

Node *myNode = *stack;

*data = (*stack)->data;

*stack = (*stack)->next;

delete myNode;

return true;

}

——

We need to pass data and stack in the form of pointer to a pointer since we are changing their contents (i.e. the location they point to) within the function.

Further, referencing the pointer *data is valid even after we explicitly “delete” myNode because *data points to some other location in the heap and not to the location which was deallocated by the “delete” statement.

—-

A related task could be to return (without deleting) the top-most node of a stack.We can accomplish this in a manner similar to the pop function.

bool return_top ( Node *stack, void **data)

{

if (! stack)

return false;

*data = stack -> data;

}

——

Note that unlike the pop function, the return_top function takes a simple pointer (instead of a pointer to a pointer) as an argument. This is because it does not need to change the location to which the head of the stack points to. If we were implementing the return_top function within a Stack class, we would have designated it as a const function signaling that it does not modify any of the members of the Stack class.

——-

Another possible way to return the top node of a stack could be to actually return the top node (i.e. as a return value of the function). In this case, we would need to pass only one argument to the function (a pointer to the head of the stack). The error-checking (i.e. the stack being empty) can be done in the environment of the caller.

We could write it thus:

——–

void* return_top ( Node *stack)

{

assert ( stack != 0);

return stack -> data;

}

—–

Push node in Stack : Stacks in C++ – 1

Here we will see how to perform basic operations on stacks (implemented here as a linked list) such as push, pop etc.

Question. Given a linked list implementation of a stack, write a function to push a node into the stack.

Solution.

Let us assume that each node is of the following form:

typedef struct Node

{

struct Node* next;

void *data;

} Node;

——

Let us also assume that “*stack” denotes a pointer to the top element of the stack.

So we can proceed as follows:

——–

// data is the data to be pushed into the stack.

// Function returns true if push succeeds; else, returns false.

bool push ( Node **stack, void *data)

{

Node *myNode = new Node;

if ( ! myNode) //memory allocation failed.

return false;

myNode -> data = data;

myNode -> next = *stack;

*stack = myNode;

return true;

}

—–

We need to check whether dynamic memory was successfully allocated or not, since that may be a point of failure in the code.

—–

Deleting entire list : C++ Linked List – 4

Question. Given a singly linked list, delete all its nodes.

Solution.

void deleteList ( Node **head)

{

if (! *head)

//if list is empty, there is nothing to delete.

return;

 

Node *curr1 = *head, *curr2 = (*head)->next;

while ( ! curr2)

{

cout << “Deleting node with data: ” << curr1 -> data << endl;

delete curr1;

curr1 = curr2;

curr2 = curr2 -> next;

}

cout << “Deleting node with data: ” << curr1 -> data << endl;

delete curr1; //this is needed to delete the last node.

//all nodes have been deleted.

// set head to null.

*head = 0;

}

—–

Deletion in linked list in C++ : Linked List – 3

Question. We are given a singly linked list and a pointer to a node to be deleted. We wish to delete that node.

Solution.

We could proceed as follows:

——–

// the function deletes node pointed to by x from the linked list.

// returns true if deletion was successful; else, returns false.

bool deleteNode ( Node **head, Node *x)

{

if ( ! head )

// empty list

return false;

 

Node *curr = *head;

if ( x == *head)  //special case: delete first node

{

head = head -> next ;

delete curr;

return true;

}

while (curr != 0   &&   curr -> next != x)

curr = curr -> next;

if ( ! curr)

//node not found.

return false;

//deleting the node

curr -> next = x -> next;

delete x;

return true;

}

——

Note that we need to pass a pointer to the head pointer since the location the head pointer points to may change (in case of deletion of first node).

——-

Traversing a linked list in C++ : Linked List – 2

Question. We wish to traverse (and print the data) in a singly linked list.

Solution.

One could proceed as follows:

——

void traverse ( Node *head)

{

Node *curr = head;

while ( ! curr)

{

cout << curr->data << endl;

curr = curr -> next;

}

}

——

Traversal takes time linear in the length of the list.

Inserting node in linked list in C++ : Linked List – 1

Question. We are given a linked list pointed to by head. We wish to insert a given node at the head of the linked list.

Solution.

Let each node of the linked be of type Node defined thus:

typedef struct Node

{

struct Node *next;//pointer to next element in list.

void *data; //data contained in the node.

} Node;

—–

Note that we need to write: struct Node *next instead of simply Node *next inside the struct definition since the typedef is not valid at that stage.

——

We can write the insert_at_head function as follows:

—–

// data contains the data to be inserted.

// function returns true if insertion succeeds, else it returns false.

bool insert_at_head ( Node **head, void *data)

{

Node *myNode = new Node;

if (! myNode)

// memory allocation failed.

return false;

myNode -> data = data;

myNode -> next = *head;

*head = myNode;

return true;

}

——

Note that we need to take a pointer to a pointer as argument (for head). That is because these arguments are passed by value. Hence if we wrote Node *head instead of Node **head, a copy of the pointer to the first element of the linked list would be passed to the insert function. The function would then change the contents of the local copy (i.e. make it point to myNode). However, the original head pointer would be unaffected and would continue to point to where it was pointing to earlier. Hence we need to pass a pointer to the head pointer as argument.

—-