jsk1016
BAN USERclass LL_Node {
public int data;
public LL_Node next;
LL_Node(int d) {
data = d;
}
}
public class FacebookLLChange {
static void printLL(LL_Node head) {
while (head != null) {
System.out.print(head.data+"->");
head = head.next;
}
System.out.println("null");
}
static LL_Node rearrangeLL(LL_Node head) {
LL_Node curr = head;
LL_Node temp1, temp2;
// Start by removing "5" and inserting it in between "1" and "2"
while (curr.next.next != null) {
curr = curr.next;
}
temp1 = curr.next; // 5->null
curr.next = null;
curr = head;
temp2 = curr.next; // 2->3->4->null
curr.next = temp1;
curr.next.next = temp2;
// Similarly, remove "4" and insert it between "2" and "3"
while (curr.next.next != null) {
curr = curr.next;
}
temp1 = curr.next; // 4->null
curr.next = null;
curr = head.next.next;
temp2 = curr.next; // 3->null
curr.next = temp1;
curr.next.next = temp2;
return head;
}
public static void main(String[] args) {
// Load all elements on new Linked List
LL_Node head = new LL_Node(1);
LL_Node curr = head;
for (int i = 1; i < 5; i++) {
curr.next = new LL_Node(i+1);
curr = curr.next;
}
System.out.println("Before change: ");
printLL(head); // 1->2->3->4->5->null
// Change Linked List without any O(n) sized buffers
head = rearrangeLL(head);
System.out.println("After change: ");
printLL(head); // 1->5->2->4->3->null
}
}
Time: O(n)
Space: O(n)
public class PalindromeChunks {
static int longestChunkedPalindrome(String s) {
int chunkCount = 0;
String left = "", right = "";
int i = 0, j = s.length() - 1;
while (i < j) {
left = left + s.substring(i, i+1);
right = right + s.substring(j, j+1);
if (left.equals(new StringBuilder(right).reverse().toString())) {
chunkCount += 2;
left = "";
right = "";
}
++i;
--j;
}
if ( (!left.equals("") && !right.equals("")) || i == j) // middle chunk left over
++chunkCount;
return chunkCount;
}
public static void main(String[] args ) {
System.out.println("VOLVO: "+longestChunkedPalindrome("VOLVO")); // 3
System.out.println("merchant: "+longestChunkedPalindrome("merchant")); // 1
System.out.println("ghiabcdefhelloadamhelloabcdefghi: "+longestChunkedPalindrome("ghiabcdefhelloadamhelloabcdefghi")); // 7
}
}
The result I got from the code above was (a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a) with an answer of 11. Is this still wrong? (It won't let me reply to you so I made a new comment thread).
- jsk1016 December 10, 2016