Queue<Integer> name = new priority Queue<Integer>();
name.add(23);
name.add(11);
name.add(1);
name.add(17);
System.out.println(name); // not in order, need to remove() one by one
while(name.isEmpty())
{
int temp = name.remove();
System.out.println(temp); // if we remove elements from priority Queue, then print outs are in sorted order as heap sort, because priority Queue is implemented in heap data structure.
}
Note: this third installment in our series on doing your best in interviews. Previously: “How to Rock an Algorithms Interview”and “The Coding Interview”.
One interview that candidates often struggle with is the systems design interview. Even if you know your algorithms and write clean code, that code needs to run on a computer somewhere — and then things quickly get complicated. A truly unbelievable amount of complexity lies beneath something as simple as visiting Google in your browser. While most of that complexity is abstracted away from the end user, as a system designer you have to face it head on, and the more you can handle, the better.
At Palantir, many of our teams give a systems design interview along with an algorithms interview and a couple of coding interviews. We don’t expect anyone to be an expert at all three disciplines (although some are). We’re looking for generalists with depth — people who are good at most things, and great at some. If systems design isn’t your strength, that’s okay, but you should at least be able to talk and reason competently about a complex system.
Read on to learn about what we’re looking for and how you can prepare.
Nominally, this interview appears to require knowledge of systems and a knack fordesign — and it does. What makes it interesting, though, and sets it apart from a coding or an algorithms interview, is that whatever solution you come up with during the interview is just a side effect. What we actually care about is the process.
In other words, the systems design interview is all about communication.
This reflects what actually working at Palantir is like. As engineers we have a tremendous amount of freedom. We aren’t asked to implement fully-specced features. Instead we take ownership of open-ended problems, and it’s our job to come up with the best solution to each. We need people we can trust to do the right thing without a lot of supervision — people who can own large projects and take them consistently in the right direction. Invariably, this means being able to communicate effectively with the people around you. Working on problems with huge scope isn’t something you can do in a vacuum.
Usually we’ll start by asking you to design a system that performs a given task. The prompt will be simple, but don’t be fooled — these problems are wide and bottomless, and the point of the interview is to see how much volume you can cover in 45 minutes.
For the most part, you’ll be steering the conversation. It’s up to you to understand the problem. That might mean asking questions, sketching diagrams on the board, and bouncing ideas off your interviewer. Do you know the constraints? What kind of inputs does your system need to handle? You have to get a sense for the scope of the problem before you start exploring the space of possible solutions. And remember, there is no single right answer to a real-world problem. Everything is a tradeoff.
Systems are complex, and when you’re designing a system you’re grappling with its full complexity. Given this, there are many topics you should be familiar with, such as:
Remember, we’re not looking for mastery of all these topics. We’re looking for familiarity. We just want to make sure you have a good lay of the land, so you know which questions to ask and when to consult an expert.
How do you get better at something? If your answer isn’t along the lines of “practice” or “hard work,” then I have a bridge to sell you. Just like you have to write a lot of code to get better at coding and do a lot of drills to get really good at basketball, you’ll need practice to get better at design. Here are some activities that can help:
The systems design interview can be difficult, but it’s also a place to be creative and to take joy in the imagining of systems unbuilt. If you listen carefully, make sure you fully understand the problem, and then take a clear, straightforward approach to communicating your ideas, you should do fine.
Good luck!
We do a lot of interviewing at Palantir, and let me tell you: it’s hard. I don’t mean that we ask tough questions (although we do). I mean that the task of evaluating a candidate is hard.
The problem? Given a whiteboard and one hour, determine whether the person across from you is someone you’d like to work with, in the trenches, for the next n years. A candidate’s performance during an interview is only weakly correlated with his or her true potential, but we’re stuck with the problem of turning the chickenscratch on the whiteboard into an ‘aye’ or ‘nay’. Sometimes it feels like a high-stakes game of reading tea leaves. Believe me we’re doing our best, but we’re often left the nagging worry that we’re passing up brilliant people who just had a bad day or who didn’t click with a particular problem.
In an effort to improve this situation, we wanted to write up a guide that will help candidates make sense of this process, or at least the part known as an Algorithms Interview. At Palantir we ask questions that test for a lot of different skills — coding, design, systems knowledge, etc. — but one of our staple interviews is to ask you to design an algorithm to solve a particular problem.
It usually starts like this:
Given X, figure out an efficient way to do Y.
First: Make sure you understand the problem. You’re not going to lose points asking for clarifications or talking through the obvious upfront. This will also buy you time if your brain isn’t kicking in right away. Nobody expects you to solve a problem in the first 30 seconds or even the first few minutes.
Once you understand the problem, try to come up with a solution – any solution whatever. As long as it’s valid, it doesn’t matter if your solution is trivial or ugly or extremely inefficient. What matters is that you’ve made progress. This does two things: (1) it forces you to engage with the structure of the problem, priming your brain for improvements you can make later, and (2) it gives you something in the bank, which will in turn give you confidence. If you can achieve a brute force solution to a problem, you’ve cleared a major hurdle to solving it in a more efficient way.
Now comes the hard part. You’ve given an O(n^3) solution and your interviewer asks you to do it faster. You stare at the problem, but nothing’s coming to you. At this point, there are a few different moves you can make, depending on the problem at hand and your own personality. Almost all of these can help on almost any problem:
You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) What are the common caveats? (Hashing is tricky, and usually takes O(k) time when k is the size of the object being hashed.) What algorithms tend to go along with each data structure? (Dijkstra’s for a graph.) But when you understand these data structures, sometimes the solution to a problem will pop into your mind as soon as you even think about using the right one.
Looking at the problem as a composition of smaller problems may also be helpful. For example, “find a number in a sorted array which has been shifted cyclically by an unknown constant k” can be solved by (1) first figuring out “k” and then (2) figuring out how to perform binary search on a shifted array).
Incidentally, trying out a few different approaches (rather than sticking with a single approach) tends to work well in interviews, because the problems we choose for an interview usually have many different solutions. Happily, the same is true for the problems we solve on the job =)
Note: this part is part two of our series on doing your best in interviews. Part one: “How to Rock an Algorithms Interview”.
Here at Palantir algorithms are important, but code is our lifeblood. We live and die by the quality of the code we ship. It’s no surprise, then, that coding ability is what we stress the most in our interview process. A candidate can get by with mediocre algorithm skills (depending on the role), but no one can skimp on coding.
Suppose you’re confident in your ability to write great software. Your task in a coding interview (of which there will be several) is to show the interviewers that you in fact do have the programming chops — that you’re an experienced coder who knows how to write solid, production-quality code.
This is easier said than done. After all, coding in your favorite IDE from the comfort of$familiar_place is very different from coding on a whiteboard (on a problem you’re totally unfamiliar with) in a pressure-filled 45-minute interview. We realize that the interview environment is not the real world, and we adjust our expectations accordingly. Nonetheless, there are a number of things you can do to put your best foot forward during the interview.
First, though, we’d like to give you a sense for what we look for during a coding interview. Most important is the ability to write clean and correct code — it’s not enough just to be correct. A lot of people will be interacting with your code once you’re on the job, so it should be readable, maintainable, and extensible where appropriate. If your solution is clean and correct, and you produced it in a reasonable amount of time without a lot of help, you’re in good shape. But even if you stumble a bit, there are other ways to demonstrate your ability. As you work, we also watch for debugging ability, problem-solving and analytical skills, creativity, and an understanding of the ecosystem that surrounds production code.
With our evaluation criteria in mind, here are some suggestions we hope will help you perform at your very best.
str.length()-suffix.length(), don’t just assume you know where that index will land; actually do the math and make sure the value is what you were hoping for.As an addendum, here are a few suggestions for books we like about the art of software construction:
An interface is a contract: the guy writing the interface say “hey, I accept things looking that way“, and the guy using the interface says “OK, the class I write looks that way“.
An interface is an empty shell, there are only the signatures (name / params / return type) of the methods. The methods do not contain anything. The interface can’t do anything. It’s just a pattern.
E.G (pseudo code):
// I say all motor vehicles should look like that :
interface MotorVehicle
{
void run();
int getFuel();
}
// my team mate complies and write vehicle looking that way
class Car implements MotorVehicle
{
int fuel;
void run()
{
print("Wrroooooooom");
}
int getFuel()
{
return this.fuel;
}
}
Implementing an interface consume very little CPU, because it’s not a class, just a bunch of names, and therefor there is no expensive lookup to do. It’s great when it matters such as in embedded devices.
Abstract classes, unlike interfaces, are classes. There are more expensive to use because there is a lookup to do when you inherit from them.
Abstract classes look a lot like interfaces, but they have something more : you can define a behavior for them. It’s more about a guy saying “these classes should look like that, and they got that in common, so fill in the blanks!”.
e.g:
// I say all motor vehicles should look like that :
abstract class MotorVehicle
{
int fuel;
// they ALL have fuel, so why let others implement that ?
// let's make it for everybody
int getFuel()
{
return this.fuel;
}
// that can be very different, force them to provide their
// implementation
abstract void run();
}
// my team mate complies and write vehicle looking that way
class Car extends MotorVehicle
{
void run()
{
print("Wrroooooooom");
}
}
While abstract classes and interfaces are supposed to be different concepts, the implementations make that statement sometimes untrue. Sometimes, they are not even what you think they are.
In Java, this rule is strongly enforced, while in PHP, interfaces are abstract classes with no method declared.
In Python, abstract classes are more a programming trick you can get from the ABC module and is actually using metaclasses, and therefore classes. And interfaces are more related to duck typing in this language and it’s a mix between conventions and special methods that call descriptors (the __method__ methods).
As usual with programming, there is theory, practice, and practice in another language 🙂
I was reading about collection framework of Java. And was studying Hashtable, HashMap and HashSet. Its quite interesting to know the differences between them. In this post I will discuss these three with examples.
Hashtable
Hashtable is basically a datastructure to retain values of key-value pair.
|
1
2
3
4
5
6
7
8
|
Hashtable<Integer,String>; cityTable = new Hashtable<Integer,String>();cityTable.put(1, "Lahore");cityTable.put(2, "Karachi");cityTable.put(3, null); /* NullPointerEcxeption at runtime*/System.out.println(cityTable.get(1));System.out.println(cityTable.get(2));System.out.println(cityTable.get(3)); |
HashMap
Like Hashtable it also accepts key value pair.
|
1
2
3
|
HashMap<Integer,String> productMap = new HashMap<Integer,String>();productMap.put(1, "Keys");productMap.put(2, null); |
HashSet
HashSet does not allow duplicate values. It provides add method rather put method. You also use its contain method to check whether the object is already available in HashSet. HashSet can be used where you want to maintain a unique list.
|
1
2
3
4
5
6
7
8
9
|
HashSet<String> stateSet = new HashSet<String>();stateSet.add ("CA");stateSet.add ("WI");stateSet.add ("NY");if (stateSet.contains("PB")) /* if CA, it will not add but shows following message*/ System.out.println("Already found");else stateSet.add("PB"); |
import java.util.Arrays;
public class queueArray {
private int[] queueArray;
private int maxSize;
private int currentSize;
private int front;
private int back;
public queueArray(int size)
{
queueArray=new int[size];
maxSize=size;
currentSize=0;
front=0;
back=0;
}
public void enqueue(int data)
{
if(back==maxSize)
{
back=0;
}
queueArray[back]=data;
back++;
currentSize++;
}
public int dequeue()
{
int temp=queueArray[front];
front++;
currentSize–;
if(front==maxSize)
{
front=0;
}
return temp;
}
public int peekFront()
{
return queueArray[front];
}
public boolean isEmpty()
{
return (currentSize==0);
}
public boolean isFull()
{
return (currentSize==maxSize);
}
public int size()
{
return currentSize;
}
}
http://www.youtube.com/watch?v=7PBH4H2znHg
public class String2Integer {
public static void main(String[] args)
{
System.out.println(String2Integer(“123”));
}
public static Integer String2Integer(String s)
{
int i = 0;
int number=0;
boolean negativeNum=false;
char[] temp = s.toCharArray();
//determine if the number is negative
if(temp[0]==’-‘)
{
negativeNum=true;
i=1;
}
//computing number using Horner’s rule
while(i<temp.length)
{
//number=0
//number=1
//number=10
//number=12
//number=120
//number=123
number*=10;
number+=temp[i]-‘0’;
i++;
}
if(negativeNum) number*=-1;
return number;
}
}
與通用式相關的方法可列表如下：
| 與通用式相關的方法 | 功能 |
|---|---|
| re.exec(string) | 從字串 string 抽取符合通用式 re 的子字串，並以字串陣列傳回 |
| re.test(string) | 以字串 string 比對通用式 re，並傳回比對結果（true 代表比對成功，false 代表比對失敗） |
| string.search(re) | 通用式 re 在某個字串 string 出現的位置 |
| string.match(re) | 從字串 string 抽取符合通用式 re 的子字串，並以字串陣列傳回，此功能和 re.exec(string) 相同 |
| string.replace(re, newStr) | 將字串 string 符合通用式 re 的部分，代換為 newStr |
在下列的表格中，我們使用幾個簡單的範例來對通用式的應用做較完整的說明：
| 通用式 | 說明及範例 | 比對不成立之字串 |
|---|---|---|
| /a/ | 含字母 “a” 的字串，例如 “ab”, “bac”, “cba” | “xyz” |
| /a./ | 含字母 “a” 以及其後任一個字元的字串，例如 “ab”, “bac”（若要比對.，請使用 \.） | “a”, “ba” |
| /^xy/ | 以 “xy” 開始的字串，例如 “xyz”, “xyab”（若要比對 ^，請使用 \^） | “axy”, “bxy” |
| /xy$/ | 以 “xy” 結尾的字串，例如 “axy”, “abxy”以 “xy” 結尾的字串，例如 “axy”, “abxy” （若要比對 $，請使用 \$） | “xya”, “xyb” |
| /[13579]/ | 包含 “1” 或 “3” 或 “5” 或 “7” 或 “9” 的字串，例如：”a3b”, “1xy” | “y2k” |
| /[0-9]/ | 含數字之字串 | 不含數字之字串 |
| /[a-z0-9]/ | 含數字或小寫字母之字串 | 不含數字及小寫字母之字串 |
| /[a-zA-Z0-9]/ | 含數字或字母之字串 | 不含數字及字母之字串 |
| /b[aeiou]t/ | “bat”, “bet”, “bit”, “bot”, “but” | “bxt”, “bzt” |
| /[^0-9]/ | 不含數字之字串（若要比對 ^，請使用 \^） | 含數字之字串 |
| /[^aeiouAEIOU]/ | 不含母音之字串（若要比對 ^，請使用 \^） | 含母音之字串 |
| /[^\^]/ | 不含 “^” 之字串，例如 “xyz”, “abc” | “xy^”, “a^bc” |
請注意在上表中，”^” 在兩條斜線中，代表一個字串的開始位置，因此 /^xy/ 代表以 “xy” 開始的字串。 同理，””在兩條斜線中，代表一個字串的結束位置，因此/xy/ 代表以 “xy” 結束的字串。 但是如果將 “^” 放在兩個方括弧中，就代表「否定」，因此 [^aeiouAEIOU] 代表不含母音之字元。
另外，若要避掉特殊字元的特殊意義，就要在此字元前加上 “\”，例如上表中的最後一列，”^” 在方括弧裡面是代表「否定」，因此若要在方括弧裡面比對 “^”，就要使用 “\^”，所以「不含 “^” 之字串」的通用式就是 “[^\^]”。
以 RegExp(pattern, flag) 的方式來建立通用式物件時，若 pattern 包含以反斜線開頭的特殊字元（例如 \d、\w、\s 等）時，我們必須再加上一個反斜線來保留其特殊意義。例如：
有些通用式會常被用到，因此已被定義為特定字元，以簡化整體通用式，這些字元可列表說明如下：
| 通用表示法的特定字元 | 說明 | 等效的通用表示法 |
|---|---|---|
| \d | 數字 | [0-9] |
| \D | 非數字 | [^0-9] |
| \w | 數字、字母、底線 | [a-zA-Z0-9_] |
| \W | 非 \w | [^a-zA-Z0-9_] |
| \s | 空白字元 | [ \r\t\n\f] |
| \S | 非空白字元 | [^ \r\t\n\f] |
此外，我們可定義字元的重複次數，如下：
| 通用表示法 | 說明 |
|---|---|
| /a?/ | 零或一個 a（若要比對? 字元，請使用 \?） |
| /a+/ | 一或多個 a（若要比對+ 字元，請使用 \+） |
| /a*/ | 零或多個 a（若要比對* 字元，請使用 \*） |
| /a{4}/ | 四個 a |
| /a{5,10}/ | 五至十個 a |
| /a{5,}/ | 至少五個 a |
| /a{,3}/ | 至多三個 a |
| /a.{5}b/ | a 和 b中間夾五個（非換行）字元 |
相信各位現在已經可以體會到通用表示式的威力了！
以下再對通用式，進行比較完整的列表與說明：
| 字元 | 說明 | 簡單範例 |
|---|---|---|
| \ | 避開特殊字元 | /A\*/ 可用於比對 “A*”，其中 * 是一個特殊字元，為避開其特殊意義，所以必須加上 “\” |
| ^ | 比對輸入列的起始位置 | /^A/ 可比對 “Abcd” 中的 “A”，但不可比對 “aAb” |
| $ | 比對輸入列的結束位置 | /A$/ 可比對 “bcdA” 中的 “A”，但不可比對 “aAb” |
| * | 比對前一個字元零次或更多次 | /bo*/ 可比對 “Good boook” 中的 “booo”，亦可比對 “Good bk” 中的 “b” |
| + | 比對前一個字元一次或更多次，等效於 {1,} | /a+/ 可比對 “caaandy” 中的 “aaa”，但不可比對 “cndy” |
| ? | 比對前一個字元零次或一次 | /e?l/ 可比對 “angel” 中的 “el”，也可以比對 “angle” 中的 “l” |
| . | 比對任何一個字元（但換行符號不算） | /.n/ 可比對 “nay, an apple is on the tree” 中的 “an” 和 “on”，但不可比對 “nay” |
| (x) | 比對 x 並將符合的部分存入一個變數 | /(a*) and (b*)/ 可比對 “aaa and bb” 中的 “aaa” 和 “bb”，並將這兩個比對得到的字串設定至變數 RegExp.1和RegExp.2。 |
| x|y | 比對 x 或 y | /a+|b+/g 可比對 “aaa k bb” 中的 “aaa” 和 “bb” |
| {n} | 比對前一個字元 n 次，n 為一個正整數 | /a{3}/ 可比對 “lllaaalaa” 其中的 “aaa”，但不可比對 “aa” |
| {n,} | 比對前一個字元至少 n 次，n 為一個正整數 | /a{3,}/ 可比對 “aa aaa aaaa” 其中的 “aaa” 及 “aaaa”，但不可比對 “aa” |
| {n,m} | 比對前一個字元至少 n 次，至多 m 次，m、n 均為正整數 | /a{3,4}/ 可比對 “aa aaa aaaa aaaaa” 其中的 “aaa” 及 “aaaa”，但不可比對 “aa” 及 “aaaaa” |
| [xyz] | 比對中括弧內的任一個字元 | /[ecm]/ 可比對 “welcome” 中的 “e” 或 “c” 或 “m” |
| [^xyz] | 比對不在中括弧內出現的任一個字元 | /[^ecm]/ 可比對 “welcome” 中的 “w”、”l”、”o”，可見出其與 [xyz] 功能相反。（同時請同學也注意 /^/ 與 [^] 之間功能的不同。） |
| [\b] | 比對退位字元（Backspace character） | 可以比對一個 backspace ，也請注意 [\b] 與 \b 之間的差別 |
| \b | 比對英文字的邊界，例如空格 | 例如 /\bn\w/ 可以比對 “noonday” 中的 ‘no’ ; /\wy\b/ 可比對 “possibly yesterday.” 中的 ‘ly’ |
| \B | 比對非「英文字的邊界」 | 例如, /\w\Bn/ 可以比對 “noonday” 中的 ‘on’ , 另外 /y\B\w/ 可以比對 “possibly yesterday.” 中的 ‘ye’ |
| \cX | 比對控制字元（Control character），其中 X 是一個控制字元 | /\cM/ 可以比對 一個字串中的 control-M |
| \d | 比對任一個數字，等效於 [0-9] | /[\d]/ 可比對 由 “0” 至 “9” 的任一數字 但其餘如字母等就不可比對 |
| \D | 比對任一個非數字，等效於 [^0-9] | /[\D]/ 可比對 “w” “a”… 但不可比對如 “7” “1” 等數字 |
| \f | 比對 form-feed | 若是在文字中有發生 “換頁” 的行為 則可以比對成功 |
| \n | 比對換行符號 | 若是在文字中有發生 “換行” 的行為 則可以比對成功 |
| \r | 比對 carriage return | |
| \s | 比對任一個空白字元（White space character），等效於 [ \f\n\r\t\v] | /\s\w*/ 可比對 “A b” 中的 “b” |
| \S | 比對任一個非空白字元，等效於 [^ \f\n\r\t\v] | /\S/\w* 可比對 “A b” 中的 “A” |
| \t | 比對定位字元（Tab） | |
| \v | 比對垂直定位字元（Vertical tab） | |
| \w | 比對數字字母字元（Alphanumerical characters）或底線字母（”_”），等效於 [A-Za-z0-9_] | /\w/ 可比對 “.A _!9” 中的 “A”、”_”、”9″。 |
| \W | 比對非「數字字母字元或底線字母」，等效於 [^A-Za-z0-9_] | /\W/ 可比對 “.A _!9” 中的 “.”、” “、”!”，可見其功能與 /\w/ 恰好相反。 |
| \ooctal | 比對八進位，其中octal是八進位數目 | /\oocetal123/ 可比對 與 八進位的ASCII中 “123” 所相對應的字元值。 |
| \xhex | 比對十六進位，其中hex是十六進位數目 | /\xhex38/ 可比對 與 16進位的ASCII中 “38” 所相對應的字元。 |
yizhaoee 