## Goldman Sachs Interview Question for Developer Program Engineers

• 0

Country: India
Interview Type: Written Test

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

I know two solutions for this problem. First one uses Palindromic Tree data structure (google it if you don't know), second uses hashes. Both approaches work in O(n) time and use O(n) memory.

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

By the way, with hashing you can do it in O(1) space if you use rolling hash.

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

@Darkhan.Imangaliev can you please describe how to solve this by using hashes..

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

here is some code on hashes. Basically the idea is to fix the center of palindrom and compare strings on left and right using hashes in O(1) time, which leads to O(N) overall

``````final static long PRIME = 31;

long []p, h, hr;
int n;

public void run() throws Exception{
out = new PrintWriter(System.out);

char []a = next().toCharArray();
n = a.length;
if (n == 1) {
out.println(0);
out.close();
return;
}
p = new long[n];
p[0] = 1;
for(int i = 1; i < n; ++i) p[i] = p[i-1] * PRIME;

h = new long[n];
hr = new long[n];
for(int i = 0; i < n; ++i) {
h[i] = p[i] * (a[i] - 'a' + 1);
hr[i] = p[i] * (a[n - i - 1] - 'a' + 1);
if (i > 0) {
h[i] += h[i-1];
hr[i] += hr[i-1];
}
}

int ret = n - 1;
for(int i = n / 2 - 1; i + 1 < n; ++i) {
int len = Math.min(i + 1, n - i - 1);
long left = h[i];
if (i - len >= 0) left -= h[i - len];
long right = hr[len - 1];
if (left * p[n - i - 1] == right * p[n - (len - 1) - 1]) {
ret = Math.min(ret, n - 2 * len);
}

len = Math.min(i + 1, n - i - 2);
if (len == 0) continue;
left = h[i];
if (i - len >= 0) left -= h[i - len];
right = hr[len - 1];
if (left * p[n - i - 1] == right * p[n - (len - 1) - 1]) {
ret = Math.min(ret, n - (2 * len + 1));
}
}

out.println(ret);
out.close();
}``````

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

Check if a word is paliendrome, if yes return. Starting from i=1 append i-th character to the left of the string. Check if a new string is a paliendrome.

``````public String paliendrome(String s) {
if (isPaliendrome(s)) 	return s;
String out = s;

for (int k=1; k<s.length(); k++) {
Char c = s.charAt(k);
s = c+s;
if (isPaliendrome(out)	break;
}
return out;
}

public boolean isPaliendrome(String s) {
int i = 0, j = s.length()-1;
while (i<j)
if (s.charAt(i--) != s.charAt(j--))
return false;
return true;
}``````

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

The code, as you wrote, contains few minor mistakes, making it incorrect. If you fix them, this will be O(N^2) time algorithm. If I were an interviewer I'd expect O(N) solution.
Hint: think how to make isPalindrome() expected O(1) time complexity.

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

hash is the way to go

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

This is example of the hash-based algorithm with O(N) time and O(1) space. Similarly to a straightforward implementation it adds characters to the prefix and checks whether resulting string is a palindrome, however all operations within a loop are performed in expected O(1) time.

``````// Returns length of a min palindrome which can be constructed from s
// by appending characters to the left of the string
// O(N) time, O(1) space
tnt minPalindrome(const string& s)
{
int n = s.size();
if (s.size() <= 1) return s.size();
// suppose the s is palindrome
int x = n / 2 - 1; // end of left part: abCdcba or abCcba
int y = (n + 1) / 2; // start of right part: abcdCba or abcCba.
hash_helper leftSuffix;
hash_helper right;

for (int i = 0; i <= x; i++) {
leftSuffix.push_back(s[i]);
right.push_back(s[n - 1 - i]);
}
if (right.hash == leftSuffix.hash) {
if (isPalindrome(s,n)) return n; // s is palindrome
}
// s isn't a palindrome, appending characters to the prefix until combined string becomes a palindrome
int j = 0; // pos of appended character
int m = n;
hash_helper leftPrefix;
for (;;) {
char c = s[n - 1 - j++];
leftPrefix.push_back(c);
if (m % 2 == 0)
leftSuffix.pop_back(s[x--]);
else
right.push_back(s[--y]);
m++;
uint32_t leftHash = leftPrefix.concat(leftSuffix);
if (leftHash == right.hash && isPalindrome(s, m))
return m;
}
return m;
}``````

isPalindrome() performs full (expensive) check for "palindromness" only when we have hash match:

``````bool isPalindrome(const string&s, int m)
{
int i = 0;
int j = s.size()*2 - m - 1;
while (i < j) {
if (s[i] != s[j])
return false;
i++; j--;
}
return true;``````

Finally, we need a hash function implementation which supports push_back, pop_back and concat operations.
The following implementation is based on linear congruential generator and it is very good hash function among those which are simple to implement.

``````// linear congruential generator based implementation
struct hash_helper
{
uint32_t hash; // hash value
const uint32_t MOD = 16777213; // prime number 2^24 - 3
const uint32_t A = 127; // factor
const uint32_t AI = 10039907; // modular multiplicative inverse of A
uint32_t F;
hash_helper() :hash(0), F(1) {};

void push_back(unsigned char c)
{
hash = ((hash * A) % MOD + c) % MOD;
F = (F * A) % MOD;
}

void pop_back(unsigned char c)
{
hash = (hash + MOD - c) % MOD;
hash = ((uint64_t)hash * AI) % MOD;
F = ((uint64_t)F * AI) % MOD;
}

uint32_t concat(const hash_helper& b)
{
return ((((uint64_t)hash * b.F) % MOD) + b.hash) % MOD;
}
};``````

The following hash function is not as good as previous, but it is easier to understand - it is based purely on shifts and XORs. If you struggle to understand how the previous hash function works, start with this one:

``````// Cyclic polynomial  implementation. Based on circular shift and XOR operations.
struct hash_helper
{
uint32_t hash; // hash value
int len; // len of the hashed substring
hash_helper() :hash(0), len(0) {};

void push_back(unsigned char c)
{
hash = ((hash << 1) | (hash >> 31)) ^ c;
len++;
}

void pop_back(unsigned char c)
{
assert(len);
hash ^= c;
hash = ((hash >> 1) | (hash << 31));
len--;
}

uint32_t concat(const hash_helper& b)
{
int q = b.len % 32;
return ((hash << q) | (hash >> (32-q))) ^ b.hash;
}
};``````

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

public class MakePalindrome
{

public static boolean isPalindrome( String palind )
{
StringBuilder rev = new StringBuilder( palind );
rev.reverse();
if( palind.equals( rev.toString() ) )
{

return true;
}
return false;

}

public static void main( String[] args )
{
StringBuilder str = new StringBuilder( "javaj" );
int len = str.length();
int i = 0;

while( len >= 0 )
{
if( !isPalindrome( str.toString() ) )
{
System.out.print( len + " " );
str.insert( str.length() - i, str.charAt( i ) );
len--;
i++;

}
else
{
break;
}
}

System.out.println( str );
}
}

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

package com.practice.gs.careercup;

public class AllProgramme {
public static void minPalindrome(String s){
int len = s.length();

int i=(len-1)/2,j=(len+1)/2;
while(i>=0 && j<len){
if(s.charAt(i)==s.charAt(j)){
i--;j++;
}else{
j=i;
i--;
}
}
if(j<len-1){
char[] c = new char[len-1-j];

for(int k= len-1;k>j;k--){
c[len-1-k] = s.charAt(k);
}
System.out.println(new String(c)+s);
}
else
System.out.println(s);
}
public static void main(String []a){
minPalindrome("java");
minPalindrome("1221");
minPalindrome("enm");
}
}

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

//You have to enter string which you want to check shortest palindrom..

package com.dhruv.gs;

import java.util.Scanner;

public class Palindrom1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter string to check shorted palindrome:");
String original = in.nextLine();
int length = original.length();
String reverse="";
for(int i= length-1;i>=0;i--){
reverse=reverse + original.charAt(i);
}
if(original.equals(reverse)){
System.out.println("shorted Palindrom for given string is " + original + " and length is " + length);
}
else{
String duplicate="";
for(int k =length-1;k>0;k--){
duplicate = duplicate + String.valueOf(original.charAt(k));
}
original = duplicate + original;
length = original.length();
System.out.println("shorted Palindrom for given string is " + original + " and length is " + length);

}
}
}

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

``````public class createPalinDrome {
public static void main(String[] args) {
String str = "javajat";
for (int i = str.length(); i > 0; i--) {
String s1 = str.substring(i, str.length());
String newS = toAddLeftSide + str;
if (reverse1(newS)) {
System.out
+ "\" to left side which created new palindrom string as - "
+ newS);
break;
}
}
}

// Reverse string using string builder
private static String reverUsingStringBuilder(String str) {
StringBuilder sb = new StringBuilder();
sb.append(str);
return sb.reverse().toString();
}

// Check if string is palindrome
private static boolean reverse1(String str) {
if (str.equals(reverUsingStringBuilder(str))) {
return true;
}
return false;
}
}``````

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

``````public static void main(String[] args) {
String str = "javajat";
for (int i = str.length(); i > 0; i--) {
String s1 = str.substring(i, str.length());
String newS = toAddLeftSide + str;
if (isPalin(newS)) {
System.out
+ "\" to left side which created new palindrom string as - "
+ newS);
break;
}
}
}

// Reverse string using string builder
private static String reverUsingStringBuilder(String str) {
StringBuilder sb = new StringBuilder();
sb.append(str);
return sb.reverse().toString();
}

// Check if string is palindrom
private static boolean isPalin(String str) {
if (str.equals(reverUsingStringBuilder(str))) {
return true;
}
return false;
}``````

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

We need to compare first and last character, if not equal we need to add first character at last character with which we are comparing till string becomes palindrome

StringBuffer sb = new StringBuffer(s);
int firstIndex;
int lastIndex;
for (int i = 0; i < sb.length(); i++)
{
firstIndex = i;
lastIndex = sb.length() - i - 1;
if(sb.charAt(firstIndex) != sb.charAt(lastIndex))
{
sb.insert(lastIndex + 1, new char[]{sb.charAt(firstIndex)}, 0, 1);
}
}

System.out.println(sb.toString());

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

package com.utsav.jpm;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PalindromString {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
String str = in.next();
List<String> al = new ArrayList<String>();
String listString = "";

String[] newString = str.split("");

for(int i=str.length(); i>1; i--){

}

for(String s : al){
listString += s;
}
System.out.println(listString + str);

}

}

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

package com.utsav.jpm;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PalindromString {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
String str = in.next();
List<String> al = new ArrayList<String>();
String listString = "";

String[] newString = str.split("");

for(int i=str.length(); i>1; i--){

}

for(String s : al){
listString += s;
}
System.out.println(listString + str);

}

}

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

``````package com.utsav.jpm;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PalindromString {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
String str = in.next();
List<String> al = new ArrayList<String>();
String listString = "";

String[] newString = str.split("");

for(int i=str.length(); i>1; i--){

}

for(String s : al){
listString += s;
}
System.out.println(listString + str);

}

}``````

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

``````import java.io.*;
import java.util.*;
public class Shortpal
{
public static void main(String []args)
{
Scanner in=new Scanner(System.in);
System.out.println("enter the string");
String s=in.nextLine();
System.out.println("shortest palindrome is "+shortpal(s));
}
public static String shortpal(String s)
{

if(s.length()==1)
return s;
int i=0;
int j=s.length()-1;
int flag=0;
while(i<j)
{
if(s.charAt(i)!=s.charAt(j))
{
flag=1;
break;
}
i++;
j--;

}
if(flag==1)
{

int l=1;
int n=s.length();
char a[]=s.toCharArray();
while(l<n)
{
s=a[l]+s;
l++;
}

return s;
}

return s;
}
}``````

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

``````String inputString = "JAVA";
inputString = inputString.substring(1, inputString.length())
+ inputString;
System.out.println(inputString);``````

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

``````String inputString = "JAVA";
inputString = inputString.substring(1, inputString.length())
+ inputString;
System.out.println(inputString);``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{

public static void shortestPalindromeString(String s)
{
char[] input = s.toCharArray();

int st=0,end=input.length-1;

while(st<end)
{
if(input[st] == input[end])
{
st++;
end--;
}
else
{
end--;
}
}

if(!(st == s.length()/2) && !(end == s.length()/2))
System.out.println(s.substring(end+1,s.length()));

}

public static void main (String[] args) throws java.lang.Exception
{
shortestPalindromeString("java");
shortestPalindromeString("enm");
shortestPalindromeString("aavaa");
}
}``````

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

Incorrect: Counter-example: abxyba

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{

public static void shortestPalindromeString(String s)
{
char[] input = s.toCharArray();

int st=0,end=0;

while((st+end+2) <= s.length() )
{
if(input[st] == input[s.length()-end-1])
{
st++;
}
end++;

}

if(st == 0)
{
System.out.println(s.substring(st+1,s.length()));
}
else if(s.length()/2 != st)
{
//System.out.println(st+" : "+((end-1)-st+1));
System.out.println(s.substring(st+1,st +(end-st+1)));
}

}

public static void main (String[] args) throws java.lang.Exception
{
shortestPalindromeString("java");
shortestPalindromeString("enm");
shortestPalindromeString("aavaa");
shortestPalindromeString("abxyba");
}
}``````

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

This will not work for all cases. like anaa.

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.