abhay0609
BAN USER@ zr.roman yup, Kadane is correct approach in modified way, thats how i solved the problem but didnot mention algo name in my code, so i want to know is it necessary to tell name of the algo to interviewer, as i am preparing for my tech interviews or implementation is enough??
- abhay0609 February 09, 2016public static ArrayList findConsecutiveMaxSum(int[] nums){
if(nums.length<1) return null;
ArrayList<Integer> res = new ArrayList<>();
int maxSofar, currMax,startIndx =0,endIndx =0;
maxSofar = currMax = nums[0];
for (int i = 1 ; i< nums.length ;i++){
if(currMax + nums[i] < nums[i]) startIndx = i;
currMax = Math.max(nums[i],currMax+nums[i]);
if(maxSofar<currMax) endIndx = i;
maxSofar = Math.max(maxSofar,currMax);
}
for (int i = startIndx ; i<=endIndx ;i++) res.add(nums[i]);
if(endIndx<startIndx) res.add(nums[endIndx]);
return res;
}
public static LinkNode insertSortedWay(LinkNode head,LinkNode newNode){
if(head == null || head.data > newNode.data){
newNode.next = head;
head = newNode;
}else {
LinkNode current = head;
while (current.next != null && current.next.data < newNode.data) current = current.next;
newNode.next = current.next;
current.next = newNode;
}
return head;
}
public static void read(int[] nums, LinkNode head1, LinkNode head2){
for(int num : nums){
LinkNode newNode = new LinkNode(num);
if(num % 2 == 0) head1 = insertSortedWay(head1, newNode);
else head2 = insertSortedWay(head2,newNode);
}
}
public static int findKthSmallestElement(int[] nums,int k){
//find occurances
Map<Integer,Integer> map = new HashMap<>();
for (int num: nums){
if(map.get(num)!=null) map.put(num,map.get(num)+1);
else map.put(num,1);
}
//Reverse Map in sorted order values<->key
TreeMap<Integer,Integer> sortedMap = new TreeMap<>();
for (Map.Entry<Integer,Integer> entry : map.entrySet()) sortedMap.put(entry.getValue(),entry.getKey());
//find kth element
for (int key :sortedMap.keySet()) if(--k==0) return sortedMap.get(key);
return Integer.MIN_VALUE;
}
Insertion sort works well on small or nearly sorted array.
Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible
public static void countFrequencies(int[] arr){
Map<Integer,Integer> frequencies = new HashMap<>();
for (int n :arr){
if(frequencies.get(n) !=null) frequencies.put(n,frequencies.get(n)+1);
else frequencies.put(n,1);
}
for (int n : frequencies.keySet()) System.out.println(n+" ->"+ frequencies.get(n));
}
- abhay0609 January 05, 2016We can use heap to find closest star since sorting will take O(nlogn) time while using heap we can find it with complexity O(nlogk) where k <<n.
1 Use a max heap
2 add an element
3 compare next element with the top if bigger do nothing else replace top of heap
public static Node mergeSort(Node head){
if(head == null || head.next==null) return head;
Node mid = getMidNode(head);
Node secondList = mid.next;
mid.next = null;
return merge(mergeSort(head),mergeSort(secondList));
}
public static Node merge(Node h1 ,Node h2){
Node result ;
if(h1==null) return h2;
if(h2 == null) return h1;
if (h1.data <= h2.data){ result = h1 ; result.next = merge(h1.next,h2); }
else{
result = h2 ;
result.next = merge(h1,h2.next);
}
return result;
}
public static Node getMidNode(Node head){
Node fast,slow;
fast = slow = head;
while (fast.next!=null && fast.next.next!=null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
Java Solution
public static String createPalindrome(String str){
if(isPalindrome(str)) return str;
StringBuilder sb = new StringBuilder();
for (char ch : str.toCharArray()) {
sb.append(ch);
sb.reverse();
if(isPalindrome(str+sb)) break;
sb.reverse();
}
return str+sb;
}
public static boolean isPalindrome(String s){
StringBuilder sb = new StringBuilder(s);
return s.equals(sb.reverse().toString());
}
public static void rearrange(int[] a){
Arrays.sort(a);
int[] result = new int[a.length];
int l = 0,r = a.length-1,i = 0;
while (l<r){
result[i++] = a[r--];
result[i++] = a[l++];
}
if(l==r) result[result.length-1] = a[l];
for (int n : result) System.out.print(n);
}
- abhay0609 December 19, 2015public void connectNeighbor(TreeNode root){
if(root == null) return;
TreeNode lastHead = root;//prevous level's head
TreeNode lastCurrent = null;//pointer
TreeNode currentHead = null;//current level's head
TreeNode current = null;//pointer
while (lastHead != null){
lastCurrent = lastHead;
while (lastCurrent !=null){
if(lastCurrent.left != null){
if(currentHead == null)
currentHead = lastCurrent.left;
current = lastCurrent.left;
}else {
current.next = lastCurrent.left;
current = current.next;
}
if(lastCurrent.right != null){
if(currentHead == null){
currentHead = lastCurrent.right;
current = lastCurrent.right;
}else {
current.next = lastCurrent.right;
current = current.next;
}
}
lastCurrent = lastCurrent.next;
}
lastHead = currentHead;
currentHead = null;
}
}
- abhay0609 December 12, 2015public static void printLevel(TreeNode root , int level,boolean ltr){
if(root == null) return;
if(level == 1) System.out.print(root.data+" ");
else if(ltr == true) {
printLevel(root.left,level-1,ltr);
printLevel(root.right, level - 1,ltr);
}else {
printLevel(root.right, level - 1,ltr);
printLevel(root.left,level-1,ltr);
}
}
public static void inwardSpiral(TreeNode root){
int h = height(root);
int firstLevel = 1;
int lastLevel = h;
while (firstLevel < lastLevel){
printLevel(root, firstLevel, true);
printLevel(root, lastLevel, false);
firstLevel++;
lastLevel--;
}
}
- abhay0609 August 01, 2016