Apple Interview Question
Software Engineer in TestsCountry: United States
I think what you mean by second last (n-1) node is where the * is
* n-1 n
_ _ _ _
{
p = ll.head; q == null; i = 0;
while (i < 3 && p != null) {
p = p.next;
}
if (p != null) {
q = ll.head;
}
while (p != null) {
p = p.next;
q = q.next;
}
// q is your answer
}
The same principal applies to the second question. q advances half the distance of p in each loop. If p hits the end of the list before it could double its stride, then q advances half the different between end of list and p
import java.util.ArrayList;
class NodeForGetSecondLastAndHalfNode {
public int data;
public NodeForGetSecondLastAndHalfNode next;
public NodeForGetSecondLastAndHalfNode(int iData) {
data = iData;
}
public void display() {
System.out.print(data + " ==> ");
}
}
class ListForGetSecondLastAndHalfNode {
private NodeForGetSecondLastAndHalfNode first;
public ListForGetSecondLastAndHalfNode() {
first = null;
}
public boolean isEmpty() {
if (first == null) {
return true;
}
return false;
}
public void insertData(int data) {
System.out.println("INSERT: " + data);
NodeForGetSecondLastAndHalfNode newElm = new NodeForGetSecondLastAndHalfNode(data);
newElm.next = first;
first = newElm;
}
public void display() {
System.out.println("DISPLAY");
if (isEmpty()) {
System.out.println("EMPTY");
return;
}
NodeForGetSecondLastAndHalfNode curr = first;
while (curr != null) {
curr.display();
curr = curr.next;
}
System.out.println();
}
public NodeForGetSecondLastAndHalfNode getFirst() {
if (isEmpty()) {
return null;
}
return first;
}
}
class GetSecondLastAndHalfNodeSolution {
public Object getSecondLastNode(ListForGetSecondLastAndHalfNode list) {
list.display();
System.out.print("\t SECOND LAST NODE: ");
NodeForGetSecondLastAndHalfNode slow = list.getFirst();
if (list.isEmpty()) {
return null;
} else if (slow.next == null) {
return null;
}
NodeForGetSecondLastAndHalfNode fast = slow.next;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
System.out.println(slow.data);
return slow;
}
public ArrayList<Integer> getHalfNode(ListForGetSecondLastAndHalfNode list) {
list.display();
NodeForGetSecondLastAndHalfNode slow = list.getFirst();
System.out.print("\t MID NODES: ");
ArrayList<Integer> out = new ArrayList<Integer>();
if (list.isEmpty()) {
return out;
} else if (slow.next == null || slow.next.next == null) {
out.add(slow.data);
} else {
NodeForGetSecondLastAndHalfNode fast = slow.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) {
out.add(slow.data);
out.add(slow.next.data);
} else {
out.add(slow.data);
}
}
return out;
}
public void display(ArrayList<Integer> out) {
for (int i = 0; i < out.size(); i++) {
System.out.print(out.get(i) + " , ");
}
System.out.println();
}
}
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def search(node, target_distance):
if node is None:
return -1, None
distance, target_node = search(node.next, target_distance)
if distance + 1 == target_distance:
target_node = node
return distance + 1, target_node
if __name__ == '__main__':
data = '1234567890'
seed = None
last_node = None
for d in data:
node = ListNode(d)
if seed is None:
seed = node
if last_node is not None:
last_node.next = node
last_node = node
distance, target_node = search(seed, 0)
print target_node.val
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def search(node, target_distance):
if node is None:
return -1, None
distance, target_node = search(node.next, target_distance)
if distance + 1 == target_distance:
target_node = node
return distance + 1, target_node
if __name__ == '__main__':
data = '1234567890'
seed = None
last_node = None
for d in data:
node = ListNode(d)
if seed is None:
seed = node
if last_node is not None:
last_node.next = node
last_node = node
distance, target_node = search(seed, 0)
print target_node.val
public LinkedListNode nthToLastLessComplexity(int n) { //is the value of nth node from last
if(head== null){
return null;
}
LinkedListNode currentNode = head;
int length = 0;
while(currentNode!=null){
currentNode = currentNode.getNext();
length ++;
}
int m = length;
int val = m-n+1;
currentNode = head;
for(int i=1;i<val;i++){
currentNode = currentNode.getNext();
}
return currentNode;
//complexity is O(n)
}
Take two pointers. Point out from start. Move one pointer (say p) with one difference and another one (say q) with two difference. So when p is at n/2, q will be on n-1.
- Shashank September 13, 2014eg. n=10.
initially p=q=1.
now p=2 and q=3.
then p=3 and q=5.
then p=4 and q=7.
then p=5 and q=9.
Our search completes when q has no node to move or null.