## 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

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.

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

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]);
}
}
}
}``````

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

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

Comment hidden because of low score. Click to expand.
0

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

Thanks
Kannan

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

iam not understood this code iam a beginner

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

sd

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Your solution will not work for this case.

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]);
}
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Bravo :)

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;
}

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;
}
}
}

Comment hidden because of low score. Click to expand.
0

what's this shit

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])) {
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)
*/

Comment hidden because of low score. Click to expand.
0

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.

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.

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

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) {
// test case1
int[] fourSum1 = { 39, 0, 1, 2, 4, 5, 8, 10, 21, 139, 75, 95 };

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

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

// test case4
int[] fourSum4 = { 0, 1, 2 };

}

}

Comment hidden because of low score. Click to expand.
0

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

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

``````public class FindFourNumbersThatAddUp {

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) {
// test case1
int[] fourSum1 = { 39, 0, 1, 2, 4, 5, 8, 10, 21, 139, 75, 95 };

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

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

// test case4
int[] fourSum4 = { 0, 1, 2 };

}

}``````

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.

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.

### 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.