Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
public static Node incrementList(Node head){
if(head== null)
return head;
Node result= head;
Node firstNine= null;
while(head.next!= null){
if(firstNine== null && head.next.data==9)
firstNine= head;
else if(head.next.data<9)
firstNine=null;
head= head.next;
}
if(firstNine==null){
head.data=head.data+1;
return result;
}
if(firstNine==result && firstNine.data==9){
Node temp1= new Node(1);
temp1.next= result;
result=temp1;
}
while(firstNine!=null){
if(firstNine.data==9)
firstNine.data=0;
else firstNine.data=firstNine.data+1;
firstNine=firstNine.next;
}
return result;
}
public Node addOneToList(Node n){
Node current=n;
Node prev=null;
int length=0;
Node last=current;
while(current!=null){
length++;
if(current.data!=9)prev=current;
last=current;
current=current.next;
}// Now last is pointing to last digit.
// Prev is pointing to last non 9.
if(prev==null){
//case when number is all 9
Node head=new Node(1);
head.next=n;
while(n!=null){
n.data=0;
n=n.next;
}
return head;
}else{
prev.data=prev.data+1;
prev=prev.next;
while(prev!=null){
prev.data=0;
prev=prev.next;
}
return n;
}
}
public Node addOneToList(Node n){
Node current=n;
Node prev=null;
int length=0;
Node last=current;
while(current!=null){
length++;
if(current.data!=9)prev=current;
last=current;
current=current.next;
}// Now last is pointing to last digit.
// Prev is pointing to last non 9.
if(prev==null){
//case when number is all 9
Node head=new Node(1);
head.next=n;
while(n!=null){
n.data=0;
n=n.next;
}
return head;
}else{
prev.data=prev.data+1;
prev=prev.next;
while(prev!=null){
prev.data=0;
prev=prev.next;
}
return n;
}
}
struct Node {
int data; //digit
struct Node* next;
}
class LinkedList {
private:
Node* head;
public:
void AddOne();
}
void LinkedList::AddOne(){
if (head == null)
throw InvalidOperationException;
Node* cur = head;
Node* prev = null;
while (cur && cur->data == 9) {
cur->data = 0;
prev = cur;
cur = cur->next;
}
if (cur)
cur->data += 1;
else
prev->next = new Node(1, null);
}
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.iterator = None
def iter_on(self):
yield self
if self.next:
yield from self.next.iter_on()
def __iter__(self):
self.iterator = self.iter_on()
return self
def __next__(self):
return next(self.iterator)
def __str__(self):
return "[%d]" % self.value
def __repr__(self):
return self.__str__()
def print_on(self):
print(*self.iter_on(), sep="->")
def make_list(number):
root = None
cur_node = None
for digit_str in str(number):
new_node = Node(int(digit_str))
if cur_node:
cur_node.next = new_node
cur_node = new_node
if not root:
root = cur_node
return root
def add_one(root):
left_most_changeable = -1
right_most_changeable = -1
for idx, node in enumerate(root):
if node.value < 9:
left_most_changeable = idx
right_most_changeable = idx
for idx, node in enumerate(root):
if left_most_changeable <= idx <= right_most_changeable:
node.value += 1
if node.value > 9:
node.value = 0
if left_most_changeable == -1:
new_root = Node(1)
new_root.next = root
root = new_root
return root
l = make_list(999)
l.print_on() # [9]->[9]->[9]->[9]
l = add_one(l)
l.print_on() # [1]->[0]->[0]->[0]->[0]
- Anonymous March 08, 2017