Amazon Interview Question Software Engineer in Tests
Country: India
Interview Type: Written Test
Not seeing how this is printing the last k nodes in reverse. It looks like it only print the first k nodes.
1) if will give exception when root length is < k
2) it's a single linked list and it can't go backward.
3) k only says number of nodes to print, not the position in the list.
I think you need to create an array with size of k. Fill the array from the list root[root.length-k] to root[root.Length] then print the array in reverse. That's O(n*m), n is the size of the single linked list. m is the size the temporary array.
If it's a double linked list, you can start from the back and do root.prev k-th times to print data from each node, but that's too easy.
Stack will make the code more readable and simple as well:
public static void PrintKnodeTillTail(LinkedList list, int k){
if (k < 1 || list == null)
return;
LinkedList regularPtr = list;
LinkedList kAheadPtr = list;
// Move the first pointer K nodes ahead
for (int i = 0; i < k; i++){
kAheadPtr = kAheadPtr.Next;
if (kAheadPtr == null)
return;
}
// when kAhead reaches end regularptr reaches K node before end
while (kAheadPtr != null){
kAheadPtr = kAheadPtr.Next;
regularPtr = regularPtr.Next;
}
// push the K nodes to stack
Stack<LinkedList> stk = new Stack<LinkedList>();
while (regularPtr != null){
stk.Push(regularPtr);
regularPtr = regularPtr.Next;
}
// pop and print them
while (stk.Count > 0)
Console.WriteLine(stk.Pop().Data);
}
Improved solution, using Prasad's code without the need for an additional external counter field: we can pass k by pointer/reference and decrement it within the function. Adapted for C#:
public void GetLastLL2(LLNode node, ref int k)
{
if (node != null)
{
GetLastLL2(node._next, ref k);
if (k-- > 0)
Console.WriteLine(node._val);
}
}
int counter=0;
Public void printList(Node root, int k)
{
If(root!=null)
{
printList(root.next);
counter++;
if(counter==k)
Print root.data;
}
}
The above algorithm takes O(n) time.
void printFromTail( Node root , int k ) {
if(root== null ) throw new InvalidArgumentException();
int[] mutable = int[1];
mutable[0] = k;
printTreeFromTailCore(root, mutable) ;
}
void printTreeFromTailCore(Node root , int[] mutable) {
if(root == null || mutable == null ) return ;
printTreeFromTailCore(root.next, mutable) ;
mutable[0] -- ;
if(mutable[0] >= 0 ) {
System.out.println(root.value) ;
} else {
return ;
}
}
public void getLastNElementFromLinkList(LinkedList<Integer> llist, int n) {
LinkedList<Integer> templist = new LinkedList<>();
it = llist.iterator();
printLastNElement(llist, n);
}
void printLastNElement(LinkedList<Integer> llist, int m) {
totalelement++;
int elementcountiniteration = totalelement;
if (it.hasNext()) {
Integer element = (Integer) it.next();
printLastNElement(llist, m);
if ((totalelement - elementcountiniteration) <= 3) {
System.out.println(element.intValue());
}
}
}
public void printReverseNnodes (int n) {
LinkedListNode previous=first, current=first, temp = first;
for(int i=0; i<n+1; i++) {
current=current.next;
}
while (current.next!=null) {
previous=previous.next;
current=current.next;
}
temp=previous;
while(temp.next!=null) {
if(temp.next==current) {
System.out.println("Node is "+current.iData);
current=temp;
temp=previous;
}
if (previous==current) {
break;
}
temp=temp.next;
}
}
public void printReverseNnodes (int n) {
LinkedListNode previous=first, current=first, temp = first;
for(int i=0; i<n+1; i++) {
current=current.next;
}
while (current.next!=null) {
previous=previous.next;
current=current.next;
}
temp=previous;
while(temp.next!=null) {
if(temp.next==current) {
System.out.println("Node is "+current.iData);
current=temp;
temp=previous;
}
if (previous==current) {
break;
}
temp=temp.next;
}
}
This solution is independent of number of elements in linked list and has no dependency on value of 'n'
public void printReverseNnodes (int n) {
LinkedListNode previous=first, current=first, temp = first;
for(int i=0; i<n+1; i++) {
current=current.next;
}
while (current.next!=null) {
previous=previous.next;
current=current.next;
}
temp=previous;
while(temp.next!=null) {
if(temp.next==current) {
System.out.println("Node is "+current.iData);
current=temp;
temp=previous;
}
if (previous==current) {
break;
}
temp=temp.next;
}
}
This solution is independent of number of elements in linked list and has no dependency on value of 'n'
public void printReverseNnodes (int n) {
LinkedListNode previous=first, current=first, temp = first;
for(int i=0; i<n+1; i++) {
current=current.next;
}
while (current.next!=null) {
previous=previous.next;
current=current.next;
}
temp=previous;
while(temp.next!=null) {
if(temp.next==current) {
System.out.println("Node is "+current.iData);
current=temp;
temp=previous;
}
if (previous==current) {
break;
}
temp=temp.next;
}
}
This solution is independent of number of elements in linked list and has no dependency on value of 'n'
public void printReverseNnodes (int n) {
LinkedListNode previous=first, current=first, temp = first;
for(int i=0; i<n+1; i++) {
current=current.next;
}
while (current.next!=null) {
previous=previous.next;
current=current.next;
}
temp=previous;
while(temp.next!=null) {
if(temp.next==current) {
System.out.println("Node is "+current.iData);
current=temp;
temp=previous;
}
if (previous==current) {
break;
}
temp=temp.next;
}
}
This solution is independent of number of elements in linked list and has no dependency on value of 'n'
public void printReverseNnodes (int n) {
LinkedListNode previous=first, current=first, temp = first;
for(int i=0; i<n+1; i++) {
current=current.next;
}
while (current.next!=null) {
previous=previous.next;
current=current.next;
}
temp=previous;
while(temp.next!=null) {
if(temp.next==current) {
System.out.println("Node is "+current.iData);
current=temp;
temp=previous;
}
if (previous==current) {
break;
}
temp=temp.next;
}
}
solution in ruby
def nodes_from_tail n
n_list = LinkedList.new(1)
2.upto(10) { |x| n_list.add(x) }
reverse_list = n_list.list_to_reverse_arr
new_list = LinkedList.new(reverse_list[0])
1.upto(n-1) { |i| new_list.add(reverse_list[i]) }
new_list.display
end
Where I have the following method added to my custom LinkedList class:
def list_to_reverse_arr
current = @head
full_list = []
while current.next_node != nil
full_list += [current.value.to_s]
current = current.next_node
end
full_list += [current.value.to_s]
full_list.reverse
end
Corrected a simple issue to print the tail list in reverse order.
- Prasad April 13, 2013int counter=0;
Public void printList(Node root, int k)
{
If(root!=null)
{
printList(root.next);
counter++;
if(counter<=k)
Print root.data;
}
}
The above algorithm takes O(n) time.