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


Advertisements

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 O(n^2) 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 O(n \log n) 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 O(n) time, we would have been able to output a non-repeated character in that string. Hence, the total running time would have been O(n \log n). 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 O(n^2) time where n 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 100_{10}.

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.

——–

%d bloggers like this: