dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 15
  1. #1
    Join Date
    Jan 2009
    Posts
    224

    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. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    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?
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  3. #3
    Join Date
    Feb 2017
    Posts
    275

    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. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    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.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  5. #5
    Join Date
    Jan 2009
    Posts
    224

    Re: Some tricky questions

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

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    Re: Some tricky questions

    Quote Originally Posted by wolle View Post
    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.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    Re: Some tricky questions

    Quote Originally Posted by mesajflaviu View Post
    "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.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  8. #8
    Join Date
    Feb 2017
    Posts
    275

    Re: Some tricky questions

    Quote Originally Posted by 2kaud View Post
    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 02:22 AM.

  9. #9
    Join Date
    Feb 2017
    Posts
    275

    Re: Some tricky questions

    Quote Originally Posted by 2kaud View Post
    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 02:21 AM.

  10. #10
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    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.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  11. #11
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    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;
    }
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  12. #12
    Join Date
    Jan 2009
    Posts
    224

    Re: Some tricky questions

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

  13. #13
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    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).
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

  14. #14
    Join Date
    Feb 2017
    Posts
    275

    Re: Some tricky questions

    Quote Originally Posted by mesajflaviu View Post
    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. #15
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,217

    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 05:50 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.7.2)

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)


×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.