DrFrag
BAN USERSreenivas, You are right. For the sake of clarity, the bug is
//BUG:
// input = { 1, 3, 5, 7, 9, -2, -4, -6, -8 };
// output = { 1, -2, 5, -4, 9, -6, 3, -8, 0, 7 } --- order of elements changes.
// expected output = {1, -2, 3, -4, 5, -6, 7, -8, 9}
The only way I can think of to insert an element in the correct position is by shifting other elements to the right.
eg: In first iteration of the example above,
elements of input array between and including index 1-4 will be shifted to index 2-5 and -2 will be inserted at index 1.
Anyone got a better solution?
There is atleast one problem with this solution.
The complexity is O(N^2). We must definitely try to improve on this by exploiting the sorted nature of the arrays.
Secondly,
A = { 1, 1 }
B = { 1, 1 }
produces, output = { 1, 1, 1, 1 }
which I personally think is not what is expected.
ooops...deleted my previous comment.
Here is what I wrote "Depends on the requirements.
If a = {1} and b = {1}
based on your logic, it may not be too intuitive that output should be {1,1} as both arrays consist of only one element. How can the output contain 2 elements that are common to both a, b?"
what extra array and how to remove it?
He means that out of all possible permutations of consecutive numbers beginning with 1 to N, find good ones where good ones are defined as the ones where x+1 does not occur after x.
eg: N = 3. Hence, input = {1,2,3} ie. {x, x+1, x+2}
Find all permutations of input and filter the good ones.
C# Solution:
Assuming that the caller will handle default values of the output array in case all its elements are not populated. Method may also return number of valid elements in output to make it convenient for the caller.
/*
* How to get common elements from two sorted arrays and you should not use any additional buffers.
* ex:- a[] = {1,1,3,4,6,9}
* b[] = {1,1,3,4,5,9}
* output[] = {1,1,3,4,9, 0}
*
* Three options:
* 1. I can return a larger than necessary output array along and hope that caller will deal with it.
* 2. Send larger than necessary array and the ending index "k" for convenience of the caller.
* 2. Copy the output array into a correctly sized array and return this new array. (extra buffer required.)
*
*
*/
public static int[] getCommonElements(int[] a, int[] b)
{
//size of output will definitely not be greater than smaller array.
int[] output = new int[Math.Min(a.Length, b.Length)];
int i, j, k = -1;
//Since arrays are sorted, we can compare elements of each array
//and increment indices based on equality of elements.
for(i = 0, j = 0; i <a.Length && j < b.Length; )
{
if (a[i] < b[j])
i++;
else if (b[j] < a[i])
j++;
else //if elements are equal
{
output[++k] = a[i];
i++;
j++;
}
}
return output;
}
C# Solution
Complexity: O(n2)
/* Algorithm:
* Compare each character with each succeeding characters.
* If there is a match, compare rest of the characters till they differ using an inner loop.
* If the length of the matched substring is greater than current max length, update max and other related values.
*
* Test Cases:
* abc
* abcab
* aaa
* abcdabcdab
* 123abcabc21
*/
public static void findLongestSubstring(string str){
if (str == null) throw new ArgumentException("String cannot be null");
int max = 0; //Length of longest substring.
int max_start = 0; //starting index of longest substring
int max_end = 0; //ending index of longest substring
int tempLen = 0;
int m, n;
for (int i = 0; i < str.Length - 1; i++){
for (int j = i+1; j < str.Length; j++){
if (str[i] == str[j]){ //if letters match, compare characters further.
for(m = i, n = j; m < str.Length && n < str.Length && str[m] == str[n]; m++, n++)
tempLen++; //increment as you keep counting length.
if (tempLen > max){ //if length of the substring is greater than current max len
max = tempLen; //update max
max_start = i; //update start and end indexes of this string.
max_end = i+max-1;
}
tempLen = 0; //for a fresh start in next iteration
}
}
}
Console.WriteLine("Max Length: {0}", max);
Console.WriteLine("Max Start: {0}", max_start);
Console.WriteLine("Max End: {0}", max_end);
}
C# Solution
/* Test Cases:
* (0,5) (2,4)
* (2,4) (0,5)
* (1,5) (3, 7)
* (7,9) (3,8)
* (0,3) (7,9)
* (0,5) (0,5)
*/
public struct range
{
internal int start;
internal int end;
}
public static void FindDifference(range a, range b)
{
//if B is contained in A
if (a.start <= b.start && b.end <= a.end)
{
for (int i = a.start; i <= a.end; i++)
{
if (i < b.start || i > b.end)
Console.Write(i + " ");
}
}
//if A is contained in B
else if ( b.start <= a.start && a.end <= b.end)
{
for (int i = b.start; i <= b.end; i++)
{
if (i < a.start || i > a.end)
Console.Write(i + " ");
}
}
//A is before B but they overlap
else if (a.start <= b.start && a.end >= b.start && a.end <= b.end)
{
for (int i = a.start; i < b.start; i++)
Console.Write(i + " ");
for (int i = a.end + 1; i <= b.end; i++)
Console.Write(i + " ");
}
//B is before A but they overlap
else if (b.start <= a.start && b.end >= a.end && b.end <= a.end)
{
for (int i = b.start; i < a.start; i++)
Console.Write(i + " ");
for (int i = b.end + 1; i <= a.end; i++)
Console.Write(i + " ");
}
//A and B are completely detached.
else
{
for (int i = a.start; i <= a.end; i++)
Console.Write(i + " ");
for (int i = b.start; i <= b.end; i++)
Console.Write(i + " ");
}
Console.WriteLine();
}
C# Solution
/* Problem: Print Fibonacci numbers between (n,m)
*
* Assumptions: m > n
*
* Algorithm:
* 1. Start calculating Fibonacci numbers from 0
* 2. If the number lies between desired range, print it.
*
* Complexity: O(N)
*
* Test cases:
* - (0, 1) => outputs 0,1,1. This falls between (0, 32)
* - (0, 32)
* - (5, 32)
*
* - (-1, 3) => fail
* - (32, 0) => fail
*/
public static void FindFibonacciNumbersInRange(int n, int m)
{
if (n < 0 || m < 0 || n >= m)
throw new ArgumentException("enter correct range");
int a = 0;
int b = 1;
//Print out the first two numbers if in range.
if (n == 0)
{
Console.WriteLine(a);
Console.WriteLine(b);
}
if (n == 1)
Console.WriteLine(b);
int c = a + b;
while (c <= m)
{
if (c >= n)
Console.WriteLine(c);
a = b;
b = c;
c = a + b;
}
}
C# Solution
/* Algorithm:
* For a maximum of (length of list)/2 iterations:
* 1. Maintain position of the element after which
* you want to insert the last element.
* 2. Move last element to the position above.
* 3. Update your marker from step 1 in preparation
* of insertion of the new last element.
*
* Complexity: O(N)
*
* Test Cases:
* - null
* - List of 1 element
* - List of 2 elements
* - List of 3 elements
* - Large list
*/
public static void OrderList(LinkedList<int> head)
{
//If the list is empty or has 1 element, return
if (head == null || head.First.Next == null)
return;
//Last element will be inserted after this position.
LinkedListNode<int> writePtr;
//Will assist in insertion operation.
LinkedListNode<int> temp;
//Find the middle of the list.
int mid = head.Count / 2;
//Move the last element
//to the starting position.
writePtr = head.Last;
head.RemoveLast();
head.AddFirst(writePtr);
//Move the pointer to the second element.
writePtr = head.First.Next;
for(int i = 1 ; i < mid; i++)
{
//remove from the end
temp = head.Last;
head.RemoveLast();
//add after required element.
head.AddAfter(writePtr, temp);
//update the marker to point to the element
//after which you want to add the new last element.
writePtr = writePtr.Next.Next;
}
I took the liberty to add comments to your code to make it more readable. Unfortunately, your approach will fail when there are more than 2 negative or positive numbers in a row. eg: int[] arr = { 1, 3, 5, 7, 9, -2, -4, -6, -8 };
- DrFrag October 15, 2013