Salesforce Interview Question
InternsTeam: Infrastructure
Country: United States
Interview Type: Phone Interview
public class SortedCircularList
{
//sentinel node.
private final Node head;
public SortedCircularList()
{
head = new Node(null);
head.next = head;
}
public static void main(String ...args)
{
SortedCircularList list = new SortedCircularList();
list.add(new Node(4));
list.add(new Node(10));
list.add(new Node(14));
list.print();
//Adding a node in between.
list.add(new Node(0));
list.print();
list.add(new Node(11));
list.print();
}
public void add(Node n)
{
if(head.next==head)
{
head.next = n;
n.next = head;
return;
}
//find the right pos.
Node prev = head.next;
Node cur = head.next.next;
while(cur!=head && cur.data<=n.data)
{
prev = cur;
cur = cur.next;
}
n.next = prev.next;
prev.next = n;
if(n.data<prev.data)
{
int temp = n.data;
n.data = prev.data;
prev.data = temp;
}
}
public void print()
{
Node n = head.next;
while(n!=head)
{
System.out.println(n.data);
n = n.next;
}
System.out.println("******");
}
static final class Node
{
private Node next;
private Integer data;
Node(Integer data)
{
this.data = data;
}
}
}
public class SortedCircularList
{
//sentinel node.
private final Node head;
public SortedCircularList()
{
head = new Node(null);
head.next = head;
}
public static void main(String ...args)
{
SortedCircularList list = new SortedCircularList();
list.add(new Node(4));
list.add(new Node(10));
list.add(new Node(14));
list.print();
//Adding a node in between.
list.add(new Node(0));
list.print();
list.add(new Node(11));
list.print();
}
public void add(Node n)
{
if(head.next==head)
{
head.next = n;
n.next = head;
return;
}
//find the right pos.
Node prev = head.next;
Node cur = head.next.next;
while(cur!=head && cur.data<=n.data)
{
prev = cur;
cur = cur.next;
}
n.next = prev.next;
prev.next = n;
if(n.data<prev.data)
{
int temp = n.data;
n.data = prev.data;
prev.data = temp;
}
}
public void print()
{
Node n = head.next;
while(n!=head)
{
System.out.println(n.data);
n = n.next;
}
System.out.println("******");
}
static final class Node
{
private Node next;
private Integer data;
Node(Integer data)
{
this.data = data;
}
}
}
public class InsertIntoSortedCircularLL {
public static void main(String args[]){
Node head = Node.createLinkedList();
Node curr =head;
while(curr.next != null)
curr=curr.next;
curr.next=head;
Scanner scan = new Scanner(System.in);
System.out.print("Enter element to insert : ");
int ele = scan.nextInt();
Node n = new Node(ele);
if(ele<=head.data){
n.next=head;
curr.next=n;
}
else{
curr=head;
while(curr.next.data<ele && curr.next!=head)
curr=curr.next;
n.next=curr.next;
curr.next=n;
}
curr=head.next;
System.out.print(head.data);
while(curr!=head){
System.out.print(curr.data);
curr=curr.next;
}
}
}
The idea is to just find the right position to insert by keeping two pointers and then either insert or swap values as needed
- sin November 08, 2016