Jeanclaude
BAN USER- 0of 0 votes
AnswersThis was a question asked to my cousin in a recent phone interview with Cisco.
- Jeanclaude in United States
You're given an array of integers (unsorted) and the length is really large (perhaps a million integers). Now you are required to write an efficient code to retrieve topN integers. If N is 10, return the top 10 integers from the array. You result may or may not be sorted, that's your call. For e.g. if given array is arr = { 2, 1, 20, 3, 6, 5, 4, 8, 11, 12 }; and given N value is 3, then your result should be either {20, 11, 12} (unsorted) or {11,12, 20} (sorted).| Report Duplicate | Flag | PURGE
Cisco Systems Development Support Engineer Arrays - 2of 2 votes
AnswersPoint errors (if any) in the following pointer code and explain what it does...
- Jeanclaude in United States
char* cp(char *a)
{
char *f;
f=(char*)malloc(strlen(a)*sizeof(char));
while(*a != 0)
{
*f=*a;
f++;
a++;
}
cout<< f;
return f;
}| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test C++ - 0of 0 votes
AnswersThis was asked in an Online written test that was timed (60 mins). And this question was one among the three.
- Jeanclaude in United States
"Write a method to merge three sorted integer arrays into just one array"
Nothing more or less was given. Since it was a written test I assumed that the 1st array had space towards to end which can fit the other two arrays. I can code this but given the timer limitations (of 20 mins per question) I thought it was a bit too much for me to handle unless there is a more obvious way to do this. I did it using two arrays and using the resultant array, I merged it with the 3rd array. That was the best i could think of at that time.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Sorting - 0of 0 votes
AnswersGiven a couple of integer arrays A = {2, 4, 3, 5, 6, 8} & B = {9, 2, 7, 6} - Return the intersection of these arrays.
- Jeanclaude in United States
Once I provided a solution (which was n squared -O (n^2)) he followed up by asking me if I could make it linear (O(n)).| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Arrays - 0of 0 votes
AnswersWrite a method which will accept a string and return true if the string is a palindrome and false if it isn't.
- Jeanclaude in United States
Special conditions:
a) your method should consider lower case and upper case characters to be the same.
b) your method should ignore special characters and white spaces, for e.g. if your input were the strings were "Madam, I'm Adam!!", then you should consider it a palindrome and hence return true ignoring case and special characters. Same with inputs like "Ma'am", "boB" etc should return true.| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer String Manipulation - 0of 0 votes
AnswersGiven a string, write code to find all the rotations of the string. e.g.
- Jeanclaude in United States
if TOP is original string, then its rotations are: OPT, PTO & TOP itself.
Follow up question: Given two input strings, for e.g. Str1="TOP", Str2="OPT", write a code to find if one is the rotation of the other. If it is a rotation, return true, else return false.
Condition: Do not use hash tables.| Report Duplicate | Flag | PURGE
Lab126 SDE1 - 0of 0 votes
AnswersThis was asked to one of my friends in her telephonic interview with ADP.
- Jeanclaude in United States
Imagine you have a 5x5 matrix containing integers... If any of the elements in this original matrix is 0, then your resultant matrix should have the corresponding row and column filled with 0s. For e.g. if 1st element of 1st row, 2nd element of 2nd row......up to 5th element of 5th row are all 0s, then your resultant 5x5 matrix should be all 0s. Your code should be flexible and work for any size of matrix (not just with 5x5).| Report Duplicate | Flag | PURGE
ADP Software Engineer in Test - 0of 0 votes
AnswersForgot to add this question along with my previous...
- Jeanclaude in United States
This is a brain teaser type question...
S E N D
+
M O R E
--------------
M O N E Y
--------------
Each of the above characters hold a specific value which is unique (meaning no two characters have same value). Now the question is, to uncover what value each character stands for...
(Hint - 'M' has to be 1 because it's the carry in the result (M O N E Y). Now similarly back track the rest of the characters)
Note: this hint is given by me, for the sake of understanding the question for interested folks, it was not given to me in the interview).| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test - 0of 0 votes
AnswersImagine we have a large string like this "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD" which contains multiple palindromes within it, like ABCBA, RACECAR, ARA, IAMAI etc... Now write a method which will accept this large string and return the largest palindrome from this string. If there are two palindromes which are of same size, it would be sufficient to just return any one of them.
- Jeanclaude in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test String Manipulation - 0of 0 votes
AnswersWrite code to search and return all those file names present in a given directory (for e.g. C:\>) where the string "Amazon" is present. All the files will be located at different folder levels. Also discuss your approach, time and space complexities for your solution.
- Jeanclaude in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test - 0of 0 votes
AnswersIn order to print all the nouns and verbs present in a given book, what is the underlying algorithm you see to achieve this problem? Discuss the pros and cons of your choice and also how would you test this method. You may assume that the system already knows what are nouns and verbs.
- Jeanclaude in United States| Report Duplicate | Flag | PURGE
Accenture Software Engineer in Test - 3of 3 votes
AnswersIn a given array a = {1, 7, 3, 4, 5, 6, 2} Print the indices of all the combinations which lead to a given sum called target. For e.g. if the method is
- Jeanclaude in United States
Void PrintAllSumCombos(int[] arr, int target) - and the array shown above is passed with sum target = 7, then the output should be:
0, 3, 6
0, 5
1
2, 3
4, 6
Note: For simplicity, You may assume the array does not contain any negative numbers and also consider same set of indices with a different order as identical - for e.g. if 2, 3 is already printed, ignore 3, 2 as they are one and the same.| Report Duplicate | Flag | PURGE
Accenture Software Engineer in Test Arrays - 2of 2 votes
AnswersIn an array of unsorted integers (you may assume the array may contain +ve, -ve and 0s), write a function
- Jeanclaude in United States
int returnNthMax(int[] arr, int n)
which will return the nth Max number. For e.g. if this is given array {2, -4, 5, 6, 0, 7, -1, 10, 9} and n=1, it should return the max number, 10 and if n=3, it should return 3rd max number, which is: 7.| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Arrays - 0of 0 votes
AnswersPrint the actual phone number when given an alphanumeric phone number. For e.g. an input of 1-800-COM-CAST should give output as 18002662278 (note: output also does not contain any special characters like "-").
- Jeanclaude in United States for Windows Phone| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Hash Table - 1of 1 vote
AnswersFind the first non repeating character in a given string. You may assume that the string contains any character from any language in the world, for e.g. an Arabic
- Jeanclaude in United States for Windows Phone
or Greek character even.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test String Manipulation - 1of 1 vote
AnswersCode to check if a given short string is a substring of a main string. Can you get a linear solution (O(n)) if possible?
- Jeanclaude in United States for Office| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test String Manipulation - 1of 1 vote
AnswersThis is one of the interesting questions asked to my friend who had a telephonic with Microsoft recently:
- Jeanclaude in United States
Question: Imagine you have a device that is used to count the number of leaves in a tree. And it has an output screen which displays how many leaves are present in a tree, plus a start/stop button. Write as many test cases as possible and sort them under as different test buckets as possible.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Testing
C# solution...
public static void PrintUniqueCharsInReverseOrder(string s)
{
List<char> list = new List<char>();
for(int i=s.Length-1; i >= 0; i--)
{
if(list.Contains(s[i]))
{
continue;
}
else
{
list.Add(s[i]);
}
}
foreach(char c in list)
{
Console.Write(c);
}
Console.WriteLine();
}
Agree with above comment.. Hashtable should be the most efficient way to do this in my opinion...
- Jeanclaude May 06, 2016I wrote the below, but I'm not exactly sure of the complexity because after comparing each of the element in the array, the sorteddictionary does sorting and I'm not sure how to take that into account while calculating the time complexity here.
public static int[] FindTopK(int[] arr, int k)
{
int[] newlist = new int[k];
if (arr.Length < k)
{
Console.WriteLine("Given array has fewer elements than K value, hence returning all 0s");
return newlist;
}
else if (arr.Length == k)
{
for (int i = 0; i < k; i++)
{
newlist[i] = arr[i];
}
return newlist;
}
else
{
SortedDictionary<int, int> topK = new SortedDictionary<int, int>();
for (int i = 0; i < k; i++)
{
topK.Add(arr[i], 1);
}
for (int i = k; i < arr.Length; i++)
{
if (arr[i] > topK.First().Key)
{
topK.Remove(topK.First().Key);
topK.Add(arr[i], 1);
}
else
continue;
}
for (int i = 0; i < k; i++)
{
newlist[i] = topK.ElementAt(i).Key;
}
}
return newlist;
}
- Jeanclaude April 25, 2015Forgot to mention an important condition. YOU SHOULD NOT SORT or MODIFY THE GIVEN INPUT ARRAY because of obvious performance reasons...
- Jeanclaude April 25, 2015How about this? Wrote this in C#...
public static void OrderOfFrequency(int[] arr, int n)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
for (int i = 0; i < arr.Length; i++)
{
if (dic.ContainsKey(arr[i]))
{
dic[arr[i]]++;
}
else
{
dic.Add(arr[i], 1);
}
}
for (int i = 0; i < n; i++)
{
var x = (from c in dic
select c).OrderByDescending(w => w.Value).ElementAt(i);
Console.Write(x.Key + " ");
if (dic.Count >= n)
continue;
else
break;
}
}
Based on suggestions from alregith and adam - here is the code to process three sorted arrays from the end:
public int[] ThreeMergeSortedArrays(int[] a1, int[] a2, int[] a3)
{
int a1L = a1.Length-1,
a2L = a2.Length-1,
a3L = a3.Length-1;
int[] result = new int[a1.Length + a2.Length + a3.Length];
int resL = result.Length-1;
while (a1L >= 0 && a2L >= 0 && a3L >= 0)
{
if (a1[a1L] >= a2[a2L] && a1[a1L] >= a3[a3L])
result[resL--] = a1[a1L--];
else if (a2[a2L] >= a1[a1L] && a2[a2L] >= a3[a3L])
result[resL--] = a2[a2L--];
else
result[resL--] = a3[a3L--];
}
if (a1L < 0)
{
while (a2L >= 0 && a3L >= 0)
{
if (a2[a2L] >= a3[a3L])
result[resL--] = a2[a2L--];
else
result[resL--] = a3[a3L--];
}
if (a2L < 0)
result[resL] = a3[a3L];
else
result[resL] = a2[a2L];
}
else if (a2L < 0)
{
while (a1L >= 0 && a3L >= 0)
{
if (a1[a1L] >= a3[a3L])
result[resL--] = a1[a1L--];
else
result[resL--] = a3[a3L--];
}
if (a1L < 0)
result[resL] = a3[a3L];
else
result[resL] = a1[a1L];
}
else
{
while (a1L >= 0 && a2L >= 0)
{
if (a1[a1L] >= a2[a2L])
result[resL--] = a1[a1L--];
else
result[resL--] = a2[a2L--];
}
if (a1L < 0)
result[resL] = a2[a2L];
else
result[resL] = a1[a1L];
}
return result;
}
- Jeanclaude March 04, 2015This was my code. There were some syntax errors which I corrected in this code:
public static int[] ThreeMergeSortedArrays(int[] a, int[] b, int[] c)
{
int[] res = TwoMergeSortedArrays(a, b);
res = TwoMergeSortedArrays(res, c);
return res;
}
public static int[] TwoMergeSortedArrays(int[] a1, int[] a2)
{
//this is under the assumption that array a1 has space to fit in entire array a2. No error conditions have been checked.
int i;
int m = a2.Length - 1;
int n = a1.Length - 1 - a2.Length;
if (a2[0] > a1[n])
{
for (i = 0; i < a2.Length; i++)
a1[i + 1 + n] = a2[i];
return a1;
}
for (int k = 0; m >= 0 && n >= 0; k++)
{
if (a1[n] > a2[m])
{
a1[a1.Length - 1 - k] = a1[n];
n--;
}
else
{
a1[a1.Length - 1 - k] = a2[m];
m--;
}
}
if (n < 0 && m >= 0)
{
while (m >= 0)
{
a1[m] = a2[m];
m--;
}
}
return a1;
}
- Jeanclaude March 03, 2015if there is a better or faster way to do this with all three arrays at the same time (instead of merging two at a time and then use that result with the third array), please advise. I'm very much interested to learn.
- Jeanclaude March 03, 2015This is not O ( n ) complexity. This is O ( n ^ 2 ).
- Jeanclaude July 24, 2014If we are allowed to use additional data structure like a Hash table, we can do this easily like this:
The below is in C#...
public static string RemoveDupCharsFromString(string str)
{
if (str == null)
return null;
string newstr = "";
Hashtable ht = new Hashtable();
char[] ca = str.ToCharArray();
int i = 0;
for (i = 0; i < ca.Length; i++)
{
if (ht.ContainsKey(ca[i]))
{
continue;
}
else
{
ht.Add(ca[i], true);
newstr = newstr + ca[i];
}
}
return newstr;
}
- Jeanclaude July 14, 2014That's simple...
How about this one?
bool ispowerof2(int num)
{
bool ispwrof2 = false;
if(num & (num - 1) == 0)
{
ispwrof2 = true;
return ispwrof2;
}
return ispwrof2;
}
Yes, I implemented the same with additional space, took a hashtable, a dictionary in fact... Below is the working solution (C# version)...
public ArrayList intersection_sorted_lists(int[] arr1, int[] arr2)
{
ArrayList alsort = new ArrayList();
int i=0;
Dictionary<int, bool> dic = new Dictionary<int, bool>();
foreach (int n in arr2)
{
if (dic.ContainsKey(n))
continue;
else
dic.Add(n, true);
}
for (i = 0; i < arr1.Length; i++)
{
if (dic.ContainsKey(arr1[i]))
alsort.Add(arr1[i]);
else
continue;
}
return alsort;
}
- Jeanclaude March 20, 2014Yes.. almost that's (ASCII) what I did, but i did not convert the string to lowercase... Below is a working solution:
class Palindrome
{
static void Main(string[] args)
{
string[] strs = new string[]{"Madam, I'm Adam!", "Bob", "", " ", "fuluf", "full"};
foreach (string str in strs)
{
try
{
if (IsPalindrome(str))
{
System.Console.WriteLine(str + " IS a palindrome");
}
else
{
System.Console.WriteLine(str + " is NOT a palindrome");
}
}
catch (Exception e)
{
System.Console.WriteLine("Exception caught: " + e);
}
}
}
public string splcharfreestring(string str)
{
char[] ca = str.ToCharArray();
StringBuilder sb = new StringBuilder();
int i=0;
for (i=0; i< str.Length; i++)
{
if((ca[i] >= 'A' && ca[i] <= 'Z') || (ca[i] >='a' && ca[i] <= 'z'))
{
sb.Append(ca[i]);
}
else
continue;
}
return sb.ToString();
}
static bool IsPalindrome(string str)
{
Palindrome sl = new Palindrome();
string elimatesplchars;
elimatesplchars = sl.splcharfreestring(str);
bool ispal = false;
char[] ca = elimatesplchars.ToCharArray();
int i = 0, j = elimatesplchars.Length - 1;
if (str == null)
{
throw new Exception("str is null");
}
if (str.Length == 1)
return true;
else if (str == "")
return false;
else
{
for (i = 0; i < ca.Length / 2; i++)
{
char ch = ca[j];
if ((ca[i] == ca[j]) || (ca[i] == (char) (ch + 32) || (ca[i] == (char) (ch - 32)) ))
{
ispal = true;
j--;
continue;
}
else
{
ispal = false;
return ispal;
}
}
}
if (ispal == true)
return ispal;
return ispal;
}
}
Here is the solution I have implemented in the interview, from scratch, given the above conditions...
static void Main(string[] args)
{
Program pg = new Program();
string str1 = "TIME";
string str2 = "ETIM";
bool is_rotate = false;
is_rotate = pg.is_rotation(str1, str2);
if(is_rotate==true)
Console.WriteLine("Str2 is a rotation of Str1");
else
Console.WriteLine("Str2 is not a rotation of Str1");
}
public bool is_rotation(string str1, string str2)
{
string[] sarr = new string[str1.Length];
bool is_rotation = false;
sarr = rotate_str(str1);
for (int k = 0; k < sarr.Length; k++)
{
Console.WriteLine(sarr[k]);
}
int i = 0;
for (i = 0; i < str1.Length;i++)
{
if(sarr[i] == str2)
{
is_rotation = true;
return is_rotation;
}
}
return is_rotation;
}
public string[] rotate_str(string str)
{
char[] ca = str.ToCharArray();
int j = 0, len = ca.Length - 1, k = 0, m=0;
char temp=' ';
string[] sa = new string[str.Length];
for (k = 0; k < str.Length; k++)
{
temp = ca[m];
for(j=0; j<len; j++)
{
ca[j] = ca[j + 1];
}
ca[j] = temp;
sa[k] = new string(ca);
if(k==sa.Length-1)
{
return sa;
}
else
{
ca = sa[k].ToCharArray();
continue;
}
}
return sa;
}
- Jeanclaude February 11, 2014Sorry for not clarifying the other conditions...
a) No requirement that the strings have to be unique... so if an input is OOO, then the total strings can be "OOO", "OOO" & "OOO".
b) That's a valid solution to check if one string is a rotation of the other, however the interviewer has openly said I should actually code the given requirements from scratch and not to use this solution...
I thought so, but then was wondering if there is any algo (that I'm not aware of) and could do that... Thanks anyway...
- Jeanclaude February 08, 2014Clarification - my friend also came up with an O(N^2) solution and the interviewer does not seem to have asked for a linear solution.. however out of my curiosity, I'm asking you folks to tell me if there is a way to do this in O(N)?
- Jeanclaude February 07, 2014This is the one I have come up with... it's of the order N^2. But coming to space, although I have used an additional list, it's not as big as the input array... Please let me know if we can do this in O(N) and without using extra space (list, array or any other variables)?
class Program
{
static void Main()
{
Program pob = new Program();
int[,] a = new int[5, 5] { { 0, 1, 1, 3, 4 }, {1, 0, 3, 2, 4 }, {1, 2, 0, 1, 4}, {1, 2, 3, 0, 4}, {1, 2, 3, 4, 0} };
pob.IfAnElementis0FillCorrespondingRowsAndColsTo0s(a);
}
public void IfAnElementis0FillCorrespondingRowsAndColsTo0s(int[,] a)
{
int r = 5, c = 5;
int i = 0, j = 0;
// a = new int[3, 3] { { 2, 1, 0 }, { 3, 2, 4 }, { 2, 1, 1 } };
List<int> list = new List<int>();
//This iteration is required to mark the row & col positions where we have 0s in original array. Add those positions to a list.
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
if (a[i, j] == 0)
{
list.Add(i);
list.Add(j);
}
else
{
continue;
}
}
}
//This iteration actually updates original matrix with 0s wherever applicable.
int k = 0;
for(i= 0; i < list.Count; i+=2)
{
for(j = 0; j < c; j++)
{
a[list[i], j] = 0;
}
for (k = 0; k < r; k++)
{
a[k, list[i+1]] = 0;
}
}
//just prints the modified matrix.
for(i=0; i< r; i++)
{
for(j=0; j < c; j++)
{
Console.Write(a[i,j] + " ");
}
Console.WriteLine("\n");
}
}
}
- Jeanclaude February 07, 2014public void find_intersection_of_two_Int_arrays(int[] arr1, int[] arr2)
{
int i = 0, j = 0, k = 0;
ArrayList aL = new ArrayList();
for (i = 0; i < arr1.Length; i++)
{
for (j = 0; j < arr2.Length; j++)
{
if (arr1[i] == arr2[j])
{
aL.Add(arr1[i]);
Console.Write(aL[k++] + ",");
}
else
continue;
}
}
}
Yes, that's correct. No negative numbers or 0s as per the interviewer.
- Jeanclaude July 09, 2013public string telephonewords(string str)
{
char[] ca = str.ToCharArray();
int i=0;
Dictionary<char, int> dic = new Dictionary<char, int>();
dic.Add('A', 2);
dic.Add('a', 2);
dic.Add('B', 2);
dic.Add('b', 2);
dic.Add('C', 2);
dic.Add('c', 2);
dic.Add('D', 3);
dic.Add('d', 3);
dic.Add('E', 3);
dic.Add('e', 3);
dic.Add('F', 3);
dic.Add('f', 3);
dic.Add('G', 4);
dic.Add('g', 4);
dic.Add('H', 4);
dic.Add('h', 4);
dic.Add('I', 4);
dic.Add('i', 4);
dic.Add('J', 5);
dic.Add('j', 5);
dic.Add('K', 5);
dic.Add('k', 5);
dic.Add('L', 5);
dic.Add('l', 5);
dic.Add('M', 6);
dic.Add('m', 6);
dic.Add('N', 6);
dic.Add('n', 6);
dic.Add('O', 6);
dic.Add('o', 6);
dic.Add('P', 7);
dic.Add('p', 7);
dic.Add('Q', 7);
dic.Add('q', 7);
dic.Add('R', 7);
dic.Add('r', 7);
dic.Add('S', 7);
dic.Add('s', 7);
dic.Add('T', 8);
dic.Add('t', 8);
dic.Add('U', 8);
dic.Add('u', 8);
dic.Add('V', 8);
dic.Add('v', 8);
dic.Add('W', 9);
dic.Add('w', 9);
dic.Add('X', 9);
dic.Add('x', 9);
dic.Add('Y', 9);
dic.Add('y', 9);
dic.Add('Z', 9);
dic.Add('z', 9);
dic.Add('1', 1);
dic.Add('2', 2);
dic.Add('3', 3);
dic.Add('4', 4);
dic.Add('5', 5);
dic.Add('6', 6);
dic.Add('7', 7);
dic.Add('8', 8);
dic.Add('9', 9);
dic.Add('0', 0);
StringBuilder sb = new StringBuilder();
//foreach (KeyValuePair<Char, int> pair in dic)
//{
// Console.WriteLine("Key: {0}, Value: {1}", pair.Key, pair.Value );
//}
while(i< ca.Length)
{
if (ca[i] == '-')
i++;
if (dic.ContainsKey(ca[i]))
{
sb.Append(dic[ca[i]]);
i++;
}
}
// Console.WriteLine(sb);
return sb.ToString();
}
public void removeduplicates(int[] array)
{
int i, j, new_length = 1;
for (i = 1; i < array.Length; i++)
{
for (j = 0; j < new_length; j++)
{
if (array[i] == array[j])
break;
}
/* if none of the values in index[0..j] of array is not same as array[i],
then copy the current value to corresponding new position in array */
if (j == new_length)
array[new_length++] = array[i];
}
for (i = 0; i < new_length; i++)
{
Console.WriteLine(array[i]);
}
}
public void CircularArrayRotation(int[] arr, int sublen)
{
int[] brr = new int[sublen];
int i, k=0, len = arr.Length;
//copy the part of 1st array that needs to be rotated (ideally the size of sublen from the last element of the array)
for (i = len-sublen; i < len; i++)
{
brr[k] = arr[i];
k++;
}
//Right shift the elements so that they are now stored from the last element of the array
for (i = len - sublen - 1; i >= 0; i--)
{
arr[i + sublen] = arr[i];
}
//Now start adding the new array's elements to the original array (from the 0th index onwards) to get the final output
for (i = 0; i < sublen; i++)
{
arr[i] = brr[i];
}
//print the resultant array
for (i = 0; i < len; i++)
{
Console.Write(arr[i] + ",");
}
}
I was not sure if the interviewer was just trying to test my approach or if we really have a way to represent the unicode char set without using an array of size 95000. But if you folks know a way to use the unicode character set without using a large array of size 95000, please do let me know as well.
- Jeanclaude June 09, 2013I answered the question with below code and the interviewer was happy with the solution, he also said that using an array with arr[95000] as in the code below is not an efficient way. I was not sure how else can I accommodate a UNICODE character set? And he did not tell me what's an efficient way when the interview got over.
public void FirstNonRepeatedCharacter(string s)
{
int i;
int[] asc = new int[95000];
char[] ca = s.ToCharArray();
for (i = 0; i < ca.Length; i++)
{
asc[ca[i]] += 1;
}
for (i = 0; i < ca.Length; i++)
{
if (asc[ca[i]] == 1)
{
Console.WriteLine("first non repeating char is: " + ca[i]);
break;
}
}
}
- Jeanclaude June 09, 2013So, if n=2,3,4,5,6 ==> then temp = 5,11,21,36,57. Let me know if you folks see a formula here, it does not come to my head at this point :-).
- Jeanclaude June 04, 2013I initially thought it to be n^2 + (n-1), but later realized this does not look to have a generic formula at least to me... for e.g. if n=2, temp will be 5, if n=3, temp will be 11, the above formula only works for n=2 and 3, but if n=4, temp = 21 (n^2 + (n+1)) and if n=5, temp = 36. So this does not look to have a generic formula.. Correct me if I'm wrong.
- Jeanclaude June 04, 2013Thanks, i'm looking into those algorithms. I didn't assume there cant be better solution than mine :), it's just that I was not aware how we can do this with a linear solution.
- Jeanclaude May 18, 2013I was able to solve it with O(n^2), but not with O(n). Also I dont think we can do it in O(n). Correct me if I'm wrong. However the interviewer did not even tell me if there exists an O(n) solution, after the interview.
this was my code:
public bool issubstring(string main, string sub)
{
char[] m = main.ToCharArray();
char[] s = sub.ToCharArray();
int i=0, j=0, k;
bool issubstr = false;
for (i=0;i<m.Length;i++)
{
k=i;
for(j=0;j<s.Length;j++)
{
if(m[k] == s[j])
{
k++;
issubstr = true;
continue;
}
else
{
issubstr = false;
break;
}
}
}
if (issubstr == true)
return issubstr;
else
return issubstr;
}
yes, it could be done in linear.. O(n).
public void PairsOfArraySumsUpToGivenInteger(int[] arr, int sum)
{
int i = 0, j = i + 1;
while (i < arr.Length)
{
if (arr[i] + arr[j] == sum)
{
Console.WriteLine(arr[i] + "," + arr[j]);
j++;
}
else
j++;
if (j >= arr.Length)
{
i++;
if (i < arr.Length - 1)
j = i + 1;
else
break;
}
}
- Jeanclaude July 25, 2012this is not a binary tree.. it is a real tree/plant.
- Jeanclaude July 25, 2012Clarifying: This tree is a real tree and not a Binary tree.
- Jeanclaude July 25, 2012
- Jeanclaude July 26, 2016