CareerCup

Here is the code for your own ArrayList program.

import java.util.RandomAccess;

public class MyOwnArrayList implements RandomAccess, Cloneable, java.io.Serializable {

    private transient Object[] elementData;  //Making one array to hold data
    private int size;
    protected transient int modCount = 0;  //Counter to find how many times Array is re-sized.
    private static final long serialVersionUID = 1234L;

    public MyOwnArrayList() {  //Making an initial Array of size 10.
        this(10);
    }
    public MyOwnArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = (Object[])new Object[initialCapacity];
    }

    public boolean add(Object obj) {
        validateCapacity(size + 1);  
        elementData[size++] = obj;
        return true;
    }

    public Object get(int index) {
        Object obj=elementData[index];
        return obj;
    }

    public int size() {
        return size;
    }
    public void validateCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1; //Size increases by 1.5 times+1.

            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elementData = (Object[])new Object[newCapacity];            
            System.arraycopy(oldData, 0, elementData, 0, size); //src, srcPos, dest, destPos, length
            //System.arraycopy(src, srcPos, dest, destPos, length);
        }
    }

    public Object remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

        modCount++;
        Object oldValue = elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0) {
            //System.arraycopy(src, srcPos, dest, destPos, length);
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        }
        elementData[--size] = null; // Let gc do its work
        return oldValue;
    }
    
    //Defining iterator method
    public FruitIterator iterator() {
        System.out.println("My overridded iterator method called in Fruit class");
        return new FruitIterator(this);
    }
}

************Mine designed Iterator***********
public class FruitIterator {
    private MyOwnArrayList fruitList;
    private int position;

    public FruitIterator(MyOwnArrayList fruitList) {
        this.fruitList = fruitList;
    }

    public boolean hasNext() {
        if (position < fruitList.size())
            return true;
        else
            return false;
    }

    public Object next() {
        Object aniObj = fruitList.get(position);
        position++;
        return aniObj;
    }
    public void remove() {
        fruitList.remove(position);
    }
}


//Program: MyFruitIteratorExample.java, Execute the below program.
public class MyFruitIteratorExample {
    public static void main(String[] args) {
        
        MyOwnArrayList fruitList = new MyOwnArrayList();
        fruitList.add("Mango");
        fruitList.add("Strawaberry");
        fruitList.add("Papaya");
        fruitList.add("Watermalon");
        
        System.out.println("-----Calling my iterator on my ArrayList-----");
        FruitIterator it=fruitList.iterator();        
        while(it.hasNext()){
            String s=(String)it.next();
            System.out.println("Value: "+s);
        }
        System.out.println("--Fruit List size: "+fruitList.size());
        fruitList.remove(1);
        System.out.println("--After removal, Fruit List size: "+fruitList.size());
    }
}

Let X be the kth node from beginning and Y be the kth node from end. Following are the interesting cases that must be handled.
1) Y is next to X
2) X is next to Y
3) X and Y are same
4) X and Y don’t exist (k is more than number of nodes in linked list)

SOLUTION USING SINGLE LINK LIST

#include<stdio.h>
#include<stdlib.h>
int main()
{
struct node
{
int data;
struct node *next;
}*head;
head=NULL;
int i,num,k,n;
struct node *temp,*temp1,*temp2;
printf("enter the number=");
scanf("%d",&num);
scanf("%d",&k);
for(i=1;i<=num;i++)
{
scanf("%d",&n);
if(head==NULL)
{
head=malloc(sizeof(struct node));
head->data=n;
temp=head;
}
else
{
temp->next=malloc(sizeof(struct node));
temp->next->data=n;
temp=temp->next;
}
}
temp->next=NULL;
temp=head;
i=1;
while(temp!=NULL)
{
if(i==k)
{
temp1=temp;
temp=temp->next;
}
else if(i==num-k-1)
{
temp2=temp;
temp=temp->next;
}
else
{
temp=temp->next;
}
i=i+1;
}
temp=temp1;
int c=temp->data;
temp=temp2;
int d=temp->data;
temp=temp1;
temp->data=d;
temp=temp2;
temp->data=c;
temp=head;
while(temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->next;
}
return 0;
}

The key data structure of the algorithm is the combination of Hash Map and Doubly-Linked List. We initialize a Hash Map in a per-defined size to store pairs, and use Doubly-Linked List to index the pairs in the order of data age.

Here is C++ code for LRU,

#include <iostream>
#include <vector>
#include <hash_map>

using namespace std;
using namespace stdext;

template<class K, class T>
struct LRUCacheEntry
{
K key;
T data;
LRUCacheEntry* prev;
LRUCacheEntry* next;
};

template<class K, class T>
class LRUCache
{
private:
hash_map< K, LRUCacheEntry<K,T>* > _mapping;
vector< LRUCacheEntry<K,T>* > _freeEntries;
LRUCacheEntry<K,T> * head;
LRUCacheEntry<K,T> * tail;
LRUCacheEntry<K,T> * entries;
public:
LRUCache(size_t size){
entries = new LRUCacheEntry<K,T>[size];
for (int i=0; i<size; i++)
_freeEntries.push_back(entries+i);
head = new LRUCacheEntry<K,T>;
tail = new LRUCacheEntry<K,T>;
head->prev = NULL;
head->next = tail;
tail->next = NULL;
tail->prev = head;
}
~LRUCache()
{
delete head;
delete tail;
delete [] entries;
}
void put(K key, T data)
{
LRUCacheEntry<K,T>* node = _mapping[key];
if(node)
{
// refresh the link list
detach(node);
node->data = data;
attach(node);
}
else{
if ( _freeEntries.empty() )
{
node = tail->prev;
detach(node);
_mapping.erase(node->key);
node->data = data;
node->key = key;
attach(node);
}
else{
node = _freeEntries.back();
_freeEntries.pop_back();
node->key = key;
node->data = data;
_mapping[key] = node;
attach(node);
}
}
}

T get(K key)
{
LRUCacheEntry<K,T>* node = _mapping[key];
if(node)
{
detach(node);
attach(node);
return node->data;
}
else return NULL;
}

private:
void detach(LRUCacheEntry<K,T>* node)
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void attach(LRUCacheEntry<K,T>* node)
{
node->next = head->next;
node->prev = head;
head->next = node;
node->next->prev = node;
}
};

package com.rakesh.topcoder;

import java.util.Scanner;

public class PerfectSquareWithAddition {

/**
* @param args
*/
public static void main(String[] args) {

Scanner input = new Scanner(System.in);
System.out.println("Enter a numer..");
int n = input.nextInt();
int finalval = findPerfectSquare(n);
if(finalval == 0) System.out.println( n + " is a Perfect Square " );
else System.out.println(n + " is not a perfect square ");
}

public static int findPerfectSquare(int n){
int a=1;

while(n>0){
n -= a;
a += 2;
}

return n;
}

}

@Anonymous: small correction....... your code doesn't work for "1020". or any input that can have 10/20.

Here is the working and modified code.....


package com.rakesh.topcoder;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class GenAlphabetCodes {

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

Scanner input = new Scanner(System.in);
System.out
.println("Please enter any length number but combination of 1 to 26 ....... ");
String val = input.next();

System.out.println("All possible Alphabet codes for the give Number: "
+ val);
for (String string : decode(val)) {
System.out.println(string);
}

}

public static Set<String> decode(String in) {
char curChar = 'a';
Map<Integer, Character> numberToChar = new HashMap<Integer, Character>();
for (int i = 1; i <= 26; i++) {
numberToChar.put(i, curChar);
curChar++;
}
return decodeHelper(numberToChar, in, 0, new ArrayList<Character>());
}

private static Set<String> decodeHelper(
Map<Integer, Character> numberToChar, String in, int charAt,
ArrayList<Character> arrayList) {
Set<String> result = new HashSet<String>();
if (charAt >= in.length()) {
String str = "";
for (char c : arrayList) {
str += c;
}
result.add(str);
return result;
} else {
int charCode = Integer.valueOf(in.charAt(charAt) + "");
if (charCode == 0) {
int precCharCode = Integer.valueOf(in.charAt(charAt - 1) + "");
if (precCharCode == 1)
charCode = 10;
if (precCharCode == 2)
charCode = 20;
}
char curChar = numberToChar.get(charCode);
arrayList.add(curChar);
result.addAll(decodeHelper(numberToChar, in, charAt + 1, arrayList));
arrayList.remove(arrayList.size() - 1);
if (in.length() > charAt + 1) {
charCode = Integer.valueOf(in.substring(charAt, charAt + 2));
if (charCode <= 26) {
curChar = numberToChar.get(charCode);
arrayList.add(curChar);
result.addAll(decodeHelper(numberToChar, in, charAt + 2,
arrayList));
arrayList.remove(arrayList.size() - 1);
}
}
}
return result;
}
}

Output:
Please enter any digit number but combination of 1 to 26 .......
2010
All possible Alphabet codes for the give Number: 2010
taj
baj
btj
tj
btaj

@volodymyr.zubariev.... your code is working only for static array. not for dynamic array.
can you please try your code with File reading? take 4,5 test cases in file as input.txt with above sample input and write result in output.txt.

what is the time complexity ? can you please write algorithm or code in java?

there is no start and end point...