Twitter Interview Question for Software Engineer Interns


Country: United States




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

short moification of 4SUM

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

convert A+B+C=D to A+B=D-C, where A,B,C,D are numbers in array.
calculate all the A+B,D-C need two double loops.
we can calculate A+B and hash it, remember to record A,B pos in array.
for each D-C, check if it exist in hash, besides the 4 pos are different.

overall complexity is O(n*n), with O(n) space.

another way is calc A+B and sort it, then for each D-C do a binary search,to find if it exist in A+B array.

- busycai December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Space complexity would be O(N^2) since you're caching all possible pairs

- gevorgk February 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void problem1()
        {
            int[] arry = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            for (int i = 0; i < arry.Length -2 ; i++)
            {
                int frstNumberIndx = i;
                int secNumberIndx = i + 1;
                int trdNumberIndx = i + 2;

                int sumOfAllNum = arry[frstNumberIndx] + arry[secNumberIndx] + arry[trdNumberIndx];

                for (int j = 0; j < arry.Length; j++)
                {
                    if (sumOfAllNum == arry[j])
                    {
                        Console.WriteLine(arry[frstNumberIndx] + " +" + arry[secNumberIndx] + " +" + arry[trdNumberIndx] + " =" + arry[j]);
                    }
                }
            }
        }

- kannan December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

your code works only if it is sorted? It fails when the array is not sorted

- kishore25kumar December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe A,B,C,D need to be distinct elements here. It will fail for [-1, 0, 1, 10] because it will think -1 + 0 + 1 = 0.

It also fails to find A,B,C when they aren't consecutive: [1, 2, 3, 4, 7]. In this case it should be 1 + 2 + 4 = 7

- Sunny December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Kishore, Sunny .. Thanks friends for pointing it out. i will correct those.

Thanks
Kannan

- kanan857 December 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

iam not understood this code iam a beginner

- lplakshmipriyalp December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sd

- Anonymous December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets initialize an empty hash H.
In this hash, we will store sum as key and pairs of indices as value. For example. if A[1]=5 and A[3]=10. then key=15 and value= arr[pair<1,3>..]. Value is array of pairs as there could be more than one pair leading up to the same sum.

For each pair of integers in the array(2 nested for loops) do the following:
if -(A[i]+A[j]) is present in Hj], then get the value arr. Scan the array to see if there is a pair other than i,j or j,i. If there is a pair say x,y. Then A[i]+A[j]+A[x]+A[y] =0
else add A[i]+A[j] as key and a pair (i,j) as value

- Anonymous December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just realized I solved a wrong problem. The above is for finding if sum of 2 elements in array = sum of another 2 elements in the array.

- Anonymous December 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have 2 hashes one for sum S and another for difference D.
In S, you store sum of pairs.
In D you store difference of pairs. While filling up D check if there is a entry in S, then you got a solution.
A+B+C=D is same as A+B=D-C , so there is a sum pair equal to a difference pair.
In the hash you have to store indices as value (just as mentioned above for the misunderstood problem), so you return only the indices of all 4 numbers are different.

- Anonymous December 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1 + 2 + 9 = 12
1 + 5 +6 = 12

Your solution will not work for this case.

- Anonymous March 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

9  -1  0  10
9  3  -4  10
-1  3  -4  0
-50  0  10  40
30  0  10  40
chris:algorithms dlzhang$ vi find4sum.java
chris:algorithms dlzhang$ vi find4sum.java

public class find4sum{
  public static void main(String [] args){
    int [] ia = {-100, 9, -1, 3, -4, -50, 30,  0, 10, 40};
    findSum(ia);
  }

  public static void findSum(int [] ia){
    for(int i = 0 ; i < ia.length - 3 ; i++ ){
      for(int j = i + 1; j < ia.length -2; j++){
        for(int m = j + 1; m < ia.length - 1; m++ ){
          for(int n = m + 1; n < ia.length; n++ ){
            if ( ia[i] == ia[j] + ia[m]+ia[n] ||
                ia[j] ==  ia[i] + ia[m]+ia[n] ||
                ia[m] == ia[j] + ia[i]+ia[n] ||
                ia[n] == ia[j] + ia[m]+ia[i] )
              System.out.println( ia[i] + "  " + ia[j] + "  " + ia[m] + "  " + ia[n]);
          }
        }
      }
    }
  }
}

- Doug December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bravo :)

- dwelo June 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// a+b+c=d
// by ma5termind
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<limits.h>
#include<cstring>
#include<cstdlib>
#include<cfloat>
#include<cassert>
#define maxm(a,b) a>b?a:b;
#define minm(a,b) a<b?a:b;
using namespace std;
//M lazy ;)
typedef long long ll;
typedef vector <int> vi;
typedef pair< int ,int > pii;
typedef istringstream iss;
typedef ostringstream oss;
typedef map<int,int> mp;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define ln length()
#define rep(i,n) for(int i=0;i<n;i++)
#define fu(i,a,n) for(int i=a;i<=n;i++)
#define fd(i,n,a) for(int i=n;i>=a;i--)
#define all(a) a.begin(),a.end()
#define ESP (1e-9)
#define gi(n) scanf("%d",&n)
#define gl(n) cin >> n
#define pi(n) printf("%d",n)
#define pl(n) cout << n
#define ps printf(" ")
#define pn printf("\n")
#define dg(n,s); printf("%s %d",s,n)
#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define lmax numeric_limits<ll>::max()
#define lmin numeric_limits<ll>::min()
#define traverse_map(a,b) for(mp::iterator it=a;it!=b;++it)
#define MOD 1000000007
#define MAX 1000001
#define cases() int t; cin>>t; while(t--)
// fast input function
#define getcx getchar_unlocked
// fast input function
#ifdef ONLINE_JUDGE
inline void inp( int &n )
{
n=0;
int ch=getcx();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}

while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
n=n*sign;
}
#else
inline void inp(int &n){
cin>>n;
}
#endif

int main(){
int t;
inp(t);
while(t--){
int n;
inp(n);
int i;
vi array;

rep(i,n){
int x;
inp(x);
array.pb(x);
}

sort(array.begin(),array.end());// sort


int A=0,B=0,C=0,D=0,sum;
bool flag=0;

for(int i=0;i<n&&!flag;i++)
{
for(int j=0;j<n&&!flag;j++)
{
if(i==j)
continue;

sum=array[i]-array[j];

int l,k;

for(k=0,l=n-1;!flag&&k<l;){

if(k==i||k==j){
k++;
continue;
}

if(l==i||l==j){
l--;
continue;
}

if(sum==(array[k]+array[l]))
{
D=i;
A=j;
B=l;
C=k;
flag=1;
}
else if(sum>(array[l]+array[k]))
{
k++;
}
else
{
l--;
}
// 1 2 3 4 7
//cout<<"hello"<<l<<k<<sum<<" "<<i<<" "<<j<<" "<<endl;
}
}
}
// time complexity for this is O(n^3)

if(array[A]+array[B]+array[C]==array[D])
cout<<array[A]<<" "<<array[B]<<" "<<array[C]<<" "<<array[D]<<endl;
else
cout<<"no such numbers exist"<<endl;
}
return 0;
}

- can numbers be reapted my mean to say is that for example December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int A=0,B=0,C=0,D=0,sum;
bool flag=0;

for(int i=0;i<n&&!flag;i++)
{
for(int j=0;j<n&&!flag;j++)
{
if(i==j)
continue;

sum=array[i]-array[j];

int l,k;

for(k=0,l=n-1;!flag&&k<l;){

if(k==i||k==j){
k++;
continue;
}

if(l==i||l==j){
l--;
continue;
}

if(sum==(array[k]+array[l]))
{
D=i;
A=j;
B=l;
C=k;
flag=1;
}
else if(sum>(array[l]+array[k]))
{
k++;
}
else
{
l--;
}
// 1 2 3 4 7
//cout<<"hello"<<l<<k<<sum<<" "<<i<<" "<<j<<" "<<endl;
}
}
}

- Anonymous December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what's this shit

- Anonymous May 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

/*
 * Given an array with numbers, your task is to find 4 numbers that will satisfy this equation: 
 * A + B + C = D
 */
public class PrintSumCombinations2 {
	static int[] a = { 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	public static void main(String[] args) {
		//Sort the array here if it not already sorted
		//Arrays.sort(a);
		HashSet set = new HashSet();
		printCombinations(0, set, 0);
	}

	private static void printCombinations(int index, HashSet set, int setTotal) {
		for (int i = index; i < a.length; i++) {
			if (set.size() == 3 && setTotal == a[i]) {
				System.out.println(set + " " + a[i]);
			}
			if (set.size() < 3 && !set.contains(a[i])) {
				set.add(a[i]);
				printCombinations(i + 1, set, setTotal + a[i]);
				set.remove(a[i]);
			}
		}

	}
}

/*
Sort the array first. And recursively call on printCombinations(int index, Set set, int setTotal)

sort Time - O(n log n)
print Combinations - O(n^2)
I used the approach similar to this - question (id =5098263317315584)
*/

- Kary January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we don't need the sorting step at all and the set can be replaced with a list so that it can handle duplicate elements as well.

- Anonymous January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

hey Kary nice approach but can you tell me how is it n^2 ? I think its n^3 since it tries every possible combination.

- byteattack July 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindFourNumbersThatAddUp {

public void printFourNumbersThatAddUp(int[] inputNumbers) {
if (inputNumbers == null) {
System.out.println("Input is null");
return;
}
if (inputNumbers.length < 4) {
System.out.println("Not enough numbers");
return;
}
findFourNumbers(inputNumbers, 0);
}

/*
* Using recursion add 3 continuous numbers and check if they match with
* numbers after. Move the starting pointer and recursively check rest of
* the numbers.
*/
private void findFourNumbers(int[] backUp, int startingPointer) {
int secondPointer = startingPointer + 1;
if (secondPointer >= backUp.length - 3) {
return;
}
int thirdPointer = secondPointer + 1;
if (thirdPointer >= backUp.length - 2) {
return;
}
for (int i = startingPointer; i < backUp.length - 3; i++) {
int sum = backUp[startingPointer] + backUp[secondPointer]
+ backUp[thirdPointer];
// check the sum starting from the first [0] number.
for (int j = 0; j < backUp.length; j++) {
if (sum == backUp[j]) {
System.out.println("Found a match : " + "A("
+ backUp[startingPointer] + ") + B("
+ backUp[secondPointer] + ") + C("
+ +backUp[thirdPointer] + ") = " + backUp[j]);
return;
}
}
}
// move the starting pointer by 1.
findFourNumbers(backUp, startingPointer + 1);
}

public static void main(String[] args) {
FindFourNumbersThatAddUp f = new FindFourNumbersThatAddUp();
// test case1
int[] fourSum1 = { 39, 0, 1, 2, 4, 5, 8, 10, 21, 139, 75, 95 };
f.printFourNumbersThatAddUp(fourSum1);

// test case2
int[] fourSum2 = { -100, 9, -1, 3, -4, -50, 30, 0, 10, 40 };
f.printFourNumbersThatAddUp(fourSum2);

// test case3
int[] fourSum3 = { 4, 1, 1, 2, 2, 3, 5, 6, 7, 8, 9, 10 };
f.printFourNumbersThatAddUp(fourSum3);

// test case4
int[] fourSum4 = { 0, 1, 2 };
f.printFourNumbersThatAddUp(fourSum4);

}

}

- harishn March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what would the time complexity be? is it O(n^3) ?

- byteattack July 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindFourNumbersThatAddUp {

	public void printFourNumbersThatAddUp(int[] inputNumbers) {
		if (inputNumbers == null) {
			System.out.println("Input is null");
			return;
		}
		if (inputNumbers.length < 4) {
			System.out.println("Not enough numbers");
			return;
		}
		findFourNumbers(inputNumbers, 0);
	}

	/*
	 * Using recursion add 3 continuous numbers and check if they match with
	 * numbers after. Move the starting pointer and recursively check rest of
	 * the numbers.
	 */
	private void findFourNumbers(int[] backUp, int startingPointer) {
		int secondPointer = startingPointer + 1;
		if (secondPointer >= backUp.length - 3) {
			return;
		}
		int thirdPointer = secondPointer + 1;
		if (thirdPointer >= backUp.length - 2) {
			return;
		}
		for (int i = startingPointer; i < backUp.length - 3; i++) {
			int sum = backUp[startingPointer] + backUp[secondPointer]
					+ backUp[thirdPointer];
			// check the sum starting from the first [0] number.
			for (int j = 0; j < backUp.length; j++) {
				if (sum == backUp[j]) {
					System.out.println("Found a match : " + "A("
							+ backUp[startingPointer] + ") + B("
							+ backUp[secondPointer] + ") + C("
							+ +backUp[thirdPointer] + ") = " + backUp[j]);
					return;
				}
			}
		}
		// move the starting pointer by 1.
		findFourNumbers(backUp, startingPointer + 1);
	}

	public static void main(String[] args) {
		FindFourNumbersThatAddUp f = new FindFourNumbersThatAddUp();
		// test case1
		int[] fourSum1 = { 39, 0, 1, 2, 4, 5, 8, 10, 21, 139, 75, 95 };
		f.printFourNumbersThatAddUp(fourSum1);

		// test case2
		int[] fourSum2 = { -100, 9, -1, 3, -4, -50, 30, 0, 10, 40 };
		f.printFourNumbersThatAddUp(fourSum2);

		// test case3
		int[] fourSum3 = { 4, 1, 1, 2, 2, 3, 5, 6, 7, 8, 9, 10 };
		f.printFourNumbersThatAddUp(fourSum3);

		// test case4
		int[] fourSum4 = { 0, 1, 2 };
		f.printFourNumbersThatAddUp(fourSum4);

	}

}

- howaboutthis? March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

didn't like it that much but works:

/*
  Given an array with numbers, your task is to find 4 numbers that will satisfy this equation: 
  A + B + C = D
*/


#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	std::vector<int> vec {6, 1, 2, 3, 4, 5};

	for(int d: vec) {
		for(int a: vec) {
			for(int b: vec) {
				for(int c: vec) {
					if((c + b + a) == d) {
						// FOUND
						std::cout 
							<< d << " = "
							<< a << " + "
							<< b << " + "
							<< c << std::endl;
					}
				}
			}
		}
	}

	return 0;
}

- Felipe December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bro, You didn't even write the straight forward code properly. why did u take for loop for 'd' in vector v?

- hi hello December 14, 2013 | Flag
Comment hidden because of low score. Click to expand.


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