Amazon Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
I think that using LinkedHashMap will solve the problem with mininum coding. Assume the stream is fed in as an Iterator.
public String firstNonRepeatWord(Iterator<String> iterator){
String word = null;
Map<String, Integer> lhm = new LinkedHashMap<String, Integer>();
while(iterator.hasNext()){
String wd = iterator.next();
Integer count = lhm.get(wd);
lhm.put(wd, count != null ? count.intValue()+1 : 1);
}
Iterator<String> keyIt = lhm.keySet().iterator();
while(keyIt.hasNext()){
String wd = keyIt.next();
if(lhm.get(wd) == 1){
return wd;
}
}
return null;
}
1. Create A DLL and take two arrays mark[ ] and inDLL[ ]
2. whenever a character first encountered make inDLL[ ] at that index true and add it to last of the DLL, and when the character repeats make mark[] at that index true.
//implementation using Deque in java.. courtsey geeksforgeeks.org
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
String s="wejfweuioewurwfjkwejfoiwefuwioeufowieuwoei";
Deque<Character> q=new LinkedList<Character>();
boolean mark[]=new boolean[256];
boolean inDLL[]=new boolean[256];
for(int i=0;i<256;i++){
mark[i]=false;
inDLL[i]=false;
}
Deque<Integer> h=new LinkedList<Integer>();
int i=0;
while(i<s.length()){
Character n= s.charAt(i);
if(!mark[n]){
if(!inDLL[n]){
q.add(n);
inDLL[n]=true;
}
else{
q.removeFirstOccurrence(n);
mark[n]=true;
}
}
if(!q.isEmpty()){
System.out.println("first element is:"+q.peek());
}else{
System.out.println("All Elements Repeated ");
}
i++;
}
}
}
In theory we could collect all the strings and compare to each next string in the stream.
With performance question put aside, there is a problem of fitting all strings into memory.
Given that stream can be very large this is not a feasible solution.
So we need to cope with the open-ended size of the stream and come up with a finite memory usage.
This can be done with
1. building 'ideal dictionary', using tries - i.e. each word is a chain of nodes, each node represents a character.
2. The dictionary would have a counter on a leaf node of each word, keeping its occurrence count.
3. Along with this we'll need to keep track of the order in which the words are inserted in to the dictionary, canbe done with array wordHeadNodes[], where each item is pointer to the word-start node in dictionary-tries.
4. Once stream.haxNext() == false, iterate through the array and stop when current word has occurrence == 1.
We could add the words in the stream in a Set and the first time the add method returns false,we print that word.
something like
Set<String>words=new Set<>();
String s="";
boolean flag;
while(read.hasNext())
{
s=read.getNext;
flag=words.add(s);
if(flag==false)
System.out.println(s);
}
import java.util.Deque;
import java.util.LinkedList;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
String s="wejfwkeuioewurwfjwejfoiwefuwioeufowieuwoei";
Deque<Character> q=new LinkedList<Character>();
boolean mark[]=new boolean[256];
boolean inDLL[]=new boolean[256];
for(int i=0;i<256;i++){
mark[i]=false;
inDLL[i]=false;
}
int i=0;
while(i<s.length()){
Character n= s.charAt(i);
if(!mark[n]){
if(!inDLL[n]){
q.add(n);
inDLL[n]=true;
}
else{
q.removeFirstOccurrence(n);
mark[n]=true;
}
}
i++;
}
if(!q.isEmpty()){
System.out.println("first element is:"+q.peek());
}else{
System.out.println("All Elements Repeated ");
}
}
}
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class WordRepeat {
static int ch;
static String s;
static HashMap<String, Integer> map = new HashMap<String, Integer>();
static ArrayList<String> list = new ArrayList<String>();
public static void main(String[] args) throws IOException {
getData();
}
private static void getData() throws IOException {
s = "";
while(true) {
if (hasNext()) {
ch = getNext();
if ((char) ch != ' ') {
if (ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z') {
s += Character.toString((char) ch);
}
} else {
if (!s.equals("")) {
list.add(s);
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else {
map.put(s, 1);
}
s = "";
}
}
} else {
list.add(s);
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else {
map.put(s, 1);
}
break;
}
}
for (String str : list) {
if (map.containsKey(str)) {
if(map.get(str) == 1) {
System.out.println(str);
break;
}
}
}
}
private static boolean hasNext() throws IOException {
if ((ch = System.in.read()) != '\n') {
return true;
} else {
return false;
}
}
private static int getNext() throws IOException {
return ch;
}
}
I use just hash map to keep appearing order in stream and when same word come up, I put the order as a negative number.
private static String solve(Stream stream) {
Map<String, Integer> counter = new HashMap<>();
StringBuilder sb = new StringBuilder();
int order = 0;
while (stream.hasNext()) {
char ch = stream.getNext();
// assume a word only have letters and digits
if (Character.isLetterOrDigit(ch)) {
ch = Character.toLowerCase(ch);
sb.append(ch);
}
if ((!Character.isLetterOrDigit(ch) || !stream.hasNext()) && sb.length() > 0) {
String str = sb.toString();
order++;
sb = new StringBuilder();
if (counter.containsKey(str)) {
counter.put(str, -order);
} else {
counter.put(str, order);
}
}
}
int minOrder = order + 1;
String result = null;
for (Map.Entry<String, Integer> e : counter.entrySet()) {
if (e.getValue() > 0 && e.getValue() < minOrder) {
result = e.getKey();
minOrder = e.getValue();
}
}
return result;
}
I use a hash map to keep order and when same word comes up, I put the order as negative.
private static String solve(Stream stream) {
Map<String, Integer> counter = new HashMap<>();
StringBuilder sb = new StringBuilder();
int order = 0;
while (stream.hasNext()) {
char ch = stream.getNext();
// assume a word only have letters and digits
if (Character.isLetterOrDigit(ch)) {
ch = Character.toLowerCase(ch);
sb.append(ch);
}
if ((!Character.isLetterOrDigit(ch) || !stream.hasNext()) && sb.length() > 0) {
String str = sb.toString();
order++;
sb = new StringBuilder();
if (counter.containsKey(str)) {
counter.put(str, -order);
} else {
counter.put(str, order);
}
}
}
int minOrder = order + 1;
String result = null;
for (Map.Entry<String, Integer> e : counter.entrySet()) {
if (e.getValue() > 0 && e.getValue() < minOrder) {
result = e.getKey();
minOrder = e.getValue();
}
}
return result;
}
here is my thought, I use a hash map to keep order of words.
private static String solve(Stream stream) {
Map<String, Integer> counter = new HashMap<>();
StringBuilder sb = new StringBuilder();
int order = 0;
while (stream.hasNext()) {
char ch = stream.getNext();
// assume a word only have letters and digits
if (Character.isLetterOrDigit(ch)) {
ch = Character.toLowerCase(ch);
sb.append(ch);
}
if ((!Character.isLetterOrDigit(ch) || !stream.hasNext()) && sb.length() > 0) {
String str = sb.toString();
order++;
sb = new StringBuilder();
if (counter.containsKey(str)) {
counter.put(str, -order);
} else {
counter.put(str, order);
}
}
}
int minOrder = order + 1;
String result = null;
for (Map.Entry<String, Integer> e : counter.entrySet()) {
if (e.getValue() > 0 && e.getValue() < minOrder) {
result = e.getKey();
minOrder = e.getValue();
}
}
return result;
}
import java.util.Scanner;
public class NonRepeatingWord {
public static void main(String[] args) {
TreeNode root = null;
TreeNode listStart = null;
TreeNode listEnd = listStart;
String word = null;
int count = 0;
Scanner sc = new Scanner(System.in);
word = sc.next();
do {
TreeNode newNode = new TreeNode(word);
if (listEnd == null) {
listStart = newNode;
listEnd = listStart;
root = listStart;
} else {
if (insertTree(newNode, root)) {
listEnd.next = newNode;
listEnd = listEnd.next;
}
}
word = sc.next();
count++;
} while (count < 10);
while (listStart != null) {
if (listStart.count == 1) {
System.out.println(listStart.value);
break;
}
listStart = listStart.next;
}
}
public static boolean insertTree(TreeNode newNode, TreeNode node) {
if (node.value.compareTo(newNode.value) > 0)
if (node.left != null)
return insertTree(newNode, node.left);
else {
node.left = newNode;
return true;
}
else if (node.value.compareTo(newNode.value) < 0)
if (node.right != null)
return insertTree(newNode, node.right);
else {
node.right = newNode;
return true;
}
else {
node.count++;
return false;
}
}
}
class TreeNode {
String value;
TreeNode next;
TreeNode left;
TreeNode right;
int count;
TreeNode(String value) {
this.value = value;
this.count = 1;
}
}
private static String solve(Stream stream) {
Map<String, Integer> counter = new HashMap<>();
StringBuilder sb = new StringBuilder();
int order = 0;
while (stream.hasNext()) {
char ch = stream.getNext();
// assume a word only have letters and digits
if (Character.isLetterOrDigit(ch)) {
ch = Character.toLowerCase(ch);
sb.append(ch);
}
if ((!Character.isLetterOrDigit(ch) || !stream.hasNext()) && sb.length() > 0) {
String str = sb.toString();
order++;
sb = new StringBuilder();
if (counter.containsKey(str)) {
counter.put(str, -order);
} else {
counter.put(str, order);
}
}
}
int minOrder = order + 1;
String result = null;
for (Map.Entry<String, Integer> e : counter.entrySet()) {
if (e.getValue() > 0 && e.getValue() < minOrder) {
result = e.getKey();
minOrder = e.getValue();
}
}
return result;
}
I use a hash map to keep order of words.
private static String solve(Stream stream) {
Map<String, Integer> counter = new HashMap<>();
StringBuilder sb = new StringBuilder();
int order = 0;
while (stream.hasNext()) {
char ch = stream.getNext();
// assume a word only have letters and digits
if (Character.isLetterOrDigit(ch)) {
ch = Character.toLowerCase(ch);
sb.append(ch);
}
if ((!Character.isLetterOrDigit(ch) || !stream.hasNext()) && sb.length() > 0) {
String str = sb.toString();
order++;
sb = new StringBuilder();
if (counter.containsKey(str)) {
counter.put(str, -order);
} else {
counter.put(str, order);
}
}
}
int minOrder = order + 1;
String result = null;
for (Map.Entry<String, Integer> e : counter.entrySet()) {
if (e.getValue() > 0 && e.getValue() < minOrder) {
result = e.getKey();
minOrder = e.getValue();
}
}
return result;
}
def findFirstNonRepeat(hasNext:()=>Boolean, next:()=>Char): Option[String] = {
@tailrec
def helper(lm:ListMap[String, Boolean]):Option[String] = {
val nextWord = parseWord(hasNext, next)
nextWord match {
case None => lm.filter{ case (_, duplicated) => !duplicated}.map(_._1).headOption
case Some(word) => helper(lm + (word -> lm.contains(word)))
}
}
helper(ListMap.empty)
}
Utility methods:
def isLetter(c:Char):Boolean = c.toLower >= 'a' && c.toLower <= 'z'
def parseWord(hasNext:()=>Boolean, next:()=>Char):Option[String] = {
@tailrec
def moveNext(acc:String):String = if(hasNext()) {
val c = next()
if(isLetter(c)) moveNext(acc + next()) else (moveNext(acc))
} else acc
val result = moveNext("")
if(result == "") None else Some(result)
}
Linked Hashset.
LinkedHashSet<String> hashset = new LinkedHashSet<String>();
while(hasNext()){
String word = getNext();
if(!hashset.contains(word))
hashset.add(word);
else
hashset.remove(word);
}
Use iterator and break after iterating the first content.
space and time : O(n)
disadvantage : blue black blue black
output would be blue which should not happen.
Other choice can be linkedhashmap with count but iterating the entire hashmap will also take 0(n) ...
We can improve further with LinkedHashMap. We need not iterate the whole map. Remove the duplicate elements from the map as you see them. And, then the first entry of the map would be the answer. Here is the code:-
String[] ar = st.split("[ .]");
Map<String, Boolean> map = new LinkedHashMap<>();
for(String s : ar){
String lower = s.toLowerCase();
if(map.containsKey(lower)){
map.remove(s);
}
else{
map.put(lower, true);
}
}
for(Map.Entry<String, Boolean> entry :map.entrySet()){
System.out.println(entry.getKey());
return;
}
string_node_map = {}
d = DoubleList()
def first_non_repeated(input_str):
if input_str in string_node_map:
val_ = string_node_map[input_str]
if val_[0]:
d.remove(input_str)
string_node_map[input_str] = (True, None)
else:
new_node = d.append(input_str)
string_node_map[input_str] = (True, new_node)
return d.head.data
Each word is stored in a Trie and also in LinkedList. Trie<Node> stores Node reference of the word in LinkedList<Word>. If the word appears again delete this node from linkedList. Insert an empty Node in trie to represent already duplicate. Repeat for every word. At the end first element of LinkedList is the answer.
- Anonymous February 17, 2015