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

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

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

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

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

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

Unable to implement a DP solution. Can somebody help ?

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

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

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

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

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

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

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

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

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

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

}

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?

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

you considering substring only, but answer will be subsequences.

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

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

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

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

salute to you, most interesting solution, loved it.

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

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

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

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

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

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

as

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

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.

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.