Interview Question for Software Engineer Interns


Country: United States




Comment hidden because of low score. Click to expand.
4
of 8 vote

I think your question is >>> "Find the number of anagrams of a given string which are palindrome".
Here is how I approach:
We assume that the string will contain only lowercase characters of the English alphabet.

1) Let the length of the string be 'n'.
2) Declare a count[0...25] array and count the number of occurrences of each character in the string. Note that there can be atmost one character with odd number of occurrences and it has to be in the middle of palindrome. Fix this character at the middle of the anagram string and reduce its count by 1. Now every character has even number of occurrences.
3) Divide the count array by 2 (i.e. reduce the count of every character by half).

for i in range(0, 25)
	set count[i] = count[i]/2.

4) We have to arrange these half of the characters in the first half of the anagram (and the other half has to be exactly the reverse of the first half). Now the problem reduces to >>> Find number of ways of arranging count[0] a's, count[1] b's, ... , count[25] z's in floor(n/2) positions.

m = floor(n/2);
Answer = m! / (count[0]! * count[1]! * ... * count[25]!);
//where, x! denotes factorial of x.

Please correct me if I've made a mistake.

- EOF July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the input string contains more than one character with odd count?

- subahjit July 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@subhajit ... then none of its permutations/anagrams can be a palindrome.

- EOF July 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the length of the given string is 10^6?

- gtkesh July 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Then you can calculate factorials and inverse-factorials (modulo some large prime).
x/factorial(y) = x*inverse-factorial(y) (mod p), where p is a prime. See Fermat's Little Theorem.
To find the multiplicative-inverse of a number 'a', we do the following.
a^p = a (mod p) ->>> follows from Fermat's little theorem.
a^(p-1) = 1 (mod p)
a^(p-2) = inverse(a) (mod p)

You'll have to preprocess the factorials and inverse-factorials in arrays using the following relation:

factorial[i] = i*factorial[i-1];

Alternatively you could compute the actual answer without actually computing the factorials. Since the answer is integral, you can intelligently divide and multiply things so that the intermediate result never overflows the integer range.

- EOF July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@all who voted down.... could you please tell me where my solution lags? .... I think its better than generating all the permutations which has an exponential complexity.

And yes if length of the string is 10^6 then all the solutions which depend on generating permutations can never give the answer.

If the length of string is 'n' then number of permutations = n!

If length of string is 30 (a very very small number) then:
number of permutations = 30! = 2.6525286e+32

Thus on a modern machine it will require (nearly) 10^16 years to give the answer for string of length = 30 (Yes! THIRTY).

- EOF July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a coding competition question: w w w.hackerrank.com/contests/july13/challenges/game-of-throne-ii

I will make the same argument that you did. Imagine the string is 200 characters long, then 100! will overflow even with 64bit unsigned long/integer. The question in the contest says the length of the string is: 1<=length of string <= 10^5, so imagine a string 100000 characters long and calculating 50000!.

I am sure there must be a better way of doing this.

- oOZz July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

IMO, EOF's solution is an optimized one. The logic to solve the problem is apparently correct, though the technical issues like overflowing can be handled by using modular arithmetic as suggested by him.

- Murali Mohan July 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent logic EOF

- rajdeeps.iitb August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For every possible permutation of the string where here every permutation of the string means an anagram then for a particular permutation or anagram we check whether it is a palindrome or not in the following way:
a. Divide the string into two halves.
b. Check for the left half if it is palindrome by again recursively dividing that left half further. Note that here the base case would be when at last two characters are are left and they are palindrome. Then when the recursive call returns check for the right half of this left half. And also note that when a single character is left then it is already a palindrome. (Single characters are always palindromes of themselves).
c. Similarly check for the right half.
d. Thus if this anagram is palindrome increase the count of palindromes.
e. At last return the number of palindromes that can occur with all the anagrams of the string.

- vgeek July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Generate all possible anagrams, add it to a Set (to avoid duplicates, in case of repeated alphabets) and check for Palindrome string individually..

public class PalindromeAnagrams {

	private static Set<String> anagrams = new HashSet<String>();
	
	public static void main(String[] args) 
	{
		String str = "ABBA";
		permutation("", str);
		System.out.println("ANAGRMAS\n-------------------");
		for(String s : anagrams)
		{
			System.out.println(s);
		}
		System.out.println("\n\nPALINDROME\n-------------------");
		checkForPalindroms();
	}
	
	private static void permutation(String prefix, String str) 
	{
	    int n = str.length();
	    if (n == 0) 
	    {
	    	anagrams.add(prefix);
	    }
	    else 
	    {
	        for (int i = 0; i < n; i++)
	        {
	            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1));
	        }
	    }
	}
	
	private static void checkForPalindroms() 
	{
		for(String str : anagrams)
		{
			boolean isPalindrome = false;
			int middle = str.length()/2;
			if(middle % 2 == 0)
			{
				isPalindrome = isPalindrome(str.substring(0, middle), str.substring(middle, str.length()));
			}
			else
			{
				isPalindrome = isPalindrome(str.substring(0, middle), str.substring(middle+1, str.length()));
			}

			if(isPalindrome)
			{
				System.out.println(str);
			}
		}
	}
	
	private static boolean isPalindrome(String firstHalf, String secondHalf)
	{
		StringBuilder sb = new StringBuilder(secondHalf);
		
		return firstHalf.equalsIgnoreCase(sb.reverse().toString());
	}
}

- no.1ankush July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

On my machine your code took 38 seconds for the string "ABBASDDFLM". And according to my calculation it will take 10^16 years for a string of length 30.

- EOF July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map.Entry;


public class CountPalindrome {
	public static void main(String[] args) {
		String input = "neveroddoreven";
		
		CountPalindrome cp = new CountPalindrome();
		char[] inpChars = new char[input.length()];
		input.getChars(0, input.length(), inpChars, 0);
				
		System.out.println(cp.countPalinAnags(inpChars));
	}
	
	public int countPalinAnags(char[] inp) {
		HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
		for (int i = 0; i < inp.length; i++) {
			Integer val = hm.get(inp[i]);
			if (null == val)
				hm.put(inp[i], 1);
			else
				hm.put(inp[i], val + 1);
		}
		
		int oddCharCnt = 0;
		int mirrCnt = 0;
		int denom = 1;
		for(Entry<Character, Integer> e : hm.entrySet()) {
			int n = e.getValue();
			if (n % 2 != 0)
				oddCharCnt++;
			
			if (oddCharCnt > 1)
				return 0;
			
			n /= 2;
			e.setValue(n);
			mirrCnt += n;
			denom *= factorial(n);
		}
		
		return factorial(mirrCnt) / denom;
	}
	
	private int factorial(int n) {
		int res = 1;
		while (n > 0) {
			res *= n;
			n -= 1;
		}
		
		return res;
	}
}

- arunbabuasp July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a coding competition question: w w w.hackerrank.com/contests/july13/challenges/game-of-throne-ii

- oOZz July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HackerRank ongoing challenge question.

- Nitin Gupta July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-Calculate the length of string. [length]

-As Palindrome consists of two kind of char... at most only one char can be single else it should be couple chars
For ex: abbcbba, abbbba,ababbcbbaba

-now get the no. of couple char [noOfCoupleChar]
-and get the no of non-coupled char [noOfNonCoupleChar]

for Ex: abbababbac
no of char 'a'=4
no of char 'b'=5
no of char 'c'=1

hence 
noOfCoupleChar = 8 and 
noOfNonCoupleChar =2

-get the no of all palindrome anagrams having length = noOfCoupleChar + 1
 [facorialOf(noOfCoupleChar / 2)] / [factorialOf(noOfOccuranceOfChar(a)/2)*factorialOf(noOfOccuranceOfChar(b)/2)..... ]*[noOfNonCoupleChar ]

-same as get the no of all palindrome anagrams having length = noOfCoupleChar
 [facorialOf(noOfCoupleChar / 2)] / [factorialOf(noOfOccuranceOfChar(a)/2)*factorialOf(noOfOccuranceOfChar(b)/2)..... ]

-like as we can calculate all possible palindromes of various length
<End Of Logic>

For Ex:
String: abbabcabba
no of couple # 4(a) + 4(b) = 8 
no of non couple  # 1(b) + 1(c) = 2
no of palindromes for length = 8+1 =>
[fact(4)]/[fact(2)*fact(2)]*[2] = 12

like wise calculate for all possible length of palindrome.

- PKT July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Firstly generate all the permutations of the given string ..
then individually check whether they are palindromes or not..

- jithin July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I didn't get this question completely. Did you mean return all the palindromic anagrams of a string?

- Epic_coder July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In other words, given a string, you are guaranteed that you can get "x" number palindromes if you rearrange the characters. For example: given "aaabbbb", the answer is 3 ( abbabba , bbaaabb and bababab).

- gtkesh July 06, 2013 | Flag


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