Amazon Interview Question Software Engineer in Tests
Country: United States
Interview Type: Phone Interview
LinkedList.metaClass.fillData { String pTest ->
for( c in pTest.toCharArray()) {
delegate.add(c)
}
return delegate
}
public boolean isPalindrome(LinkedList list){
if(list.size()==0) return true;
def asc = list.iterator();
def desc = list.descendingIterator();
while ( asc.next()==desc.next() ){
if (!asc.hasNext()) return true;
}
return false
}
assert isPalindrome(new LinkedList().fillData("lol"))
assert !isPalindrome(new LinkedList().fillData("nottrue"))
My Javascript solution, you can only iterate upto middle if you are maintaining size of list.
function node(data){
this.data = data;
this.next = null;
this.previous = null;
}
function list(){
this.head = null;
this.tail = null;
}
list.prototype.add = function(data){
let n =new node(data);
if(!this.head){
this.head = n;
this.tail = n;
return;
}
this.tail.next = n;
n.previous = this.tail;
this.tail = n;
}
let l = new list();
l.add('a')
l.add('b')
l.add('c')
l.add('b')
l.add('a')
function ispalindrome(l){
let h = l.head;
let t = l.tail;
while(h){
if(h.data !== t.data){
console.log('no');
return
}
h = h.next;
t = t.previous;
}
console.log('yes')
}
ispalindrome(l)
Java. Just keep two pointers and run front and back checking data of these pointers.
class Node {
Node next = null;
Node back = null;
int data;
public Node() {
}
public Node(Node next, Node prev, int data) {
this.next = next;
this.back = prev;
this.data = data;
}
}
private boolean isPalindrome(Node start) {
if(start == null)
return false;
if(start.next == null)
return true;
Node rearRunner = start; // from middle to back till start
Node runner = start.next;
Node frontRunner = runner; //from middle to end.
while(runner.next != null ) {
runner = runner.next;
frontRunner = frontRunner.next;
if(runner.next != null) {
runner = runner.next;
rearRunner = rearRunner.next;
}
}
boolean isPalindrome = true;
while(frontRunner != null) {
if(rearRunner.data != frontRunner.data) {
isPalindrome = false;
break;
} else {
rearRunner = rearRunner.back;
frontRunner = frontRunner.next;
}
}
return isPalindrome;
}
public class DLLPalindrome {
static DoublyLinkedList DLL = new DoublyLinkedList();
public static void main(String args[])
{
DLLPalindrome dp = new DLLPalindrome ();
dp.populateDLL();
DLL.iterateForward();
dp.isPalindrome(DLL);
}
private void isPalindrome(DoublyLinkedList dll) {
for(int i=0;i<dll.getSize()/2;i++)
{
if(dll.head.data == dll.tail.data)
{
dll.head = dll.head.next;
dll.tail = dll.tail.prev;
}
else
{
System.out.println("not a palindrome");
}
}
}
private void populateDLL() {
DLL.addDataToFirst(4);
DLL.addDataToFirst(5);
DLL.addDataToLast(4);
DLL.addDataToLast(5);
}
}
Public static boolean IsPaL(Node head){
if(head == null || head.next == null)return true;
int size = 1;
Node temp = head;
while(temp.next != null){
size++;
temp = temp.next;
}
int middle;
if(size % 2 == 1)middle = (size/2)+1;
else{
size = size / 2;
}
Node temp1 = head;
while(middle != 0){
if(temp1.data != temp.data)return false;
temp = temp.prev;
temp1 = temp1.next
}
return true;
}
class Node:
def __init__(self,data):
self.data = data
self.next = None
self.prev = None
class Linkedlist:
def __init__(self):
self.head = Node(None)
def AddNode(self,data):
newnode = Node(data)
currnode = self.head.next
if currnode == None:
currnode = self.head
while currnode.next is not None:
currnode = currnode.next
currnode.next = newnode
newnode.prev = currnode
def IsPalindrome(self):
tempstring_frwd= ""
tempstring_rev = ""
if self.head.next == None :
print "LinkedList doesn't have any nodes"
return
currnode = self.head.next
while currnode.next :
tempstring_frwd += str(currnode.data)
currnode = currnode.next
tempstring_frwd += str(currnode.data)
while currnode.prev:
tempstring_rev += str(currnode.data)
currnode = currnode.prev
if tempstring_rev == tempstring_frwd :
return "Palindrome"
else:
return "Not Palindrome"
dl = Linkedlist()
dl.AddNode(1)
dl.AddNode(2)
dl.AddNode(3)
dl.AddNode(2)
dl.AddNode(1)
print dl.IsPalindrome()
C++ Solution
struct Node {
string data;
Node *next;
Node *prev;
};
Node* createNode(string& A, Node *prev, Node* next);
void display(Node* head);
bool isPalindrome(Node* firstNode, Node* lastNode);
void destroyList(Node* first);
int main(int argc, char** argv)
{
string A [] = {"A", "B","B","A"};
int size = sizeof(A) / sizeof(A[0]);
// Head Node
Node * firstNode = NULL;
Node * lastNode = NULL;
for ( int index=0; index <size ; index++ )
{
if ( firstNode == NULL )
{
firstNode = createNode(A[index], NULL, NULL);
lastNode = firstNode;
}
else
{
lastNode->next = createNode(A[index], lastNode, NULL );
lastNode = lastNode->next; // Move to the next node
}
}
display(firstNode);
// Check is plaindrome?
cout<<"Is Palindrome:"<< isPalindrome(firstNode, lastNode) <<endl;
display(firstNode);
return 0;
}
Node* createNode(string & A, Node* prev, Node* next)
{
Node* newPtr = new Node();
newPtr->data = A;
newPtr->next = next;
newPtr->prev = prev;
return newPtr;
}
// Is Palindrome
bool isPalindrome(Node* firstNode, Node* lastNode)
{
while( firstNode != lastNode)
{
if ( firstNode->data != lastNode->data)
{
return 0;
}
firstNode = firstNode->next;
lastNode = lastNode->prev;
}
return 1;
}
//file: Link_node.java:
public class Link_Node {
char letter;
Link_Node next;
Link_Node prev;
public Link_Node (char letter) {
this.letter =letter;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Link_Node current = this;
while (current != null) {
sb.append(current.letter + "->");
current = current.next;
}
return sb.toString();
}
}
//file Main.java:
public class Main {
public static void main(String[] args) {
Link_Node a = new Link_Node('a');
Link_Node b = new Link_Node('b');
Link_Node c = new Link_Node('c');
Link_Node d = new Link_Node('b');
Link_Node e = new Link_Node('a');
//a<->b<->c<->d<->e
a.next = b; b.prev = a;
b.next = c; c.prev = b;
c.next = d; d.prev = c;
d.next = e; e.prev = d;
Solution s = new Solution();
boolean result = s.isDLLPalindrome(a);
System.out.println(result);
}
}
//file Solution.java:
//Time complexity: O(n)
//Space : O(1)
public class Solution {
public boolean isDLLPalindrome(Link_Node first) {
if (first == null) {return true;}
Link_Node last = first;
while (last.next != null) {
last = last.next;
}
while (first != last) {
if (first.letter != last.letter) {
return false;
}else {
first = first.next;
last = last.prev;
}
}
return true;
}
}
public boolean check(Node node) {
if (node == null)
return false;
Node last = null;
head = node;
boolean b = false;
int count = 0;
while(head!=null) {
last = head;
head = head.next;
count ++;
}
head = node;
while(count>0) {
if(head.data==last.data) {
head = head.next;
last = last.prev;
b = true;
}
else {
b = false;
break;
}
count--;
}
return b;
}
public void checkPalindrone() {
if(head != null) {
int size=0;
Node n = head;
Node start = head;
Node end = null;
Boolean isPalindrone = false;
while(null!=n) {
end = n;
n=n.next;
size++;
}
for(int i =1; i<=size/2 ; i++) {
if(start.data == end.data){
isPalindrone = true;
} else {
isPalindrone = false;
break;
}
start = start.next;
end = end.previous;
}
if(isPalindrone) {
System.out.println("it is palindrone");
} else {
System.out.println("not palindrone");
}
}
}
public void checkPalindrone() {
if(head != null) {
int size=0;
Node n = head;
Node start = head;
Node end = null;
Boolean isPalindrone = false;
while(null!=n) {
end = n;
n=n.next;
size++;
}
for(int i =1; i<=size/2 ; i++) {
if(start.data == end.data){
isPalindrone = true;
} else {
isPalindrone = false;
break;
}
start = start.next;
end = end.previous;
}
if(isPalindrone) {
System.out.println("it is palindrone");
} else {
System.out.println("not palindrone");
}
}
}
1. Set one pointer at start and another at last
- Dinkar February 19, 20172. Start pointer move next
3 last pointer move prev
4. At each move 2&3 check if both values not equal return false
Else return true outside the loop