codealtecdown
BAN USER 4of 4 votes
AnswersWrite a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0.
 codealtecdown in United States
Constraints:
Space complexity should be O(1)
Time complexity  Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones.
Edit:
Recursion is not allowed since it is O(n) space on stack Report Duplicate  Flag  PURGE
Microsoft Software Engineer Algorithm
if we want to count duplicate char as two different characters we will need number of strings * 26 matrix
 First pass fill the matrix Nx26 with each row containing frequency of char for that position
 Next, traverse the matrix and add min in each column and return the addition
static void Permute(char[] input, int l)
{
if (l == (input.Length  1))
Console.WriteLine(new string(input));
else
for (int i = l; i < input.Length; i++)
{
Swap(input, l, i);
Permute(input, l + 1);
Swap(input, l, i);
}
}

codealtecdown
October 13, 2015 According to the question description, the root pointer is not given, only two employees are given. If there is no mistake in the question then the solution might be different.
 codealtecdown October 11, 2015Iterative one
private static Node GetClosestNodeToX(Node root, int x)
{
Node result = null;
int min = Int32.MaxValue;
while (root != null)
{
int currMin = Math.Abs(root.data  x);
if (currMin == 0)
return root;
if (min > currMin)
{
result = root;
min = currMin;
}
if (x < root.data)
root = root.left;
else if (x > root.data)
root = root.right;
}
return result;
}

codealtecdown
October 03, 2015 c# implementation using Dictionary. Please check and comment.
using System;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
Node root1 = new Node(5);
root1.left = new Node(1);
root1.right = new Node(6);
root1.left.left = new Node(5);
root1.left.right = new Node(4);
root1.right.left = new Node(3);
root1.right.right = new Node(6);
Node root2 = new Node(1);
root2.left = new Node(3);
root2.right = new Node(4);
root2.left.left = new Node(6);
root2.left.right = new Node(5);
if(HaveSameData(root1,root2))
Console.WriteLine("Same Data");
else
Console.WriteLine("Not same Data");
}
static bool HaveSameData(Node root1, Node root2)
{
Dictionary<int,bool> map = new Dictionary<int,bool>();
Traverse(root1, map);
if(!TraverseAndCheck(root2, map))
return false;
foreach(KeyValuePair<int,bool> item in map)
{
if(!item.Value)
return false;
}
return true;
}
static void Traverse(Node root, Dictionary<int,bool> map)
{
if(root == null)
return;
Traverse(root.left, map);
if(map.ContainsKey(root.data))
map[root.data] = false;
else
map.Add(root.data, false);
Traverse(root.right, map);
}
static bool TraverseAndCheck(Node root, Dictionary<int,bool> map)
{
if(root == null)
return true;
if(map.ContainsKey(root.data))
map[root.data] = true;
else
return false;
return TraverseAndCheck(root.right, map) && TraverseAndCheck(root.left, map);
}
}
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int d)
{
data = d;
}
}

codealtecdown
October 02, 2015 For the extension, along with identifying if it is a opening or closing parenthesis, you would need to identify its pair. for example if you figured out that it's a closing ']' you would need to find its pair in terms of opening '['. So to do it in O(1) time, you would need to keep another map which has closingopening pair. Isn't it?
 codealtecdown October 02, 2015can you give some more information on your approach
are you suggesting to use disjoint set? will it not be O(n) space?
We can use Heap Sort. It has O(nlogn) time and O(1) space.
 codealtecdown September 24, 2015static bool IsBST(Node root, int low, int high)
{
if (root == null)
return true;
if (root.data < low  root.data > high)
return false;
return IsBST(root.left, low, root.data1) && IsBST(root.right, root.data+1, high);
}

codealtecdown
September 24, 2015 I think solution suggested by technoapurva will work in all cases. Can you give an example where it will not work?
 codealtecdown September 23, 2015good solution.
 codealtecdown September 23, 2015@Hari Krishna
I don't get your point. If one element is 0, why would the entire matrix be only zeros? Only that row and column should be 0.
recursion is not allowed. its O(n) on stack
 codealtecdown September 22, 2015Iterative solution. ReversePairs is inside LinkedList class, so head is class level variable.
public void ReversePairs()
{
if(head == null  head.next == null)
return;
Node curr = head, prev=null;
head = curr.next;
while (curr != null && curr.next != null)
{
Node next = curr.next;
curr.next = next.next;
next.next = curr;
if (prev != null)
prev.next = next;
if (curr.next != null)
curr = curr.next;
prev = next.next;
}
}

codealtecdown
September 19, 2015 static bool IsPalindromeOnlyChars(string input)
{
int i = 0, j = input.Length  1;
input = input.ToLower();
while (i < j)
{
while (!(('a' <= input[i] && input[i] <= 'z')))
i++;
while (!(('a' <= input[j] && input[j] <= 'z')))
j;
if (input[i] != input[j])
return false;
i++;
j;
}
return true;
}

codealtecdown
September 19, 2015 Heap solution will be O(n log N) where n is array size and N is top N elements.
If the topN operation needs to be performed frequently, sorting would be better rather than spending O(n log N). Fetching top N from sorted array would be O(N).
time complexity is O(min(n,m)) isnt it?
 codealtecdown September 19, 2015It might be a good idea to keep len(a) and len(b) in a variable then calculating every loop, small improvement
 codealtecdown September 19, 2015sorry for the typo in the second step above.
2. Traverse arr from left to right, and find a digit which is less than max2
Considering following arr & rep
arr={3,1,4,5,6}
rep={1,9,5,2,3}
and assumption that output should be
res={9,1,4,5,6}
Approach:
1. Find the maximum number from rep, max2
2. Traverse arr from right to left, and find a digit which is less than max2
3. If found, replace and return arr
4. If not found, replace the last digit(right most) of arr with max2. Assumption here is that we have to replace one element even if it is bringing down the number
Comments plz!!!
Two approaches I can think:
1) O(1) space  Sort the array and traverse the array and count distinct elements. time O(nlogn)
2) O(n) space  use hashtable, traverse the array and put each element in hashtable if not present, count while doing that. time  O(n)
Can someone think of a solution with O(n) time and O(1) space?
The interviewer was pretty sure that it is possible.
 codealtecdown September 19, 2015Infact I was too confused. Trying to solve the problem considering the BST and wondering how to use the BST property.
If it is plain binary tree,
we can use two stack and do level order traversal with swapping stacks.
private static void ReArrangeAlternte(int[] input)
{
int n = input.Length;
for (int i = 1; i < n / 2; i++)
{
int start = n / 2  i;
int end = n / 2 + i;
for (int j = start; j < end; j += 2)
{
int tmp = input[j];
input[j] = input[j + 1];
input[j + 1] = tmp;
}
}
}

codealtecdown
September 17, 2015 sorry it will be O(n*m)
 codealtecdown September 16, 2015It is finding kth rank in the n*m matrix, where k = (n+m)/2
Is that correct?
time complexity O(n+m)
this can be done using backtracking
using System;
using System.Collections;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
char[,] charArray = new char[,] {{'a', 'b', 'c', 'd', 'e'},
{'f', 't', 'i', 'g', 'h'},
{'f', 'm', 'i', 'c', 'j'},
{'k', 'o', 'l', 'r', 'm'},
{'n', 's', 'o', 'p', 'q'}
};
Console.WriteLine(IsWordPresent(charArray, "microsoft"));
}
private static bool IsWordPresent(char[,] matrix, string target)
{
List<Point> points = new List<Point>();
string curr = target.Substring(0, 1);
for (int i = 0; i < matrix.GetLength(0); i++)
{
for (int j = 0; j < matrix.GetLength(1); j++)
{
if (matrix[i, j] == target[0])
{
points.Add(new Point(i, j));
}
}
}
bool result = false;
foreach (Point p in points)
result = IsWordPresentUtil(matrix, target, p, 1, curr);
return result;
}
private static bool IsWordPresentUtil(char[,] matrix, string target, Point p, int index, string curr)
{
if (curr == target)
return true;
if (index >= target.Length)
return false;
foreach (Point point in GetPoints(p, matrix.GetLength(0)))
{
if (matrix[point.x, point.y] == target[index])
{
curr += target[index];
if (IsWordPresentUtil(matrix, target, point, index + 1, curr))
return true;
curr = curr.Remove(curr.Length  1, 1);
}
}
return false;
}
private static List<Point> GetPoints(Point p, int n)
{
int[] xvalues = new int[] { 1, 1, 1, 0, 0, 1, 1, 1 };
int[] yvalues = new int[] { 1, 0, 1, 1, 1, 1, 0, 1 };
List<Point> result = new List<Point>();
for (int i = 0; i < 8; i++)
{
int x = p.x + xvalues[i];
int y = p.y + yvalues[i];
if (x < n && x >= 0 && y < n && y >= 0)
{
result.Add(new Point(x, y));
}
}
return result;
}
}

codealtecdown
September 12, 2015 how about this? Isn't this simple? Am I missing something?
private static int FindNth(int[] arr1, int[] arr2, int n)
{
int i = 0, j = 0, c = 2, target = 0;
while (c < n)
{
if (arr1[i] < arr2[j])
{
i++;
target = i;
}
else
{
j++;
target = j;
}
c++;
}
return arr2[target];
}

codealtecdown
September 12, 2015 private static int RowWithMaxOne(int[,] input)
{
int maxRow = input.GetLength(0);
int maxCol = input.GetLength(1);
int row = 0;
int col = maxCol  1;
int result = 0;
while (row < maxRow && col >= 0)
{
if (input[row, col] == 1)
{
col;
result = row;
}
else
row++;
}
return result;
}

codealtecdown
September 12, 2015 private static int ConvertToInt(string input)
{
int result = 0;
int d = 1;
for(int i=input.Length 1 ; i>=0; i)
{
result += (input[i]  '0') * d;
d = d * 10;
}
return result;
}

codealtecdown
September 12, 2015 private static int PassingMarkInLessTime(int[] marks, int[] time, int p)
{
int n = marks.Length;
int[,] temp = new int[n + 1, p + 1];
int minVal = Int32.MaxValue;
int sumSoFar = 0;
for (int i = 0; i <= n; i++)
{
if (i != 0)
sumSoFar += marks[i  1];
for (int j = 0; j <= p; j++)
{
if (i == 0  j == 0)
{
temp[i, j] = 0;
continue;
}
if (j <= sumSoFar)
{
if (j < marks[i  1])
{
temp[i, j] = temp[i  1, j];
}
else
{
int v1 = temp[i  1, j] == 0 ? Int32.MaxValue : temp[i  1, j];
temp[i, j] = Math.Min(v1, time[i  1] + temp[i  1, j  marks[i  1]]);
}
minVal = temp[i, j];
}
else
{
temp[i, j] = 0;
continue;
}
}
}
return minVal;
}

codealtecdown
September 11, 2015 can you give the pointers to solutions for the rectangle problem?
 codealtecdown September 11, 2015Questions to ask:
Does an array contains duplicate?
Does an array contain negative?
Can we afford O(n) auxiliary space to boost performance?
Approaches:
Use hashtable  Time O(n) and Space O(n)
static void PrintSumNPairs(int[] input, int sum)
{
Dictionary<int, int> map = new Dictionary<int, int>();
foreach (int i in input)
map.Add(i, 1);
foreach (int j in input)
{
if (j != sum j && map.ContainsKey(sum  j))
{
Console.WriteLine("Pair found  " + j + ", " + (sum  j));
map.Remove(j);
map.Remove(sum  j);
}
}
}
Approach 2:
Sort O(nlogn)
Traverse from front and back in  O(n2)
total time O(n2) space O(1)
you need to multiply 0.4, 0.3, 0.3 to get probability, not sum
 codealtecdown September 06, 2015If we use Hashtable, we can achieve O(n) complexity. Am I correct?
Traversal needs to be changed to refer/populate Hashtable.
It doesn't matter. Calculate 6 distances. As told in the first answer
 codealtecdown September 06, 2015Square/Rectangle need not be parallel to x/y axis.
 codealtecdown September 06, 2015This seems correct.
Distance between two points P1(x,y), P2(x,y)
D(P1,P2) = SQRT( Sqr(P1.xP2.x) + Sqr(P1.yP2.y))
Isn't this simple
Traverse first string. Take a pointer to second string. When char pointed in the second string equals current char in first string, increment pointer. do this until string one is fully traversed and pointer reaches string 2 end
This can be done using Disjoint Set.
1. For each vertex v, call MakeSet(v)
2. For each edge vertices, u & v, UnionSet(u, v). Modify UnionSet to return parent, if parent is a new one, increment count
3. Count has number of connected components
public void ReverseNFromFrontToNFromBack(int n)
{
Node p0 = null, p1 = null, p2 = head, p3 = head;
while (n > 1)
{
p0 = p3;
p3 = p3.next;
n;
}
p1 = p3;
while (p3.next != null)
{
p2 = p2.next;
p3 = p3.next;
}
//now p1 & p2 points to start and end of sublist which needs to be reversed
ReverseMiddle(p0, p1, p2);
}
private void ReverseMiddle(Node prev, Node curr, Node next)
{
Node head = prev;
Node b = curr;
Node last = next.next;
while(curr != last)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
b.next = last;
head.next = prev;
}

codealtecdown
September 06, 2015 private static void SpiralTraversal(Node root)
{
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
stack1.Push(root);
while (stack1.Count != 0  stack2.Count != 0)
{
while (stack1.Count > 0)
{
Node curr = stack1.Pop();
if (curr.left != null)
stack2.Push(curr.left);
if (curr.right != null)
stack2.Push(curr.right);
Console.Write(curr.data + " ");
}
Console.WriteLine();
while (stack2.Count > 0)
{
Node curr = stack2.Pop();
if (curr.right != null)
stack1.Push(curr.right);
if (curr.left != null)
stack1.Push(curr.left);
Console.Write(curr.data + " ");
}
Console.WriteLine();
}
}

codealtecdown
August 25, 2015 it can't be this easy buddy. no extra space plz. in place plz.
 codealtecdown August 23, 2015public static int MinDishes(int[,] pdm)
{
Data count = new Data();
count.count = Int32.MaxValue;
List<int> hungry = new List<int>();
int[] dishes = new int[pdm.GetLength(1)];
for (int i = 0; i < pdm.GetLength(0); i++)
{
hungry.Add(i);
}
for (int i = 0; i < pdm.GetLength(1); i++)
{
dishes[i] = 0;
}
MinDishes(pdm, pdm.GetLength(0), pdm.GetLength(1), 0, hungry, dishes, ref count);
return count.count;
}
private static bool MinDishes(int[,] pdm, int n, int k, int person, List<int> hungry, int[] dishes, ref Data count)
{
if (hungry.Count == 0)
return true;
for (int p = person; p < n; p++)
{
for (int d = 0; d < k; d++)
{
if (pdm[p, d] == 1)
{
if (hungry.Contains(p))
hungry.Remove(p);
dishes[d]++;
if (MinDishes(pdm, n, k, p + 1, hungry, dishes, ref count))
{
if (count.count > dishes.Count(i => i > 0))
count.count = dishes.Count(i => i > 0);
}
if (!hungry.Contains(p))
hungry.Add(p);
dishes[d];
}
else
continue;
}
}
return false;
}

codealtecdown
August 23, 2015 C# version
static void PrintSumPath(BinarySearchTree<int>.Node root, int k, List<int> list)
{
if (root == null  root.data > k)
return;
list.Add(root.data);
if (root.data == k)
{
PrintList(list);
}
PrintSumPath(root.left, k  root.data, list);
PrintSumPath(root.right, k  root.data, list);
list.Remove(root.data);
PrintSumPath(root.left, k, list);
PrintSumPath(root.right, k, list);
}
private static void PrintList(List<int> list)
{
foreach (int i in list)
Console.Write(i + " ");
Console.WriteLine();
}

codealtecdown
August 01, 2015 static string DigitToRoman(int n, int d)
{
string[,] map = new string[3, 3] { { "I", "V", "X" }, { "X", "L", "C" }, { "C", "D", "M" } };
string result="";
if (d <= 2)
{
switch (n)
{
case 0:
result = "";
break;
case 1:
result = map[d, 0];
break;
case 2:
result = map[d, 0] + map[d, 0];
break;
case 3:
result = map[d, 0] + map[d, 0] + map[d, 0];
break;
case 4:
result = map[d, 0] + map[d, 1];
break;
case 5:
result = map[d, 1];
break;
case 6:
result = map[d, 1] + map[d, 0];
break;
case 7:
result = map[d, 1] + map[d, 0] + map[d, 0];
break;
case 8:
result = map[d, 1] + map[d, 0] + map[d, 0] + map[d, 0];
break;
case 9:
result = map[d, 0] + map[d, 2];
break;
}
}
else if (d == 3 && n < 5)
{
while (n >= 0)
{
result += "M";
}
}
else
{
return "Error! Can't convert numbers larger than 4999.";
}
return result;
}
static string ConvertToRoman(int num)
{
int d = 0;
string result = "";
while (num > 0)
{
int n = num % 10;
result = DigitToRoman(n, d) + result;
d++;
num = num / 10;
}
return result;
}

codealtecdown
July 28, 2015 One pointer to keep track of one empty number which is not assigned. getNumber will just return the number in the the pointer and make sure that there is another number ready when it is needed. Both will take O(1)
Keep HashSet with int as value. requestNumber  O(1) to check if value contains, and O(1) to add if not there. At each requestNumber call, make sure that there is one empty element present in the HashSet which is not assigned. This will take another O(1) in case the item needs to be added in HashSet and modify the current pointer.
RData class to pass index and random number
public class RData<T>
{
public int index;
public T randomData;
public RData()
{
index = 0;
}
public RData(int i, T r)
{
index = i;
randomData =r;
}
}

codealtecdown
July 20, 2015
 codealtecdown October 29, 2015