워드 랩 문제-TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 정책

단어 줄 바꿈 문제는 일련의 단어가 입력으로 주어지면 한 번에 한 줄에 들어갈 수있는 단어의 수를 찾아야한다고 말합니다. 그래서 이렇게하기 위해 우리는 인쇄 된 문서가 멋지게 보이도록 주어진 순서에 브레이크를 넣습니다. Microsoft Office, Libre Office 및 기타 문서 도구와 같은 단어 편집기는 문서를보기 좋게 만들기 위해 줄 바꿈을 사용합니다. 여기서 nice 란 공간을 균등하게 배치하는 것을 의미합니다. 추가 공백이 많은 줄과 적은 양이있는 줄이 없어야합니다.

여기서도 단어 길이가 줄 크기를 초과하지 않는다고 가정합니다. 좀 더 일반적인 것을 만들기 위해 질문에서 const 함수를 (추가 공간 수) ^ 3으로 고려하고 있습니다. 그렇지 않으면 너무 쉬웠을 것입니다. 이 비용 함수는 질문에 따라 다를 수 있습니다.

핀

예

여기서는 단어 수, 단어 크기 및 줄 크기를 입력으로 제공합니다.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6

설명 : 첫 번째 단어는 1 개의 추가 공백이있는 첫 번째 줄에, 두 번째 및 세 번째 단어는 1 개의 추가 공백이있는 두 번째 줄에, 마지막 단어는 추가 공백없이 세 번째 줄에 배치 할 수 있습니다 (마지막 단어 뒤의 공백은 고려하지 않음). 추가 공간으로). 따라서 비용 함수를 사용하여 비용을 3로 찾습니다.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10

설명 : 여기서 우리는 모든 단어를 동일한 줄, 즉 첫 번째 줄에 배치 할 수 있으므로 비용은 1입니다.

줄 바꿈 문제에 대한 접근 방식

가장 먼저 떠오르는 접근 방식은 단순히 단어를 한 줄에 계속 배치하는 탐욕스러운 솔루션입니다. 같은 줄에 단어를 넣을 수 없으면 두 번째 줄로 이동합니다. 이것은 잘 작동하는 것 같지만 문제가 있습니다. 이 알고리즘은 추가 공간을 변경하면 더 나은 글로벌 솔루션으로 끝날 수있는 경우가있을 수 있으므로 최적의 결과를 생성하지 않습니다.

Greedy Approach를 사용한 출력

”cat is an animal”, line size = 6

이해를 돕기 위해 wordSize 대신 단어로 입력을 표시했습니다.

설명 : cat is_

____

동물

여기에는 두 번째 줄에 4 개의 추가 공백이 있고 세 번째 줄에 1 개의 추가 공백이 있습니다.

계산 : 4 ^ 3 + 1 ^ 3 = 65

더 나은 해결책이 있습니다.

고양이___

이다_

동물

총 비용은 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3)으로 65보다 낫습니다.

이제 다음을 사용하여 단어 줄 바꿈 문제를 해결합니다. 동적 프로그래밍. 우리는 문제에 글로벌 최적 솔루션이 필요하다는 것을 알고 있으며 이전 알고리즘은 그 결과 로컬 최적 솔루션을 제공하려고했습니다. 여기에서 각 줄에서 차지하는 추가 공간을 찾을 수 있으므로 각 행에 대한 비용을 각각 찾을 수 있습니다. 한 줄에 남아있는 extraSpace, i에서 j까지의 단어가 한 줄에 묶여 있음을 알려주는 extraSpace 행렬을 유지합니다. 그런 다음이 extraSpace 매트릭스를 사용하여 최소 비용을 찾습니다.

암호

단어 줄 바꿈 문제에 대한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int wordWrap (int wordSize[], int n, int lineSize) 
{ 
  int extraSpace[n+1][n+1];
  int minCost[n+1];

  for (int i=1;i<=n;i++) 
  { 
    extraSpace[i][i] = lineSize - wordSize[i-1];
    for (int j=i+1;j<=n;j++) 
        extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
  }
  
  minCost[0] = 0; 
  for (int i = 1; i <= n; i++) 
  { 
    minCost[i] = INT_MAX;
    for (int j = 1; j <= i; j++) 
    { 
        int cost; // stores cost of storing words[i,j] in single line
        
        //if extraSpace required is negative, then we can't place
        //words[i,j] in a single line, else if we placed our last
        //word, then we don't consider extraSpace, else calculate
        //cost as per given cost function.
        if(extraSpace[j][i]<0)cost = INT_MAX;
        else if(i==n && extraSpace[j][i]>=0)cost = 0;
        else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
        
      if (minCost[j-1] != INT_MAX && cost != INT_MAX
      && (minCost[j-1] + cost < minCost[i])) 
        minCost[i] = minCost[j-1] + cost;
    }
  }
  
  return minCost[n];
} 

int main() 
{
    int t;cin>>t;
    while(t--) {
       int n;cin>>n;
       int wordSize[n];
       for(int i=0;i<n;i++)
            cin>>wordSize[i];
       int lineSize;cin>>lineSize;
       int ans = wordWrap(wordSize, n, lineSize);
       cout<<ans<<endl;
    }
}

28
0
0

워드 랩 문제에 대한 자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{ 
  static int wordWrap (int wordSize[], int n, int lineSize) 
  { 
    int extraSpace[][] = new int[n+1][n+1]; 
    int minCost[] = new int[n+1];
  
    for (int i=1;i<=n;i++) 
    { 
      extraSpace[i][i] = lineSize - wordSize[i-1];
      for (int j=i+1;j<=n;j++) 
          extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
    } 
    
    	minCost[0] = 0; 
    	for (int i = 1; i <= n; i++) 
    	{ 
    		minCost[i] = Integer.MAX_VALUE;
    		for (int j = 1; j <= i; j++) 
    		{ 
    		    int cost; // stores cost of storing words[i,j] in single line
    		    
    		    //if extraSpace required is negative, then we can't place
    		    //words[i,j] in a single line, else if we placed our last
    		    //word, then we don't consider extraSpace, else calculate
    		    //cost as per given cost function.
    		    if(extraSpace[j][i]<0)cost = Integer.MAX_VALUE;
    		    else if(i==n && extraSpace[j][i]>=0)cost = 0;
    		    else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
    		    
    			if (minCost[j-1] != Integer.MAX_VALUE && cost != Integer.MAX_VALUE
    			&& (minCost[j-1] + cost < minCost[i])) 
    				minCost[i] = minCost[j-1] + cost;
    		}
    	}
  
    return minCost[n];
  } 

  public static void main(String args[]) 
  {
      Scanner sc = new Scanner(System.in);
      
      int t = sc.nextInt();
      while(t-- > 0) {
         int n = sc.nextInt();
         int wordSize[] = new int[n];
         for(int i=0;i<n;i++)
              wordSize[i] = sc.nextInt();
         
         int lineSize = sc.nextInt();
         int ans = wordWrap(wordSize, n, lineSize);
         System.out.println(ans);
      }
  }
}

28 
0 
0

복잡성 분석

시간 복잡성 : O (n ^ 2)

여기에서 외부 루프는 1에서 n까지, 내부 루프는 1에서 i로 실행되므로 다항식 시간 복잡도는 O (n ^ 2)입니다.

공간 복잡성 : O (n ^ 2)

여기서 extraSpace 배열은 크기가 N * N 인 2D 배열로, 다항식 공간 복잡도는 O (N ^ 2)입니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러