Goldman Sachs Interview Question Developer Program Engineers
Country: 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, 2015import java.util.HashMap; import java.util.Map; public class Main { // for adding new nodes private static Node headNode = null; // for LROM private static Node tailNode = null; // for check existing messages private static Map<String, Node> messages = new HashMap<>(); // double linked list node private static class Node { private Node prev; private Node next; private String message; public Node(String message) { next = prev = null; this.message = message; } public Node getPrev() { return prev; } public void setPrev(Node prev) { this.prev = prev; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public String getMessage() { return message; } } // add a new message to list private static void addNode(String msg) { Node newNode = null; // first message into list if (messages.isEmpty()) { newNode = new Node(msg); headNode = tailNode = newNode; messages.put(msg, newNode); // remember message } else { // if message already exists if (messages.containsKey(msg)) { newNode = messages.get(msg); // if it is head node we are done otherwise if (newNode != headNode) { newNode.getPrev().setNext(newNode.getNext()); if (newNode != tailNode) { // if not tail node set next node newNode.getNext().setPrev(newNode.getPrev()); } else { // if tail node set it accordingly tailNode = newNode.getPrev(); tailNode.setNext(null); } // make it head node newNode.setNext(headNode); headNode.setPrev(newNode); newNode.setPrev(null); headNode = newNode; } } else { // a new message comes newNode = new Node(msg); if (headNode == tailNode) { // if only message in list headNode = newNode; headNode.setNext(tailNode); tailNode.setPrev(headNode); } else { // set head node only headNode.setPrev(newNode); newNode.setNext(headNode); headNode = newNode; } messages.put(msg, newNode); // remember message } } } public static void main(String[] args) { addNode("M2"); addNode("M1"); addNode("M3"); addNode("M2"); addNode("M1"); System.out.println("LROM=" + tailNode.getMessage()); } }