Algorithms Forever ...: Circular Swap

Algorithms Forever ...: Circular Swap

Given three numbers a, b and c. Write a program to swap them circularly (as per following example) using only one single statement in any programming language.

Ex. a=10 b=20 c=30
Answer a=20 b=30 c=10

Solution :

a = a^b^c^(b=c)^(c=a);
This is equivalent to a = (a^b^c^c^a) = b along with the values of b and c being changed by b=c and c=a assignments.
This is an excellent answer and defeats the proposed ones in the reference.

Reference :
http://stackoverflow.com/questions/8635686/swap-three-numbers-in-single-statement

The operator ^ is undefined for the argument type(s) float,  float

http://www.dummies.com/how-to/content/assignment-statements-in-java.html

An assignment expression has a return value just as any other expression does; the return value is the value that’s assigned to the variable. For example, the return value of the expression a = 5 is 5. This allows you to create some interesting, but ill-advised, expressions by using assignment expressions in the middle of other expressions. For example:

int a;
int b;
a = (b = 3) * 2;   // a is 6, b is 3

Using assignment operators in the middle of an expression can make the expression harder to understand, so it’s not recommend that.

http://stackoverflow.com/questions/8635686/swap-three-numbers-in-single-statement

You can use this in many languages like C,C++ and Java.

It will work for float and long also.

a=(a+b+c) - (b=c) - (c=a);

http://bryanpendleton.blogspot.com/2009/05/java-assignment-expression.html

Java's "if" statement only accepts boolean-valued expressions in its test, which means that some of the worst types of accidental mistakes from C will not occur in Java; the following code will not compile:

            int i = 2;
            if (i = 3)
                    System.out.println("I is 3.");

However, other rather frightening bits of Java code are legal, and do compile, and require a fair bit of thought to understand. Consider these snippets from the Java Language Specification itself:

int i = 2;
int j = (i=3) * i;
System.out.println(j);
int a = 9;
a += (a = 3);
System.out.println(a);
int b = 9;
b = b + (b = 3);
System.out.println(b);

This code prints 9, 12, and 12. 
public SQLInteger(Integer obj) {
if (isnull = (obj == null))
;
else
value = obj.intValue();
}

if(a=b) // when a, b is boolean variable, it compiles, otherwise not.
Read full article from Algorithms Forever ...: Circular Swap

Given read4k, implement readanysize | Hello World

Given read4k, implement readanysize
Given API: int Read4096(char* buf);

It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file. The return is the number of chars read.

Use above API to Implement API “int Read(char* buf, int n)” which reads any number of chars from the file.
http://www.careercup.com/question?id=14424684
Given read4k, implement readanysize | Hello World
The key here is to maintain a buffer of 4k by your self, and read from this buffer.

public class AnysizeRead {

    private final int SIZE = 4096;

    //assume you are given a method that reads 4k data, implement readanysize method using this method.

    int curr = 0;

    List<Integer> buff = new ArrayList<Integer>();

    public List<Integer> readAnySize(int size) {

        List<Integer> result = new ArrayList<Integer>();

        while(size > 0) { //keep reading until finished reading all the size

            if (curr + size < SIZE) {

                result.addAll(buff.subList(curr, curr + size));

                curr += size;

                size = 0;

            }

            else {

                result.addAll(buff.subList(curr, buff.size()));

                curr = 0;

                size -= SIZE - curr;

                buff = read4k();

            }

        }

        return result;

    }

}

String buffer = null;
int p = 0;

public String read(int n) {
    if (n < 0) {
        return null;
    } else if (n == 0) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        // there is (LENGTH - p) chars left in the local buffer
        if (buffer == null || p == buffer.length()) {
            // no char left in buffer, update buffer
            buffer = GoogleApi.read4096();
            p = 0;
            if (buffer.length() == 0) {
                // finish reading the file (no more input chars)
                break;
            }
        } else {
            int numChars = buffer.length() - p;
            if (numChars >= n) {
                sb.append(buffer.substring(p, p + n));
                p = p + n;
                n = 0;
            } else {
                sb.append(buffer.substring(p));
                p = buffer.length();
                n -= numChars;
            }
        }
    }
    return sb.toString();
}

Read4K problem, followup, how to make it work with multiple calls, 
subsequent call should starts from where the last one ends.

https://github.com/mission-peace/interview/blob/master/src/com/interview/misc/Read4Function.java
public class Read4Function extends Read4{

    class Queue {
        int start;
        int end;
        int count;
        char[] data;
        int size;
        Queue(int size) {
            data = new char[size];
            this.size = size;
        }

        boolean isEmpty() {
            return count == 0;
        }

        void offer(char b) {
            data[start] = b;
            start = (start + 1)%size;
            count++;
        }

        char poll() {
            char d = data[end];
            end = (end + 1)%size;
            count--;
            return d;
        }
    }

    private final Queue queue;
    public Read4Function() {
        queue = new Queue(4);
    }

    public int read(char[] buf, int n) {
        int r = 0;
        while (!queue.isEmpty() && r < n) {
            buf[r++] = queue.poll();
        }

        if (r == n) {
            return r;
        }
        int index = 0;
        int readSize = 0;
        char[] input = null;
        do {
            input = new char[4];
            readSize = read4(input);
            index = 0;
            while(r < n && index < readSize) {
                buf[r++] = input[index++];
            }
        } while (readSize == 4 && r < n);

        while (index < readSize) {
            queue.offer(input[index++]);
        }
        return r;
    }
Read full article from Given read4k, implement readanysize | Hello World

Find duplicate integer in an large integer array | Hello World

Find duplicate integer in an large integer array | Hello World
You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?
4KB memory = 4*8*2^10 bits, which is larger than the 32000, so we can map each integer to one bit and count the duplicates.
The java only support granularity of bytes, so in order to do bit operation, we need to implement bitSet of our own. Here is a sample of implementation, the divide operation could be replaced by bitshift operation.

public class BitSet {

    int [] bitSet;

    public BitSet(int size) {

        bitSet = new int [size/4]; // use integer array to store bitset

    }

     

    public void set(int pos){

        int wordNum = pos/32;

        int offSet = pos%32;

        bitSet[wordNum] |= (0x1 << offSet);

    }

     

    public boolean get(int pos) {

        int wordNum = pos/32;

        int offSet = pos%32;

        return (0x1 & (bitSet[wordNum] >> offSet)) != 0;

    }

}

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/BitSet.java
Read full article from Find duplicate integer in an large integer array | Hello World