Interview Question
Country: United States
Outlining a simple two-pass approach with dictionary/hashmap. TC:- O(n) and SC:- O(n) where n = number of elements.
Solution in Python:
def findMax(head):
counter = collections.defaultdict(int)
curr = head
# First pass puts the values along with the counts in the map
while curr != None:
counter[curr.data] += 1
curr = curr.next
# Second pass obtains the value with the highest count
# and iterates through the dictionary to find the correct element.
maxCount = max(counter.values())
curr = head
while curr != None:
if counter[curr.data] is maxCount:
print(f'Element {curr.data} is the maxElement occuring {maxCount} times.')
break
curr = curr.next
Test code:
import collections
class Node:
def __init__(self, data):
self.next = None
self.data = data
class SinglyLL:
def __init__(self):
self.head = None
def constructSinglyLL(self, data):
if self.head is None:
self.head = Node(data)
else:
curr, prev = self.head, None
while curr != None:
prev = curr
curr = curr.next
prev.next = Node(data)
return self.head
# Construct 1 2 3 4 2 3 2
singlyLL = SinglyLL()
head1 = None
for node in [1,2,3,4,2,3,3,2]:
head1 = singlyLL.constructSinglyLL(node)
findMax(head1)
# Construct 4 3 5 3 4 5
singlyLL = SinglyLL()
head2 = None
for node in [4,3,5,3,4,5]:
head2 = singlyLL.constructSinglyLL(node)
findMax(head2)
'''
OUTPUT:
Element 2 is the maxElement occuring 3 times.
Element 4 is the maxElement occuring 2 times.
'''
// package whatever; // don't place package name!
import java.io.*;
import java.util.*;
class MyCode
{
private static class LinkedListNode
{
int data;
LinkedListNode next;
}
private static class LinkedList
{
LinkedListNode head;
void add(int data)
{
LinkedListNode node = new LinkedListNode();
node.data = data;
if(head == null)
{
head = node;
}
else
{
LinkedListNode currentNode = new LinkedListNode();
currentNode = head;
while(currentNode.next != null)
{
currentNode = currentNode.next;
}
currentNode.next = node;
}
}
void traverse()
{
LinkedListNode currentNode = head;
if(currentNode == null)
{
System.out.println("List is empty");
return;
}
while(currentNode.next != null)
{
System.out.print(currentNode.data + " ->");
currentNode = currentNode.next;
}
System.out.print(currentNode.data);
}
}
static int getMajor(LinkedList list)
{
HashSet<Integer> majorElemList = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
LinkedListNode currentNode = list.head;
if(currentNode == null)
return -1;
while(currentNode != null)
{
int currElem = currentNode.data;
if(!map.containsKey(currElem))
{
map.put(currElem, 1);
}
else
{
map.put(currElem, map.get(currElem) + 1);
}
if(majorElemList.size() == 0)
{
majorElemList.add(currElem);
}
else
{
int currElemFreq = map.get(currElem);
Iterator iter = majorElemList.iterator();
int majorElemFreq = map.get((int)iter.next());
if(currElemFreq == majorElemFreq)
{
majorElemList.add(currElem);
}
else if(currElemFreq > majorElemFreq)
{
majorElemList.clear();
majorElemList.add(currElem);
}
}
currentNode = currentNode.next;
}
int majorElem = -1;
if(majorElemList.size() == 1)
{
Iterator iter = majorElemList.iterator();
majorElem = (int)iter.next();
}
else
{
currentNode = list.head;
while(currentNode != null)
{
if(majorElemList.contains(currentNode.data))
{
majorElem = currentNode.data;
break;
}
currentNode = currentNode.next;
}
}
return majorElem;
}
public static void main (String[] args)
{
LinkedList list = new LinkedList();
list.add(4);
list.add(3);
list.add(5);
list.add(3);
list.add(4);
list.add(5);
//list.add(2);
int majorElem = getMajor(list);
//list.traverse();
System.out.println("Major element is " + majorElem);
}
}
// package whatever; // don't place package name!
import java.io.*;
import java.util.*;
class MyCode
{
private static class LinkedListNode
{
int data;
LinkedListNode next;
}
private static class LinkedList
{
LinkedListNode head;
void add(int data)
{
LinkedListNode node = new LinkedListNode();
node.data = data;
if(head == null)
{
head = node;
}
else
{
LinkedListNode currentNode = new LinkedListNode();
currentNode = head;
while(currentNode.next != null)
{
currentNode = currentNode.next;
}
currentNode.next = node;
}
}
void traverse()
{
LinkedListNode currentNode = head;
if(currentNode == null)
{
System.out.println("List is empty");
return;
}
while(currentNode.next != null)
{
System.out.print(currentNode.data + " ->");
currentNode = currentNode.next;
}
System.out.print(currentNode.data);
}
}
static int getMajor(LinkedList list)
{
HashSet<Integer> majorElemList = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
LinkedListNode currentNode = list.head;
if(currentNode == null)
return -1;
while(currentNode != null)
{
int currElem = currentNode.data;
if(!map.containsKey(currElem))
{
map.put(currElem, 1);
}
else
{
map.put(currElem, map.get(currElem) + 1);
}
if(majorElemList.size() == 0)
{
majorElemList.add(currElem);
}
else
{
int currElemFreq = map.get(currElem);
Iterator iter = majorElemList.iterator();
int majorElemFreq = map.get((int)iter.next());
if(currElemFreq == majorElemFreq)
{
majorElemList.add(currElem);
}
else if(currElemFreq > majorElemFreq)
{
majorElemList.clear();
majorElemList.add(currElem);
}
}
currentNode = currentNode.next;
}
int majorElem = -1;
if(majorElemList.size() == 1)
{
Iterator iter = majorElemList.iterator();
majorElem = (int)iter.next();
}
else
{
currentNode = list.head;
while(currentNode != null)
{
if(majorElemList.contains(currentNode.data))
{
majorElem = currentNode.data;
break;
}
currentNode = currentNode.next;
}
}
return majorElem;
}
public static void main (String[] args)
{
LinkedList list = new LinkedList();
list.add(4);
list.add(3);
list.add(5);
list.add(3);
list.add(4);
list.add(5);
//list.add(2);
int majorElem = getMajor(list);
//list.traverse();
System.out.println("Major element is " + majorElem);
}
}
C++ solution, O(n) complexity.
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
// Time complexity O(n)
pair<int,int> findMaxOccurence(list<int> sll){
// Save occurence of all numbers in the list. 1 Pass.
unordered_map<int,int> rankMap;
for(auto it : sll){
rankMap[it]++;
}
// Get maxx occurence #
int maxOcc = 0;
for(auto it: rankMap){
if(maxOcc < it.second)
maxOcc = it.second;
}
//Find first pair that has the max. occurences and return it.
for(auto it : sll){
if(rankMap[it] == maxOcc)
return make_pair(it, rankMap[it]);
}
}
int main()
{
list<int> list1 = {1,2,3,4,2,3,2};
pair<int,int> maxOcc = findMaxOccurence(list1);
cout << "Element " << maxOcc.first << " occurs " << maxOcc.second << " time(s)" << endl;
list1 = {4,3,5,3,4,5};
maxOcc = findMaxOccurence(list1);
cout << "Element " << maxOcc.first << " occurs " << maxOcc.second << " time(s)" << endl;
}
Output:
Element 2 occurs 3 time(s)
Element 4 occurs 2 time(s)
Process returned 0 (0x0) execution time : 0.015 s
Press any key to continue.
// Swift
// Creation of linked list
class Node
{
var value:Int // Contains value in node
var nextNode:Node? // Contains reference of next node
init(withValue value:Int)
{
self.value = value
}
}
protocol DataStructure
{
func add(value:Int)
func search(value:Int) -> Node?
func update(value:Int)
func remove(value:Int)
func display()
}
class LinkedList : DataStructure
{
var firstNode:Node?
init() {
}
private func createNode(withValue value:Int)-> Node
{
return Node(withValue: value)
}
private func getLastNode()->Node
{
var currentNode:Node = firstNode!
while currentNode.nextNode != nil {
currentNode = currentNode.nextNode!
}
return currentNode
}
func add(value:Int)
{
if firstNode == nil
{
firstNode = createNode(withValue: value)
}
let lastNode:Node = getLastNode()
lastNode.nextNode = Node(withValue: value)
}
func search(value:Int) -> Node?
{
var currentNode:Node = firstNode!
while currentNode.nextNode != nil {
if currentNode.value == value
{
return currentNode
}
currentNode = currentNode.nextNode!
}
return nil
}
func update(value:Int)
{
let node = search(value: value)
node?.value = value
}
func remove(value:Int)
{
var node = search(value: value)
let prevNode = search(value: value)
let afterNode = node?.nextNode
prevNode?.nextNode = afterNode
node = nil
}
func display()
{
var currentNode:Node = firstNode!
while currentNode.nextNode != nil {
currentNode = currentNode.nextNode!
print("node value \(currentNode.value)")
}
}
func maxOccurancesItems()->(Int, Int)
{
var currentNode:Node = firstNode!
var dict:Dictionary<Int,Int> = Dictionary<Int, Int>();
while currentNode.nextNode != nil {
currentNode = currentNode.nextNode!
var count:Int = -1
if dict[currentNode.value] != nil
{
count = dict[currentNode.value]!
}
else
{
count = 0
}
dict[currentNode.value] = count + 1
}
var maxOccuraces = 0
var maxKey :Int = 0
for key in dict.keys
{
if dict[key]! > maxOccuraces
{
maxKey = key
maxOccuraces = dict[key]!
}
}
return (maxKey,maxOccuraces)
}
}
let linkedList:LinkedList = LinkedList()
linkedList.add(value:4)
linkedList.add(value: 5)
linkedList.add(value: 1)
linkedList.add(value: 3)
linkedList.add(value: 5)
linkedList.add(value: 3)
linkedList.display()
// Find max frequency of occurances in linked list
let maxOccur = linkedList.maxOccurancesItems()
print(" Element \(maxOccur.0) and occurance \(maxOccur.1)")
using namespace std;
int countNode(Node *root)
{
map< int, pair <int,int> > hash;
// ele, occurance,index
int index =1;
while(root)
{
if(hash.find(root->ele) == hash.end()) {
//new one
hash[root->ele]=make_pair(1,index);
} else {
pair <int , int> pr = hash[root->ele];
//dont change index
hash[root->ele]=make_pair(++pr.first,pr.second);
}
root=root->next;
index++;
}
//in hash if you traverse it will be in sorted format
//trverse and pick the first max occuring index
map< int, pair <int,int> >::iterator it;
int max_occ=0;
int first_index=100;
int element=0;
for(it=hash.begin();it!=hash.end();it++)
{
int ele = it->first;
pair <int, int> occ_index=it->second;
if( occ_index.first>=max_occ )
{
if( occ_index.first == max_occ &&
first_index < occ_index.second)
{
continue;
}
max_occ = occ_index.first;
first_index = occ_index.second;
element= ele;
}//end of for
cout << " Element " << element << " index " << first_index <<
" Occrance " << max_occ << endl;;
}
using namespace std;
int countNode(Node *root)
{
map< int, pair <int,int> > hash;
// ele, occurance,index
int index =1;
while(root)
{
if(hash.find(root->ele) == hash.end()) {
//new one
hash[root->ele]=make_pair(1,index);
} else {
pair <int , int> pr = hash[root->ele];
//dont change index
hash[root->ele]=make_pair(++pr.first,pr.second);
}
root=root->next;
index++;
}
//in hash if you traverse it will be in sorted format
//trverse and pick the first max occuring index
map< int, pair <int,int> >::iterator it;
int max_occ=0;
int first_index=100;
int element=0;
for(it=hash.begin();it!=hash.end();it++)
{
int ele = it->first;
pair <int, int> occ_index=it->second;
if( occ_index.first>=max_occ )
{
if( occ_index.first == max_occ &&
first_index < occ_index.second)
{
continue;
}
max_occ = occ_index.first;
first_index = occ_index.second;
element= ele;
}
}//end of for
cout << " Element " << element << " index " << first_index <<
" Occrance " << max_occ << endl;;
}
using namespace std;
int countNode(Node *root)
{
map< int, pair <int,int> > hash;
// ele, occurance,index
int index =1;
while(root)
{
if(hash.find(root->ele) == hash.end()) {
//new one
hash[root->ele]=make_pair(1,index);
} else {
pair <int , int> pr = hash[root->ele];
//dont change index
hash[root->ele]=make_pair(++pr.first,pr.second);
}
root=root->next;
index++;
}
//in hash if you traverse it will be in sorted format
//trverse and pick the first max occuring index
map< int, pair <int,int> >::iterator it;
int max_occ=0;
int first_index=100;
int element=0;
for(it=hash.begin();it!=hash.end();it++)
{
int ele = it->first;
pair <int, int> occ_index=it->second;
if( occ_index.first>=max_occ )
{
if( occ_index.first == max_occ &&
first_index < occ_index.second)
{
continue;
}
max_occ = occ_index.first;
first_index = occ_index.second;
element= ele;
}
}//end of for
cout << " Element " << element << " index " << first_index <<
" Occrance " << max_occ << endl;;
}
using namespace std;
int countNode(Node *root)
{
map< int, pair <int,int> > hash;
// ele, occurance,index
int index =1;
while(root)
{
if(hash.find(root->ele) == hash.end()) {
//new one
hash[root->ele]=make_pair(1,index);
} else {
pair <int , int> pr = hash[root->ele];
//dont change index
hash[root->ele]=make_pair(++pr.first,pr.second);
}
root=root->next;
index++;
}
//in hash if you traverse it will be in sorted format
//trverse and pick the first max occuring index
map< int, pair <int,int> >::iterator it;
int max_occ=0;
int first_index=100;
int element=0;
for(it=hash.begin();it!=hash.end();it++)
{
int ele = it->first;
pair <int, int> occ_index=it->second;
if( occ_index.first>=max_occ )
{
if( occ_index.first == max_occ &&
first_index < occ_index.second)
{
continue;
}
max_occ = occ_index.first;
first_index = occ_index.second;
element= ele;
}
}//end of for
cout << " Element " << element << " index " << first_index <<
" Occrance " << max_occ << endl;;
}
#include <map>
#include <iostream>
int
main (int argc, char* argv[])
{
std::map<int, std::pair<int, int> > m;
int idx = 0;
while (true) {
int val;
std::cin >> val;
if (!std::cin.good())
break;
std::cout << val << " ";
auto p = m.find (val);
if (p == m.end()) {
std::pair <int, int> elem;
elem.first = 1;
elem.second = idx;
m[val] = elem;
}
else {
(*p).second.first++;
}
idx++;
}
std::cout << std::endl;
int mx = -1;
int pos = -1;
int key = -1;
for (auto i = m.begin(); i != m.end(); ++i) {
if (mx <= (*i).second.first) {
mx = (*i).second.first;
if (pos <= (*i).second.second) {
key = (*i).first;
pos = (*i).second.second;
}
}
}
std::cout << key << " occurs " << mx << " times at pos " << pos << std::endl;
}
/* To compile
$ g++ --std=c++11 mode.cc
$ cat mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
# To test
$ ./a.out < mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
2 occurs 5 times at pos 2
*/
#include <map>
#include <iostream>
int
main (int argc, char* argv[])
{
std::map<int, std::pair<int, int> > m;
int idx = 0;
while (true) {
int val;
std::cin >> val;
if (!std::cin.good())
break;
std::cout << val << " ";
auto p = m.find (val);
if (p == m.end()) {
std::pair <int, int> elem;
elem.first = 1;
elem.second = idx;
m[val] = elem;
}
else {
(*p).second.first++;
}
idx++;
}
std::cout << std::endl;
int mx = -1;
int pos = -1;
int key = -1;
for (auto i = m.begin(); i != m.end(); ++i) {
if (mx <= (*i).second.first) {
mx = (*i).second.first;
if (pos <= (*i).second.second) {
key = (*i).first;
pos = (*i).second.second;
}
}
}
std::cout << key << " occurs " << mx << " times at pos " << pos << std::endl;
}
/*
$ g++ --std=c++11 mode.cc
$ cat mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
$ ./a.out < mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
2 occurs 5 times at pos 2
*/
#include <map>
#include <iostream>
int
main (int argc, char* argv[])
{
std::map<int, std::pair<int, int> > m;
int idx = 0;
while (true) {
int val;
std::cin >> val;
if (!std::cin.good())
break;
std::cout << val << " ";
auto p = m.find (val);
if (p == m.end()) {
std::pair <int, int> elem;
elem.first = 1;
elem.second = idx;
m[val] = elem;
}
else {
(*p).second.first++;
}
idx++;
}
std::cout << std::endl;
int mx = -1;
int pos = -1;
int key = -1;
for (auto i = m.begin(); i != m.end(); ++i) {
if (mx <= (*i).second.first) {
mx = (*i).second.first;
if (pos <= (*i).second.second) {
key = (*i).first;
pos = (*i).second.second;
}
}
}
std::cout << key << " occurs " << mx << " times at pos " << pos << std::endl;
}
/*
$ g++ --std=c++11 mode.cc
$ cat mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
$ ./a.out < mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
2 occurs 5 times at pos 2
*/
#include <map>
#include <iostream>
int
main (int argc, char* argv[])
{
std::map<int, std::pair<int, int> > m;
int idx = 0;
while (true) {
int val;
std::cin >> val;
if (!std::cin.good())
break;
std::cout << val << " ";
auto p = m.find (val);
if (p == m.end()) {
std::pair <int, int> elem;
elem.first = 1;
elem.second = idx;
m[val] = elem;
}
else {
(*p).second.first++;
}
idx++;
}
std::cout << std::endl;
int mx = -1;
int pos = -1;
int key = -1;
for (auto i = m.begin(); i != m.end(); ++i) {
if (mx <= (*i).second.first) {
mx = (*i).second.first;
if (pos <= (*i).second.second) {
key = (*i).first;
pos = (*i).second.second;
}
}
}
std::cout << key << " occurs " << mx << " times at pos " << pos << std::endl;
}
#include <map>
#include <iostream>
int
main (int argc, char* argv[])
{
std::map<int, std::pair<int, int> > m;
int idx = 0;
while (true) {
int val;
std::cin >> val;
if (!std::cin.good())
break;
std::cout << val << " ";
auto p = m.find (val);
if (p == m.end()) {
std::pair <int, int> elem;
elem.first = 1;
elem.second = idx;
m[val] = elem;
}
else {
(*p).second.first++;
}
idx++;
}
std::cout << std::endl;
int mx = -1;
int pos = -1;
int key = -1;
for (auto i = m.begin(); i != m.end(); ++i) {
if (mx <= (*i).second.first) {
mx = (*i).second.first;
if (pos <= (*i).second.second) {
key = (*i).first;
pos = (*i).second.second;
}
}
}
std::cout << key << " occurs " << mx << " times at pos " << pos << std::endl;
}
#include <map>
#include <iostream>
int
main (int argc, char* argv[])
{
std::map<int, std::pair<int, int> > m;
int idx = 0;
while (true) {
int val;
std::cin >> val;
if (!std::cin.good())
break;
std::cout << val << " ";
auto p = m.find (val);
if (p == m.end()) {
std::pair <int, int> elem;
elem.first = 1;
elem.second = idx;
m[val] = elem;
}
else {
(*p).second.first++;
}
idx++;
}
std::cout << std::endl;
int mx = -1;
int pos = -1;
int key = -1;
for (auto i = m.begin(); i != m.end(); ++i) {
if (mx <= (*i).second.first) {
mx = (*i).second.first;
if (pos <= (*i).second.second) {
key = (*i).first;
pos = (*i).second.second;
}
}
}
std::cout << key << " occurs " << mx << " times at pos " << pos << std::endl;
}
/*
$ g++ --std=c++11 mode.cc
$ cat mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
$ ./a.out < mode_input.txt
1 1 2 2 3 4 3 5 6 4 4 2 4 1 2 3 2
2 occurs 5 times at pos 2
*/
- jp May 18, 2018/* with out the duplicate bit*/ pair<int, int> findMostFrequentElement(LinkedListNode* node) { pair<int, int> result; unordered_map<int,int> frequency; int max=0; int max_key=0; int key; while(node!=NULL){ frequency[node->value]++; if (frequency[node->value]>max){ max_key=node->value; max=frequency[node->value]; cout<<"Max is:"<< max<< " key is:" << max_key<<endl; result=make_pair(max_key,max); } node=node->next; } return result;