Goldman Sachs Interview Question for Java Developers


Team: Java
Country: India
Interview Type: Phone Interview




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

#include<bits/stdc++.h>
using namespace std;
int dp[101][100][2];
int solve(string str, int idx, int flag, int s, int d, int n){
if(s > n || s < 0)
return 0;
int len = str.length();
if(idx >= len)
return 0;
int res = 0;
if( (str[idx] == 'l' && flag == 0 ) || ( str[idx] == 'r' && flag) ){
int f = 1;
if(str[idx] == 'l')
f = -1;
res = solve(str, idx + 1, flag, s + f, d, n) + solve(str, idx + 1, 1 - flag, s + f, d, n);
if(s + f == d)
res++;
}
else{
res = solve(str, idx + 1, flag, s, d, n);
}
dp[idx][s][flag] = res;
return res;
}
int main(){
string str;
cin >> str;
int len = str.length();
int n;
cin >> n;
int s, d;
cin >> s >> d;
memset(dp, -1, sizeof(dp));
int res = solve(str, 0 , 0, s, d, n) + solve(str, 0, 1, s, d, n);
cout << res << endl;
}

- devbishnoi August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain what flag means here? A little commenting of the code should be helpful. Thanks!

- Anonymous October 26, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not a DP solution . it has exponential time complexity . why did you define dp[][][] array when you are not using it anywhere .

- v.jain4494 December 07, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unable to implement a DP solution. Can somebody help ?

- Anonymous January 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<bits/stdc++.h>
using namespace std;
int dp[101][100][2];
int solve(string str, int idx, int flag, int s, int d, int n){
if(s > n || s < 0)
return 0;
int len = str.length();
if(idx >= len)
return 0;
int res = 0;
if( (str[idx] == 'l' && flag == 0 ) || ( str[idx] == 'r' && flag) ){
int f = 1;
if(str[idx] == 'l')
f = -1;
res = solve(str, idx + 1, flag, s + f, d, n) + solve(str, idx + 1, 1 - flag, s + f, d, n);
if(s + f == d)
res++;
}
else{
res = solve(str, idx + 1, flag, s, d, n);
}
dp[idx][s][flag] = res;
return res;
}
int main(){
string str;
cin >> str;
int len = str.length();
int n;
cin >> n;
int s, d;
cin >> s >> d;
memset(dp, -1, sizeof(dp));
int res = solve(str, 0 , 0, s, d, n) + solve(str, 0, 1, s, d, n);
cout << res << endl;
}

- Anksus July 18, 2021 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can someone please explain the unique DP state.
Like what flag here signifies? Thanks in advance.

- Prateek October 04, 2021 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Weird solution - what's the point of dp array here?

- Anonymous November 10, 2021 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

following are valid moves
s1 -> r
s2 -> rrl
s3 -> rlr
s4 -> lrr
s5 -> rrlrl
s6 -> rlrlr
s7 -> rrllr

- Rakesh June 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Running code is given below.Enjoy!

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HashSet<String> set = new HashSet<String>();
		String current ="";
		System.out.println(findWay("rrlrlr",current, set,0, 0, 1));
	}
	
	
	public static int findWay(String patt, String current,HashSet<String> set,int index, int 			
                                                value, int difference){
		int count = 0;
		if(index == patt.length() && value == difference){
			if(set.contains(current)){
				return 0;
			}else{
				System.out.println(current);
				set.add(current);
				return 1;
			}
		}else if(index == patt.length()){
			return 0;
		}
		
		count += findWay(patt,current,set, index+1, value, difference);
		if(patt.charAt(index)=='r'){
			value++;
			current = current+"r";
		}else{
			value--;
			current = current+"l";

		}
		count += findWay(patt,current,set, index+1, value, difference);
		return count;
	}

Output Will be:-
r
rlr
lrr
rrl
rlrlr
rrllr
rrlrl
7

- erkejriwal June 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.HashSet;
import java.util.Set;


public class Solution{

static HashSet<String> set = new HashSet<String>();
public static void main(String[] args) {
// TODO Auto-generated method stub

String current ="";

p("rrlrlr");
System.out.println(set);
}


public static void p(String input){

for(int i=0;i<input.length();i++)
{

StringBuilder in=new StringBuilder(input);
in.deleteCharAt(i);
String inStr=in.toString();
if(isValidMove(inStr))
set.add(inStr);

p(inStr);
}

}
private static boolean isValidMove(String c) {

int dest=1;
int v=0;
for( int i=0; i< c.length();i++)
{
if(c.charAt(i)=='r')
v++;
else
v--;//l char
}

if(dest==v)
return true;

return false;
}

}

- hetprint July 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since he has to move right by 1 step, I can think of only the following 5 unique combinations,
r, rrl, rlr, rlrlr, rrlrl

I don't understand why is the output 7, am I missing any other combinations?

- Sairam May 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you considering substring only, but answer will be subsequences.

- Anonymous November 04, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static HashSet<String> set = new HashSet<String>();
public static void main(String[] args) {
// TODO Auto-generated method stub

String current ="";

p("rrlrlr");
System.out.println(set);
}


public static void p(String input){

for(int i=0;i<input.length();i++)
{

StringBuilder in=new StringBuilder(input);
in.deleteCharAt(i);
String inStr=in.toString();
if(isValidMove(inStr))
set.add(inStr);

p(inStr);
}

}
private static boolean isValidMove(String c) {

int dest=1;
int v=0;
for( int i=0; i< c.length();i++)
{
if(c.charAt(i)=='r')
v++;
else
v--;//l char
}

if(dest==v)
return true;

return false;
}

- hetprint July 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int calc(string str,int n,int x,int y)
{
	const ll mod=1e9+7;
	ll i,j,len=str.length(),src=x,dest=y,pos,val=n,flag;
	string temp;
	set<string> st;
	for(i=0;i<(1<<len);i++)
	{
		pos=src;
		flag=1;
		for(j=0;j<len;j++)
		{
			if(i&(1<<j))
			{
				if(str[i]=='l')
					pos--;
				else
					pos++;
				if(pos<0 || pos>n)
				{
					flag=0;
					break;
				}
			}
		}
		if(pos==dest && flag)
		{
			temp="";
			for(j=0;j<len;j++)
			{
				if((1<<j)&i)
					temp+=str[j];
			}
			st.insert(temp);
		}
	}
	return (int)(st.size()%mod);
}

int main()
{
	string str;
	int n,x,y;
	cin>>str;
	cin>>n>>x>>y;
	cout<<calc(s,n,x,y)<<endl;	
}

- Rahul Padhy August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

salute to you, most interesting solution, loved it.

- anuj July 25, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for input as rrlrlr
6
1
2
its giving 2 but answer is 7 man i dont get it and is it really a dp question because i got tle in 5 test cases lol

- SomeRandomDude August 19, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks to devbishnoi for the idea. Here is a working dp solution

public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = sc.nextInt();
        int s = sc.nextInt();
        int d = sc.nextInt();
        // Assuming n and str.len() < 100
        int[][][] dp = new int[101][100][2];
        for (int i = 0; i < 100; i++)
            for (int j = 0; j < 100; j++)
                for (int z = 0; z < 2; z++)
                    dp[i][j][z] = -1;

        int res = solve(str, 0 , 0, s, d, n, dp) + solve(str, 0, 1, s, d, n, dp);
        System.out.println(res);

    }
    static int solve(String str, int idx, int flag, int s, int d, int n, int[][][] dp){
        if(s > n || s < 0)
            return 0;
        if(dp[idx][s][flag] != -1) {
            return dp[idx][s][flag];
        }
        int len = str.length();
        if(idx >= len)
            return 0;
        int res;
        if( (str.charAt(idx) == 'l' && flag == 0 ) || ( str.charAt(idx) == 'r' && flag != 0) ){
            int f = 1;
            if(str.charAt(idx) == 'l')
                f = -1;
            res = solve(str, idx + 1, flag, s + f, d, n, dp) + solve(str, idx + 1, 1 - flag, s + f, d, n, dp);
            // Do a modulo here if needed
            if(s + f == d)
                res++;
        }
        else{
            res = solve(str, idx + 1, flag, s, d, n, dp);
        }
        dp[idx][s][flag] = res;
        return res;
    }

- Vivek July 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks to devbishnoi for the idea. Here is a working solution

public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = sc.nextInt();
        int s = sc.nextInt();
        int d = sc.nextInt();
        // Assuming n and str.len() < 100
        int[][][] dp = new int[101][100][2];
        for (int i = 0; i < 100; i++)
            for (int j = 0; j < 100; j++)
                for (int z = 0; z < 2; z++)
                    dp[i][j][z] = -1;

        int res = solve(str, 0 , 0, s, d, n, dp) + solve(str, 0, 1, s, d, n, dp);
        System.out.println(res);

    }
    static int solve(String str, int idx, int flag, int s, int d, int n, int[][][] dp){
        if(s > n || s < 0)
            return 0;
        if(dp[idx][s][flag] != -1) {
            return dp[idx][s][flag];
        }
        int len = str.length();
        if(idx >= len)
            return 0;
        int res;
        if( (str.charAt(idx) == 'l' && flag == 0 ) || ( str.charAt(idx) == 'r' && flag != 0) ){
            int f = 1;
            if(str.charAt(idx) == 'l')
                f = -1;
            res = solve(str, idx + 1, flag, s + f, d, n, dp) + solve(str, idx + 1, 1 - flag, s + f, d, n, dp);
            // Do a modulo here if needed
            if(s + f == d)
                res++;
        }
        else{
            res = solve(str, idx + 1, flag, s, d, n, dp);
        }
        dp[idx][s][flag] = res;
        return res;
    }

- Vivek July 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks to devbishnoi for the idea. Here is a working solution

public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = sc.nextInt();
        int s = sc.nextInt();
        int d = sc.nextInt();
        // Assuming n and str.len() < 100
        int[][][] dp = new int[101][100][2];
        for (int i = 0; i < 100; i++)
            for (int j = 0; j < 100; j++)
                for (int z = 0; z < 2; z++)
                    dp[i][j][z] = -1;

        int res = solve(str, 0 , 0, s, d, n, dp) + solve(str, 0, 1, s, d, n, dp);
        System.out.println(res);

    }
    static int solve(String str, int idx, int flag, int s, int d, int n, int[][][] dp){
        if(s > n || s < 0)
            return 0;
        if(dp[idx][s][flag] != -1) {
            return dp[idx][s][flag];
        }
        int len = str.length();
        if(idx >= len)
            return 0;
        int res;
        if( (str.charAt(idx) == 'l' && flag == 0 ) || ( str.charAt(idx) == 'r' && flag != 0) ){
            int f = 1;
            if(str.charAt(idx) == 'l')
                f = -1;
            res = solve(str, idx + 1, flag, s + f, d, n, dp) + solve(str, idx + 1, 1 - flag, s + f, d, n, dp);
            // Do a modulo here if needed
            if(s + f == d)
                res++;
        }
        else{
            res = solve(str, idx + 1, flag, s, d, n, dp);
        }
        dp[idx][s][flag] = res;
        return res;
    }

- Vivek July 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

as

- Vivek July 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int dp[101][100][2];
int solve(string str, int idx, int flag, int s, int d, int n){
if(s > n || s < 0)
return 0;
int len = str.length();
if(idx >= len)
return 0;
int res = 0;
if( (str[idx] == 'l' && flag == 0 ) || ( str[idx] == 'r' && flag) ){
int f = 1;
if(str[idx] == 'l')
f = -1;
res = solve(str, idx + 1, flag, s + f, d, n) + solve(str, idx + 1, 1 - flag, s + f, d, n);
if(s + f == d)
res++;
}
else{
res = solve(str, idx + 1, flag, s, d, n);
}
dp[idx][s][flag] = res;
return res;
}
int main(){
string str;
cin >> str;
int len = str.length();
int n;
cin >> n;
int s, d;
cin >> s >> d;
memset(dp, -1, sizeof(dp));
int res = solve(str, 0 , 0, s, d, n) + solve(str, 0, 1, s, d, n);
cout << res << endl;
}

- anksus July 18, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can break problem into 2 subproblems:
1. Find all subString of a String
2. Validate if a string is valid(for movement in between range) and will move Jamie from start to end.

- Anonymous January 07, 2018 | Flag Reply


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