CareerCup

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.

I don't understand how could counting sort work here. The link that you have shared talks about radix sort. I don't understand how radix sort would be a solution to the frequency item.

Is there any proper solution to the problem other than getting all products?

There 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;
                    }
                }
            }
        }

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);
    }
}

Not O(1) since you're splitting and storing the split results.

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;
        }
}

Yes, I'm certain that this works as expected.

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();
        }
    }

Assuming that there are no properties within the tag, which needs further discussion, usually it is represented as a tree data structure - like json.

// 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;
	}
}

/// <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;
        }

Yeah, max heap is a solution but as mentioned in the question, all operations should be O(1).
I think the interviewer wanted a discussion to see if was possible.

I like the thought in solution proposed. But scaling that will by a stupid attempt as with each addition, we are possibly creating another thread/processor performing possible reorganization in parallel.

Consider the following sequence:
Add 100 --> add 200 --> Add 150 --> remove 200
At the end, the stack will only have 100, but the max is 150. Next max call will return 100 not 150. Hence keeping a stack won't help.

@0xF4: After further scruitiny, I know why are you saying so. I agree, the solution is quadratic. The only optimization is that, for some, it is possible to not parse half of them.

@0xF4, if the tree is self balancing, then the complexity will be what I have mentioned.

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.

This is an open ended question. There will be more clarity on what is the error information in the runtime error. Could be typecasting, lazy loading or multithreading issue until there is further clarity.

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;
            }
        }
    }
}

Boyce Moore algo would also work

Why would it do in linear time? I don't think so because your second loop, which is implicit one is where s is being reset to zero.

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.

Can you please explain a little bit in details?

Variation of subset sum problem. I will post the code soon.

Can someone please explain if there is any specific algorithms for the question?

This question is form of bin-packing algorithm. Will post the solution soon.

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.

Approach 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 non-space 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();
    }

You haven't backtracked. Will it work?

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);
        }
    }

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?

@Saurabh: I can't think of an inplace and order-n solution to this problem. Did interviewer give any hint?

Connected components solution should work here.

I haven't yet understood the approach. Can you please use an example to demonstrate the usage of your approach? This will be helpful!

Create a BST. Traverse the tree. If difference between parent and child is 1, increment the count. Also, keep the count of number of times the element is appeared so that the count can be incremented appropriately.

The answer is subject to the type of vending machine. It seems like more or less system design question.

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.

None of the solutions above are handling circular nature of the linked list.
Nitin, can you please explain what will be the output of the circular nature? Should it remain circular or not? If yes, will the start node of the circle remain the same?

Why do we need priority queue?

For 3, I don't think keeping a bitmap is wise as there could be thousands of element with most of repetitions.

For the solution without hashtable, what if the elements are duplicate in the arrays? And how does that solution becomes nlogn? I could not get it.

Or

int rand7() {
	int rand5 = rand(5);
	return rand5 + (rand5 % 2);
  }

rand(5) + rand(5)%2

I guess LRU is the solution....

Can you please explain what is expected when two strings are given, I mean what kind of comparison is expected?

Help 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/2-1)th index.

BBBCCCAAAAUUUAAABBBDEF will be converted to B3C3A4U3A3B3DEF. Is this correct assumption?