Spotify Puzzles. Reversed Binary Numbers (Difficulty Level: Easy)

Yi has moved to Sweden and now goes to school here. The first years of schooling she got in China, and the curricula do not match completely in the two countries. Yi likes mathematics, but now… The teacher explains the algorithm for subtraction on the board, and Yi is bored. Maybe it is possible to perform the same calculations on the numbers corresponding to the reversed binary representations of the numbers on the board? Yi dreams away and starts constructing a program that reverses the binary representation, in her mind. As soon as the lecture ends, she will go home and write it on her computer. See Spotify Puzzles.

Task

Your task will be to write a program for reversing numbers in binary. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.

Input

The input contains a single line with an integer N, 1 ≤ N ≤ 1000000000.

Output

Output one line with one integer, the number we get by reversing the binary representation of N.

Sample input 1
13
Sample output 1
11
Sample input 2
47
Sample output 2
61
Java
Time complexity: O(1)
Space complexity: O(1)

public class Solution {
    //full integer range is supported
    public static int reverseBits(int n) {

        if (n == 0) return 0;

        int result = 0;

        while (n != 0) {
            result = (result << 1) + (n & 1); 
            n >>>= 1;
        }

        return result;
    }
}
Go
Time complexity: O(1)
Space complexity: O(1)

package main

import (
	"fmt"
)

func reverseBits(n int) int{
	if n == 0 {
		return 0
	}
	
	res := 0
	for n != 0 {
	        res <<= 1 
            if n & 1 == 1{ 
                res += 1 
            } 
            n >>= 1
	}
	return res
}

Advertisements

K’th Largest Element in Unsorted Array

Given an array and a number k where k is smaller than size of array, find the k’th largest element in the given array. All array elements are distinct.

Examples:

Input: arr[] = {1, 7, 10, 4, 3, 30, 15}
       k = 3
Output: 10

Input: arr[] = {1, 7, 10, 4, 3, 30}
       k = 4
Output: 4

Java (sorting)
Time complexity: O(N log N)
Space complexity: O(1)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        Arrays.sort(nums);
        
        return nums[nums.length-k];
        
    }
}

Java (heap sort)
Time complexity: O(N log N)
Space complexity: O(N)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for (int n : nums){
            q.offer(n);
        }
        
        for (int i = 1; i < k; ++i){
            q.poll();
        }
        
        return q.poll();
        
    }
}

Java (quick select)
Time complexity: O(N)
Space complexity: O(N)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        //shuffle to eliminate worst case running time O(N^2)
        shuffle(nums);

        return findKthLargest(nums, k, 0, nums.length - 1);

    }

    private int findKthLargest(int[] nums, int k, int lo, int hi){
       if (lo <= hi){
            int pivot = partition(nums, lo, hi);

            if (hi - pivot == k - 1){
                return nums[pivot];
            } else if (hi - pivot < k - 1){
                return findKthLargest(nums,k-(hi-pivot+1),lo, pivot - 1);
            } else {
                return findKthLargest(nums,k,pivot + 1, hi);
            }
        }

        return -1;
    }

    private int partition(int[] nums, int lo, int hi){
        if (lo <= hi){
            int i = lo + 1;
            int j = lo + 1;

            while (j <= hi){
                if (nums[j] < nums[lo]){
                    swap(i, j, nums);
                    ++i;
                }
                 ++j;
            }

            swap(lo, i-1, nums);
            return i-1;
        }
        return -1;
    }

    private void shuffle(int[] nums){
        Random r = new Random();
        for (int i = 1; i < nums.length; ++i){
            int j = r.nextInt(i+1);
            swap(i, j, nums);
        }

    }


    private void swap(int i, int j, int[] nums){
        int x = nums[i];
        x ^= nums[j];
        nums[j] = x ^ nums[j];
        nums[i] = x ^ nums[j];
    }
}

Interval Scheduling

Input: set of intervals on the line, represented by pairs of points (ends of intervals).

Output: finding the largest set of intervals such that none two of them overlap.

Java
Time complexity: O(N log N)
Space complexity: O(N)

public class IntervalScheduling {

    static class Interval{
        private int start;
        private int finish;

        public Interval(int start, int finish){
            this.start = start;
            this.finish = finish;
        }

        public int getStart(){
            return start;
        }

        public int getFinish(){
            return finish;
        }

        @Override
        public String toString(){
            return "[" + start + ", " + finish + "]";
        }
    }

    public List<Interval> maxNonOverlap(List<Interval> intervals){
        if (intervals == null || intervals.size() == 0){
            return Collections.EMPTY_LIST;
        }

        intervals.sort((Interval i1, Interval i2)->i1.getFinish() - i2.getFinish());

        List<Interval> res = new ArrayList<>();
        res.add(intervals.get(0));
        int ptr = 1;

        while (ptr < intervals.size()){
            Interval curr = res.get(res.size() - 1);
            while (ptr < intervals.size() && intervals.get(ptr).getStart() < curr.getFinish()){
                ++ptr;
            }
            if (ptr < intervals.size()){
                res.add(intervals.get(ptr++));
            }
        }

        return res;

    }

    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(600, 830));
        intervals.add(new Interval(800, 900));
        intervals.add(new Interval(900, 1100));
        intervals.add(new Interval(900, 1130));
        intervals.add(new Interval(1030, 1400));
        intervals.add(new Interval(1230, 1400));

        List<Interval> nonOverlapIntervals = new IntervalScheduling().maxNonOverlap(intervals);
        System.out.println((Iterable) nonOverlapIntervals);

    }

}

Lintcode. Number of Airplanes in the Sky

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Notice

If landing and flying happens at the same time, we consider landing should happen at first.

 

Java
Time complexity: O(N log N)
Space complexity: O(N)

class Solution {
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) { 
        // write your code here
        if (airplanes == null || airplanes.size() == 0){
            return 0;
        }
        
        int n = airplanes.size();
        int[] start = new int[n];
        int[] land = new int[n];
        
        for (int i = 0; i < n; ++i){
            Interval t = airplanes.get(i);
            start[i] = t.start;
            land[i] = t.end;
        }
        
        Arrays.sort(start);
        Arrays.sort(land);
        
        int maxPlanes = Integer.MIN_VALUE;
        int currPlanes = 0;
        
        int startPtr = 0;
        int landPtr = 0;
        
        while (startPtr < n){
            if (land[landPtr] <= start[startPtr]){
                currPlanes -= 1;
                ++landPtr;
            } else if (start[startPtr] < land[landPtr]){
                currPlanes += 1;
                ++startPtr;    
            } 
            maxPlanes = Math.max(maxPlanes, currPlanes);
        }
        
        return maxPlanes;
        
        
    }
}

Python
Time complexity: O(N log N)
Space complexity: O(N)

class Solution:
    # @param airplanes, a list of Interval
    # @return an integer
    def countOfAirplanes(self, airplanes):
        # write your code here
        if not len(airplanes):
            return 0;
        
        #creates copy of iterable, one may use [].sort() instead   
        start = sorted([plane.start for plane in airplanes])
        land = sorted([plane.end for plane in airplanes])
        
        maxAirplanes = 0
        currAirplanes = 0
        sIdx = 0
        lIdx = 0
        
        while sIdx < len(airplanes):
            if start[sIdx] < land[lIdx]:
                currAirplanes += 1
                sIdx += 1
            else:
                currAirplanes -= 1
                lIdx += 1
                
            maxAirplanes = max(maxAirplanes, currAirplanes)
        
            
        return maxAirplanes;

Detect Cycle in Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return complete cycle path if given graph contains at least one cycle, else return null.

Java
Time complexity: O(V+E)
Space complexity: O(V) + O(h), where h is the longest path on call stack

public class DirectCycle<V>{


    public DirectCycle(){
    }

    public List<DirectedEdge<V>> getCycle(Digraph<V> g){
        if (g == null){
            throw new IllegalArgumentException("Invalid param passed!");
        }
        if (g.V() == 0 || g.E() == 0){
            return new ArrayList<>();
        }

        Set<V> whiteSet = new HashSet<>();//initial set of all vertexes
        Set<V> greySet = new HashSet<>();//vertexes processed on current stack
        Set<V> blackSet = new HashSet<>();//already processed vertexes
        Map<V,V> path = new HashMap<>();

        for (V v : g.getVertexes()){
            whiteSet.add(v);
        }

        while (!whiteSet.isEmpty()){
            V v = whiteSet.iterator().next();

            if (dfs(v, g, whiteSet, greySet, blackSet, path)){
                List<DirectedEdge<V>> cycle = buildCycle(v, path);
                return cycle;
            }
        }

        return null;
    }

    private List<DirectedEdge<V>> buildCycle(V v, Map<V, V> path) {
        List<DirectedEdge<V>> cycle = new ArrayList<>();
        V curr = v;
        while (path.containsKey(curr)){
            cycle.add(new DirectedEdge<V>(curr, path.get(curr)));
            V temp = path.get(curr);
            path.remove(curr);
            curr = temp;
        }
        return cycle;
    }

    private boolean dfs(V v, Digraph<V> g, Set<V> whiteSet, Set<V> greySet, Set<V> blackSet, Map<V,V> path){

        move(whiteSet, greySet, v);

        for (DirectedEdge<V> de : g.adj(v)){

            V neighb = de.to();
            path.put(v, neighb);

            if (blackSet.contains(neighb)){
                continue;
            }

            if (greySet.contains(neighb)){
                return true;
            }

            if (dfs(neighb, g, whiteSet, greySet, blackSet, path)){
                return true;
            }
        }

        move(greySet, blackSet, v);
        return false;

    }

    private void move(Set<V> source, Set<V> dest, V v){
        source.remove(v);
        dest.add(v);
    }

}

Leetcode. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0){
            return -1;
        }
        
        int start = 0;
        int fuel = 0;
        int tank = 0;
        
        for (int i = 0; i < gas.length; ++i){
            fuel += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0){ 
                tank = 0; start = i + 1; 
            } 
        } 
        return fuel >= 0 ? start : -1;
        
    }
}

Go
Time complexity: O(N)
Space complexity: O(1)

func canCompleteCircuit(gas []int, cost []int) int {
    if gas == nil || len(gas) == 0{
        return -1;
    }
    var fuel, tank, start int = 0, 0, 0
    
    for i := 0; i < len(gas); i++ {
        fuel += gas[i] - cost[i]
        tank += gas[i] - cost[i]
        if tank < 0{
            tank = 0
            start = i + 1
        }
    }
    
    if fuel < 0{
        return -1
    } else{
        return start;
    }
}

Leetcode. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]


Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<Integer>();
        
        for (int n : nums){
            int idx = Math.abs(n);
            if (nums[idx-1] < 0){
                res.add(idx);
            }
            nums[idx-1] = ~nums[idx-1] + 1;
        }
        //restore array
        for (int i = 0; i < nums.length; ++i){
            nums[i] = Math.abs(nums[i]);
        }
        return res;
    }
}