Leading Tech Donkey: 2016

Sunday, 26 June 2016

Saturday, 25 June 2016

16. [Technical Interview] [Leetcode] - Minimum Path Sum

This post has been moved to the new and improved blog: http://belugacode.blogspot.ca/2017/02/6-technical-interview-leetcode-minimum.html

Wednesday, 22 June 2016

15. [Technical Interview] [Leetcode] - Counting Bits

You will need to see a table or integers and their binary representation to see a pattern where the formula f[i] = f[i / 2] + i % 2 can solve this question. Help from here: https://leetcode.com/discuss/92609/three-line-java-solution

import java.util.*;

public class HelloWorld{

     public static void main(String []args){
        System.out.println(Arrays.toString(countBits(5)));
     }
     
    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        
        for (int i = 1; i <= num; i++)
        {
            // To understand this logic, you will need to look at
            // a table showing numbers and their binary representation.
            // What you will see if that for a number, if you divide that
            // number by 2, the resulting number and its binary representation
            // will be the same as the current number, and only differentiate
            // by one bit.
            // For example, 10 is 1010 and 11 is 1011. 5 is the resulting number
            // after dividing 10 or 11 by 2. 5 binary representation is
            // 0101. The (i & 1) will determine if you need to add another count
            // for an extra bit or no need to add extra bit. 10 you don't, but 
            // 11 you do.
            result[i] = result[i >> 1] + (i & 1);
        }
        
        return result;
    }
}

14. [Technical Interview] [Leetcode] - Flatten Nested List Iterator

The code won't compile because we don't know the implementation of NestedInteger, but we just need to fill in the NestedInterator constructor, the next() method and the hasNext() method. Will use a stack and will need to traverse backwards because we want to put the end elements in the stack first and the beginning elements in the stack last. This will result in the beginning elements showing up at the top of the stack (LIFO).

import java.util.*;

public class HelloWorld{

     public static void main(String []args){
        System.out.println("Hello World");
     }
     
     /**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<NestedInteger>();
    
    public NestedIterator(List<NestedInteger> nestedList) {
        
        // need to do traversal in reverse because we want the
        // last nested integer elements at the bottom of the stack
        // and the first nested integers at the top of the stack
        for (int i = nestedList.size() - 1; i >= 0; i--)
        {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty())
        {
            NestedInteger current = stack.peek();
            
            // if current is an integer and not a list of integer
            // return true and let next() take care of the popping
            if (current.isInteger())
            {
                return true;
            }
            
            // else current is not an integer, so pop the list of integer off
            // then proceed to pushing each int in the current list of integer
            // to the stack, and let next() pop them later
            stack.pop();
            
            // need to traverse in reverse because we want the last ints in the
            // nested integer to be at the bottom of the stack and the first ints
            // in the nested integer to be at the top of the stack
            for (int i = current.getList().size() - 1; i >= 0; i--)
            {
                stack.push(current.getList().get(i));
            }
        }
        
        return false;
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
}

13. [Technical Interview] Integer Break

You will need to spot the repeating 3 pattern. Followed this link to understand the problem: https://github.com/haoel/leetcode/blob/master/algorithms/cpp/integerBreak/IntegerBreak.cpp

public class HelloWorld{

     public static void main(String []args){
        System.out.println(integerBreak(11));
     }
     
    // For any n greater than 4, so 5 or up, will always see a
    // repeating 3 as the pattern. With each 3, we subtract 3
    // from the original n and eventually we will get a number
    // that is <= 4 and that will be the last number in the multiplication.
    public static int integerBreak(int n) {
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        
        int result = 1;
        
        while (n > 4)
        {
            result = result * 3;
            n = n - 3;
        }
        
        result = result * n;
        return result;
    }
}

12. [Technical Interview] Top K Frequent Elements

You will use a max heap to place the most occurrences of a number at the top of the queue and going down in count.

import java.util.*;

public class HelloWorld{
     public static void main(String []args){
        
        int[] testIntArray = {1, 1, 1, 2, 2, 3};
        List<Integer> result = topKFrequent(testIntArray, 3);
        
        Iterator it = result.iterator();
        while (it.hasNext())
        {
            System.out.println(it.next());
        }
     }
     
    public static List<Integer> topKFrequent(int[] nums, int k) {
        // count the frequency of each number in nums and add
        // them to the map
        Map<Integer, Integer> counterMap = new HashMap<Integer, Integer>();
        for (int num : nums)
        {
            int countValue = counterMap.getOrDefault(num, 0);
            counterMap.put(num, countValue + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> b.getValue()-a.getValue());
        for (Map.Entry<Integer, Integer> entry : counterMap.entrySet())
        {
            pq.offer(entry);
        }
        
        Iterator it = pq.iterator();
       while (it.hasNext())
       {
        System.out.println ( "Value: "+ it.next()); 
       }
        
        List<Integer> result = new LinkedList<Integer>();
        int counter = 0;
        while (counter < k)
        {
            if (result == null)
                System.out.println ("bad result"); 
            if (pq == null)
                System.out.println ("bad pq"); 
            result.add(pq.poll().getKey());
            counter++;
        }
        
        return result;
    }
}

11. [Technical Interview] Given a list of non negative integers, arrange them such that they form the largest number.

Given a list of non negative integers, arrange them such that they form the largest number.

import java.util.*;

public class HelloWorld{
     public static void main(String []args){
        
        int[] testIntArray = {3, 30};
        System.out.println(largestNumber(testIntArray));
     }
     
     public static String largestNumber(int[] nums)
     {
         String result = "";
         String[] numAsStringsArray = new String[nums.length];
         
         for (int i = 0; i < nums.length; i++)
         {
             numAsStringsArray[i] = Integer.toString(nums[i]);
         }
         
         // The lambda expression must be (str1, str2) -> (str2 + str1).compareTo(str1 + str2)
         // because you are comparing str2 to str1. For example, str1 is 3 and str2 is 30.
         // so we must do (str2 + str1).compareTo(str1 + str2) and not (str1 + str2).compareTo(str2 + str1)
         // because we are comparing str2 to str1, so str2 must come before str1 so it will look like
         // 303 compare to 330, compareTo does natural order in ascending order so we want this way

         Arrays.sort(numAsStringsArray, (str1, str2) -> (str2 + str1).compareTo(str1 + str2));
         
         if (numAsStringsArray[0].equals("0"))
         {
             return "0";
         }
         
         StringBuilder sb = new StringBuilder();
         for (String str : numAsStringsArray)
         {
             sb.append(str);
         }
         
        return sb.toString();   
     }
}

Monday, 30 May 2016

10. [Technical Interview] Given an array of integers, return the indices of the two numbers such that they add up to a specific target in Java

You will loop through each number in the given int array. With each number, subtract it from the target number and you will get the complement.

For example, the target is 9 and the first number in the int array is 2. 9 - 2 = 7, so 7 is the complement.

Check if we have seen the complement before.

If no, add the number as the key in the map, and the index i as the value (the index i is the value because the solution wants us to return the index for the answer). The map is used to keep track of previously seen numbers and if the current number has a complement that we have seen already and is currently in our map, we can stop.

If yes (as in the case when the current interation gives us the number 7), this means we have seen the complement 2 before during our iteration, and the complement of 7 in order to add up to 9 is 2. Thus, we found the answer, stop the loop, and the answer will be the current iteration index of i, and the value we get corresponding to the key of the complement 2.

 import java.util.*;  
   
 public class HelloWorld{  
   
   public static int[] twoSum(int[] nums, int target) {  
     Map<Integer, Integer> mapOfAnswers = new HashMap<Integer, Integer>();  
       
     for (int i = 0; i < nums.length; i++)  
     {  
       int complement = target - nums[i];  
         
       if (mapOfAnswers.containsKey(complement))  
       {  
         return new int[] {mapOfAnswers.get(complement), i};  
       }  
         
       mapOfAnswers.put(nums[i], i);  
     }  
       
     throw new IllegalArgumentException("No two sum solution");  
   }  
   
   public static void main(String []args){  
     int[] data = new int[]{2, 7, 11, 15};  
       
     System.out.println(Arrays.toString(twoSum(data, 9)));  
   }  
 }

9. [Technical Interview] Check if two strings are anagrams in Java

You may be asked during an interview how to determine if two strings are anagrams (ie. bob, bbo, obb are anagrams).

You can create an int array that will keep count of each character see in the first string. Then iterate through each character seen in the second string. If at the end, the int array contains zero count for each character, then that means string 1 and string 2 both contains the same occurrence of each character and thus, they are anagrams!

 public class HelloWorld  
 {  
   public static boolean anagram(String first, String second)  
   {  
     // if the lengths of both strings are not the same, then they cannot  
     // be anagrams  
     if (first.length() != second.length())  
       return false;  
       
     // int array to keep count of each character  
     int[] letters = new int[256];  
       
     // increment the count of each character in the first string  
     // that we see  
     for (char c : first.toCharArray())  
     {  
       letters[c]++;  
     }  
       
     // decrement the count of each character we see in the second  
     // string  
     for (char character : second.toCharArray())  
     {  
       letters[character]--;  
     }  
       
     // check to see that each character count is zero and if so,  
     // that means the occurrence of each letter in both strings  
     // are the same, and hence they are anagrams, return false  
     // if we find a letter count that is not 0  
     for (int i : letters)  
     {  
       if (letters[i] != 0)  
         return false;  
     }  
         
     return true;  
   }  
   
    public static void main(String []args){  
     System.out.println(anagram("bob", "bbo"));  
    }  
 }

Friday, 20 May 2016

8. [How-to] Perform a HTTP POST to upload an object as JSON to an online web server in React Native

This post has been moved to the new and improved blog: http://belugacode.blogspot.ca/2017/02/9-how-to-perform-http-post-to-upload.html

7. [How-to] Do or perform a HTTP GET to download a JSON file from online web server in React Native

You will use the fetch networking API and is available in React Native by default.

I followed this guide: https://facebook.github.io/react-native/docs/network.html

The code highlighted in green will show you how to download a json file from an online web server using the fetch api and then show the content of the json in an alert. You can click a button or TouchableOpacity to trigger the downloading (GET request) of the JSON file.

import React, {
  AppRegistry,
  Alert,
  Component,
  View,
  Text,
  AsyncStorage,
  TouchableOpacity,
  Navigator,
  ScrollView,
  Image,
  Dimensions,
  Animated,
  PanResponder,
  StatusBar,
} from 'react-native'

let {height, width} = Dimensions.get('window')

import Splash from './Splash'
import Element from './Element'

export default class App extends Component {
  constructor(props){
    super(props)
    let appData = {
      page1: {
        type: 'View',
        passProps: {style: {flex:1, backgroundColor: 'white'}},
        children: [{
          type: 'TouchableOpacity',
          passProps: {onPress: ()=>this.navigate({pageName: 'page2', navFunction: 'push'}), style: {flex:1, backgroundColor: '#6a6c94', alignItems: 'center', justifyContent: 'center',}},
          children: {
            type: 'Text',
            passProps: {style: {color: 'white'}},
            children: 'Navigate to Page 2'}
          }, {
          type: 'View',
          passProps: {style: {flex:1, backgroundColor: '#dd4444', alignItems: 'center', justifyContent: 'center',}},
          children: {
            type: 'Text',
            passProps: {style: {color: 'white'}},
            children: 'Page 1 Text'}
          },
        ],
      },
      page2: {
        type: 'View',
        passProps: {style: {flex:1, backgroundColor: 'white'}},
        children: {
          type: 'View',
          passProps: {style: {flex:1, backgroundColor: '#6a6c94', alignItems: 'center', justifyContent: 'center',}},
          children: {
            type: 'Text',
            passProps: {style: {color: 'white'}},
            children: 'Page2 first view'
          }
        }
      },
      page3: {
        type: 'View',
        passProps: {style: {flex:1, backgroundColor: 'white'}},
        children: null,
      },
      page4: {
        type: 'View',
        passProps: {style: {flex:1, backgroundColor: 'white'}},
        children: null,
      },
    }
    let appDataString = JSON.stringify(appData, function(key, val) {
    if (typeof val === 'function') {
      return val + ''; // implicitly `toString` it
    }
    return val
    })
    appData = JSON.parse(appDataString)
    this.state = {
      splashScreen: true,
      currentPage: 'page1',
      isStructureMode: true,
      structureFlexAnim: new Animated.Value(2),
      styleFlexAnim: new Animated.Value(1),
      isPlayMode: false,
      dropZoneValues  : null,
      pan             : new Animated.ValueXY(),
      appData: appData,
    }

    this.panResponder = PanResponder.create({
        onStartShouldSetPanResponder    : () => true,
        onPanResponderMove              : Animated.event([null,{
            dx  : this.state.pan.x,
            dy  : this.state.pan.y
        }]),
        onPanResponderRelease           : (e, gesture) => {
            if(this.isDropZone(gesture)){
              let appData = {...this.state.appData}
              delete appData[e.dispatchMarker.slice(-5)]
              this.setState({appData})
            }
            Animated.spring(
                this.state.pan,
                {toValue:{x:0,y:0}}
            ).start()

        }
    })
  }

  downloadjson(){

    // change the url to the path of where you json file is located;
    fetch('http://gerrycao.com/drago/testFile.json', {
      method: 'GET',
      headers: {
        'Accept': 'application/json',
        'Content-Type': 'application/json',
      }
    }).then((response)=>{
        alert(response);
      response.json().then((jsonBody)=>{
        alert(jsonBody);
      })
    })
    .catch((err)=>{
      alert("error getting json");
    })
  }
  componentDidMount(){
    setTimeout(()=>this.setState({
      splashScreen: false
    }), 2000)
  }
  render(){
    if(this.state.splashScreen) {
      // Load App here, and show Splash while we load the app.
      return <Splash />
    }
    return (
      <View style={{flex: 1, backgroundColor: '#404040'}}>
        <StatusBar backgroundColor="black" />
        <View style={{flexDirection: 'row', justifyContent:'flex-end', alignItems: 'center', backgroundColor: '#212121'}}>
          <TouchableOpacity onPress={this.export.bind(this)}>
          <Image source={require('./img/upload.png')} style={{width: 50, height:50}} resizeMode='contain'/>
          </TouchableOpacity>

          <TouchableOpacity onPress={this.downloadjson.bind(this)}>
          <Image source={require('./img/download.png')} style={{width: 50, height:50}} resizeMode='contain'/>
          </TouchableOpacity>

  {/*        <TouchableOpacity onPress={this.addobjecttoapp.bind(this)}>
          <Text style={{color:'black'}}>Add Object to App</Text>
          </TouchableOpacity>*/}
        </View>


        {/*<View style={{flex:1, backgroundColor: 'pink'}}>
          <View style={{flex:1, backgroundColor: 'orange', alignItems: 'center', justifyContent: 'center',}}>
            <Text style={{color: 'blue'}}>Page2 first view</Text>
          </View>
        </View>*/}
        <View style={{flex:1, flexDirection: 'row'}}>
          <View style={{flex:2, flexDirection: 'column', marginRight: 12}}>
            {/*<View style={{flex:65, borderLeftWidth: 18, borderColor: '#dd4444', backgroundColor: '#514d4d', marginTop: 19, elevation: 25}}>
              <ScrollView style={{marginTop: 4, marginBottom: 4}}>
                {this.renderStyleElements()}
              </ScrollView>
            </View>*/}
            <View style={{flex:65, borderLeftWidth: 18, borderColor: this.state.isStructureMode?'#6a6c94':'#dd4444', backgroundColor: '#514d4d', marginTop: 19, elevation: 12}}>
              <ScrollView style={{marginTop: 4, marginBottom: 4}}>
                { this.state.isStructureMode
                  ? this.renderViewElements()
                  : this.renderStyleElements()
                }
              </ScrollView>
            </View>
            <View style={{flex:12, marginTop: 8, marginBottom: 8, flexDirection: 'row', elevation: 12}}>
              <TouchableOpacity onPress={()=>{
                  if(this.state.isPlayMode) {
                    this.setState({isPlayMode: false})
                  } else {
                    this.setState({isPlayMode: true})
                  }
                }}
                style={{flex:1, borderLeftWidth: 18, borderColor: '#009688', backgroundColor: '#514d4d', marginRight: 6, elevation: 12, alignItems: 'center', justifyContent: 'center'}}>
                <Image source={this.state.isPlayMode?require('./img/icon_build.png'):require('./img/icon_preview.png')} style={{width: 80}} resizeMode='contain'/>
              </TouchableOpacity>
              <View onLayout={this.setDropZoneValues.bind(this)}
                style={{flex:1, borderLeftWidth: 18, borderColor: '#009688', backgroundColor: '#514d4d', elevation: 12, alignItems: 'center', justifyContent: 'center'}}>
                  <TouchableOpacity>
                    <Image source={require('./img/icon_delete.png')} style={{width: 80}} resizeMode='contain'/>
                  </TouchableOpacity>
              </View>
            </View>
            <View style={{flex:23, borderLeftWidth: 18, borderColor: '#6a6c94', backgroundColor: '#514d4d', marginBottom: 12, justifyContent: 'center', elevation: 8}}>
              <ScrollView contentContainerStyle={{margin: 8, flexDirection: 'row', flexWrap: 'wrap'}} bounces={false}>
                {this.renderPageThumbnails()}
              </ScrollView>
            </View>
          </View>
          <View style={{flex:3, marginTop: 12, marginBottom:6, width: (width*2)/3, marginLeft: -24, marginRight: 36}}>
            <Image style={{flex:1, width: (width*2)/3}} resizeMode='contain' source={require('./img/phone_mockup.png')} >
              <View style={{flex:1, margin: 70, marginTop: 139, marginBottom: 132}}>
                <Navigator
                  ref='navigator'
                  initialRoute={{name: 'My First Scene', index: 0}}
                  renderScene={(route, navigator) =>
                    <Element {...this.state.appData[route.currentPage || this.state.currentPage]} navigator={navigator} route={route} />
                  }
                />
              </View>
            </Image>
            {/*<Navigator
              ref='navigator'
              initialRoute={{name: 'My First Scene', index: 0}}
              renderScene={(route, navigator) =>
                <Element {...this.state.appData[route.currentPage || 'page1']} navigator={navigator} route={route} />
              }
            />*/}
          </View>
        </View>

        {/*<View style={{height: 70, flexDirection: 'row', backgroundColor: 'grey', alignItems: 'center'}}>
          {this.renderPageThumbnails()}
        </View>*/}

        {/* --- Render bottom two buttons --- */}
        <View style={{height: 44, flexDirection: 'row'}}>
          <Animated.View style={{flex:this.state.structureFlexAnim}}>
            <TouchableOpacity style={{flex:1}} onPress={()=>{
                this.setState({isStructureMode: true})
                Animated.timing(  // Uses easing functions
                  this.state.structureFlexAnim,  // The value to drive
                  {toValue: 2, duration: 200,}  // Configuration
                ).start()
                Animated.timing(  // Uses easing functions
                  this.state.styleFlexAnim,  // The value to drive
                  {toValue: 1, duration: 200,}  // Configuration
                ).start()
              }}>
              <View style={{flex:1, backgroundColor: this.state.isStructureMode?'#6a6c94':'#212121', alignItems: 'center', justifyContent: 'center'}}>
                <Text style={{color: 'white'}}>Structure</Text>
              </View>
            </TouchableOpacity>
          </Animated.View>
          <Animated.View style={{flex:this.state.styleFlexAnim}}>
            <TouchableOpacity style={{flex:1}} onPress={()=>{
                this.setState({isStructureMode: false})
                Animated.timing(  // Uses easing functions
                  this.state.styleFlexAnim,  // The value to drive
                  {toValue: 2, duration: 200,}  // Configuration
                ).start()
                Animated.timing(  // Uses easing functions
                  this.state.structureFlexAnim,  // The value to drive
                  {toValue: 1, duration: 200,}  // Configuration
                ).start()
              }}>
              <View style={{flex:1, backgroundColor: this.state.isStructureMode?'#212121':'#dd4444', alignItems: 'center', justifyContent: 'center'}}>
                <Text style={{color: 'white'}}>Style</Text>
              </View>
            </TouchableOpacity>
          </Animated.View>
        </View>
      </View>
    )
  }
}

AppRegistry.registerComponent('drago', () => App)

Leading Tech Donkey