Linkedin Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Why are dynamic programming problems more suited for onsite interviews, as opposed to phone interviews? There are relatively simple algorithms that use Dynamic Programming, no? And why would that make you upset? Did you get a rejection from LinkedIn?
If it's the last, don't worry so much. LinkedIn's data privacy is horrible and I would feel bad for working there. For example, one of my friend's personal data was sold to some of her creditors and they then started calling her contacts about her debt. Just see it all as exercise - no matter if it is an onsite interview or a phone interview. You will always coming out knowing more than before.
I don't understand why don't people write full questions? why do I even have to think about what exactly is the question
i) does the order of words matter?
ii) do we want to minimize total number of trailing spaces or minimize the Max of (for all lines, number of trailing spaces in that line)
This code works fine. Can someone explain to me the complexity of this solution?
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class WordWrap {
static void justifyString(List<String> s, int n) {
char[] charArr = new char[n];
LinkedList<String> just = new LinkedList<String>();
for (String st : s) {
char[] ch = st.toCharArray();
if (st.length() > n) {
just.addLast(st.substring(0, n));
just.addLast(st.substring(n, st.length()));
}
else {
String str = just.peekLast();
if (str == null) {
just.addLast(st);
}
else if (st.length() + str.length() + 1 <= n) {
just.removeLast();
just.addLast(str + " " + st);
}
else {
just.addLast(st);
}
}
}
for(String j : just) {
System.out.println(j);
}
}
public static void main(String args[]) {
List<String> st = new ArrayList<String>();
st.add("aaaaaa");
st.add("bb");
st.add("cc");
st.add("ddd");
justifyString(st, 5);
}
}
This question is very similar to the Text Justification on LeetCode. Unless I understand the problem wrong, this code works fine.
import java.util.ArrayList;
public class TextJustification {
public ArrayList<String> fullJustify(String[] words, int L) {
if (words == null)
throw new NullPointerException("Null string array!");
ArrayList<String> rst = new ArrayList<String> ();
if (words.length == 0)
return rst;
int maxLength = words[0].length();
for (int i = 0; i < words.length; i++) {
maxLength = Math.max(maxLength, words[i].length());
}
if (maxLength > L)
return rst;
int prev_start = 0;
int currSum = 0;
int countWord = 0;
for (int i = 0; i <= words.length; i++) {
if (i == words.length || (currSum + words[i].length() + countWord > L)) {
int totalSpace = L - currSum;
String tmp = "";
if (i == words.length || countWord == 1) {
for (int j = prev_start; j < i; j++) {
tmp += words[j];
if (j != i - 1)
tmp += " ";
}
tmp = appendSpace(tmp, L - tmp.length());
}
else {
int spaceEachWord = totalSpace / (countWord - 1);
int extraSpace = totalSpace % (countWord - 1);
for (int j = prev_start; j < i - 1; j++) {
tmp += words[j];
if (j != i - 1) {
tmp = appendSpace(tmp, spaceEachWord);
}
if (extraSpace > 0) {
tmp += " ";
extraSpace--;
}
}
tmp += words[i - 1];
}
rst.add(tmp);
if (i == words.length)
break;
prev_start = i;
currSum = words[i].length();
countWord = 1;
}
else {
currSum += words[i].length();
countWord++;
}
}
return rst;
}
private String appendSpace(String s, int space) {
String rst = s;
for (int i = 0; i < space; i++)
rst += " ";
return rst;
}
}
public static void justifyString(List<String> s, int n) {
char[] charArr = new char[n];
LinkedList<String> just = new LinkedList<String>();
int nFactor = 0;
for (String st : s) {
char[] ch = st.toCharArray();
nFactor = 0;
if (st.length() > n) {
int t = st.length();
String tmpstr = just.peekLast();
int start = 0;
if(tmpstr != null && tmpstr.length() < n-1)
{
just.removeLast();
just.addLast(tmpstr+" "+st.substring(0, n - tmpstr.length() - 1));
st = st.substring(tmpstr.length()-1, t);
}
while(t > n && st.length() > n)
{
just.addLast(st.substring(0, n));
t-=n;
nFactor++;
}
just.addLast(st.substring(n*nFactor, st.length()));
} else {
String str = just.peekLast();
if (str == null) {
just.addLast(st);
} else if (st.length() + str.length() + 1 <= n) {
just.removeLast();
just.addLast(str + " " + st);
} else {
just.addLast(st);
}
}
}
for (String j : just) {
System.out.println(j);
}
}
Some code samples that were posted earlier do not work for the case when a word's length is two or more times 'n'. For example, it fails in the case of "justification".
The following code fixes the bug:
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class WordWrap {
static void justifyString(List<String> s, int n) {
LinkedList<String> list = new LinkedList<>();
for (String st : s) {
if (st.length() > n) {
list.addLast(st.substring(0, n));
String rem = st.substring(n, st.length());
while(true) {
if(rem.length() <= n) {
list.addLast(rem.substring(0, rem.length()));
break;
}
else {
list.addLast(rem.substring(0, n));
rem = rem.substring(n);
}
}
} else {
String str = list.peekLast();
if (str == null) {
list.addLast(st);
} else if (st.length() + str.length() + 1 <= n) {
list.removeLast();
list.addLast(str + " " + st);
} else {
list.addLast(st);
}
}
}
for (String str : list) {
System.out.println(str);
}
}
public static void main(String[] args) {
WordWrap wp = new WordWrap();
String[] words = new String[]{"Hello", "justification", "string" };
wp.justifyString(Arrays.asList(words), 4);
}
}
Dynamic programming solution:
Say the words are w1, w2, ..., wn.
We start with w1 and try to figure out the best, by adding one word at a time.
Say we have manage to find the best using w1, w2, ..., wk.
Now when we add w(k+1), we pick all j such that wj, w(j+1), ..., w(k+1) form the last sentence.
Thus we compute the best using the already computed best for w1, w2, .., w(j-1) and add to that the cost of making wj, w(j+1), .., w(k+1) the last line.
We do this for each j, and pick the best for k+1.
This is O(n^2) time and O(n) space.
public static void print(ArrayList<String> arr, int length) {
ArrayList<String> curLine = new ArrayList<String>();
int cur = 0;
for (int i = 0; i < arr.size(); i++) {
if (cur + arr.get(i).length() <= length) {
curLine.add(arr.get(i));
cur += arr.get(i).length() + 1;
} else {
int remainSpace = length - cur + 1;
int spacePerword = curLine.size() == 1 ? 0 : remainSpace / (curLine.size() - 1) + 1;
int oneMoreSpace = curLine.size() == 1 ? 0 : remainSpace % (curLine.size() - 1);
for (int j = 0; j < curLine.size(); j++) {
System.out.print(curLine.get(j));
for (int sp = 0; sp < spacePerword; sp++) {
System.out.print(" ");
}
if (oneMoreSpace > 0) {
oneMoreSpace--;
System.out.print(" ");
}
}
System.out.println("");
curLine.clear();
curLine.add(arr.get(i));
cur = arr.get(i).length() + 1;
}
}
if (cur != 0) {
int remainSpace = length - cur + 1;
int spacePerword = curLine.size() == 1 ? 0 : remainSpace / (curLine.size() - 1) + 1;
int oneMoreSpace = curLine.size() == 1 ? 0 : remainSpace % (curLine.size() - 1);
for (int j = 0; j < curLine.size(); j++) {
System.out.print(curLine.get(j));
for (int sp = 0; sp < spacePerword; sp++) {
System.out.print(" ");
}
if (oneMoreSpace > 0) {
oneMoreSpace--;
System.out.print(" ");
}
}
System.out.println("");
}
}
#define N 100
#define L 100
int f[N] = {0};
int m[N] = {0};
for (int i = n - 1; i >= 0; i—)
{
int s = length(word[i]);
f[i] = L - s + f[i+1];
m[i] = j;
for (int j = i + 1; j < n && s + length(word[j]) <= L; j++)
{
s += length(word[j]);
if (f[i] > L - s + f[j+1])
{
f[i] = L - s + f[j+1];
m[i] = j;
}
}
}
return f[0];
Dynamic programming. This is a typical textbook/homework problem on Dynamic Programming. LinkedIn folks are idiots to be asking this in a phone interview (more suited for onsite).
- Anonymous April 07, 2014