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