## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/* with out the duplicate bit*/
{
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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
# 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())
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):

def constructSinglyLL(self, data):
else:
while curr != None:
prev = curr
curr = curr.next
prev.next = Node(data)

# Construct 1 2 3 4 2 3 2
singlyLL = SinglyLL()
for node in [1,2,3,4,2,3,3,2]:

# Construct 4 3 5 3 4 5
singlyLL = SinglyLL()
for node in [4,3,5,3,4,5]:

'''
OUTPUT:
Element 2 is the maxElement occuring 3 times.
Element 4 is the maxElement occuring 2 times.
'''``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

// package whatever; // don't place package name!

import java.io.*;
import java.util.*;

class MyCode
{

{
int data;
}

{

{

node.data = data;

{
}
else
{

while(currentNode.next != null)
{
currentNode = currentNode.next;
}

currentNode.next = node;
}
}

void traverse()
{
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);
}
}

{
HashSet<Integer> majorElemList = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

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)
{
}
else
{
int currElemFreq = map.get(currElem);
Iterator iter = majorElemList.iterator();

int majorElemFreq = map.get((int)iter.next());

if(currElemFreq == majorElemFreq)
{
}
else if(currElemFreq > majorElemFreq)
{
majorElemList.clear();
}
}

currentNode = currentNode.next;
}

int majorElem = -1;
if(majorElemList.size() == 1)
{
Iterator iter = majorElemList.iterator();

majorElem = (int)iter.next();
}
else
{
while(currentNode != null)
{
if(majorElemList.contains(currentNode.data))
{
majorElem = currentNode.data;
break;
}

currentNode = currentNode.next;
}
}

return majorElem;
}

public static void main (String[] args)
{

int majorElem = getMajor(list);
//list.traverse();
System.out.println("Major element is " + majorElem);

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

// package whatever; // don't place package name!

import java.io.*;
import java.util.*;

class MyCode
{

{
int data;
}

{

{

node.data = data;

{
}
else
{

while(currentNode.next != null)
{
currentNode = currentNode.next;
}

currentNode.next = node;
}
}

void traverse()
{
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);
}
}

{
HashSet<Integer> majorElemList = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

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)
{
}
else
{
int currElemFreq = map.get(currElem);
Iterator iter = majorElemList.iterator();

int majorElemFreq = map.get((int)iter.next());

if(currElemFreq == majorElemFreq)
{
}
else if(currElemFreq > majorElemFreq)
{
majorElemList.clear();
}
}

currentNode = currentNode.next;
}

int majorElem = -1;
if(majorElemList.size() == 1)
{
Iterator iter = majorElemList.iterator();

majorElem = (int)iter.next();
}
else
{
while(currentNode != null)
{
if(majorElemList.contains(currentNode.data))
{
majorElem = currentNode.data;
break;
}

currentNode = currentNode.next;
}
}

return majorElem;
}

public static void main (String[] args)
{

int majorElem = getMajor(list);
//list.traverse();
System.out.println("Major element is " + majorElem);

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

// Swift

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 search(value:Int) -> Node?
func update(value:Int)
func remove(value:Int)

func display()
}

{
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
}

{
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)
}
}

// Find max frequency of occurances in linked list

print(" Element \(maxOccur.0) and occurance \(maxOccur.1)")

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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

*/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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
*/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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
*/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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
*/

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.