Lyubomir
BAN USER
- 1
0of 0 votes
AnswerCreate a class Graph, which must represent the graph data structure in java. What will be the difference between directional and unidirectional Graph? How would you represent the weight of the edges?
- Lyubomir in United States| Report Duplicate | Flag | PURGE
Hi5 Java Developer - 7
0of 0 votes
AnswersIf we have a very big text file which contains millions of lines of code. On every line there is a one word. We also have a random generator which returns a number between 0 and 1. When we have 1 - this will corresponds to the last line of the file. When we have 0 - to the first one. We want an algorithm which tells as the word (the line) which corresponds to the generated number.
- Lyubomir in UK for Love Film| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer - 21
0of 0 votes
AnswersWrite an algorithm to check if a tree is binary search tree
- Lyubomir in UK for Love Film| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm
Here is my C# implementation. To convert it to java or c is trivial...
1using System;
using System.Text;
namespace Algo
{
static class Parser
{
//input a2b1c3d10
//output aabcccdddddddddd...
public static String Parse(String str)
{
if (String.IsNullOrEmpty(str))
return String.Empty;
StringBuilder sb = new StringBuilder();
char[] strArr = str.ToCharArray();
int counter = 0;
while (counter < strArr.Length)
{
if(isChar(strArr[counter]))
{
char c = strArr[counter];
++counter;
string sNumberofTimes = strArr[counter].ToString();
while(isNumber(strArr[counter]))
{
sNumberofTimes +=strArr[counter].ToString();
counter++;
}
int numberOfTimes = int.Parse(sNumberofTimes);
for (int i = 0; i < numberOfTimes; i++)
{
sb.Append(c);
}
}
//Console.WriteLine(strArr[counter]);
counter++;
}
return sb.ToString();
}
private static bool isChar(char c)
{
char[] possibleChars = { 'a', 'b', 'c', 'd' };
for (int i = 0; i < possibleChars.Length; i++)
{
if (c == possibleChars[i])
return true;
}
return false;
}
private static bool isNumber(char c)
{
int[] possibleNumbers = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 0; i < possibleNumbers.Length; i++)
{
if (c == possibleNumbers[i])
return true;
}
return false;
}
}
}
public void traverseToNThSmallest(Node root) {
if (root.left != null) {
traverseToNThSmallest(root.left);
}
counter++;
if(counter ==nthElement)
{
System.out.println(nthElement+"th element: "+ root.val);
return;
}
if (root.right != null) {
traverseToNThSmallest(root.right);
}
}
Hello, could you check my implementation? To merge the lists what I do is:
1. Find the middle - where the second list starts and save this node
2. Compare the values of the start and the middle lists, if the value of the start is smaller than the value of the second list - > move the pointer of the first part to ne next element.
If the the other part is greater then:
1 step Create a new Node with the value of the element;
2 stepCreate a node - pointer to the next element of the second list;
3 step remove the node of the second list
4 step add the new node to the element before the current element of the first list
5 step move the current element of the second list to point to the next element - the node create in step 2
Here is the code in Java:
//2.Given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list in place [do not use any extra space].
//Sample test case:
//Input: List 1:1->2->3->4->5->1->2; Output: 1->1->2->2->3->4->5
//Input 2: 1->5->7->9->11->2->4->6; Output 2: 1->2->4->5->6->7->9->11
public class MergeLinkedLists {
public static void main(String[] args) {
List list = new List();
list.addToEnd(1).addToEnd(9).addToEnd(13).addToEnd(15);
// the next sorted part of the list
list.addToEnd(5).addToEnd(6).addToEnd(14).addToEnd(15).addToEnd(20);
System.out.println(list);
list.mergeLists();
System.out.println(list);
}
public static class List {
Node head;
int count;
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node linkToStart = head;
while (linkToStart != null) {
sb.append(linkToStart.val + " - > ");
linkToStart = linkToStart.next;
}
return sb.toString();
}
public void mergeLists() {
Node linkToList1 = head;
Node linkToList2 = findTheStartOfTheSecondPart();
while (linkToList1.next != null && linkToList2.next != null) {
if (linkToList1.val <= linkToList2.val) {
linkToList1 = linkToList1.next;
} else {
// copy node - I am not sure this is the best
Node n = new Node(linkToList2.val, null);
Node next = linkToList2.next;
remove(linkToList2);
addBefore(linkToList1, n);
linkToList2 = next;
}
}
}
private Node findTheStartOfTheSecondPart() {
// find the starting point of the second sorted linked list
Node linkToList1 = head;
Node linkToList2 = null;
int tmpVal = -1;
if (linkToList1 != null)
tmpVal = linkToList1.val;
while (linkToList1 != null) {
linkToList1 = linkToList1.next;
if (linkToList1.val < tmpVal) {
linkToList2 = linkToList1;
break;
} else {
tmpVal = linkToList1.val;
}
}
return linkToList2;
}
public void add(int val) {
add(new Node(val, null));
}
public void add(Node node) {
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
count++;
}
public void swapWithNext(int val1) {
Node linkToHead = head;
while (linkToHead.next != null) {
if (linkToHead.val == val1) {
int tmp = linkToHead.val;
linkToHead.val = linkToHead.next.val;
linkToHead.next.val = tmp;
return;
}
linkToHead = linkToHead.next;
}
}
/**Add before by the node - compared by its value
* @param beforeNode
* @param node
*/
public void addBefore(Node beforeNode, Node node) {
addBefore(beforeNode.val, node.val);
}
/**
* Add before node - it adds after and then swap the values
* @param beforeNodeVal
* @param nodeVal
*/
public void addBefore(int beforeNodeVal, int nodeVal) {
addAfter(beforeNodeVal, nodeVal);
swapWithNext(beforeNodeVal);
}
public void addAfter(int afterNodeVal, int nodeVal) {
Node afterNode = new Node(afterNodeVal, null);
Node node = new Node(nodeVal, null);
addAfter(afterNode, node);
}
public void addAfter(Node afterNode, Node node) {
Node linkToHead = head;
while (linkToHead.next != null) {
if (linkToHead.val == afterNode.val) {
Node nextNode = linkToHead.next;
linkToHead.next = node;
node.next = nextNode;
return;
}
linkToHead = linkToHead.next;
}
linkToHead.next = node;
}
/**
* Add Element to the end of the linked list
*
* @param val
* the value of the element
*/
public List addToEnd(int val) {
return addToEnd(new Node(val, null));
}
/**
* Adds element to the end of the linked list
*
* @param node
*/
public List addToEnd(Node node) {
if (head == null)
head = node;
else {
Node linkToHead = head;
while (linkToHead.next != null) {
linkToHead = linkToHead.next;
}
linkToHead.next = node;
}
return this;
}
public Node getHead() {
return head;
}
/**
* Remove the head element of the linked list
*
* @return the Head node of the linked list
*/
public Node removeHead() {
if (head == null)
return null;
else {
Node pointerToHead = head;
head = head.next;
return pointerToHead;
}
}
/**
* Remove an element from the linked list - it searched the elements and
* removes after it finds one with the same value
*
* @param val
* the value of the element which will be removed
* @return true if the element has been removed
*/
public boolean remove(int val) {
return remove(new Node(val, null));
}
public boolean remove(Node node) {
if (head == null)
return false;
else {
Node pointerToHead = head;
while (pointerToHead.next != null) {
if (pointerToHead.val == node.val) {
pointerToHead.val = pointerToHead.next.val;
pointerToHead.next = pointerToHead.next.next;
return true;
}
pointerToHead = pointerToHead.next;
}
}
return false;
}
}
/**
* @author lyubo Node of Linked List
*/
public static class Node {
int val;
Node next;
/**
* Constructor of the Node class
*
* @param val
* @param next
*/
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
Node linkToNode = this;
StringBuilder sb = new StringBuilder();
while (linkToNode != null) {
sb.append(linkToNode.val + " -> ");
linkToNode = linkToNode.next;
}
return sb.toString();
}
}
}
I will be very happy if someone can check my merge method and idea. Thanks :)
- Lyubomir January 17, 2013Sorting the array will give better time complexity than O(n^2). We can assume thant sorting is O(nlogn) + Iteration of the elements which are less than N (arr[i] + arr[j] < N) - I can not say how much time it takes, but I believe that it is better than O(n^2)
public class SumOfNums {
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 2, 3, 4, 5 };
int N = 4; // (x+y==4 ?)
// sort the array
Arrays.sort(arr);
int i = 0;
while (i < arr.length-1) {
int j = i+1;
while (j < arr.length - 1 && arr[i] + arr[j] < N) {
j++;
}
if (arr[i] + arr[j] == N)
System.out.print("(" + arr[i] + "," + arr[j] + "), ");
i++;
}
}
}
//given an array of size n, it holds distinct integers from 1 to n. Give an algorithm to sort the array? one way is to just assign a[i]=i in the array. how to sort the array using the elements of the array and not just assigning directly
public class Sort {
public static void main(String[] args) {
int[] arr = { 2, 4, 1, 3 };
int i = 0;
int j = 0;
while (j < arr.length-1) {
i=j;
int x=i+1;
while (arr[i] != i+1) {
swap(arr, i, x);
x++;
}
j++;
}
for(int a: arr)
{
System.out.print(a + ", ");
}
}
private static void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
}
The time complexity is O(n^2), no additional space is required - O(n) - the size of the array itself
- Lyubomir January 07, 2013This does not make any sense for me. The heap allows to get the smallest or the biggest element in constant time after the heap is created in linear time... but when a new car comes we have to rearrange the heap it depens from the value... I do not know but to represent parking I thin the best would be just an array of spaces
- Lyubomir December 23, 2012is there anything more simple than this:
package com.jwetherell.algorithms.data_structures;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArrayList;
/**
* Graph. Could be directed or undirected depending on the TYPE enum. A graph is
* an abstract representation of a set of objects where some pairs of the
* objects are connected by links.
*
*
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class Graph<T extends Comparable<T>> {
private List<Vertex<T>> verticies = new CopyOnWriteArrayList<Vertex<T>>();
private List<Edge<T>> edges = new CopyOnWriteArrayList<Edge<T>>();
public enum TYPE {
DIRECTED, UNDIRECTED
};
private TYPE type = TYPE.UNDIRECTED;
public Graph() {
}
public Graph(Graph<T> g) {
// Deep copies
// Copy the vertices (which copies the edges)
for (Vertex<T> v : g.getVerticies()) {
this.verticies.add(new Vertex<T>(v));
}
// Update the object references
for (Vertex<T> v : this.verticies) {
for (Edge<T> e : v.getEdges()) {
Vertex<T> fromVertex = e.getFromVertex();
Vertex<T> toVertex = e.getToVertex();
int indexOfFrom = this.verticies.indexOf(fromVertex);
e.from = this.verticies.get(indexOfFrom);
int indexOfTo = this.verticies.indexOf(toVertex);
e.to = this.verticies.get(indexOfTo);
this.edges.add(e);
}
}
type = g.getType();
}
public Graph(TYPE type) {
this();
this.type = type;
}
public Graph(List<Vertex<T>> verticies, List<Edge<T>> edges) {
this(TYPE.UNDIRECTED, verticies, edges);
}
public Graph(TYPE type, List<Vertex<T>> verticies, List<Edge<T>> edges) {
this(type);
this.verticies.addAll(verticies);
this.edges.addAll(edges);
for (Edge<T> e : edges) {
Vertex<T> from = e.from;
Vertex<T> to = e.to;
if (!this.verticies.contains(from) || !this.verticies.contains(to)) continue;
int index = this.verticies.indexOf(from);
Vertex<T> fromVertex = this.verticies.get(index);
index = this.verticies.indexOf(to);
Vertex<T> toVertex = this.verticies.get(index);
fromVertex.addEdge(e);
if (this.type == TYPE.UNDIRECTED) {
Edge<T> reciprical = new Edge<T>(e.cost, toVertex, fromVertex);
toVertex.addEdge(reciprical);
this.edges.add(reciprical);
}
}
}
public TYPE getType() {
return type;
}
public List<Vertex<T>> getVerticies() {
return verticies;
}
public List<Edge<T>> getEdges() {
return edges;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (Vertex<T> v : verticies) {
builder.append(v.toString());
}
return builder.toString();
}
public static class Vertex<T extends Comparable<T>> implements Comparable<Vertex<T>> {
private T value = null;
private int weight = 0;
private List<Edge<T>> edges = new ArrayList<Edge<T>>();
public Vertex(T value) {
this.value = value;
}
public Vertex(T value, int weight) {
this(value);
this.weight = weight;
}
public Vertex(Vertex<T> vertex) {
this(vertex.value, vertex.weight);
this.edges = new ArrayList<Edge<T>>();
for (Edge<T> e : vertex.edges) {
this.edges.add(new Edge<T>(e));
}
}
public T getValue() {
return value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public void addEdge(Edge<T> e) {
edges.add(e);
}
public List<Edge<T>> getEdges() {
return edges;
}
public boolean pathTo(Vertex<T> v) {
for (Edge<T> e : edges) {
if (e.to.equals(v)) return true;
}
return false;
}
/**
* {@inheritDoc}
*/
@Override
public int compareTo(Vertex<T> v) {
if (this.value == null || v.value == null) return -1;
return this.value.compareTo(v.value);
}
/**
* {@inheritDoc}
*/
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object v1) {
if (!(v1 instanceof Vertex)) return false;
Vertex<T> v = (Vertex<T>) v1;
boolean values = this.value.equals(v.value);
if (!values) return false;
boolean weight = this.weight == v.weight;
if (!weight) return false;
return true;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("vertex:").append(" value=").append(value).append(" weight=").append(weight).append("\n");
for (Edge<T> e : edges) {
builder.append("\t").append(e.toString());
}
return builder.toString();
}
}
public static class Edge<T extends Comparable<T>> implements Comparable<Edge<T>> {
private Vertex<T> from = null;
private Vertex<T> to = null;
private int cost = 0;
public Edge(int cost, Vertex<T> from, Vertex<T> to) {
if (from == null || to == null) throw (new NullPointerException("Both 'to' and 'from' Verticies need to be non-NULL."));
this.cost = cost;
this.from = from;
this.to = to;
}
public Edge(Edge<T> e) {
this(e.cost, e.from, e.to);
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;;
}
public Vertex<T> getFromVertex() {
return from;
}
public Vertex<T> getToVertex() {
return to;
}
/**
* {@inheritDoc}
*/
@Override
public int compareTo(Edge<T> e) {
if (this.cost < e.cost) return -1;
if (this.cost > e.cost) return 1;
return 0;
}
/**
* {@inheritDoc}
*/
@Override
public int hashCode() {
return this.cost * (this.getFromVertex().value.hashCode() * this.getToVertex().value.hashCode());
}
/**
* {@inheritDoc}
*/
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object e1) {
if (!(e1 instanceof Edge)) return false;
Edge<T> e = (Edge<T>) e1;
boolean costs = this.cost == e.cost;
if (!costs) return false;
boolean froms = this.from.equals(e.from);
if (!froms) return false;
boolean tos = this.to.equals(e.to);
if (!tos) return false;
return true;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("edge:").append(" [").append(from.value).append("]").append(" -> ").append("[").append(to.value).append("]").append(" = ")
.append(cost).append("\n");
return builder.toString();
}
}
public static class CostVertexPair<T extends Comparable<T>> implements Comparable<CostVertexPair<T>> {
private int cost = Integer.MAX_VALUE;
private Vertex<T> vertex = null;
public CostVertexPair(int cost, Vertex<T> vertex) {
if (vertex == null) throw (new NullPointerException("vertex cannot be NULL."));
this.cost = cost;
this.vertex = vertex;
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;
}
public Vertex<T> getVertex() {
return vertex;
}
/**
* {@inheritDoc}
*/
@Override
public int compareTo(CostVertexPair<T> p) {
if (p == null) throw new NullPointerException("CostVertexPair 'p' must be non-NULL.");
if (this.cost < p.cost) return -1;
if (this.cost > p.cost) return 1;
return 0;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Vertex=").append(vertex.getValue()).append(" cost=").append(cost).append("\n");
return builder.toString();
}
}
public static class CostPathPair<T extends Comparable<T>> {
private int cost = 0;
private Set<Edge<T>> path = null;
public CostPathPair(int cost, Set<Edge<T>> path) {
if (path == null) throw (new NullPointerException("path cannot be NULL."));
this.cost = cost;
this.path = path;
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;
}
public Set<Edge<T>> getPath() {
return path;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Cost = ").append(cost).append("\n");
for (Edge<T> e : path) {
builder.append("\t").append(e);
}
return builder.toString();
}
}
}
// We need this for the Stack class.
import java.util.*;
class ExprTreeNode {
ExprTreeNode left, right; // The usual pointers.
boolean isLeaf; // Is this a leaf?
int value; // If so, we'll store the number here.
char op; // If not, we need to know which operator.
}
class ExpressionTree {
ExprTreeNode root;
public void parseExpression (String expr)
{
root = parse (expr);
}
ExprTreeNode parse (String expr)
{
ExprTreeNode node = new ExprTreeNode ();
// Note: expr.charAt(0) is a left paren.
// First, find the matching right paren.
int m = findMatchingRightParen (expr, 1);
String leftExpr = expr.substring (1, m+1);
// Bottom-out condition:
if (m == expr.length()-1) {
// It's at the other end => this is a leaf.
String operandStr = expr.substring (1, expr.length()-1);
node.isLeaf = true;
node.value = getValue (operandStr);
return node;
}
// Otherwise, there's a second operand and an operator.
// Find the left paren to match the rightmost right paren.
int n = findMatchingLeftParen (expr, expr.length()-2);
String rightExpr = expr.substring (n, expr.length()-1);
// Recursively parse the left and right substrings.
node.left = parse (leftExpr);
node.right = parse (rightExpr);
node.op = expr.charAt (m+1);
return node;
}
int findMatchingRightParen (String s, int leftPos)
{
Stack<Character> stack = new Stack<Character>();
stack.push (s.charAt(leftPos));
for (int i=leftPos+1; i<s.length(); i++) {
char ch = s.charAt (i);
if (ch == '(') {
stack.push (ch);
}
else if (ch == ')') {
stack.pop ();
if ( stack.isEmpty() ) {
// This is the one.
return i;
}
}
}
// If we reach here, there's an error.
System.out.println ("ERROR: findRight: s=" + s + " left=" + leftPos);
return -1;
}
int findMatchingLeftParen (String s, int rightPos)
{
Stack<Character> stack = new Stack<Character>();
stack.push (s.charAt(rightPos));
for (int i=rightPos-1; i>=0; i--) {
char ch = s.charAt (i);
if (ch == ')') {
stack.push (ch);
}
else if (ch == '(') {
stack.pop ();
if ( stack.isEmpty() ) {
// This is the one.
return i;
}
}
}
// If we reach here, there's an error.
System.out.println ("ERROR: findLeft: s=" + s + " right=" + rightPos);
return -1;
}
int getValue (String s)
{
try {
int k = Integer.parseInt (s);
return k;
}
catch (NumberFormatException e) {
return -1;
}
}
public int computeValue ()
{
return compute (root);
}
int compute (ExprTreeNode node)
{
if (node.isLeaf) {
return node.value;
}
// Otherwise do left and right, and add.
int leftValue = compute (node.left);
int rightValue = compute (node.right);
if (node.op == '+') {
return leftValue + rightValue;
}
else if (node.op == '-') {
return leftValue - rightValue;
}
else if (node.op == '*') {
return leftValue * rightValue;
}
else {
return leftValue / rightValue;
}
}
public String convertToPostfix ()
{
String str = postOrder (root);
return str;
}
String postOrder (ExprTreeNode node)
{
String result = "";
if (node.left != null) {
result += postOrder (node.left);
}
if (node.right != null) {
result += " " + postOrder (node.right);
}
if (node.isLeaf) {
result += " " + node.value;
}
else {
result += " " + node.op;
}
return result;
}
}
class PostfixEvaluator {
public int compute (String postfixExpr)
{
// Create a stack: all our operands are integers.
Stack<Integer> stack = new Stack<Integer>();
// Use the Scanner class to help us extract numbers or operators:
Scanner scanner = new Scanner (postfixExpr);
while (scanner.hasNext()) {
if (scanner.hasNextInt()) {
// It's an operand => push it on the stack.
int N = scanner.nextInt();
stack.push (N);
}
else {
// It's an operator => apply the operator to the top two operands
String opStr = scanner.next();
int b = stack.pop(); // Note: b is popped first.
int a = stack.pop();
if (opStr.equals("+")) {
stack.push (a+b);
}
else if (opStr.equals("-")) {
stack.push (a-b);
}
else if (opStr.equals("*")) {
stack.push (a*b);
}
else if (opStr.equals("/")) {
stack.push (a/b);
}
}
} // end-while
// Result is on top.
return stack.pop();
}
}
public class ExpressionParser {
public static void main (String[] argv)
{
String s = "((1)+(2))";
test (s);
s = "(((1)+(2))*(3))";
test (s);
s = "(((35)-((3)*((3)+(2))))/(4))";
test (s);
}
static void test (String s)
{
ExpressionTree expTree = new ExpressionTree ();
expTree.parseExpression (s);
int v = expTree.computeValue ();
System.out.println (s + " = " + v);
String postStr = expTree.convertToPostfix ();
PostfixEvaluator postfixEval = new PostfixEvaluator();
int p = postfixEval.compute (postStr);
System.out.println ("Postfix: " + postStr + " postfix eval=" + p);
}
}
Algorithm: put every character from the first string in a hash table, which has char as key and value - int which shows the number of times the char occurs.
Iterate through the second string and remove all matching characters from the hash table, if there is no match - the strings are not anagrams. If after the iterations there is some value in the table - then they are not anagrams otherwise they are.
import java.util.Hashtable;
import java.io.Console;
public class Anagrams {
public static void main(String[] args) {
System.out.println("Example \"The eyes\" and \"They see\"");
String str1;
String str2;
Console console = System.console();
str1 = console.readLine("Enter the first string: ");
str2 = console.readLine("Enter the second string: ");
if (isAnagrams(str1.toLowerCase(), str2.toLowerCase())) {
System.out.println("Anagrams");
} else
System.out.println("Not anagrams");
}
private static boolean isAnagrams(String str1, String str2) {
if(str1==null || str2==null) throw new NullPointerException("s1 or s2");
Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
for (char c : str1.toCharArray()) {
if(c==' ')
{
continue;
}
if (ht.containsKey(c))
ht.put(c, ht.get(c) + 1);
else
ht.put(c, 1);
}
for (char c : str2.toCharArray()) {
if(c==' ')
{
continue;
}
if(!ht.containsKey(c))
return false;
else {
if (ht.get(c) > 1)
ht.put(c, ht.get(c) - 1);
else
ht.remove(c);
}
}
if (!ht.keys().hasMoreElements())
return true;
return false;
}
}
Algorithm: Iterate through the string and for every element except the start and the last one check his two neighbouring elements. If they are different characters - then this is the unique character. The firs and the last element must be compared only with their closest neighbour - only one element each.
public class FirstNRC {
public static void main(String[] args) {
String str ="aabbbccccddeffffgg";
System.out.println(FindFirstNonChar(str));
}
private static Character FindFirstNonChar(String str)
{
if(str.length()==0)
return ' ';
if(str.charAt(0)!=str.charAt(1))
return str.charAt(0);
for(int i=1; i<str.length()-1; i++)
{
if(str.charAt(i)!=str.charAt(i-1)&&str.charAt(i)!=str.charAt(i+1))
return str.charAt(i);
}
if(str.charAt(str.length()-1)!=str.charAt(str.length()-2))
{
return str.charAt(str.length()-1);
}
return ' ';
}
}
I can not tell the exact algorithm, but I am sure that if you build a suffix tree, which can be done on linear time, then checking if the second string is in the tree is also linear and as far as I remember it was very easy to get the node of the tree which points to the start of the string.
- Lyubomir December 08, 2012this functions prints all the permutations of a given string
import java.util.Hashtable;
import java.io.Console;
public class PermutationsString
{
public static void main(String[] args)
{
System.out.println("Example \"The eyes\" and \"They see\"");
String str1;
Console console = System.console();
str1 = console.readLine("Enter the first string: ");
permutations(str1);
}
private static void permutations(String str)
{
permutation("", str);
}
private static void permutation(String prefix, String str)
{
int n = str.length();
if (n == 0)
{
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));
}
}
}
}
We can do it with quicksort. There in the partition subroutine we know which elements in the linked list we have to swap, because we have them when traversing from the beginning to the pivot element and from the end to the pivot element. This will be O(n logn) time without additional memory usage.
- Lyubomir December 08, 2012import java.util.Hashtable;
import java.io.Console;
import java.util.*;
import java.io.*;
import java.lang.*;
public class Reverse {
public static void main(String[] args) {
String str1;
Console console = System.console();
str1 = console.readLine("Enter the string: ");
//reverse the whole string
String s=reverseString(str1);
//split the string and reverse all the substrings
String[] strArr = s.split(" ");
// StringBuilder sb = new StringBuilder();
String result = new String();
for(String part:strArr)
{
result += reverseString(part) + " ";
}
System.out.println(result);
}
// 12345 6789
// 9876 54321
// 6789 12345
private static String reverseString(String str)
{
char[] ch = str.toCharArray();
int i=0;
int j = ch.length-1;
char c;
while (i<j)
{
c = ch[j];
ch[j] = ch[i];
ch[i] = c;
i++;
j--;
}
return new String(ch);
}
}
We can write insertion sort algorithm very easily for linked lists.
Algorithm:
While(index of unsorted linklist is not at an element pointing null- the last element)
{
1. Search for the biggest element one, after the other element
2. After the biggest element is found, remove it from the list and append it to the beginning of the list.
}
The complexity is O(n) like the implementation with arrays. The deletion of element in the list and insertion takes linear time.
public class MergeSorted {
public static void main(String[] args) {
int[] arr1 = { 1, 2, 12, 33, 35, 36 };
int[] arr2 = { 13, 20, 40, 60 };
int[] arr3 = new int[arr1.length + arr2.length];
int i, j, x = 0;
for (i = 0, j = 0; i < arr1.length && j < arr2.length;) {
System.out.println("i: " + i + " j: " + j);
if (arr1[i] < arr2[j])
arr3[x++] = arr1[i++];
else
arr3[x++] = arr2[j++];
}
while (i < arr1.length)
arr3[x++] = arr1[i++];
while (j < arr2.length)
arr3[x++] = arr2[j++];
for (int z : arr3) {
System.out.println(z);
}
}
}
- 0
RepRitterNicole, DIGITAL MARKETING at Arista Networks
I am Ritter, Experimental psychologist refers to work done who apply experimental methods to psychological study and the processes that ...
What do you mean by "user request"?
- Lyubomir August 19, 2013