## Yahoo Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

``````// ZoomBA
def single_pass( string ){
l = list()
set( string.value ) ->{
if ( \$.item @ \$.partial ){
l -=  \$.item
}else{
l += \$.item
}
\$.item // is the key
}
empty(l) ? 'Nothing' : l
}``````

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

This question is really straight forward if more than one passes are allowed. The following are the approaches for more than one passes:

1) Brute Force: Simple O(N^2) solution, compare each character with all the remaining characters.
2) Using a Hashtable: O(N) solution, populate the Hashtable (lets say HashMap) in the first pass. The HashMap contains the character and the count of the character occurrences.
In the second pass, we can look at the count in the HashMap and figure out the the first unrepeated.

Single Pass Solution:
1) If the character is not present in the HashMap, we add the a node to the doubly linked list and to the HashMap.
2) If the character is already present in the HashMap and has occurred only one time before (count of occurrences of character maintained in a different HashMap), we delete the node from the doubly linked list.
3) If the character is already present in the HashMap and has occurred more than one time before simply update the count in the HashMap that maintains the count.

Maintain the head of the doubly linked list in a separate reference throughout the pass, the value of this node will be the first unrepeated character.

Solution for the single pass HashMap and Doubly Linked List proposal:

``````public Character getFirstUnrepeatedCharacter(String inputString)
{
if(inputString==null)
return null;

int inputLength = inputString.length();

if(inputLength<=0)
return null;

Map<Character,DoublyListNode> charHash = new HashMap<Character,DoublyListNode>();
Map<Character,Integer> charCountHash = new HashMap<Character,Integer>();

DoublyListNode firstUnrepeatedChar = null;
DoublyListNode lastUnrepeatedChar = null;
Character currentChar;
DoublyListNode refCharNode;
Integer currentCharCount;

for(int charIndex=0; charIndex<inputLength; charIndex++)
{
currentChar = inputString.charAt(charIndex);
refCharNode = charHash.get(currentChar);

if(refCharNode==null)
{
charCountHash.put(currentChar, 1);
}

else
{
currentCharCount = charCountHash.get(currentChar);
if(currentCharCount==1)
{
firstUnrepeatedChar = removeDoublyNodeFromList(firstUnrepeatedChar, lastUnrepeatedChar, refCharNode);
if(lastUnrepeatedChar == refCharNode)
{
lastUnrepeatedChar = lastUnrepeatedChar.prev;
}
}

charCountHash.put(currentChar, currentCharCount+1);
}

DoublyListNode current = firstUnrepeatedChar;

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

if(firstUnrepeatedChar==null)
return null;

return firstUnrepeatedChar.element;
}

private DoublyListNode removeDoublyNodeFromList(DoublyListNode firstUnrepeatedChar,
DoublyListNode lastUnrepeatedChar, DoublyListNode refCharNode) {
if(firstUnrepeatedChar == refCharNode)
{
if(firstUnrepeatedChar.next==null)
{
firstUnrepeatedChar=null;
lastUnrepeatedChar=null;
}
else
{
firstUnrepeatedChar = firstUnrepeatedChar.next;
}
}

else
{
if(lastUnrepeatedChar != refCharNode)
{
refCharNode.next.prev = refCharNode.prev;
}
refCharNode.prev.next = refCharNode.next;
}

return firstUnrepeatedChar;
}

if(firstUnrepeatedChar==null)
{
}

else
{
}

return firstUnrepeatedChar;
}

class DoublyListNode
{
char element;
DoublyListNode next;
DoublyListNode prev;

DoublyListNode(char element)
{
this.element=element;
}
}``````

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

Just maintain vector<pair<char, bool>> and map<char, int>.

``````char firstChar(string s) {
vector<pair<char, bool> > v;
map<char, int> m;
for (size_t i = 0; i < s.length(); i++) {
if (m.find(s[i]) != m.end())
v[m[s[i]]].second = false;
else {
m[s[i]] = v.size();
v.push_back({s[i], true});
}
}
for (auto p : v) {
if (p.second)
return p.first;
}
return '#';
}``````

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

This is my solution passing only once in the array (string whatever) but using a queue to control de first unique:

``````package problems;

import java.util.*;

/**
* Created by fsantos on 2/10/17.
*/
public class Prob153 {
public static void findFirstUnique(int[] arr) {
Queue<Integer> queue = new ArrayDeque<>();
Map<Integer, Integer> freqMap = new HashMap<>();

for (int i = 0; i < arr.length; i++) {
Integer c = freqMap.get(arr[i]);
if (c == null) {
freqMap.put(arr[i], 1);
} else {
freqMap.put(arr[i], c + 1);

if (queue.peek() == arr[i])
queue.remove();
}
}

boolean found = false;

while (!queue.isEmpty()) {
Integer x = queue.remove();
Integer c = freqMap.get(x);

if (c == 1 && !found) {
System.out.println(x);
// Guarantee to purge to queue
found = true;
}
}
}

public static void main(String[] args) {
findFirstUnique(new int[] {1, 2, 3, 1});
}
}``````

Output:

``2``

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Should just need a HashMap and if you traverse from end to front (still just one pass), the last unseen char is the answer. O(l) time and space where l is length of string.

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.