CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member
Join Date
Jan 2009
Posts
232

## Some tricky questions

Somebody ask me some interview questions, regarding programming:
1. How can multiply 2 numbers, without using '*' operator ? For instance, 7 * 4, but without using "*" ?
2. If we have a simple linked list (of pointers), and we loop this list, how can we know if we were reach again an element of the list, but, without using any helper list (an helper list, where we can insert every element on looping, and on every loop, to check if this element was met before).

If you have few minutes, I will be glad if you answer me.

Thank you.

2. ## Re: Some tricky questions

1) The 'obvious answer' is to sum the first number the number of times of the second. So 7 * 4 is 7 + 7 + 7 + 7

However, to multiply a number by 2 all you need to do is shift it one bit to the left, by 4 is 2 bits, 8 is 3 bits etc. This works for any number that is a power of 2. So 7 * 4 is 7 << 2. So consider 7 * 10. This can be written as 7 * 8 + 7 * 2 which would be (7 << 3) + (7 << 1). In the same way, 7 * 11 is 7 * 10 + 7 which is (7 << 3) + (7 << 1) + 7 etc etc etc.

2) Do you mean are there any duplicates in the list?

3. Member
Join Date
Feb 2017
Posts
320

## Re: Some tricky questions

As an alternative to 2kaud's suggestion you can utilize that that 7*4 = 7 / (1/4). So instead of one * you get two /. This works when the numbers are represented as floating points.

Regarding the list. You can use two nested loops. You scan the list in the outer loop and for each element E you encounter you scan the list in the inner loop from the beginning up to E and check whether there's a match before E is reached.

4. ## Re: Some tricky questions

Re 2). If this is a c++ list, then you could use .unique() to first remove duplicates. This however modifies the list. Depending upon the size of the list and for what it's being used for, how many times it's scanned etc etc, depends upon whether this or Wolle's suggestion in post #3 would be the most efficient.

5. Member
Join Date
Jan 2009
Posts
232

## Re: Some tricky questions

"2) Do you mean are there any duplicates in the list? "
Yes, but is about CList, not std::list.

6. ## Re: Some tricky questions

Originally Posted by wolle
As an alternative to 2kaud's suggestion you can utilize that that 7*4 = 7 / (1/4). So instead of one * you get two /. This works when the numbers are represented as floating points.
It needs to be written as 7.0 / (1.0 / 4.0) so that floating point division is used. In c/c++, 7 / (1 / 4) gives division by 0 as integer 1 / 4 gives 0. Note that using floating point division may not produce the required answer in every case due to rounding errors on floating point division.

7. ## Re: Some tricky questions

Originally Posted by mesajflaviu
"2) Do you mean are there any duplicates in the list? "
Yes, but is about CList, not std::list.
Then use Wolle's suggestion in post #3. This could be slow depending upon the size of the list.

8. Member
Join Date
Feb 2017
Posts
320

## Re: Some tricky questions

Originally Posted by 2kaud
It needs to be written as 7.0 / (1.0 / 4.0) so that floating point division is used.
Well, the OP talked about "numbers" without specifying the actual C++ type so I just mentioned in words that the "numbers" in 7 / (1 / 4) should be represented as floating points for this to work. There also may be no zero division.

In the C++ expression 7.0 / (1.0 / 4.0) all "numbers" have type double but also other floating point types such as float and long double will work with my suggestion.
Last edited by wolle; February 1st, 2018 at 03:22 AM.

9. Member
Join Date
Feb 2017
Posts
320

## Re: Some tricky questions

Originally Posted by 2kaud
you could use .unique() to first remove duplicates.
I checked out std::unique and from what I can see it only removes duplicates from consecutive groups of equal elements. It means if you have a list of say 1, 2, 1 the 1's will never be considered duplicates.

To fix this I suppose the list first has to be sorted. If an std::list is used it can be sorted in O(N * logN) but I'm unsure whether this is done without any supporting data structures as the OP requires.
Last edited by wolle; February 1st, 2018 at 03:21 AM.

10. ## Re: Some tricky questions

I checked out std::unique and from what I can see it only removes duplicates from consecutive groups of equal elements.
You are right. I've never used it and only went by what a brief description said. In this case the list would first need to be sorted as you stated.

is done without any supporting data structures as the OP requires.
But that begs the question about whether only supporting data structures introduced by the programmer are not allowed or whether 'hidden' structures used by 'standard c++' are also not allowed and when does 'standard c++' use 'hidden' structures?

This is why I absolutely don't like these types of 'trick' interview questions. They don't really answer what we consider to be the fundamental question 'Can they write decent c++ code'.

NB The OP has now said that the question relates to the CList structure which doesn't have .unique() anyhow - so two nested loops are needed.

11. ## Re: Some tricky questions

However, to multiply a number by 2 all you need to do is shift it one bit to the left, by 4 is 2 bits, 8 is 3 bits etc. This works for any number that is a power of 2. So 7 * 4 is 7 << 2. So consider 7 * 10. This can be written as 7 * 8 + 7 * 2 which would be (7 << 3) + (7 << 1). In the same way, 7 * 11 is 7 * 10 + 7 which is (7 << 3) + (7 << 1) + 7 etc etc etc.
For one way for unsigned integers consider

Code:
```unsigned int Mult(unsigned int n, unsigned int m)
{
unsigned int res = 0;

for (unsigned int pow = 0; n; n >>= 1, ++pow)
if (n % 2)
res += m << pow;

return res;
}```

12. Member
Join Date
Jan 2009
Posts
232

## Re: Some tricky questions

Yes, the CList it is the chosen list. So, there will be 2 lists ...

13. ## Re: Some tricky questions

For one way to display unique items in a list (c++ list used here but principle same for other types) consider

Code:
```	list<int> li {1, 2, 3, 1, 4, 2, 5, 2, 1, 6, 3, 2, 1, 6, 4};

for (auto it1 = li.begin(); it1 != li.end(); ++it1) {
bool dup = false;
for (auto it2 = li.begin(); !dup && (it2 != it1); ++it2)
dup = (*it1 == *it2);

if (!dup)
cout << *it1 << " ";
}

cout << endl;```
This displays

Code:
`1 2 3 4 5 6`
so only non-identical elements are processed. For lists containing a large number of elements, this could be slow as the execution is of O(n * n).

14. Member
Join Date
Feb 2017
Posts
320

## Re: Some tricky questions

Originally Posted by mesajflaviu
Yes, the CList it is the chosen list. So, there will be 2 lists ...
The nested loop solution I suggested which 2kaud implemented is a valid solution on all accounts but with the drawback that it's O(N^2).

If a supportive data structure may be used O(N) is possible . It's just to scan the input list once and insert each element in a hashtable. If an element is already in the hashtable it's a duplicate and discarded, otherwise it's added to the output list.

But there also is an O(N * logN) solution that may fit the bill. It's based on the observation that all duplicates in a sorted list can be removed in just one scan of the list. The question then is whether a list can be sorted in O(N *logN) without any use of supportive data structures. I'd say it can if the output list doesn't count as a supportive data structure. Have a look at Mergesort,

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

The third pseudocode at that site (Top-down implementation using lists) shows an implementation that grows the output list recursively without using any other data structures. This algorithm can be modified so duplicates are removed during sorting, or the duplicates can be removed afterwards in one O(N) scan.

In a job interview for an intermediate programmer position the Mergesort solution probably is what you are expected to come up with, especially if you are a CS graduate.

15. ## Re: Some tricky questions

Re-reading the original question, my take on this question is now

For an immutable linked list, iterate this list until a duplicate is found without using intermediate additional storage

which has two constraints
1) Original list can't be altered
2) Other storage can't be used to hold working data (such as a list of processed items, hash tables etc)

For this take on the question, then IMO the double loop is the only solution? For an interview question around this, it could lead to a discussion of time complexity and what constraints could be removed in order to reduce/improve this time complexity and what improvement(s) could be seen (and how implemented eg hash tables, merge sort etc) if these constraints were removed (eg going from O(N^2) to O(N*logN) to O(N)). For large N, this gives an improvement greater than 99% !
Last edited by 2kaud; February 4th, 2018 at 06:50 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•