Interview Question


Country: India




Comment hidden because of low score. Click to expand.
6
of 6 vote

Well, you could do it in O(n^2). I'm assuming positive integers here for simplicity. First, sort the array. Then, In the equality a^2 + b^2 = c^2, try every element for c. Now for each choice of c, have two pointers, one initially pointing to the smallest element and one pointing to the element right before c. Let the first pointer be a and the second be b. Compute a^2 + b^2 for this choice of a, b and compare to c^2. If a^2 + b^2 = c^2, you're done. If a^2 + b^2 > c^2, decrement the b pointer. If a^2 + b^2 < c^2, increment the a pointer. if the two pointers meet, there are no a,b that satisfy the equality for the current choice of c.

Since given a particular choice of c, you're shrinking the distance between the two pointers by 1 every time and that distance was at most O(n) to begin with, each choice of c is evaluated in O(n) time. Since there are O(n) choices of c, the algorithm is O(n^2).

Beating O(n^2) is probably very difficult because even for the (presumably) simpler problem of finding three numbers satisfying a + b = c, it is an open research problem whether a subquadratic time algorithm exists.

- eugene.yarovoi July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 good approach

- niraj.nijju July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there are negative integers, we should sort them by their absolute value.

- notbad July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice approach!

- ethioer July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 nice one

- Anonymous July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

int findTriplet(int *arr,int size)
{
        int a,b,c;
        c=size-1;
        while(c>1)
        {
                a=0;b=c-1;
                while(a<b)
                {
                        if(arr[a]*arr[a]+arr[b]*arr[b]==arr[c]*arr[c])
                        {
                                printf("%d %d %d\n",arr[a],arr[b],arr[c]);
                                a++;b--;
                        }
                        else if(arr[a]*arr[a]+arr[b]*arr[b]<arr[c]*arr[c])
                                a++;
                        else
                                b--;
                }
                c--;
        }
}

Complete code here: ideone.com/Z3B5O

- Aashish July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ok we can also find it with n^2 with hash table with O(n) space.

can even better solution to this n^2.

- niraj.nijju July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hash tables are much slower than arrays. Also, that gives you expected instead of deterministic time.

- eugene.yarovoi July 20, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More