AMD Interview Question
AssociatesCountry: India
Interview Type: In-Person
public static void printPalindrom(int N)
{
List<int> list = new List<int>();
while(N>0)
{
list.Add(1);
if (list.Count <= 2)
{
Console.WriteLine();
foreach (int n in list)
{
Console.Write(n);
}
N--;
continue;
}
int i = 0;
int j = list.Count - 1;
while (i <= j - 2)
{
i++;
j--;
list[i] = 0;
list[j] = 0;
}
while (i >= 0 && N > 0)
{
Console.WriteLine();
foreach (int n in list)
{
Console.Write(n);
}
list[i] = 1;
list[j] = 1;
i--;
j++;
N--;
}
}
}
My idea is we use an ArrayList to store all Palindromes. And
F(2i) = "1" + F(2i-2) + "1";
F(2i +1) = "1" + F(2i-2) + "1";
With F(j) is all values in this ArrayList. Note that before we add new value to ArrayList, we ensure that F(2i-2) and F(2i-1) have exact length by adding "0" at 2 sizes of F. (I use method format(String s, int length) to do this)
import java.util.ArrayList;
public class FirstNPalindromes {
public static void main(String[] args) {
print(10);
}
private static void print(int n) {
ArrayList<String> list = new ArrayList<>();
list.add("0");
list.add("1");
list.add("11");
if (n == 0) {
return;
}
if (n >= 1) {
System.out.println("1");
}
if (n >= 2) {
System.out.println("11");
}
int length = 3;// length of current palindromes
int current = 3; // count size
int i = 3;
int j = 0;
while (i < n) {
j = 0;
current = list.size();
while (j < current && i <= n) {
String obj = list.get(j);
if ((length - obj.length()) % 2 != 0) {
if (j == 0) {
obj = "1" + format("", length - 2) + "1";
list.add(obj);
System.out.println(obj);
}
j++;
continue;
}
obj = "1" + format(obj, length - 2) + "1";
list.add(obj);
System.out.println(obj);
j++;
i++;
}
length++;
}
}
private static String format(String s, int length) {
StringBuilder builder = new StringBuilder();
int need = (length - s.length()) / 2;
for (int i = 0; i < need; i++) {
builder.append("0");
}
StringBuilder builderTotal = new StringBuilder();
builderTotal.append(builder).append(s).append(builder);
return builderTotal.toString();
}
}
Converting int to binary and checking if its a palindrome.
public class PrintBinaryPalindome {
public static void main(String[] args) {
//Print first N binary palindrome numbers
binaryPalindome(20);
}
////////////////////////////////////////
//Method to Print N binary palindrome///
////////////////////////////////////////
public static void binaryPalindome(int n) {
int i = 1;
while (n > 0) {
int binaryValue = decimalToBinary(i);
if (isPalindrome(String.valueOf(binaryValue))) {
System.out.println(binaryValue);
n--;
}
i++;
}//End of while
} //End of binaryPalindome() method
////////////////////////////////////////
//Method to convert Decimal to Binary///
////////////////////////////////////////
private static int decimalToBinary(int input) {
// Special case
if (input == 1 || input == 0)
return input;
int result = 0;
int p = 0;
int base = 2;
int finalBase = 10;
while (Math.abs(input) > 0) { // 5
int reminder = input % base;
result += reminder * Math.pow(finalBase, p);
input /= base;
p++;
} // End of while
return result;
}// End of decimalToBinary() Method
//////////////////////////////////////////////////////
//Method to Check if a number is palindrome or not?///
//////////////////////////////////////////////////////
private static boolean isPalindrome(String str){
if(str==null)
return false;
StringBuffer sb = new StringBuffer(str);
sb.reverse();
return sb.toString().equals(str);
}//End of isPalindrome() method
}
{
//if n is less than 3 ,then its a trivial palindrome
private static String [] trivialPalin ={"1","11"};
//main method which prints the palindromes
public static void printBinaryPalin(int n){
String arr[]=new String[n];
for(int i=0;i<((n>2)?2:n);i++)
arr[i]=trivialPalin[i];
int digitCount=1;
//for n>2 ,we use a recursive sub method to fetch substrings which are palindromes
//involving zeroes and ones
for(int i=3;i<=n;){
//call submethod which returns substrings of digit count
//for i=3 we call the sub method to return substring of digitcount i-2 ,that is 1 and
//soon
List<String> subStr = fetchSubStrPalin(digitCount);
digitCount++;
for(String str:subStr){
//we append 1 at the beginning to increase digits and a correspoding 1 at
//the end to make it a palindrome
arr[i-1]="1"+str+"1";
i++;
if(i>n)
break;
}
}
//print the accumulated binary palindromes
for(String str:arr){
System.out.println(str);
}
}
//recursive method to return palindromes involving 0 and 1
public static List<String> fetchSubStrPalin(int digits){
List<String> subStrList = new ArrayList<String>();
//trivial case 1
if(digits==1){
subStrList.add("0");
subStrList.add("1");
return subStrList;
}
else if(digits==2){//trivial case 2
subStrList.add("00");
subStrList.add("11");
return subStrList;
}
//if it is not a trivial case call recursively for digits -2
List<String> recursiveRes= (fetchSubStrPalin(digits-2));
//append 0 at beginning and end to make it a palindrome starting and ending with 0
for(String str:recursiveRes){
subStrList.add("0"+str+"0");
}
//similarly append 1 at beginning and end to make it a palindrome with
//begiining and trailing 1's
for(String str:recursiveRes){
subStrList.add("1"+str+"1");
}
return subStrList;
}
}
{{
import sys
def gen_bin(n):
pal = ['1']
if n < 1:
return []
if n < 2:
return pal
# How many palindromes I've encountered so far
count = 1
# Lenght of the next binary string
bin_len = 2
while True:
# Odd binary strings need a middle filler
middle = [''] if not bin_len % 2 else ['0', '1']
# Each binary number of lenght L will count up to
# 2**L. I'm only interested in odd counts to avoid
# leading zeros in the solution.
for x in xrange(1, 2**(bin_len/2), 2):
# Get binary string
s = bin(x)[2:]
# Pad with leading zeros
s = '0' * (bin_len/2 - len(s)) + s
for mid in middle:
pal.append(s[::-1] + mid + s)
count += 1
if count == n:
# Short cirtuit here to avoid extra computation.
return pal
bin_len += 1
print gen_bin(int(sys.argv[1])
}}
We can count up from 0 and reverse and add every number to itself which will give us the correct ordering. The important trick is to hold off with the odd length palindromes until we hit a new power of two.
private List<String> getBitPalindromes(int count) {
List<String> palindromes = new ArrayList<>(), oddLengths = new ArrayList<>();
palindromes.add("1");
int current = 1, powOfTwo = 0;
while (palindromes.size() < count) {
if (powOfTwo != Integer.numberOfLeadingZeros(current)) {
palindromes.addAll(oddLengths);
oddLengths.clear();
powOfTwo = Integer.numberOfLeadingZeros(current);
}
String left = Integer.toBinaryString(current);
String right = new StringBuilder(left).reverse().toString();
palindromes.add(left + right);
oddLengths.add(left + "0" + right);
oddLengths.add(left + "1" + right);
current++;
}
return palindromes.subList(0, count);
}
public class BinStrPalindrome { public static void generateBinStrings(int n){ /* * Helper function to set up the recursive call to generateBinStrings */ //Check for valid input if (n<1){ return; } // These 3 cases can produce all binary string palindromes. It is easy to see that they will not // produce any overlapping solutions. generateBinStrings("", n); // This will generate all even length palindromes generateBinStrings("1", n); //This will generate all odd length palindromes where '1' is middle bit generateBinStrings("0", n); //This will gererate all odd length palindromes where '0' is middle bit } private static void generateBinStrings(String bin_string, int n){ /* * prints all binary string palindromes up to length n */ //We don't want to print any palindromes that start (and end) in '0' also don't print the empty string if (bin_string.length() > 0 && bin_string.charAt(0) != '0'){ System.out.println(bin_string); } // Make sure we stop at n if (bin_string.length() + 2 <= n){ //Recursively generate the next palindrome by either appending '1' to both sides or '0' generateBinStrings("1" + bin_string + "1", n); generateBinStrings("0" + bin_string + "0", n); } } public static void main(String[] args){ generateBinStrings(12); generateBinStrings(3); generateBinStrings(0); } }
#include<iostream>
using namespace std;
const int MAX_CHAR = 256;
void makestarting(char* s, int num) { //num is always >2
int c = 0;
s[c++] = '1';
while (c <= num - 2) {
s[c++] = '0';
}
s[c] = '1';
}
void printxy(char* s, int start, int end) {
if (start>end) return;
if (start == end) {
cout << s << endl;
s[start] = '0' + ((s[start] == '0') ? 1 : 0);
cout << s << endl;
s[start] = '0' + ((s[start] == '0') ? 1 : 0);
}
printxy(s, start + 1, end - 1);
s[start] = s[end] = ('0' + ((s[start] == '0') ? 1 : 0));
printxy(s, start + 1, end - 1);
s[start] = s[end] = ('0' + ((s[start] == '0') ? 1 : 0));
return;
}
void PrintAllPermutations(int N) {
if (N <= 0 || N>= MAX_CHAR) return;
if (N >= 1) cout<< "1" << endl;
if (N >= 2) cout << "11" << endl;
char STR[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++) {
STR[i] = 0;
}
int last = 2;
while (last <= N) {
makestarting(STR, last + 1);
printxy(STR, 1, last-1);
last++;
}
}
int main() {
int T, N;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
cout << "Test Case : #" << i + 1 << endl;
PrintAllPermutations(N);
}
}
void makestarting(char* s, int num) { //num is always >2
int c = 0;
s[c++] = '1';
while (c <= num - 2) {
s[c++] = '0';
}
s[c] = '1';
}
void printxy(char* s, int start, int end) {
if (start>end) return;
if (start == end) {
cout << s << endl;
s[start] = '0' + ((s[start] == '0') ? 1 : 0);
cout << s << endl;
s[start] = '0' + ((s[start] == '0') ? 1 : 0);
}
printxy(s, start + 1, end - 1);
s[start] = s[end] = ('0' + ((s[start] == '0') ? 1 : 0));
printxy(s, start + 1, end - 1);
s[start] = s[end] = ('0' + ((s[start] == '0') ? 1 : 0));
return;
}
void PrintAllPermutations(int N) {
if (N <= 0 || N>= MAX_CHAR) return;
if (N >= 1) cout<< "1" << endl;
if (N >= 2) cout << "11" << endl;
char STR[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++) {
STR[i] = 0;
}
int last = 2;
while (last <= N) {
makestarting(STR, last + 1);
printxy(STR, 1, last-1);
last++;
}
}
void makestarting(char* s, int num) { //num is always >2
int c = 0;
s[c++] = '1';
while (c <= num - 2) {
s[c++] = '0';
}
s[c] = '1';
}
void printxy(char* s, int start, int end) {
if (start>end) return;
if (start == end) {
cout << s << endl;
s[start] = '0' + ((s[start] == '0') ? 1 : 0);
cout << s << endl;
s[start] = '0' + ((s[start] == '0') ? 1 : 0);
}
printxy(s, start + 1, end - 1);
s[start] = s[end] = ('0' + ((s[start] == '0') ? 1 : 0));
printxy(s, start + 1, end - 1);
s[start] = s[end] = ('0' + ((s[start] == '0') ? 1 : 0));
return;
}
void PrintAllPermutations(int N) {
if (N <= 0 || N>= MAX_CHAR) return;
if (N >= 1) cout<< "1" << endl;
if (N >= 2) cout << "11" << endl;
char STR[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++) {
STR[i] = 0;
}
int last = 2;
while (last <= N) {
makestarting(STR, last + 1);
printxy(STR, 1, last-1);
last++;
}
}
import java.util.LinkedList;
import java.util.Queue;
public class BinaryPal {
public static void printNum(int n){
Queue q = new LinkedList();
q.add("1");
while(n!=0){
n--;
String s1=(String) q.peek();//retrives the node's value but do not removes it
q.poll();//gets the first node and removes it from the queue
//System.out.println(s1);
String temp=new StringBuffer(s1).reverse().toString();
if(temp.equals(s1)){
System.out.println(s1);
}
String s2=s1;
q.add(s1.concat("0"));
q.add(s2.concat("1"));
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int n=10;
printNum(100);
}
}
- Indraja.Punna June 13, 2016