目录

程序员子悠 · 好记性不如烂笔头

技术人生 X 人生技术

X

The 15th Week of ARTS:KthLargest Element in a Stream_703

   
    0 0 zhuSilence

Introduction

  • Algorithm - Learning Algorithm
  • Review - Learning English
  • Tip - Learning Techniques
  • Share - Learning Influence

Let's do it!!!

Algorithm

KthLargest Element in a Stream

  1. Description

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

  1. My Solution
package com.silence.arts.leetcode.stack;

import java.util.PriorityQueue;

/**
 * <br>
 * <b>Function：</b><br>
 * <b>Author：</b>@author Silence<br>
 * <b>Date：</b>2018-12-01 16:04<br>
 * <b>Desc：</b>无<br>
 */
public class KthLargest_703 {

    /**
     * PriorityQueue is kind of MINI Heap structure
     */
    private PriorityQueue<Integer> queue;
    private int k;

    public KthLargest_703(int k, int[] nums) {
        this.queue = new PriorityQueue<>(k);
        this.k = k;
        for (int num : nums) {
            add(num);
        }
    }

    /**
     * If the size < k that means we just need to add the element then maintain the Heap
     * else if the peek() < val we need to poll() the head of Heap and add the element then maintain the Heap
     * if the peek() > val we do nothing
     * return the peek()
     *
     * @param val
     * @return
     */
    public int add(int val) {
        if (queue.size() < k) {
            queue.offer(val);
        } else if (queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

Extra spaces keep ListNode

Review

I just got a developer job at Facebook. Here’s how I prepped for my interviews.

Main ideas
  • Algorithm Interviews
  • Architecture Design Interviews
  • Behavioral Interviews
  • Culture Fit
  • Pair Programming
  • Finding and Patching Bugs
  • Testing Domain Knowledge
  • Understanding Operating Systems
Resources
  1. Mock Interviews
  1. Algorithms
  1. Operating Systems
  1. Architecture Design
  1. Behavioural

Tips

Java CAS(Compare And Swap)比较交换

  1. MySql数据库的 InnoDB 引擎的索引采用 B+树存储，之所以采用 B+树是为了减少磁盘的访问，提供查询效率
  2. 主键索引保存的是整行数据，普通索引保存的是主键，索引普通索引的查询比主键搜索的查询多一次树的搜索

Share

Sharing

常用算法笔记——持续更新

One more thing

标题：The 15th Week of ARTS:KthLargest Element in a Stream_703
作者：zhuSilence
地址：https://home.zxsilence.cn/articles/2018/12/01/1570340346710.html