CareerCup

Solution using a map to keep track the previous segments:
Runtime: O(n) and O(n) space.

bool check_sum_subarray(const std::vector<int> V, int N) {
    std::unordered_map<int, int> map_sum_to_index;
    std::vector<int> sum(V.size());

    int acc = 0;

    for (int i = 0; i < V.size(); i++) {
        acc += V[i];
        if (acc == N) return true;

        
        if (map_sum_to_index.find(acc - N) != map_sum_to_index.end()) {
            return true;
        }

        map_sum_to_index[acc] = i;
    }
    
    return false;
}

Basically, this is the same problem of longest path in a binary tree but considering the required directions in the path string:

package problems;

import problems.auxiliar.BinaryTreeFactory;
import problems.auxiliar.BinaryTreeNode;

/**
 * Created by fsantos on 3/7/17.
 */
public class Prob175 {
    public static <T extends Comparable<T>> String longestPath(BinaryTreeNode<T> root, String steps) {
        return longestPath(root, steps, 0, "");
    }

    private static <T extends Comparable<T>> String longestPath(BinaryTreeNode<T> node, String steps, int step, String path) {
        if (node == null) {
            return path.substring(0, path.length() - 1);
        }

        char chr = '?';
        if (step < steps.length())
            chr = steps.charAt(step);

        String pathLeft = null;
        String pathRight = null;

        switch(chr) {
            case 'L':
                pathLeft = longestPath(node.left, steps, step + 1, path + "L");
                break;
            case 'R':
                pathRight = longestPath(node.right, steps, step + 1, path + "R");
                break;
            case '?':
                pathLeft = longestPath(node.left, steps, step + 1, path + "L");
                pathRight = longestPath(node.right, steps, step + 1, path + "R");
                break;
        }

        if (pathLeft != null && pathRight != null)
            return pathLeft.length() > pathRight.length() ? pathLeft : pathRight;
        else if (pathLeft != null) return pathLeft;
        else return pathRight;
    }

    public static void main(String[] args) {
        BinaryTreeNode<Integer> root = BinaryTreeFactory.makeBinaryTree();
        String longestPath = longestPath(root, "?");
        System.out.println(longestPath);
    }
}

Tree used in the test:

1
                      2        3
                   4   5
                          6

Output:

LRR

This is my solution passing only once in the array (string whatever) but using a queue to control de first unique:

package problems;

import java.util.*;

/**
 * Created by fsantos on 2/10/17.
 */
public class Prob153 {
    public static void findFirstUnique(int[] arr) {
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, Integer> freqMap = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            Integer c = freqMap.get(arr[i]);
            if (c == null) {
                freqMap.put(arr[i], 1);
                queue.add(arr[i]);
            } else {
                freqMap.put(arr[i], c + 1);

                if (queue.peek() == arr[i])
                    queue.remove();
            }
        }

        boolean found = false;

        while (!queue.isEmpty()) {
            Integer x = queue.remove();
            Integer c = freqMap.get(x);

            if (c == 1 && !found) {
                System.out.println(x);
                // Guarantee to purge to queue
                found = true;
            }
        }
    }

    public static void main(String[] args) {
        findFirstUnique(new int[] {1, 2, 3, 1});
    }
}

Output:

2

Don't provide public methods that will change your object.
In case of modification, return a new instance.
Prefer to declare your variables as final.
Process everything needed in the constructor.

Example:

public class DoTheMath {
	private int x;
	private int z;

	public DoTheMath(int N) {
		calculate(N);
	}

	private void calculate(int N) {
		// code code code
	}

	public int getX() {
		return this.x;
	}

	public int getZ() {
		return this.z;
	}
}

Now I am a little bit happier with the code. It is using additional space to do 2 steps of merge but the code is clean:

package problems;

import java.util.*;

/**
 * Created by fsantos on 2/9/17.
 */
public class Prob149 {
    public static void mergeUsingAdditionalSpace(List<String> l1, List<String> l2, List<String> l3) {
        List<String> l4 = merge(l1, l2);
        List<String> l5 = merge(l4, l3);

        for (String s: l5)
            System.out.println(s);
    }

    private static List<String> merge(List<String> l1, List<String> l2) {
        List<String> t = new ArrayList<>();
        int i1 = 0;
        int i2 = 0;

        while (i1 < l1.size() && i2 < l2.size()) {
            int cmp = l1.get(i1).compareTo(l2.get(i2));
            if (cmp == 0) {
                t.add(l1.get(i1));
                i1++;
                i2++;
            } else if (cmp < 0) {
                t.add(l1.get(i1++));
            } else {
                t.add(l2.get(i2++));
            }
        }

        if (i2 < l2.size()) {
            i1 = i2;
            l1 = l2;
        }

        while (i1 < l1.size())
            t.add(l1.get(i1++));

        return t;
    }

    public static void main(String[] args) {
        mergeUsingAdditionalSpace(Arrays.asList("aaa", "bbb", "ddd", "xyxz"),
                Arrays.asList("bbb", "ccc", "ccc", "hkp"),
                Arrays.asList("ddd", "eee", "ffff", "lmn"));
    }
}

Output:

aaa
bbb
ccc
ccc
ddd
eee
ffff
hkp
lmn
xyxz

Very trick question to code. I am not very happy because of many conditional checks...

package problems;

import java.util.*;

/**
 * Created by fsantos on 2/9/17.
 */
public class Prob149 {
    public static void merge(List<String> l1, List<String> l2, List<String> l3) {
        int i1 = 0;
        int i2 = 0;
        int i3 = 0;

        while (i1 < l1.size() && i2 < l2.size() && i3 < l3.size()) {
            if (l1.get(i1).compareTo(l2.get(i2)) < 0) {
                // l1 < l2
                if (l1.get(i1).compareTo(l3.get(i3)) < 0) {
                    // l1 < l3
                    System.out.println(l1.get(i1));

                    if (l2.get(i2).compareTo(l1.get(i1)) == 0) i2++;
                    if (l3.get(i3).compareTo(l1.get(i1)) == 0) i3++;

                    i1++;
                } else {
                    // l3 < l1
                    System.out.println(l3.get(i3));

                    if (l1.get(i1).compareTo(l3.get(i3)) == 0) i1++;
                    if (l2.get(i2).compareTo(l3.get(i3)) == 0) i2++;

                    i3++;
                }
            } else {
                // l2 < l1
                if (l2.get(i2).compareTo(l3.get(i3)) < 0) {
                    // l2 < l3
                    System.out.println(l2.get(i2));

                    if (l1.get(i1).compareTo(l2.get(i2)) == 0) i1++;
                    if (l3.get(i3).compareTo(l2.get(i2)) == 0) i3++;

                    i2++;
                } else {
                    // l3 < l2
                    System.out.println(l3.get(i3));

                    if (l1.get(i1).compareTo(l3.get(i3)) == 0) i1++;
                    if (l2.get(i2).compareTo(l3.get(i3)) == 0) i2++;

                    i3++;
                }
            }
        }

        if (i3 < l3.size()) {
            if (i1 > l1.size()) {
                i1 = i2;
                l1 = l2;
            } else {
                i2 = i3;
                l2 = l3;
            }
        }

        while (i1 < l1.size() && i2 < l2.size()) {
            if (l1.get(i1).compareTo(l2.get(i2)) < 0) {
                System.out.println(l1.get(i1));

                if (l2.get(i2).compareTo(l1.get(i1)) == 0) i2++;

                i1++;
            } else {
                System.out.println(l2.get(i2));

                if (l2.get(i2).compareTo(l1.get(i1)) == 0) i2++;

                i2++;
            }
        }

        if (i2 < l2.size()) {
            i1 = i2;
            l1 = l2;
        }

        while (i1 < l1.size()) {
            System.out.println(l1.get(i1++));
        }
    }

    public static void main(String[] args) {
        merge(Arrays.asList("aaa", "bbb", "ddd", "xyxz"),
                Arrays.asList("bbb", "ccc", "ccc", "hkp"),
                Arrays.asList("ddd", "eee", "ffff", "lmn"));
    }
}

Output:

aaa
bbb
ccc
ccc
ddd
eee
ffff
hkp
lmn
xyxz

To transmit something, you have to create a way to identify the streaming begin/end.
Having the encoding type is good too. So, Something like HTTP would be interesting.

Client -> Server
GET /\r\n
Accepted-Content-Type: gziped, text\r\n
\r\n\r\n

Server -> Client
Content-Type: gziped\r\n
Content-Length: xxx\r\n
[..] GZIP CONTENT [..] (xxx bytes long)
\r\n\r\n

cat file | awk -F"," '{print $(NF-1)}'

Output:

$ cat file.txt | awk -F"," '{print $(NF-1)}'
e
3
y

I am thinking in a solution using sum arrays.
So, in linear time, I could create the arrays/subarrays containing the accumulative sum.
What do you think about this idea guys?
Thanks

Simple solution using dfs(dfs())

public class Prob139 {
    public static class Res {
        private List<List<BinaryTreeNode<Integer>>> listOfPaths = new ArrayList<>();
        public Res() {

        }

        public void addList(List<BinaryTreeNode<Integer>> path) {
            listOfPaths.add(path);
        }

        public void printPaths() {
            for (List<BinaryTreeNode<Integer>> l: listOfPaths) {
                System.out.print("PATH: ");
                for (BinaryTreeNode<Integer> n: l) {
                    System.out.print(n.value + ", ");
                }
                System.out.println();
            }
        }
    }

    public static void simpleFindSumUpToK(BinaryTreeNode<Integer> node, int K) {
        if (node == null)
            return;

        Res res = new Res();
        List<BinaryTreeNode<Integer>> path = new ArrayList<>();
        dfs(node, K, 0, path, res);
        res.printPaths();

        simpleFindSumUpToK(node.left, K);
        simpleFindSumUpToK(node.right, K);
    }

    private static void dfs(BinaryTreeNode<Integer> node, int K, int sum, List<BinaryTreeNode<Integer>> path, Res res) {
        if (node == null)
            return;

        path.add(node);
        sum += node.value;

        if (sum == K) {
            res.addList(path);
            return;
        }

        List<BinaryTreeNode<Integer>> pathToLeft = new ArrayList<>(path);
        List<BinaryTreeNode<Integer>> pathToRight = new ArrayList<>(path);

        dfs(node.left, K, sum, pathToLeft, res);
        dfs(node.right, K, sum, pathToRight, res);
    }

    public static void main(String[] args) {
        BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1);
        root.left = new BinaryTreeNode<>(1);
        root.right = new BinaryTreeNode<>(2);
        root.left.right = new BinaryTreeNode<>(1);

        simpleFindSumUpToK(root, 3);
    }
}

Output:

PATH: 1, 1, 1, 
PATH: 1, 2,

The trick here is to save the value in case where the data is different and consider on hasNext().

public static class ResultIterator <E extends Comparable<E>> {
        private Iterator<E> itr1;
        private Iterator<E> itr2;
        private E savedNext = null;

        ResultIterator(Iterator<E> itr1, Iterator<E> itr2) {
            this.itr1 = itr1;
            this.itr2 = itr2;
        }

        public boolean hasNext() {
            return itr1.hasNext() || itr2.hasNext() || savedNext != null;
        }

        public E next() {
            if (savedNext != null) {
                E ret = savedNext;
                savedNext = null;
                return ret;
            }

            if (itr1.hasNext() && itr2.hasNext()) {
                E nextItr1 = itr1.next();
                E nextItr2 = itr2.next();
                int cmp = nextItr1.compareTo(nextItr2);

                if (cmp == 0) {
                    return nextItr1;
                } else if (cmp > 0) {
                    savedNext = nextItr1;
                    return nextItr2;
                } else {
                    savedNext = nextItr2;
                    return nextItr1;
                }
            }

            if (itr1.hasNext()) {
                return itr1.next();
            }
            return itr2.next();
        }
    }

I am using a map to count the frequency. Then, I iterate thru string2 decreasing the frequency for the present characters.

Example:

felipe
f -> 1
e -> 2
l -> 1
i -> 1
p -> 1

felipa
f -> 0
e -> 1
l -> 0
i -> 0
p -> 0
a -> -1

If the string2 is smaller (in length) than string1, I consider all differences in frequency map greater than 0. Else, I consider negative differences.

Following the C++ 11 code:

#include <iostream>
#include <string>
#include <unordered_map>
#include <cstdlib>

int custom_string_compare(const std::string& s1, const std::string& s2) {
    std::unordered_map<char, int> freq;

    for (int i = 0; i < s1.length(); i++)
        freq[s1[i]]++;


    for (int i = 0; i < s2.length(); i++)
        freq[s2[i]]--;

    int diff = 0;
    
    if (s2.length() < s1.length()) {
        for (auto it: freq) {
            if (it.second > 0)
                diff += it.second;
        }
    } else {
        for (auto it: freq) {
            if (it.second < 0)
                diff += std::abs(it.second);
        }
    }
    
    return diff;
}

bool string_difference_validation(int max_diff,
                                  const std::string& s1
                                  const std::string& s2) {
    int diff = custom_string_compare(s1, s2);
    return diff == max_diff;
}

#include <iostream>
#include <vector>

/*
 * Output:
 * 6, 4
 * FelipeCerqueira, dosSantos
 */

template<typename T>
std::vector<T> acc(std::vector<T>& V, int n) {
    int len = V.size() / n;

    if (V.size() % n != 0)
	len++;

    std::vector<T> R(len);

    int c = 0;
    for (int i = 0; i < V.size(); i++) {
	if (i > 0 && i % n == 0) 
	    c++;

	R[c] += V[i];
    }
    
    return R;
}

template<typename T>
void test(std::vector<T>& V, int n) {
    auto R = acc(V, n);

    for (auto it = R.begin(); it != R.end(); it++) {
	if (it != R.begin()) std::cout << ", ";
	std::cout << *it;
    }
    std::cout << std::endl;
}

int main(void) {
    std::vector<int> V1 {3, 3, 3, 1};
    std::vector<std::string> V2 {"Felipe", "Cerqueira", "dos", "Santos"};

    test(V1, 2);
    test(V2, 2);

    return 0;
}

Yes.
But my solution is solving the problem and would be very easy to recreate the binary tree.

Longest common prefix means both need to start at the same point.
Am I wrong?

private static String commonPrefix(String s1, String s2) {
		StringBuilder sb = new StringBuilder();
		int min = Math.min(s1.length(), s2.length());
		
		for (int i = 0; i < min; i++) {
			if (s1.charAt(i) != s2.charAt(i))
				break;
				
			sb.append(s1.charAt(i));
		}
		
		return sb.toString();
	}

You have to store the binary tree just using the same format of a heap.
It is, an array where the left and right nodes are positioned at idx * 2 and idx * 2 + 1.

Following a code to serialize a binary Tree. Limitations: Its fills the array with zeros for nulled nodes.

Example:

/*
       10
11          12
                     14

arr[] = 10, 12, 11, 0, 0, 0, 14 
*/

public static final class SerializeBinaryTreeCustom {
        private int[] arr = new int[1];

        public SerializeBinaryTreeCustom(Node root) {
            dfs(root, 0);
        }

        private void dfs(Node node, int idx) {
            if (node == null) return;
            if (arr.length <= idx)
                arr = Arrays.copyOf(arr, idx + 1);

            arr[idx] = node.value;
            dfs(node.left, (idx * 2) + 1);
            dfs(node.right, (idx * 2) + 2);
        }

        public int[] arr() {
            return arr;
        }
    }

The method removeLast should me renamed to removeFirst or removeOlder to be better.

Use a LinkedListHashMap to keep a list of keys ordered by insertion.
Every time you reach the limit (10 in this case), you remove the first inserted key (older one)

public static final class BoundedLinkedListHashMap<Key, Value> {
        private LinkedHashMap<Key, Value> map = new LinkedHashMap<>();
        private int N;

        public BoundedLinkedListHashMap(int N) {
            this.N = N;
        }

        public synchronized void put(Key k, Value v) {
            map.put(k, v);

            if (map.keySet().size() > N) {
                removeLast();
            }
        }

        public synchronized Value get(Key k) {
            return map.get(k);
        }

        private void removeLast() {
            map.remove(map.keySet().iterator().next());
        }
    }

If you have to solve with two queues, you will need a max and min Queue.
After inserting, you will need to exchange elements to keep both queues with the same number of elements as possible.

Use the mediam to determine where you should insert.

-- logmonitor.sh --
#!/bin/sh

tail -f logfile.txt | awk '{if ($3 > 30) {print $0}}'
-- eof --

Test:

echo "PNAME - 31 - Time"| awk '{if ($3 > 30) {print $0}}'

Follow my design to this problem:

Person
- Name
- Age

Teacher (Person)
- ID

Student (Person)
- Preference

Subject
- String description

Class
- Teacher
- Subject
- List of Student

. addStudent(Student)
. removeStudent(Student)

Preference
- SMS | TWITTER | FACEBOOK


Course (interface)
. addClass
. removeClass


OnlineCourse (Course)
- Map<Subject, Class> classBySubject;
- Map<Teacher, Class> classByTeacher;

. addClass
. removeClass

You can use the LinkedListHashSet.

You can use a doubly linked list with a fixed size of N.
InsertLast and RemoveFirst.

In the end, you'll have the last N lines.

What do you think to use a retrieval of sha1 hashs?
It would be a good approach to compact the data in memory and to perform fast comparisons.

The complexity would be N log L (Where L is the sha1 hash length).

PS: this solution is valid for N repeated lines.

Another interesting point: sha1 or md5 doest not require to read the whole line... so, it does not matter if the line can be stored in memory or not.

The cons about this solution against using a hashset is because a retrieval will compact the data (sha1 hashs).

Following is my solution in O(n):

/**
 * Created by sky on 5/11/15.
 */
public class DistributeChocolate {

    public static void main(String[] args) {
        int[] kids = new int[] {2, 6, 1, 2, 9, 1, 1, 4, 9, 6, 3, 5, 1};
        int[] choco = new int[kids.length];

        int saved = 1;
        for (int i = 0; i < kids.length; i++) {
            if (i == 0) {
                choco[i] = saved;
                continue;
            }

            if (kids[i] <= kids[i - 1]) {
                saved = 1;
                choco[i] = saved;
            } else {
                choco[i] = ++saved;
            }
        }

        for (int i = 0; i < choco.length; i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(choco[i]);
        }
        System.out.println();
    }
}

I am sorry. But the output is not correct.
A tree where node.right > node and node.left < node is a Binary Search Tree.
I understood from the problem that we dont have a BST. Is is a regular tree.
Where We can have arbitrary values everywhere.

So, from a regular tree, how do you print the elements in order?

As you can see, using an arbitrary tree, the output is not sorted:

14
12
17 > 12 (wrong)
10
7
9
6

Walking thru a BST in order is very easy:

dfs(node.left)
print value;
dfs(node.right);

But, this is not the case...

Hello Kaidul Islam,
I have tested your code but it did not work. Are you considering a BST?
I think this is not a BST, else, would be easy to do that...

Output from your algorithm developed in Java:

14
12
17
10
7
9
6

/**
 * Created by sky on 5/5/15 from Kaidul Islam algorithm
 */
public class RegularTreeInOrder {
    private static final class Node<T> {
        private T value;
        private Node<T> right;
        private Node<T> left;

        public Node(T value) {
            this.value = value;
        }
    }

    public static <T> void inorderWithConstantSpace(Node<T> root) {
        if (root == null)
            return;

        Node<T> current = root;

        while(current != null) {
            if(current.left != null) {
                Node<T> leftChild = current.left;
                Node<T> tmp = leftChild;
                Node<T> rightMost = null;

                while(leftChild != null) {
                    rightMost = leftChild;
                    leftChild = leftChild.right;
                }

                rightMost.right = current;
                current.left = null;
                current = tmp;
            } else {
                System.out.println(current.value);
                current = current.right;
            }
        }
    }

    public static void main(String[] args) {
        Node<Integer> root = new Node<>(10);
        root.right = new Node<>(9);
        root.right.right = new Node<>(6);
        root.right.left = new Node<>(7);

        root.left = new Node<>(12);
        root.left.right = new Node<>(17);
        root.left.left = new Node<>(14);

        inorderWithConstantSpace(root);
    }
}

Just fixing the past answer: Not Queue but Tree.

You are right. I though about flaging to avoid delete because I was thinking the cost to remove from a BST (where you should rebalance the Tree).
For a regular tree, you can remove in constant time.

So, traverse in O(n^2) and remove the sorted (printed) numbers.

It would required O(n) space. Sadly, I don't think it is a possibility.
What I am thinking is, there is a space limit but nothing was said about running time.
In N^2 you would be able to traverse the tree marking the printed node (smallest one) and then, repeating the process.

In the end, you should print the nodes in order.

O(1) space would be possible traversing the tree N times and marking the selected nodes.

I'm using a HashMap to create a frequency and a max PriorityQueue to maintain the N most frequent.
To insert and remove a register from PriorityQueue would be a long (N). IE: Log N of 5.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Created by sky on 21/04/15.
 */
public class MostFrequentWords {
    private static final class Counter {
        private String word;
        private int counter;

        public Counter(String word, int initial) {
            this.word = word;
            this.counter = initial;
        }

        public void increment() {
            counter++;
        }

        @Override
        public String toString() {
            return "[" + word + ", " + counter + "]";
        }
    }

    public static void main(String[] args) throws Exception {
        Reader in = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(in);

        Map<String, Counter> freq = new HashMap<>();

        int N = 1;


        PriorityQueue<Counter> priorityQueue = new PriorityQueue<>(N + 1, new Comparator<Counter>() {
            @Override
            public int compare(Counter o1, Counter o2) {
                return o1.counter - o2.counter;
            }
        });

        String line;
        while((line = br.readLine()) != null) {
            Counter counter = freq.get(line);

            if (counter == null) {
                counter = new Counter(line, 1);
                freq.put(line, counter);
                priorityQueue.add(counter);
            } else {
                counter.increment();
                priorityQueue.add(counter);
            }

            if (priorityQueue.size() > N)
                priorityQueue.remove();
        }

        br.close();
        in.close();

        while (!priorityQueue.isEmpty()) {
            Counter max = priorityQueue.remove();
            System.out.println(max);
        }

    }
}

I have created a solution with code clearance/quality in mind. So, I divided it into two methods that could be reused:

/**
 * Created by sky on 21/04/15.
 */
public class SumBinary {
    public static int binaryStringToInteger(String binary) {
        int a = 0;
        int mul = 1;

        for (int i = binary.length() - 1; i >= 0; i--) {
            Character chr = binary.charAt(i);
            int bit = chr == '1' ? 1 : 0;
            a += bit * mul;
            mul <<= 1;
        }
        return a;
    }

    public static String integerToBinaryString(int v) {
        int mask = 1;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 32; i++) {
            if ((v & mask) > 0) {
                sb.append('1');
            } else {
                sb.append('0');
            }

            mask <<= 1;
        }

        String bin = sb.reverse().toString();
        int idx = bin.indexOf('1');
        return bin.substring(idx);
    }

    public static String sumBinary(String binary1, String binary2) {
        int a = 0;
        int b = 0;
        a = binaryStringToInteger(binary1);
        b = binaryStringToInteger(binary2);

        int res = a + b;
        return integerToBinaryString(res);
    }

    public static void main(String[] args) {
        System.out.println(sumBinary("0111101", "1101"));
    }
}

My solution is: I am going to use a HashMap to keep a frequency (counter) and a LinkedHashSet to keep the characters ordered by its insertion.

Every time I detect a frequency = 2, I am going to remove from the LinkedHashSet.
In the end, just the characters presented once will remain sorted by insertion time.

import java.util.*;

/**
 * Created by sky on 4/19/15.
 */
public class FirstNonRepeatedCharacter {
    private static class Counter {
        private int counter;

        public Counter(int initial) {
            this.counter = initial;
        }

        public void increment() {
            this.counter++;
        }

        @Override
        public String toString() {
            return "[" + this.counter + "]";
        }
    }

    public static void main(String[] args) {
        String s = "abcdeabc";
        Map<Character, Counter> freq = new HashMap<>();
        Set<Character> nonRepeated = new LinkedHashSet<>();

        for (int i = 0; i  < s.length(); i++) {
            Character chr = s.charAt(i);
            Counter c = freq.get(chr);
            if (c != null) {
                c.increment();
                if (c.counter == 2) {
                    nonRepeated.remove(chr);
                }
            } else {
                freq.put(chr, new Counter(1));
                nonRepeated.add(chr);
            }
        }


        Iterator it = nonRepeated.iterator();
        if (it.hasNext())
            System.out.println("First non repeated: " + it.next());
    }
}

Stack memory is always limited.
That is the reason why some programs crash while calling recursive functions. (It uses stack).
The limit depends on your compiler.

Heap memory is limited by your system RAM + swap. For sure, allocating more memory than available will impact in a serious performance issue.

My solution in place and O(n) running time

/**
 * Created by sky on 16/04/15.
 */
public class InPlacePalindromeCheck {
    public static void main(String[] args) {
        String word = "A man, a plan, a canal, Panama";
        System.out.println(isPalindrome(word));
    }

    private static boolean isPalindrome(String word) {
        boolean ret = true;

        int i = 0;
        int j = word.length() -1;

        while (j > i) {
            if (!Character.isDigit(word.charAt(j))) {
                j--;
                continue;
            }

            if (!Character.isDigit(word.charAt(i))) {
                i++;
                continue;
            }

            if (word.charAt(i) != word.charAt(j)) {
                ret = false;
                break;
            }
            j--;
            i++;
        }

        return ret;
    }
}

My proposition requires O(n) space and O(n) running time:

/**
 * Created by sky on 16/04/15.
 */
public class FindLongestSequence {
    public static void main(String[] args) {
        //int[] arr = {1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6};
        int[] arr = {1, 2, 3, 1, 2, 3, 4};
        int[] tmp = new int[arr.length - 1];

        for (int i = 1; i < arr.length; i++) {
            tmp[i - 1] = arr[i] - arr[i - 1];
            System.out.print(tmp[i - 1] + " ");
        }
        System.out.println();

        int i = 0;
        int maxRepeated = 0;
        int repeated;
        int idx = 0;

        while (i < tmp.length) {
            int j = i + 1;

            repeated = 2;
            while (j < tmp.length && tmp[j] == tmp[i]) {
                j++;
                repeated++;
            }

            if (repeated > maxRepeated) {
                idx = i;
                maxRepeated = repeated;
            }

            i = j;
        }

        idx += 1;

        System.out.println(idx + " " + maxRepeated);

    }
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	private char[][] arr;
	
    public Ideone(char[][] in) 
    {
		arr = deepCopy(in);
    }

	private char[][] deepCopy(char[][] in)
	{
		char[][] out = new char[in.length][];
		for (int i = 0; i < in.length; i++) {
			out[i] = Arrays.copyOf(in[i], in[i].length);
		}
		return out;
	}
            
    private void printArr() 
    {
    	for (int i = 0; i < arr.length; i++) {
    		for (int l = 0; l < arr[i].length; l++)
    			System.out.print(arr[i][l] + " ");
    		System.out.println();
    	}	
    }        
    
    private void fill(int x, int y) 
    {
    	arr[x][y] = 'X';
    	
    	printArr();
    	
		if (y + 1 < arr[0].length && arr[x][y + 1] == '.')
			fill(x, y + 1);
		if (x + 1 < arr.length && arr[x + 1][y] == '.') 
			fill(x + 1, y);
		if (x > 0 && arr[x - 1][y] == '.')
			fill(x - 1, y);
		if (y > 0 && arr[x][y - 1] == '.')
			fill(x, y - 1);
			
		return;
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		char[][] in={
            {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', 'X', 'X', 'X', '.', '.', 'X', 'X', 'X', '.'},
            {'.', 'X', '.', 'X', 'X', 'X', 'X', '.', 'X', '.'},
            {'.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.'},
            {'.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.'},
            {'.', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'}};
            
        Ideone ide = new Ideone(in);
        ide.printArr();
		ide.fill(2, 2);
	}
}

Follow my answers bellow:

Which one of the following applies to multi-core system?
a. Multiple users can use the system at the same time

Answer: Correct. In a multiplrocessor system, you can do more then one task at the same time. In a single processor, it's not possible and what you have is a emulation due to schedule features.

b. The kernel can run in SMP mode

Answer: Yes. I mean, for working with multiple processor you need a SMP hardware (more then one CPU sharing the same main memory).

c. Multiple tasks can execute in parallel without the need for scheduling

Answer: False. Even executing in parallel, you need a scheduler.

d. semaphores and mutexes should be replaced with spinlock

Answer: False. Its a matter of implementation.
Spin lock is very similar then a mutex_try_acquire in a busy loop (to avoid loosing its CPU time).

O(n) solution using a set

#include <iostream>
#include <set>
#include <cmath>

int main() {
	int N = 91;
	std::set<long> cubics_set;

	// Generating all cubic values between 1 and N
	for(int i = 1; i < N; i++) {
		cubics_set.insert(std::pow(i, 3));
	}

	for(auto it = cubics_set.begin(); it != cubics_set.end(); ++it) {
		if(*it > N)
			break;

		long required = N - *it;

		if(cubics_set.find(required) != cubics_set.end())
			std::cout << "a:" << *it << " "
				  << "b:" << required << std::endl;

	}

	return 0;
}

Start iterating through the biggest array and inserting into a set.
After that, iterate thru the others first searching in the set for a repeated and inserting a non-exsisting into a set.
After that, all values found in set are commons.

911 is not a sequence... I didn't consider numbers changing size and I assume at least the first pair should be in a sequence.

O(N) Solution.

#include <iostream>
#include <string>

int find_number_length(std::string& s, size_t l=1) {
	std::string n1 = s.substr(0, l);
	std::string n2 = s.substr(l, l);
	
	int a = std::stoi(n1);
	int b = std::stoi(n2);

	if((b - a) == 1)
		return l;

	return find_number_length(s, l+1);
}

int find_missing(std::string& s, size_t l) {
	int a, b;
	     
	a = std::stoi(s.substr(0, l));
	for(int i = 1; i < s.length() / l; ++i) {
		b = std::stoi(s.substr(l * i, l));
		
		if((b - a) > 1) {
			// Found missing number
			return a + 1;
		}
		
		a = b;
	}

	return 0;
}

int main() {
	std::string s1{"960961962964"};
	std::string s2{"12345789"};

	std::cout <<  find_missing(s1, find_number_length(s1)) << std::endl;
	std::cout <<  find_missing(s2, find_number_length(s2)) << std::endl;

	return 0;
}

Very simple solution and works with unsorted array and arrays with different size.
Ah.. generic too. Could be applied for chars, strings and so on...

/*
  i have an array{{1,2,3},{4,5,6},{7,8,9}}.I want output=1,2,4,3,5,7,6,8,9  
 */

#include <iostream>
#include <vector>

template <typename T>
void print_specific_order(std::vector< std::vector<T> > & vec) {
	T saved;
	bool is_saved = false;
	for(auto v: vec) {
		for(int i = 0; i < v.size(); ++i) {
			if(i == v.size()-1) {
				saved = v[i];
				is_saved = true;
				continue;
			}

			std::cout << v[i] << std::endl;

			if(is_saved) {
				std::cout << saved << std::endl;
				is_saved = !is_saved;
			}
		}
	}

	std::cout << saved << std::endl;
}

int main() {
	std::vector< std::vector<int> > vec {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
	print_specific_order<int>(vec);
	return 0;
}

There are so many good solutions here but I want to share mine too ok?
Suggestions are always welcome.

#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <utility>

template <typename T>
struct node {
	node(T value) : value_{value}, right_{nullptr}, left_{nullptr} {}
	~node() { delete(right_); delete(left_); }
	T value_;
	node<T>* right_;
	node<T>* left_;
};

template <typename T>
void in_order_traversal(node<T>* nd) {
	if(nd == nullptr)
		return;

	in_order_traversal(nd->left_);
	in_order_traversal(nd->right_);
	std::cout << nd->value_ << std::endl;
}

int main() {
	std::vector<std::pair<int,int> > vec {{2,4}, {1,2}, {3,6}, {1,3}, {2,5}};
	std::map<int, node<int> *> nodesmap;
	node<int>* root = nullptr;
	
	for(auto p: vec) {
		std::map<int, node<int>*>::iterator itsrc;
		std::map<int, node<int>*>::iterator itdest;

		itsrc = nodesmap.find(p.first);
		itdest = nodesmap.find(p.second);
		
		node<int>* src = nullptr;
		node<int>* dest = nullptr;

		if(itsrc != nodesmap.end())
			src = itsrc->second;
		else
			src = new node<int>(p.first);
		
		if(itdest != nodesmap.end())
			dest = itdest->second;
		else
			dest = new node<int>(p.second);

		std::cout << "src:" << src->value_ << " "
			  << "dest:" << dest->value_ << std::endl;

		if(src->left_ == nullptr)
			src->left_ = dest;
		else
			src->right_ = dest;

		nodesmap.insert(std::pair<int, node<int>*>(p.first, src));
		nodesmap.insert(std::pair<int, node<int>*>(p.second, dest));
	}

	std::map<int, node<int>*>::iterator it = nodesmap.find(1);
	if(it != nodesmap.end()) {
			root = it->second;			
			in_order_traversal<int>(root);
	}
	return 0;
}

Basically, battery consumption and getting higher CPU temperature.

Using Sieve of Eratosthenes and bitset to save results

/*
  Sieve of Aristhoteles
  Prime numbers
*/

#include <iostream>
#include <bitset>

template <size_t N>
class prime_util {
public:
	prime_util();
	int get_smaller_bigger_prime(int x);

private:
	std::bitset<N> bset;
};

template <size_t N>
prime_util<N>::prime_util() {

	bset.set(0);
	bset.set(1);

	// Initialize the bitset with sieve of Aristoteles
	for(int i = 2; i < N; ++i) {
		if(bset.test(i))
			continue;

		for(int c = i + i; c < N; c += i) {
			bset.set(c);
		}
	}

}

template <size_t N>
int prime_util<N>::get_smaller_bigger_prime(int x) {
	if(x > N)
		return -1;

	for(int check = x; check < N; ++check)
		if(!bset.test(check))
			return check;

	return -1;
}

int main() {
        const int max = 20;
	prime_util<max> primeutil;
	std::cout << primeutil.get_smaller_bigger_prime(6) << std::endl;
	std::cout << primeutil.get_smaller_bigger_prime(7) << std::endl;
	return 0;
}

If a specific web server starts failing you could remove this one from load balancer connection pool until problem be fixed.
Using a cloud infrastructure, could be easy start a new server to replace that one with problem...

If you have a software problem happening in all servers. It could be a capacity problem and the solution could be adding new servers to the pool to reduce the load.

Solution in O(n):

Output:
3
1
1
2
2
1
4
9
3
2
9
1
sum(A)38
sum(B)20
sum(C)18

/* 
Problem:

Given an unsorted array, how to divide them into two equal arrays whose 
sum of difference is minimum. 
Can it be done in O(n)? 
*/

#include <iostream>
#include <vector>
#include <cstdlib>
#include <vector>
#include <algorithm>

void print_vector(const std::vector<int> &A) 
{
    for(auto it = A.cbegin(); it != A.cend(); ++it) {
		std::cout << *it << std::endl;
    }
}

int sum_of_elements(const std::vector<int>&A)
{
    int sum_of_elements = 0;
    for(int n: A) {
		sum_of_elements += n;
    }
    return sum_of_elements;
}

class Result {
public: 
    Result(int n) : vec(n), sum{0}, average{0} {
		it = vec.begin();
    }

    int check_sum(int value) {
		return sum + value;
    }

    bool is_value_greater_then_average(int value) {
		return value > average;
    }

    bool add(int value) {
		if(it == vec.end())
		    return false;
	
		*it = value;
		sum += value;
		++it;
	
		average += sum;
		if(vec.size() > 1)
		    average /= 2;
	
		return true;
    }

    int result() {
		return sum;
    }

private:
    std::vector<int> vec;
    std::vector<int>::iterator it;
    int sum;
    int average;
};

int main(int argc, char ** argv)
{
    //std::vector<int> A {1000, 1, 1, 1, 1, 1000};
    std::vector<int> A {3, 1, 1, 2, 2, 1, 4, 9, 3, 2, 9, 1};
    Result B(A.size()/2);
    Result C(A.size()/2);

    // O(n)
    for(auto itA = A.begin(); itA != A.end(); ++itA) {
	std::cout << *itA << std::endl;

	if(B.check_sum(*itA) > C.check_sum(*itA)) {
	    if(C.is_value_greater_then_average(*itA)) {
		if(C.add(*itA) != true)
		    B.add(*itA);
	    } else {
		if(B.add(*itA) != true)
		    C.add(*itA);
	    }
	} else {
	    if(B.is_value_greater_then_average(*itA)) {
		if(B.add(*itA) != true)
		    C.add(*itA);
	    } else {
		if(B.add(*itA) != true) 
		    C.add(*itA);
	    }
	}
    }

    std::cout << "sum(A)" << sum_of_elements(A) << std::endl;
    std::cout << "sum(B)" << B.result() << std::endl;
    std::cout << "sum(C)" << C.result() << std::endl;

    return 0;
}

Isn't it an additional space? It's really not required to solve this problem.
I think you should use s.charAt()