Amazon Interview Question for SDE1s


Country: United States
Interview Type: Written Test




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

package com.santhosh.test;

public class FindAllPalindromeSubString	{
	
	
	public static void getSubStringPalindrome(String str)	{
	
		for(int i = 0; i < str.length() ; i++)	{
			
			for(int j = i ; j < str.length(); j++ )	{
				
				String s = str.substring(i , j);
				
				if(s.length() <= 1)	{
					continue;
				}
				
				if(isPalindrome(s))	{
					
					System.out.println(s);
				}
			}
		}
		
		
	}
	
	
	public static boolean isPalindrome(String s )	{
		
		//System.out.println("IsPalindrome:" + s + "?");
		StringBuilder sb = new StringBuilder(s);
		String reverse = sb.reverse().toString();
		//System.out.println("IsPalindrome Reverse:" + reverse + "?");
		return reverse.equals(s);
		
	}
	
	
	public static void main(String args[])	{
		
		
		
		String s = "sanracecarhdjd";
		getSubStringPalindrome(s);
		
	}

}

- Santhosh February 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

subString function omits last character in the string, update it to following:

String s = str.substring(i , j+1);

- Miral February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The complexity of your solution is O(n^3)

Here is a solution O(n+P) where P is the total size of all palindromes.

void print_palindromes(const std::string& s)
{
	auto n = s.length();
	for (auto i = 0; i < n; ++i)
	{
		// odd palindrome
		auto j = i;
		auto k = i;
		while (j >= 0 && k < n)
		{
			if (s[j] != s[k]) break;
			std::cout << s.substr(j,j-k+1) << std::endl;
			--j; ++k;
		}
		// even palindrome
		j = i-1;
		k = i;
		while (j >= 0 && k < n)
		{
			if (s[j] != s[k]) break;
			std::cout << s.substr(j,j-k+1) << std::endl;
			--j; ++k;
		}

	}
}

- Omri.Bashari May 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

s = our string

Keep two pointers. p1 is always one element behind p2. Every iteration, both are incremented. We check if s[p2] == s[p1] or s[p1-1]. If so, we know that we have a palindrome in some form, so we start recording the string with 2 pointers- iterate outwards until the palindrome ends and record all of the "visited" strings into an output table.

For example with the String "4racecarses", p1 and p2 are incremented until p2 = 5 and p1 = 4, s[p2] = s[p1-1]. Now, we iterate outwards: cec -> aceca -> racecar -> stop at 4racecars since the outward pointers won't match.

Back to the original loop, p2 is then at 6. Until it gets to the final element, it won't find a potential palindrome

In the end, add all single characters to the list

- SK February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

package com.practice.algo.and.ds.dp;

public class FindAllThePalindromesInString {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String str = "Mississippi";
		FindAllThePalindromesInString f = new FindAllThePalindromesInString();
		f.getAllPalindromes(str);
	}

	private void getAllPalindromes(String str) {
		// TODO Auto-generated method stub
	
		int[][] dp = new int[str.length()][str.length()];
		
		//Mark one length string as palindromes
		for(int i=0;i<str.length();i++){
			dp[i][i] = 1;	
		}

		//Mark two length string as palindromes if both start and end are same
		for(int i=0;i<str.length()-1;i++){
			if(str.charAt(i)==str.charAt(i+1))
				dp[i][i+1] = 1;	
		}
		
		
		for(int jump =2 ;jump<str.length();jump++){
			for(int i=0;i<str.length()-jump;i++){
				int j = i+jump;
				
				if(str.charAt(i)==str.charAt(j)){
					if(dp[i+1][j-1]>=1){
						dp[i][j] = dp[i+1][j-1]>=1?(1+dp[i+1][j-1]):0;
						for(int k=i;k<=j;k++){
							System.out.print(str.charAt(k));
						}
						System.out.println();
					}
				}else{
					dp[i][j] = 0;
				}
				 
			}	
		}
		
	}

}

- Anonymous April 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

package com.practice.algo.and.ds.dp;

public class FindAllThePalindromesInString {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String str = "Mississippi";
		FindAllThePalindromesInString f = new FindAllThePalindromesInString();
		f.getAllPalindromes(str);
	}

	private void getAllPalindromes(String str) {
		// TODO Auto-generated method stub
	
		int[][] dp = new int[str.length()][str.length()];
		
		//Mark one length string as palindromes
		for(int i=0;i<str.length();i++){
			dp[i][i] = 1;	
		}

		//Mark two length string as palindromes if both start and end are same
		for(int i=0;i<str.length()-1;i++){
			if(str.charAt(i)==str.charAt(i+1))
				dp[i][i+1] = 1;	
		}
		
		
		for(int jump =2 ;jump<str.length();jump++){
			for(int i=0;i<str.length()-jump;i++){
				int j = i+jump;
				
				if(str.charAt(i)==str.charAt(j)){
					if(dp[i+1][j-1]>=1){
						dp[i][j] = dp[i+1][j-1]>=1?(1+dp[i+1][j-1]):0;
						for(int k=i;k<=j;k++){
							System.out.print(str.charAt(k));
						}
						System.out.println();
					}
				}else{
					dp[i][j] = 0;
				}
				 
			}	
		}
		
	}

}

- Saurabh April 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First you start by populating a two-dimensional array with two arrays of objects, one for single characters (index 0, 1) and the other for double characters (index 0, 2), with the following information:
the palindrome itself and
the position in the string of the start of the palindrome.

From there you iterate through the arrays, starting at N = 3, with each step N starting off of array N - 2 (which starts at 0, N - 2 in the 2D array). For each palindrome in the array for the current step, check the string for if charAt(palindromeStart - 1) == charAt(palindromeStart + N), adding the substring for those positions to the Nth array in the 2D array. Repeat until the arrays of indices 0, N - 1 and 0, N - 2 are empty, or N > the total length of the string.

For a visual example, the strings "Mississippi" and "racecar" would give you

[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[M][i][s][s][i][s][s][i][p][p][i]
[ss][ss][pp]
[sis]
[issi][issi][ippi]
[ssiss]
[]EMPTY
[ississi]

and

[ ][ ][ ][ ][ ][ ][ ]
[r][a][c][e][c][a][r]
[ ]EMPTY
[cec]
[ ]EMPTY
[aceca]
[ ]EMPTY
[racecar]

Worst case complexity would be O(n^2), for a string of only identical characters, with an average case of O(n).

- Michael February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For a palindrome, it should have a pattern like this:
aa
aXa
where 'a' is a set of palindromic characters. e.g.
abba
abXba .. and so on.

An algo could be:
1. find a character that matches with another one. We can use a 'diff' that goes from 1 to length/2. If the characters at i-th and (i+diff)-th position matches, it's a potential palindrome.
2. if the diff==1, the characters are side by side, like 'ss', which is a palindrome anyway.
3. if the diff>1, check the characters from both sides, up to the middle of the substring. if it matches from both sides, it's a palindrome.

Something like this (elaborated with sysouts) ... can be tuned, though.

package com.mishra.partha.prep.simple;

public class Palindromes {
	public static void main(String[] args){
		String str="mississipi";
		System.out.println("Number of Palindromes found= "+getPalindromes(str));
	}
	static int getPalindromes(String s){
		int count=0;
		for(int diff=1; diff < s.length()/2; diff++){
			for(int i=0; i<s.length()-diff; i++){
				if(s.charAt(i)==s.charAt(i+diff)){
					count+= checkPalindromic(s,i,diff);
				}
			}
		}
		return count;
	}
	private static int checkPalindromic(String s, int i, int diff) {
		int end=i+diff;
		if (diff >1){
			for(int x=0; x<diff; x++){
				if(s.charAt(i+x)!=s.charAt(end-x)){
					return 0;
				}
			}
		}
		System.out.println("Found Palindrome: "+s.substring(i, end+1));
		return 1;
	}
}

Output comes as

Found Palindrome: ss
Found Palindrome: ss
Found Palindrome: sis
Found Palindrome: ipi
Found Palindrome: issi
Found Palindrome: issi
Found Palindrome: ssiss
Number of Palindromes found= 7

- partha.mishra February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ississi ?

- Miral February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually, on the last mississipi (missing a 'p') example, there should be one more palidrome... "ississi".

If Spelled correctly, it should have found 9... including
"ippi" and "pp"

- steve February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it's 10, actually
1 issi
2 sis
3 ssiss
4 s
5 p
6 M
7 ss
8 pp
9 ississi
10 i

- Anonymous February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution based on using two pointers (p1 and p2):

For odd palindromes
1) At each index i of the String s, set p1 to i - 1 and p2 to i + 1.
2) If s[p1] == s[p2], then we have a palindrome. Continue to next index until we reach boundary of string and set p1 = p1 - 1 and p2 = p2 + 1.

For even palindromes, it is the same as above but start with p1 = i instead of i - 1.

public static Set<String> findAllPalindromes(String string) {
		Set<String> palindromes = new HashSet<String>();
		
	    char[] stringAsCharArray = string.toCharArray();
	    
	    //Odd palindromes
	    for (int i=0; i < string.length(); i++) {
	    	int p1 = i - 1;
	    	int p2 = i + 1;
	    	
	    	while (p1 >= 0 && p2 < string.length()) {
	    		if (stringAsCharArray[p1] == stringAsCharArray[p2]) {
	    			palindromes.add(string.substring(p1, p2 + 1));
	    		} else {
	    			break;
	    		}
	    		p1 = p1 - 1;
	    		p2 = p2 + 1;
	    	}
	    }
	    
	    //Even palindromes
	    for (int i=0; i < string.length(); i++) {
	    	int p1 = i;
	    	int p2 = i + 1;
	    	
	    	while (p1 >= 0 && p2 < string.length()) {
	    		if (stringAsCharArray[p1] == stringAsCharArray[p2]) {
	    			palindromes.add(string.substring(p1, p2 + 1));
	    		} else {
	    			break;
	    		}
	    		p1 = p1 - 1;
	    		p2 = p2 + 1;
	    	}
	    }
	    
	    return palindromes;
	}

- Adam February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check even/odd for every centered palindromes:

#include <stdio.h>
#include <string.h>

int main(void)
{
        int i, j; 
        char str[] = "mississipi";
        int n = (int)strlen(str);
        int even, odd;

        for (i = 0; i < n; i++) {
                even = 1; 
                odd = 1; 
                for (j = 0; even || odd; j++) {
                        if (i - j < 0) 
                                break;
                        if (i + j >= n) 
                                break;
                        if (str[i + j] != str[i - j]) {
                                odd = 0; 
                        } else if (odd) {
                                printf("%.*s\n", 2 * j + 1,  str + i - j);
                        }

                        if (i + 1 + j >= n) 
                                continue;
                        if (str[i + 1 + j] != str[i - j]) {
                                even = 0; 
                        } else if (even) {
                                printf("%.*s\n", 2 * (j + 1), str + i - j);
                        }
                }
        }
        return 0; 
}

- ken February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

$ gcc -Wall -Wextra palin.c && ./a.out 
m
i
s
ss
issi
s
i
sis
ssiss
ississi
s
ss
issi
s
i
p
ipi
i

- ken February 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findAllPalindrome2(String str){
		List<String> result = new ArrayList<String>();
		for(int i=0;i<str.length();i++){
			getAllCombinations(result,str,i,str.length()-1);
		}
		
		for(String s:result){
			System.out.println(s);
		}
	}
	private static void getAllCombinations(List<String> result, String str,
			int startIndex,int endIndex) {
		if(endIndex<=startIndex){
			return ;
		}
		if(str.charAt(startIndex)==str.charAt(endIndex)){
			if(checkIfPalindrome(str,startIndex,endIndex)){
				//add to the result;
				result.add(str.substring(startIndex,endIndex+1));
			}
		}
		getAllCombinations(result, str, startIndex, endIndex-1);
		
	}
	private static boolean checkIfPalindrome(String str, int startIndex,
			int endIndex) {
		while(startIndex<=endIndex && startIndex<str.length() && endIndex>=0){
			if(str.charAt(startIndex++)!=str.charAt(endIndex--)){
				return false;
			}
		}
		return true;
	}

- Resh February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice and concise :)

void PrintPalindromes(char* pStr)
{
   char* pStart = pStr-1, *pEnd;
   while (*(pEnd = ++pStart)){
fail: while ((pEnd = strchr(pEnd+1, *pStart)) != NULL){
         for (int i = 0; (i < (pEnd-pStart+1)/2); i++)
            if (pStart[i] != pEnd[-i]) goto fail;
         std::cout << std::string(pStart, pEnd-pStart+1) << "\n";
      }
   }
}

- Tyson February 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<String> findPal(String str) {
        int global = 0, left = 0, right = 0;
        List<String> res = new ArrayList<String>();
        while (global < str.length()) {
            res.add(new String(new char[]{str.charAt(global)}));
            right++;
            while (right < str.length() && str.charAt(global) == str.charAt(right)) {
                res.add(str.substring(global, right + 1).intern());
                right++;
            }
            left--;
            while (right < str.length() && left >= 0) {
                if (str.charAt(left) == str.charAt(right)) {
                    res.add(str.substring(left, right + 1).intern());
                } else {
                    break;
                }
                right++;
                left--;
            }
            global++;
            right = global;
            left = global;
        }
        return res;

    }

- Iurii Mykhailov February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output:
M
i
s
ss
issi
s
i
sis
ssiss
ississi
s
ss
issi
s
i
p
pp
ippi
p
i

- Iurii Mykhailov February 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def f(a) {
    def sl = a.size()
    (1 .. sl).each{ l ->
        (0 .. sl-l).each{ i ->
            def ss = a.substring(i, i+l)
            if (ss?.reverse() == ss) print ss+' '
}   }   }
f('mississipi'); // m i s s i s s i p i ss ss sis ipi issi issi ssiss ississi

- sebnukem March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findAllPalindromes(String s){
		if(s.isEmpty() || s==null) throw new IllegalArgumentException();

		int n=s.length();
		boolean[][] res= new boolean[n][n];
		List<String> palindromes= new LinkedList<String>();

		for(int i=0;i<n;i++){
			res[i][i]=true;
			palindromes.add(Character.toString(s.charAt(i)));

		}
		
		for(int cl=2;cl<=n;cl++){
			for(int i=0;i<n-cl+1;i++){
				int j=i+cl-1;
				
				if(s.charAt(i)==s.charAt(j) && cl==2){
					palindromes.add(s.substring(i,j));
					res[i][j]=true;
				}
				else if(s.charAt(i)==s.charAt(j) ){
					res[i][j]=(res[i+1][j-1])?true:false;
					
					if(res[i][j] && j==n-1){
						palindromes.add(s.substring(i));
					}
					else if(res[i][j]){
						palindromes.add(s.substring(i,j+1));
					}				

				}
				else{
					res[i][j]=false;
				}
			}
		}

		for(String pal: palindromes){
			System.out.println(pal);
		}
	}

- dm November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findAllPalindromes(String s){
		if(s.isEmpty() || s==null) throw new IllegalArgumentException();

		int n=s.length();
		boolean[][] res= new boolean[n][n];
		List<String> palindromes= new LinkedList<String>();

		for(int i=0;i<n;i++){
			res[i][i]=true;
			palindromes.add(Character.toString(s.charAt(i)));

		}
		
		for(int cl=2;cl<=n;cl++){
			for(int i=0;i<n-cl+1;i++){
				int j=i+cl-1;
				
				if(s.charAt(i)==s.charAt(j) && cl==2){
					palindromes.add(s.substring(i,j));
					res[i][j]=true;
				}
				else if(s.charAt(i)==s.charAt(j) ){
					res[i][j]=(res[i+1][j-1])?true:false;
					
					if(res[i][j] && j==n-1){
						palindromes.add(s.substring(i));
					}
					else if(res[i][j]){
						palindromes.add(s.substring(i,j+1));
					}				

				}
				else{
					res[i][j]=false;
				}
			}
		}

		for(String pal: palindromes){
			System.out.println(pal);
		}
	}

- dm November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use dynamic programming

- dm November 12, 2016 | 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