Microsoft Interview Question Software Engineer in Tests
0of 0 votesFind 1st non-repeating char in string ?
Team: MSIT
Country: United States
i think using the array of size 256 will require an initial pass to initialize the array with 0 values, and this will take an additional o(n) steps which can be avoided if we used hashing, because i think a hashtable is initialized with 0 values automatically.
In programming languages like JAVA all arrays are initialized with default values, here the int array will contain zeros.
@hello_world: which still takes time because it's still work that has to get done by the CPU.
Crate the hashtable with string char as key and the increment the counter when you found the same char in the string , then iterate your hashtable whenever you first found the 1 counter that will be your first non-repeating char.
I think hash table iteration wont give you the "first" non-repeating char as the iterator is not expected to return the keys in order of insertion.
Easily fixed, though: Iterate over the characters in the string, in order, instead of iterating over the hash table.
I don't think the first char with the counter 1 in the hash table is the first non-repeating char in the original string. You may forget the hashcode is generated.
Use set .. wont add duplicates first false operation of insertion is your non repeating character
will not work, initially the set is empty, so every insertion will be a false opertion right?
No, an insertion returns true if the insertion is successful (ie. the element is not already in the set), so the first time it returns false is when you hit the first duplicate.
This, however, doesn't tell you what the first non-repeating character is, only what the first repeating one is.
use set operation, insert each char one by one from the end of the string, the last true operation is the first non repeating char
#include<stdio.h>
#include<string.h>
void main()
{
int n, i=0 , j , count;
char input[10] = "hhhello";
char *ptr1;
ptr1 = input;
n = strlen(input);
for(j=0;j<n;j++)
{
i=0;
count = 0;
for(;i<n;i++)
{
if(ptr1[j] == input[i])
{
++count;
}
}
if (count == 1)
{
printf("The Answer is %c", ptr1[j]);
break;
}
}
}
private static char getFirstNonReatingChar(String input){
boolean isFNR=false;
Set uniqueDs=new HashSet();
for(int i=0;i<input.length();i++){
char c=input.charAt(i);
isFNR=uniqueDs.add(c);
//This the duplicate
if(!isFNR){
i=-1;
uniqueDs=new HashSet();
input=input.replaceAll(c+"","");
}
}
return input.charAt(0);
}
if you use only hash table or only counting array then you have to traverse the string twice making the complexity 2n. but if you use counting array along with a linked list then you can do it in one traversal and you can find kth non repeating character.
for example the input is "ccacbdedb". the steps of the algorithm are :
1. count of 'c' is 1 insert 'c' into the linked list and go ahead.
2. count of 'c' becomes 2 remove 'c' from the linked list and go ahead.
3. count of 'a' is 1 insert 'a' into the linked list and go ahead.
4. count of 'c' becomes 3 go ahead.
5. count of 'b' is 1 insert 'b' into the linked list and go ahead.
6. count of 'd' is 1 insert 'd' into the linked list and go ahead.
7. count of 'e' is 1 insert 'e' into the linked list and go ahead.
8. count of 'd' becomes 2 remove 'd' from the linked list and go ahead.
9. count of 'b' becomes 2 remove 'b' from the linked list and go ahead.
now the linked list contains only 'a' & 'e'. 'a' is the first non repeating character and 'e' is the second non repeating character. you can do it in O(n) (not O(2n)) time in single iteration.
public static int[] getlargest(int [] a, int k){
int max = Integer.MIN_VALUE;
int maxpos = 0;
int [] arr = new int [k];
for(int i=0; i<k; i++){
for(int j=0; j<a.length; j++){
if(a[j] > max){
max = a[j];
maxpos = j;
}
}
arr[i] = max;
a[maxpos] = Integer.MIN_VALUE;
max = Integer.MIN_VALUE;
}
return arr;
}
public static void main(String [] args){
int [] a = {3,5,6,41,4,7,1,2,8,19,65,21};
int [] res = getlargest(a,4);
for(int i=0; i<res.length; i++){
System.out.println((i+1)+"th largest element is : "+res[i]);
}
}
char[] ch2 = "microsoft".toCharArray();
LinkedHashMap<Character, Integer> result1 = new LinkedHashMap<Character, Integer>();
for (int i = 0; i < ch2.length; i++) {
if (result1.containsKey(ch2[i]))
result1.put(ch2[i], -1);
else
result1.put(ch2[i], i);
}// cfimorst //ftsrcomi
for (char ch1 : result1.keySet())
if (result1.get(ch1) != -1) {
System.out.print(ch1);
break;
}
public static char findFirstNotRepeatChar(string inputStr)
{
char outChar = '\0';
int[] charList = new int[256];
for (int i = 0; i < inputStr.Length; i++)
{
charList[inputStr[i]]++;
}
for (int i = 0; i < inputStr.Length; i++)
{
if (charList[inputStr[i]] == 1)
{
outChar=inputStr[i];
break;
}
}
return outChar;
}
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class FirstNonRepeatitiveCharacter {
public static void main(String[] args) {
String s = "alkdfskdjdff";
@SuppressWarnings("unchecked")
LinkedHashMap<String , String> map = (LinkedHashMap<String, String>) populateMap(s);
Set<String> set = map.keySet();
Iterator<String> itr = set.iterator();
while(itr.hasNext()){
String key = itr.next();
if(map.get(key).equals(String.valueOf(1))){
System.out.println(" The first non-repeatitive character is : " + key);
return;
}
}
}
private static Map populateMap(String s){
char[] a = s.toCharArray();
LinkedHashMap<String, String> mMap = new LinkedHashMap<String, String>();
for (int i = 0; i < a.length; i++) {
String key = "" + a[i];
int initalCount = 1;
//Put of Map returns the previous value of the key.
String value = mMap.put(key, String.valueOf(initalCount));
//If the value == null, it means the key is being inserted for the first time
// or the previous value of Key is null , which is not the case here
//If the value != null, it means the key already exists.So,we should get the value
// and increment it by 1
if (value != null) {
int currentCount = Integer.valueOf(value);
currentCount += 1;
mMap.put(key, String.valueOf(currentCount));
}
}
return mMap;
}
}
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class FirstNonRepeatitiveCharacter {
public static void main(String[] args) {
String s = "alkdfskdjdff";
@SuppressWarnings("unchecked")
LinkedHashMap<String , String> map = (LinkedHashMap<String, String>) populateMap(s);
Set<String> set = map.keySet();
Iterator<String> itr = set.iterator();
while(itr.hasNext()){
String key = itr.next();
if(map.get(key).equals(String.valueOf(1))){
System.out.println(" The first non-repeatitive character is : " + key);
return;
}
}
}
private static Map populateMap(String s){
char[] a = s.toCharArray();
LinkedHashMap<String, String> mMap = new LinkedHashMap<String, String>();
for (int i = 0; i < a.length; i++) {
String key = "" + a[i];
int initalCount = 1;
//Put of Map returns the previous value of the key.
String value = mMap.put(key, String.valueOf(initalCount));
//If the value == null, it means the key is being inserted for the first time
// or the previous value of Key is null , which is not the case here
//If the value != null, it means the key already exists.So,we should get the value
// and increment it by 1
if (value != null) {
int currentCount = Integer.valueOf(value);
currentCount += 1;
mMap.put(key, String.valueOf(currentCount));
}
}
return mMap;
}
}
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class FirstNonRepeatitiveCharacter {
public static void main(String[] args) {
String s = "alkdfskdjdff";
@SuppressWarnings("unchecked")
LinkedHashMap<String , String> map = (LinkedHashMap<String, String>) populateMap(s);
Set<String> set = map.keySet();
Iterator<String> itr = set.iterator();
while(itr.hasNext()){
String key = itr.next();
if(map.get(key).equals(String.valueOf(1))){
System.out.println(" The first non-repeatitive character is : " + key);
return;
}
}
}
private static Map populateMap(String s){
char[] a = s.toCharArray();
LinkedHashMap<String, String> mMap = new LinkedHashMap<String, String>();
for (int i = 0; i < a.length; i++) {
String key = "" + a[i];
int initalCount = 1;
//Put of Map returns the previous value of the key.
String value = mMap.put(key, String.valueOf(initalCount));
//If the value == null, it means the key is being inserted for the first time
// or the previous value of Key is null , which is not the case here
//If the value != null, it means the key already exists.So,we should get the value
// and increment it by 1
if (value != null) {
int currentCount = Integer.valueOf(value);
currentCount += 1;
mMap.put(key, String.valueOf(currentCount));
}
}
return mMap;
}
}
First iteration ==> O(n)
Add the characters into a HashMap with String as key and the value as integer count.
Second iteration ==> O(n)
Create a queue, FirstInFirstOut
Traverse on string{
Check if the String key in hashMap is 1
then insert into Queue
}
At the end, You will get the first non repeating, second non repeating ... in order from the queue. (On dequeue method)
package nonRepeating;
import java.util.Scanner;
public class nonRepeating {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
System.out.println("Enter the string:");
String s=scan.nextLine();
int len=s.length();
int j=0,count=0;
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
count=0;
while(j<len){
if(c==s.charAt(j)){
count++;}
j++;
}
if(count==1){
System.out.println(s.charAt(i));
break;
}
}
}
}
Why to use hashing when a simple look up table of size 256 is sufficient?
- hello world March 03, 2012Then iterating through the string again and checking for the values should give you an answer
Eg:MICROSOFT
count['C']=1
count['F']=1
count['I']=1
count['M']=1
count['O']=2
count['R']=1
count['S']=1
count['T']=1
for(char ch : string.toCharArray())
{
if(count[ch] == 1)
return ch;
}
I can see one problem with this if the character set changes then we have to change the count array size. But we have to ask the interviewer for clarification.