Morgan Stanley Interview Question
InternsCountry: India
Interview Type: Written Test
#include<iostream>
char * firstUnqChar(char* str)
{
char prev = 0; // null char
while(*str)
{
if((prev != *str) && (*str != *(str+1)))
{ return str;}
prev = *str;
++str;
}
return NULL;
}
int main(int argc, char* argv[])
{
if(argc != 2)
return 0;
if(char *p=firstUnqChar(argv[1]))
{
std::cout<<"unique char: "<<*p<<std::endl;
}
else
{
std::cout<<"no unique char"<<std::endl;
}
return 0;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main(){
char str[]="aabbbccccddefffggh";
for(int i=1;str[i]!='\0';i++){
if(str[i]!=str[i-1] && str[i]!=str[i+1]){
printf("%c",str[i]);
getch();
return 0;
}
}
}
it will not check if first element is non-repeating. ex "asssxxxxwwwwww"
add condition for first element.
what if we got a string like this abaczbdcdzeejkjrjk.
you code won't be able to find 'r'.
but this code can:
char FindFirstNonRepeatChar(const char* s)
{
int asc[128][2]={0};
int size=strlen(s);
unsigned char first=-1;
for(int i=0;i<size;i++)
{
asc[s[i]][0]++;
asc[s[i]][1]=i;
}
for(int i=0;i<128;i++)
{
if(asc[i][0]==1)
{
if(first=-1)
{
first=i;
}
else if(asc[first][1]>asc[i][1])
{
first=i;
}
}
}
return first;
}
oday0311 why you are saying it not work for string aaaazddddddejjjjjj....... because while executing its giving correct answer.... check it ones again..
int main()
{
int char1 = getchar(), char2 = getchar(), char3;
if (char1 != char2) printf("%c", char1);
while((char3 = getchar())!=EOF) {
if ((char1 != char2) && (char2 != char3))
printf("%c", char2);
char1 = char2;
char2 = char3;
}
}
//input is char a[]
int temp[26]={0};
int i;
for(i=0; i<alen; i++)
{
temp[a[i]-'a']++
}
for(i=0; i<26; i++)
{
if(temp[i]==1)
printf("%d\n", i+'a');
}
Bin.... your code will not give the first non repeating character in the srting.... But it gives any non repeating character from the string which may or may not be the first.... Check it onces..
char First_repeating_char()
{
char *str = "aabbbccccddeffffgg";
char character[26] ;
for(int i =0 ;i < 26 ;i++)
character[i] = '0';//Not_found;
char *ptr = str ;
while(*ptr != '\0')
{
char x = *ptr;
int insert_index = int(x)-97;
char read = character[insert_index];
if(read == '0')
character[insert_index] = '1';
else if ( read =='1')
character[insert_index] = '2';
ptr++;
}
for(int index =0;index < 26;index++)
{
if (character[index] == '1')
return char(index+97);
}
}
adobe-interview-questions 3 Answers
what will be the output of this code..please explain
#include <iostream>
using namespace std;
int main()
{
int *i, *j;
i=(int *)60;
j=(int *)20;
printf("%d %d %d\n",i,j,i-j);
getchar();
getchar();
return 0;
}
the answer will be 60 20 10. In variable i the address stored is 60 and in variable j the address stored is 20. now when we say print i then 60 is printed, when we say print j then 20 gets printed and when we say print i-j then it means we want to print the number of integers that can be accomodated between these 2 addresses and that is (60-20)/4 = 10
Algorithm: Iterate through the string and for every element except the start and the last one check his two neighbouring elements. If they are different characters - then this is the unique character. The firs and the last element must be compared only with their closest neighbour - only one element each.
public class FirstNRC {
public static void main(String[] args) {
String str ="aabbbccccddeffffgg";
System.out.println(FindFirstNonChar(str));
}
private static Character FindFirstNonChar(String str)
{
if(str.length()==0)
return ' ';
if(str.charAt(0)!=str.charAt(1))
return str.charAt(0);
for(int i=1; i<str.length()-1; i++)
{
if(str.charAt(i)!=str.charAt(i-1)&&str.charAt(i)!=str.charAt(i+1))
return str.charAt(i);
}
if(str.charAt(str.length()-1)!=str.charAt(str.length()-2))
{
return str.charAt(str.length()-1);
}
return ' ';
}
}
Repeating means does it have to be continuous?
I mean if we have abcabcd - does the question caters to this kind of string or it assumes that repeating character to be continous.
Because this code does not work for stings like abcabcd
#include<stdio.h>
#include<stdlib.h>
#define NO_OF_CHARS 256
int *getCharCountArray(char *str)
{
int *count=(int*)calloc(sixeof(int),NO_OF_CHARS);
int i;
for(i=0;*(str+i);i++)
count[*(str+i)]++;
return count;
}
int firstNonRepeating(*str)
{
int *count=getCharCount(str);
int index=-1,i;
for(i=0;*(str+1);i++)
{
if (count[*(str++)]==1)
{index=i;
break;}}
return index;
}
int main()
{
char str[]="hheeyyy you can inpur any string here";
int index=firstNonRepeating(str);
if(index==-1)
{printf("Either all char are repeating or string is empty");}
else{printf("First non-repeating character is%c",str[index]);}
getchar();
return 0;}
Is this ok?
int main()
{
char *str="aaabbbcccdddeggg";
char c='0';
int i=0;
char *str2= new char[strlen(str)];
strcpy(str2,str);
int flag=0;
while(str[i]!='\0')
{
c=str[i];
int j=0;
int count=0;
while(str2[j]!='\0')
{
if(str2[j]==c)
{
count++;
}
j++;
}
if(count==1)
{
cout<<"non repeative char is "<<c;
flag=1;
break;
}
i++;
}
if(flag==0)
cout<<"not found";
getch();
return 1;
}
#include<stdio.h>
#include<string.h>
char first_non_repeat(char *s) {
char *p = s;
char temp;
int count = 0;
char result;
while(*p) {
temp = *p;
count = 0;
while(*p == temp) {
p++;
count++;
}
if(count == 1) {
result = temp;
break;
}
}
if(count == 1) {
return temp;
} else {
return '\0';
}
}
void main() {
char s[] = "aabbbccccddeffffgg";
char result = first_non_repeat(s);
if(result) {
printf("%c\n", result);
} else {
printf("no.\n");
}
getchar();
}
int firstNonRepeatingChar(const char *in)
{
int i;
i=0;
if(*in=='\0')
{
printf("There is not any non repating character\n");
return 1;
}
in++;
i++;
do
{
if(*in!=*(in-1))
{
i++;
}
else
{
i=0;
}
if(i>=2)
{
printf("1st non repeating character is <%c>\n",*(in-1));
break;
}
}while(*in++);
return 0;
}
Alright I wrote an answer that does not require an array for storing repeating characters. It only requires 2 pointers and a flag. The algorithm looks at two characters at a time and sets a flag if they are the same. If they are not the same and the flag is unset then we have our first non repeating character.
public static char retFirstNonRep(string vars)
{
int length = vars.Length;
//handle base cases
if (length == 1)
return vars[0];
if (length == 2)
{
if (vars[0] != vars[1])
return vars[0];
}
int a = 0;
int b = 1;
bool rpt = false;
while (b < length)
{
//check matching
if (vars[a] == vars[b])
rpt = true;
else
{
//check repeat flag
if (rpt == false)
return vars[a];
else
rpt = false;
}
//increment ptrs
a++;
b++;
}
b--;
a--;
if (vars[a] != vars[b])
{
return vars[b];
}
return '\0';
}
I think this approach would be simple and fast, (I am using Java)
Take 2 arraylists, L1 and L2, I will use L1 for all the characters which are non - repeating and L2 for the characters which are repeating.
Consider the example: aabcccddddebfff
Iterate through the characters in the array, so first alphabet is 'a' and put it in L1 assuming this is not repeating, but 2nd character is 'a' again, so check if L1 already has it or not, in this case L1 already had it, so that means it is repeating, so remove 'a' from L1 and put it in L2 (which contains the repeating characters), keep on doing this for all the remaining characters as well, and after the iteration completes, if L1.get(0) is null then all the characters are repeating else L1.get(0) gives you the first non repeating character and L1.get(1) gives you 2nd non repeating character and so on....
I think this solution will work for both aaabbbbcccdeeee and aaabccccdeeebbb type of strings as well, where the repeating characters may not be adjacent.
If you want to make it more fast you can also use LinkedHashMap instead of ArrayLists which will make the running time of the above algorithm as O(n)
public static void finds(char[] n)
{
Hashtable<Character, Integer> table = new Hashtable<Character, Integer>();
for (int i=0;i<n.length;i++)
{
if(!table.containsKey(n[i]))
{
table.put(n[i], 1);
}
else
{
int times = table.get(n[i]);
table.put(n[i],times+1);
}
}
for (int i=0;i<n.length;i++)
{
//System.out.println("The number of times i've seen "+n[i]+" is: "+table.get(n[i]));
if(table.get(n[i])==1)
{
System.out.println("FOUND IT: "+n[i]);
}
}
}
public class NonRepeatingCharacter {
public String str;
public Character ch;
public static void main(String args[])
{
NonRepeatingCharacter n = new NonRepeatingCharacter();
n.setStr("aabbbccccddffffgd");
Character c=n.getNonRepeatingCharacter();
System.out.println(c);
}
public NonRepeatingCharacter()
{
str = "";
ch='A';
}
public void setStr(String str)
{
this.str = str;
}
public Character getNonRepeatingCharacter()
{
int n=str.length();
int i=0,j=0;;
for(i=0,j=2*i+1;j<n-1;i++,j=2*i+1)
{
//System.out.println(str.charAt(j));
if(str.charAt(j)!=str.charAt(j-1) && str.charAt(j)!=str.charAt(j+1))
{
ch=str.charAt(j);
break;
}
}
if(n%2 == 0)
{
if(str.charAt(j-1)!=str.charAt(j))
ch=str.charAt(j);
}
return ch;
}
}
public static void main(String[] args) {
String abc="aabbbccccdeeffffg";
for(int i=0;i<abc.length();i++){
char c=abc.charAt(i);
if(abc.indexOf(c)==abc.lastIndexOf(c)){
System.out.println("The character is ==>"+c);
}
}
You can also put a break one find the first match to make it more efficient.
public void firstNon_repeatingChar(String str){
LinkedHashMap<Character, Integer> hashMap = new LinkedHashMap<Character, Integer>();
for(int i = 0; i < str.length(); i++){
Character c = str.charAt(i);
if(hashMap.get(c) != null){
int value = ((Integer)hashMap.get(c)).intValue();
value++;
hashMap.put(c, value);
}else{
hashMap.put(c, 1);
}
}
Iterator it = hashMap.entrySet().iterator();
boolean first = false;
while(it.hasNext()){
Map.Entry map = (Map.Entry)it.next();
if((Integer)map.getValue() == 1){
if(!first){
System.out.println("first non-repeating character is:" + map.getKey());
first = true;
}
}
}
}
Find all non-repeating:
char str[] = "aaabbbcccddefffgghhiiijjjklllmnoopqqr";
int changed = 0;
int len = strlen(str);
for(int i = 1; i < len; i++)
{
if(str[i-1] != str[i])
changed++;
else changed = 0;
if(changed > 1)
fprintf(stderr, "non-repeating: %c\n", str[i-1]);
if(i == len-1)
fprintf(stderr, "non-repeating: %c\n", str[i]);
}
Solution using java.
package com.algo;
import java.util.HashSet;
import java.util.Set;
public class FirstNonRepeatChar {
public static void main(String[] args) {
Set<Character> alpha = new HashSet<Character>();
Boolean prev = null;
for (int index = 0; index < args[0].length(); index++) {
boolean curr = alpha.add(args[0].charAt(index));
if (curr && Boolean.TRUE.equals(prev)) {
System.out.println("found: " + args[0].charAt(index - 1));
break;
}
prev = curr;
}
}
}
public class FirstNonRepetative {
public static void main(String[] args) {
String str = "aabbbccccddeffffgg";
char[] strInChar = str.toCharArray();
char c = getFirstNonRepChar(strInChar, 1);
System.out.println(c);
}
private static char getFirstNonRepChar(char[] strInChar, int i) {
if (i == 1 && strInChar[0] != strInChar[1]) {
return strInChar[0];
}
else if ((strInChar[i] != strInChar[i - 1]) && (strInChar[i] != strInChar[i + 1])) {
return strInChar[i];
} else {
return getFirstNonRepChar(strInChar, ++i);
}
}
}
#include<stdio.h>
#include<conio.h>
int main()
{
char a[]="aaabbbgsjdgggdudggsiuii";
char *ptr;
ptr=a;
char var[26]={0};
int i=0;
while((*ptr++))
{
var[a[i]-'a']++;
i++;
}
for(int j=0;j<26;j++)
{
if(var[j]==1);
{ printf("first non repiting character \n");
printf("%c",var[j+65]);
break;}
}
getch();
return 0;
}
{{
char * FirstUniqueChar( char * text )
{
int len = strlen( text );
char ch;
if( len < 1 )
{
return NULL;
}
int i = 1;
for( ; i < len-1; i++ )
{
if( text[i-1] != text[i] && text[i] != text[i+1] )
{
return &text[i];
}
}
if( i>= len - 1 )
{
if( text[i-1] != text[i] )
{
return &text[i];
}
}
return NULL;
}
int main( int argc, char ** argv )
{
char buf[] = "aabbccccddefffgg";
char * r = FirstUniqueChar( buf );
printf("%c\n", *r );
return 0;
}
}}
Here is algorithm in java to print first no-repeated character in given string :
public void printFirstOneRepeatedChar(String str) {
if (str.length() == 0) return;
else if (str.length() == 1) System.out.println(str);
else if (str.length() == 2) {
if ( str.charAt(0) != str.charAt(1))
System.out.println(str.charAt(0));
else
return;
}
else {
for (int i=1; i<str.length(); i++) {
boolean unique = (i < str.length()) ? ( (str.charAt(i-1) == str.charAt(i)) || (str.charAt(i) == str.charAt(i+1)) ) : (str.charAt(i-1) == str.charAt(i));
if (unique)
continue;
else
System.out.println(str.charAt(i));
}
}
}
I wrote the code as below.. Please provide suggestions how to optimize it further
//Find first non -repeatin character in string
int main()
{
char string[20];
gets(string);
int i=0;
if(string[i]!=string[i+1]){printf("%c",string[i]);return 0;}
for(;i<strlen(string)-1;i++)
{
if((string[i]!=string[i+1])&&(string[i]!=string[i-1])&&(i!=0))
{printf("%c",string[i]); break;}
}
getch();
return 0;
}
// TODO Auto-generated method stub
final List<String> list = new ArrayList<String>();
list.add("a");
list.add("a");
list.add("b");
list.add("b");
list.add("b");
list.add("c");
list.add("c");
list.add("c");
list.add("c");
list.add("d");
list.add("d");
list.add("e");
list.add("f");
list.add("f");
list.add("f");
list.add("f");
list.add("g");
list.add("g");
Object[] s = list.toArray();
int i =0,j=1;
boolean flag = true;
for(i=0;i<(s.length)-1;)
{
i=j-1;
int count =0;
j=i+1;
do
{
if(((String) s[i]).equalsIgnoreCase((String) s[j]) && (j<list.size()))
{
count++;
flag= true;
}
else
{
flag = false;
}
if(j<(s.length)-1)
j++;
}while(flag) ;
if(count == 0)
{
System.out.println("non repeating character is :::::::"+s[i]);
break;
}
}
Using hash map , the question is pretty straightforward. Works for all the cases.
static void repeatStr(String str){
// brute force: store all in map and find the first non repeating
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0;i<str.length();i++){
char ch = str.charAt(i);
if(map.containsKey(ch)){
map.put(ch,map.get(ch)+1);
}
else{
map.put(ch,1);
}
}
for(int i=0;i<str.length();i++){
char ch = str.charAt(i);
if(map.get(ch) == 1){
System.out.println("first non rep elem is: "+ch);
break;
}
else if(i==str.length()-1){
System.out.println("no such elem");
}
}
}
public class FirstNonRepeating {
public static void main(String[] args) {
String str="aabbbccccddeffffgg";
char ch[]=str.toCharArray();
Map<Character,Integer> hs1=new LinkedHashMap<Character,Integer>();
for(Character ch1:ch)
{
if(hs1.containsKey(ch1))
{
hs1.put(ch1,hs1.get(ch1)+1);
}
else
{
hs1.put(ch1,1);
}
}
Character ch2=null;
for(Character ch1:ch)
{
if(hs1.get(ch1)==1)
{
ch2=ch1;
//System.out.println(ch1);
break;
}
}
System.out.println("So first non-repeating character="+ch2);
}
}
Hi,
In C# with out using Linq
class Program
{
static void Main(string[] args)
{
string str = "aabbbcccccddddddeffffggg";
string tempStr = str;
int charCount = 0;
foreach (char c in tempStr)
{
if (tempStr.Contains(c))
{
charCount++;
}
if (charCount > 1)
{
tempStr = tempStr.Replace(c.ToString(), string.Empty);
charCount = 0;
}
}
Console.WriteLine("Answer = " + tempStr);
Console.ReadLine();
}
}
public static void main(String[] args) {
String str = "aazzzeeeefffmtttddxyz";
char[] characters = str.toCharArray();
Map<Character,Integer> countMap = new HashMap<Character,Integer>();
int count = 0;
for (Character character : characters) {
if (countMap.containsKey(character)) {
countMap.put(character, countMap.get(character) + 1);
} else {
countMap.put(character, 1);
}
}
Set<Character> charSet = countMap.keySet();
for (Character c : charSet) {
if (countMap.get(c) == 1) {
System.out.println("Non Repeating character: " + c);
}
}
}
public static void main(String[] args) {
String str = "aazzzeeeefffmtttddxyz";
char[] characters = str.toCharArray();
Map<Character,Integer> countMap = new HashMap<Character,Integer>();
int count = 0;
for (Character character : characters) {
if (countMap.containsKey(character)) {
countMap.put(character, countMap.get(character) + 1);
} else {
countMap.put(character, 1);
}}
Set<Character> charSet = countMap.keySet();
for (Character c : charSet) {
if (countMap.get(c) == 1) {
System.out.println("Non Repeating character: " + c);
}}}
- Amit January 19, 2013