## CGI-AMS Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

An O(n) solution in code:

``````string S = "aabbccd";
int count[26];
memset(count, 0, sizeof(count));

for(int i = 0; i < S.size(); i++){
count[S[i] - 'a']++;
}

int odds = 0;

for(int i = 0; i < 26; i++){
if(count[i] % 2 == 1){
odds++;
}
}

return odds <= 1;``````

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

package com.test;

public class PolindromString {

public static void main(String[] args) {
// TODO Check Polindrom
boolean p=true;
String s="assa";
int k=s.length()-1;
for(int i=0; i<=k;i++,k--){

if (s.charAt(i)!=s.charAt(k)){
p=false;
break;
}

}
if(p&s.length()!=0)
System.out.println(s+" is palindrom");
else
System.out.println(s+" is not palindrom");

}

}

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

Count the number of occurrences of each character. Let A the number of characters that have an odd number of occurrences in the string. You can shuffle for palindrome if:

A = 0 or A = 1

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

string S = "aabbccd";
int count[26];
memset(count, 0, sizeof(count));

for(int i = 0; i < S.size(); i++){
count[S[i] - 'a']++;
}

int odds = 0;

for(int i = 0; i < 26; i++){
if(count[i] % 2 == 1){
odds++;
}
}

return odds <= 1;

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

``````private static final int ASCII_MAX = 255;

boolean canBePalindrome(String str){
checkNotNull(str, "'str' is NULL");

BitSet foundChars = new BitSet(ASCII_MAX+1);

int strLength = str.length();
int chCode;

for( int i =0; i < strLength; i++){
chCode = str.charAt(i);
checkArgument(chCode <= ASCII_MAX, "Not an ascci character found, code: " + chCode);
foundChars.flip(chCode);
}

boolean isStrLengthOdd = (str.length() & 1) != 0;
int foundCharsCardinality = foundChars.cardinality();

return (isStrLengthOdd && foundCharsCardinality == 1 ) || (! isStrLengthOdd && foundCharsCardinality == 0 );
}``````

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

For a string to form palindrome, number of character occuring odd number of times should be <= 1. For example, aabbaa(0 odd chars) or aabaa or abcccba (1 odd chars).
So this problem can be reduced to find the number of characters occurring odd number of times <= 1.

There are 2 solutions I can think of
1) Sort the characters and count the number of times each character occurs.
Complexity O(nlogn + n) = O(n log n )
2) Hash the characters with number of times they occur and check how many characters occur odd number of times = O(n + number of unique chars) = O(n)

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

Find frequency of each characters.
If the number of characters wtih odd frequence <= 1 then YES else NO

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

``````import java.util.Arrays;

/* Program to check if Anagram of a String is a palindrome or not*/
public class AnagramOfStringIsPalindrome {
public static void main(String arr[]){
String str = "aabbcdcaa11";
System.out.println(isPalindrome(str));
}
public static String isPalindrome(String str){
/* Converting String to Array and sorting it */
char[] a = str.toCharArray();
Arrays.sort(a);
int uniqueCount = 0;
/* Check if adjacent elements after sorting match */
/* Keep a count of no of elements that dint match if its just one its still a palindrome */
for(int i=0;i<a.length-1;){
if(a[i] == a[i+1]){
i += 2; continue;
}else{
uniqueCount++;
if(uniqueCount>1)
return "Not a Palindrome";
}
}
return "Is Palindrome";
}
}``````

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

import java.util.*;
public class palindrome {

public static void main(String[] args) {
String str="abcdcba";
int count=0;
Map<Character,Integer> hmap=new HashMap<Character,Integer>();
for(int i=0;i<str.length();i++)
{
if(hmap.containsKey(str.charAt(i)))
hmap.put(str.charAt(i),hmap.get(str.charAt(i))+1);
else
hmap.put(str.charAt(i), 1);

}

Set set=hmap.entrySet();
Iterator itr=set.iterator();
while(itr.hasNext())
{
Map.Entry me=(Map.Entry)itr.next();
Integer i=(Integer)me.getValue();
if(i%2!=0)
count++;

}
if(count==1||count==0)
System.out.println("can be palindrome");
else
System.out.println("not palindrome");
}
}

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

``````import java.util.*;
public class palindrome {

public static void main(String[] args) {
String str="abcdcba";
int count=0;
Map<Character,Integer> hmap=new HashMap<Character,Integer>();
for(int i=0;i<str.length();i++)
{
if(hmap.containsKey(str.charAt(i)))
hmap.put(str.charAt(i),hmap.get(str.charAt(i))+1);
else
hmap.put(str.charAt(i), 1);

}

Set set=hmap.entrySet();
Iterator itr=set.iterator();
while(itr.hasNext())
{
Map.Entry me=(Map.Entry)itr.next();
Integer i=(Integer)me.getValue();
if(i%2!=0)
count++;

}
if(count==1||count==0)
System.out.println("can be palindrome");
else
System.out.println("not palindrome");
}
}``````

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

``````package com.test;

public class PolindromString {

public static void main(String[] args) {
// TODO Check Polindrom
boolean p=true;
String s="assa";
int k=s.length()-1;
for(int i=0; i<=k;i++,k--){

if (s.charAt(i)!=s.charAt(k)){
p=false;
break;
}

}
if(p&s.length()!=0)
System.out.println(s+" is palindrom");
else
System.out.println(s+" is not palindrom");

}

}``````

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

``````package com.test;

public class PolindromString {

public static void main(String[] args) {
// TODO Check Polindrom
boolean p=true;
String s="assa";
int k=s.length()-1;
for(int i=0; i<=k;i++,k--){

if (s.charAt(i)!=s.charAt(k)){
p=false;
break;
}

}
if(p&s.length()!=0)
System.out.println(s+" is palindrom");
else
System.out.println(s+" is not palindrom");

}

}``````

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

``````package com.test;

public class PolindromString {

public static void main(String[] args) {
// TODO Check Polindrom
boolean p=true;
String s="assa";
int k=s.length()-1;
for(int i=0; i<=k;i++,k--){

if (s.charAt(i)!=s.charAt(k)){
p=false;
break;
}

}
if(p&s.length()!=0)
System.out.println(s+" is palindrom");
else
System.out.println(s+" is not palindrom");

}

}``````

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.