Victor
BAN USERThere is a lot of ambiguity that needs further clarification. A few questions are below:
1. Is the system need to handle logs for multiple days?
2. If answer to #1 is yes, then, is it possible to have questions for multiple days?
3. If answer to #1 is no, then, can a user visit multiple pages in a day or same page multiple times by the same user?
4. Do we need to keep visited timestamps?
Here is my solution in C# assuming the tree is binary tree.
Regarding the max number of elements in stack at a time  height of the binary tree. Assuming the binary tree is balanced, it is log(n) where n is number if elements in the tree.
public static void InOrderWithoutStack(Node root)
{
if (root == null)
throw new ArgumentNullException("root");
Node temp = root;
Stack<Node> s = new Stack<Node>();
while (temp != null)
{
s.Push(temp);
temp = temp.Left;
}
while (s.Count != 0)
{
Node t = s.Pop();
System.Console.WriteLine(t.Value + " ");
if (t.Right != null)
{
t = t.Right;
while (t != null)
{
s.Push(t);
t = t.Left;
}
}
}
}

Victor
January 29, 2015 My solution in C#:
public class Matrix
{
public static int NumberOfCountries(int [,] a)
{
if (a == null  a.Length == 0)
{
return 0;
}
return CountCountries(a);
}
private static int CountCountries(int [,] a)
{
bool [,] b = new bool[a.GetLength(0), a.GetLength(1)];
int counter = 0;
for (int i = 0; i < a.GetLength(0); i++)
{
for (int j = 0; j < a.GetLength(1); j++)
{
if (a[i,j] != int.MinValue && !b[i,j])
{
Counter(a,b,i,j, a[i,j]);
counter++;
}
}
}
return counter;
}
private static void Counter(int[,]a, bool[,]b, int i, int j, int current)
{
if (i == a.GetLength(0)  i < 0  j == a.GetLength(1)  j < 0  a[i,j] != current)
return;
a[i,j] = int.MinValue;
b[i,j] = true;
Counter(a, b, i  1, j, current);
Counter(a, b, i, j  1, current);
Counter(a, b, i + 1, j, current);
Counter(a, b, i, j + 1, current);
}
}

Victor
January 29, 2015 Logic is simple. First reverse the sentence then reverse the words
void str_reverse(char* arr, int start, int end) {
for (;start < end; start++, end) {
char temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
void inplace_reverse(char* arr, int length) {
if (arr == NULL)
return;
if (length <= 0)
return;
str_reverse (arr, 0, length  1);
int start = 0;
int next = start;
for(; next < length; ) {
while(next < length && arr[next] != ' ') next++;
str_reverse(arr, start, next  1);
start = next + 1;
next = start;
}
}

Victor
January 21, 2015 Use breadth first traversal will work with an addition that after traversal at each depth, you will have to return to the next line. This you can do by keeping an identifier, like null node.
Here is the code:
public class BstLevelOrderTraversal
{
public static void Traverse(BinaryTreeNode root)
{
if (root == null)
{
throw new ArgumentNullException("root");
}
Queue<BinaryTreeNode> q = new Queue<BinaryTreeNode>(2);
q.Enqueue(root);
while (q.Count != 0)
{
q.Enqueue(BinaryTreeNode.GetNullNode());
while(!BinaryTreeNode.IsNullNode(q.Peek()))
{
BinaryTreeNode temp = q.Dequeue();
System.Console.Write(temp.Value + " ");
if (temp.Left != null)
q.Enqueue(temp.Left);
if (temp.Right != null)
q.Enqueue(temp.Right);
}
System.Console.WriteLine();
q.Dequeue();
}
q.Clear();
}
}

Victor
January 05, 2015 // Note that I have switched zeros and 1s
public class MatrixProblem {
/**
* Design an algo to decide if the GO game is over. i.e.
* Given a boolean matrix, write a code to find if an island of 1's is completely surrounded by 0's.
* @param a
* @return
*/
public static boolean IsGoGameOver(int [][] a)
{
if (a == null)
{
throw new RuntimeException("a");
}
if (a.length == 0  a[0].length == 0)
{
System.out.println("Array length is zero");
return false;
}
// The boolean 2D array is initialized to false
boolean [][]visited = new boolean[a.length][a[0].length];
for (int i = 0; i < a.length; i++)
{
for (int j = 0; j < a[0].length; j++)
{
if (a[i][j] == 1 && !visited[i][j])
{
if (IdentifyIsland(a, i, j, visited))
{
return true;
}
}
}
}
return false;
}
/**
* Actual logic to find if the island is surrounded with 0
* @param a
* @param row
* @param col
* @param visited
* @return
*/
private static boolean IdentifyIsland(int[][] a, int row, int col, boolean[][] visited)
{
// No checks will be performed since this is an private class.
visited[row][col] = true;
if (row == 0  row == a.length  1  col == 0  col == a[0].length  1) {
visited[row][col] = false;
return false;
}
boolean up = true;
boolean down = true;
boolean left = true;
boolean right = true;
if (a[row  1][col] == 1 && !visited[row  1][col]) up = IdentifyIsland (a, row  1, col, visited);
if (a[row][col + 1] == 1 && !visited[row][col+1]) right = IdentifyIsland (a, row, col + 1, visited);
if (a[row + 1][col] == 1 && !visited[row + 1][col]) down = IdentifyIsland (a, row + 1, col, visited);
if (a[row][col  1] == 1 && !visited[row][col  1]) left = IdentifyIsland (a, row, col  1, visited);
return up && right && down && left;
}
}

Victor
January 05, 2015 /// <summary>
/// Find if the element is present in the array.
/// Property of array is that each neighbor element is not more than 1 difference
/// </summary>
/// <param name="a">Array to be searched</param>
/// <param name="x">Element to be searched</param>
/// <returns>Returns the index of the element</returns>
public static int FindElement(int[] a, int x)
{
if (a == null  a.Length == 0)
{
throw new ArgumentNullException("a");
}
for (int i = 0; i < a.Length; )
{
int jump = 1;
if (x == a[i])
{
return i;
}
jump = Math.Abs(x  a[i]);
i += jump;
}
return 1;
}

Victor
December 31, 2014 My approach:
1. Create a binary search tree for the array with longer length where each node in the BST will have value and the index
2. For each element in the other array, search for the appropriate nodes based on greater or lesser needed, print all the nodes from the subtree.
Complexity: it is still quadratic. But it has potential of elements parsing to half for the larger array.
My code in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Test_Application
{
public class Node
{
public Tuple<char, int> Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
public class Program
{
private static List<Tuple<char, int, int>> list3 = new List<Tuple<char, int, int>>();
private static List<Tuple<char, int>> list2 = new List<Tuple<char, int>>();
static void Main(string[] args)
{
list3.Add(Tuple.Create<char, int, int>('a', 1, 7));
list3.Add(Tuple.Create<char, int, int>('b', 5, 12));
list3.Add(Tuple.Create<char, int, int>('c', 10, 11));
list3.Add(Tuple.Create<char, int, int>('d', 12, 16));
list3.Add(Tuple.Create<char, int, int>('e', 15, 24));
list3.Add(Tuple.Create<char, int, int>('f', 18, 19));
Node root = null;
foreach (Tuple<char, int, int> t3 in list3)
{
List<Tuple<char, int>> l = ConvertFrom2TupleTo3(t3);
foreach (Tuple<char, int> temp in l)
{
AddToBinaryTree(ref root, temp);
}
}
// Perform a in order traversal and print the tuples
TraverseAndPrint(root);
}
private static void TraverseAndPrint(Node root)
{
if (root == null)
{
return;
}
TraverseAndPrint(root.Left);
System.Console.Out.Write("{ " + root.Value.Item1 + ", " + root.Value.Item2 + " }");
TraverseAndPrint(root.Right);
}
private static List<Tuple<char, int>> ConvertFrom2TupleTo3(Tuple<char, int, int> t3)
{
if (t3 == null)
{
throw new ArgumentNullException("t3");
}
List<Tuple<char, int>> list = new List<Tuple<char, int>>();
list.Add(Tuple.Create<char, int>(t3.Item1, t3.Item2));
list.Add(Tuple.Create<char, int>(t3.Item1, t3.Item3));
return list;
}
public static void AddToBinaryTree(ref Node root, Tuple<char, int> element)
{
if (element == null)
{
throw new ArgumentNullException("element");
}
if (root == null)
{
root = new Node();
root.Value = element;
return;
}
Node temp = root;
Node current = root;
while (true)
{
bool isLeft = true;
if (element.Item2 < current.Value.Item2)
{
// Move to left
current = current.Left;
isLeft = true;
}
else
{
// Move to right
current = current.Right;
isLeft = false;
}
if (current == null)
{
// We need to add here
if (isLeft)
{
temp.Left = new Node();
temp.Left.Value = element;
}
else
{
temp.Right = new Node();
temp.Right.Value = element;
}
break;
}
temp = current;
}
}
}
}

Victor
October 09, 2014 Just a random thought, not yet tried to code:
If we consider this as bitwise numbers for the given example, the problem reduces to the following table:
Price : 5 4 8 12 14
Combo : 4 2 1 7 5
where Combo is of bits [BFC]
For example, if combo value is 5, meaning the price corresponds to B+C
Now suppose we are looking to minimize BF  that means we are looking for all the subsets with sum is atleast 6 and the answer would be minimum of the elements of all the subsets whose sum >= 6.
I would refrain from using string.split() operation and would ask from the interviewer first. Also, interviewer might ask what is the complexity of split operation  which we should be ready with the answer. Also, this uses additional space. Otherwise a good solution.
 Victor July 17, 2014Approach 1:
Let the words in the sentence be defined as w0, w1, ... , wn. Let prefix (LP) be defined as w0.
For each word wi in w1 ... wn {
LP = common_prefix(LP, wi)
if (LP.isEmpty())
return LP
}
return LP
==================================================
Now it all depends how we calculate common_prefix(). We can use trie to generate a structure once when LP is initialized and use the same data structure to find out the prefix. or we can use two pointers to get the common prefix strings each time in the function.
Approach 2:
This approach is slight modification of the approach 1.
Assuming that the words are delimited by space character, we will not find any words separately and then iterate over words. In fact, we will iterate over sentence and perform common_prefix() operation on the word within the string.
public static String findCommonSuffix(final String sentence) {
if (sentence == null) throw new NullPointerException("String is null");
if (sentence.length() == 0) return "";
// Initialize LP first
StringBuilder LP = new StringBuilder();
for (int i = 0; sentence.charAt(i) != ' '; i++) {
LP.append(sentence.charAt(i));
}
// Move the forward pointer to the next nonspace character
int next = LP.length();
while (next < sentence.length()) {
int s = next;
while (s < sentence.length() && sentence.charAt(s) == ' ') s++;
if (s == sentence.length()) return LP.toString();
StringBuilder temp = new StringBuilder();
for (int j = 0; j < LP.length() && s < sentence.length() && sentence.charAt(s) == LP.charAt(j); j++, s++) {
temp.append(LP.charAt(j));
}
LP = null;
LP = temp;
if (LP.length() == 0) return LP.toString();
if (s == sentence.length()) return LP.toString();
while (s < sentence.length() && sentence.charAt(s) != ' ') s++;
next = s;
}
return LP.toString();
}

Victor
July 17, 2014 public void replaceMarkWith0and1(String str) {
if (str == null) {
throw new NullPointerException("Parameter passed is null");
}
if (str.isEmpty()) {
System.out.println("String is empty");
return;
}
char[] carray = str.toCharArray();
printWithMark(carray, 0);
}
private void printWithMark(char[] str, int current) {
if (str == null) {
throw new NullPointerException("Parameter str is null");
}
if (current == str.length) {
System.out.println(new String(str));
return;
}
if (str[current] == '?') {
str[current] = '0';
printWithMark(str, current + 1);
str[current] = '1';
printWithMark(str, current + 1);
str[current] = '?';
} else {
current++;
printWithMark(str, current);
}
}

Victor
June 02, 2014 Simple mergesort is O(nlogn) but inplace. Anyways, here is what I could get:
1. Find the middle and end of the linked list. Now we have three pointers.
2. Repeat the step 1 (left, middle) and (middle,right) lists until two nodes are lef in each.
3. Merge at the time of return.
Basically the idea is to have all the nodes considered as independent with respect to the pointer which needs to be assigned and use the other one to parse the list.
I'll get the code for this but I hope the algorithm above would work.
I am not able to find any O(n) inplace solution. In java, there is a data structure sortedmap, that can be used to make the solution O(n). If anyone has a suggestion, I would love to know it. Also, I am assuming that all nodes hold unique values.
Asking again, did interviewer give any hint?
This seems like not an algo interview question. From shell perspective, a new variable is created if list is not present. Command "ls" is executed and output is stored in list. If the list is present, then the old value is overridden. I am not sure what system calls are made or file descriptors are created.
 Victor April 30, 2014Help me understand this logic. Let's assume that I have two arrays without duplicated: a = {0,2,4,7} and b={1,3,5,6} and i have to find k=4th smallest element. From visual inspection, the 4th smallest one is 3. Right? Based on your logic, in each array, i should start from 2nd index (which is 1) or index = 2? In my opinion, it should start from 2nd element meaning (k/21)th index.
 Victor February 22, 2014Open Chat in New Window
Actually, I made a mistake here as I assumed it was a tree. Since it is a graph, the error condition is that if all the neighbors of "a" current node are visited and the current node is not the end node, then return false. Meaning that there is a path that does not lead to end node.
 Victor January 05, 2019