Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

You can write a Reverse function of link list on node (default is head). algo:
2) ReverseNumber = Count - 5
3) Move to ReverseNumber and set pointer suppose P1 (O(n-5) ==> O(n))
4) pass P1.next to reverse function (O(5) because only 5 to reverse)
5) P1.Next = Return of reverse function

So: Complexity = O(n)

Code:

``````public SingleNode Reverse(SingleNode head)
{

SingleNode prev = null;

while(curr != null)
{
SingleNode next = curr.Next;
curr.Next = prev;
prev = curr;
curr = next;
}

return prev;
}

static void Main(string[] arg)
{
int count = list.Count;
int ReverseNumber = 5;

SingleNode reverseNode = new SingleNode(null);

if (count <= ReverseNumber)
{
//If count less than 5 then reverse at head
}
else
{
int nodeToTravel = count - ReverseNumber;
// Traverse to n-5 node
for (int i = 0; i < nodeToTravel; i++)
startNode = startNode.Next;
//Reverse last 5
reverseNode = list.Reverse(startNode.Next);

startNode.Next = reverseNode;

// Print all link list data
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````/**
* Created by dheeraj on 12/12/14.
*/

public static class Node {
int value;
Node next;

public Node(int data) {
value = data;
next = null;
}
}

Node root;
int length;

root = null;
length = 0;
}

public void insert(int data) {
root = insertPrivate(root, data);
length++;
}

private Node insertPrivate(Node root, int data) {
if (root == null) {
root = new Node(data);
} else {
root.next = insertPrivate(root.next, data);
}
return root;
}

public void traverse() {
traversePrivate(root);
}

private void traversePrivate(Node root) {
if (root == null) {
return;
} else {
System.out.println(root.value);
traversePrivate(root.next);
}
}

public void reverse() {
root = reversePrivate(root);
}

private Node reversePrivate(Node root) {
Node previous = null;
Node current = root;
Node next = null;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}

public void reverseFromNthNodeFromStart(int n) {
Node temp = root;
for (int x = 1; x <= n-1; x++) {
temp = root.next;
if (temp == null) {
return;
}
}
temp.next = reversePrivate(temp.next);
}

public void reverseFromNthNodeFromEnd(int n){
reverseFromNthNodeFromStart(length-n);
}

}

public static void main(String[] args) {

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

In my solution I keep track of the last N node in a List, then I attach the last node to the N-1th node in the original list and read backwards the nodes on the List containing the last N nodes. Running time O(n) and you don't have to know the length of the list of nodes in advance.

``````import java.util.ArrayList;
import java.util.List;

class Lnode {
int value;
Lnode next;
public Lnode (int value) {
this.value = value;
this.next=null;
}
public Lnode(int value,Lnode next) {
this(value);
this.next = next;
}
public String toString() {
return this.value+" ";
}
}

public class ReverseNthNode {
public static void printLnode(Lnode head) {
System.out.print(" -> ");
}
}
System.out.println();
}
public static Lnode reverseLastN(Lnode head, int n) {
List<Lnode> lasts = new ArrayList<Lnode>();
Lnode prev = null;
while(current!=null) {
if(lasts.size()>=n) {
prev = lasts.remove(0);
}
current=current.next;
}
for(int i=lasts.size()-1;i>0;i--) {
lasts.get(i).next = lasts.get(i-1);
}
if(prev != null) {
lasts.get(0).next=null;
prev.next=lasts.get(lasts.size()-1);
}
else {
lasts.get(0).next=null;
return lasts.get(lasts.size()-1);
}
}
public static void main(String[] args) {
Lnode l7 = new Lnode(7);
Lnode l6 = new Lnode(6,l7);
Lnode l5 = new Lnode(5,l6);
Lnode l4 = new Lnode(4,l5);
Lnode l3 = new Lnode(3,l4);
Lnode l2 = new Lnode(2,l3);
Lnode l1 = new Lnode(1,l2);
printLnode(l1);
printLnode(reverseLastN(l1,5));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private LinkedList reverseLinkListRecursive(LinkedList node){
if(node.getNext()==null){
return node;
}
node.getNext().setNext(node);
node.setNext(null);

}

int count=1;
while(fastPointer.getNext()!=null){
fastPointer=fastPointer.getNext();
if(count>=6){
slowPointer=slowPointer.getNext();
}
count++;
}

}

while(current.getNext()!=null){
System.out.print(current.getData()+"-->");
current=current.getNext();

}
System.out.print(current.getData()+"\n");

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void reverseLastNnodes(int n) throws EmptyListException, InvalidPositionException{

throw new EmptyListException("In reverse N Node : Empty exception.");
}

if(this.size < n){
throw new InvalidPositionException("Node count exception.");
}

int i = 0;
while(i < (n-1)){
fast = fast.getNext();
i++;
}

while(fast.getNext() != null){
if(tem == null && fast.getNext().getNext() == null){
tem = slow;
}
slow = slow.getNext();
fast = fast.getNext();
}

tem.setNext(reverseListNodes(slow,null));
}

/**
* Utility method to reverse last n nodes
*
* @param node
* @param temp
* @return
*/

private ListNode<T> reverseListNodes(ListNode<T> node, ListNode<T> temp){

while(node != null){
ListNode<T> nextNode = null;
nextNode = node.getNext();
node.setNext(temp);
temp = node;
node = nextNode;
}

return temp;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
My code is a code that use recursion. It basically runs to the end of the list, and when it gets there it is starting to reverse the order of the nodes...
the complexity stays O(n) but in my opinion the code is more clear to read (and much shorter) here..
Thanks,

``````package neww;

public static void main(String[] args) {
Node n7 = new Node(7, null);
Node n6 = new Node(6, n7);
Node n5 = new Node(5, n6);
Node n4 = new Node(4, n5);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
int numberOfNodestoReverse = 5;
System.out.println(n1.toString());
reverse(getNthElement(n1 ,numberOfNodestoReverse+1));

System.out.println(n1.toString());
}

public static Node getNthElement(Node head, int n) {

for (; n > 0; n--) {
f_ptr = f_ptr.next;
}

while (f_ptr != null) {
f_ptr = f_ptr.next;
s_ptr = s_ptr.next;
}
System.out.println(s_ptr.toString());

return s_ptr;

}

public static void reverse(Node curr) {
Node oldNext=curr.next;
Node newNext=reverse(curr.next,curr.next.next);
curr.next=newNext;
oldNext.next=null;
}

private static Node reverse(Node pre, Node curr) {
if (curr == null) {
return pre;
}
Node ret=reverse(curr,curr.next);
curr.next=pre;
return ret;
}
}

class Node {
int value;
Node next;

Node(int value, Node next) {
this.value = value;
this.next = next;
}

public String toString() {
String result = value + " ";
if (next != null) {
result += next.toString();
}
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reverseN(int n)
{
if(n>this.count())
return;
Stack<Node> s= new Stack<Node>();
//traverse n nodes to point nth node
for(int i=0;i<n-1;i++)
{
cur=cur.next;
}
while(cur.next!=null)
{
old=prev;
prev=prev.next;
cur=cur.next;
}
while(prev!=null)
{
temp=prev.next;
prev.next=null;
s.push(prev);
prev=temp;
}
while(s.size()>0)
{
old.next=s.pop();
old=old.next;
}
}

public static void main(String[] args) {
LL l = new LL();

l.insert(1); l.insert(2);l.insert(3);
l.insert(4); l.insert(5);l.insert(6);
l.insert(7);
l.display(); System.out.println();
l.reverseN(5);
l.display();

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void reverseN(int n)
{
if(n>this.count())
return;
Stack<Node> s= new Stack<Node>();
//traverse n nodes to point nth node
for(int i=0;i<n-1;i++)
{
cur=cur.next;
}
while(cur.next!=null)
{
old=prev;
prev=prev.next;
cur=cur.next;
}
while(prev!=null)
{
temp=prev.next;
prev.next=null;
s.push(prev);
prev=temp;
}
while(s.size()>0)
{
old.next=s.pop();
old=old.next;
}
}

public static void main(String[] args) {
LL l = new LL();

l.insert(1); l.insert(2);l.insert(3);
l.insert(4); l.insert(5);l.insert(6);
l.insert(7);
l.display(); System.out.println();
l.reverseN(7);
l.display();

}``````

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Rough solution, yes we can do some more optimization but I believe code readability is great

``````class Node
attr_accessor :value, :next_node

def initialize(value, next_node)
@value = value
@next_node = next_node
end

end

def initialize(value)
end

while current.next_node != nil
current = current.next_node
end

current.next_node = Node.new(value, nil)
end

def display
list = []
while current.next_node != nil
list += [current.value.to_s]
current = current.next_node
end

list += [current.value.to_s]
end

list = []
while current.next_node != nil
list += [current.value.to_s]
current = current.next_node
end
list += [current.value.to_s]

length = list.length
return if length < value_to_reverse
counter = 1
(0..(length-1)).each do |value|
rotating_point = (length - 1) - value_to_reverse
if rotating_point and value > rotating_point
counter = counter + 1
else
end
end
end

end

obj.display
obj.display``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my java code. It has a time complexity of O(n).

``````class Nodeq{
Nodeq next;
int data;
Nodeq(int x){
data=x;
}
}
Nodeq root;

public void print(){
Nodeq temp =root;
if(temp==null)
return;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public void reverse(){
Nodeq fast=root,med=root;
Nodeq slow=root;
if(fast==null)
return;
for(int i=0;i<4;i++){
med=fast;
fast=fast.next;
if(fast==null){
System.out.println("Node are less than five");
return;
}
}

while(fast.next!=null){
slow=slow.next;
med=med.next;
fast=fast.next;
//System.out.println("In fast");
}
for(int i=0;i<2;i++){
int temp=slow.data;
slow.data=fast.data;
fast.data=temp;
fast=med;
slow=slow.next;
}

}

public static void main(String[] args) {
// TODO Auto-generated method stub

}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

While almost all the answers are good the objective of such a question cannot be the solution. If I was the interviewer I would like to see how better corner cases are held. Almost all the answers above will fail in some cases.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.