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[j-1]))
{
input[j] = input[j] ^ input[j - 1];
input[j-1] = 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
Considering
1. negative numbers in both numerator and denominator
2. divide by zero
public double Divide(double numerator, double denominator)
{
bool negativeResult = false;
double temp = 1.0;
if (denominator == 0)
{
throw new Exception("Divide by zero error");
}
else if (numerator == 0)
{
return 0;
}
else if (numerator < 0 && denominator < 0)
{
numerator *= -1;
denominator *= -1;
}
else if (numerator < 0 && denominator >= 1)
{
numerator *= -1;
negativeResult = true;
}
else if (numerator >= 1 && denominator < 0)
{
denominator *= -1;
negativeResult = true;
}
if (numerator < denominator)
{
numerator *= 10;
temp = 0.1 * Divide(numerator, denominator);
numerator = denominator;
}
return (negativeResult ? -1 : 1) * (temp + Divide(numerator - denominator, denominator));
}
public double Divide(double numerator, double denominator)
{
double temp = 1.0;
if (numerator == 0)
return 0;
if (numerator < denominator)
{
numerator *= 10;
temp = 0.1 * Divide(numerator, denominator);
numerator = denominator;
}
return temp + Divide(numerator - denominator, denominator);
}
public List<string> FindWord(List<string> dictionary, string word)
{
List<string> output = new List<string>();
int[] charCount = new int[26];
char[] input = word.ToCharArray();
for (int i = 0; i < input.Length; i++)
{
charCount[input[i] - 'a']++;
}
int[] temp = new int[26];
foreach (string _word in dictionary)
{
if (Math.Abs(_word.Length - input.Length) == 1 || Math.Abs(_word.Length - input.Length) == 0)
{
charCount.CopyTo(temp, 0);
char[] _input = _word.ToCharArray();
for (int i = 0; i < _input.Length; i++)
{
temp[_input[i] - 'a']--;
}
int sum = 0;
for (int i = 0; i < temp.Length; i++)
{
sum += Math.Abs(temp[i]);
}
if (sum <= 2)
{
output.Add(_word);
}
}
}
return output;
}
Each and every digit as an array element
for example the number 1,23,45,67,89,12,34,56,789 can fit in array of size 18
another way is to have each and every digit as linked list node but in reverse direction to provide the increment and decrement operation on head which is the last digit of the number
9->8->7->6->5 and so on
ABC, when A is instantiated during declaration
BAC, when A is instantiated in C's constructor
class A
{
public A()
{
Console.Write("A");
}
}
class B
{
public B()
{
Console.Write("B");
}
}
class C : B
{
A a = new A();
// A a;
public C()
{
//a = new A();
Console.Write("C");
}
}
question from career cup book
public static void rotate(int[][] matrix, int n)
{
for (int layer = 0; layer < n / 2; ++layer)
{
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; ++i)
{
int offset = i - first;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[last - offset][first];
// bottom -> left
matrix[last - offset][first] = matrix[last][last - offset];
// right -> bottom
matrix[last][last - offset] = matrix[i][last];
// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}
In place compression, I did not append the count to the character if it exists only once
public char[] InPlaceCompress(string input)
{
char[] inputInChar = input.ToCharArray();
if (inputInChar.Length == 0)
return null;
char prevCharacter = inputInChar[0];
int count = 1;
int changeIndex = 0;
for (int i = 1; i < inputInChar.Length; i++)
{
if (prevCharacter == inputInChar[i])
{
count++;
}
else
{
inputInChar[changeIndex] = prevCharacter;
changeIndex++;
if (count > 1)
{
char[] countAsChars = count.ToString().ToCharArray();
for (int j = 0; j < countAsChars.Length; j++)
{
inputInChar[changeIndex] = countAsChars[j];
changeIndex++;
}
count = 1;
}
prevCharacter = inputInChar[i];
}
}
inputInChar[changeIndex] = prevCharacter;
changeIndex++;
if (count > 1)
{
char[] countAsChars = count.ToString().ToCharArray();
for (int j = 0; j < countAsChars.Length; j++)
{
inputInChar[changeIndex] = countAsChars[j];
changeIndex++;
}
}
for (int k = changeIndex; k < inputInChar.Length; k++)
{
inputInChar[k] = '\0';
}
return inputInChar;
}
tested with some inputs
input: abbbbbbbbbbbbbbbbbbbbbbbbbbccccddddd
output: ab26c4d5
input: aaaaaabbbbbccccd
output: a6b5c4d
input: abcd
output: abcd
following checks should be done before proceeding
null check on list
N <= 0, throw custom exception
N == 1, we need to delete all the nodes
Circular check using Floyd's cycle detection method or any other method
if not circular, its easy
int count = 0;
while (current != null)
{
count++;
if (count % n == 0)
{
current.prev.next = current.next;
if (current.next != null)
current.next.prev = current.prev;
}
current = current.next;
}
or we need to find the start of the loop and check for it when we iterate through the list and delete
simple, let the input be 1,4,3,2,4
4 is repeated, 5 is missing, let repeated number be x1 and missing number be x2
arithmetic progression
n(n+1)/2 - x2 + x1 = summation of all the numbers
5(5+1)/2 - x2 + x1 = 14
15 - x2 + x1 = 14
x2-x1 = 1 -------> equation 1
find the product
(n! * x1)/x2 = product of all the numbers
((1*2*3*4*5) * x1) / x2 = 1*2*3*4*4
(120 * x1) / x2 = 96
120 * x1 = 96 * x2
x1 = (96 * x2) / 120 -------------> equation 2
substitute x1 in equation 1
x2 - ((96*x2) / 120) = 1
120 * x2 - 96 * x2 = 120
24 * x2 = 120
x2 = 5
substitute x2 in equation 1
5 - x1 = 1
x1 = 4
hence proved :-)
Binary search is the right way, matrix is not sorted row wise as you can check the question
011
111
000
sorted column wise --->
but not row wise
|
|
v
so we need to count no of 1's in first row using binary search and keep track of row number and 1's count, then move to the next row and perform the same, at the end you will have 1's count for all the rows, print all the rows which has max 1's which should be closer or equal to n (column length)
Input is in sorted order
- siva November 21, 2012As per my knowledge, in binary search we do compare first element, middle element and last element.
So if they are same then we can have special case to find it in O(1)
What do you say?