Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
I assume it's a singly linked list, and the head place has greater value than the tail place.
Looks like the requirement of O(1) space doesn't leave a lot of choice.
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
next_ = NULL;
}
int val_;
Node *next_;
};
Node *AddDigit(Node *head, int digit)
{
int size = 0;
for (Node *n = head; n != NULL; n = n->next_) {
++size;
}
int carry = digit;
for (int i = size; i > 0 && carry != 0; --i) {
Node *n = head;
for (int j = 0; j < i - 1; ++j) {
n = n->next_;
}
int sum = n->val_ + carry;
n->val_ = sum % 10;
carry = sum >= 10 ? 1 : 0;
}
if (carry != 0) {
Node *new_head = new Node(carry);
new_head->next_ = head;
head = new_head;
}
return head;
}
void Print(Node *head)
{
for (Node *n = head; n != NULL; n = n->next_) {
cout << n->val_ << ", ";
}
cout << "\n";
}
int main()
{
Node *head = NULL;
for (int i = 0; i < 100; ++i) {
head = AddDigit(head, 1);
Print(head);
}
return 0;
}
- clk September 21, 2017