CareerCup

You could implement any sort also (merge or quicksort). Make sure the comparison is done 
on the ascii values of these characters. This will give then sorted string.

Not sure if this can be done in-memory, I have however used stack iteratively with Deque implementation. Here is the code :

public Node swapApp(Node node) {
    Deque<Node> stack = new ArrayDeque<>();
    while (node != null) {
          stack.addFirst(node);
          node = node.next;
    }
    Node head = new Node('Z');
    Node dummy = head;
    boolean isAlternate = true;
    while (!stack.isEmpty()) {
        Node n1 = null;
        if (isAlternate) {
            n1 = stack.pollLast();
            head.next = n1;
        } else {
            n1 = stack.pollFirst();
           head.next = n1;
        }
        n1.next = null;
        isAlternate = !isAlternate;
        head = head.next;
    }

    return dummy.next;
  }

I think it is easy to use Trie in this case. Define trie with maps, where each value in map is an entity (file or directory). Maintain a stack (say currPath) at class level which serves as current path of the cursor (pwd in unix). so if you want to create a file or directory, go in the depth of trie and when path is equal to currPath, do the intended operation.

public class DuplicateContacts {

  public static class Contacts {

    String contactID;
    List<String> emails = new ArrayList<>(  );

    public Contacts (String contactID, List<String> emails) {
      this.contactID = contactID;
      this.emails = emails;
    }
  }

  public static void main(String[] args) {
    Contacts c1 = new Contacts( "C1", Arrays.asList("a@gmail.com", "b@gmail.com", "c@gmail.com", "d@gmail.com") );
    Contacts c2 = new Contacts( "C2", Arrays.asList("aa@gmail.com", "bb@gmail.com", "cc@gmail.com") );
    Contacts c3 = new Contacts( "C3", Arrays.asList("a@gmail.com", "b@gmail.com", "c@gmail.com") );
    Contacts c4 = new Contacts( "C4", Arrays.asList("aa@gmail.com", "bb@gmail.com", "cc@gmail.com") );
    Contacts c5 = new Contacts( "C5", Arrays.asList("aaa@gmail.com") );

    List<Contacts> list = Arrays.asList( c1,c2,c3,c4,c5 );

    Set<Contacts> finalList = getUniqueList(list);

    for (Contacts ct : finalList)
        System.out.print(ct.contactID + " ");
  }


  private static Set<Contacts> getUniqueList(List<Contacts> listContact) {
    Set<Contacts> finalList = new HashSet<>(  );
    Map<String, Contacts> map = new HashMap<>();

    for (Contacts c : listContact) {
       for (String email : c.emails) {
          if (!map.containsKey( email ))
                map.put (email, c);
       }
    }

    for (Contacts c : map.values()) {
      if (listContact.contains( c ))
            finalList.add(c);
    }

    return finalList;
  }
}

Question not clear - a = [5, 2, 4, 3, 1], k = 2
Return [2, 3, 1, 4, 5]

Can you please provide some more example?

You can store in set the result to avoid duplicate values:

public static void permutation(String str) {
		Map<Character, List<Integer>> map = new HashMap<>();
		int i = 0;
		for (Character ch : str.toCharArray()) {
			if (map.containsKey(ch))
				(map.get(ch)).add(++i);
			else {
				List<Integer> list = new ArrayList<>();
				list.add(++i);
				map.put(ch, list);
			}

		}
		permutation("", str, map);
	}

	private static void permutation(String prefix, String str, Map<Character, List<Integer>> map) {
		int n = str.length();
		if (n == 0) {
			if (check(prefix, map))
				System.out.println(prefix);
		} else {
			for (int i = 0; i < n; i++) {

				permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), map);
			}
		}
	}

	private static boolean check(String prefix, Map<Character, List<Integer>> map) {
		int i = 1;
		for (Character ch : prefix.toCharArray()) {
			if (map.get(ch).contains(i++))
				return false;
		}
		return true;
	}

My working solution, I think this could be further optimized:

private static int getHigestNumDivisibleByThree(int[] arr) {

		int sum = 0;
		StringBuilder str = new StringBuilder();
		Arrays.sort(arr);

		for (int i = arr.length; i > 0; i--) {
			sum = sum + arr[i - 1];
			str.append(arr[i - 1]);
		}

		int remainder = sum % 3;
		if (remainder == 0)
			return Integer.parseInt(str.toString());

		str = new StringBuilder();

		boolean condition = true;
		int removeNum = 0;
		while (condition && remainder <= 9) {
			if (contains(arr, remainder)) {
				removeNum = remainder;
				break;
			}
			remainder = remainder + 3;
		}
		if (removeNum == 0)
			return 0;
		for (int i = arr.length; i > 0; i--) {
			if (removeNum == arr[i - 1]) {
				continue;
			}
			str.append(arr[i - 1]);
		}
		return Integer.parseInt(str.toString());
	}

	private static boolean contains(int[] arr, int num) {
		for (int i : arr)
			if (i == num)
				return true;
		return false;
	}

Following is what I tried, after coming up with examples.

private static String KthLongestDistinctSubString(String string, int numChars) {

		int j = 0, distinct = 0;
		String result = "";
		char[] ch = string.toCharArray();
		for (int i = 0; i < string.length(); i++) {
			j = i;
			StringBuffer sb = new StringBuffer();
			int[] charAscii = new int[26];// 0,0,0,
			
			while (j < string.length()) // aaaabbbb
			{
				char chac = ch[j];
				if (charAscii[chac-'a'] > 0) {
					sb.append(chac);
				}
				if (charAscii[chac-'a'] == 0) {
						if (distinct > numChars)
								break;
					distinct++;
					sb.append(chac);
					charAscii[chac-'a'] = 1;
				} 

				j++;
			}
			if (result.length() < sb.toString().length()) {
				result = sb.toString();

			}
		}

		return result;

	}

How about this:

public static String encode(List<String> stringList) {
		StringBuilder encodedString = new StringBuilder();
		for (String str : stringList) {
			int length = str.length();
			encodedString.append(length).append(str);
		}
		return encodedString.toString();
	}

	public static List<String> decode(String encodedString) {
		List<String> list = new ArrayList<>();
		char[] stringChars = encodedString.toCharArray();
		StringBuffer sb = new StringBuffer();
		int count = Integer.parseInt(stringChars[0]+"");

		int j = 0;
		for (int i = 1; i < encodedString.length(); i++) {
			j = 0;
			while (j++ < count) {
				sb.append(stringChars[i++] + "");
			}
			list.add(sb.toString());
			sb = new StringBuffer();
			if (i < encodedString.length()) {
				count = Integer.parseInt(stringChars[i]+"");
			}
		}
		return list;
	}

O(n) is the straightforward solution by first iterating the array for products, and then one more iteration, for diving the product with each of value at index. Can we do better than O(n) ?

1. First find the root of all - this could be one or more.
2. Use recursive call to simply print the child.

public static void printParentChild(Map<String, List<String>> map) {
		Set<String> keys = map.keySet();
		Set<String> stringKeys = new HashSet<>();
		for (String str : keys)
			stringKeys.add(str);	

		for (String str : keys) {
			List<String> list = map.get(str);
			for (String string : list) {
				if (stringKeys.contains(string))
					stringKeys.remove(string);
			}
		}
		printParentChild(stringKeys, map, 0);
	}
	private static String getBlank (int num) {
		StringBuilder sb = new StringBuilder("");
			while (num--!=0)
					sb.append(" ");
		return sb.toString();
	}
	private static void printParentChild(Set<String> stringKeys, Map<String, List<String>> map, Integer numBlanks) {

		if (stringKeys.isEmpty()) {
			return;
		}

		for (String str : stringKeys) {
			System.out.println(getBlank(numBlanks) + str);
			if (map.get(str) != null) {
				Set<String> foo = new HashSet<String>(map.get(str));
				printParentChild(foo, map, ++numBlanks);
				--numBlanks;	
			}

		}

	}

I derived following solution ::

private static int calculate(int[] arrInitial, int[] arrFinal) {
		int totalsteps = 0, position = 0, blankSpot = 0, placeholder = 0, finalBlankSpot = 0, tempValue = 0,
				tempIndex = 0;

		blankSpot = findIndex(arrInitial, -1);
		finalBlankSpot = findIndex(arrFinal, -1);

		while (finalSet.size() != arrInitial.length - 1) {

			if (arrInitial[position] == arrFinal[position]) {
				if (arrInitial[position] != -1)
					finalSet.add(arrInitial[position]);
				position++;
				totalsteps++;
				continue;
			}
			tempValue = arrFinal[position];
			// for tempValue in arr1, find its index
			tempIndex = findIndex(arrInitial, tempValue);
			// swap value of arrInital[position] with blankSpot
			arrInitial[blankSpot] = arrInitial[position];
			arrInitial[position] = -1;
			blankSpot = position;
			// now swap value of tempIndex in arrInitial with new blankspot and
			// update blankspot value
			arrInitial[position] = arrInitial[tempIndex];
			arrInitial[tempIndex] = -1;
			blankSpot = tempIndex;

			if (arrInitial[position] != -1)
				finalSet.add(arrInitial[position]);
			position++;
			totalsteps++;

		}
			
		return totalsteps;
	}

	private static int findIndex(int[] arr, int value) {
		int index = 0;
		for (int i : arr) {
			if (i == value)
				return index;
			index++;
		}
		return index;
	}

With Complexity equivalent to O(n)

private static int getMaxLength(String next) {
		Map<Character, Integer> map = new ConcurrentHashMap<Character, Integer>();
		int count = 1;
		char key = '0', mid = '0';
		int val;
		String palin = "";
		for (Character ch : next.toCharArray()) {
			if (map.containsKey(ch)) {
				count = map.get(ch) + 1;
				map.put(ch, count);
			} else {
				map.put(ch, 1);
			}
		}
		System.out.println(map);
		while (! map.isEmpty())
		for (Map.Entry<Character, Integer> entry : map.entrySet()) {
			if (entry.getValue() >= 2) {
				val = entry.getValue();
				key = entry.getKey();
				palin = palin + key;
				map.put(key, val - 2);
			} else {
				if (entry.getValue() == 1)
					mid = entry.getKey();
				map.remove(entry.getKey());
				continue;
			}
		}

		if (mid != '0')
			palin = palin + mid + reverse(palin);
		else
			palin = palin + reverse(palin);
		System.out.println("Palin is : " + palin);
		return palin.length();

	}

// Using the power of recursion:

public static Node mergerSortedKthList(Node list1, Node list2, int k) {
		if (k == 0) {
			return null;
		}
		Node node;
		if (list1.val > list2.val) {
			node = list2; k = k-1;
			node.next = mergerSortedKthList(list1, list2.next, k);
		} else {
			node = list1; k = k-1;
			node.next = mergerSortedKthList(list1.next, list2, k);
		}
		return node;
	}

private static boolean isTargetsumExists(int[] list1, int[] list2, int target) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();	
		 
		for (int i : list1) {
			map.put(Math.abs(i), i);
		}
		 
		for (int j : list2) {
			if(map.get(Math.abs(target-j)) != null ) {
				return true;
			}
		}
		return false;
	}

Following code should work:

private static int[] moveZeroesAhead(int[] num) {
		int j = 0;
		for (int i=1; i<num.length;i++) {
			if(num[i]==0)
			{
			   int count = i;
			    while (count>j && num[count-1] >0) {
					num[count] = num[count-1];
					num[count-1] = 0;
					count--;
				}
			    j++;
			}
		}
		return num;
	}

Following code implements LRU cache using linklist.

package linkList;

import java.util.*;


/*
 * we are using linked list with hashmap for Lru.
 * Reason behind this is ,since HashMap is able to store data and key but
 * how do we get info about least recently used cache value?. For this we need to keep track all inserted data into map
 * by using linked list. When inserting new values , add this value to the top of linked list. When key,value is already
 * present then refresh it by removing it from the linked list and adding it to top of the linked list. 
 * */

public class LRUImpl {
	
	private static final int String = 0;

	public interface CacheStrategy<K, T>{
		T get(K key);
		void put(K key,T data);
	}
	
	class CacheStrategyLRU<K, T> implements CacheStrategy<K, T> {
		
		class Node{
			K key;
			T data;
			Node next;
			Node prev;
			
			public Node(K key, T data){
				this.key = key;
				this.data = data;
			}
		}
		
		Node head,tail;
		Map< K, Node> map;
		int maxsize;
		
		public CacheStrategyLRU(int mxsize){
			this.maxsize = mxsize;
			map = new HashMap<K ,Node>();
			head =  new Node(null,null);
			tail = new Node(null,null);
			head.next=tail;
			tail.prev=head;
		}
		
		private void  attach(Node head,Node node){
			node.prev = head;
			node.next = head.next;
			head.next.prev=node;
			head.next = node;
		}
		
		private void remove(Node node){
			node.prev.next = node.next;
			node.next.prev = node.prev;
		}
		
		
		@Override
		public T get(K key) {
			Node node = map.get(key);
			if(node==null){
				return null;
			}
			
			if(map.size()==1){
				return node.data;
			}
			remove(node);
			attach(head,node);
			return node.data;
		}

		@Override
		public void put(K key, T data) {
			if(maxsize<=0){
				return;
			}
			Node node = map.get(key);
			if(node!=null){
				remove(node);
				attach(head,node);
				node.data = data;
			}else{
				if(map.size() >= maxsize){
					remove(tail.prev);//tail is node pointer ,its not containg any node so delete tail.prev
					map.remove(tail.prev.key);
				}
				Node nd = new Node(key,data);
				map.put(key, nd);
				attach(head,nd);
			}
			
		}
    	
    }  
	
}

This brings complexity of O(n).

Following code has O(n) complexity, as there is only one loop and it prints only the distinct set.

	public static void find_sum_pair(int[] arr, int sum) {
		HashMap<Integer,Integer> map = new HashMap<>();
		for (int i=0; i<arr.length; i++) {
			if (map.containsKey(sum - arr[i])) {
				System.out.println("("+ (sum - arr[i]) + ","+arr[i] + ")");
			}
			map.put(arr[i], 0);
		}
	}

public static void popularIteminSortedArray(int[] arr) {

		int counterBeg = 0;
		int counterEnd = 0;
		boolean isThereAny = false;
		for (int i = 1, j = arr.length - 1; i < arr.length && j > 0; i++, j--) {
			if (i>j && (counterBeg < 3) && (counterEnd < 3))
				  break;
             if(arr[i] == arr[i-1]) {
            	 if(counterBeg >= 4){
            		 System.out.println(" element is: " + arr[i]);
            		 counterBeg = 0;
            		 isThereAny = true;
            		 continue;
            	 }
            	 counterBeg++;
             }
             if (arr[j] == arr[j - 2]) {
            	 if(counterEnd > 4){
            		 System.out.println(" element is: " + arr[j]);
            		 counterEnd = 0;
            		 isThereAny = true;
            		 continue;
            	 }
            	 counterEnd++; 
             }
		}
		
		if (!isThereAny) System.out.println("None !!!");
	}

Strategy Pattern should be good fit for this design problem.