uafshahid
BAN USERThe following can be a solution for the problem (Write your base cases first):
1. Declare a HashSet and a LinkedHashSet.
a. The purpose of the HashSet is to store characters in the String
b. The purpose of the LinkedHashSet is to maintain the unique characters in the String
and also maintain the order of insertion of unique characters
2. Write a loop starting from zero to the length of the String.
3. Check in the loop if the character is already in the HashSet, remove it from LinkedHashSet; otherwise, add the character to both HashSet and LinkedHashSet.
4. return call to LinkedHashSet iterator method and then next method in a chain.
Note: This algorithm will guarantee to return first unique character of the String.
Here is the Code:
import java.util.HashSet;
import java.util.LinkedHashSet;
public class NonRepeatingCharacter {
public static Character getNonRepeatingCharacter(String testString) throws Exception{
if(testString == null) throw new NullPointerException(); //First ask the Interviewer what to return for base cases
if(testString.isEmpty()) throw new Exception("String is empty"); //First ask the Interviewer what to return for base cases
if(testString.length() == 1) return new Character(testString.charAt(0)); //This is totally valid output, assuming single character as unique character in the String
HashSet<Character> characterSet = new HashSet<>();
LinkedHashSet<Character> uniqueCharacter = new LinkedHashSet<>();
for(int i = 0; i < testString.length(); i++)
{
Character charToAdd = new Character(testString.charAt(i));
if(characterSet.contains(charToAdd)){
uniqueCharacter.remove(charToAdd);
}
else{
characterSet.add(charToAdd);
uniqueCharacter.add(charToAdd);
}
}
return uniqueCharacter.iterator().next();
}
public static void main(String args[]) throws Exception{
String testString = "abcdeadcb";
System.out.println("Expected e, Actual "+ getNonRepeatingCharacter(testString));
testString = "abcdneadcb";
System.out.println("Expected n, Actual "+ getNonRepeatingCharacter(testString));
}
}
import java.lang.reflect.Array;
public class ConstantTimeStack<T extends Comparable<T>> {
int length = 10;
T[] stack;
T[] minStack;
int size = 0;
int minSize = 0;
public ConstantTimeStack(Class<T> t, int sizeOfStack)
{
length = sizeOfStack;
stack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
minStack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
}
public void AddElement(T item) throws Exception
{
if(!isStackOverflow(size)){
stack[size++] = item;
if(isEmpty(minSize) || item.compareTo(currentElement()) < 0){
minStack[minSize++] = item;
}
}
else{
throw new Exception("StackOverflow");
}
}
public T GetMin(){
return minStack[(minSize-1)];
}
public boolean RemoveLastElement() throws Exception{
int previousSize = size;
GetLastElement();
return (previousSize -1) == size;
}
private T currentElement(){
return minStack[(minSize-1)];
}
public T GetLastElement()throws Exception{
if(!isEmpty(size)){
T returnValue = stack[--size];
if(isStackOverflow(minSize) || returnValue == currentElement()){
--minSize;
}
return returnValue;
}
else{
throw new Exception("StackUnderflow");
}
}
public boolean isEmpty(int size)
{
return size == 0;
}
private boolean isStackOverflow(int size)
{
return size == length;
}
public static void main(String args[]) throws Exception
{
ConstantTimeStack<Item> minStack = new ConstantTimeStack<>(Item.class, 10);
minStack.AddElement(new Item("Shahid",20));
minStack.AddElement(new Item("Khalid",10));
minStack.AddElement(new Item("Aslam",34));
minStack.AddElement(new Item("raheel",2));
minStack.AddElement(new Item("Bashir",44));
minStack.AddElement(new Item("Insan",1));
minStack.AddElement(new Item("rashid",100));
System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
System.out.println(minStack.RemoveLastElement());
System.out.println(minStack.RemoveLastElement());
System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
System.out.println(minStack.GetLastElement().id);
System.out.println(minStack.GetLastElement().id);
System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
}
}
class Item implements Comparable<Item> {
String name;
int id;
public Item(String name, int id){
this.name = name;
this.id = id;
}
@Override
public int compareTo(Item o) {
if(o == null) throw new NullPointerException("Second Object is null");
if(this.id < o.id) return -1;
else if(this.id > o.id) return 1;
return 0;
}
}
import java.util.Stack;
public class ConstantTimeCustomStack<E extends Comparable<E>>{
/**
* @param args
*/
Stack<E> regularStack = new Stack<>();
Stack<E> minStack = new Stack<>();
public ConstantTimeCustomStack(){
}
public void AddElement(E item) throws Exception
{
regularStack.push(item);
if(minStack.isEmpty() || minStack.peek().compareTo(item) > 0){
minStack.push(item);
}
}
public E GetMin(){
return minStack.peek();
}
public E RemoveLastElement(){
E removedElement = regularStack.pop();
if(!minStack.isEmpty() && removedElement.compareTo(GetMin())==0)
{
minStack.pop();
}
return removedElement;
}
public E GetLastElement()throws Exception{
return regularStack.peek();
}
public static void main(String[] args) throws Exception {
ConstantTimeCustomStack<Item> minStack = new ConstantTimeCustomStack<>();
minStack.AddElement(new Item("Shahid",20));
minStack.AddElement(new Item("Khalid",10));
minStack.AddElement(new Item("Aslam",34));
minStack.AddElement(new Item("raheel",2));
minStack.AddElement(new Item("Bashir",44));
minStack.AddElement(new Item("Insan",1));
minStack.AddElement(new Item("rashid",100));
System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
System.out.println(minStack.GetLastElement().id);
System.out.println(minStack.GetLastElement().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
}
}
class Item implements Comparable<Item> {
String name;
int id;
public Item(String name, int id){
this.name = name;
this.id = id;
}
@Override
public int compareTo(Item o) {
if(o == null) throw new NullPointerException("Second Object is null");
if(this.id < o.id) return -1;
else if(this.id > o.id) return 1;
return 0;
}
}
import java.util.Stack;
public class ConstantTimeCustomStack<E extends Comparable<E>>{
/**
* @param args
*/
Stack<E> regularStack = new Stack<>();
Stack<E> minStack = new Stack<>();
public ConstantTimeCustomStack(){
}
public void AddElement(E item) throws Exception
{
regularStack.push(item);
if(minStack.isEmpty() || minStack.peek().compareTo(item) > 0){
minStack.push(item);
}
}
public E GetMin(){
return minStack.peek();
}
public E RemoveLastElement(){
E removedElement = regularStack.pop();
if(!minStack.isEmpty() && removedElement.compareTo(GetMin())==0)
{
minStack.pop();
}
return removedElement;
}
public E GetLastElement()throws Exception{
return regularStack.peek();
}
public static void main(String[] args) throws Exception {
ConstantTimeCustomStack<Item> minStack = new ConstantTimeCustomStack<>();
minStack.AddElement(new Item("Shahid",20));
minStack.AddElement(new Item("Khalid",10));
minStack.AddElement(new Item("Aslam",34));
minStack.AddElement(new Item("raheel",2));
minStack.AddElement(new Item("Bashir",44));
minStack.AddElement(new Item("Insan",1));
minStack.AddElement(new Item("rashid",100));
System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
System.out.println(minStack.GetLastElement().id);
System.out.println(minStack.GetLastElement().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println(minStack.RemoveLastElement().id);
System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
}
}
class Item implements Comparable<Item> {
String name;
int id;
public Item(String name, int id){
this.name = name;
this.id = id;
}
@Override
public int compareTo(Item o) {
if(o == null) throw new NullPointerException("Second Object is null");
if(this.id < o.id) return -1;
else if(this.id > o.id) return 1;
return 0;
}
}
//-------------OR ---------------
import java.lang.reflect.Array;
public class ConstantTimeStack<T extends Comparable<T>> {
int length = 10;
T[] stack;
T[] minStack;
int size = 0;
int minSize = 0;
public ConstantTimeStack(Class<T> t, int sizeOfStack)
{
length = sizeOfStack;
stack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
minStack = (T[]) Array.newInstance(t, length);//(T[])new Object[length];
}
public void AddElement(T item) throws Exception
{
if(!isStackOverflow(size)){
stack[size++] = item;
if(isEmpty(minSize) || item.compareTo(currentElement()) < 0){
minStack[minSize++] = item;
}
}
else{
throw new Exception("StackOverflow");
}
}
public T GetMin(){
return minStack[(minSize-1)];
}
public boolean RemoveLastElement() throws Exception{
int previousSize = size;
GetLastElement();
return (previousSize -1) == size;
}
private T currentElement(){
return minStack[(minSize-1)];
}
public T GetLastElement()throws Exception{
if(!isEmpty(size)){
T returnValue = stack[--size];
if(isStackOverflow(minSize) || returnValue == currentElement()){
--minSize;
}
return returnValue;
}
else{
throw new Exception("StackUnderflow");
}
}
public boolean isEmpty(int size)
{
return size == 0;
}
private boolean isStackOverflow(int size)
{
return size == length;
}
public static void main(String args[]) throws Exception
{
ConstantTimeStack<Item> minStack = new ConstantTimeStack<>(Item.class, 10);
minStack.AddElement(new Item("Shahid",20));
minStack.AddElement(new Item("Khalid",10));
minStack.AddElement(new Item("Aslam",34));
minStack.AddElement(new Item("raheel",2));
minStack.AddElement(new Item("Bashir",44));
minStack.AddElement(new Item("Insan",1));
minStack.AddElement(new Item("rashid",100));
System.out.println("Expected 1, Actual "+ minStack.GetMin().id);
System.out.println(minStack.RemoveLastElement());
System.out.println(minStack.RemoveLastElement());
System.out.println("Expected 2, Actual "+ minStack.GetMin().id);
System.out.println(minStack.GetLastElement().id);
System.out.println(minStack.GetLastElement().id);
System.out.println("Expected 10, Actual "+ minStack.GetMin().id);
}
}
class Item implements Comparable<Item> {
String name;
int id;
public Item(String name, int id){
this.name = name;
this.id = id;
}
@Override
public int compareTo(Item o) {
if(o == null) throw new NullPointerException("Second Object is null");
if(this.id < o.id) return -1;
else if(this.id > o.id) return 1;
return 0;
}
}
If all the threads are used, Rejection policies are as follow:
- In the default ThreadPoolExecutor.AbortPolicy, the handler throws a runtime RejectedExecutionException upon rejection.
- In ThreadPoolExecutor.DiscardPolicy, a task that cannot be executed is simply dropped.
- uafshahid June 08, 2017