Capgemini Interview Question Senior Software Development Engineers
Team: Chetu
Country: India
Interview Type: Written Test
The first mistake was assuming there was valid question in there. Forget the mistake about C#.
Don't read too much into it dude. Just found something, figured the intention of the question and attempted it.
Keep pushing the element in stack while reading.
While writing pop from the stack and write it. After every 3rd element take a new line.
Using a stack would use extra space. Why waste the space when it can be avoided and the problem can be in the same time.
There will always be a trade-off between memory and time. The reason i suggested stack is because it looked straight forward and even the interviewer might wanted to test the knowledge of Datastructure. With stack time & memory both are O(n)
On second thoughts, it would be more impressive to come up with your stack solution first and then to point out there was a way the same time could be achieved inplace (O(1) space) and that if 'n' was huge you'd prefer the latter.
Are you sure you will go for latter if n would have been huge ??? Just check the time complexity. O(m*n) whereas memory would always be O(n).
I posted the code below. Its simple in-place swapping. It would save me O(m*n) space when either m or n are large.
Also, the stack solution gives you O(2*m*n). Although 2 is too small and is ignored for large values. You will ultimately end up spending more time.
As per the assumption of this answer ....If we are sure that each line has size 3, than there will be no need to use extra space ....here is algo:
for(int i =0; i < 3; i++){
for(int i =0; i < 3; i++){
swap(a[i][j], a[2 - i][2 - j]);
}
}
But i dont think that in real business scenarios we have such kind of privileges .. :)
@bossAjeet, bail this thread man.
This similar to each and everyone proving some different statement on the premise of a contradiction.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Akatsuki
{
class Program
{
class MessageStack
{
private Stack<char> charStack;
public void PrintMessage()
{
char c;
while (charStack.Count > 0)
{
c = charStack.Pop();
Console.Write(c);
}
}
public void AddMessage(string Message)
{
var x = Message.ToCharArray();
charStack.Push('\n');
for (int i = 0; i < x.Length; i++)
{
charStack.Push(x[i]);
}
}
public MessageStack()
{
charStack = new Stack<char>();
}
}
static void Main(string[] args)
{
var msg = new MessageStack();
msg.AddMessage("XWV");
msg.AddMessage("UTS");
msg.AddMessage("RQP");
msg.PrintMessage();
}
}
}
This looks like rotating a matrix 180. Here`s a version that rotates a NxN matrix in place:
static void rotateMatrix180(char[][] matrix) {
int layers = matrix.length >> 1;
int layer;
for (layer = 0; layer < layers; ++layer) {
for (int j = layer; j < matrix.length - layer; ++j) {
char temp = matrix[layer][j];
int oppRow = matrix.length - 1 - layer;
int oppCol = matrix.length - 1 - j;
matrix[layer][j] = matrix[oppRow][oppCol];
matrix[oppRow][oppCol] = temp;
if (j > layer && j < matrix.length - 1 - layer) {
temp = matrix[j][layer];
matrix[j][layer] = matrix[oppCol][oppRow];
matrix[oppCol][oppRow] = temp;
}
}
}
}
May I ask what's the purpose for this:
if (j > layer && j < matrix.length - 1 - layer)
{
temp = matrix[j][layer];
matrix[j][layer] = matrix[oppCol][oppRow];
matrix[oppCol][oppRow] = temp;
}
The elements are swapped in place with only one temp variable. The matrix is swapped in frames where a frame is the most current outter first row ->last column ->last row -> last column. Since you start from the complete matrix and remove inverted frames one by one the size decreases by one.
Because in this case we do a 180 that if check that makes sure that when rotating the column we rotatae everything but the first and last elements in the column which were rotated with the row otherwise they'll be swapped back to their original positions.
public class WarZone {
public static void main(String a[]){
String str = "XWV UTS RQP";
System.out.println(str);
String[] arr = str.split(" ");
for(int i=arr.length-1; i>=0; i--)
{
String[] arr1 = null;
for(int j=arr[i].length()-1; j>=0; j--) {
System.out.print(arr[i].charAt(j));
}
System.out.print(" ");
}
}
}
I think ,THIS WORKS..ALGORITHM:
1)Do reverse of each row..like the following for this
i/p:
XWV
UTS
RQP
o/p:
VWX
STU
PQR
2)Do swap the first and last row only..keep the middle one as it as..
so the desired output is..
i/p:
VWX
STU
PQR
o/p:
PQR
STU
VWX i thnk ths is gonna works..wait fr code..i m thnking,,,,,,
A straight forward solution in O(m*n) time and O(1) space :
public void modifyArray(char[][] inputArray) { if(inputArray == null) return; int maxRow = inputArray.length-1; int maxColumn = inputArray[0].length-1; int iIndex1= 0; int jIndex1 = 0; int iIndex2= maxRow; int jIndex2 = maxColumn; while(iIndex1<=iIndex2) { jIndex1 = 0; jIndex2 = maxColumn; while(jIndex1<=maxRow) { if(iIndex1 == iIndex2 && jIndex1 == jIndex2) return; swap(inputArray,iIndex1,jIndex1,iIndex2,jIndex2); jIndex1++; jIndex2--; } iIndex1++; iIndex2--; } } private void swap(char[][] inputArray, int iIndex1, int jIndex1, int iIndex2, int jIndex2) { char temp = inputArray[iIndex2][jIndex2]; inputArray[iIndex2][jIndex2] = inputArray[iIndex1][jIndex1]; inputArray[iIndex1][jIndex1] = temp; }This solution would work for any (m*n) 2-d char array.
- teli.vaibhav October 28, 2013