Adobe Interview Question
Android test engineersCountry: India
Interview Type: Written Test
line = "Hi I am there, am good"
table = dict()
for word in line.split():
word = ''.join(e for e in word if e.isalnum()) # Strip special characters
if word not in table:
table[word] = 1
else:
table[word] += 1
sorted_table = sorted(table.iteritems(), key = lambda (k, v): (-v, k))
print sorted_table
Output:
[('am', 2), ('Hi', 1), ('I', 1), ('good', 1), ('there', 1)]
package com.test.training;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class Testing {
public static void main(String[] args) {
HashMap<String,Double> map = new HashMap<String,Double>();
ValueComparator bvc = new ValueComparator(map);
TreeMap<String,Double> sorted_map = new TreeMap<String,Double>(bvc);
map.put("A",67.4);
map.put("B",67.4);
map.put("C",68.4);
map.put("D",67.4);
System.out.println("unsorted map: "+map);
sorted_map.putAll(map);
System.out.println("results: "+sorted_map);
}
}
class ValueComparator implements Comparator<String> {
Map<String, Double> base;
public ValueComparator(Map<String, Double> base) {
this.base = base;
}
// Note: this comparator imposes orderings that are inconsistent with equals.
public int compare(String a, String b) {
if (base.get(a) > base.get(b)) {
return -1;
} else if(base.get(a) < base.get(b)){
return 1;
} else{
return a.compareTo(b);// returning 0 would merge keys
}
/*int ret=0;
if(base.get(a).compareTo(base.get(b))==0){
ret=a.compareTo(b);
} else if (base.get(a) >= base.get(b)) {
ret= 1;
} else {
ret= -1;
}*/
}
}
//heavy
class Node{
String word;
int count;
Node next;
public Node(String word, int count) {
this.word = word;
this.count = count;
}
}
private void reducer(Map<Integer, Node> map){
if(null == map)return;
for (Node node : map.values()) {
if(node.next == null)System.out.println("Word: "+ node.word+" , count: "+node.count);
else{
Node temp = node;
while(temp != null){
System.out.println("Word: "+ temp.word+" , count: "+temp.count);
temp = temp.next;
}
}
}
}
private Map<Integer, Node> mapper(String input){
if(null == input)return null;
Map<Integer, Node> map = new HashMap<Integer, Node>();
String[] words = input.split("\\s+");
for (String data : words) {
if(map.get(data.hashCode())== null){
map.put(data.hashCode(), new Node(data, 1));
}else{
Node node = map.get(data.hashCode());
if(node.word.equals(data)){
node.count = node.count+1;
map.put(data.hashCode(), node);
}else{
while(node.next != null){ //linked list
if(node.word.equals(data)){
node.count = node.count+1;
map.put(data.hashCode(), node);
System.out.println( node.word+" , count: "+node.count);
}
node = node.next;
}
node.next = new Node(data, 1);
}
}
}
return map;
}
package datastructures;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
/*
* Find the occurences of each word in a sentence/
e.g :
"Hi I am there, am good"
am=2, good=1,Hi=1, I=1,there=1
Print in sorted order as per count.
If count is same, it should be alphabetically sorted.
*/
public class StringCategry1 {
LinkListNode start, temp,curr;
char [] sub ;
ArrayList<String> words;
public void output(String s){
s = s.toLowerCase();
int len = s.length();
int i=0,size=0;
words = new ArrayList<String>();
String strs[] = s.split(" ");
while(i<strs.length){
words.add(strs[i]);
i++;
}
System.out.println(words);
Collections.sort(words);
System.out.println(words);
}
public void print(ArrayList<String> w){
int len = w.size();
int i =0,count=1;
//String s = w.get(i);
while(i<len){
if(i+1<len){
if(w.get(i).equals(w.get(i+1)))
count++;
else{
System.out.print(w.get(i)+" "+count+" ");
count=1;
}
}else
System.out.print(w.get(i)+" "+count+" ");
i++;
}
}
public static void main(String args[]){
StringCategry1 obj = new StringCategry1();
obj.output("Hi I am there, am good");
obj.print(obj.words);
}
}
This does not include hashtable concept. Complexity is O(n)+O(nlgn). O(n) for print method and O(nlgn) for sorting list.
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <cctype>
using namespace std;
int main()
{
set<string> words;
map<string, int> words_counts;
string read_str;
getline(cin,read_str);
istringstream line(read_str);
string word;
while (line >> word){
for(int i=0;i<word.size();++i){
if(!isalpha(word[i]))
word.erase(i);
}
++words_counts[word];
words.insert(word);
}
for(set<string>::iterator it=words.begin();it!=words.end();++it){
cout<<(*it)<<"="<<words_counts[(*it)]<<" ";
}
return 0;
}
public class FindCount {
public static void main(String[] args) {
//String s1="Hi Prateek hello Prateek Test String String";
String s1="A B C Z Y X Z X M";
String temp[]=s1.split("\\s+");
TreeMap<ValueObject,Integer> m=new TreeMap<ValueObject,Integer>();
for(int i=0;i<temp.length;i++)
{
ValueObject obj=new ValueObject(temp[i]);
int count;
if((m.get(obj))!=null)
count=m.get(obj)+1;
else
count=1;
m.put(obj,count);
}
System.out.println(m);
}
}
class ValueObject implements Comparable
{
String val;
public ValueObject(String val)
{
this.val=val;
}
@Override
public int compareTo(Object o1) {
String s1=((ValueObject)o1).val;
int comp=compareString(this.val,s1);
return comp;
}
public int compareString(String s1, String s2)
{
char[] c1=s1.toCharArray();
char[] c2=s2.toCharArray();
int l1=c1.length;
int l2=c2.length;
int l=Math.min(l1,l2);
for(int i=0;i<l;i++)
{
if(c1[i]!=c2[i])
return c1[i] - c2[i];
}
return l1-l2;
}
@Override
public boolean equals(Object obj) {
if(this.val.equals(((ValueObject)obj).val))
return true;
return false;
}
@Override
public String toString() {
return this.val;
}
}
Create a hash table with word as key and count as value. As you process each word, look up in the hash table and if found increment count, else insert to hashtable with count 1.
- ns2 February 16, 2013When completed traverse the hash table and insert into a Binary Search Tree with key as the count; if a second node with same count is to be inserted, the value (word) are compared and the smaller value is pushed down. In-order traverse the tree to get final order.