Yahoo Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
Great solution!
I have same idea.
Below is my implementation in C++, using doubly linked list.
Interesting Java has LinkedHashSet data structure. I don't know whether C++ has the alternative or not.
#include <iostream>
#include <map> // use unordered_map for hashing in O(1)
using namespace std;
struct Node{
char item;
Node * next;
Node * prev;
};
class List{ // doubly linked list
private:
Node * _head;
Node * _tail;
public:
List(){
_head = NULL;
_tail = NULL;
};
~List(){};
//insert a new node to the tail of the list:
Node * insert(char newItem){
Node *x = new Node;
x->item = newItem;
x->next = NULL;
x->prev = NULL;
//first element:
if (NULL == _head){
_head = x;
_tail = x;
return _head;
};
//not first:
_tail->next = x;
x->prev = _tail;
_tail = _tail->next;
return x;
};
//remove a node pointed by x. Precondition: x must be in the list!
void remove (Node *x){
if (x == _head){
if (x == _tail){
_head = NULL;
_tail = NULL;
delete x; x = NULL;
return;
};
_head = x -> next;
_head -> prev = NULL;
x->next = NULL; x->prev = NULL;
delete x; x = NULL;
return;
};
if (x == _tail){ // x != _head
_tail = x -> prev;
_tail->next = NULL;
x->next = NULL; x->prev = NULL;
delete x; x = NULL;
return;
};
// x in the middle:
x->prev->next = x->next;
x->next->prev = x->prev;
x->next = NULL; x->prev = NULL;
delete x; x = NULL;
return;
};
char getHead(){
if (_head) return _head->item;
else return 0;
};
void clear(){
_head = NULL;
_tail = NULL;
};
};
List myDLL;
map<char, Node *> myHash;
map<char, int> Counter;
int main()
{
myDLL.clear();
string S = "gaabfcacbdegdfehhoto";
for(int i = 0; i<S.length(); i++){
if (Counter.count(S[i]) < 1){ // not in the Counter
Node *x = myDLL.insert(S[i]);
myHash[S[i]] = x;
}else
if (Counter[S[i]] ==1){
Node *x = myHash[S[i]];
myDLL.remove(x);
myHash[S[i]] = NULL;
};
Counter[S[i]]++;
};
char c = myDLL.getHead();
cout <<"First unique character is: ";
if (c and (Counter[c]==1)) cout <<c<<endl;
else cout <<" No unique char!"<<endl;
return 0;
}
Nice solution but I think this can be optimized further. I don't think you need a HashMap.
Hi,
The other way is to use LinkedHashMap. Don't need LinkedHashSet.
After inserting each character into the LinkedHashMap (first time character value is 0, second character value is 1). After these all finish, search from the top of Linked hash map to find the first character with value 0.
Let's keep a secondary array that will tell us whether the character at the index has a copy.
We will also keep a hashtable, call it h, with key value pair of this <char, indices of char>.
Finally keep a pointer on the secondary array.
We pass through the list and add characters to the hashtable. If there is already a value for the key to that char, we set the position in the secondary array to 1. If we set a value to 1 and the secondary array pointer is pointing there, we increment this pointer until it points to a 0.
at the end, return the character at the position the pointer is pointing to.
Some code:
public char firstUnique(String s) {
HashMap<Character, ArrayList<Integer>> h = new HashMap<Character, ArrayList>();
int[] valid = new int[s.length()];
int ptr = 0;
char currentChar;
for (int i = 0; i < s.length(); i++) {
currentChar = s.charAt(i);
if (!isUnique(currentChar, i, h, valid)) {
for (Integer i : h.get(currentChar)) {
if (i == ptr) {
while (arr[ptr++] != 0) {}
}
}
}
}
if (ptr >= s.length()) {
return '';
}
return s.charAt(ptr);
}
public boolean isUnique(char c, int currIndex, HashMap h, int[] arr) {
if (h.exists(c)) {
h.get(c).add(currIndex);
arr[currIndex] == 1;
return true;
}
ArrayList<Integer> toAdd = new ArrayList<Integer>();
toAdd.add(currIndex);
h.put(c, toAdd);
return false;
}
HI SK,
I didn't really get your solution , would you please explain a little more systematically.
Sure,
The hashtable will be what notifies us if we've reached a non-unique character, because we will have multiple things in our value to the key of such a character. Our secondary array serves to flag characters that are non-unique (0 for unique, 1 for nonunique). When we update the hashtable so that we have uncovered a non-unique char, we will know to update the secondary array at the index for that char. The pointer of the secondary array will tell us the first character that is non-unique, so we only want to move it when the hashtable update results in an update in that array at the position of that pointer. So we increment this pointer until it gets to 0, indicating the first non-unique character.
HI Sk,
Thank you for your response. This is a good solution.
But the interviewer wanted me to optimize more. you have a loop where we sent the pointer to index with 0 value. I had proposed something similar and he wanted me to remove that loop as well.
I ended up suggesting using a LinkedList as a queue instead of the secondary array (i also maintained a hashmap) and inserting at unique chars at end as and when they come. He wanted the removal ( setting point ptr in your solution) to be O(1) so i suggested maintaining reference to the Node and using a doubly Linkedlist.
I feel this isnt a clean solution but I couldnot think of anything better.
public int find(String str){
int leng =str.length();
Map<String, Integer> poses = new HashMap();
for(int i=0; i<str.length();i++){
String c = str.substring(i, i+1);
if(poses.containsKey(c)){
int tmp = (int) poses.get(c);
poses.put(c, tmp+leng );
}else{
poses.put(c, i);
}
}
int minPos = 1000;
String s;
for (String key : poses.keySet() ) {
if( poses.get(key) < minPos ){
minPos = poses.get(key);
s = key;
}
}
return minPos;
}
s=raw_input()
li=[]
d={}
for l in s:
if l not in li:
li.append(l)
d[l]=d.get(l,0)+1
for l in li:
if d[l]==1:
print l
break
void findFirstNonRepeatedCharSinglePass()
{
string str = "tis ils kheskt";
char charMap[256] = { 0 };
//lets have a vector with <index, char > they will be stored in sorted order of the string index
vector<pair<int, char>> map;
for (int i = 0; i < str.size(); i++) {
//if the char is already duplicate we we can avoid it adding into charindex
if (charMap[str[i]] == 0){
map.push_back(make_pair(i, str[i])); // This will not work for bigger strings as i can be very large so either u need array of size oO(N) space;
}
charMap[str[i]]++;
}
int size = map.size();
for (auto &x : map) {
if (charMap[x.second] == 1) {
cout << "first non-repeating char " << x.second;
}
}
}
here is the logic:
1. maintain two 256 char tables one to keep count of char occurrence.
2. second to store chars as per their indexes in the string, skip chars occurring more than once.
3. traverse second array and check the char's count in first arr if it's one, you got first non-repeating char.
void findFirstNonRepeatedCharSinglePass()
{
string str = "tis is thesk";
char charMap[256] = { 0 };
char charIndx[256] = {' '};
for (int i = 0; i < str.size(); i++) {
//if the char is already duplicate we we can avoid it adding into charindex
if (charMap[str[i]] == 0){
charIndx[i] = str[i];
}
charMap[str[i]]++;
}
for (int i = 0; i < 256; i++) {
char ch = charIndx[i];
if (ch != ' ' && charMap[ch] == 1) {
cout << "First non-repeated char " << ch;
break;
}
}
}
import java.util.ArrayList;
class SolutionForFindFirstNonRepeatingCharInSinglePass {
public String firstNonRepeatingChar(String str) {
if(str.length() == 0) {
return "";
}
ArrayList<Character> temp = new ArrayList<Character>();
boolean[] charmap = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (!charmap[val]) {
temp.add(str.charAt(i));
charmap[val] = true;
} else {
if (temp.size() != 0) {
temp.remove((Character) str.charAt(i));
}
}
}
if (temp.size() == 0) {
return "";
}
return temp.get(0) + "";
}
}
public class FindFirstNonRepeatingCharInSinglePass {
public static void main(String[] args) {
SolutionForFindFirstNonRepeatingCharInSinglePass sol = new SolutionForFindFirstNonRepeatingCharInSinglePass();
System.out.println("1.INPUT: aaaaaaaaaaa ANS: " + sol.firstNonRepeatingChar("aaaaaaaaaaa"));
System.out.println("2.INPUT: \"\" ANS: " + sol.firstNonRepeatingChar(""));
System.out.println("3.INPUT: aabbccd ANS: " + sol.firstNonRepeatingChar("aabbccd"));
System.out.println("4.INPUT: aabcbcba ANS: " + sol.firstNonRepeatingChar("aabcbcba"));
System.out.println("5.INPUT: aabcbcbe ANS: " + sol.firstNonRepeatingChar("aabcbcbe"));
System.out.println("6.INPUT: abcde ANS: " + sol.firstNonRepeatingChar("abcde"));
System.out.println("7.INPUT: abcbcbae ANS: " + sol.firstNonRepeatingChar("abcbcbae"));
System.out.println("8.INPUT: abcbedcbae ANS: " + sol.firstNonRepeatingChar("abcbedcbae"));
System.out.println("9.INPUT: abcbedcbfae ANS: " + sol.firstNonRepeatingChar("abcbedcbfae"));
}
}
HI scorpion king, Thank you for your response. This is a good solution.
If i understand correctly this is 2 scans. One for your main for loop for length of string. Other is the arraylist remove operation
temp.remove((Character) str.charAt(i));
Removing a element from ArrayList is linear time.
The interviewer (as mentioned in question) wanted a single scan solution, without any subloops
public static Character firstUnqiue(String str) {
Map<Character, Integer> occRecorder = new LinkedHashMap<Character, Integer>();
for (char c : str.toCharArray()) {
if (occRecorder.get(c) == null) {
occRecorder.put(c, 1);
} else {
occRecorder.put(c, occRecorder.get(c) + 1);
}
}
for (Character key : occRecorder.keySet()) {
if (occRecorder.get(key) == 1) {
return key;
}
}
return null;
}
/*Solution: 1. Create a LinkedHashSet "set" that stores the Characters
* 2. Loop through the String.
* 3. Check if the ascii array has true for that character.
* 4. If yes then check if set contains the character. If yes then remove it.
*
* 3-b) If ascci array is false for that Character mark it true and add it to the set.
*
* 5. After the loop return the first element in the set if size of set > 0
*
* */
public static void problem3()
{
//String input = "tis ils khesktplhe";
String input = "abcedbacc";
Set<Character> set = new LinkedHashSet<>();
boolean[] ascii = new boolean[256];
for(char ch : input.toCharArray())
{
int index = (int) ch;
if(ascii[index])
{
if(set.contains(ch))
{
set.remove(ch);
}
}
else
{
ascii[index] = true;
set.add(ch);
}
}
for(Character ch : set)
{
System.out.println(ch);
break;
}
}
My solution is: I am going to use a HashMap to keep a frequency (counter) and a LinkedHashSet to keep the characters ordered by its insertion.
Every time I detect a frequency = 2, I am going to remove from the LinkedHashSet.
In the end, just the characters presented once will remain sorted by insertion time.
import java.util.*;
/**
* Created by sky on 4/19/15.
*/
public class FirstNonRepeatedCharacter {
private static class Counter {
private int counter;
public Counter(int initial) {
this.counter = initial;
}
public void increment() {
this.counter++;
}
@Override
public String toString() {
return "[" + this.counter + "]";
}
}
public static void main(String[] args) {
String s = "abcdeabc";
Map<Character, Counter> freq = new HashMap<>();
Set<Character> nonRepeated = new LinkedHashSet<>();
for (int i = 0; i < s.length(); i++) {
Character chr = s.charAt(i);
Counter c = freq.get(chr);
if (c != null) {
c.increment();
if (c.counter == 2) {
nonRepeated.remove(chr);
}
} else {
freq.put(chr, new Counter(1));
nonRepeated.add(chr);
}
}
Iterator it = nonRepeated.iterator();
if (it.hasNext())
System.out.println("First non repeated: " + it.next());
}
}
using System;
public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];
for(int i = 0 ; i<cs.Length;i++)
{
int count=0;
for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}
}
}
using System;
public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];
for(int i = 0 ; i<cs.Length;i++)
{
int count=0;
for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}
}
}
using System;
public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];
for(int i = 0 ; i<cs.Length;i++)
{
int count=0;
for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}
}
}
using System;
public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];
for(int i = 0 ; i<cs.Length;i++)
{
int count=0;
for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}
}
}
using System;
public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];
for(int i = 0 ; i<cs.Length;i++)
{
int count=0;
for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}
}
}
/* package whatever; // don't place package name! */
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 input = "abbaad";
// to hold unique characters in string
ArrayList<Character> al = new ArrayList<Character>();
// to hold duplicate characters in string
ArrayList<Character> bl = new ArrayList<Character>();
for(int i = 0; i < input.length(); i++){
if(bl.contains(input.charAt(i))){
al.remove(new Character(input.charAt(i)));
}
else{
al.add(new Character(input.charAt(i)));
bl.add(new Character(input.charAt(i)));
}
}
System.out.println("First non-repeating character is " +al.get(0));
}
}
/* package whatever; // don't place package name! */
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 input = "abbaad";
ArrayList<Character> al = new ArrayList<Character>();
ArrayList<Character> bl = new ArrayList<Character>();
for(int i = 0; i < input.length(); i++){
if(bl.contains(input.charAt(i))){
al.remove(new Character(input.charAt(i)));
}
else{
al.add(new Character(input.charAt(i)));
bl.add(new Character(input.charAt(i)));
}
}
System.out.println("First non-repeating character is " +al);
}
}
This C++ version has just one loop, however uses std::remove which might be doing some looping on the non_repeating char vector.
char find_first_nonrepeating(const std::string& str) {
std::map<char, int> index_map;
std::vector<char> vec;
for (auto ch : str) {
auto it = index_map.find(ch);
if (it == index_map.end()) {
vec.push_back(ch);
index_map.insert(std::pair<char,int>(ch, static_cast<int>(vec.size())));
} else {
int it2 = it->second;
if (it2 != -1) {
vec.erase(std::remove(vec.begin(), vec.end(), ch), vec.end());
index_map[ch] = -1;
}
}
}
if (vec.size())
return vec[0];
else
return '\0';
}
utilize a dynamic list-like structure, i.e. a set in python. Have two sets, values we know are repeated, and values weve only seen once so far.
As you traverse the characters in the string, check to see if char x (the current char) is already in the set of values we know repeat, if so, skip it. If x is in the set of values weve only seen once, add x to the set of repeating vals and remove it from the unseen set. Otherwise, just add it to set of unseen values.
in python:
def find_non_rep(word):
seen_vals = set()
unseen_vals = set()
for x in word:
if x in seen_vals:
continue
elif x in unseen_vals:
seen_vals.add(x)
unseen_vals.remove(x)
else:
unseen_vals.add(x)
return unseen_vals[0] if unseen_vals else None
How this works is that any values we know (empirically) are repeated are made accesible to allow skipping and keep track of invalid values. If the value we look at has been seen before, it will be either in the repeated vals or the list of vals only seen once, in either case, it will be skipped. What is left after the whole process is finished is a set of values only seen once, just take the first one.
runs through the whole string once, so it runs in O(n) time, and the space usage is at most twice the size of the string, so, O(n) space.
char findFirstUniqueCharacter(const string &s)
{
unordered_set<char> st; map<int, char> index; map<char, int> rank;
int cnt = 0;
for (char c : s)
{
if (st.count(c) > 0)
{
if (rank.count(c) > 0)
{
int i = rank[c]; rank.erase(c); index.erase(i);
}
}
else
{
st.insert(c); rank[c] = ++cnt; index[cnt] = c;
}
}
return index.begin()->second;
}
The problem can be solved using two hashmaps in c++
map double<char,ind>;
map single<char,ind>;
traverse the array and check for each index
1)if the element is in map double then continue to next iteration
2)if the element is in map single then add the element to map double and delete it from map single
3)if the element is not in map single add it to map single with it's index value
Then finally display the character with min index in map single.
My python Solution
def FirstNonRepeatingChar(string):
array = [0]*26
for char in string:
intValue = ord(char) - 97
if array[intValue] == 0:
array[intValue] = 1
elif array[intValue]==1:
array[intValue] = 2
else:
continue
for index in range(26):
if array[index] == 1:
print chr(index+97)
return
FirstNonRepeatingChar('asdfadksl')
#space complexity = O(c)
#time complexity = O(n)
here's one solution using HashMap in java :
import java.util.*;
import java.io.*;
public class FindNonrepeatSinglePass {
static String inputstr = "aabcadeadfa";
public static void main(String[] args) {
HashMap<Character, Integer> mapCharacters = new HashMap<Character, Integer>();
for(int i=0;i<inputstr.length(); i++) {
char c = inputstr.charAt(i);
if(mapCharacters.containsKey(c)) {
int cnt = mapCharacters.get(c);
mapCharacters.put(c, ++cnt);
}
else {
mapCharacters.put(c, 1);
}
}
Iterator<Map.Entry<Character, Integer>> iter = mapCharacters.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry<Character, Integer> entry = iter.next();
if(entry.getValue()>1) {
iter.remove();
}
}
System.out.println(mapCharacters.keySet().toArray()[0]);
}
}
import java.util.*;
import java.io.*;
public class FindNonrepeatSinglePass {
static String inputstr = "aabcadeadfa";
public static void main(String[] args) {
HashMap<Character, Integer> mapCharacters = new HashMap<Character, Integer>();
for(int i=0;i<inputstr.length(); i++) {
char c = inputstr.charAt(i);
if(mapCharacters.containsKey(c)) {
int cnt = mapCharacters.get(c);
mapCharacters.put(c, ++cnt);
}
else {
mapCharacters.put(c, 1);
}
}
Iterator<Map.Entry<Character, Integer>> iter = mapCharacters.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry<Character, Integer> entry = iter.next();
if(entry.getValue()>1) {
iter.remove();
}
}
System.out.println(mapCharacters.keySet().toArray()[0]);
}
}
Python solution time complexity O(N)
def firstOccurrence(S):
dict = {}
Array = []
print "First Occurrence of Char:"
for index in range(len(S)):
if S[index] not in dict.keys():
dict[S[index]] = 1
Array.append(S[index])
else: # If multiple occurrence then set value to -1
dict[S[index]] = -1
#
for elm in Array:
if dict[elm] != -1:
print elm
break
S="californiac"
firstOccurrence(S)
My Python Code
def FirstNonRepeatingChar(string):
array = [0]*26
for char in string:
intValue = ord(char) - 97
if array[intValue] == 0:
array[intValue] = 1
elif array[intValue]==1:
array[intValue] = 2
else:
continue
for index in range(26):
if array[index] == 1:
print chr(index+97)
return
FirstNonRepeatingChar('asdfadksl')
#space complexity = O(c)
#time complexity = O(n)
I came up with the following solution:
Its single pass and uses optimal data structures to avoid subloops.
The idea is:
Maintain a Hashmap of <Character, Integer> which stored how many time a character has appeared as we traverse.
The LinkedHashSet maintains a LinkedList of characters in the order they have appeared.
If any character has re-appeared (count of it in Hashmap > 1) while scanning remove it from LinkedHashSet , which is O(1) operation.
The motivation to use this is final lookup operation to get the first non repeating character is O(1).
If it appeared first time add to the LinkedHashSet (the datastructure will add it to the end of underlying LinkedList) and add to HashMap with count 1.
Thus this LinkedHashSet stores only characters which have appeared once in the order they appear in the string.
At the end of scan of string print the first character from the LinkedHashSet as it will the element which has appeared only once and also it has appeared first. Thus its the First Non Repeating Character.
- um01 April 18, 2015