Google Interview Question
InternsCountry: United States
Interview Type: Phone Interview
if(head != NULL){
while( count < k ){
must change to
if(ref_ptr != NULL){
while( count < k ){
to deal with the pathological case you are checking. Just a way to avoid that extra if block.
if
k == 1
, then
ref_ptr
should not be moved at the preparing stage!
Thus count should starts from 1 rather than 0.
Here's a simpler code
function item findElemFromTail(LinkedList list, int k) {
item* p = list->head;
item* elem = NULL;
int i = 0;
while(p!=null) {
if(i == k) {
elem = p;
}
if (item!=null) item = item->next;
p = p->next;
i++;
}
return elem;
}
This is O(N) and we are only scanning the linked list once.
#include<iostream>
#include<list>
int findkthreverseelement(const std::list<int>& elements, int k) {
std::list<int>::const_iterator front = elements.begin();
std::list<int>::const_iterator back = front;
for (int i = 1; i <= k; i++) ++front;
while (front != elements.end()) {
++front;
++back;
}
return *back;
}
int main() {
std::list<int> elements;
int input=0;
int k;
std::cout << "Enter k\n";
std::cin >> k;
std::cout << "Enter elements\n";
while (std::cin >> input) {
elements.push_back(input);
}
for(std::list<int>::iterator it = elements.begin(); it != elements.end(); ++it) {
std::cout << *it << " ";
}
int result = findkthreverseelement(elements, k);
std::cout << "answer is " << result << "\n";
return 0;
}
With Size given problem will be too simple to solve so i will try solving without the Size
1.Have two pointers both of them pointing to head at first assume P1 and P2
2.move p2 to k times in the list(assuming the question is kth to last )
(for int i=0;i<k-1;i++){
p2=p2.next;
}
4.now P2 will be k node in to the list and P1 still pointing to the head
5.now move P1 and p2 on the same speed iterating over the list
while p2.next !=null// that means list's end
{
p1=p1.next;
p2=p2.next;
}
return p1
An answer below this question uses two pointers which has the distance k. Move them simultaneously. When the first pointer catch the last one, the second pointer reach to kth element from the tail.
There is a trick, this method have to move 2 * length in the whole. So there is an more efficient method.
Just as the answer mentioned above, we have:
first pointer
second pointer
second pointer points to the head, while first pointer points to kth element in the linked list
You can simply move first pointer k(sometimes less than k times, because maybe list has not enough elements to traverse) times every single loop, remember the times to T, after every k times movement, check whether first pointer reach the end. If not, let second pointer point to the position which first pointer points when this loop begins, and go on. If so, move second pointer T times and this is the kth element from the tail in the linked list.
Now i just use k to be the number of moves for first pointer every single loop. When k is much smaller than the linked list length, this method seems not more efficient than traditional one. So how to makes this method most efficient? With my glance, I think we could choose the number of moves every single loop dynamically. The best number is related to k and length of linked list.
class Node(object):
def __init__(self, value, node):
self.value = value
self.node = node
root = Node(0,None)
previousNode = root
for i in range(1, 50):
node = Node(i, None)
previousNode.node = node
previousNode = node
node = root
for i in range(50):
print node.value
node = node.node
def kthElementFromTail(k):
p = root
kthFromTail = 0
q = p;
for i in range(k):
if(q.node != None):
q = q.node
else:
print "k is out of range of linkedList"
return
while q.node != None:
temp = q
position = 0
for i in range(0,k):
if(q.node != None):
position += 1
q = q.node
else:
break
if(position < k):
for i in range(position):
p = p.node
return p
else:
kthFromTail += position
p = temp
return None
k = kthElementFromTail(3)
print k.value
function item findElemFromTail(LinkedList list, int k) {
item* p = list->head;
item* elem = NULL;
int k = ;
int i = 0;
while(p!=null) {
if(i == k) {
elem = p;
}
if (item!=null) item = item->next;
p = p->next;
i++;
}
return elem;
}
This is O(N) and we are only scanning the linked list once.
public Node<E> findKthElementFromEnd(int k) {
if (k < 0 || this.size - k < 0) {
System.out.println("Enter Correct value of K");
return null;
}
if (head == null || head.next == null)
return head;
Node<E> fast = head;
Node<E> slow = head;
int i = 0;
while (i < k) {
fast = fast.next;
i++;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
In java
--same as C++ program above. Please include the check for K > size of the list.
1.) move the fast pointer to kth position
2.) move the fast and slow pointers by one
3.) exit when fast reached the end
4.) print the value of the slow pointer
public void findKthElement(int k)
{
if( head == null ){
return;
}
//add condition to handle k >= length of list
Node<AnyType> fast = head;
Node<AnyType> slow = head;
while(k > 0){
fast = fast.next;
k--;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
System.out.println("kth element value is: " + slow.data );
}
public class KthElementFromTail {
public static void main(String args[]){
SLLImpl list = new SLLImpl();
list.addToTail(1);
list.addToTail(2);
list.addToTail(3);
list.addToTail(4);
list.addToTail(5);
list.addToTail(6);
int element = getKthElementFromTail(2, list);
System.out.println(element);
}
private static int getKthElementFromTail(int index, SLLImpl list) {
int position = 1;
SLLNode node = null;
for(node = list.head; position != list.size - index; node=node.next){
position++;
}
return node.data;
}
}
public class KthElementFromTail {
public static void main(String args[]){
SLLImpl list = new SLLImpl();
list.addToTail(1);
list.addToTail(2);
list.addToTail(3);
list.addToTail(4);
list.addToTail(5);
list.addToTail(6);
int element = getKthElementFromTail(2, list);
System.out.println(element);
}
private static int getKthElementFromTail(int index, SLLImpl list) {
int position = 1;
SLLNode node = null;
for(node = list.head; position != list.size - index; node=node.next){
position++;
}
return node.data;
}
}
If you know the length of the given linked list, just subtract from the length and do one traversal to get it from the "front" of the list:
public static Node getKFromTail(int k) {
int from_zero = length-k-1;
Node curr = top;
for(int i = 0; i<from_zero; i++) {
curr = curr.next;
}
return curr;
}
Can be done in O(n) time. Travel the list in O(n) time. This will give you the length of the list - lets say 'n'.
SUbtract k from the length and 1 in it. (n-k)+1
Once again travel from beginning and n-k+1 is the kth element from the tail.
import java.util.Scanner;
public class LinkedInsert {
static Node[] newNode;
static int numberOfNode;
public static void main(String args[]) {
Node head = null;
System.out.print("Enter Number of Node:");
numberOfNode = new Scanner(System.in).nextInt();
newNode = new Node[numberOfNode];
for (int i = 0; i < numberOfNode; i++) {
int d = new Scanner(System.in).nextInt();
newNode[i] = new Node(d);
if (i == 0) {
head = newNode[i];
}
else {
head.nextNode = newNode[i];
head = newNode[i];
}
}
System.out.print("Enter Find Data:");
int find = new Scanner(System.in).nextInt();
getSpecificElementFromTailOfStack(find);
}
private static void getSpecificElementFromTailOfStack(int find) {
// TODO Auto-generated method stub
int f = numberOfNode - find;
System.out.print("Data:" + newNode[f].data);
}
}
#include<iostream>
using namespace std;
struct node{
int data;
node *next;
};
int my_func(node *new_list,int m)
{
node *bptr;int count=0,count1=0,count2=0;
bptr=new_list;
while((bptr->next)!=NULL)
{
bptr=bptr->next;
count1++;
}
count2=count1-m+1;
bptr=new_list;
while((count2>0))
{
bptr=bptr->next;
count2--;
}
int h=bptr->data;
return h;
}
int main()
{
node *list,*nptr,*tptr;
int item,n,i;
list=NULL;
cout<<"PLEASE.......Type how many nodes that you want ";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"Type your "<<i<<" node item ";
cin>>item;
nptr=new(node);
nptr->data=item;
nptr->next=NULL;
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
tptr=list;
for(i=1;i<=n;i++)
{
cout<<endl;
cout<<tptr->data<<" ";
tptr=tptr->next;
}
cout<<endl;
cout<<"Enter your node number from the tail in a linked list ";
cin>>item;
int data_new=my_func(list,item);
cout<<" \n\n"<<item<<" element from the tail in a linked list= "<<data_new<<endl<<endl;
return 0;
}
void printKthElementReverse(int nPos)
{
if(pHead == NULL)
{
std::cout<<"No Element Found at "<<nPos<<" position";
return;
}
int count = 0;
stList* pCurr = pHead;
stList* pKthElem = pHead;
stList* pPrev = NULL;
while(count < nPos)
{
pPrev = pKthElem;
if(NULL == pKthElem)
break;
pKthElem = pKthElem->pNList;
count++;
}
if(pPrev == NULL || count < nPos)
{
std::cout<<"No Element Found at "<<nPos<<" position";
return;
}
stList* pCurPrev = NULL;
while(pPrev != NULL)
{
pCurPrev = pCurr;
pPrev = pPrev->pNList;
pCurr = pCurr->pNList;
}
std::cout<<nPos<<" Element from Reverse is "<<pCurPrev->data;
}
Use two pointers both pointing to the head of the linked list. Move one of the pointers k ahead. Now move both of the pointers one node ahead at a time. When the first one reaches the end the second one would be k nodes behind it.
- Expressions April 05, 2013