daydreamer
BAN USERlearner
This question talks about LinkedList, not a queue
You have to tell the fifth element from last using a linkedList
O(n^2) solution but is a stable Sort
public class UniqueSortedIntegerLeft {
public static Integer[] sort(final Integer[] input) {
int duplicateIndex = -1;
for (int i = 1; i < input.length; ){
if (input[i-1] == input[i]) {
if (duplicateIndex == -1) {
duplicateIndex = i;
}
i++;
}
else {
if (duplicateIndex != -1) {
shiftArray(input, duplicateIndex, i);
duplicateIndex = -1;
} else {
i++;
}
}
}
return input;
}
private static void shiftArray(final Integer[] array, int startIndex, int copyFromIndex) {
int copyValue = array[startIndex];
while (copyFromIndex < array.length) {
array[startIndex++] = array[copyFromIndex++];
}
while (startIndex < array.length) {
array[startIndex++] = copyValue;
}
}
private static void printArray(final Integer[] array) {
for (Integer value: array) {
System.out.print(value + " ");
}
System.out.println();
}
private static void swap(final Integer[] array, int from, int to) {
int tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
public static void main(String args[]) {
printArray(sort(new Integer[]{1,1,1,2,3}));
printArray(sort(new Integer[]{1,1,2,3,4,4,5,6}));
printArray(sort(new Integer[]{1,1,1,3,4}));
}
}
Output:
1 2 3 1 1
1 2 3 4 5 6 1 4
1 3 4 1 1
It does, thank you Dilbert
- daydreamer September 20, 2012public class IncrementValueInArray {
public static Integer[] plusOne(final Integer[] input) {
int carry = 1;
for (int i = input.length - 1; i >= 0; i--) {
int sum = input[i] + carry;
carry = sum /10;
input[i] = carry > 0? sum % carry : sum;
}
if (carry != 0) {
Integer[] result = new Integer[1 + input.length];
result[0] = carry;
for (int j = 0; j < input.length; j++) {
result[j + 1] = input[j];
}
return result;
}
return input;
}
private static void printArray(final Integer[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String args[]) {
printArray(plusOne(new Integer[]{9,9}));
printArray(plusOne(new Integer[]{8, 2}));
printArray(plusOne(new Integer[]{1, 8, 2}));
printArray(plusOne(new Integer[]{1, 9, 9}));
printArray(plusOne(new Integer[]{9, 9, 9}));
}
}
Output:
1 0 0
8 3
1 8 3
2 0 0
1 0 0 0
I did not understand the concept of using x and y and how addtional spaces are spread uniformly, can you explain?
- daydreamer September 19, 2012for i in range(1, n):
C += C[i] * x^(n-1)
use array and hashmap
for each key=(a+b), put pair in hashmap
put the key in array too
basically the value in hashmap is list, to avoid collisions
now we have array, get top N elements using K-th Order statistic
for each key in array, get value from map
space complexity is high - O(2n) and time complexity - O(n)
Correct me if I am wrong
can somebody please explain the problem with example, I did not get it completely
- daydreamer September 01, 2010It can be done in O(n) using hashmap, and also if we create BST by ignoring creation of nodes with duplicate nodes. I tried to program in Java, source code below:
BSTNode.java:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package careercup.google;
/**
*
* @author Harit
*/
public class BSTNode {
private int value;
private int leftChild;
private int rightChild;
public BSTNode(int v){
value = v;
leftChild = -1;
rightChild = -1;
}
public int getValue(){
return this.value;
}
public int getChild(boolean left){
if(left){
return this.leftChild;
}
else{
return this.rightChild;
}
}
public void setChild(int child, boolean left){
if(left){
this.leftChild = child;
}else{
this.rightChild = child;
}
}
}
RemDupArrayBST:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package careercup.google;
import java.util.ArrayList;
/**
*
* @author Harit
*/
public class RemDupArrayBST {
/* Output Array of Nodes */
private static ArrayList<BSTNode> nodes = new ArrayList<BSTNode>();
private static int parent = -1;
private static boolean left = false;
public static void main(String args[]){
/* Sample Input Array */
//int[] input_array = new int[]{3,1,2,1};
//int[] input_array = new int[]{3,5,4,2,1,2,3,1};
int[] input_array = new int[]{1,2,3,2,4,4};
/* end sample input */
for(int i=0; i<input_array.length; i++){
if(nodes.size() == 0){
/* tree is empty, add root */
BSTNode node = new BSTNode(input_array[i]);
nodes.add(node);
}else{
/* search if node already exists */
if(!contains(input_array[i])){
BSTNode node = new BSTNode(input_array[i]);
nodes.add(node);
nodes.get(parent).setChild(nodes.size()-1, left);
}else{
System.out.println(input_array[i] + " : already exists - ignoring");
}
}
}
/* final print */
System.out.print("Inorder Traversal: ");
inOrderTraverse(nodes.get(0));
System.out.println("");
System.out.print("PostOrder Traversal: ");
postOrderTraverse(nodes.get(0));
System.out.println("");
System.out.print("PreOrder Traversal: ");
preOrderTraverse(nodes.get(0));
System.out.println("");
}
private static boolean contains(int value){
int index = 0;
while(index >= 0){
if (nodes.get(index).getValue() == value){
return true;
}
if (nodes.get(index).getValue() > value){
parent = index;
left = true;
index = nodes.get(index).getChild(true);
}else{
parent = index;
left = false;
index = nodes.get(index).getChild(false);
}
}
return false;
}
private static void inOrderTraverse(BSTNode node){
if(node == null){
return;
}
if(node.getChild(true) != -1){
inOrderTraverse(nodes.get(node.getChild(true)));
}
System.out.print(node.getValue() + " ");
if(node.getChild(false) != -1){
inOrderTraverse(nodes.get(node.getChild(false)));
}
}
private static void postOrderTraverse(BSTNode node){
if(node == null){
return;
}
if(node.getChild(true) != -1){
postOrderTraverse(nodes.get(node.getChild(true)));
}
if(node.getChild(false) != -1){
postOrderTraverse(nodes.get(node.getChild(false)));
}
System.out.print(node.getValue() + " ");
}
private static void preOrderTraverse(BSTNode node){
if(node == null){
return;
}
System.out.print(node.getValue() + " ");
if(node.getChild(true) != -1){
preOrderTraverse(nodes.get(node.getChild(true)));
}
if(node.getChild(false) != -1){
preOrderTraverse(nodes.get(node.getChild(false)));
}
}
}
O(n) solution
General Solution to find nth node from tail
Output:
- daydreamer September 20, 2012