Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
Simply extend LinkedHashMap class and in the constructor set the parameter 'accessorder' = true.Override the method removeEldestEntry() and you are done.
LinkedHashMap manages the data using a hashtable and doubly-linked list. Whenever a hashtable key is accessed or inserted or modified, value is moved to the tail of the linkedlist. In that way, the least recently used element is always present at the head of the linkedlist.
import java.util.*;
public class LROM
{
public static void main( String[] args )
{
LinkedList<String> ll = new LinkedList<String>();
ll.add( "M1" );
ll.add( "M2" );
ll.add( "M4" );
ll.add( "M3" );
int k = 0;
String lrom = ll.get( k++ );
for( int i = 1; i < ll.size(); i++ )
{
for( int j = i; j < ll.size(); j++ )
{
if( lrom.equals( ll.get( j ) ) )
{
lrom = ll.get( k++ );
}
}
}
System.out.println(lrom);
}
}
import java.util.ArrayList;
public class Tester {
public static void main(String[] args) {
String[] msg = {"m3","m2","m1","m3","m1"};
ArrayList<String> msgOccur = new ArrayList<>();
for (String string : msg) {
if(msgOccur.indexOf(string) < 0){
msgOccur.add(string);
}
else{
msgOccur.remove(string);
msgOccur.add(string);
}
}
System.out.println(msgOccur.get(0));
}
}
import java.util.ArrayList;
public class Tester {
public static void main(String[] args) {
String[] msg = {"m3","m2","m1","m3","m1"};
ArrayList<String> msgOccur = new ArrayList<>();
for (String string : msg) {
if(msgOccur.indexOf(string) < 0){
msgOccur.add(string);
}
else{
msgOccur.remove(string);
msgOccur.add(string);
}
}
System.out.println(msgOccur.get(0));
}
}
just put the stuff in list and while putting the stuff in list check it element is already there.if yes.then remove it and add same element and when you are done with your inputstream,you are left with least recent as first entry(oth index) in list.list.getIndex(0)
import java.util.ArrayList;
public class LeastRecentOccuredMessages {
public static void main(String[] args) {
// TODO Auto-generated method stub
String message = "m";
ArrayList<String> arrayList = new ArrayList<>();
java.util.Random random = new java.util.Random();
for (int i = 1; i < 20; i++) {
int k = random.nextInt(5);
String temp = message + k;
if (arrayList.contains(temp)) {
arrayList.remove(temp);
arrayList.add(temp);
}
else
{
arrayList.add(temp);
}
}
System.out.println("least recent message is"+">>>"+arrayList.get(0));
}
}
Insert : O(log n)
getMin : O(1)
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
class mNode{
public:
int t;
string m;
mNode(){};
mNode(int t, string m){
this->t = t;
this->m = m;
}
};
class messageMinHeap{
public:
mNode* harr;
int capacity;
int heap_size;
map<string, int> hmap;
messageMinHeap(int cap){
heap_size = 0;
capacity = cap;
harr = new mNode[cap];
}
int parent(int i){
return (i-1)/2;
}
int left(int i){
return 2*i + 1;
}
int right(int i){
return 2*i + 2;
}
void minHeapify(int i){
int small = i;
int l = left(i);
int r = right(i);
if(l < heap_size && harr[l].t < harr[i].t){
small = l;
}
if(r < heap_size && harr[r].t < harr[small].t){
small = r;
}
if(i != small){
swap(i, small);
minHeapify(small);
}
}
string getMin(){
if(heap_size > 0){
return harr[0].m;
}
else{
return "No message recieved so far.";
}
}
void newMessage(string m, int t){
if(hmap.find(m) == hmap.end()){
insertMessage(m, t);
}
else{
updateMessageTime(m, t);
}
}
void insertMessage(string m, int t){
if(heap_size >= capacity){
cout << "Insert ERROR !!! Heap capacity full." << endl;
return;
}
heap_size++;
int i = heap_size -1;
harr[i] = mNode(t, m);
hmap[m] = i;
while(i != 0 && harr[parent(i)].t > harr[i].t){
swap(parent(i), i);
i = parent(i);
}
}
void updateMessageTime(string m, int t){
int i = hmap[m];
harr[i].t = t;
minHeapify(i);
}
void swap(int i, int j){
mNode temp = harr[i];
hmap[harr[i].m] = j;
hmap[harr[j].m] = i;
harr[i] = harr[j];
harr[j] = temp;
}
};
int main()
{
messageMinHeap mheap(100);
mheap.newMessage("m1", 1);
mheap.newMessage("m2", 2);
mheap.newMessage("m1", 3);
mheap.newMessage("m3", 4);
cout << mheap.getMin() << endl;
}
package LeastCommonRecent;
import java.util.HashMap;
import java.util.LinkedList;
public class LeastCommonRecentMessage {
private HashMap<String,Integer> messageCount = new HashMap<String,Integer>();
private LinkedList<String> messages = new LinkedList<String>();
public static void main(String[] args) {
LeastCommonRecentMessage lrm = new LeastCommonRecentMessage();
lrm.add("M2");
lrm.add("M1");
System.out.println(lrm.leastCommonRecentMessage());
LeastCommonRecentMessage lrm1 = new LeastCommonRecentMessage();
lrm1.add("M3");
lrm1.add("M1");
lrm1.add("M2");
lrm1.add("M1");
System.out.println(lrm1.leastCommonRecentMessage());
}
public void add(String message){
messages.add(message);
if(messageCount.containsKey(message)){
messageCount.put(message, messageCount.get(message)+1);
}else{
messageCount.put(message, 1);
}
}
public String leastCommonRecentMessage(){
String lrm = null;
int leastOccurence = 1000;
for (String message : messages) {
int occurence = messageCount.get(message);
if(leastOccurence >= occurence){
leastOccurence = occurence;
lrm = message;
}
}
return lrm;
}
}
- Bharat Kumar Arya January 11, 2015