Mock Interview: Microsoft

Sort Colors

class Solution {
    public void sortColors(int[] nums) {
        int zero = 0;
        int two = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zero++;
            } else if (nums[i] == 2) {
                two++;
            }
        }
        
        for (int j = 0; j < zero; j++) {
            nums[j] = 0;
        }
        
        for (int k = zero; k < nums.length - two; k++) {
            nums[k] = 1;
        }
        
        for (int l = nums.length - two; l < nums.length; l++) {
            nums[l] = 2; 
        }
        
        
    }
}

^^... not one pass

class Solution {
    public void sortColors(int[] nums) {
        int r = 0;
        int b = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) r++;
            else if (nums[i] == 2) b++;
        }
        int w = nums.length - r - b;
        
        for (int j = 0; j < nums.length; j++) {
            if (j < r) {
                nums[j] = 0;
            } else if (j < nums.length - b) {
                nums[j] = 1;
            } else {
                nums[j] = 2; 
            }
        }
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Colors.
Memory Usage: 37.6 MB, less than 46.63% of Java online submissions for Sort Colors.

다행이 생각났네요^^

Remove K digits

class Solution {
    public String removeKdigits(String num, int k) {
        
        
    }
}

^^... RG~?

루션이

class Solution {
  public String removeKdigits(String num, int k) {
    LinkedList<Character> stack = new LinkedList<Character>();
        
    for(char digit : num.toCharArray()) {
      while(stack.size() > 0 && k > 0 && stack.peekLast() > digit) {
        stack.removeLast();
        k -= 1;
      }
      stack.addLast(digit);
    }
        
    /* remove the remaining digits from the tail. */
    for(int i=0; i<k; ++i) {
      stack.removeLast();
    }
        
    // build the final string, while removing the leading zeros.
    StringBuilder ret = new StringBuilder();
    boolean leadingZero = true;
    for(char digit: stack) {
      if(leadingZero && digit == '0') continue;
      leadingZero = false;
      ret.append(digit);
    }
        
    /* return the final string  */
    if (ret.length() == 0) return "0";
    return ret.toString();
  }
}

뭔소리여;;;;