Today we discuss a coding problem.
Question: Given a series of numbers from 1 to pow (2, n) on a paper, we fold it in the following way  with the help of two commands
L : Fold the paper from left edge to right edge
R : Fold the paper from right edge to left edge
For n = 1 we have numbers 1,2
These can be folded in two ways L & R
L makes the number 1 come on top of 2
R makes the number 2 come on top of 1
And a sequence of alternating L and R.
After n number of commands there will be a number in each layer
We have to print it from top to bottom as
{1,2} in this case.
Solution Note that folding only involves left and right commands
And this is repeated for log N steps
If we maintain a list for each index, folding causes elements to be added onto each index from another index.
In each step these lists on either side of the center come closer until there is only one.
With a data structure as a list of list for current and previous iterations,
We can iterate for log N steps and merge according to whether the command is left or right

// partial code
List<int> Fold(List<int> numbers>)
{
string command = "L";
var curr = new List<List<int>> ();

for (int i = 0; i < numbers.Length; i++)
{
      curr.append (new List<int>(){ numbers[i]});
}

For (int i = 0; i < curr.length/2; i++)
{
       if (command == "L")
       {
            for (k = 0; k < curr.length / 2; k++)
                Merge(ref curr, k, length-1-k);
            LeftShift(curr, curr.length/2);
       }
       else
       {
            for (k=0; k < curr.lenght / 2; k++)
                Merge(ref curr, length-1-k, k)
            RightShift(curr, curr.length/2);
       }
}
return curr[0];
}

void Merge(ref List<List<int>> curr, int src, int dest)
{
// source will have its list reversed and pushed at the front of the list on destination
// source list will be set to null
}
LeftShift and RightShift will trim the left and right null lists.

Another question along similar lines is that there are two arrays given and we can sort all the elements of array A in the order of B. Then the remaining elements of A can be sorted in that order.

Question : Given an array where each element is maximum +-k index away from its sorted position, find an algorithm to sort such array. 

Solution : We will assume n = number of elements in array is greater than k.  

 

One solution is to use InsertionSort. It will benefit from the property of the given array because it won't have to traverse the entire length of the array in the worst case. 

The Insertion sort goes like this :  

for int i = 1 to len(A) -1 

   j = i 

   while( j > 0 and A[j-1] > A[j]) 

       swap(A[j] and A[j-1]) 

       j = j - 1 

 

 

Another algorithm cited online was to use a heap of size 2K. As the elements fill up, we could take the minimum and output it. This does not affect the input array.  

However this will not work because the heapsize has to be all the elements of the array for this kind of sorting to work because the choice of the first 2k elements does not guarantee that the successor of the next element will be found  

 

 

Question: Given a string left rotate it by a given number of times. 

Answer: Let us first write it down as it is described. 

void Rotate(Stringbuilder b, int n) 

while (n) 

  char c = b.removeAt(0) 

  b.append(c) 

  n-- 

return b; 

Next the optimal solution would be to split the string at the index and swap the two partitions 

 

Question: Given a number between 0 to 1000, raise 11 to that number and determine the count of times '1' appears in the result. 

Answer: Generate the Pascal numbers with levels upto and inclusive of that number. Then for each number appearing at that level test and count the number of ones. 

 

Question: given a string of characters x and o where x and o are interspersed, find the cheapest way to group all the x together. Each movement of a letter is expensive. 

Answer: we can find the weighted average of the index by taking a weight of 1 for all x and a weight of 0 for all o. Then we can shift all the x’s closer together to this index. 

Question Write SQL to calculate the number of work days  between two dates
Answer:
SELECT (DATEDIFF(dd, @StartDate, @EndDate)+1) - (DATEDIFF(wk,@StartDate,@EndDate)*2)
-(CASE WHEN DATENAME(dw, @StartDate) = 'Sunday' THEN 1 ELSE 0 END)
-(CASE WHEN DATENAME(dw, @EndDate)='Saturday' THEN 1 ELSE 0 END)

 
Question: Design a file search utility
Answer: A depth first traversal with escape for current and parent folder notations.