Goldman Sachs Interview Question Developer Program Engineers
Country: India
Interview Type: Written Test
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{
in = new BufferedReader(new InputStreamReader(System.in));
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();
}
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;
}
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.
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;
}
};
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 );
}
}
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");
}
}
//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);
}
}
}
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 toAddLeftSide = reverUsingStringBuilder(s1);
String newS = toAddLeftSide + str;
if (reverse1(newS)) {
System.out
.println("Added \""
+ toAddLeftSide
+ "\" 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;
}
}
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 toAddLeftSide = reverUsingStringBuilder(s1);
String newS = toAddLeftSide + str;
if (isPalin(newS)) {
System.out
.println("Added \""
+ toAddLeftSide
+ "\" 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;
}
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
String s = "mad";
StringBuffer sb = new StringBuffer(s);
int firstIndex;
int lastIndex;
int characterToAdd = 0;
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);
characterToAdd++;
}
}
System.out.println(sb.toString());
System.out.println("Minimum Characters To Add : " + characterToAdd);
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--){
al.add(newString[i]);
}
for(String s : al){
listString += s;
}
System.out.println(listString + str);
}
}
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--){
al.add(newString[i]);
}
for(String s : al){
listString += s;
}
System.out.println(listString + str);
}
}
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--){
al.add(newString[i]);
}
for(String s : al){
listString += s;
}
System.out.println(listString + str);
}
}
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;
}
}
/* 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
{
// your code goes here
shortestPalindromeString("java");
shortestPalindromeString("enm");
shortestPalindromeString("aavaa");
}
}
/* 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
{
// your code goes here
shortestPalindromeString("java");
shortestPalindromeString("enm");
shortestPalindromeString("aavaa");
shortestPalindromeString("abxyba");
}
}
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.
- Darkhan.Imangaliev January 11, 2015