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);
}
}
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;
}
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;
}
}
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 closing-opening 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.data-1) && IsBST(root.right, root.data+1, high);
}
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;
}
}
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;
}
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, 2015In-fact 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;
}
}
}
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;
}
}
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];
}
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;
}
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;
}
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;
}
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.x-P2.x) + Sqr(P1.y-P2.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 sub-list 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;
}
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();
}
}
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;
}
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();
}
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;
}
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.
if(n>0 && n&(n-1) ==0)
return true
else
return false
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 October 29, 2015