siva
BAN USER 0of 0 votes
AnswersGiven an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141
 siva in United States for WF
Can we solve this in less than n square time?
n square algo is here
private bool isSwapNeeded(int i, int j)
{
int isum = i * (int)Math.Pow(10, NumberOfDigits(j)) + j;
int jsum = j * (int)Math.Pow(10, NumberOfDigits(i)) + i;
return isum > jsum;
}
private int NumberOfDigits(int i)
{
int noOfDigits = 0;
if (i == 0)
return 1;
while (i>0)
{
noOfDigits++;
i /= 10;
}
return noOfDigits;
}
public int[] MaximumConcatArray(int[] input)
{
int j;
for (int i = 1; i < input.Length; i++)
{
j = i;
while (j>=1 && isSwapNeeded(input[j],input[j1]))
{
input[j] = input[j] ^ input[j  1];
input[j1] = input[j] ^ input[j  1];
input[j] = input[j] ^ input[j  1];
j;
}
}
return input;
} Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm  0of 0 votes
AnswersWrite positive test cases to test this function
 siva in India for Bing
bool FileCopy(string source, string destination) Report Duplicate  Flag  PURGE
Microsoft Software Engineer in Test Testing  2of 2 votes
AnswersYou are at the center of n*n*n cube if n is odd and somewhere near center if n is even, print all possible paths to reach the surface of the cube
 siva in United States for Windows Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm  0of 0 votes
AnswersGiven an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141
 siva in United States Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm
As per my understanding I'm providing the below example for others to try out
Input:
singly linked list
1>2>3>4>5>6>7>8>9>10>11>12>13>14>15>16>17>18>19>20
and k = 5
Output:
1>2>3>4>5>10>9>8>7>6>15>14>13>12>11>20>19>18>17>16
Note: Take care of corner cases like n%k != 0 (n  number of nodes in LL) when you work out.
Sort both the arrays A1 and A2 separately using any sorting which guarantees nlogn time
Create an output array A3 of size A1.length+A2.length
Have 2 pointers at the end of each array, compare them (may be using ASCII) and copy the elements to the new array A3, decrement the pointer based on the comparison
sample comparison part:
if (A1[end1] > A2[end2])
{
A3[end3] = A1[end1];
end1;
}
else
{
A3[end3] = A2[end2];
end2;
}
end3;

siva
November 01, 2013 forgot to say, the time complexity is O(log n) for both push and pop.
The only problem I can think of using heap data structure (tree representation of an array) is the size. Array allocation is purely assumption as the input is a stream of numbers and we don't know the size. Array is not expandable, once it reaches full the only way to make room is allocating a bigger array and copying all the elements which adds up time and space complexity.
Did interviewer ask this question? and what is the answer?
Assuming you referred to Sieve of Eratosthenes (en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
It helps finding prime numbers and prints them in sorted order and not in lexicographic order (treating numbers as strings, for example 11 comes before 2)
Please let me know if you intended to describe some thing else.
@Rakesh  The data structure used for storing character occurrence counts depends on the range the characters in the input string.
If the input contains only alphanumeric then an array of constant size would suffice.
If the input contains wide range of characters then the hash table would save lot of memory.
It all depends on the assumptions which you take during the interview.
After lot of math and paper work here is the code in C# with inline comments
O(n) time and O(1) space complexity
public void PrintNumbersInDictionaryOrder(int N)
{
// straight forward
if (N < 9)
{
for (int i = 1; i <= N; i++)
{
Console.WriteLine(i);
}
return;
}
int startingDigit, multiplyingFactor, loopCount, max;
// dangerous code with lot of math :)
for (int index = 1; index <= 9; index++)
{
// prints single digit numbers
startingDigit = index;
Console.WriteLine(startingDigit);
// reset variables
multiplyingFactor = 1;
loopCount = 1;
while (startingDigit * 10 < N)
{
// 10, 100, 1000 and so on
// 20, 200, 2000 and so on
startingDigit = startingDigit * (int)Math.Pow(10, 1);
// 9, 99, 999, 9999 and so on
max = 9 * multiplyingFactor;
// max value depends on N
// for example, if N is 25 then max will become 5 instead of 9
// another example, if N is 256 then max will become 56 instead of 99
if (N  startingDigit < Math.Pow(10, loopCount))
{
max = N  startingDigit;
}
// prints 10  19, 100  199 and so on
for (int j = 0; j <= max; j++)
{
Console.WriteLine(startingDigit + j);
}
// 1, 11, 111, 1111 and so on
multiplyingFactor = (multiplyingFactor * 10) + 1;
loopCount++;
}
// corner case to print
// for example, if N = 10/100/1000 while loop fails to print the number
if (startingDigit * 10 == N)
{
Console.WriteLine(N);
}
}
}
The above code gives you just the idea and it can be refactored more to reduce some Math.
 siva October 04, 2013As I understand, the expected output is AABBCCCCBBAA for the input 'ABCD', but why the question talks about second and third iteration?
that will be a separate routine if 'ABC' is passed as input, the expected output is AABBBBAA
and same is with the third routine with the input as 'AB' and the expected output as AAAA
Why your thinking is restricted to 4 bit? and also the binary representation of 11 is 1011 and not 1111 which is for 15
n ranges from 0 to 10^9 (10 power 9) which is a 32 bit number and the number 4294967295 has 32 1's in it.
n2^k = 4294967295
so the problem here is to find the number 'k' for a given 'n' written on the board in order to reach 4294967295
lets think and find out...
It is easy if you follow my post in the given link, but it involves number to string conversion.
For the case you mentioned, frame a string like below and call it as pattern
"111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 99999999"
if single digit number
digits are not repeated
else
if pattern.contains(num.toString())
digits are repeated
else
digits are not repeated
test case:
11
22
33
111
222
333
1111
2222
3333
.
.
.
.
888888888 < 987654321 which is the biggest number with repeated digits
all these numbers when converted to string is a sub string in the pattern :)
Frame a string based on the input range 45 to 4578
"1111 2222 3333 4444 555 666 777 888 999"
this string contains all the possible repeated digits between 45 to 4578 starting from 55 to 4444
Convert the number to string say 45 > "45" then check if the above string contains this string
if yes, then it has repeating digits
foreach number in the range
convert the number to string
if pattern.contains(string)
repeated digits
else
no repeated digits
1. Have two pointers ptr1 and ptr2 pointing to head of linked list
2. Traverse one pointer say ptr2 to distance n from head
3. Now, traverse both
4. When ptr2 reaches the tail, ptr1 is at distance "n" from the tail of linked list
Need to do validation like
1. null check,
2. n might be greater than the length of linked list,
3. loop check and etc.,
void LevelOrderHelper(Node root)
{
if (root == null)
return;
int height = Height(root);
for (int i = height; i >= 1; i)
{
LevelOrderRecursive(root, i);
Console.WriteLine();
}
}
void LevelOrderRecursive(Node root, int level)
{
if (root == null)
return;
if (level == 1)
{
Console.Write(root.data);
}
else
{
LevelOrderRecursive(root.left, level  1);
LevelOrderRecursive(root.right, level  1);
}
}
int Height(Node root)
{
if (root == null)
{
return 0;
}
int leftHeight = Height(root.left);
int rightHeight = Height(root.right);
if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
static void Main()
{
TreeProblems t = new TreeProblems();
Node root = new Node(1);
Node level1Child1 = new Node(2);
Node level1Child2 = new Node(3);
Node level2Child1 = new Node(4);
Node level2Child2 = new Node(5);
Node level2Child3 = new Node(6);
Node level2Child4 = new Node(7);
root.left = level1Child1;
root.right = level1Child2;
level1Child1.left = level2Child1;
level1Child1.right = level2Child2;
level1Child2.left = level2Child3;
level1Child2.right = level2Child4;
t.LevelOrderHelper(root);
Console.ReadLine();
}
Implementation in C#, in place, O(n)
void Convert(char[] input)
{
if (input == null)
return;
int zeroCount = 0;
int oneCount = 0;
for (int i = 0; i < input.Length; i++)
{
if (input[i] == '0')
{
zeroCount++;
}
else if (input[i] == '1')
{
oneCount++;
}
else
{
throw new ApplicationException("invalid string format");
}
}
for (int i = 0; i < input.Length; i++)
{
if (zeroCount != 0)
{
input[i] = '0';
zeroCount;
}
else if (oneCount != 0)
{
input[i] = '1';
oneCount;
}
}
Console.WriteLine(new string(input));
}
By your post, I assume that there are variables in both the equations.
As per my knowledge, only way to solve this problem is to parse and find variables
What I meant by random numbers is
if you substitute x by 2 in equation (1) do the same in equation(2), by this way you can ensure that both the expressions are same only if they evaluates to same output.
Basic idea is to use expression tree to evaluate both the strings and then return true or false based on the output of both.
If the equations are something like "2x+3(y*z)" and "3x2y/(x^z)" think of replacing x, y and z in both the strings to some random number.
Note: validation is required before blindly replacing, because both the expressions can be completely different, one with a,b,c and other with x,y,z..
Life is easy when the expressions are just numbers and operators
@vinod  can you guess what is the condition for this step
"now traverse both upwards and they reach at LCA"
before this step both n1 and n2 are at equal distance from LCA
while (n1.data != n2.data)
{
n1 = n1.parent;
n2 = n2.parent;
}
will this not take care when one node is the child of other ?
public string largestPalindrome(string input)
{
int i, j, k, len = input.Length, maxLengthTillNow = 0;
string palindromeString = string.Empty;
for (i = 1; i < len; ++i)
{
// for even length palindrome
if (input[i  1] == input[i])
{
j = i  2;
k = i + 1;
//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j;
k++;
}
//compare with prev max
if (maxLengthTillNow < (k  j  1))
{
maxLengthTillNow = k  j  1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}
// for odd length palindrome
if ((i + 1 < len) && input[i  1] == input[i + 1])
{
j = i  2;
k = i + 2;
//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j; k++;
}
//compare with prev max
if (maxLengthTillNow < (k  j  1))
{
maxLengthTillNow = k  j  1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}
}
return palindromeString;
}
easy...same as linked list intersection problem.
traverse upwards from both the nodes using parent pointer and find the distance to the root
say d1 > d2
traverse n1 upwards, d1d2 times...by keeping n2 at same position
now traverse both upwards and they reach at LCA.
why not using min heap of size 3
parse the array, when ever the element in the array is greater than the root of min heap, replace the root with new element and run min heapify on root
at the end, root will contain the third largest number
this can also be modified to find kth largest element where k = 1 to n
How about writing extension methods for string type?
static class StringExtensions
{
public static string CustomConcat(this string s, string s2)
{
return string.Concat(s, s2).ToUpper();
}
}
static void Main(string[] args)
{
string s = "abc";
s = s.CustomConcat("def");
}
Open Chat in New Window
@saurabh  I thought of same idea...here is the implementation in C#
 siva January 12, 2014