Goldman Sachs Interview Question
Java DevelopersTeam: Java
Country: India
Interview Type: Phone Interview
Can you explain what flag means here? A little commenting of the code should be helpful. Thanks!
It is not a DP solution . it has exponential time complexity . why did you define dp[][][] array when you are not using it anywhere .
#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;
}
Can someone please explain the unique DP state.
Like what flag here signifies? Thanks in advance.
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
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;
}
}
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?
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;
}
#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;
}
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;
}
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;
}
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;
}
#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;
}
#include<bits/stdc++.h>
- devbishnoi August 03, 2017using 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;
}