Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
package LinkedList;
import java.util.LinkedList;
public class LinkedListNode {
int value;
LinkedListNode next = null;
public LinkedListNode(int i) {
this.value = i;
}
public LinkedListNode addNode(int i) {
this.next = new LinkedListNode(i);
return next;
}
public LinkedListNode getNext() {
return next;
}
@Override
public String toString() {
String restElement = value+"->";
LinkedListNode newNext = getNext();
while(newNext != null)
{restElement = restElement + newNext.value + "->";
newNext = newNext.getNext();}
restElement = restElement +newNext;
return restElement;
}
public static void main(String[] args) {
LinkedListNode headnode = new LinkedListNode(1);
headnode.addNode(2)
.addNode(3)//.addNode(4).addNode(5).addNode(6)
;
System.out.println(headnode);
headnode = reverse(null,headnode,headnode.getNext());
System.out.println(headnode);
}
private static LinkedListNode reverse(LinkedListNode prev, LinkedListNode current, LinkedListNode next) {
current.setNext(prev);
if(next == null)
return current;
return reverse(current,next,next.getNext());
}
private void setNext(LinkedListNode prev) {
this.next = prev;
}
}
This is my solution:
public class Link {
public int number;
public Link next;
public Link(int number) {
this.number = number;
this.next = null;
}
public void display() {
System.out.println(number);
}
public String toString() {
return Integer.toString(number);
}
public static void main(String[] args) {
LinkList as = new LinkList();
as.insertFirstLink(1);
as.insertFirstLink(2);
as.insertFirstLink(3);
as.insertFirstLink(4);
as.display();
as.reverse(as);
System.out.println("----");
as.display();
}
}
class LinkList {
public Link firstLink;
public LinkList() {
this.firstLink = null;
}
// Add element to Link List
public void insertFirstLink(int number) {
Link newLink = new Link(number);
// Reference to first link
newLink.next = firstLink;
// first link is now equal to last link added
firstLink = newLink;
}
public void display() {
Link theLink = firstLink;
if(theLink == null){
System.out.println("Empty LinkedList");
}
while (theLink != null) {
theLink.display();
System.out.println("Next link: " + theLink.next);
theLink = theLink.next;
System.out.println();
}
}
public void reverse(LinkList data){
Link curren = firstLink;
Link prev = null;
Link next = null;
while(curren != null){
next = curren.next;
curren.next = prev;
prev = curren;
curren = next;
}
firstLink = prev;
}
}
public class ReverseLinkedList {
Node l;
Node f;
int size = 0;
public void add(int i) {
Node newnode = new Node(l, i, null);
size++;
if (l == null) {
f = newnode;
} else {
l.next = newnode;
}
l = newnode;
}
public int get(int i) {
Node currentNode = l;
for (int j = 0; j <= size; j++) {
if (i == j)
return currentNode.i;
currentNode = currentNode.prev;
}
return -1;
}
private class Node {
int i;
Node prev;
Node next;
Node(Node prev, int i, Node next) {
this.prev = prev;
this.next = next;
this.i = i;
}
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package ds.linklist.op;
/**
*
* @author lokhavij
*/
public class SingleLinkList {
Node start;
Node current;
int length;
public void add(int data){
Node node;
if(start==null){
start=new Node(data);
current=start;
length=1;
}
else{
current.next=new Node(data);
current=current.next;
length++;
}
}
public void delete(int data){
Node item=start;
if(item.data==data){
start=item.next;
}
else{
while(item!=null) {
if(item.next.data==data){
item.next=item.next.next;
length--;
break;
}
item=item.next;
}
}
}
public void print(){
Node item=start;
while (item!=null) {
System.out.println(item.data);
item=item.next;
}
}
public int getCount(){
return length;
}
public void reverse(){
Node prevTmp=null;
Node nextTmp=null;
Node headTmp=start;
while(headTmp!=null){
nextTmp=headTmp;
headTmp=headTmp.next;
nextTmp.next=prevTmp;
prevTmp=nextTmp;
start=nextTmp;
}
}
public static void main(String[] args) {
SingleLinkList linkList=new SingleLinkList();
linkList.add(0);
linkList.add(1);
linkList.add(2);
linkList.add(3);
linkList.add(4);
linkList.add(5);
linkList.print();
System.out.println("length ->"+linkList.getCount());
linkList.reverse();
linkList.print();
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package ds.linklist.op;
/**
*
* @author lokhavij
*/
public class SingleLinkList {
Node start;
Node current;
int length;
public void add(int data){
Node node;
if(start==null){
start=new Node(data);
current=start;
length=1;
}
else{
current.next=new Node(data);
current=current.next;
length++;
}
}
public void delete(int data){
Node item=start;
if(item.data==data){
start=item.next;
}
else{
while(item!=null) {
if(item.next.data==data){
item.next=item.next.next;
length--;
break;
}
item=item.next;
}
}
}
public void print(){
Node item=start;
while (item!=null) {
System.out.println(item.data);
item=item.next;
}
}
public int getCount(){
return length;
}
public void reverse(){
Node prevTmp=null;
Node nextTmp=null;
Node headTmp=start;
while(headTmp!=null){
nextTmp=headTmp;
headTmp=headTmp.next;
nextTmp.next=prevTmp;
prevTmp=nextTmp;
start=nextTmp;
}
}
public static void main(String[] args) {
SingleLinkList linkList=new SingleLinkList();
linkList.add(0);
linkList.add(1);
linkList.add(2);
linkList.add(3);
linkList.add(4);
linkList.add(5);
linkList.print();
System.out.println("length ->"+linkList.getCount());
linkList.reverse();
linkList.print();
}
}
Using the power of recursion and dynamic programming
public void ReverseALikedList(myLinkedList<int> number)
{
if (number == null) return;
ReverseALikedList(number.Next);
CreateReverseLinkedList(number.data);
}
public LinkedList reversedLinkedList = new LinkedList();
private void CreateReverseLinkedList(int data)
{
reversedLinkedList.AddLast(data);
}
Consider
Reverse function should be like that:
- Mike L February 05, 2017