CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: challenged problem C++ implementation - homework help (preparing for an interview).

  1. #1
    Join Date
    Jan 2021
    Posts
    2

    challenged problem C++ implementation - homework help (preparing for an interview).

    Hi guys .

    I'm struggling to implement in C/C++ a function that gets as two inputs , one input is an integer array, second input is the given sum.

    the function returns the pairs of two element that its sum equal to the given sum.

    I don't have much experience in C/C++, and I started to implement the function by myself.



    I've seen the solution here step by step :
    https://www.youtube.com/watch?v=WJP62MCWTM8&t=209s

    but I really didn't understand the logic of the explained code in the video, could anyone please explain to me the algorithm / the code that's explained on the video?

    how really we find the matched two pairs that its sum equal to the given sum?



    For me a pseudo code is also awesome to understand the solution of the problem.



    Much appreciated.

  2. #2
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,481

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    Haven't seen the video, but why not code it up as instructed and then step through the code in a debugger?

    Imo, there's no better way to learn unknown code than to step through it line by line to see how it works.

  3. #3
    Join Date
    Jan 2021
    Posts
    2

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    Quote Originally Posted by Arjay View Post
    Haven't seen the video, but why not code it up as instructed and then step through the code in a debugger?

    Imo, there's no better way to learn unknown code than to step through it line by line to see how it works.
    I understand you, but you're telling me like just copy and paste the code from the video, here I want to learn , copy and
    paste codes will not help me now or even on the future , I would do what you suggest without posting this thread.

    I posted this thread in order to understand well what's explained on the video and how its explained algorithm match to the problem.


    Anyway, Thanks for your reply but it wouldn't help me.

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

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    I started to implement the function by myself.
    If you post your code then we'll be able to provide guidance re it.

    The brute force solution is to start at index 0 (say loop i), then iterate from index i (say loop j) and checking if the sum of the array at positions i and j equal to the required value. Then increment i etc. If the array is sorted, then the loop(s) can be terminated once the sum is greater than the required value.

    I'd have a std::vector of std:: pair for the return type.

    PS.
    If you would like the code from the video explained, then post the actual code (not a link to the video).
    Last edited by 2kaud; January 3rd, 2021 at 06:31 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++20 Compiler: Microsoft VS2019 (16.10.2)

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

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    One simple implementation could be:

    Code:
    #include <vector>
    #include <utility>
    #include <iostream>
    
    auto makesum(const std::vector<int>& nos, int sum)
    {
    	std::vector<std::pair<int, int>> fnd;
    
    	for (size_t i = 0; i < nos.size(); ++i)
    		for (size_t j = i; j < nos.size(); ++j)
    			if (nos[i] + nos[j] == sum)
    				fnd.emplace_back(nos[i], nos[j]);
    
    	return fnd;
    }
    
    int main()
    {
    	const std::vector<int> nos {1, 2, 3, 4, 5, 6, 7};
    
    	std::cout << "Sum 7\n";
    	const auto pr7 {makesum(nos, 7)};
    
    	for (const auto& [no1, no2] : pr7)
    		std::cout << no1 << "  " << no2 << '\n';
    
    	std::cout << "\nSum 8\n";
    	const auto pr8 {makesum(nos, 8)};
    
    	for (const auto& [no1, no2] : pr8)
    		std::cout << no1 << "  " << no2 << '\n';
    }
    Code:
    Sum 7
    1  6
    2  5
    3  4
    
    Sum 8
    1  7
    2  6
    3  5
    4  4
    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++20 Compiler: Microsoft VS2019 (16.10.2)

  6. #6
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,481

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    Quote Originally Posted by Ryan Vayer View Post
    I understand you, but you're telling me like just copy and paste the code from the video, here I want to learn , copy and
    paste codes will not help me now or even on the future , I would do what you suggest without posting this thread.

    I posted this thread in order to understand well what's explained on the video and how its explained algorithm match to the problem.


    Anyway, Thanks for your reply but it wouldn't help me.
    I'm not asking you to copy and paste code, I'm asking you to type in the code line by line and think about it while you are typing it.

    Then, once the code compiles and runs, step through the code in a debugger and inspect it line by line.

  7. #7
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,481

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    Quote Originally Posted by Arjay View Post
    I'm not asking you to copy and paste code, I'm asking you to type in the code line by line and think about it while you are typing it.

    Then, once the code compiles and runs, step through the code in a debugger and inspect it line by line.
    Oh wait, you mentioned homework and preparing for an interview.

  8. #8
    Join Date
    Feb 2017
    Posts
    606

    Re: challenged problem C++ implementation - homework help (preparing for an interview

    Quote Originally Posted by Ryan Vayer View Post
    but I really didn't understand the logic of the explained code in the video, could anyone please explain to me the algorithm / the code that's explained on the video?

    how really we find the matched two pairs that its sum equal to the given sum?
    This problem is quite common and there are several ways to solve it,

    https://web.stanford.edu/class/cs9/s...obs/TwoSum.pdf

    The video uses the hashtable approach. A hashtable is a data structure where you can store things quickly, for example integers, and then quickly determine whether something, for example a specific integer, is stored or not. In c++ it is called std::unordered_set.

    http://www.cplusplus.com/reference/u...unordered_set/

    Say there is a sequence of integers,

    ............a.............b...........

    and a+b=sum, so a and b is a valid pair.

    1. Start with an empty hashtable.
    2. Pick integers x from the sequence one by one from left to right.
    3. For each x, check whether sum-x is in the hashtable.
    4. If not, insert x into the hashtable and continue.
    5. At some point x=a, but you will not find sum-x=b because b has not yet been encountered and therefore is not yet in the hashtable. So you insert x=a into the hashtable and continue.
    6. Then after a while x=b is encountered. Check whether sum-x=a is in the hashtable and it is because a has been inserted before.
    7. The a and b pair has been found.
    Last edited by wolle; January 5th, 2021 at 01:58 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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)