santidltp
BAN USER- 1of 1 vote
AnswersGiven a Tree:
A /\ B C /\ /\ D E F G
Write a function that prints:
- santidltp in United States
A
BC
DEFG| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
I really like this question, because it proves whether you understand this basic data structure or not. Here is my implementation; (i)my stack is going to be a array of numbers. (ii) push(int) will store the number in to the array and increment a position of the array and puts the number into a hashmap. (iii) pop() will decrement the position of the array and decrements the number in the hashmap. (iv)mode() takes the max occurrences of the given number and returns it.
import java.util.*;
public class stack{
private int [] iStack;
private int currentPos = -1;
private HashMap <Integer,Integer> map = new HashMap<Integer,Integer>();
/*
* Constructor: initializes the size
* of the stack.
*/
public stack(int size){
iStack= new int[size];
}
/*
* push: pushes a number into the stack
*/
public void push(int number){
if((++currentPos) < iStack.length){
iStack[currentPos] = number;
//put in a hashmap for mode.
if(map.get(iStack[currentPos])!= null)
map.put(iStack[currentPos], map.get(iStack[currentPos])+1);
else
map.put(iStack[currentPos],1);
}
else
System.out.println("There's no space in the stack");
}
/*
* pop: takes the last number placed
* in the stack.
*/
public int pop(){
if(currentPos > -1){
if((map.get(iStack[currentPos]) != null) || (map.get(iStack[currentPos]) > 0))
map.put(iStack[currentPos],map.get(iStack[currentPos]-1));
return iStack[currentPos--];
}
else
return -1;
}
/*
* peek: returnst the last number
* placed in the stack.
*/
public int peek(){
if(currentPos > -1)
return iStack[currentPos];
else
return -1;
}
/*
* mode: returns the most repeated number,
* if two numbers have the max value, it
* it retursn the the latest number being
* pushed to the stack.
*/
public int mode(){
int max=0,val=0,index=0;
if(currentPos > 0)
for(int i=0;i<=currentPos; i++){
val=map.get(iStack[i]);
if(val>max){
max=val;
index =i;
}
}
return iStack[index];
}
public static void main(String [] args){
stack newStack = new stack(10);
newStack.push(1);
newStack.push(5);
newStack.push(8);
newStack.push(3);
newStack.push(2);
newStack.push(3);
newStack.push(1);
// System.out.println(newStack.peek());
// newStack.push(2);
// System.out.println(newStack.pop());
System.out.println(newStack.mode());
}
}
If you are coding in Java, you can implement a HashMap. Using these functions, can make your life a lot easier, in my opinion.
public static int SecondMostRepeated(int[] array){
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int value = 0,secondMax=0,max=0,number=0,current=0;
//populate hashMap
for(int i=0;i<array.length; i++){
//if the hashmap doesn't contain
//the item, add one instance of it.
if(map.get(array[i]) == null)
map.put(array[i], 1);
//otherwise, increment its value.
else{
value = map.get(array[i]);
map.put(array[i], ++value);
}
}
for(int i=0; i<array.length; i++){
current=map.get(array[i]);
//keep a track on the maximum number.
if(current > max){
secondMax=max;
max = current;
}else {//keep a track on the second-Maximum
if(current>=secondMax){
secondMax=current;
number = array[i];//what we are looking for.
}
}
}
return number;
}
you are right, I guess I wan't as careful as I thought. My implementation works using extra storage.
- santidltp April 14, 2015